From Lyapunov Analysis to Algorithm Design in two-sided PL Minimax Optimization

We derive algorithms for smooth nonconvex nonconcave minimax optimization and establish linear convergence rates for problems that satisfy the two-sided Polyak-Lojasiewicz (PL) inequality. At the core of our approach is the observation that Lyapunov functions can be used not only to certify convergence a posteriori, but also to design algorithms. By replacing an idealized, intractable Lyapunov function with a computable surrogate based on gradient information, we derive TALDA (Tri-Action Lyapunov Descent Ascent), a single-loop algorithm that enforces Lyapunov descent by construction. TALDA guarantees linear convergence under the two-sided PL condition, with a rate that depends explicitly on the cross-smoothness constant. This recovers existing worst-case guarantees while yielding sharper convergence rates in weakly coupled min–max problems.

Many modern machine learning problems can be viewed as a game between two competing objectives, where improving one side can worsen the other. Designing algorithms that reliably solve these problems is challenging: even simple methods such as gradient descent-ascent can fail to converge in basic settings like bilinear games. In this work, we propose a new way to design optimization algorithms using Lyapunov functions, which are energy-like quantities used to study stability in dynamical systems. In physical systems, decreasing energy often indicates that the system is becoming stable. Similarly, in optimization, Lyapunov functions are typically used to prove that an algorithm converges. We ask a different question: instead of using Lyapunov functions only to analyze algorithms, can they be used to directly construct stable update rules? We answer this question positively by developing a new algorithmic framework for a class of nonconvex-nonconcave minimax problems. Our approach uses Lyapunov functions as a design principle, leading to algorithms that are stable and convergent by construction.