PaperlayerView exact revision on arXiv

Source-linked AI summary

Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization

Constantinos Daskalakis, Ioannis Panageas

arXiv:1807.04252v5math.OCcs.GTstat.ML

TL;DR

The paper addresses whether no-regret learning can achieve last-iterate convergence in constrained min-max optimization, where classic multiplicative weights may cycle. It analyzes Optimistic Multiplicative-Weights Update, proving convergence to the exact solution under uniqueness and suitable stepsizes through progress in KL divergence followed by local stability.

  • Problem

    No-regret methods generally guarantee only average-iterate convergence, while last iterates can diverge or cycle in min-max problems.

  • Method

    The paper analyzes OMWU using KL-divergence progress away from the solution and Jacobian-based local asymptotic stability near it.

  • Results

    OMWU converges pointwise to the unique optimal solution from uniform initialization with an appropriate learning rate.

  • Takeaways & Limitations

    The analysis extends last-iterate convergence from unconstrained optimistic dynamics to constrained zero-sum games and offers techniques for studying other learning algorithms.

  • Takeaways & Limitations

    Polynomial-time convergence and exact rates remain open, and the stated results are currently beyond the bilinear setting an open direction.

Abstract

from arXiv · show

Motivated by applications in Game Theory, Optimization, and Generative Adversarial Networks, recent work of Daskalakis et al \cite{DISZ17} and follow-up work of Liang and Stokes \cite{LiangS18} have established that a variant of the widely used Gradient Descent/Ascent procedure, called "Optimistic Gradient Descent/Ascent (OGDA)", exhibits last-iterate convergence to saddle points in {\em unconstrained} convex-concave min-max optimization problems. We show that the same holds true in the more general problem of {\em constrained} min-max optimization under a variant of the no-regret Multiplicative-Weights-Update method called "Optimistic Multiplicative-Weights Update (OMWU)". This answers an open question of Syrgkanis et al \cite{SALS15}. The proof of our result requires fundamentally different techniques from those that exist in no-regret learning literature and the aforementioned papers. We show that OMWU monotonically improves the Kullback-Leibler divergence of the current iterate to the (appropriately normalized) min-max solution until it enters a neighborhood of the solution. Inside that neighborhood we show that OMWU is locally (asymptotically) stable converging to the exact solution. We believe that our techniques will be useful in the analysis of the last iterate of other learning algorithms.

1 Introduction

The paper studies last-iterate convergence for constrained zero-sum min-max problems, extending prior unconstrained results to optimistic multiplicative-weights dynamics. It introduces OMWU and proves convergence under a uniqueness assumption.

  • Last vs Average Iterate Convergence: No-regret methods typically guarantee convergence of time averages, while last iterates may diverge or enter limit cycles.This gap motivates studying pointwise convergence in constrained min-max optimization.
  • Prior Optimistic Dynamics: GDA can diverge in unconstrained problems, whereas OGDA was shown to exhibit last-iterate convergence.These results motivate analogous optimistic dynamics for constrained problems.
  • Constrained Min-Max Optimization: With simplex constraints, GDA-style methods are replaced by MWU, but MWU can cycle; the paper therefore studies its optimistic variant, OMWU.OMWU corresponds to optimistic FTRL with entropy regularization.
  • Main Result: OMWU converges in the last iterate to the optimal solution when the zero-sum game has a unique solution and the learning rate is appropriately chosen.Starting from uniform distributions, (x_t, y_t) converges to (x*, y*).
  • Main Result: The uniqueness assumption is generic because zero-sum games with non-unique equilibria have Lebesgue measure zero.Independent sampling of A's entries from a continuous distribution yields a unique solution with probability one.
  • Contributions: The paper's proof techniques differ fundamentally from standard no-regret analyses, which usually establish convergence only for time averages.The authors also argue that these techniques may help analyze last iterates of other learning algorithms.

2 Preliminaries

The paper formulates OMWU as a discrete dynamical system on probability simplices and establishes convergence under a unique-solution assumption with sufficiently small, constant stepsize.

  • Dynamical systems: OMWU is represented as a discrete dynamical system whose state maps ((x_t, y_t, x_{t−1}, y_{t−1})) to ((x_{t+1}, y_{t+1}, x_t, y_t)).This representation allows fixed-point and local-stability analysis.
  • Main result: OMWU decreases a divergence measure until iterates become O(η^1/3)-close, then uses local asymptotic stability to establish last-iterate convergence.The stepsize may change between the global decrease phase and the local stability phase.
  • OMWU dynamics: The optimal quadruple (x*, y*, x*, y*) is a fixed point, and the simplex product remains invariant under OMWU dynamics.The updates preserve non-negativity and normalization of both distributions.
  • Approximate solutions: An α-close point satisfies approximate stationarity conditions for coordinates with positive mass, while zero coordinates are exempt from those coordinatewise conditions.Such points can represent approximate solutions induced by submatrices, but 0-closeness alone need not imply global optimality.
  • Approximate solutions: An ε-approximate point limits both players’ unilateral payoff improvements, and 0-approximate points are optimal solutions of the min-max problem.This definition directly captures approximate Nash equilibrium in the simplex-constrained game.
  • Main result: For a matrix with a unique solution, sufficiently small η yields convergence from uniform initialization, with η constant over time.The stated stepsize depends on n, m, and A, while its precise required magnitude is not specified by the theorem.

3 Last iterate convergence of OMWU

