mlsanityData to 7 Oct 2026

A Projection-free Algorithm for Constrained Stochastic Multi-level Composition Optimization

arXiv 2202.04296 ↗First posted 9 Feb 2022math.OC math.ST stat.MLcited by 8

Not on the map. Why?

Abstract (arXiv)

We propose a projection-free conditional gradient-type algorithm for smooth stochastic multi-level composition optimization, where the objective function is a nested composition of T functions and the constraint set is a closed convex set. Our algorithm assumes access to noisy evaluations of the functions and their gradients, through a stochastic first-order oracle satisfying certain standard unbiasedness and second moment assumptions. We show that the number of calls to the stochastic first-order oracle and the linear-minimization oracle required by the proposed algorithm, to obtain an ε-stationary solution, are of order OT(ε-2) and OT(ε-3) respectively, where OT hides constants in T. Notably, the dependence of these complexity bounds on ε and T are separate in the sense that changing one does not impact the dependence of the bounds on the other. Moreover, our algorithm is parameter-free and does not require any (increasing) order of mini-batches to converge unlike the common practice in the analysis of stochastic conditional gradient-type algorithms.

Key facts. Cited by 8 papers in the map (data through 7 Oct 2026). Builds on 34 of its 59 references that are in the map. First posted on arXiv 9 Feb 2022.

Builds on

34 of 59 references.

References · 34

  1. 2018Stochastic model-based minimization of weakly convex functionscited by 157
  2. 2018Tight Analyses for Non-Smooth Stochastic Gradient Descentcited by 94
  3. 2014Stochastic Compositional Gradient Descent: Algorithms for Minimizing Compositions of Expected-Value Functionscited by 93
  4. 2018On the Convergence of Adaptive Gradient Methods for Nonconvex Optimizationcited by 91
  5. 2015On the Global Linear Convergence of Frank-Wolfe Optimization Variantscited by 76
  6. 2020A High Probability Analysis of Adaptive SGD with Momentumcited by 61
  7. 2020Minimal Variance Sampling with Provable Guarantees for Fast Training of Graph Neural Networkscited by 54
  8. 2018A Single Time-Scale Stochastic Approximation Method for Nested Stochastic Optimizationcited by 53
  9. 2020Solving Stochastic Compositional Optimization is Nearly as Easy as Solving Stochastic Optimizationcited by 51
  10. 2017Stochastic Methods for Composite and Weakly Convex Optimization Problemscited by 48
  11. 2018Stochastic Conditional Gradient Methods: From Convex Minimization to Submodular Maximizationcited by 47
  12. 2016Accelerating Stochastic Composition Optimizationcited by 46
22 more
  1. 2020Biased Stochastic First-Order Methods for Conditional Stochastic Optimization and Applications in Meta Learningcited by 46
  2. 2014Faster Rates for the Frank-Wolfe Method over Strongly-Convex Setscited by 42
  3. 2020An Online Method for A Class of Distributionally Robust Optimization with Non-Convex Objectivescited by 42
  4. 2016Variance-Reduced and Projection-Free Stochastic Optimizationcited by 40
  5. 2016Stochastic Frank-Wolfe Methods for Nonconvex Optimizationcited by 40
  6. 2021Generalization of Model-Agnostic Meta-Learning Algorithms: Recurring and Unseen Taskscited by 36
  7. 2021Stochastic Optimization of Areas Under Precision-Recall Curves with Provable Convergencecited by 34
  8. 2021Bayesian Optimization of Function Networkscited by 33
  9. 2019One Sample Stochastic Frank-Wolfecited by 32
  10. 2020High Probability Convergence Bounds for Non-convex Stochastic Gradient Descent with Sub-Weibull Noisecited by 31
  11. 2016Solving Systems of Random Quadratic Equations via Truncated Amplitude Flowcited by 28
  12. 2019Multi-Level Composite Stochastic Optimization via Nested Variance Reductioncited by 28
  13. 2020Stochastic Multi-level Composition Optimization Algorithms with Level-Independent Convergence Ratescited by 25
  14. 2018Multi-Level Stochastic Gradient Methods for Nested Composition Optimizationcited by 24
  15. 2020A Stochastic Subgradient Method for Nonsmooth Nonconvex Multi-Level Composition Optimizationcited by 16
  16. 2021Momentum Accelerates the Convergence of Stochastic AUPRC Maximizationcited by 14
  17. 2013Conditional Gradient Algorithms for Norm-Regularized Smooth Convex Optimizationcited by 13
  18. 2015Linearly Convergent Away-Step Conditional Gradient for Non-strongly Convex Functionscited by 12
  19. 2017Non-convex Conditional Gradient Slidingcited by 12
  20. 2021Frank-Wolfe with a Nearest Extreme Point Oraclecited by 8
  21. 2017Unbiased Simulation for Optimizing Stochastic Function Compositionscited by 6
  22. 2018Improved Complexities of Conditional Gradient-Type Methods with Applications to Robust Matrix Recovery Problemscited by 6

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 3; 2023: 1; 2024: 1; 2025: 0; 2026: 3.

8 papers.

  1. 2023Optimal Algorithms for Stochastic Bilevel Optimization under Relaxed Smoothness Conditionscited by 31
  2. 2022A Single-Timescale Analysis For Stochastic Approximation With Multiple Coupled Sequencescited by 17
  3. 2022Constrained Stochastic Nonconvex Optimization with State-dependent Markov Datacited by 6
  4. 2022Validation of Composite Systems by Discrepancy Propagationcited by 2
  5. 2024Projection-Free Variance Reduction Methods for Stochastic Constrained Multi-Level Compositional Optimizationcited by 2
  6. 2026On the Convergence of Stochastic Gradient Descent with Perturbed Forward-Backward Passescited by 0
  7. 2026Stochastic Compositional Optimization via Hybrid Momentum Frank--Wolfecited by 0
  8. 2026Optimal Momentum Methods for Stochastic Multilevel Compositional Optimizationcited by 0