Memory Constrained Adversarial Hypothesis Testing

Technical Summary: Memory Constrained Adversarial Hypothesis Testing

Problem Statement
This work investigates binary hypothesis testing under two simultaneous constraints: memory limitations and adversarial sample generation. The detector is modeled as a time-invariant randomized finite state machine (FSM) with a finite state space $S$. Unlike classical settings where samples are independent and identically distributed (i.i.d.) from a fixed distribution, this problem considers a composite hypothesis setting where the underlying distributions belong to closed convex sets $\mathcal{P}_0$ and $\mathcal{P}_1$.

Crucially, the setting is adversarial. An adversary, knowing the true hypothesis ($H=0$ or $H=1$), selects the distribution for each sample $X_n$ from the corresponding set ($\mathcal{P}_0$ or $\mathcal{P}_1$). The adversary's choice is dynamic, depending on the history of past samples and the entire history of the detector's internal states. The goal is to minimize the asymptotic average probability of error, defined as the worst-case error over all possible adversarial strategies, as a function of the number of states $S$.

Methodology and Approach
The authors build upon the foundational work of Hellman and Cover, who studied memory-constrained hypothesis testing for simple hypotheses (single distributions). While Hellman and Cover utilized a "saturable counter" FSM that transitions based on specific letters maximizing the likelihood ratio, this paper generalizes the approach to handle composite and adversarial settings.

1. Generalized FSM Design: Instead of relying on fixed letters $x^+$ and $x^-$ that provide the strongest evidence for one hypothesis over the other (which may not exist or be consistent in an adversarial setting), the proposed FSM utilizes non-negative functions $f_+$ and $f_-$ defined on the alphabet $\mathcal{X}$. The transition probabilities from state $s$ to $s+1$ or $s-1$ are determined by $f_+(x)$ and $f_-(x)$ respectively, subject to $f_+(x) + f_-(x) \leq 1$.
2. Martingale Analysis: Standard analysis of FSMs often relies on stationary distributions. However, the presence of an adaptive adversary can break ergodicity, rendering stationary distribution analysis invalid. To overcome this, the authors employ a martingale-based analysis. They construct specific submartingales and supermartingales (by adjusting the raw state counts with a potential function $V(s)$) to bound the time the FSM spends in boundary states (which determine the decision) versus internal states.
3. Minimax Optimization: The performance bounds are derived by optimizing over the choice of functions $f_+$ and $f_-$. The authors define a generalized exponent $\gamma$ involving a supremum over these functions and a minimum over the adversarial distributions.

Key Contributions and Results
The paper establishes tight upper and lower bounds on the minimax asymptotic probability of error $P^*_e(S)$ for a given number of states $S$.

• Error Bounds: The authors prove that:
  $$P^*_e(S) \geq \frac{1}{1 + \sqrt{\gamma}^{S-1}}$$
  $$P^*_e(S) \leq \frac{1}{1 + \sqrt{C\gamma^{S-2}}}$$
  where $\gamma$ and $C$ are constants derived from the sets $\mathcal{P}_0$ and $\mathcal{P}_1$ via a minimax optimization over functions $f_+, f_-$.
• Exponential Behavior: Both bounds exhibit the same exponential behavior in $S$. Consequently, the error exponent $\Gamma$ is exactly characterized as:
  $$\Gamma = \frac{1}{2} \log \gamma$$
• Weak Least Favourable Distributions (LFD): The paper introduces the concept of a "weak LFD pair" $(p^*, q^*)$. If such a pair exists, the error exponent simplifies to the Hellman-Cover exponent calculated on these specific distributions: $\gamma = \gamma_{HC}(p^*, q^*)$. This generalizes the classical result that the worst-case error in composite testing is determined by the "least favourable" distributions.
• Optimality of Non-Indicator Functions: Through a specific example, the authors demonstrate that the optimal functions $f_+$ and $f_-$ are not necessarily indicator functions (which would correspond to selecting specific letters). In some cases, linear combinations of letters (represented by non-binary functions) yield a strictly better error exponent than any strategy restricted to fixed subsets of the alphabet.
• Minimax Theorem Application: A significant technical contribution is the proof that the order of minimization (over distributions) and maximization (over functions) can be interchanged in the definition of $\gamma$, despite the function not being jointly quasi-convex/concave in the standard sense. This is achieved by decomposing the problem and applying Sion's minimax theorem iteratively.

Significance
The paper provides a rigorous characterization of the fundamental limits of statistical inference when both memory is constrained and the data source is actively adversarial. It extends the classical Hellman-Cover framework to a more robust and realistic setting where distributions are unknown and potentially manipulated. The work highlights that in adversarial environments, simple "hard" decisions based on single symbols are suboptimal; instead, randomized transitions based on weighted combinations of observations are necessary to achieve the optimal error exponent. The results offer a precise understanding of how the number of memory states $S$ scales with the difficulty of the hypothesis testing problem under worst-case conditions.