Source-linked AI summary
Saddle-point dynamics: conditions for asymptotic stability of saddle points
Ashish Cherukuri, Bahman Gharesifard, Jorge Cortes
TL;DR
The paper asks when saddle-point dynamics converge asymptotically to min-max saddle points, including continua of such points. It develops complementary conditions based on convexity-concavity and, more generally, linearization, proximal-normal behavior, and linearity in one variable. The results establish local and global asymptotic stability, with convergence to a point under several conditions.
Problem
The paper addresses the lack of general asymptotic convergence guarantees for saddle-point dynamics toward min-max saddle points, which may form a continuum.
Method
The paper catalogs complementary stability conditions using convexity-concavity, linearization, proximal normals, and linearity in one variable.
Results
The results establish local and global asymptotic stability of saddle-point sets, with convergence to a point under several convexity-concavity and quasiconvexity-quasiconcavity conditions.
Takeaways & Limitations
Saddle-point dynamics can converge to saddle sets, including continua, under complementary structural conditions on the saddle function.
Takeaways & Limitations
The paper’s conditions do not cover every saddle function: examples may be globally convex-concave yet fail strictness or required linearity assumptions.
Abstract
from arXiv · showhide
This paper considers continuously differentiable functions of two vector variables that have (possibly a continuum of) min-max saddle points. We study the asymptotic convergence properties of the associated saddle-point dynamics (gradient-descent in the first variable and gradient-ascent in the second one). We identify a suite of complementary conditions under which the set of saddle points is asymptotically stable under the saddle-point dynamics. Our first set of results is based on the convexity-concavity of the function defining the saddle-point dynamics to establish the convergence guarantees. For functions that do not enjoy this feature, our second set of results relies on properties of the linearization of the dynamics, the function along the proximal normals to the saddle set, and the linearity of the function in one variable. We also provide global versions of the asymptotic convergence results. Various examples illustrate our discussion.
1. Introduction.
The paper studies when saddle-point dynamics converge asymptotically to min-max saddle points, including continua of saddle points, motivated by constrained optimization and zero-sum games.
- Saddle-point dynamics combine gradient descent in one variable with gradient ascent in the other.
- Unlike ordinary gradient dynamics, saddle-point dynamics need not converge asymptotically to critical points for continuously differentiable functions.
- The paper seeks conditions ensuring convergence when critical points are min-max saddle points that may form a continuum.
- The motivating applications are equality-constrained optimization and Nash-equilibrium computation in zero-sum games.
Literature review.
Prior work applies primal-dual or saddle-point dynamics across optimization, networks, and games, while this paper broadens the convergence setting beyond isolated convex-concave cases.
- Primal-dual dynamics have been used to reach Lagrangian saddle points in constrained optimization.
- Related applications include distributed optimization, linear programming, power networks, bargaining, and two-person zero-sum games.
- Most prior work assumes convex-concavity, whereas this paper studies a wider class of functions and allows continua of saddle points.
- The paper excludes nonnegativity-preserving projection on individual variables and emphasizes convergence to a point wherever feasible.
Statement of contributions.
The paper catalogs complementary conditions guaranteeing local or global convergence of saddle-point dynamics, covering convex-concave and several non-convex-concave settings.
- The dynamics are gradient descent in the first variable and gradient ascent in the second, with convergence studied toward the saddle-point set and possibly a point.
- Convex-concave functions: For convex-concave functions, strict convexity or concavity yields asymptotic stability, including pointwise convergence under stated component conditions.
- General saddle functions: For functions lacking convex-concavity, the analysis uses linearization, proximal normals, and linearity in one variable.
- General saddle functions: The paper derives polynomial-growth relationships for variations along proximal-normal directions to ensure asymptotic convergence.
- Global convergence conditions are developed wherever feasible across the considered scenarios.
Organization.
The paper progresses from preliminaries and problem formulation to convex-concave stability, general-function convergence analysis, and concluding remarks.
- Section 2 introduces notation and basic preliminaries.
- Section 3 presents the saddle-point dynamics and problem statement.
- Section 4 studies saddle functions with convexity-concavity properties.
- Section 5 analyzes non-convex-concave cases using linearization, proximal normals, and function linearity.
- Section 6 summarizes the conclusions and future-work ideas.
2. Preliminaries.
The preliminaries establish notation for vectors, matrices, derivatives, regularity, proximal geometry, saddle points, and convexity-related function classes.
- Notation: The paper defines standard sets, norms, vector concatenation, matrix definiteness, eigenvalues, ranges, null spaces, differentiability classes, and sublevel sets.
- Notation: A piecewise C2 vector field is continuous and agrees with finitely many C2 functions on patches whose closures cover the domain.
- Proximal calculus: For a closed set E, projE(x) contains nearest points, while nonnegative multiples of x−y define proximal normals at y.
- Saddle points: A local min-max saddle point satisfies local minimization in the first variable and maximization in the second; global saddle points use the full domains.
- Convexity and concavity: Local convex-concavity requires convexity in x and concavity in z over a neighborhood, with strictness requiring strict convexity or strict concavity in one variable.
- Quasiconvexity: Strong quasiconvexity and quasiconcavity are defined through a positive parameter, and joint strong quasiconvex-quasiconcavity applies these properties to both variables locally.
3. Problem statement.
The paper studies gradient descent-ascent dynamics for a continuously differentiable saddle function and seeks conditions ensuring local or global convergence to its nonempty saddle-point set.
- Problem formulation: For F: R^n × R^m → R, the saddle-point dynamics performs gradient descent in one argument and gradient ascent in the other.
- Objectives: The analysis seeks conditions for trajectories to converge locally asymptotically to Saddle(F), possibly to a point, and globally whenever feasible.
- Assumption: The saddle-point set is assumed nonempty, an assumption motivated by constrained-optimization Lagrangians and zero-sum game value functions.
4. Convergence analysis for convex-concave saddle functions.
The paper establishes local and global asymptotic stability of saddle-point sets under complementary convexity-concavity, linearity, and strong quasiconvexity-quasiconcavity conditions.
- 4.1. Stability under strict convexity-concavity.: Local strict convexity-concavity makes each isolated path connected component of Saddle(F) locally asymptotically stable, with trajectories converging to points.The proof uses a LaSalle function and the LaSalle Invariance Principle.
- 4.1. Stability under strict convexity-concavity.: Global strict convexity-concavity makes Saddle(F) globally asymptotically stable, and every trajectory converges to a point.
- 4.2. Stability under convexity-linearity or linearity-concavity.: Under local convexity-concavity and linearity in z, each isolated path connected saddle component is locally asymptotically stable with pointwise trajectory convergence.The additional condition requires equality at fixed z∗ to imply membership in Saddle(F) locally in x.
- 4.2. Stability under convexity-linearity or linearity-concavity.: Global convexity-concavity and linearity in z, together with the equality condition, yield global asymptotic stability of Saddle(F) and convergence to a point.
- 4.2. Stability under convexity-linearity or linearity-concavity.: For a convex optimization example, the original Lagrangian fails strict convexity-concavity and the stated convexity-linearity condition, so an augmented Lagrangian is used instead.Its saddle-point dynamics converge to a point in Saddle(L), with the limit depending on the initial condition.
- 4.3. Stability under strong quasiconvexity-quasiconcavity.: Strong quasiconvexity-quasiconcavity is sufficient for local asymptotic stability of isolated path connected saddle components and pointwise convergence.The result assumes F is C2 and ∇xzF is locally Lipschitz; a global version is also developed when the hypotheses hold globally.
5. Convergence analysis for general saddle functions.
For nonconvex-concave saddle functions, the paper gives complementary local and global convergence conditions based on linearization, proximal normals, and linearity in one argument.
- Linearization: Piecewise-smooth linearization yields local asymptotic stability when Jacobian limit matrices share a common kernel and have negative-real-part nonzero eigenvalues.The result applies to a manifold of saddle points under the stated regularity and spectral assumptions.
- Linearization: For C3 saddle functions, a p-dimensional saddle manifold is locally asymptotically stable when zero is semisimple with multiplicity p and all other Jacobian eigenvalues avoid the imaginary axis.The proof uses the saddle-point Hessian structure and the resulting spectral properties.
- Linearity in one argument: If the saddle function is linear in its second argument, range(∇zxF) ∩ null(∇xxF) = {0} excludes nonzero imaginary Jacobian eigenvalues at saddle points.This condition supplies the spectral hypothesis used by the linearization-based stability result.
- Examples: For a nonconvex constrained optimization Lagrangian, the saddle set is nonconvex, yet Jacobian spectral conditions establish asymptotic convergence to a saddle point.The convergence point depends on the initial condition, and simulations illustrate the result.
- Proximal normals: Proximal-normal conditions establish local asymptotic stability of a closed saddle set, with convergence to a point when every point in the set is stable.The result becomes global when the corresponding bounds hold with Lx = Lz = 0.
- Examples: For F(x, z) = xz^2, bounded trajectories and instability of non-saddle equilibria imply convergence to the saddle set from almost all initial conditions.This application uses the global result for saddle functions linear in one argument.
6. Conclusions.
The paper establishes complementary conditions for asymptotic convergence of saddle-point dynamics, including convexity-concavity, linearization, proximal-normal properties, and linearity in one variable.
- The results prove convergence to the saddle-point set under complementary conditions on the saddle function.The conditions include convexity-concavity, linearization properties, behavior along proximal normals, and linearity in one variable.
- Global stability guarantees and convergence to a point are established wherever the assumptions permit.
- For piecewise twice continuously differentiable vector fields, center-manifold ideas yield a general stability result for manifolds of equilibria.
Appendix.
The appendix supplies auxiliary lemmas and proves stability results for saddle-point dynamics and manifolds of equilibria, including convergence to individual equilibrium points.
- Path connected sets of local saddle points have constant saddle-function value under local convexity-concavity.
- Strong quasiconvexity provides a first-order inequality derived from interpolation bounds and Taylor expansion.
- A trajectory approaching a stable equilibrium set within a compact positively invariant set converges to a point in that set.
- The appendix notes that the piecewise-C2 stability result is inspired by, but not directly implied by, center manifold theory.
- For piecewise C2 vector fields, generalized Jacobian conditions with stable transverse eigenvalues and a common positive definite matrix imply local asymptotic stability of an equilibrium manifold.The proof linearizes the vector field on patches and uses a common Lyapunov function with a bound on second-order growth.
- The manifold-stability proof shows exponential decay of transverse coordinates, neighborhood invariance, convergence to the equilibrium manifold, and convergence to a point.
- An example concludes local asymptotic stability from nonzero 2 × 2 blocks whose eigenvalues have negative real parts and share the identity matrix as a common Lyapunov function.