mlsanityData to 14 Oct 2026

The Interplay Between Interpolation and Aggregation in Regression: Optimal Sample Complexity

arXiv 2605.29819 ↗First posted 28 May 2026cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

This work investigates theoretically the interplay between interpolation and aggregation in regression. We establish that the γ-graph dimension characterizes learnability for a broad class of natural aggregation procedures. Furthermore, we prove that an extremely simple aggregation procedure, combining three interpolating hypotheses via the median, is optimal among all these aggregation procedures, and is strictly more powerful than proper learning. Finally, we show that some hypothesis classes are learnable only by aggregating infinitely many hypotheses or by using non-interpolating aggregation rules (which may predict outside the range of their inputs), and any finite interpolating aggregation fails to achieve even trivial performance.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 28 of its 43 references that are in the map. First posted on arXiv 28 May 2026.

Builds on

28 of 43 references.

References · 28

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,621
  2. 2018Reconciling modern machine learning practice and the bias-variance trade-offcited by 927
  3. 2017The Implicit Bias of Gradient Descent on Separable Datacited by 655
  4. 2019Benign Overfitting in Linear Regressioncited by 549
  5. 2019Surprises in High-Dimensional Ridgeless Least Squares Interpolationcited by 513
  6. 2018Just Interpolate: Kernel "Ridgeless" Regression Can Generalizecited by 190
  7. 2018To understand deep learning we need to understand kernel learningcited by 187
  8. 2021Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolationcited by 132
  9. 2018Does data interpolation contradict statistical optimality?cited by 95
  10. 2015The Optimal Sample Complexity of PAC Learningcited by 72
  11. 2022A Characterization of Multiclass Learnabilitycited by 67
  12. 2014Optimal Learners for Multiclass Problemscited by 65
16 more
  1. 2021A Theory of PAC Learnability of Partial Concept Classescited by 60
  2. 2020Proper Learning, Helly Number, and an Optimal SVM Boundcited by 53
  3. 2022Bagging is an Optimal PAC Learnercited by 34
  4. 2023Optimal PAC Bounds Without Uniform Convergencecited by 33
  5. 2023Optimal Learners for Realizable Regression: PAC Learning and Online Learningcited by 23
  6. 2018Sample Compression for Real-Valued Learnerscited by 19
  7. 2021Distribution-Free Robust Linear Regressioncited by 19
  8. 2021Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Gamescited by 16
  9. 2024Revisiting Agnostic PAC Learningcited by 11
  10. 2018Agnostic Sample Compression Schemes for Regressioncited by 7
  11. 2021Fat-Shattering Dimension of k-fold Aggregationscited by 5
  12. 2025On Agnostic PAC Learning in the Small Error Regimecited by 5
  13. 2025Efficient Optimal PAC Learningcited by 4
  14. 2025Improved Margin Generalization Bounds for Voting Classifierscited by 4
  15. 2024The Many Faces of Optimal Weak-to-Strong Learningcited by 3
  16. 2024Understanding Aggregations of Proper Learners in Multiclass Classificationcited by 3

Built on by

Not cited yet.