← Back to papers
2023 COLT COLT 2023

Shortest Program Interpolation Learning

Abstract

We prove that the Minimum Program Length learning rule exhibits tempered overfitting. We obtain tempered agnostic finite sample learning guarantees and characterize the asymptotic behavior in the presence of random label noise.

🧭 Keyword Pioneer — minimum program length
🐝 Cross-Pollinator — Artificial Intelligence, Computer Science, Computer Vision, Data Science & Analytics, Deep Learning, Healthcare & Medicine, Interdisciplinary, Machine Learning, Mathematics & Optimization, Natural Language Processing, Reinforcement Learning, Security & Privacy, Speech & Audio

Authors

Naren Sarayu Manoj , Nathan Srebro

Topics

Machine Learning > Optimization & Theory > Learning Theory Machine Learning > Optimization & Theory > Statistical Learning

Keywords

label noise agnostic learning minimum program length tempered overfitting finite sample learning
Download PDF

Related papers

Towards a Complete Analysis of Langevin Monte Carlo: Beyond Poincaré Inequality 2023
Improved Discretization Analysis for Underdamped Langevin Monte Carlo 2023
Convergence of AdaGrad for Non-convex Objectives: Simple Proofs and Relaxed Assumptions 2023
Stability and Generalization of Stochastic Optimization with Nonconvex and Nonsmooth Problems 2023
Online Learning and Solving Infinite Games with an ERM Oracle 2023