Research map / Optimization / Optimizers
Scaling-up Empirical Risk Minimization: Optimization of Incomplete $U$-statistics
Stephan Clémençon, Igor Colin, Aurélien Bellet
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace complete U-statistic with incomplete U-statistic (same pair budget) in one-time sampling | ERM for metric learning · Synthetic metric learning | subsample size p to reach 5% of optimum risk: p = 50 vs p > 80 | Improved |
| replace complete U-statistic with incomplete U-statistic in one-time sampling | ERM for metric learning · MNIST metric learning | test risk | Improved |
| use incomplete U-statistic mini-batches instead of complete ones in SGD | SGD metric learning · MNIST metric learning (mini-batch sizes 10 to 253) | test risk | Improved |
| use incomplete U-statistic instead of complete one for clustering risk | model selection · Forest cover type clustering | model selection time (s): 66 -> 0.1 | Improved |
| use incomplete U-statistic with B=5,000 instead of complete risk | model selection · Forest cover type clustering | selected model: P8 selected by both | No clear effect |
| use incomplete U-statistic instead of complete U-statistic on subsample (same pair count) | model selection · Forest cover type clustering | correct model selection: 57% -> 100 of 100 seeds | Improved |
| increase mini-batch size | SGD-Incomplete vs SGD-Complete · MNIST metric learning | gap between variants: gap shrinks as m grows | Hurt |
Closest papers by meaning
- Distributed Algorithms for U-statistics-based Empirical Risk Minimization (JMLR 2023 · similarity 0.91)
- On the Asymptotic Distribution of the Minimum Empirical Risk (ICML 2024 · similarity 0.91)
- On the Fine-Grained Complexity of Empirical Risk Minimization: Kernel Methods and Neural Networks (NeurIPS 2017 · similarity 0.90)
- Universal Rates of Empirical Risk Minimization (NeurIPS 2024 · similarity 0.89)
- On the Efficiency of ERM in Feature Learning (NeurIPS 2024 · similarity 0.88)
- Sample-Optimal Agnostic Boosting with Unlabeled Data (ICML 2025 · similarity 0.87)
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.
