Skip to content
conftrace_
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.

Authors

Naren Sarayu Manoj, Nathan Srebro

Topics

Machine Learning > Optimization & Theory > Learning Theory Machine Learning > Optimization & Theory > Statistical Learning Machine Learning > Learning Types > Supervised Learning

Keywords

label noise agnostic learning minimum description length interpolation learning minimum program length tempered overfitting finite sample learning random label noise sample learning guarantee
Download PDF

More from COLT 2023

All COLT 2023 papers →
Finite-Sample Symmetric Mean Estimation with Fisher Information Rate
Fast Algorithms for a New Relaxation of Optimal Transport
Generalization Guarantees via Algorithm-dependent Rademacher Complexity
ℓ_p-Regression in the Arbitrary Partition Model of Communication
On Classification-Calibration of Gamma-Phi Losses
Generalization Error Bounds for Noisy, Iterative Algorithms via Maximal Leakage