A Projection-free Algorithm for Constrained Stochastic Multi-level Composition Optimization
This work addresses optimization challenges in machine learning and AI where objectives involve nested compositions and constraints, offering a parameter-free method with separate complexity dependence on ε and T, though it appears incremental relative to existing conditional gradient-type algorithms.
The paper tackles the problem of constrained stochastic multi-level composition optimization by proposing a projection-free conditional gradient-type algorithm, achieving complexity bounds of O_T(ε^{-2}) for stochastic first-order oracle calls and O_T(ε^{-3}) for linear-minimization oracle calls to obtain an ε-stationary solution.
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 $\mathcal{O}_T(ε^{-2})$ and $\mathcal{O}_T(ε^{-3})$ respectively, where $\mathcal{O}_T$ 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.