Research map / Optimization / Nonconvex and smooth optimization
A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional 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 ALEXR, a single-loop primal-dual block-coordinate stochastic algorithm (extrapolated mirror ascent on sampled dual blocks plus proximal SGD on primal) for convex finite-sum coupled compositional optimization, with improved rates and near-optimal lower bounds.
Problem
Convex finite-sum coupled compositional optimization (cFCCO), arising in group DRO, pAUC maximization and imbalanced learning, where existing methods need smooth f_i and g_i, nested loops, or large batches.
Approach
Reformulate cFCCO as a convex-concave min-max problem and solve it with a single-loop block-coordinate method that updates only sampled dual blocks via extrapolated stochastic mirror ascent, paired with stochastic proximal gradient on the primal; the analysis uses virtual sequences to handle block dependence and yields rates that improve on MSVR/SOX and are near-optimal by matching lower bounds.
Key results
- On GDRO with CVaR divergence, ALEXR attains mean worst-group test accuracy 66.80% across Adult and CelebA settings, the highest among compared methods (SOX and BSGD 66.46%, MSVR 62.20%).
- Theoretically, ALEXR's merely convex smooth rate is O(max{1/(S eps^2), n/(BS eps^2)}), improving on MSVR's O(n/(sqrt(B) S eps^2)).
- Lower bounds show Omega(max{S/mu, n} eps^-1) for smooth strongly convex and Omega(n eps^-2) for non-smooth f_i, matching ALEXR up to log factors.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use ALEXR instead of SOX | CVaR-penalized GDRO · Adult worst-0.1 groups | test accuracy (%): 56.34 -> 56.58 | Helped |
| Use ALEXR instead of BSGD | CVaR-penalized GDRO · Adult worst-0.15 groups | test accuracy (%): 58.58 -> 58.52 | Hurt |
| Use ALEXR instead of MSVR | CVaR-penalized GDRO · CelebA worst-0.1 groups | test accuracy (%): 75.34 -> 75.79 | Helped |
| Use ALEXR instead of BSGD | CVaR-penalized GDRO · CelebA worst-0.15 groups | test accuracy (%): 76.16 -> 76.29 | Helped |
| Optimize the pAUC surrogate instead of cross-entropy | pAUC maximization with restricted TPR · Covtype, Cardiomegaly, Lung-mass, and Higgs | pAUC | Helped |
Surprising findings
- For non-smooth outer functions, strong convexity does not yield a faster rate than the merely convex case.
Limitations
- Analysis does not cover concave outer functions such as the logarithm, which the authors leave open.
- Non-smooth outer function with strong convexity gives no rate improvement, and the Omega(n eps^-2) lower bound limits the non-smooth case.
- Experiments are limited to linear models and two GDRO and pAUC settings.
Experimental setup
Datasets: Adult CelebA Covtype Higgs Cardiomegaly Lung-mass
Benchmarks: Adult CelebA Covtype Higgs Cardiomegaly Lung-mass
Metrics: test accuracy on worst-alpha-n groups validation loss curves pAUC during training
Baselines: SGD SGD-UW OOA BSGD SOX MSVR
Builds on: SOX MSVR SAPD stochastic sequential dual (SSD)
Closest papers by meaning
- Stochastic Momentum Methods for Non-smooth Non-Convex Finite-Sum Coupled Compositional Optimization (NeurIPS 2025 · similarity 0.90)
- Stability and Generalization of Stochastic Compositional Gradient Descent Algorithms (ICML 2024 · similarity 0.88)
- Projection-Free Variance Reduction Methods for Stochastic Constrained Multi-Level Compositional Optimization (ICML 2024 · similarity 0.87)
- Gradient-Free Methods for Nonconvex Nonsmooth Stochastic Compositional Optimization (NeurIPS 2024 · similarity 0.87)
- A Doubly Recursive Stochastic Compositional Gradient Descent Method for Federated Multi-Level Compositional Optimization (ICML 2024 · similarity 0.86)
- Efficient Algorithms for Empirical Group Distributionally Robust Optimization and Beyond (ICML 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.