PaperlayerView exact revision on arXiv

Source-linked AI summary

Local Saddle Point Optimization: A Curvature Exploitation Approach

Leonard Adolphs, Hadi Daneshmand, Aurelien Lucchi, Thomas Hofmann

arXiv:1805.05751v3cs.LGmath.OCstat.ML

TL;DR

Gradient dynamics can stabilize at saddle-problem stationary points that are not locally optimal, raising a difficulty for finding the intended min-max solutions. The paper adds extreme-curvature steps to gradient-based methods and proves that, under its analysis, this removes undesired stationary points; empirical examples also show curvature exploitation’s advantage. The analysis does not guarantee convergence for general non-convex-concave problems, and GAN experiments exhibit Hessian degeneracy that violates its conditions.

  • Problem

    Gradient dynamics can have stable stationary points that are not locally optimal saddles, complicating the search for solutions with the desired min-max structure.

    Source: §1 · p. 1, §4 · p. 4

  • Method

    The paper uses extreme curvature information to guide gradient trajectories toward saddles with the desired min-max structure.

    Source: §1 · p. 2, §5 · p. 5

  • Results

    With Cesp, stable stationary points coincide with locally optimal saddles, and the toy example converges to the locally optimal saddle where gradient iterates often reach an undesired point.

    Source: §5 · p. 5, §7.1 · p. 7

  • Takeaways & Limitations

    Curvature exploitation can avoid undesired stationary points, but the paper does not guarantee convergence on general non-convex-concave problems.

    Source: §1 · p. 2, §5 · p. 5

    In GAN experiments, convergent solutions have zero eigenvalues in the x-Hessian, violating the analysis conditions; addressing this degeneracy is left for future work.

    Source: §7.3 · p. 8

Abstract

from arXiv · show

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.

1 INTRODUCTION

The paper studies locally optimal saddle points for smooth objectives that need not be convex in x or concave in y. It argues that gradient dynamics can stabilize at undesired stationary points and proposes using extreme curvature to steer optimization toward the desired min-max structure.

1 INTRODUCTION

  • For non-convex-concave objectives, the goal is a locally optimal saddle point that satisfies the min-max condition in a neighborhood.The paper notes that finding a global saddle point is computationally infeasible for this general class.Source: §1 · p. 1
  • Stable gradient dynamics can converge to stationary points that are not locally optimal, unlike in minimization, and small gradient perturbations do not guarantee escape.The undesired points fail the structural min-max property.Source: §1 · pp. 1–2
  • The desired local saddle structure is a minimum in x and a maximum in y, which curvature information can help certify.The paper associates violations with negative curvature directions in x or positive curvature directions in y.Source: §1 · p. 2
  • Extreme curvature exploitation uses eigenvectors for the maximum and minimum eigenvalues to guide gradient trajectories away from undesired saddles.The authors prove it avoids convergence to undesired saddles, but do not guarantee convergence on general non-convex-concave problems; empirical results support its advantage.Source: §1 · p. 2

2 RELATED WORK

Prior saddle-point convergence results largely rely on convex-concave structure or related conditions, while several applications do not satisfy those assumptions. The paper distinguishes its approach from methods that escape saddle points indiscriminately by targeting the min-max structure through curvature.

2 RELATED WORK

  • Classical convergence analyses establish results under strict convex-concavity or related conditions, with extensions to relaxed assumptions and methods.The cited work covers primal-dual dynamics, subgradient methods, and further relaxations.Source: §2 · p. 2
  • For non-strictly convex-concave problems, gradient dynamics may oscillate; averaging or extragradient methods are cited as remedies [13].Convergence rates are also reported for convex-concave settings and related methods.Source: §2 · p. 2
  • GAN convergence results rely on suitable conditions, and convergence properties remain poorly understood; cited local results assume strong convex-concavity or suitable player capacity [27] [34] [24].One cited result gives exponential convergence near a stable local Nash equilibrium under local strong convexity-concavity [24].Source: §2 · p. 2
  • Unlike methods that seek to escape any saddle point, the paper targets stationary points satisfying the min-max condition through curvature information.Prior negative-curvature approaches include trust-region methods and Hessian-vector-product methods such as Lanczos and Oja’s algorithm [8, 33, 6, 35, 9, 1].Source: §2 · p. 3

3 PRELIMINARIES

The analysis defines local optimality through the min-max structure and imposes smoothness and non-degeneracy assumptions. Under those assumptions, stationarity together with the appropriate Hessian signs characterizes a locally optimal saddle.

3 PRELIMINARIES

  • Local optimality is considered within a neighborhood, with the desired point defined by the paper’s local saddle condition.The definition is framed for a local neighborhood around the candidate point.Source: §3 · p. 3
  • The analysis assumes sufficient smoothness and non-degenerate second derivatives at locally optimal points.The stated smoothness assumption makes the objective C2 with Lipschitz gradient and Hessian.Source: §3 · p. 3
  • Under Assumption 3, a point is locally optimal if and only if its gradient is zero and its second derivatives are positive definite in x and negative definite in y.The Hessian conditions require positive constants μ_x and μ_y.Source: §3 · p. 3

