mlsanityData to 7 Oct 2026

A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization

arXiv 2312.02277 ↗First posted 4 Dec 2023math.OC cs.LGcited by 3

Not on the map. Why?

Abstract (arXiv)

This paper studies a class of convex Finite-sum Coupled Compositional Optimization (cFCCO) problems with applications including group distributionally robust optimization (GDRO) and learning with imbalanced data. To better address these problems, we introduce an efficient single-loop primal-dual block-coordinate stochastic algorithm called ALEXR. The algorithm employs block-coordinate stochastic mirror ascent with extrapolation for the dual variable and stochastic proximal gradient descent updates for the primal variable. We establish the convergence rates of ALEXR in both convex and strongly convex cases under smoothness and non-smoothness conditions of involved functions, which not only improve the best rates in previous works on smooth cFCCO problems but also expand the realm of cFCCO for solving more challenging non-smooth problems such as the dual form of GDRO. Finally, we derive lower complexity bounds, demonstrating the (near-)optimality of ALEXR within a broad class of stochastic algorithms for cFCCO. Experimental results on GDRO and partial Area Under the ROC Curve (pAUC) maximization demonstrate the promising performance of our algorithm.

Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 29 of its 46 references that are in the map. First posted on arXiv 4 Dec 2023.

Builds on

29 of 46 references.

References · 29

  1. 2014Deep Learning Face Attributes in the Wildcited by 3,679
  2. 2019Distributionally Robust Neural Networks for Group Shifts: On the Importance of Regularization for Worst-Case Generalizationcited by 1,232
  3. 2021MedMNIST v2 -- A large-scale lightweight benchmark for 2D and 3D biomedical image classificationcited by 682
  4. 2017A systematic study of the class imbalance problem in convolutional neural networkscited by 510
  5. 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 302
  6. 2020Large-Scale Methods for Distributionally Robust Optimizationcited by 179
  7. 2022AUC Maximization in the Era of Big Data and AI: A Surveycited by 100
  8. 2014Stochastic Compositional Gradient Descent: Algorithms for Minimizing Compositions of Expected-Value Functionscited by 93
  9. 2019On the convergence of single-call stochastic extra-gradient methodscited by 88
  10. 2016Accelerating Stochastic Composition Optimizationcited by 46
  11. 2020Biased Stochastic First-Order Methods for Conditional Stochastic Optimization and Applications in Meta Learningcited by 46
  12. 2022Provable Stochastic Optimization for Global Contrastive Learning: Small Batch Does Not Harm Performancecited by 40
17 more
  1. 2014Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimizationcited by 30
  2. 2022When AUC meets DRO: Optimizing Partial AUC for Deep Learning with Non-Convex Convergence Guaranteecited by 29
  3. 2022Finite-Sum Coupled Compositional Stochastic Optimization: Theory and Applicationscited by 27
  4. 2023Not All Semantics are Created Equal: Contrastive Self-supervised Learning with Automatic Temperature Individualizationcited by 25
  5. 2022Large-scale Stochastic Optimization of NDCG Surrogates for Deep Learning with Provable Convergencecited by 21
  6. 2020Optimal Algorithms for Convex Nested Stochastic Composite Optimizationcited by 20
  7. 2018Tight Dimension Independent Lower Bound on the Expected Convergence Rate for Diminishing Step Sizes in SGDcited by 18
  8. 2022Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimizationcited by 16
  9. 2022Near-Optimal Algorithms for Group Distributionally Robust Optimization and Beyondcited by 16
  10. 2020Random extrapolation for primal-dual coordinate descentcited by 10
  11. 2021Robust Accelerated Primal-Dual Methods for Computing Saddle Pointscited by 10
  12. 2023Non-Smooth Weakly-Convex Finite-sum Coupled Compositional Optimizationcited by 10
  13. 2023Blockwise Stochastic Variance-Reduced Methods with Parallel Speedup for Multi-Block Bilevel Optimizationcited by 8
  14. 2022Algorithmic Foundations of Empirical X-risk Minimizationcited by 7
  15. 2022On the Complexity of a Practical Primal-Dual Coordinate Methodcited by 6
  16. 2023A Model-Based Method for Minimizing CVaR and Beyondcited by 5
  17. 2018Randomized Primal-Dual Methods with Adaptive Step Sizescited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 1; 2026: 2.

3 papers.

  1. 2025Stochastic Primal-Dual Double Block-Coordinate for Two-way Partial AUC Maximizationcited by 1
  2. 2026A Geometry-Aware Efficient Algorithm for Compositional Entropic Risk Minimizationcited by 1
  3. 2026Scalable Cox Regression via Grouped Risk Sets and Sharper LogSumExp Ratescited by 0