On the Convergence of Stochastic Smoothed Multi-Level Compositional Gradient Descent Ascent

Multi-level compositional optimization is a fundamental framework in machine learning with broad applications. While recent advances have addressed compositional minimization problems, the stochastic multi-level compositional minimax problem introduces significant new challenges-most notably, the biased nature of stochastic gradients for both the primal and dual variables. In this work, we address this gap by proposing a novel stochastic multi-level compositional gradient descentascent algorithm, incorporating a smoothing technique under the nonconvex-PL condition. We establish a convergence rate to an (ϵ, ϵ/ √ κ)-stationary point with improved dependence on the condition number at O(κ 3/2 ), where ϵ denotes the solution accuracy and κ represents the condition number. Moreover, we design a novel stage-wise algorithm with variance reduction to address the biased gradient issue under the two-sided PL condition. This algorithm successfully enables a translation from and (ϵ, ϵ/ √ κ)-stationary point to an ϵ-stationary point. Finally, extensive experiments validate the effectiveness of our algorithms.