Oracle-efficient Hybrid Learning with Constrained Adversaries

The Hybrid Online Learning Problem, where features are drawn i.i.d. from an unknown distribution but labels are generated adversarially, is a well-motivated setting positioned between statistical and fully-adversarial online learning. Prior work has presented a dichotomy: algorithms that are statistically-optimal, but computationally intractable \citep{wu2023expected}, and algorithms that are computationally-efficient (given an ERM oracle), but statistically-suboptimal \citep{pmlr-v247-wu24a}. This paper takes a significant step towards achieving statistical optimality and computational efficiency \emph{simultaneously} in the Hybrid Learning setting. To do so, we consider a structured setting, where the Adversary is constrained to pick labels from an expressive, but fixed, class of functions $\mathcal{R}$. Our main result is a new learning algorithm, which runs efficiently given an ERM oracle and obtains regret scaling with the Rademacher complexity of a class derived from the Learner's hypothesis class $\mathcal{H}$ and the Adversary's label class $\mathcal{R}$. As a key corollary, we give an oracle-efficient algorithm for computing equilibria in stochastic zero-sum games when action sets may be high-dimensional but the payoff function exhibits a type of low-dimensional structure. Technically, we develop a number of novel tools for the design and analysis of our learning algorithm, including a novel Frank-Wolfe reduction with "truncated entropy regularizer" and a new tail bound for sums of "hybrid'' martingale difference sequences.