Stochastic Compositional Optimization via Hybrid Momentum Frank--Wolfe
Abstract
Stochastic compositional optimization minimizes $F(f(x), x)$ over a compact convex set when the inner map f is available only through noisy samples. We propose Hybrid Momentum Stochastic Frank--Wolfe, a projection-free method for outer functions F that are jointly convex and Lipschitz but not necessarily differentiable, such as maxima, CVaR, and norms. The method tracks the Jacobian and the value of f with momentum, using a Taylor correction for the value, and passes the tracked linearization to a generalized linear minimization oracle. Under finite-variance noise, it attains an expected generalized Frank--Wolfe gap of order K−1/4 for non-convex objectives and, when the linearized models minorize the objective, a last-iterate primal error of order K−1/3. The analysis extends to heavy-tailed noise without clipping, with separate moment orders for values and Jacobians. With an exact oracle, the method reduces to the deterministic method of Vladarean et al. (2023).
Related
- Optimal Momentum Methods for Stochastic Multilevel Compositional Optimization
- Projection-Free Multi-level Algorithms for Stochastic Constrained Compositional Optimization
- Asynchronous Parallel Computation of Lagrangian Bounds for Mixed-Integer Stochastic Programs by Frank-Wolfe Methods within Projective Hedging
- A Frank-Wolfe-based primal heuristic for quadratic mixed-integer optimization
- Solving Finite-sum Coupled Compositional Optimization via Multi-block-Single-probe Estimator
BibTeX
@misc{chayti2026stochastic,
title = {{Stochastic Compositional Optimization via Hybrid Momentum Frank--Wolfe}},
author = {El Mahdi Chayti and Mohamad Fakhouri},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2605.15350},
eprint = {2605.15350},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.15350},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Stochastic Compositional Optimization via Hybrid Momentum Frank--Wolfe
AU - El Mahdi Chayti
AU - Mohamad Fakhouri
PY - 2026
DA - 2026/10/09
PB - arXiv
DO - 10.48550/arxiv.2605.15350
UR - https://arxiv.org/abs/2605.15350
AB - Stochastic compositional optimization minimizes $F(f(x), x)$ over a compact convex set when the inner map f is available only through noisy samples. We propose Hybrid Momentum Stochastic Frank--Wolfe, a projection-free method for outer functions F that are jointly convex and Lipschitz but not necessarily differentiable, such as maxima, CVaR, and norms. The method tracks the Jacobian and the value of f with momentum, using a Taylor correction for the value, and passes the tracked linearization to a generalized linear minimization oracle. Under finite-variance noise, it attains an expected generalized Frank--Wolfe gap of order K^−1/4 for non-convex objectives and, when the linearized models minorize the objective, a last-iterate primal error of order K^−1/3. The analysis extends to heavy-tailed noise without clipping, with separate moment orders for values and Jacobians. With an exact oracle, the method reduces to the deterministic method of Vladarean et al. (2023).
ER -