Research map / Learning theory and algorithms / Kernels and regression theory
On the Efficiency of ERM in Feature Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies ERM over the union of linear classes induced by a family of feature maps, showing asymptotic excess-risk quantiles match an oracle's up to a factor of two under a unique optimal feature map, plus a non-asymptotic bound with localization.
Problem
Understanding the excess risk of empirical risk minimization for square-loss regression when both the feature map (from a collection indexed by T) and the linear predictor must be learned jointly from data.
Approach
Treats feature learning as ERM over a union of linear classes and shows that, asymptotically, its excess-risk quantiles coincide (up to factor two) with an oracle that knows the optimal feature map; non-asymptotically, the dependence on the global size of T decays with sample size via localization over sublevel sets of feature-map suboptimality.
Key results
- Asymptotic quantiles of the excess risk of any ERM sequence are sandwiched within a factor of two of those of the oracle when the optimal feature map is unique and T is not too large.
- Non-asymptotic bound on ERM excess risk of order 1/n whose dependence on T decays through sublevel sets of feature-map suboptimality.
- Application: new guarantees for best subset selection in sparse linear regression under general assumptions.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| learn the feature map by ERM over the union instead of knowing the optimal map in advance | ERM over feature-map union · General square-loss regression with a unique optimal feature map (asymptotic) | excess-risk quantile: \frac{1}{2} \cdot Q_{Z^{-}}(1-\delta) \leq \liminf_{n \to \infty} n \cdot Q_{\mathcal{E}(\hat{t}_{n}, \hat{w}_{n})} (1-\ | No clear effect |
| restrict the risk bound to the iteratively localized set of feature maps | ERM over feature-map union · General square-loss regression (non-asymptotic) | excess risk: 24 \cdot (n \delta)^{-1} \cdot \Exp\brack{\sup_{s \in \mathcal{S}_{n,\delta,k}} G^{2}_{n}(s)} | Helped |
Surprising findings
- Asymptotically, the global complexity of the feature-map index set T is irrelevant to the excess risk of ERM when T is not too large.
Limitations
- Requires a unique optimal feature map for the sharpest asymptotic result.
- Sample size requirements and dependence on delta can be poor under weak moment assumptions.
- Non-asymptotic bounds are too general to interpret for infinite index sets without estimates of empirical process suprema.
Experimental setup
Metrics: excess risk asymptotic quantiles of excess risk
Baselines: oracle ERM over the optimal linear class
Builds on: iterative localization random-design linear regression excess risk bounds Bousquet concentration inequality
Closest papers by meaning
- On the Fine-Grained Complexity of Empirical Risk Minimization: Kernel Methods and Neural Networks (NeurIPS 2017 · similarity 0.90)
- Asymptotic Theory of Iterated Empirical Risk Minimization, with Applications to Active Learning (ICML 2026 · similarity 0.89)
- Risk Minimization from Adaptively Collected Data: Guarantees for Supervised and Policy Learning (NeurIPS 2021 · similarity 0.88)
- On the Asymptotic Distribution of the Minimum Empirical Risk (ICML 2024 · similarity 0.88)
- Universal Rates of Empirical Risk Minimization (NeurIPS 2024 · similarity 0.87)
- A Survey of Learning Criteria Going beyond the Usual Risk (Abstract Reprint) (AAAI 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.