Memory Constrained Adversarial Hypothesis Testing
It provides theoretical guarantees for hypothesis testing in adversarial settings with limited memory, which is relevant for security and resource-constrained applications.
This paper studies adversarial binary hypothesis testing under memory constraints using finite state machines, deriving matching upper and lower bounds on the minimax asymptotic probability of error as a function of the number of states.
We study adversarial binary hypothesis testing under memory constraints. The test is a time-invariant randomized finite state machine (FSM) with S states. Associated with each hypothesis is a set of distributions. Given the hypothesis, the distribution of each sample is chosen from the set associated with the hypothesis by an adversary who has access to past samples and the history of states of the FSM so far. We obtain upper and lower bounds on the minimax asymptotic probability of error as a function of S. The bounds have the same exponential behaviour in S and match for a class of problems.