PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile

Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan-Sheng Foo, Vijay Chandrasekhar, Georgios Piliouras

arXiv:1807.02629v2cs.LGcs.GTmath.OCstat.ML

TL;DR

Saddle-point theory is well developed mainly for convex-concave problems, while GAN training involves difficult non-monotone settings where first-order methods may cycle or fail. This paper analyzes mirror descent under coherence and shows that an optimistic extra-gradient step yields convergence across coherent problems, with stochastic and GAN experiments supporting the theory.

  • Problem

    The paper addresses limited theory for efficient GAN training beyond convex-concave saddle-point problems, where first-order methods may fail to converge.

  • Method

    The paper studies mirror descent in coherent non-monotone problems and introduces optimistic mirror descent with an extra-gradient step using a future gradient.

  • Results

    The last iterate of optimistic mirror descent converges in all coherent problems, including null-coherent ones, with stochastic guarantees under strict coherence and validation across GAN models.

  • Takeaways & Limitations

    Optimism can eliminate cycles and stabilize first-order GAN training methods as a flexible extra-gradient add-on.

  • Takeaways & Limitations

    Monotonic convergence need not hold with imperfect gradient inputs, since a single bad stochastic sample can disrupt the iterate.

Abstract

from arXiv · show

Owing to their connection with generative adversarial networks (GANs), saddle-point problems have recently attracted considerable interest in machine learning and beyond. By necessity, most theoretical guarantees revolve around convex-concave (or even linear) problems; however, making theoretical inroads towards efficient GAN training depends crucially on moving beyond this classic framework. To make piecemeal progress along these lines, we analyze the behavior of mirror descent (MD) in a class of non-monotone problems whose solutions coincide with those of a naturally associated variational inequality - a property which we call coherence. We first show that ordinary, "vanilla" MD converges under a strict version of this condition, but not otherwise; in particular, it may fail to converge even in bilinear models with a unique solution. We then show that this deficiency is mitigated by optimism: by taking an "extra-gradient" step, optimistic mirror descent (OMD) converges in all coherent problems. Our analysis generalizes and extends the results of Daskalakis et al. (2018) for optimistic gradient descent (OGD) in bilinear problems, and makes concrete headway for establishing convergence beyond convex-concave games. We also provide stochastic analogues of these results, and we validate our analysis by numerical experiments in a wide array of GAN models (including Gaussian mixture models, as well as the CelebA and CIFAR-10 datasets).

1. Introduction

The paper studies mirror descent for coherent non-monotone saddle-point problems, motivated by convergence failures in GAN training and bilinear games. It shows that optimism via an extra-gradient step restores convergence more broadly than vanilla mirror descent.

  • Motivation: GANs remain theoretically difficult because standard optimization methods often fail to converge to reasonable solutions.The paper contrasts adversarial deep learning with better-understood single-agent deep learning.
  • Motivation: First-order methods can fail even in bilinear zero-sum games, while optimistic gradient descent succeeds where vanilla gradient descent fails.This earlier result motivates extending optimism beyond unconstrained bilinear saddle-point problems.
  • Approach: The paper analyzes mirror descent in coherent non-monotone problems, whose solutions coincide with those of an associated variational inequality.This follows a strategy of establishing theory in restricted settings before testing demanding GAN environments.
  • Results: Under strict coherence, vanilla mirror descent converges almost surely, including in stochastic problems, whereas under null coherence it can spiral outward or cycle indefinitely.Null coherence includes all bilinear models, so gradient and mirror descent alone are insufficient in those settings.
  • Method: Optimistic mirror descent uses an extra-gradient step along a future gradient, replacing averaging that does not provide tangible benefits beyond monotone problems.The method changes both the algorithm’s output structure and its accompanying analysis.
  • Results: The last iterate of optimistic mirror descent converges in all coherent problems, including null-coherent ones.The paper also reports stochastic convergence under strict coherence and experimental validation across GAN models and datasets.

2. Problem setup and preliminaries