4 UNDESIRED STABILITY

The section shows that gradient dynamics may stabilize at stationary points that are not locally optimal saddle points. It examines convergent sequences and illustrates the issue with a two-dimensional example where even small gradient perturbations fail to ensure escape.

4 UNDESIRED STABILITY

  • Gradient optimization can diverge, enter a loop, or converge to a stationary point; this section studies the convergent case without claiming general convergence guarantees.The paper says typical guarantees require convexity-concavity or relaxed conditions such as quasiconvexity-quasiconcavity [7].Source: §4 · pp. 3–4
  • If a gradient sequence converges from random initialization under the stated assumptions, its stationary point is almost surely stable.The result concerns the type of stationary point reached, not whether the sequence converges.Source: §4 · p. 4
  • Stable stationary points need not be locally optimal saddles, unlike the correspondence between stable points and local minima in minimization.Prior work establishes that locally optimal saddles are stable, but saddle problems can have additional stable points [26] [27].Source: §4 · p. 4
  • In the example, gradient steps converge to an undesired stable point whose y-coordinate is a local minimum, and small perturbations do not prevent that convergence.Only z1 is a locally optimal saddle point in the example.Source: §4 · p. 4

5 EXTREME CURVATURE EXPLOITATION

The method adds an extreme-curvature direction to gradient updates to escape undesired stable stationary points in saddle-point optimization. Its guarantees identify the Cesp dynamics’ stationary points with locally optimal saddle points, while its convergence guarantee is limited to convergent sequences.

  • Cesp adds an extreme-curvature direction to gradient steps, using eigenvectors for the minimum x-eigenvalue and maximum y-eigenvalue rather than the full eigenspace.The method is called extreme curvature exploitation; in regions with positive x-eigenvalues and negative y-eigenvalues, its curvature vector is zero and the update reduces to gradient optimization.Source: §5 · pp. 4–5
  • Cesp’s stationary points are exactly the locally optimal saddle points, and every convergent Cesp sequence therefore yields a solution to the local saddle-point problem.The paper states that exploiting extreme curvature makes points outside the locally optimal set non-stationary.Source: §5 · p. 5
  • From a γ-neighbourhood of an undesired stationary point of the gradient dynamics, the Cesp iterates escape that neighbourhood after one step.The stated result concerns initial iterates in a γ-neighbourhood of an undesired stationary point.Source: §5 · p. 6
  • Cesp uses only extreme curvature, distinguishing it conceptually from Newton-type second-order optimization, for which the paper reports no evidence of success on general smooth saddle-point problems.The paper also notes that Cesp’s curvature direction can be extracted through Hessian-vector products, as efficiently as gradient evaluations.Source: §5 · p. 6

6 CURVATURE EXPLOITATION FOR LINEAR-TRANSFORMED GRADIENT STEPS

The paper extends curvature exploitation to gradient updates transformed by a linear map, including Adagrad. With a positive-definite transformation, the modified method retains the same stable-point characterization as the original Cesp method.

6 CURVATURE EXPLOITATION FOR LINEAR-TRANSFORMED GRADIENT STEPS

  • Adagrad is a popular optimization method in the linear-transformed gradient family, and the paper proposes adapting Cesp to this family of updates.The transformed update uses a symmetric, block-diagonal linear transformation; the appendix table lists choices for different optimizers.Source: §6 · p. 6, Extreme Curvature Exploitation · p. 6

Extreme Curvature Exploitation

  • With a positive-definite transformation matrix, linear-transformed Cesp has stable points exactly at the locally optimal saddle points, a property that also applies to Adagrad.The paper states that curvature exploitation for Adagrad is experimentally evaluated later.Source: Extreme Curvature Exploitation · pp. 6–7

7 EXPERIMENTS

The experiments compare CESP with gradient-based methods on a toy saddle problem, neural-network robust optimization, and GAN training. They report improved convergence toward locally optimal saddle-point curvature conditions, while noting a Hessian-degeneracy limitation in the GAN setting.

7.1 Escaping From Undesired Stationary Points of the Toy Example

  • On the toy problem, gradient descent converges to an undesired stationary point from many initializations, whereas CESP converges to a locally optimal saddle point.Figure 3 compares their trajectories from (−3, −1).Source: §7.1 · p. 7, Figure 3 · p. 8

7.2 Robust Optimization

  • In neural-network robust optimization, CESP more reliably drives convergent runs to a positive minimum x-Hessian eigenvalue than gradient descent.Figure 4 compares the minimum eigenvalue with squared gradient norm; the experiment uses a Wisconsin breast cancer classifier.Source: §7.2 · p. 7, Figure 4 · p. 8

