AI & ML
Memory Constrained Adversarial Hypothesis Testing
arXiv math.IT0 views
arXiv:2605.12063v2 Announce Type: replace Abstract: 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 error probability that are tight to within one state. These bounds determine the exact error exponent in S, and coincide under a weak least-favourability condition. For time-invariant deterministic FSMs, we also extend known achievable error-exponent bounds from the non-adversarial Bernoulli setting to the adversarial case with parameters in two separated intervals.
Source:https://arxiv.org/abs/2605.12063PreviousAnalytically Characterized Optimal Power Control for Signal-Level-Integrated Sensing, Computing and Communication in Federated LearningNextImportance Sampling for Event Discovery via Guesswork
Related posts
Kusner's conjecture on equilateral sets is false
0arXiv cs.NA
Nearly Optimal Fixed-Confidence Best-Arm Identification with 1-Bit Feedback
0arXiv stat.ML
When Does On-Policy Interaction Help? Representational Tradeoffs in Value-Based Imitation Learning
0arXiv stat.ML
Disentangling Continuous-Time Latent Dynamics: Identifiability of Latent SDEs via Diffusion Shifts
0arXiv stat.ML
Exact Constrained Decoding for Sequence Models: Controller-Augmented Hidden Markov Models and Beyond
0arXiv stat.ML
Kernel-based potential mean-field games with unbiased random Fourier $U$-statistics
0arXiv stat.ML