The paper formulates saddle-point problems as zero-sum optimization over compact convex regions and studies their gradient-driven variational inequalities. It introduces coherence to extend solution equivalence beyond monotone problems, including non-monotone examples.

  • 2.1. Saddle-point problems.: The feasible regions are compact convex subsets of finite-dimensional normed spaces, and the value function is assumed to be continuously differentiable.Compactness streamlines the presentation; a coercivity assumption can replace it in a convex-closed framework.
  • 2.1. Saddle-point problems.: A saddle-point problem has two players: a minimizer seeking the least loss and a maximizer seeking the highest reward.Both objectives are determined by the shared value function f(x1,x2).
  • 2.2. Variational inequalities and coherence.: In monotone, convex-concave problems, saddle-point solutions are equivalently characterized by an associated Minty variational inequality.The paper uses this equivalence as the starting point for a broader formulation.
  • 2.2. Variational inequalities and coherence.: This saddle-point/variational-inequality equivalence extends to bilinear and quasi-convex-concave problems and can hold in non-monotone examples.A one-dimensional example has a unique saddle-point and unique variational-inequality solution despite lacking quasi-monotonicity.
  • 2.2. Variational inequalities and coherence.: Coherence requires saddle-points and variational-inequality solutions to coincide; strict coherence uses strict inequality away from saddle-points, while null coherence uses equality everywhere.Strictly convex-concave problems are strictly coherent, whereas bilinear objectives with interior solutions are typical null-coherent examples.
  • 2.2. Variational inequalities and coherence.: The analysis could accommodate a relaxation in which only some saddle-point solutions are recovered from the variational inequality, but the paper does not pursue it.The restriction is adopted to keep the treatment simple.

3. Mirror descent

The paper formulates mirror descent for coherent saddle-point problems and studies when its iterates converge. Vanilla MD converges under strict coherence but can spiral and cycle under null coherence, including bilinear games.

  • The method: Mirror descent uses a strongly convex distance-generating function to define a Bregman divergence and prox-mapping for gradient-based updates.The prox-mapping produces a feasible point by taking a dual step from the current state.
  • The method: The gradient oracle may be exact or may provide noisy estimates that are unbiased with bounded conditional variance.Exact feedback is recovered when the noise parameter σ equals 0.
  • Convergence analysis: Beyond convex-concave problems, averaging offers no tangible benefits, so convergence must be analyzed for the generating sequence Xn itself.The paper therefore focuses directly on the iterates produced by MD.
  • Convergence analysis: Under strict coherence and suitable step-size summability, MD converges almost surely to a solution, including uniquely under strict convex-concavity.Theorem 3.1 establishes convergence under stochastic gradient feedback; Corollary 3.2 gives the strictly convex-concave case.
  • Convergence analysis: Under null coherence, MD’s Bregman divergence is non-decreasing and its iterates drift away and cycle without converging.For bilinear objectives with an interior saddle point, the limiting divergence remains positive when initialization differs from the solution.

4. Optimistic mirror descent

Optimistic mirror descent replaces averaging with a look-ahead prox step using a future gradient. In coherent problems, its last iterate converges monotonically under exact feedback, while stochastic convergence requires strict coherence and additional step-size conditions.

  • The method: OMD first computes an intermediate waiting state, evaluates the gradient there, and uses that future gradient to produce the next state from the original iterate.This extra-gradient construction is also known as mirror-prox.
  • Convergence analysis: For coherent problems with exact gradients and bounded suitable step sizes, OMD converges monotonically to a solution, with Bregman distance decreasing to zero.The result applies to the last iterate rather than only an ergodic average.
  • Convergence analysis: In bilinear problems, OMD’s iterates also converge monotonically to a solution.This includes the bilinear saddle-point setting addressed by earlier optimistic-gradient analyses.
  • Convergence analysis: OMD converges in coherent problems where MD can fail, and its Bregman distance decreases at every iteration instead of spiraling toward a limit cycle.The paper identifies optimism as the extra-gradient mechanism responsible for this stabilization.
  • Stochastic convergence: With imperfect gradient input, monotonic convergence generally cannot hold because a single bad gradient sample can displace the iterate.Under strict coherence and the theorem’s stochastic assumptions, convergence still holds almost surely with an appropriate variable step-size sequence.
  • Stochastic convergence: The stochastic theorem’s step-size policy differs from the exact-gradient theorem and depends partly on the strong convexity modulus of the distance-generating function.This dependence may permit more aggressive step-size policies through choice of geometry.

