Limited Memory LRSGA Optimizer to competitive optimization

Katherine Rossella Foglia, Francesco Sergio Pisani, Vittorio Colao · 2025

Read Limited Memory LRSGA Optimizer to competitive optimization by Katherine Rossella Foglia, Francesco Sergio Pisani, Vittorio Colao (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-26983.txt.

Introduction

Katherine Foglia, Francesco Pisani, and Vittorio Colao present a memory-light method for finding Nash equilibria, meaning stable points where no player gains by moving alone, in smooth competitive problems. Their method adapts a gradient scheme that adds stabilizing second-order fixes through low-rank data. Storing full history is costly when models have many parameters, as in adversarial networks that pit two models against each other.

The new variant keeps only a short history of curvature pairs and rebuilds the fix through a two-loop routine. The authors give a per-step stability condition near equilibria and a local convergence analysis for fixed history length. Tests on image training tasks include checks of the training dynamics that support the theory.

Catalog record

CREATORKatherine Rossella Foglia, Francesco Sergio Pisani, Vittorio Colao
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE46 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-26983

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Limited Memory LRSGA Optimizer to competitive optimization Katherine Rossella Foglia, Francesco Sergio Pisani, Vittorio Colao Abstract We introduce LM-LRSGA, a limited-memory variant of Low-Rank Symplectic Gradient Adjustment (LRSGA) for differentiable games. It is an iterative scheme for approximating Nash equilibria at first-order cost while preserving the stabilizing benefits of second-order information. By storing only a limited history of curvature pairs, LM-LRSGA is well suited to high-parameter competitive models such as GANs. Keywords Nash equilibria \cdot Competitive optimization \cdot GreenAI \cdot Limited memory \cdot Spectral analysis 1 Introduction Optimization in multi-agent and adversarial settings is a central challenge in modern machine learning. Examples include Generative Adversarial Networks (GANs), adversarial training for robustness, and multi-agent reinforcement learning, where two or more agents optimize distinct, often conflicting objectives. These problems can be viewed as differentiable games: each agent minimizes its own objective. Despite the similarity to classical optimization, the coupled objectives and the lack of a single potential make the dynamics fundamentally different. Even in the two-player case, gradient methods may cycle, oscillate, or diverge rather than converge to equilibrium Arjovsky et al. 2017 ; M Wiatrak 2019 ; Balduzzi et al. 2018 . Formally, for the two-player setting, we denote by x\in\mathbb{R}^{m} and y\in\mathbb{R}^{n} the strategy variables for Players 1 and 2, and by f,g:\mathbb{R}^{m+n}\to\mathbb{R} the corresponding payoff functions. A Nash equilibrium (x^{*},y^{*}) is a pair where neither player can locally improve its objective, holding the other fixed. For differentiable f and g , the first-order conditions are \partial_{x}f(x^{*},y^{*})=0,\qquad\partial_{y}g(x^{*},y^{*})=0. (1) Stacking w=(x,y)\in\mathbb{R}^{m+n} , the game gradient is defined as F(w)=\begin{pmatrix}\partial_{x}f(w)\\[3.0pt] \partial_{y}g(w)\end{pmatrix}, so that equilibria satisfy F(w^{*})=0 . This generalizes single-objective optimization to a vector field, but here F is typically non-conservative and non-monotone, so standard convex tools do not apply in general. Understanding the underlying geometry is therefore crucial. The Jacobian of F , i.e., the game Hessian, H(w)=\begin{pmatrix}\partial^{2}_{xx}f(w)&\partial^{2}_{xy}f(w)\\ \partial^{2}_{yx}g(w)&\partial^{2}_{yy}g(w)\end{pmatrix}, admits the decomposition H=S+A with symmetric S=\tfrac{1}{2}(H+H^{\top}) and antisymmetric A=\tfrac{1}{2}(H-H^{\top}) . The part S drives motion toward equilibria, while A induces rotational or Hamiltonian-like components that prevent convergence. Prior work Balduzzi et al. 2018 ; Gemp and Mahadevan 2018 shows that unmitigated rotations cause simultaneous gradient descent to behave as a non-dissipative dynamical system; even in the bilinear game \Phi(x,y)=x^{\top}y , x_{n+1}=x_{n}-\eta\,\partial_{x}f(x_{n},y_{n}),\quad y_{n+1}=y_{n}-\eta\,\partial_{y}g(x_{n},y_{n}) generates limit cycles (see also Schäfer and Anandkumar 2019 ). These rotations arise from antisymmetric interactions between players’ gradients and behave like a skew-symmetric force field. In continuous time, dynamics resemble Hamiltonian systems: energy is conserved, producing a potential (gradient) component toward equilibria and a rotational flow around them. Hence, restoring convergence requires damping or correcting the antisymmetric part. This insight motivated algorithms with second-order corrections, symplectic damping, or predictive steps. The Symplectic Gradient Adjustment (SGA) Balduzzi et al. 2018 preconditions updates with (I-\tau A(w)) , counteracting rotation and stabilizing trajectories near equilibria. The Optimistic Gradient method Daskalakis and Panageas 2018 and the Extragradient technique Korpelevich 1976 ; Gidel et al. 2019 exploit the variational structure of the problem to capture and correct the cycling behaviour. Finally, Competitive Gradient Descent (CGD) Schäfer and Anandkumar 2019 interprets game optimization through a local bilinear model whose Nash equilibrium defines a stable update. However, many of these methods are costly: explicit or implicit mixed second-order derivatives scale poorly. Even for moderate networks, forming \partial^{2}_{xy}f and \partial^{2}_{yx}g is impractical. Quasi-Newton approximations mitigate this: BFGS/L-BFGS Nocedal 1980 ; Liu and Nocedal 1989 maintain low-rank curvature via secant updates, achieving near-second-order behavior at first-order cost. Building on this, Low-Rank SGA (LRSGA) Vater et al. 2025 replaces mixed derivatives with low-rank secant updates, recovering much of SGA’s stabilization without full Hessian storage. Yet the low-rank factors still require memory that grows with problem dimension, which can become prohibitive for large models. We address this scalability bottleneck with Limited-Memory Low-Rank Symplectic Gradient Adjustment (LM-LRSGA). The method combines symplectic gradient corrections with L-BFGS-style recursions: instead of storing dense factors, it keeps a short history of curvature pairs capturing essential information from recent iterates. Modified two-loop recursion algorithms compute the LRSGA products implicitly, avoiding matrix formation or storage. Thus LM-LRSGA preserves LRSGA’s stabilizing effect while using linear memory and first-order-like per-step complexity, making it suitable for large-scale adversarial/stochastic settings (e.g., GANs with millions of parameters). We validate the approach on GAN training over MNIST and Fashion-MNIST, comparing LM-LRSGA against the Adam Kingma and Ba 2014 optimizer. Empirically, LM-LRSGA yields more stable training dynamics and faster convergence, with smooth and synchronized loss trajectories for both generator and discriminator. Quantitatively, it improves Fréchet Inception Distance (FID) by up to 30\% over Adam while maintaining comparable computational cost. Sensitivity analyses show robustness to learning rate, history length, and damping factors, highlighting suitability for large-scale and stochastic regimes. Beyond computation, the method supports sustainable ML: by avoiding explicit second-order computation and reducing memory footprint, LM-LRSGA lowers training time, suggesting efficiency and environmental friendliness. The rest of the paper is organized as follows. Section 2 reviews competitive optimization and recalls SGA and LRSGA. Section 3 presents LM-LRSGA, detailing its two-loop recursion algorithms and update rules. Section 4 reports experiments on GANs trained on MNIST and Fashion-MNIST, and presents sensitivity analyses. Section 6 concludes and outlines potential future extensions to large-scale stochastic and distributed settings. 2 Preliminaries and Mathematical Framework Let X\subset\mathbb{R}^{m} and Y\subset\mathbb{R}^{n} be nonempty, convex and compact subsets, and \Omega\subset\mathbb{R}^{m+n} open and convex such that X\times Y\subset\Omega . Let f,g\in C^{3}(\Omega,\mathbb{R}) be two objective functions. A two-player competitive optimization problem, where Player 1 (with strategy x ) and Player 2 (with strategy y ) aim to minimize their respective objective functions f and g , can be written as: \min_{x\in X}f(x,y)\qquad\min_{y\in Y}g(x,y). (2) Solutions to problem 2 are called Nash equilibria (NE) and denoted by (x^{*},y^{*}) . For a shorter notation, we write w=(x,y)\in X\times Y . The first-order stationarity and the second-order necessary conditions for a local NE are: F(w^{*})=0,\qquad\partial_{xx}^{2}f(w^{*})\succeq 0,\qquad\partial_{yy}^{2}g(w^{*})\succeq 0. (3) Moreover, to ensure that the NE is isolated and locally stable, we assume H(w*) to be invertible and semi-definite positive i.e. \langle z,\,H(w^{\text{NE}})\,z\rangle\geq 0\quad\text{for all }z\in\mathbb{R}^{m+n} . We remark that the game Hessian matrix admits the symmetric/antisymmetric decomposition S(x,y)=\frac{H(x,y)+H(x,y)^{\top}}{2},\quad A(x,y)=\frac{H(x,y)-H(x,y)^{\top}}{2}. As reported in the literature Balduzzi et al. 2018 , the antisymmetric component A(x,y) is directly responsible for rotational/oscillatory dynamics during training, which can delay or even prevent rapid convergence to equilibria. To counteract such phenomena, the Symplectic Gradient Adjustment (SGA) method introduced in Balduzzi et al. 2018 modifies the descent direction by subtracting the rotational component induced by A . Its update rule is w_{k+1}=w_{k}-\eta\,(I-\tau\,A(w_{k}))\,F(w_{k}), where I represents the identity matrix in the appropriate Euclidean space, w_{k}:=(x_{k},y_{k}) the iterate k , \eta>0 the stepsize and \tau>0 controls the strength of the antisymmetric correction.The antisymmetric component of the game Hessian at iterate w_{k} A(w_{k}) has the block form: A(w_{k})=\begin{pmatrix}0_{m}&\frac{1}{2}\,(\partial_{xy}^{2}f(w_{k})-\partial_{yx}^{2}g(w_{k})^{\top})\\ \frac{1}{2}\,(\partial_{yx}^{2}g(w_{k})-\partial_{xy}^{2}f(w_{k})^{\top})&0_{n}\end{pmatrix} (4) As outlined in the introduction, our recent variant— Low-Rank Symplectic Gradient Adjustment (LRSGA) —proposed in Vater et al. 2025 , addresses the high computational cost of explicitly forming the mixed second derivatives \partial^{2}_{xy}f(x,y) and \partial^{2}_{yx}g(x,y) by employing Broyden’s least–change (rank–one) secant updates Broyden 1965 to obtain efficient approximations of these mixed blocks. In particular, we maintain Broyden-type Jacobian estimates with \mu_{k}\approx\bigl(\partial_{xx}^{2}f\,\big|\,\partial_{xy}^{2}f\bigr)\in\mathbb{R}^{m\times(m+n)} and \nu_{k}\approx\bigl(\partial_{yx}^{2}g\,\big|\,\partial_{yy}^{2}g\bigr)\in\mathbb{R}^{n\times(m+n)} . Henceforth we retain only the mixed–derivative block–columns, denoted [\mu_{k}]_{2} and [\nu_{k}]_{1} , which approximate

Read the complete text