Oracle-efficient Hybrid Learning with Constrained Adversaries

2026-03-04 · Princewill Okoroafor, Robert Kleinberg, Michael P. Kim arxiv

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 (Wu et al., 2023), and algorithms that are computationally-efficient (given an ERM oracle), but statistically-suboptimal (Wu et al., 2024). This paper takes a significant step towards achieving statistical optimality and computational efficiency 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 $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 $H$ and the Adversary's label class $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 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.

📄 PDF Abstract BibTeX arXiv:2603.04546

Code (0)

등록된 구현이 없습니다.

Tasks

Computational Efficiency

Oracle-Efficient Online Learning for Beyond Worst-Case Adversaries

2022-02-17 · Nika Haghtalab, Yanjun Han, Abhishek Shetty, Kunhe Yang

In this paper, we study oracle-efficient algorithms for beyond worst-case analysis of online learning. We focus on two settings. First, the smoothed analysis setting of [RST11,HRS22] where an adversary is constrained to …

Transductive Learning

Scaling Adversarial Training to Large Perturbation Bounds

2022-10-18 · Sravanti Addepalli, Samyak Jain, Gaurang Sriramanan, R. Venkatesh Babu

The vulnerability of Deep Neural Networks to Adversarial Attacks has fuelled research towards building robust models. While most Adversarial Training algorithms aim at defending attacks constrained within low magnitude L…

Adversarial Defense Adversarial Robustness

Towards Achieving Adversarial Robustness Beyond Perceptual Limits

2021-09-29 · ICML Workshop AML 2021 7 · Sravanti Addepalli, Samyak Jain, Gaurang Sriramanan, Venkatesh Babu Radhakrishnan

The vulnerability of Deep Neural Networks to Adversarial Attacks has fuelled research towards building robust models. While most Adversarial Training algorithms aim towards defending attacks constrained within low magnit…

Adversarial Defense Adversarial Robustness

Zero-Knowledge Federated Learning with Lattice-Based Hybrid Encryption for Quantum-Resilient Medical AI

2026-03-03 · Edouard Lansiaux arxiv

Federated Learning (FL) enables collaborative training of medical AI models across hospitals without centralizing patient data. However, the exchange of model updates exposes critical vulnerabilities: gradient inversion …

Federated Learning

Reducing Oracle Feedback with Vision-Language Embeddings for Preference-Based RL

2026-03-30 · Udita Ghosh, Dripta S. Raychaudhuri, Jiachen Li, Konstantinos Karydis 외 arxiv

Preference-based reinforcement learning can learn effective reward functions from comparisons, but its scalability is constrained by the high cost of oracle feedback. Lightweight vision-language embedding (VLE) models pr…

parameter-efficient fine-tuning Reinforcement Learning