5. Experimental results

Experiments test extra-gradient training on multimodal Gaussian mixtures and on CelebA and CIFAR-10 with Adam. Across these settings, the add-on improves distribution learning and stability, while no-look-ahead methods show collapse or oscillation.

  • Gaussian mixture models: In a 16-Gaussian 4 × 4 grid, models trained with RMSprop or Adam without look-ahead exhibit mode collapse or oscillations throughout training.The experiment evaluates outputs through at least 20000 iterations to assess generator hopping behavior.
  • Image experiments: Figure 4 displays samples generated by Adam with an extra-gradient step on CelebA and CIFAR-10.The samples provide a qualitative complement to the metric comparison in Figure 3.
  • Gaussian mixture models: The extra-gradient add-on consistently improves learning of the multimodal Gaussian-mixture distribution and greatly reduces oscillations.Adam with an extra-gradient step is reported as the most promising method in the Gaussian-mixture experiments.

6. Conclusions

The paper concludes that optimism is a flexible add-on for GAN optimizers, improving performance and stability by eliminating cycles. It connects this behavior to coherence and identifies local convergence analysis in multimodal settings as future work.

  • Conclusions: An optimistic extra-gradient step can be attached to diverse GAN training methods, including RMSProp, Adam, and SGA.The experiments indicate noticeable gains in performance and stability across these methods.
  • Conclusions: The strict-versus-null coherence dichotomy explains the stabilizing role of optimism through elimination of cycles.The authors propose that this property supports future local convergence analysis in multimodal settings.

Appendix A. Coherent saddle-point problems

The appendix establishes coherence properties for saddle-point problems, including its relationship to variational inequalities and convex-concave structure. It also proves that coherent solution sets are closed.

  • Convex-concave problems: Convex-concave saddle-point problems are coherent, while strictly convex-concave problems are strictly coherent.The result follows from first-order optimality and monotonicity of the associated gradient operator.
  • Coherence and variational inequalities: Coherence makes saddle-points and solutions of the associated variational inequality coincide.The converse is established by applying the variational inequality along feasible line segments.
  • Coherence and variational inequalities: Strict coherence additionally requires the variational inequality to be strict away from saddle-points.If equality held at a non-saddle point, strict convex-concavity would be contradicted.
  • Closedness of the solution set: Under coherence, the solution set of the saddle-point problem is closed.A convergent sequence of solutions satisfies the variational inequality at its limit, which coherence maps back to a saddle-point.

Appendix B. Properties of the Bregman divergence

The appendix develops the Bregman-divergence and prox-mapping tools used in the convergence analysis. It establishes mirror-map identities, three-point bounds, and regularity properties, while documenting a failure mode of divergence-based convergence tests.

  • Bregman divergence: The Bregman divergence is generated by a strongly convex distance-generating function and lower-bounds squared norm distance.It need not be symmetric or satisfy the triangle inequality.
  • Prox and mirror mappings: The prox-mapping and mirror map are equivalent through the subdifferential relation ∇h(x) + y ∈ ∂h(x+).This identity makes the prox update well-posed and connects it to the convex conjugate mirror map.
  • Bregman bounds: The three-point identity decomposes D(p,x′) into D(p,x), D(x,x′), and a gradient inner-product term.This identity supports the subsequent upper and lower bounds for prox steps.
  • Regularity caveat: Bregman divergence convergence to zero implies norm convergence, but norm convergence need not imply divergence convergence without Bregman reciprocity.Level sets can accumulate at a target while remaining at positive divergence.
  • Bregman bounds: The prox-mapping is Lipschitz in its gradient input, and Proposition B.4 relates prox steps taken along different directions.These properties are used in the analysis of optimistic mirror descent.

