Research map / Optimization / Nonconvex and smooth optimization
Efficient Algorithms for Empirical Group Distributionally Robust Optimization and Beyond
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 ALEG, a double-loop variance-reduced stochastic mirror prox with group sampling for empirical GDRO (complexity O(m√(n̄ ln m)/ε)), and ALEM, a two-stage extension to empirical MERO.
Problem
Empirical Group DRO minimizes the maximal empirical risk across m groups; existing algorithms have quadratic dependence on accuracy or suboptimal complexity in m, and empirical MERO (excess risk) lacks efficient methods.
Approach
Exploit the two-level finite-sum structure: sample one sample per group to build a stochastic gradient with a 1/m smaller Lipschitz constant, then apply variance reduction in a modified mirror prox with one-index-shifted weighted averages allowing variable learning rates; extend to MERO via a two-stage scheme that estimates per-group minimal risks with ALEG.
Key results
- ALEG attains O(m√(n̄ ln m)/ε) computation complexity, improving the state-of-the-art MPVR-based rate by a factor of √m.
- ALEM achieves Õ(m√(n̄ ln m)/ε) complexity for empirical MERO, improving over ERMEG's O(m n̄ ln(m n̄)/ε²) and TSA's O(m ln m/ε²).
- Experiments on synthetic and CIFAR-100 show ALEG converges faster and reaches lower max empirical risk than SMD, MPVR, and AL-SVRE.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use group sampling with one sample from each group instead of MPVR sampling | ALEG for empirical GDRO · Empirical GDRO | computation complexity: improves the state-of-the-art computation complexity by a factor of \sqrt{m} | Helped |
| use ALEG instead of SMD | Empirical GDRO · Empirical GDRO | computation complexity: \mathcal{O}\brac{\frac{m\ln m}{\varepsilon^2}} -> \mathcal{O}\brac{\frac{m\sqrt{\bar n\ln{m}}}{\varepsilon}} | Helped |
| use ALEG instead of MPVR | Empirical GDRO · Empirical GDRO | computation complexity: \mathcal{O}\brac{m\bar n+\frac{m\sqrt{m\bar n\ln{m}}}{\varepsilon}} -> \mathcal{O}\brac{\frac{m\sqrt{\bar n\ln{m}}}{\var | Helped |
| use ALEM instead of ERMEG | Empirical MERO · Empirical MERO | computation complexity: \mathcal{O}\brac{\frac{m\bar n\ln(m\bar n)}{\varepsilon^2}} -> \tilde{\mathcal{O}}\brac{\frac{m\sqrt{\bar n\ln{m}}}{\var | Helped |
| use ALEM instead of TSA | Empirical MERO · Empirical MERO | computation complexity: \mathcal{O}\brac{\frac{m\ln m}{\varepsilon^2}} -> \tilde{\mathcal{O}}\brac{\frac{m\sqrt{\bar n\ln{m}}}{\varepsilon}} | Helped |
Limitations
- Convergence results assume smooth, Lipschitz, convex risks; the convexity assumption excludes deep networks despite the CIFAR-100 experiments using a linear model.
- Group sampling queries m times more stochastic gradients per iteration than MPVR's uniform sampling.
- Experiments use only linear models and a single synthetic setting; the parameter sets K_s and alpha are kept constant in theory.
Experimental setup
Datasets: synthetic Gaussian logistic dataset CIFAR-100
Benchmarks: CIFAR-100 synthetic logistic dataset
Metrics: max empirical risk max excess empirical risk
Baselines: SMD MPVR AL-SVRE ERMEG TSA
Builds on: Mirror Prox with Variance Reduction (MPVR) Stochastic Mirror Descent AL-SVRE ERMEG
Closest papers by meaning
- Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity (ICML 2025 · similarity 0.91)
- Group Distributionally Robust Optimization with Flexible Sample Queries (NeurIPS 2026 · similarity 0.91)
- MixMax: Distributional Robustness in Function Space via Optimal Data Mixtures (ICLR 2025 · similarity 0.87)
- Differentially Private Worst-group Risk Minimization (ICML 2024 · similarity 0.87)
- A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization (ICML 2025 · similarity 0.86)
- Communication-Efficient Federated Group Distributionally Robust Optimization (NeurIPS 2024 · similarity 0.85)
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.