Efficient Robust Learning at the Information-Theoretic Limit

arXiv:2609.17655 · cs.DS, cs.LG, stat.ML · Submitted 2026-09-15 · Read on arXiv

cs.DS, cs.LG, stat.ML

Submitted: 2026-09-15

Updated: 2026-09-15

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Terminology

• Regret — 19× in this paper · explained in 3 episodes
• Adam — 11× in this paper · explained in 2 episodes
• Generalization — 7× in this paper · explained in 13 episodes
• VC Dimension — 7× in this paper · explained in 2 episodes
• Accuracy — 6× in this paper · explained in 1 episode
• Generalization Bounds — 6× in this paper · explained in 2 episodes
• Agnostic Learning — 4× in this paper · explained in 1 episode
• AI Institute for Foundations of Machine Learning — 3× in this paper
• Distribution Shift — 3× in this paper · explained in 6 episodes
• Intrinsic Dimension — 3× in this paper · explained in 2 episodes
• Objective Function — 2× in this paper · explained in 2 episodes
• Reward Function — 2× in this paper · explained in 2 episodes
• Sample Complexity — 2× in this paper · explained in 15 episodes
• Benchmark — 1× in this paper · explained in 2 episodes
• Covariate Shift — 1× in this paper · explained in 2 episodes
• Loss Function — 1× in this paper · explained in 2 episodes

Sources

• Iterative Chow Filtering for Learning with Distribution Shift
• Learning Constant-Depth Circuits in Malicious Noise Models

Related papers

• Cascaded Learned Bloom Filter for Optimizing Model-Filter Size Balance and Fast Rejection
• Edge-Private Matching Kernels Through Local Decoding
• Local Node Differential Privacy
• Cheaper by the Batch: Shared Traversal for Genotype Graph Editing
• Scalable Algorithms for Approximate DNF Model Counting
• On the Approximation Relationship between Optimizing Ratio of Submodular (RS) and Difference of Submodular (DS) Functions