On the Efficiency of ERM in Feature Learning
Not on the map. Why?
Abstract (arXiv)
Given a collection of feature maps indexed by a set T, we study the performance of empirical risk minimization (ERM) on regression problems with square loss over the union of the linear classes induced by these feature maps. This setup aims at capturing the simplest instance of feature learning, where the model is expected to jointly learn from the data an appropriate feature map and a linear predictor. We start by studying the asymptotic quantiles of the excess risk of sequences of empirical risk minimizers. Remarkably, we show that when the set T is not too large and when there is a unique optimal feature map, these quantiles coincide, up to a factor of two, with those of the excess risk of the oracle procedure, which knows a priori this optimal feature map and deterministically outputs an empirical risk minimizer from the associated optimal linear class. We complement this asymptotic result with a non-asymptotic analysis that quantifies the decaying effect of the global complexity of the set T on the excess risk of ERM, and relates it to the size of the sublevel sets of the suboptimality of the feature maps. As an application of our results, we obtain new guarantees on the performance of the best subset selection procedure in sparse linear regression under general assumptions.
Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 25 of its 77 references that are in the map. First posted on arXiv 18 Nov 2024.
Builds on
25 of 77 references.
References · 25
- 2017Attention Is All You Needcited by 60,361
- 2015Deep Residual Learning for Image Recognitioncited by 52,096
- 2018On Lazy Training in Differentiable Programmingcited by 675
- 2015An Introduction to Matrix Concentration Inequalitiescited by 397
- 2014Breaking the Curse of Dimensionality with Convex Neural Networkscited by 331
- 2021Deep learning: a statistical viewpointcited by 240
- 2020When Do Neural Networks Outperform Kernel Methods?cited by 150
- 2022High-dimensional Asymptotics of Feature Learning: How One Gradient Step Improves the Representationcited by 150
- 2015Best Subset Selection via a Modern Optimization Lenscited by 100
- 2019Limitations of Lazy Training of Two-layers Neural Networkscited by 87
- 2014Learning without Concentrationcited by 50
- 2020Sparse Regression at Scale: Branch-and-Bound rooted in First-Order Optimizationcited by 45
13 more
- 2017Sparse High-Dimensional Regression: Exact Scalable Algorithms and Phase Transitionscited by 43
- 2015Learning with Square Loss: Localization through Offset Rademacher Complexitycited by 38
- 2019Exact minimax risk for linear least squares, and the lower tail of sample covariance matricescited by 34
- 2013Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regressioncited by 32
- 2018Finite-sample analysis of M-estimators using self-concordancecited by 30
- 2019Sparse Regression: Scalable algorithms and empirical performancecited by 27
- 2017High-Dimensional Regression with Binary Coefficients. Estimating Squared Error and a Phase Transitioncited by 12
- 2015Optimal prediction for sparse linear models? Lower bounds for coordinate-separable M-estimatorscited by 9
- 2022Exponential Tail Local Rademacher Complexity Risk Bounds Without the Bernstein Conditioncited by 9
- 2023Feature Adaptation for Sparse Linear Regressioncited by 6
- 2024A New Branch-and-Bound Pruning Framework for ℓ0-Regularized Problemscited by 5
- 2024Minimax Linear Regression under the Quantile Riskcited by 3
- 2023Optimal Excess Risk Bounds for Empirical Risk Minimization on p-Norm Linear Regressioncited by 2
Built on by
Citing papers per year: 2025: 1.
1 paper.