Appendix C. Convergence analysis of mirror descent

The appendix analyzes stochastic mirror descent through Bregman-divergence recursions. It proves convergence under strict coherence and characterizes the nonconvergent behavior that can occur under null coherence.

  • Oracle assumptions: The stochastic analysis assumes unbiased gradient estimates, represented by E[ĝ_n | F_n] = g(X_n).The filtration records the history of the generating sequence through the current stage.
  • Mirror descent convergence analysis: Under coherence, the Bregman divergence from any solution converges almost surely to a finite random variable.The proof uses a supermartingale convergence argument under the stated oracle and step-size assumptions.
  • Strict coherence: Under strict coherence, mirror descent has a subsequence approaching the solution set almost surely.The proof combines compactness, strict positivity away from solutions, and martingale estimates.
  • Null coherence: Under null coherence, the Bregman divergence is nondecreasing, so mirror descent can remain on a nonzero divergence level set.The update identity and nonnegativity of the step divergence yield the monotonicity claim.
  • Strict coherence: Consequently, under strict coherence, the full mirror-descent sequence converges almost surely to a solution.The divergence has an almost-sure limit and a subsequence with limit zero, forcing the limit to be zero.

1 Mx2 (C.12)

The appendix shows that finite zero-sum games with an interior equilibrium exhibit null-coherent cycling under vanilla mirror descent. Figure 5 contrasts this behavior with optimistic mirror descent’s convergent trajectory.

  • Figure 5: Figure 5 plots vanilla and optimistic mirror-descent trajectories over objective contours for Matching Pennies.The left and right panels correspond to vanilla and optimistic mirror descent, respectively.
  • Vanilla mirror descent: Finite zero-sum games with a unique interior equilibrium and exact gradients can cycle at positive Bregman distance from equilibrium.This non-convergence does not require summability assumptions on the step sizes.
  • Null coherence: Interior equilibria make the associated bilinear game null-coherent, activating the non-convergence result for mirror descent.The proof uses the equilibrium’s interiority to establish the null-coherence identity.

Appendix D. Convergence analysis of optimistic mirror descent

The appendix establishes monotonic convergence of optimistic mirror descent under coherence, Lipschitz continuity, and bounded step sizes, including exact and stochastic-gradient settings.

  • Algorithm and assumptions: OMD uses incumbent and intermediate gradient queries to take an extra-gradient step through a future gradient.The recursion represents the intermediate state as PXn(−γn ĝn) and the next iterate as PXn(−γn ĝn+1/2).
  • Exact-gradient convergence: Under coherence and Lipschitz continuity, exact-gradient OMD converges monotonically to a solution when step sizes remain positive and below K/L.The theorem states that D(x∗, Xn) decreases monotonically to zero.
  • Stochastic convergence: For stochastic gradients, the analysis tracks martingale terms and shows that the Bregman-distance sequence converges while a subsequence of iterates converges to the solution.The appendix explicitly introduces the stochastic-gradient convergence result and its subsequence argument.
  • Experimental implementation: The experiments implement an optimistic Adam variant using separate moment estimates for the first and second gradient steps.This implementation is used for both Gaussian mixture models and the CelebA/CIFAR-10 experiments.

E.2. Experiments with standards datasets.

Image experiments compare GAN training with and without an extra-gradient step on CelebA and CIFAR-10, using a standard DCGAN architecture and reported inception and FID scores.

  • Image experiments: The extra-gradient add-on improves GAN performance and stabilizes training in CelebA and CIFAR-10 image experiments.Without the extra-gradient step, performance tends to drop noticeably after approximately 100k steps.
  • Image experiments: Generated samples, especially for CelebA, are consistently more representative and faithful to the target data distribution with the optimistic method.The comparison uses Adam with and without an extra-gradient step.
  • Experimental setup: The experiments use a standard DCGAN with a 5-layer batch-normalized generator, an 8-layer discriminator, and 32×32×3 RGB outputs.The architecture and settings are documented for reproducibility.
Loading 1807.02629v2…