mlsanityData to 7 Oct 2026

Finite-Sum Coupled Compositional Stochastic Optimization: Theory and Applications

arXiv 2202.12396 ↗First posted 24 Feb 2022math.OC cs.LGcited by 27

Not on the map. Why?

Abstract (arXiv)

This paper studies stochastic optimization for a sum of compositional functions, where the inner-level function of each summand is coupled with the corresponding summation index. We refer to this family of problems as finite-sum coupled compositional optimization (FCCO). It has broad applications in machine learning for optimizing non-convex or convex compositional measures/objectives such as average precision (AP), p-norm push, listwise ranking losses, neighborhood component analysis (NCA), deep survival analysis, deep latent variable models, etc., which deserves finer analysis. Yet, existing algorithms and analyses are restricted in one or other aspects. The contribution of this paper is to provide a comprehensive convergence analysis of a simple stochastic algorithm for both non-convex and convex objectives. Our key result is the improved oracle complexity with the parallel speed-up by using the moving-average based estimator with mini-batching. Our theoretical analysis also exhibits new insights for improving the practical implementation by sampling the batches of equal size for the outer and inner levels. Numerical experiments on AP maximization, NCA, and p-norm push corroborate some aspects of the theory.

Key facts. Cited by 27 papers in the map (data through 7 Oct 2026). Builds on 18 of its 30 references that are in the map. First posted on arXiv 24 Feb 2022.

Builds on

18 of 30 references.

References · 18

  1. 2017Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networkscited by 4,861
  2. 2020REALM: Retrieval-Augmented Language Model Pre-Trainingcited by 2,126
  3. 2021Improving language models by retrieving from trillions of tokenscited by 1,278
  4. 2016DeepSurv: Personalized Treatment Recommender System Using A Cox Proportional Hazards Deep Neural Networkcited by 354
  5. 2017Gradient Sparsification for Communication-Efficient Distributed Optimizationcited by 199
  6. 2020PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimizationcited by 116
  7. 2014Stochastic Compositional Gradient Descent: Algorithms for Minimizing Compositions of Expected-Value Functionscited by 93
  8. 2018Distributed learning with compressed gradientscited by 53
  9. 2018A Single Time-Scale Stochastic Approximation Method for Nested Stochastic Optimizationcited by 53
  10. 2020Biased Stochastic First-Order Methods for Conditional Stochastic Optimization and Applications in Meta Learningcited by 46
  11. 2021Stochastic Optimization of Areas Under Precision-Recall Curves with Provable Convergencecited by 34
  12. 2019Multi-Level Composite Stochastic Optimization via Nested Variance Reductioncited by 28
6 more
  1. 2020Optimal Algorithms for Convex Nested Stochastic Composite Optimizationcited by 20
  2. 2019Non-asymptotic Analysis of Stochastic Methods for Non-Smooth Non-Convex Regularized Problemscited by 14
  3. 2021Momentum Accelerates the Convergence of Stochastic AUPRC Maximizationcited by 14
  4. 2013Stochastic Block Mirror Descent Methods for Nonsmooth and Stochastic Optimizationcited by 12
  5. 2021Variance Reduction via Primal-Dual Accelerated Dual Averaging for Nonsmooth Convex Finite-Sumscited by 10
  6. 2022On the Complexity of a Practical Primal-Dual Coordinate Methodcited by 6

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 6; 2023: 8; 2024: 5; 2025: 5; 2026: 3.

27 papers.

Sort:

By area:

  1. 2022When AUC meets DRO: Optimizing Partial AUC for Deep Learning with Non-Convex Convergence Guaranteecited by 29
  2. 2022Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimizationcited by 16
  3. 2023LibAUC: A Deep Learning Library for X-Risk Optimizationcited by 15
  4. 2022FeDXL: Provable Federated Learning for Deep X-Risk Optimizationcited by 10
  5. 2023Non-Smooth Weakly-Convex Finite-sum Coupled Compositional Optimizationcited by 10
  6. 2025Advantage Shaping as Surrogate Reward Maximization: Unifying Pass@K Policy Gradientscited by 10
  7. 2022Exploring the Algorithm-Dependent Generalization of AUPRC Optimization with List Stabilitycited by 8
  8. 2022Algorithmic Foundations of Empirical X-risk Minimizationcited by 7
  9. 2024FastCLIP: A Suite of Optimization Techniques to Accelerate CLIP Training with Limited Resourcescited by 7
  10. 2023Debiasing Conditional Stochastic Optimizationcited by 6
  11. 2023Learning Unnormalized Statistical Models via Compositional Optimizationcited by 5
  12. 2025Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraintscited by 5
15 more
  1. 2023Federated Conditional Stochastic Optimizationcited by 4
  2. 2025Improved Stochastic Optimization of LogSumExpcited by 4
  3. 2023Provable Multi-instance Deep AUC Maximization with Stochastic Poolingcited by 3
  4. 2023Serverless Federated AUPRC Optimization for Multi-Party Collaborative Imbalanced Data Miningcited by 3
  5. 2023A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimizationcited by 3
  6. 2024A Retention-Centric Framework for Continual Learning with Guaranteed Model Developmental Safetycited by 3
  7. 2024Communication-Efficient Federated Group Distributionally Robust Optimizationcited by 3
  8. 2024Provable Optimization for Adversarial Fair Self-supervised Contrastive Learningcited by 2
  9. 2024On Discriminative Probabilistic Modeling for Self-Supervised Representation Learningcited by 2
  10. 2025Discriminative Finetuning of Generative Large Language Models without Reward Models and Human Preference Datacited by 1
  11. 2026Breaking the Limits of Open-Weight CLIP: An Optimization Framework for Self-supervised Fine-tuning of CLIPcited by 1
  12. 2026A Geometry-Aware Efficient Algorithm for Compositional Entropic Risk Minimizationcited by 1
  13. 2022Fairness via Adversarial Attribute Neighbourhood Robust Learningcited by 0
  14. 2025Stochastic Momentum Methods for Non-smooth Non-Convex Finite-Sum Coupled Compositional Optimizationcited by 0
  15. 2026Scalable Cox Regression via Grouped Risk Sets and Sharper LogSumExp Ratescited by 0