Projection-free algorithms improve complex optimization with constraints
Projection-Free Multi-level Algorithms for Stochastic Constrained Compositional Optimization
Machine Learning
Summary
Optimizing complicated problems made of nested functions often requires adjusting solutions to fit certain rules, which can be slow or difficult. The authors developed new methods that avoid the slow step of projecting solutions back into allowed regions, instead using a shortcut that simplifies each step. These methods work well even when the problem is hard to solve and have proven guarantees on how fast they get close to a good answer. Experiments show these methods work effectively in practice.
What this means in practice
- •For machine learning engineers: Create efficient training routines for models with complex layers under constraints without expensive projection steps.
- •For operations research teams: Solve multi-stage decision-making problems with nested objectives more efficiently in resource allocation or logistics.
Authors
Wei Jiang, Sifan Yang, Wenhao Yang, Yibo Wang, Yuanyu Wan, Zechao Li, Lijun Zhang
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.