pipette
ENEnglish

Stochastic Gradient Descent Ascent is Suboptimal for Nonconvex-PL Min-Max Games

Junsoo Ha

Preprint

En palabras de los autores

How far can stochastic gradient descent ascent (SGDA) go by tuning its timescale ratio and step sizes in nonconvex min-max games? We answer this question for nonconvex-PL (NC-PL) games by establishing the first tight complexity of two-timescale SGDA with a fixed timescale ratio and non-increasing step sizes. For -smooth games with an inner -PL inequality, we prove a complexity lower bound , where is the condition number, is the gradient variance, and measures the outer gradient norm. This matches existing SGDA upper bounds and establishes a complexity separation from Smoothed-AGDA (Yang et al., 22'). In addition, we show that SGDA can fail to find a stationary point when its timescale ratio is as small as . Our negative results highlight the fundamental limitation of SGDA in NC-PL games, and justify the development of alternative methods.

Resultado principalEl resumen no menciona limitaciones.

Apareció: miércoles, 7 de octubre. arXiv. Preprint, todavía sin revisión por pares.