Local Saddle Point Optimization: A Curvature Exploitation Approach

By Leonard Adolphs, Hadi Daneshmand, Aurélien Lucchi, Thomas Hofmann. 2018

115 citations recorded by the source corpus.

Gradient-based optimization methods are the most popular choice for finding local optima for classical minimization and saddle point problems. Here, we highlight a systemic issue of gradient dynamics that arise for saddle point problems, namely the presence of undesired stable stationary points that are no local optima. We propose a novel optimization approach that exploits curvature information in order to escape from these undesired stationary points. We prove that different optimization methods, including gradient method and Adagrad, equipped with curvature exploitation can escape non-optimal stationary points. We also provide empirical results on common saddle point problems which confirm the advantage of using curvature exploitation.

Subfields: Computational Mechanics, Numerical Analysis, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Numerical Analysis

In Optimization & Training

Citations in the corpus

A Tight and Unified Analysis of Extragradient for a Whole Spectrum of Differentiable Games (2019, background): “However, as shown by Adolphs et al. (2019); Mazumdar et al. (2019), stationary points are not necessarily Nash equilibria in general but if v is monotone, these two notions are equivalent.”
A Closer Look at the Optimization Landscapes of Generative Adversarial Networks (2019, methodology): “(3) With this perspective, the notion of DNE is replaced by the notion of locally stable stationary point (LSSP).”
Negative Momentum for Improved Game Dynamics (2018, background): “For instance, some stable stationary points of the dynamics may not be (local) Nash equilibria (Adolphs et al., 2018; Daskalakis and Panageas, 2018).”
On Solving Minimax Optimization Locally: A Follow-the-Ridge Approach (2019, background): “Besides, Adolphs et al. (2019); Mazumdar et al. (2019) attempt to solve the undesirable convergence issue of GDA by exploiting curvature information, but they focus on simultaneous game on ﬁnding local Nash and it is unclear how to extend their algorithm to sequential games.”
A Tight and Unified Analysis of Gradient-Based Methods for a Whole Spectrum of Differentiable Games (2020, methodology): “However, as shown by Adolphs et al. (2019); Mazumdar et al. (2019); Berard et al.”
Minmax Optimization: Stable Limit Points of Gradient Descent Ascent are Locally Optimal (2019, background): “Speciﬁcally, Daskalakis and Panageas [2018], Mazumdar and Ratliff [2018], and Adolphs et al. [2018] show that some of the stable limit points of GDA may not be Nash equilibria.”
What is Local Optimality in Nonconvex-Nonconcave Minimax Optimization? (2019, methodology): “Most previous work (e.g., Daskalakis and Panageas, 2018; Mazumdar and Ratliff, 2018; Adolphs et al., 2018) studied a notion of local Nash equilibrium which replaces all the global minima or maxima in the definition of Nash equilibrium by their local counterparts.”
Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms (2019, methodology): “Consensus optimization [307], symplectic gradient adjustment [312], and extragradient method [310] have been advocated to mitigate the oscillatory behaviors around the equilibria; while [308, 305]”
Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization (2020, background): “This work has focused on attaining improved rates [3, 4,19,21,26,29–31,41,45,48] and/or obtaining last-iterate convergence guarantees [1,2,13–15,20,22,28,35,37,38,43].”
On the convergence of single-call stochastic extra-gradient methods (2019, background): “2 At the local level, the geometric convergence results discussed above echo a surge of interest in local convergence guarantees of optimization algorithms applied to games and saddle-point problems, see e.g., [1, 3, 15, 24] and references therein.”
On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems (2019, background): “Most recent work aims at defining a notion of goodness or the development of new procedures for reducing oscillations (Daskalakis & Panageas, 2018b; Adolphs et al., 2018; Mazumdar et al., 2019) and speeding up the convergence of gradient dynamics (Heusel et al.”
Ellipsoidal Trust Region Methods and the Marginal Value of Hessian Information for Neural Network Training (2019, background): “Finally, there is a growing body of first-order algorithms that explicitly include additional negative curvature steps to derive state-of-the-art time complexities in classical minimization problems [4, 66, 14, 40] as well as in min-max problems to avoid convergence to unstructured saddle points [1]”