# Optimal Learners for Realizable Regression: PAC Learning and Online Learning

arXiv: https://arxiv.org/abs/2307.03848 · HTML: https://mlsanity.com/paper/2307.03848/

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- Builds on 38 of its 82 references that are in the map.
- First posted on arXiv 7 Jul 2023.

## Builds on (most cited first, 30 of 38)

- [Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/2002.04926/) (2020)
- [Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizability](https://mlsanity.com/paper/2003.12699/) (2020)
- [VC Classes are Adversarially Robustly Learnable, but Only Improperly](https://mlsanity.com/paper/1902.04217/) (2019)
- [The Optimal Sample Complexity of PAC Learning](https://mlsanity.com/paper/1507.00473/) (2015)
- [A Characterization of Multiclass Learnability](https://mlsanity.com/paper/2203.01550/) (2022)
- [Optimal Learners for Multiclass Problems](https://mlsanity.com/paper/1405.2420/) (2014)
- [An Equivalence Between Private Classification and Online Prediction](https://mlsanity.com/paper/2003.00563/) (2020)
- [A Theory of Universal Learning](https://mlsanity.com/paper/2011.04483/) (2020)
- [A Theory of PAC Learnability of Partial Concept Classes](https://mlsanity.com/paper/2107.08444/) (2021)
- [Proper Learning, Helly Number, and an Optimal SVM Bound](https://mlsanity.com/paper/2005.11818/) (2020)
- [Smoothed Online Learning is as Easy as Statistical Learning](https://mlsanity.com/paper/2202.04690/) (2022)
- [Sample compression schemes for VC classes](https://mlsanity.com/paper/1503.06960/) (2015)
- [Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalization](https://mlsanity.com/paper/2303.12921/) (2023)
- [Adversarial Laws of Large Numbers and Optimal Regret in Online Classification](https://mlsanity.com/paper/2101.09054/) (2021)
- [Differentially Private Ordinary Least Squares](https://mlsanity.com/paper/1507.02482/) (2015)
- [Optimal PAC Bounds Without Uniform Convergence](https://mlsanity.com/paper/2304.09167/) (2023)
- [Reducing Adversarially Robust Learning to Non-Robust PAC Learning](https://mlsanity.com/paper/2010.12039/) (2020)
- [Realizable Learning is All You Need](https://mlsanity.com/paper/2111.04746/) (2021)
- [Adversarially Robust Learning with Unknown Perturbation Sets](https://mlsanity.com/paper/2102.02145/) (2021)
- [A Characterization of List Learnability](https://mlsanity.com/paper/2211.04956/) (2022)
- [Empirical entropy, minimax regret and minimax risk](https://mlsanity.com/paper/1308.1147/) (2013)
- [A Theory of PAC Learnability under Transformation Invariances](https://mlsanity.com/paper/2202.07552/) (2022)
- [Sample Compression for Real-Valued Learners](https://mlsanity.com/paper/1805.08254/) (2018)
- [Optimal Prediction Using Expert Advice and Randomized Littlestone Dimension](https://mlsanity.com/paper/2302.13849/) (2023)
- [Majorizing Measures, Sequential Complexities, and Online Learning](https://mlsanity.com/paper/2102.01729/) (2021)
- [Adversarially Robust Learning: A Generic Minimax Optimal Learner and Characterization](https://mlsanity.com/paper/2209.07369/) (2022)
- [Statistical Indistinguishability of Learning Algorithms](https://mlsanity.com/paper/2305.14311/) (2023)
- [Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Games](https://mlsanity.com/paper/2111.08911/) (2021)
- [Multiclass Learnability Beyond the PAC Framework: Universal Rates and Partial Concept Classes](https://mlsanity.com/paper/2210.02297/) (2022)
- [A Characterization of Semi-Supervised Adversarially-Robust PAC Learnability](https://mlsanity.com/paper/2202.05420/) (2022)

## Built on by (most cited first, 23 of 23)

- [Regularization and Optimal Multiclass Learning](https://mlsanity.com/paper/2309.13692/) (2023)
- [Information Complexity of Stochastic Convex Optimization: Applications to Generalization and Memorization](https://mlsanity.com/paper/2402.09327/) (2024)
- [Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back](https://mlsanity.com/paper/2511.12659/) (2025)
- [Multiclass Transductive Online Learning](https://mlsanity.com/paper/2411.01634/) (2024)
- [Transfer Learning Beyond Bounded Density Ratios](https://mlsanity.com/paper/2403.11963/) (2024)
- [A Characterization of List Regression](https://mlsanity.com/paper/2409.19218/) (2024)
- [Multiscale Reward Hedging from Correct Demonstrations](https://mlsanity.com/paper/2608.06825/) (2026)
- [Is Transductive Learning Equivalent to PAC Learning?](https://mlsanity.com/paper/2405.05190/) (2024)
- [Sample Compression Unleashed: New Generalization Bounds for Real Valued Losses](https://mlsanity.com/paper/2409.17932/) (2024)
- [Is Efficient PAC Learning Possible with an Oracle That Responds 'Yes' or 'No'?](https://mlsanity.com/paper/2406.11667/) (2024)
- [Every Feedforward Neural Network Definable in an o-Minimal Structure Has Finite Sample Complexity](https://mlsanity.com/paper/2605.07097/) (2026)
- [Transductive Learning Is Compact](https://mlsanity.com/paper/2402.10360/) (2024)
- [Sample Compression Scheme Reductions](https://mlsanity.com/paper/2410.13012/) (2024)
- [On The Statistical Complexity of Offline Decision-Making](https://mlsanity.com/paper/2501.06339/) (2025)
- [Learning in Structured Stackelberg Games](https://mlsanity.com/paper/2504.09006/) (2025)
- [Sequential Probability Assignment with Contexts: Minimax Regret, Contextual Shtarkov Sums, and Contextual Normalized Maximum Likelihood](https://mlsanity.com/paper/2410.03849/) (2024)
- [PAC Learning is just Bipartite Matching (Sort of)](https://mlsanity.com/paper/2502.00607/) (2025)
- [Online Realizable Regression and Applications for ReLU Networks](https://mlsanity.com/paper/2602.19172/) (2026)
- [Tighter Learning Guarantees on Digital Computers via Concentration of Measure on Finite Spaces](https://mlsanity.com/paper/2402.05576/) (2024)
- [Multiplicative Oracle Inequalities for Transductive Learning via Level-Set Aggregation](https://mlsanity.com/paper/2603.02043/) (2026)
- [Margin in Abstract Spaces](https://mlsanity.com/paper/2603.07221/) (2026)
- [Realizable Bayes-Consistency for General Metric Losses](https://mlsanity.com/paper/2605.03823/) (2026)
- [The Interplay Between Interpolation and Aggregation in Regression: Optimal Sample Complexity](https://mlsanity.com/paper/2605.29819/) (2026)

## Abstract (arXiv)

In this work, we aim to characterize the statistical complexity of realizable regression both in the PAC learning setting and the online learning setting. Previous work had established the sufficiency of finiteness of the fat shattering dimension for PAC learnability and the necessity of finiteness of the scaled Natarajan dimension, but little progress had been made towards a more complete characterization since the work of Simon (SICOMP '97). To this end, we first introduce a minimax instance optimal learner for realizable regression and propose a novel dimension that both qualitatively and quantitatively characterizes which classes of real-valued predictors are learnable. We then identify a combinatorial dimension related to the Graph dimension that characterizes ERM learnability in the realizable setting. Finally, we establish a necessary condition for learnability based on a combinatorial dimension related to the DS dimension, and conjecture that it may also be sufficient in this context. Additionally, in the context of online learning we provide a dimension that characterizes the minimax instance optimal cumulative loss up to a constant factor and design an optimal online learner for realizable regression, thus resolving an open question raised by Daskalakis and Golowich in STOC '22.