Stable Nonconvex-Nonconcave Training via Linear Interpolation

Thomas Pethick, Wanyun Xie, Volkan Cevher

Abstract

Training complex models like Generative Adversarial Networks (GANs) often involves solving nonconvex-nonconcave minimax problems. These problems are notoriously unstable, frequently leading to oscillatory or divergent dynamics. While the "Lookahead" optimizer has emerged as a popular heuristic to stabilize training through linear interpolation, its theoretical foundations have remained elusive. This paper bridges this gap by framing linear interpolation as a Krasnosel’skiĭ-Mann (KM) iteration within the context of operator theory. We introduce the Relaxed Approximate Proximal Point (RAPP) algorithm, providing the first global last-iterate convergence guarantees for Lookahead-style methods in non-monotone settings. Our results provide a principled justification for common practices, such as the use of an interpolation constant of 0.5, and demonstrate significant empirical improvements in GAN training stability and performance.

1. Introduction

The optimization of modern deep learning architectures, particularly those involving adversarial components like GANs, often requires navigating "minimax" landscapes. Unlike standard minimization, these landscapes are frequently nonconvex-nonconcave, where gradients from competing networks can lead to unstable dynamics. In practice, practitioners often observe the training process cycling indefinitely around a solution or diverging entirely.

To combat this, the Lookahead algorithm—which periodically interpolates between "fast" and "slow" weights—has become a staple for stabilizing training. However, despite its success, Lookahead has largely been treated as a heuristic. This research provides a rigorous theoretical foundation for why linear interpolation stabilizes training, introducing a new algorithm, RAPP, that ensures convergence even in difficult, non-monotone environments.

2. Theoretical Framework: Optimization as Operator Theory

The authors re-envision the optimization process through the lens of operator theory. By treating the update rule as an operator, the goal of training becomes finding a fixed point.

2.1 Krasnosel’skiĭ-Mann (KM) Iteration

A key contribution of this work is identifying that the linear interpolation step in Lookahead is essentially a Krasnosel’skiĭ-Mann (KM) iteration. KM iteration is a classical mathematical technique used to find fixed points by averaging the current state with a proposed update. This connection allows the authors to apply decades of mathematical theory to modern deep learning optimizers.

2.2 Cohypomonotonicity

To model the "messy" landscapes of neural networks, the paper employs the structural assumption of cohypomonotonicity. In standard monotone problems, gradients always point generally toward the solution. In cohypomonotone settings, gradients are allowed to point away from the solution occasionally, provided they maintain a certain global structure. This assumption is far more representative of the actual landscapes encountered in GAN training.

3. The RAPP Algorithm

Building on the KM framework, the authors propose the Relaxed Approximate Proximal Point (RAPP) algorithm. RAPP is a double-loop algorithm designed for robustness:

  • Inner Loop: Approximates a "resolvent," which is a mathematically stable step that behaves better than a raw gradient update.
  • Outer Loop: Performs the linear interpolation (KM iteration) to ensure global stability.

RAPP serves as a "principled version" of Lookahead. While Lookahead is more computationally efficient, RAPP provides the theoretical backbone that guarantees convergence to a stationary point without requiring restrictive conditions like "anchoring."

4. Key Insights

4.1 Stability via Averaging

The research demonstrates that linear interpolation is not merely a smoothing trick. Instead, it is a principled mechanism that transforms an unstable, expansive operator into a "quasi-nonexpansive" one. This transformation mathematically forces the iterates to remain near the solution, preventing the divergent spirals common in GAN training.

4.2 Last-Iterate Convergence

Most existing optimization theories only guarantee that the average of all iterations will eventually reach a solution. In practice, however, we use the final set of weights. This paper proves last-iterate convergence, ensuring that the final model weights themselves are high-quality and stable.

4.3 The Optimality of λ = 0.5

In the Lookahead algorithm, users typically choose an interpolation constant (λ) of 0.5. This paper provides the first theoretical justification for this choice, showing that λ = 0.5 is the optimal upper bound for the convergence rate in these problem classes.

5. Experimental Results

The theoretical findings were validated through both synthetic "toy" problems and large-scale image generation tasks.

5.1 Synthetic Benchmarks

The authors tested RAPP and Lookahead variants on problems like PolarGame, Quadratic functions, and the Forsaken example. These benchmarks are designed with vector fields that cause standard optimizers to spiral or diverge. In all cases, the interpolation-based methods successfully converged to the equilibrium where standard methods failed.

5.2 GAN Training on CIFAR10

To demonstrate real-world utility, the authors trained ResNet-based GANs on the CIFAR10 dataset. The results showed a clear advantage for interpolation-based methods:

  • Stability: While standard Adam optimizers eventually diverged, Lookahead-Adam (LA-Adam) remained stable throughout training.
  • Performance: LA-GDA achieved a Fréchet Inception Distance (FID) of 16.87, compared to 19.36 for standard GDA. Similarly, LA-ExtraAdam reached an FID of 15.88, significantly outperforming the standard ExtraAdam's score of 21.04.

6. Conclusion and Future Work

This work provides a long-overdue theoretical justification for linear interpolation in nonconvex-nonconcave optimization. By identifying Lookahead as a KM iteration, the authors have opened a new path for analyzing and improving deep learning optimizers. While RAPP introduces some computational overhead due to its double-loop structure, its stability guarantees are invaluable for complex minimax problems. Future research may extend this framework to other "inner-outer" loop algorithms, such as Federated Averaging and Reptile (meta-learning), potentially providing similar stability breakthroughs in those fields.

Summary updated

Abstract

This paper presents a theoretical analysis of linear interpolation as a principled method for stabilizing (large-scale) neural network training. We argue that instabilities in the optimization process are often caused by the nonmonotonicity of the loss landscape and show how linear interpolation can help by leveraging the theory of nonexpansive operators. We construct a new optimization scheme called relaxed approximate proximal point (RAPP), which is the first 1-SCLI method to achieve last iterate convergence rates for $\rho$-comonotone problems while only requiring $\rho > -\tfrac{1}{2L}$. The construction extends to constrained and regularized settings. By replacing the inner optimizer in RAPP we rediscover the family of Lookahead algorithms for which we establish convergence in cohypomonotone problems even when the base optimizer is taken to be gradient descent ascent. The range of cohypomonotone problems in which Lookahead converges is further expanded by exploiting that Lookahead inherits the properties of the base optimizer. We corroborate the results with experiments on generative adversarial networks which demonstrates the benefits of the linear interpolation present in both RAPP and Lookahead.
BibTeX
@inproceedings{pethick2023stable,
  author = {Thomas Pethick and Wanyun Xie and Volkan Cevher},
  title = {{Stable Nonconvex-Nonconcave Training via Linear Interpolation}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2023},
  url = {https://openreview.net/forum?id=b1JPBGJhUi},
}
Figure