# A Projection-free Algorithm for Constrained Stochastic Multi-level Composition Optimization arXiv: https://arxiv.org/abs/2202.04296 · HTML: https://mlsanity.com/paper/2202.04296/ ## Key facts - Cited by 8 papers in the map (data through 14 Oct 2026). - Builds on 34 of its 59 references that are in the map. - First posted on arXiv 9 Feb 2022. ## Builds on (most cited first, 30 of 34) - [Stochastic model-based minimization of weakly convex functions](https://mlsanity.com/paper/1803.06523/) (2018) - [Tight Analyses for Non-Smooth Stochastic Gradient Descent](https://mlsanity.com/paper/1812.05217/) (2018) - [Stochastic Compositional Gradient Descent: Algorithms for Minimizing Compositions of Expected-Value Functions](https://mlsanity.com/paper/1411.3803/) (2014) - [On the Convergence of Adaptive Gradient Methods for Nonconvex Optimization](https://mlsanity.com/paper/1808.05671/) (2018) - [On the Global Linear Convergence of Frank-Wolfe Optimization Variants](https://mlsanity.com/paper/1511.05932/) (2015) - [A High Probability Analysis of Adaptive SGD with Momentum](https://mlsanity.com/paper/2007.14294/) (2020) - [Minimal Variance Sampling with Provable Guarantees for Fast Training of Graph Neural Networks](https://mlsanity.com/paper/2006.13866/) (2020) - [A Single Time-Scale Stochastic Approximation Method for Nested Stochastic Optimization](https://mlsanity.com/paper/1812.01094/) (2018) - [Solving Stochastic Compositional Optimization is Nearly as Easy as Solving Stochastic Optimization](https://mlsanity.com/paper/2008.10847/) (2020) - [Stochastic Methods for Composite and Weakly Convex Optimization Problems](https://mlsanity.com/paper/1703.08570/) (2017) - [Stochastic Conditional Gradient Methods: From Convex Minimization to Submodular Maximization](https://mlsanity.com/paper/1804.09554/) (2018) - [Biased Stochastic First-Order Methods for Conditional Stochastic Optimization and Applications in Meta Learning](https://mlsanity.com/paper/2002.10790/) (2020) - [Accelerating Stochastic Composition Optimization](https://mlsanity.com/paper/1607.07329/) (2016) - [Faster Rates for the Frank-Wolfe Method over Strongly-Convex Sets](https://mlsanity.com/paper/1406.1305/) (2014) - [An Online Method for A Class of Distributionally Robust Optimization with Non-Convex Objectives](https://mlsanity.com/paper/2006.10138/) (2020) - [Stochastic Frank-Wolfe Methods for Nonconvex Optimization](https://mlsanity.com/paper/1607.08254/) (2016) - [Variance-Reduced and Projection-Free Stochastic Optimization](https://mlsanity.com/paper/1602.02101/) (2016) - [Generalization of Model-Agnostic Meta-Learning Algorithms: Recurring and Unseen Tasks](https://mlsanity.com/paper/2102.03832/) (2021) - [Stochastic Optimization of Areas Under Precision-Recall Curves with Provable Convergence](https://mlsanity.com/paper/2104.08736/) (2021) - [Bayesian Optimization of Function Networks](https://mlsanity.com/paper/2112.15311/) (2021) - [One Sample Stochastic Frank-Wolfe](https://mlsanity.com/paper/1910.04322/) (2019) - [High Probability Convergence Bounds for Non-convex Stochastic Gradient Descent with Sub-Weibull Noise](https://mlsanity.com/paper/2006.05610/) (2020) - [Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow](https://mlsanity.com/paper/1605.08285/) (2016) - [Multi-Level Composite Stochastic Optimization via Nested Variance Reduction](https://mlsanity.com/paper/1908.11468/) (2019) - [Stochastic Multi-level Composition Optimization Algorithms with Level-Independent Convergence Rates](https://mlsanity.com/paper/2008.10526/) (2020) - [Multi-Level Stochastic Gradient Methods for Nested Composition Optimization](https://mlsanity.com/paper/1801.03600/) (2018) - [A Stochastic Subgradient Method for Nonsmooth Nonconvex Multi-Level Composition Optimization](https://mlsanity.com/paper/2001.10669/) (2020) - [Momentum Accelerates the Convergence of Stochastic AUPRC Maximization](https://mlsanity.com/paper/2107.01173/) (2021) - [Conditional Gradient Algorithms for Norm-Regularized Smooth Convex Optimization](https://mlsanity.com/paper/1302.2325/) (2013) - [Linearly Convergent Away-Step Conditional Gradient for Non-strongly Convex Functions](https://mlsanity.com/paper/1504.05002/) (2015) ## Built on by (most cited first, 8 of 8) - [Optimal Algorithms for Stochastic Bilevel Optimization under Relaxed Smoothness Conditions](https://mlsanity.com/paper/2306.12067/) (2023) - [A Single-Timescale Analysis For Stochastic Approximation With Multiple Coupled Sequences](https://mlsanity.com/paper/2206.10414/) (2022) - [Constrained Stochastic Nonconvex Optimization with State-dependent Markov Data](https://mlsanity.com/paper/2206.11346/) (2022) - [Validation of Composite Systems by Discrepancy Propagation](https://mlsanity.com/paper/2210.12061/) (2022) - [Projection-Free Variance Reduction Methods for Stochastic Constrained Multi-Level Compositional Optimization](https://mlsanity.com/paper/2406.03787/) (2024) - [Stochastic Compositional Optimization via Hybrid Momentum Frank--Wolfe](https://mlsanity.com/paper/2605.15350/) (2026) - [On the Convergence of Stochastic Gradient Descent with Perturbed Forward-Backward Passes](https://mlsanity.com/paper/2602.20646/) (2026) - [Optimal Momentum Methods for Stochastic Multilevel Compositional Optimization](https://mlsanity.com/paper/2610.01572/) (2026) ## 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.