# Finite-Sum Coupled Compositional Stochastic Optimization: Theory and Applications

arXiv: https://arxiv.org/abs/2202.12396 · HTML: https://mlsanity.com/paper/2202.12396/

## Key facts

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

## Builds on (most cited first, 18 of 18)

- [Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks](https://mlsanity.com/paper/1703.03400/) (2017)
- [REALM: Retrieval-Augmented Language Model Pre-Training](https://mlsanity.com/paper/2002.08909/) (2020)
- [Improving language models by retrieving from trillions of tokens](https://mlsanity.com/paper/2112.04426/) (2021)
- [DeepSurv: Personalized Treatment Recommender System Using A Cox Proportional Hazards Deep Neural Network](https://mlsanity.com/paper/1606.00931/) (2016)
- [Gradient Sparsification for Communication-Efficient Distributed Optimization](https://mlsanity.com/paper/1710.09854/) (2017)
- [PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization](https://mlsanity.com/paper/2008.10898/) (2020)
- [Stochastic Compositional Gradient Descent: Algorithms for Minimizing Compositions of Expected-Value Functions](https://mlsanity.com/paper/1411.3803/) (2014)
- [Distributed learning with compressed gradients](https://mlsanity.com/paper/1806.06573/) (2018)
- [A Single Time-Scale Stochastic Approximation Method for Nested Stochastic Optimization](https://mlsanity.com/paper/1812.01094/) (2018)
- [Biased Stochastic First-Order Methods for Conditional Stochastic Optimization and Applications in Meta Learning](https://mlsanity.com/paper/2002.10790/) (2020)
- [Stochastic Optimization of Areas Under Precision-Recall Curves with Provable Convergence](https://mlsanity.com/paper/2104.08736/) (2021)
- [Multi-Level Composite Stochastic Optimization via Nested Variance Reduction](https://mlsanity.com/paper/1908.11468/) (2019)
- [Optimal Algorithms for Convex Nested Stochastic Composite Optimization](https://mlsanity.com/paper/2011.10076/) (2020)
- [Non-asymptotic Analysis of Stochastic Methods for Non-Smooth Non-Convex Regularized Problems](https://mlsanity.com/paper/1902.07672/) (2019)
- [Momentum Accelerates the Convergence of Stochastic AUPRC Maximization](https://mlsanity.com/paper/2107.01173/) (2021)
- [Stochastic Block Mirror Descent Methods for Nonsmooth and Stochastic Optimization](https://mlsanity.com/paper/1309.2249/) (2013)
- [Variance Reduction via Primal-Dual Accelerated Dual Averaging for Nonsmooth Convex Finite-Sums](https://mlsanity.com/paper/2102.13643/) (2021)
- [On the Complexity of a Practical Primal-Dual Coordinate Method](https://mlsanity.com/paper/2201.07684/) (2022)

## Built on by (most cited first, 27 of 27)

- [When AUC meets DRO: Optimizing Partial AUC for Deep Learning with Non-Convex Convergence Guarantee](https://mlsanity.com/paper/2203.00176/) (2022)
- [Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization](https://mlsanity.com/paper/2207.08540/) (2022)
- [LibAUC: A Deep Learning Library for X-Risk Optimization](https://mlsanity.com/paper/2306.03065/) (2023)
- [FeDXL: Provable Federated Learning for Deep X-Risk Optimization](https://mlsanity.com/paper/2210.14396/) (2022)
- [Advantage Shaping as Surrogate Reward Maximization: Unifying Pass@K Policy Gradients](https://mlsanity.com/paper/2510.23049/) (2025)
- [Non-Smooth Weakly-Convex Finite-sum Coupled Compositional Optimization](https://mlsanity.com/paper/2310.03234/) (2023)
- [FastCLIP: A Suite of Optimization Techniques to Accelerate CLIP Training with Limited Resources](https://mlsanity.com/paper/2407.01445/) (2024)
- [Algorithmic Foundations of Empirical X-risk Minimization](https://mlsanity.com/paper/2206.00439/) (2022)
- [Exploring the Algorithm-Dependent Generalization of AUPRC Optimization with List Stability](https://mlsanity.com/paper/2209.13262/) (2022)
- [Debiasing Conditional Stochastic Optimization](https://mlsanity.com/paper/2304.10613/) (2023)
- [Learning Unnormalized Statistical Models via Compositional Optimization](https://mlsanity.com/paper/2306.07485/) (2023)
- [Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints](https://mlsanity.com/paper/2504.15243/) (2025)
- [Federated Conditional Stochastic Optimization](https://mlsanity.com/paper/2310.02524/) (2023)
- [A Retention-Centric Framework for Continual Learning with Guaranteed Model Developmental Safety](https://mlsanity.com/paper/2410.03955/) (2024)
- [Improved Stochastic Optimization of LogSumExp](https://mlsanity.com/paper/2509.24894/) (2025)
- [Provable Multi-instance Deep AUC Maximization with Stochastic Pooling](https://mlsanity.com/paper/2305.08040/) (2023)
- [Serverless Federated AUPRC Optimization for Multi-Party Collaborative Imbalanced Data Mining](https://mlsanity.com/paper/2308.03035/) (2023)
- [A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization](https://mlsanity.com/paper/2312.02277/) (2023)
- [Communication-Efficient Federated Group Distributionally Robust Optimization](https://mlsanity.com/paper/2410.06369/) (2024)
- [Provable Optimization for Adversarial Fair Self-supervised Contrastive Learning](https://mlsanity.com/paper/2406.05686/) (2024)
- [On Discriminative Probabilistic Modeling for Self-Supervised Representation Learning](https://mlsanity.com/paper/2410.09156/) (2024)
- [Discriminative Finetuning of Generative Large Language Models without Reward Models and Human Preference Data](https://mlsanity.com/paper/2502.18679/) (2025)
- [Breaking the Limits of Open-Weight CLIP: An Optimization Framework for Self-supervised Fine-tuning of CLIP](https://mlsanity.com/paper/2601.09859/) (2026)
- [A Geometry-Aware Efficient Algorithm for Compositional Entropic Risk Minimization](https://mlsanity.com/paper/2602.02877/) (2026)
- [Fairness via Adversarial Attribute Neighbourhood Robust Learning](https://mlsanity.com/paper/2210.06630/) (2022)
- [Stochastic Momentum Methods for Non-smooth Non-Convex Finite-Sum Coupled Compositional Optimization](https://mlsanity.com/paper/2506.02504/) (2025)
- [Scalable Cox Regression via Grouped Risk Sets and Sharper LogSumExp Rates](https://mlsanity.com/paper/2609.40120/) (2026)

## 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.