7.3 Generative Adversarial Networks

  • The GAN experiment uses MNIST and a one-hidden-layer, 100-unit architecture, with Adagrad, power-iteration curvature estimates, and mini-batch approximations.The gradient and extreme-curvature vectors are approximated in this mini-batch setting.Source: §7.3 · p. 7
  • On the MNIST GAN, both Adagrad variants converge and satisfy the y-curvature condition, while CESP converges faster on the x-curvature measure.Figure 5 tracks the minimum x-Hessian eigenvalue, maximum y-Hessian eigenvalue, and squared gradient norm.Source: §7.3 · p. 7, Figure 5 · p. 8
  • Zero x-Hessian eigenvalues at convergent GAN solutions violate the conditions required for the analysis.The paper notes this matches evidence that Hessians are degenerate in common deep-learning architectures and leaves the phenomenon for future work.Source: §7.3 · p. 8

8 CONCLUSION

The paper identifies stable gradient-method stationary points that are not locally optimal saddle points and proposes using extreme curvature to avoid them. It presents curvature exploitation as beneficial for saddle-point optimization, while stronger global convergence guarantees remain a possible direction for future algorithms.

8 CONCLUSION

  • Gradient methods can have stable stationary points that are not locally optimal, a difficulty specific to saddle-point optimization.Source: §8 · p. 8
  • The proposed approach exploits extreme curvature information to avoid convergence to undesired stationary points.Source: §8 · p. 8
  • The authors suggest curvature information may motivate algorithms with stronger global convergence guarantees.Source: §8 · p. 8

A Theoretical Analysis

The proof treats local saddle optimality through the separate minimization and maximization conditions in x and y. For the x-minimum, it uses first- and second-order necessary conditions, with the y-maximum argument following symmetrically.

A.1 Lemma 4

  • The lemma treats a locally optimal saddle point as a local minimum in x and a local maximum in y.Source: §A.1 · p. 11
  • The corresponding proof for the local maximum in y follows directly from the x-minimum argument.Source: §A.1 · p. 11
  • A local minimum in x requires ∇x f(x*, y)=0, since a nonzero gradient admits a feasible descent direction.Source: §A.1 · p. 11
  • At a local minimum in x, negative Hessian curvature would yield a descent direction and contradict local minimality.Source: §A.1 · p. 12

A.2 Lemma 6

The appendix establishes key properties of CESP: iterates escape neighborhoods of undesired stationary points, while the method preserves descent in x and ascent in y. It also characterizes stationary and stable points under the stated assumptions.

A.2 Lemma 6

  • Under Assumption 2 and a sufficiently small step size, gradient iterates from random initialization that converge to a stationary point converge almost surely to a stable point.The gradient mapping is shown to be a diffeomorphism, a premise used in the random-initialization result.Source: §A.2 · pp. 12–13

A.3 Lemma 7

  • A point is stationary under Eq. (22) if and only if it is a locally optimal saddle point.The proof derives zero gradients and the required curvature signs.Source: §A.3 · p. 13

A.4 Lemma 8

  • Within K*γ, the neighborhood of a locally optimal saddle point, iterates of Eq. (22) are stable; f has no extreme curvatures (vz = 0), and Eq. (22) reduces to the gradient update in Eq. (3).Source: §A.4 · p. 14

A.5 Lemma 9

  • From a γ-neighborhood of an undesired stationary point, CESP iterates escape that neighborhood after one step.The escape result applies to iterates of Eq. (22).Source: §A.5 · p. 14

A.6 Guaranteed decrease/increase

  • Within regions of extreme curvature, CESP guarantees a larger decrease in x and increase in y than gradient descent/ascent, without claiming faster global convergence.The update’s decrease and increase guarantees require the stated step-size condition.Source: §A.6 · pp. 16–17

A.7 Lemma 10

Lemma 10 identifies the stable points of the linear-transformed CESP update with locally optimal saddle points. The appendix also presents update matrices for commonly used optimization methods.

A.7 Lemma 10

  • The stable points of the linear-transformed CESP update are exactly the locally optimal saddle points.The proof establishes stability of locally optimal saddles for a sufficiently small step size.Source: §A.7 · pp. 17–18

B Transformed Gradient Updates

C Experiments

The experiments include a toy saddle-point basin comparison and a single-layer MNIST GAN trained with separate losses. In the GAN experiment, CESP reduces negative curvature where the gradient method does not exploit it appropriately.

C.1 Toy Example

  • Figure 6 compares GD and CESP attraction basins to the locally optimal saddle and the undesired critical point in the toy saddle-point problem.The caption marks the locally optimal saddle’s basin green and the undesired critical point’s basin red.Source: §C.1 · p. 18, Figure 6 · p. 19

C.2.1 Single-layer GAN

  • The single-layer GAN experiment uses MNIST and separates training into two individual loss functions.CESP is defined for the two parameter sets individually and can be applied to this split-objective setting.Source: §C.2.1 · pp. 18–19
  • In the single-layer GAN with individual losses, CESP decreases negative curvature in the x-objective, while the gradient method’s smallest eigenvalue oscillates in the negative region.Figure 7 also plots the maximum eigenvalue of the y-objective Hessian and the gradient norm.Source: §C.2.1 · p. 19, Figure 7 · p. 20
Loading 1805.05751v3…