Stochastic Compositional Optimization via Hybrid Momentum Frank--Wolfe

Stochastic compositional optimization minimizes objectives of the form $\min_{\vx \in \cX} F(\vf(\vx), \vx)$, where $\vf$ is accessible only through noisy queries. Existing stochastic methods assume the outer function $F$ is continuously differentiable, which excludes robust max-of-losses, Conditional Value-at-Risk, and norm regularizers. We propose the Hybrid Momentum Stochastic Frank--Wolfe algorithm, which drops this assumption. Combining a momentum Jacobian tracker with a Taylor-corrected function tracker, it feeds an entire stochastic linearization, rather than a single gradient, into a generalized linear minimization oracle. We prove an $\mathcal{O}(K^{-1/4})$ rate in the generalized Frank--Wolfe gap for non-convex objectives with $L_F$-Lipschitz $F$, which is optimal for single-sample projection-free stochastic methods under expected smoothness, and the analysis covers heavy-tailed noise with bounded $r$-th moments, $r \in (1,2]$.