ZOFOSGDA: A Hybrid Method for Nonsmooth Nonconvex-Nonconcave Minimax Optimization

Minimax optimization arises in many machine-learning problems, including robust learning, adversarial training, and AUC maximization. Some of these formulations are nonsmooth and may exhibit nonconvex–nonconcave geometry.However, most existing optimization methods are designed primarily for smooth objectives, and their convergence guarantees typically apply only to weakly convex–(strongly) concave or nonconvex–(strongly) concave settings. To address this gap, we study stochastic noncomposite minimax optimization with a nonsmooth, nonconvex outer variable and a smooth, possibly nonconcave inner variable that satisfies a uniform projected Polyak-ojasiewicz condition. We propose ZOFOSGDA, a hybrid method that combines randomized two-point zeroth-order estimates for the outer variable, stochastic first-order gradients for the inner variable, and SPIDER variance reduction. Our stationarity criterion pairs a projected Goldstein residual in the outer block with a projected-gradient residual in the inner block. Under a uniformly bounded initial potential gap and the canonical smoothing radius $\delta =c_{\delta }ϵ=\Theta (ϵ)$, ZOFOSGDA returns both an expected blockwise generalized Goldstein stationary point and an expected projected Goldstein stationary point of the value function. Its oracle costs are $\tilde{\mathcal{O}}(d_1^{3/2}{ϵ}^{-4})$ stochastic function queries and $\tilde{\mathcal{O}}(d_1^{1/2}{ϵ}^{-4})$ stochastic inner-gradient queries, where $d_1$ is the outer dimension. An outer-gradient tracking bound enables the value-function guarantee. A controlled classification benchmark verifies the nonconcave projected-P geometry, while a supplementary AUC-maximization task provides an additional finite-sample stress test.