Research map / Optimization / Nonconvex and smooth optimization
Efficient Stochastic Approximation of Minimax Excess Risk Optimization
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.
Proposes anytime stochastic approximation (m parallel SMD instances plus a saddle-point SMD with biased gradients) and a two-stage weighted variant to directly optimize minimax excess risk (MERO) without empirical risk minimization each iteration.
Problem
Minimax excess risk optimization (MERO) requires estimating each distribution's minimal risk, and existing algorithms for its empirical version solve an ERM problem every iteration, which is computationally prohibitive for large sample sizes.
Approach
Cast MERO as a stochastic convex-concave saddle-point problem; run m SMD instances to estimate each per-distribution minimal risk and use their averaged iterates to build biased stochastic gradients, so the bias from estimating R_i* stays controlled, enabling an anytime O(sqrt(log m / t))-type rate. A weighted version with distribution-specific budgets yields O(log m / sqrt(n_i)) excess-risk rates
Key results
- The anytime MERO reaches the target maximal excess risk 5.7x faster than empirical MERO (E-MERO) on the synthetic dataset and 6.9x faster on Adult.
- The anytime algorithm achieves an O((log^2 t + log^{1/2} m log^{3/2} t)/sqrt(t)) optimization error rate for MERO, in expectation and with high probability.
- The weighted two-stage method gives per-distribution excess risk O((log m)/sqrt(n_i)) for distributions with n_i <= n_m^2, versus O(sqrt(log m / n_m)) for the unweighted method.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use stochastic approximation for MERO instead of empirical MERO optimization | MERO vs. E-MERO · Synthetic | time to reach maximal excess risk 0.05: 5.7 times faster | Helped |
| use stochastic approximation for MERO instead of empirical MERO optimization | MERO vs. E-MERO · Adult | time to reach maximal excess risk 0.03: 6.9 times faster | Helped |
| use the anytime MERO algorithm rather than the preset-horizon multi-stage method | MERO vs. MS-MERO · Synthetic and Adult | maximal excess risk | Helped |
| optimize maximal excess risk rather than raw risk | MERO vs. GDRO · Synthetic, distributions P1–P4 | individual risk | Helped |
| optimize maximal excess risk rather than raw risk | MERO vs. GDRO · Synthetic, distributions P5–P6 | individual risk | Hurt |
| optimize maximal excess risk rather than raw risk | MERO vs. GDRO · Adult, distributions P1, P3, and P5 | individual risk | Hurt |
| use MERO instead of GDRO at equal running time | MERO vs. GDRO · Synthetic and Adult | risk versus running time | Hurt |
| use weighted stochastic approximation rather than empirical weighted MERO optimization | W-MERO vs. EW-MERO · Imbalanced synthetic | maximal weighted excess risk | Helped |
Surprising findings
- GDRO achieves lower risk on the high-noise distributions, so MERO does not dominate GDRO on every individual distribution, only on maximal excess risk.
Limitations
- Maintaining m extra models makes per-iteration cost higher than standard GDRO stochastic methods.
- The anytime rate carries extra log factors compared with the fixed-budget multi-stage approach.
- Weighted-MERO guarantees require smoothness and regularity assumptions, and the optimal value p* is generally unknown.
Experimental setup
Datasets: Adult synthetic Gaussian classification data
Benchmarks: Adult synthetic Gaussian classification
Metrics: maximal excess risk running time to target MER maximal weighted excess risk
Baselines: E-MERO MS-MERO GDRO EW-MERO
Builds on: minimax regret optimization group DRO stochastic mirror descent stochastic mirror-prox
Closest papers by meaning
- Large-Scale Non-convex Stochastic Constrained Distributionally Robust Optimization (AAAI 2024 · similarity 0.88)
- Distributionally Robust Optimization with Bias and Variance Reduction (ICLR 2024 · similarity 0.88)
- Stochastic Zeroth-Order Optimization Under Heavy-Tailed Noise (NeurIPS 2026 · similarity 0.86)
- Drago: Primal-Dual Coupled Variance Reduction for Faster Distributionally Robust Optimization (NeurIPS 2024 · similarity 0.86)
- Generalization Analysis of Biased Stochastic Gradient Methods for Minimax Problems (NeurIPS 2026 · similarity 0.86)
- Bayesian Nonparametrics Meets Data-Driven Distributionally Robust Optimization (NeurIPS 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.