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

• URL: http://arxiv.org/abs/2605.29819v1
• Date: Thu, 28 May 2026 12:02:09 GMT
• Title: The Interplay Between Interpolation and Aggregation in Regression: Optimal Sample Complexity
• Abstract summary: We show that some hypothesis classes are learnable only by aggregating infinitely many hypotheses.<n>We prove that an extremely simple aggregation procedure, combining three interpolating hypotheses via the median, is optimal among all these aggregation procedures.
• Score: 21.276981570672064
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Rate optimal learning of equilibria from data [63.14746189846806]
  We close theoretical gaps in Multi-Agent Imitation Learning (MAIL) by characterizing the limits of non-interactive MAIL and presenting the first interactive algorithm with near-optimal sample complexity.<n>For the interactive setting, we introduce a framework that combines reward-free reinforcement learning with interactive MAIL and instantiate it with an algorithm, MAIL-WARM.<n>We provide numerical results that support our theory and illustrate, in environments such as grid worlds, where Behavior Cloning fails to learn.
  arXiv  Detail & Related papers  (2025-10-10T12:28:35Z)
• Generalization error of min-norm interpolators in transfer learning [2.7309692684728617]
  Min-norm interpolators emerge naturally as implicit regularized limits of modern machine learning algorithms. In many applications, a limited amount of test data may be available during training, yet properties of min-norm in this setting are not well-understood. We establish a novel anisotropic local law to achieve these characterizations.
  arXiv  Detail & Related papers  (2024-06-20T02:23:28Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  Multi-distribution learning seeks to learn a shared model that minimizes the worst-case risk across $k$ distinct data distributions.<n>We propose a novel algorithm that yields an varepsilon-optimal randomized hypothesis with a sample complexity on the order of (d+k)/varepsilon2.
  arXiv  Detail & Related papers  (2023-12-08T16:06:29Z)
• Optimal Multitask Linear Regression and Contextual Bandits under Sparse Heterogeneity [41.772562538698395]
  Multitask learning methods improve efficiency by leveraging commonalities across datasets.<n>We study multitask linear regression and contextual bandits under sparse heterogeneity.<n>We show that our methods are minimax optimal by providing a number of lower bounds.
  arXiv  Detail & Related papers  (2023-06-09T22:48:13Z)
• Kernel-based off-policy estimation without overlap: Instance optimality beyond semiparametric efficiency [53.90687548731265]
  We study optimal procedures for estimating a linear functional based on observational data. For any convex and symmetric function class $mathcalF$, we derive a non-asymptotic local minimax bound on the mean-squared error.
  arXiv  Detail & Related papers  (2023-01-16T02:57:37Z)
• Malign Overfitting: Interpolation Can Provably Preclude Invariance [30.776243638012314]
  We show that "benign overfitting" in which models generalize well despite interpolating might not favorably extend to settings in which robustness or fairness are desirable. We propose and analyze an algorithm that successfully learns a non-interpolating classifier that is provably invariant.
  arXiv  Detail & Related papers  (2022-11-28T19:17:31Z)
• Teach me how to Interpolate a Myriad of Embeddings [18.711509039868655]
  Mixup refers to data-based augmentation, originally motivated as a way to go beyond empirical risk minimization. We introduce MultiMix, which interpolates an arbitrary number $n$ of length $m$, with one vector $lambda$ per length. Our contributions result in significant improvement over state-of-the-art mixup methods on four benchmarks.
  arXiv  Detail & Related papers  (2022-06-29T19:16:48Z)
• Equilibrium Aggregation: Encoding Sets via Optimization [4.849550522970841]
  We propose an optimization-based method called Equilibrium Aggregation. We show that many existing aggregation methods can be recovered as special cases of Equilibrium Aggregation. We validate its efficiency on three different tasks: median estimation, class counting, and molecular property prediction.
  arXiv  Detail & Related papers  (2022-02-25T16:13:55Z)
• Predict then Interpolate: A Simple Algorithm to Learn Stable Classifiers [59.06169363181417]
  Predict then Interpolate (PI) is an algorithm for learning correlations that are stable across environments. We prove that by interpolating the distributions of the correct predictions and the wrong predictions, we can uncover an oracle distribution where the unstable correlation vanishes.
  arXiv  Detail & Related papers  (2021-05-26T15:37:48Z)
• An Online Learning Approach to Interpolation and Extrapolation in Domain Generalization [53.592597682854944]
  We recast generalization over sub-groups as an online game between a player minimizing risk and an adversary presenting new test. We show that ERM is provably minimax-optimal for both tasks.
  arXiv  Detail & Related papers  (2021-02-25T19:06:48Z)
• Good Classifiers are Abundant in the Interpolating Regime [64.72044662855612]
  We develop a methodology to compute precisely the full distribution of test errors among interpolating classifiers. We find that test errors tend to concentrate around a small typical value $varepsilon*$, which deviates substantially from the test error of worst-case interpolating model. Our results show that the usual style of analysis in statistical learning theory may not be fine-grained enough to capture the good generalization performance observed in practice.
  arXiv  Detail & Related papers  (2020-06-22T21:12:31Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.