On the Convergence of Stochastic Smoothed Multi-Level Compositional Gradient Descent Ascent
Xinwen Zhang, Hongchang Gao
Multi-level compositional optimization is a fundamental framework in machine learning with broad applications. While recent advances have addressed the stochastic optimization of minimization problems, the multi-level compositional minimax setting introduces significant new challenges—the biased nature of stochastic gradients for both the primal and dual variables. In this work, we address this gap by proposing a stochastic multi-level compositional gradient descent ascent algorithm  with variance reduction,  incorporating smoothed technique under the nonconvex-PL condition. We establish a convergence rate to an $(\epsilon, \epsilon/\sqrt{\kappa})$-stationary point with improved dependence on the condition number at $O\left(\kappa^{3/2}\right)$. To obtain an $\epsilon$-stationary point, we further design a stage-wise algorithm under the two-sided PL condition that enables a translation between two stationarity measures. Extensive experiments validate the effectiveness of our approach.