Projection-Free Multi-level Algorithms for Stochastic Constrained Compositional Optimization
Abstract
This paper studies projection-free algorithms for stochastic constrained multi-level compositional optimization. In this context, the objective function is a nested composition of several smooth functions, and the decision set is closed and convex. Since projection onto the constraint set can be computationally expensive, we develop projection-free methods that rely on linear minimization oracles. For non-convex objectives, we propose variance-reduced projection-free algorithms and establish complexity guarantees under both the Frank-Wolfe gap and the gradient mapping criteria. We also develop momentum-based methods that achieve convergence guarantees under weaker smoothness assumptions. Additionally, by using a stage-wise design, we derive a parameter-free variant that preserves the same complexities for the Frank-Wolfe gap. Such a design can be further used to develop algorithms for convex and strongly convex functions whose rates match those of single-level projection-free counterparts. Finally, we consider finite-sum problems and derive complexities for non-convex, convex, and strongly convex objectives. Numerical experiments across multiple tasks demonstrate the effectiveness of the proposed methods.
Related
- Constrained Nonconvex Stochastic Optimization with One Projection
- Projection-Free Algorithms for Nonsmooth Stochastic Convex-Concave Saddle-Point Problems
- Stochastic Compositional Optimization via Hybrid Momentum Frank--Wolfe
- Optimal Momentum Methods for Stochastic Multilevel Compositional Optimization
- Denoising as Projection: Constrained Optimization with Gradient-Guided Diffusion
BibTeX
@misc{jiang2026projectionfree,
title = {{Projection-Free Multi-level Algorithms for Stochastic Constrained Compositional Optimization}},
author = {Wei Jiang and Sifan Yang and Wenhao Yang and Yibo Wang and Yuanyu Wan and Zechao Li and Lijun Zhang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.15679},
eprint = {2609.15679},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.15679},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Projection-Free Multi-level Algorithms for Stochastic Constrained Compositional Optimization
AU - Wei Jiang
AU - Sifan Yang
AU - Wenhao Yang
AU - Yibo Wang
AU - Yuanyu Wan
AU - Zechao Li
AU - Lijun Zhang
PY - 2026
DA - 2026/09/14
PB - arXiv
DO - 10.48550/arxiv.2609.15679
UR - https://arxiv.org/abs/2609.15679
AB - This paper studies projection-free algorithms for stochastic constrained multi-level compositional optimization. In this context, the objective function is a nested composition of several smooth functions, and the decision set is closed and convex. Since projection onto the constraint set can be computationally expensive, we develop projection-free methods that rely on linear minimization oracles. For non-convex objectives, we propose variance-reduced projection-free algorithms and establish complexity guarantees under both the Frank-Wolfe gap and the gradient mapping criteria. We also develop momentum-based methods that achieve convergence guarantees under weaker smoothness assumptions. Additionally, by using a stage-wise design, we derive a parameter-free variant that preserves the same complexities for the Frank-Wolfe gap. Such a design can be further used to develop algorithms for convex and strongly convex functions whose rates match those of single-level projection-free counterparts. Finally, we consider finite-sum problems and derive complexities for non-convex, convex, and strongly convex objectives. Numerical experiments across multiple tasks demonstrate the effectiveness of the proposed methods.
ER -