# Projection-Free Variance Reduction Methods for Stochastic Constrained Multi-Level Compositional Optimization

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 49 references that are in the map.
- First posted on arXiv 6 Jun 2024.

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

- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [Stochastic Compositional Gradient Descent: Algorithms for Minimizing Compositions of Expected-Value Functions](https://mlsanity.com/paper/1411.3803/) (2014)
- [Convergence Rate of Frank-Wolfe for Non-Convex Objectives](https://mlsanity.com/paper/1607.00345/) (2016)
- [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)
- [Accelerating Stochastic Composition Optimization](https://mlsanity.com/paper/1607.07329/) (2016)
- [On Tilted Losses in Machine Learning: Theory and Applications](https://mlsanity.com/paper/2109.06141/) (2021)
- [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)
- [Faster Projection-free Online Learning](https://mlsanity.com/paper/2001.11568/) (2020)
- [One Sample Stochastic Frank-Wolfe](https://mlsanity.com/paper/1910.04322/) (2019)
- [Multi-Level Composite Stochastic Optimization via Nested Variance Reduction](https://mlsanity.com/paper/1908.11468/) (2019)
- [Theoretical Convergence of Multi-Step Model-Agnostic Meta-Learning](https://mlsanity.com/paper/2002.07836/) (2020)
- [A Stochastic Composite Gradient Method with Incremental Variance Reduction](https://mlsanity.com/paper/1906.10186/) (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)
- [Projection-free Online Learning over Strongly Convex Sets](https://mlsanity.com/paper/2010.08177/) (2020)
- [Optimal Algorithms for Stochastic Multi-Level Compositional Optimization](https://mlsanity.com/paper/2202.07530/) (2022)
- [Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization](https://mlsanity.com/paper/2207.08540/) (2022)
- [Projection-free Distributed Online Learning with Sublinear Communication Complexity](https://mlsanity.com/paper/2103.11102/) (2021)
- [Non-stationary Projection-free Online Learning with Dynamic and Adaptive Regret Guarantees](https://mlsanity.com/paper/2305.11726/) (2023)
- [Non-convex Conditional Gradient Sliding](https://mlsanity.com/paper/1708.04783/) (2017)
- [Efficient Algorithms for Empirical Group Distributionally Robust Optimization and Beyond](https://mlsanity.com/paper/2403.03562/) (2024)
- [Exploiting the Curvature of Feasible Sets for Faster Projection-Free Online Learning](https://mlsanity.com/paper/2205.11470/) (2022)
- [Projection-free Online Exp-concave Optimization](https://mlsanity.com/paper/2302.04859/) (2023)
- [A Projection-free Algorithm for Constrained Stochastic Multi-level Composition Optimization](https://mlsanity.com/paper/2202.04296/) (2022)
- [Learning Unnormalized Statistical Models via Compositional Optimization](https://mlsanity.com/paper/2306.07485/) (2023)

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

- [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)

This paper investigates projection-free algorithms for stochastic constrained multi-level optimization. In this context, the objective function is a nested composition of several smooth functions, and the decision set is closed and convex. Existing projection-free algorithms for solving this problem suffer from two limitations: 1) they solely focus on the gradient mapping criterion and fail to match the optimal sample complexities in unconstrained settings; 2) their analysis is exclusively applicable to non-convex functions, without considering convex and strongly convex objectives. To address these issues, we introduce novel projection-free variance reduction algorithms and analyze their complexities under different criteria. For gradient mapping, our complexities improve existing results and match the optimal rates for unconstrained problems. For the widely-used Frank-Wolfe gap criterion, we provide theoretical guarantees that align with those for single-level problems. Additionally, by using a stage-wise adaptation, we further obtain complexities for convex and strongly convex functions. Finally, numerical experiments on different tasks demonstrate the effectiveness of our methods.