The proof combines global KL-divergence decrease with local asymptotic stability to establish last-iterate convergence of OMWU under uniqueness and sufficiently small stepsizes.

  • KL decreases and OMWU reaches neighborhood: OMWU's KL divergence decreases by at least Ω(η^3) per iteration unless the current iterate is O(η^1/3)-close.This supplies the global progress phase of the convergence proof.
  • Last iterate convergence of OMWU: The convergence proof also applies to interior nonuniform initializations, but the stepsize then depends on the initial distributions as well as n, m, and A.The theorem's stated initialization is uniform, while the proof notes this broader interior-start scope.
  • KL decreases and OMWU reaches neighborhood: An O(η^1/3)-close iterate approaches the unique optimum in ℓ1 distance as η tends to zero.The argument also controls probability mass outside the optimal solution's support.
  • Proving local convergence: Near the optimum, the OMWU update is locally asymptotically stable because its Jacobian has spectral radius below one under uniqueness.The local phase may use a different sufficiently small constant stepsize.
  • Last iterate convergence of OMWU: Starting from uniform distributions, OMWU reaches the local-stability neighborhood after O(log(nm)/η^3) steps or an equivalent KL-small condition.The proof then changes to the second-phase stepsize and invokes local stability.

4 Experiments

Experiments examine how OMWU's iteration count scales with matrix dimension and target ℓ1 error, using random square matrices and fixed-step runs.

  • Experimental setup: The experiments measure convergence speed by counting iterations until the last iterate reaches a specified ℓ1 distance from the optimal solution.Optimal solutions were computed using linear-programming solvers.
  • Scaling with dimension: For fixed error 0.1, experiments vary random matrix dimensions n = 25, 50, ..., 250 and record iterations from uniform initialization.Entries are sampled independently from uniform [−1, 1].
  • Scaling with error: With n = 50 and η = 0.01, experiments vary target errors ϵ from 0.5 to 0.007812 and count iterations to reach each target.The stepsize remains fixed throughout these runs.
  • Observed scaling: The authors estimate that iteration growth with dimension lies between linear and quadratic, while dependence on error appears inverse polynomial.These are stated as empirical guesses rather than formal scaling results.
  • Stepsize sensitivity: Stepsize selection creates a speed-stability trade-off: large η may produce cycles, whereas smaller η slows progress.The proofs require η to be sufficiently small.

5 Conclusion

The paper reports pointwise convergence of OMWU to Nash equilibria in two-player zero-sum games, using analysis distinct from standard no-regret techniques. It identifies convergence-rate and broader-generalization questions for future work.

  • The number of iterations needed for a given error is examined through an OMWU convergence figure using ℓ1 distance to the optimal solution.
  • OMWU converges pointwise to a Nash equilibrium in two-player zero-sum games.
  • The analysis uses techniques that differ from standard no-regret learning approaches.
  • The authors suggest these techniques may help analyze other learning algorithms without provable pointwise-convergence guarantees.
  • Open questions include polynomial-time convergence in n and m, exact convergence rates, and extending OMWU beyond the bilinear setting.

A.1 Equations computed at point (x, y, z, w)

This appendix section computes partial derivatives for coordinate functions in the OMWU-related expressions at a generic point (x, y, z).

  • The expressions distinguish coordinate functions g1,i and g3,i through their partial derivatives with respect to x.
  • For g3,i, the derivative with respect to x_i is 1, while the other listed partial derivatives are zero.
  • For g4,i, the derivative with respect to y_i is 1 and the other listed partial derivatives are zero.

A.2 Equations computed at point (x∗, y∗, x∗, y∗)

At the optimal point, the appendix uses equal-payoff identities on the supports of x∗ and y∗ and records coordinate-wise derivative behavior for the associated functions.

  • At (x∗, y∗), supported coordinates satisfy (A⊤x∗)_i = (Ay∗)_j = v, where v = x∗⊤Ay∗.
  • The normalization factors at the optimum are Sx = e^(ηv) and Sy = e^(-ηv).
  • For coordinates outside Supp(x∗), the listed cross-coordinate derivatives of g1,i are zero.
  • For coordinates outside Supp(y∗), the listed cross-coordinate derivatives of g2,i are zero.
  • The appendix records unit derivatives in x_i for g3,i and y_i for g4,i, with other listed derivatives equal to zero.

B Missing claims and proofs

The appendix develops lemmas controlling OMWU’s update differences, auxiliary quantities, and KL-divergence change. These ingredients establish contraction away from a neighborhood of the optimum under sufficiently small learning rates.

  • Lemma B.1: Lemma B.1 states that one-step changes in classic and linear OMWU are O(η), while their next iterates differ by O(η^2) in distance.
  • Auxiliary inequalities: The displayed inequalities show decreases involving ηR_t^x and ηR_t^y, up to O(η^2) terms and a factor 1 − O(η).
  • Update comparison: The proof compares OMWU with its linear variant and uses the fact that the extrapolated iterate remains in the simplex for sufficiently small η.
  • KL-divergence analysis: The KL-divergence proof computes the difference between consecutive iterates, then applies Lemma B.4 and second-order Taylor approximations.
  • KL-divergence analysis: As long as the iterate is not O(η^(1/3))-close to the solution, the derived inequalities imply a decrease in KL divergence by at least a factor of η^3.
  • Spectral property: Lemma B.5 shows that a product of a skew-symmetric matrix and a positive diagonal matrix has only imaginary eigenvalues.
Loading 1807.04252v5…