Research map / Learning theory and algorithms / Prediction and decision losses
On the Asymptotic Distribution of the Minimum Empirical Risk
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.
Derives asymptotic distributions of root-n blowups of minimum empirical risk under weak assumptions (non-IID dependence, discontinuous losses, non-Euclidean parameter spaces), and applies them to bootstrap confidence sets, penalized model selection, and neural network classification.
Problem
Limiting distribution of the root-n blowup of the minimum empirical risk (MER) typically requires strong assumptions: Euclidean parameter spaces, differentiable and uniquely minimized risks, and IID data. These fail in modern settings with non-differentiable risks, multiple minima, dependent data, o
Approach
Combines recent Danskin-type theorems for infima over bounded (possibly discontinuous) function classes with a directionally differentiable delta method to obtain sqrt(n)-blowup limits under abstract conditions (uniform CLT plus boundedness), then uses these for bootstrap inference, model selection via penalized MER, and incremental parameter spaces.
Key results
- SWIC selected the true number of GMoE components (k*=2) in all 50 simulations at n=2000, while AIC always underestimated and BIC selected correctly with probability 0.72.
- In the neural network experiment, the nonparametric bootstrap and the two consistent procedures all achieved nominal 90% coverage for large samples, with the Firpo et al. method considerably faster than the others.
- Main theorems give sqrt(n)-blowup limits of the MER under non-IID (beta-mixing), discontinuous, and functional-parameter settings, relaxing Shapiro (2021)'s IID, Lipschitz, and compact Euclidean assumptions.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SWIC penalties instead of BIC penalties | GMoE model selection · Gaussian mixture of experts (50 simulations, n = 2000) | correct model selection | Helped |
| Use SWIC penalties instead of AIC penalties | GMoE model selection · Gaussian mixture of experts (50 simulations, n = 2000) | model complexity selection | Helped |
| Use BIC penalties | GMoE model selection · Gaussian mixture of experts (50 simulations, n = 2000) | correct model selection: 0.72 | Mixed |
| Use the standard nonparametric bootstrap instead of the modified bootstrap procedures | Neural network MER confidence intervals · Binary classification neural network | 90% confidence interval coverage | No clear effect |
| Use the Firpo et al. procedure instead of the other bootstrap procedures | Neural network MER confidence intervals · Binary classification neural network | computation time | Helped |
Surprising findings
- The standard nonparametric bootstrap offers little support in the studied setting, and the authors note all methods gave conservative coverage at moderate sample sizes.
Limitations
- Moving block bootstrap conditions (E1-E3) are stronger than non-bootstrap conditions, requiring higher moments and fast mixing.
- Bootstrap consistency is established only under restrictive conditions (e.g., constancy of loss on the minimizer set), since the infimum map is only directionally differentiable in general.
- Neural network experiment uses a small, known data-generating model with a globally optimized fit via particle swarm.
Experimental setup
Datasets: synthetic GMoE data synthetic binary classification data from a ReLU network
Benchmarks: synthetic GMoE model selection synthetic neural network classification coverage
Metrics: empirical probability of correct model order selection bootstrap CI coverage mean CI width
Baselines: standard nonparametric bootstrap BIC AIC Hong & Li bootstrap Firpo et al. bootstrap
Builds on: Shapiro (1991) sqrt(n)-blowup theory Carcamo et al. (2020) Danskin theorem Romisch (2014) delta method Fang & Santos (2019) bootstrap Sin & White (1996) information criterion
Closest papers by meaning
- Asymptotic Theory of Iterated Empirical Risk Minimization, with Applications to Active Learning (ICML 2026 · similarity 0.91)
- On Empirical Risk Minimization with Dependent and Heavy-Tailed Data (NeurIPS 2021 · similarity 0.90)
- On the Fine-Grained Complexity of Empirical Risk Minimization: Kernel Methods and Neural Networks (NeurIPS 2017 · similarity 0.89)
- On the Variance, Admissibility, and Stability of Empirical Risk Minimization (NeurIPS 2023 · similarity 0.89)
- Universal Rates of Empirical Risk Minimization (NeurIPS 2024 · similarity 0.89)
- On the Efficiency of ERM in Feature Learning (NeurIPS 2024 · similarity 0.88)
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.