Research map / Optimization / Nonconvex and smooth optimization
Drago: Primal-Dual Coupled Variance Reduction for Faster Distributionally Robust 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 DRAGO, a minibatch stochastic primal-dual algorithm with cyclic and randomized table updates and a regularized primal update that achieves linear convergence for penalized DRO with support-constrained convex uncertainty sets, for any nu>0.
Problem
Penalized distributionally robust optimization (DRO) with a closed convex uncertainty set: achieving linear convergence for any dual regularization nu>0 in large-sample settings, where prior stochastic DRO methods have sublinear rates or require nu to be large (Omega(n)).
Approach
A stochastic primal-dual method combining randomized sampling of blocks with cyclic (block-wise) updates of historical loss/gradient/dual tables, plus a carefully regularized primal update (a proximal term over past iterates) that cancels variance from the coupled term, yielding dual variance reduction and linear rates with individual condition numbers.
Key results
- Complexity O((n/b + kappa_Q L/mu + (n/b) sqrt(nG^2/(mu nu))) ln(1/eps)) iterations, giving linear convergence for any nu>0 without a lower bound on nu.
- On kin8nm (n=6553), DRAGO reaches 1e-7 primal gap within 1 second while LSVRG reaches only about 1e-2 in the same time.
- On emotion text classification with d=270, DRAGO reaches close to 1e-5 primal suboptimality within 4 seconds while SGD and LSVRG gaps are 2 to 3 orders of magnitude larger.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use Drago (b = n/d) instead of LSVRG | DRO optimization on kin8nm · kin8nm | primal suboptimality gap within 1 second: 10^{-2} -> 10^{-7} | Helped |
| use Drago instead of SGD or LSVRG | DRO optimization on emotion · emotion | primal suboptimality gap within 4 seconds: close to a 10^{-5} primal suboptimality gap; SGD and LSVRG gaps are 2 to 3 orders of magnitude larger | Helped |
| set batch size to n/d rather than smaller or tuned batch sizes (ablation) | Drago · regression datasets | wall-clock time to reduce primal suboptimality | Helped |
| set batch size to 1 (ablation) | Drago · regression datasets with n ≤ 1,000 | oracle-query performance | No clear effect |
| set batch size to 16 instead of 1 (ablation) | Drago · larger regression datasets | oracle-query performance | Helped |
| use LSVRG instead of SGD at smaller values of ν | DRO optimization on emotion · emotion | wall-clock time | Hurt |
Surprising findings
- LSVRG is outperformed by SGD in wall-clock time for smaller nu on the ill-conditioned text classification task.
Limitations
- Requires smoothness and Lipschitzness of losses and strong convexity of the primal regularizer (mu>0) and divergence penalty (nu>0) for the main guarantee.
- Global complexity scales with kappa_Q, so large uncertainty sets can degrade the incremental method toward full-batch subgradient performance.
- Experiments are limited to regression and small-scale classification with a fixed PCA-reduced BERT featurization.
Experimental setup
Datasets: yacht energy concrete acsincome kin8nm power emotion
Benchmarks: yacht energy concrete acsincome kin8nm power emotion
Metrics: normalized primal suboptimality gap wall-clock time number of first-order oracle queries
Baselines: distributionally robust SGD LSVRG full-batch gradient descent Prospect sub-gradient method
Builds on: SAGA IAG stochastic PDHG LSVRG Prospect
Closest papers by meaning
- Revisiting Large-Scale Non-convex Distributionally Robust Optimization (ICLR 2025 · similarity 0.91)
- Distributionally Robust Optimization with Bias and Variance Reduction (ICLR 2024 · similarity 0.90)
- Large-Scale Non-convex Stochastic Constrained Distributionally Robust Optimization (AAAI 2024 · similarity 0.89)
- Outlier-Robust Distributionally Robust Optimization via Unbalanced Optimal Transport (NeurIPS 2024 · similarity 0.89)
- Wasserstein Distributionally Robust Optimization through the Lens of Structural Causal Models and Individual Fairness (NeurIPS 2024 · similarity 0.88)
- Double Variance Reduction: A Smoothing Trick for Composite Optimization Problems without First-Order Gradient (ICML 2024 · 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.