Cover Image

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

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Høgsgaard, Mikael Møller, Larsen, Kasper Green, Zou, Liang-Yu
Format:	Preprint
Published:	2026
Subjects:	Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Optimal Parallelization of Boosting
by: da Cunha, Arthur, et al.
Published: (2024)

The Optimal Sample Complexity of Linear Contracts
by: Høgsgaard, Mikael Møller
Published: (2026)

Improved Margin Generalization Bounds for Voting Classifiers
by: Høgsgaard, Mikael Møller, et al.
Published: (2025)

AdaBoost is not an Optimal Weak to Strong Learner
by: Høgsgaard, Mikael Møller, et al.
Published: (2023)

The Many Faces of Optimal Weak-to-Strong Learning
by: Høgsgaard, Mikael Møller, et al.
Published: (2024)

Majority-of-Three: The Simplest Optimal Learner?
by: Aden-Ali, Ishaq, et al.
Published: (2024)

Efficient Optimal PAC Learning
by: Høgsgaard, Mikael Møller
Published: (2025)

Sample-Near-Optimal Agnostic Boosting with Improved Running Time
by: da Cunha, Arthur, et al.
Published: (2026)

Understanding Aggregations of Proper Learners in Multiclass Classification
by: Asilis, Julian, et al.
Published: (2024)

Uniform Mean Estimation for Heavy-Tailed Distributions via Median-of-Means
by: Høgsgaard, Mikael Møller, et al.
Published: (2025)

Agnostic Language Identification and Generation
by: Høgsgaard, Mikael Møller, et al.
Published: (2026)

On Agnostic PAC Learning in the Small Error Regime
by: Asilis, Julian, et al.
Published: (2025)

Revisiting Agnostic Boosting
by: da Cunha, Arthur, et al.
Published: (2025)

The Sample Complexity of Replicable Realizable PAC Learning
by: Larsen, Kasper Green, et al.
Published: (2026)

Boosting, Voting Classifiers and Randomized Sample Compression Schemes
by: da Cunha, Arthur, et al.
Published: (2024)

An Exponential Separation Between Quantum and Quantum-Inspired Classical Algorithms for Linear Systems
by: Grønlund, Allan, et al.
Published: (2024)

Tight Margin-Based Generalization Bounds for Voting Classifiers over Finite Hypothesis Sets
by: Larsen, Kasper Green, et al.
Published: (2025)

Tight Generalization Bounds for Large-Margin Halfspaces
by: Larsen, Kasper Green, et al.
Published: (2025)

Optimally Interpolating between Ex-Ante Fairness and Welfare
by: Høgsgaard, Mikael Møller, et al.
Published: (2023)

A Fine-Grained Understanding of Uniform Convergence for Halfspaces
by: Kontorovich, Aryeh, et al.
Published: (2026)

Improved Replicable Boosting with Majority-of-Majorities
by: Larsen, Kasper Green, et al.
Published: (2025)

Finite Sample Bounds for Non-Parametric Regression: Optimal Sample Efficiency and Space Complexity
by: Maran, Davide, et al.
Published: (2024)

Learning with Monotone Adversarial Corruptions
by: Larsen, Kasper Green, et al.
Published: (2026)

Revisiting Agnostic PAC Learning
by: Hanneke, Steve, et al.
Published: (2024)

On the Interpolation Error of Nonlinear Attention versus Linear Regression
by: Liao, Zhenyu, et al.
Published: (2025)

Derandomizing Multi-Distribution Learning
by: Larsen, Kasper Green, et al.
Published: (2024)

Sample Complexity Characterization for Linear Contextual MDPs
by: Deng, Junze, et al.
Published: (2024)

Sampling Complexity of TD and PPO in RKHS
by: Zou, Lu, et al.
Published: (2025)

Near-Optimal Sample Complexity for Iterated CVaR Reinforcement Learning with a Generative Model
by: Deng, Zilong, et al.
Published: (2025)

Achieving the Asymptotically Optimal Sample Complexity of Offline Reinforcement Learning: A DRO-Based Approach
by: Wang, Yue, et al.
Published: (2023)

Local Linear Attention: An Optimal Interpolation of Linear and Softmax Attention For Test-Time Regression
by: Zuo, Yifei, et al.
Published: (2025)

Heterogeneity-Aware Client Sampling for Optimal and Efficient Federated Learning
by: Weng, Shudi, et al.
Published: (2025)

Replicable Learning of Large-Margin Halfspaces
by: Kalavasis, Alkis, et al.
Published: (2024)

Actively Learning Halfspaces without Synthetic Data
by: Black, Hadley, et al.
Published: (2025)

Kernel Two-Sample Tests in High Dimension: Interplay Between Moment Discrepancy and Dimension-and-Sample Orders
by: Yan, Jian, et al.
Published: (2021)

The Exact Sample Complexity Gain from Invariances for Kernel Regression
by: Tahmasebi, Behrooz, et al.
Published: (2023)

The Optimal Sample Complexity of Multiclass and List Learning
by: Pabbaraju, Chirag
Published: (2026)

Preventing Model Collapse Under Overparametrization: Optimal Mixing Ratios for Interpolation Learning and Ridge Regression
by: Garg, Anvit, et al.
Published: (2025)

High-Dimensional Gaussian Process Regression with Soft Kernel Interpolation
by: Camaño, Chris, et al.
Published: (2024)

Kernel Multigrid: Accelerate Back-fitting via Sparse Gaussian Process Regression
by: Zou, Lu, et al.
Published: (2024)