ODE Analysis of Stochastic Gradient Methods with Optimism and Anchoring for Minimax Problems

• GAN training remains difficult to understand globally because it solves minimax games with stochastic gradients despite strong empirical success.Source: §1 · p. 1
• The work targets global convergence of last iterates for simGD and its variants in convex-concave zero-sum games using stochastic subgradients.Source: §1 · p. 1
• Continuous-time first-order ODEs guide the analyses by interpreting optimism and anchoring as discretizations of regularized dynamics.Source: §1 · pp. 1–2
• The paper analyzes unmodified simGD, generalized optimistic simGD with separately tuned optimism, and anchored simGD, a new method.Source: §1 · pp. 1–2
• Anchored simGD establishes last-iterate convergence for convex-concave costs with stochastic subgradients without strict convexity or analogous assumptions.Source: §1 · p. 2
• The focus complements prior GAN-improvement directions by treating architecture, losses, and regularizers as fixed and studying optimization dynamics.Source: §1 · p. 2

2 Stochastic simultaneous subgradient descent

• The minimax problem seeks a saddle point of a convex-concave cost, represented by a monotone operator whose zeros are exactly saddle points.Source: §2 · p. 2
• SSSGD uses an unbiased stochastic subgradient oracle with IID randomness and positive learning rates; the section proves convergence under strict convexity in x.Source: §2 · pp. 2–3, §2.2 · p. 3

2.1 Continuous-time illustration

• For continuous-time dynamics, distance to a saddle point need not increase, but without an additional mechanism the trajectory need not converge.Source: §2.1 · p. 3
• In the bilinear example L0(x,u)=xu, trajectories cycle, whereas adding a quadratic primal term makes the saddle point the only cluster point.Source: §2.1 · p. 3, Figure 1 · p. 3

2.2 Discrete-time convergence analysis

• Under (A0), (A1), and (A2), strict convexity in x ensures SSSGD convergence; strict concavity in u can alternatively provide the same result.Source: §2.2 · pp. 3–4
• The proof links discrete stochastic processes to continuous-time differential inclusions, then uses the LaSalle–Krasnovskii principle to identify saddle-point cluster points.Source: §2.2 · p. 4

3.1 Continuous-time illustration

• Continuous-time analysis interprets optimism as a regularized dynamics whose discretization yields SimGD-O and bounds the terminal squared gradient norm.The regularized mapping preserves equilibrium points and is β-cocoercive, while the continuous-time bound is ∥g(t)∥2 ≤ 1/(2αβt) times an initial-distance term.Source: §3.1 · pp. 4–5

3.2 Discrete-time convergenece analysis

• Optimistic simGD converges for convex-concave losses with separate rates when 0 < α < 2β(1 − 2βR).Theorem 2 extends convergence beyond the α = β setting and provides an explicit rate.Source: §3.2 · pp. 5–6
• The optimal bound parameters α = 0.124897/R and β = 1.94431α improve the factor only from 136 to 135.771.The paper describes the improvement over Corollary 1 as very small.Source: §3.2 · p. 5
• The discrete analysis gives a best-iterate gradient bound, whereas Theorem 3 provides a rate close to O(1/k) for the last iterate.The distinction arises because continuous-time gradient norms decrease monotonically, while the discrete norms lack an analogous monotonicity condition.Source: §3.2 · p. 6

3.3 Difficulty with stochastic gradients

• With stochastic gradients, both α_k and β_k must diminish, and α_k must diminish faster than β_k; equal-rate choices fail to converge in the experiment.The reported condition is 0 < q < p for α_k = 1/k^p and β_k = 1/k^q.Source: §3.3 · p. 6, Figure 2 · p. 6
• The observed stochastic-gradient behavior motivates anchoring because general nonlinear convex-concave convergence and compatibility of optimism with subgradients remain unclear.Prior analyses under strict convex-concavity do not establish a compelling need for optimism when simGD already converges.Source: §3.3 · p. 6

4 Simultaneous GD with anchoring

• Anchored simGD is proposed for both deterministic and stochastic setups, using an anchor-rate parameter γ and exponent p in (1/2, 1).The stochastic variant adds a diminishing anchor term toward the initial point z0.Source: §4 · pp. 6–7, §4.2 · p. 8

4.1 Continuous-time illustration

• Anchoring achieves continuous-time rate O(1/t^2), faster than optimism’s O(1/t), although discretization does not preserve this advantage.The discrete analysis explains that accumulated discretization errors prevent a rate better than O(1/k).Source: §4.1 · p. 7, §4.2 · p. 9
• The continuous-time analysis uses a monotonically nonincreasing, nonpositive Lyapunov function to derive convergence-rate bounds for the anchored dynamics.The paper presents this Lyapunov analysis as its strongest contribution but does not treat the ODE arguments as rigorous existence-and-uniqueness theorems.Source: §4.1 · p. 8

4.2 Discrete-time convergenece analysis

• Theorem 3 proves deterministic SimGD-A convergence when p ∈ (1/2, 1) and γ ≥ 2, with the proof viewed as a discretization of the continuous-time analysis.The discrete rate is O(1/k^(2−2p)), which is slightly slower than O(1/k).Source: §4.2 · pp. 8–9
• Theorem 4 proves stochastic SSSGD-A convergence for p ∈ (1/2, 1), ε ∈ (0, 1/2), and γ > 0, while experiments suggest ε = 0 and p = 2/3 are optimal.The small ε is introduced to make the proof work and is conjectured to be removable; bilinear tests show divergence when p < 1/2.Source: §4.2 · pp. 8–9

5 Conclusion

• Anchored SSSGD provably converges for convex-concave costs under the paper’s most general setup.Source: §5 · p. 9
• The paper leaves convergence under different notions and generalizations involving projections or proximal operators as future work.The convergence theorems use differing asymptotic and non-asymptotic notions, while projections arise in GAN techniques such as weight clipping and spectral normalization.Source: §5 · p. 9
• Theorems 2, 3, and 4 extend without proof modifications to monotone operators, with Theorem 4 giving strong convergence in infinite-dimensional settings.Theorem 1 does not extend because its proof uses the LaSalle–Krasnovskii principle specifically for convex-concave saddle functions.Source: §5 · p. 9

A Notation and preliminaries

• The preliminaries formulate equilibria through maximal monotone operators and define Zer(G) as the set of saddle points or equilibrium points.Source: A Notation and preliminaries · p. 13

B Analysis of Theorem 1

• Under (A0), (A1), (A2), and strict convexity in x, Theorem 1 establishes SSSGD convergence.Source: B Analysis of Theorem 1 · p. 14
• The proof uses a differential inclusion technique that connects the discrete-time stochastic process to a continuous-time trajectory.The technique first establishes a differential inclusion limit, analyzes its properties, and then transfers the conclusion back to discrete time.Source: B Analysis of Theorem 1 · p. 14
• The continuous-time argument represents the dynamics through an initial-value differential inclusion and its time-evolution operator.For maximal monotone operators, the solution exists uniquely and the time-evolution operator is 1-Lipschitz.Source: B Analysis of Theorem 1 · pp. 14–15

B.1 Proof of Theorem 1

• Strict convexity enables the differential-inclusion trajectory to converge to a saddle point via an adapted LaSalle–Krasnovskii principle.Source: §B.1 · p. 15
• Monotonicity makes the squared distance to any saddle point nonincreasing along the differential-inclusion trajectory.Source: §B.1 · p. 15

Define the time-shifted process

• The interpolated stochastic process has cluster points that satisfy the differential inclusion, while sharing cluster points with the original iterates.Source: Define the time-shifted process · pp. 16–17
• The proof transfers continuous-time convergence to discrete time by showing subsequential limits evolve toward a saddle point and then using convergence of distances.Source: Define the time-shifted process · pp. 17–18

C Analysis of Theorem 2

• The theorem assumes that L is convex-concave and has a saddle point.Source: C Analysis of Theorem 2 · p. 18
• If 0 < α < 2β(1 − 2βR), SimGD-O converges under assumptions (A0) and (A3).Source: C Analysis of Theorem 2 · p. 18
• The convergence condition couples the learning rate α with the optimism parameter β and constant R.Source: C Analysis of Theorem 2 · p. 18

C.1 Proof of Theorem 2

• The descent argument yields ∥z_{k+1} − z_k∥^2→0 and ∥g_k∥^2→0.These limits are obtained after summing the one-step inequality and using the auxiliary bounds.Source: §C.1 · p. 19
• The iterates are bounded, every convergent subsequence reaches an equilibrium, and the full sequence converges to z∞.The proof uses continuity of G and g_k→0 to obtain G(z∞)=0, then identifies z⋆ with z∞ to prove z_k→z∞.Source: §C.1 · p. 19
• Under Theorem 2’s assumption β > 1/2 and R < (2β −1)/(4β^2), the sequence ∥zk+1 + βgk −z⋆∥2 + 2β2R∥zk+1 −zk∥2 is nonincreasing.Source: §C.1 · pp. 18–19

D.1 Preliminary lemmas

• Elementary inequalities and discrete recursion lemmas provide the convergence tools used to control nonnegative sequences and establish vanishing limits.The lemmas include inequalities for powers, summation bounds, and recursion results such as V_k→0 or lim sup V_k≤C2.Source: §D.1 · pp. 19–20, §D.2 · p. 21

D.3 Proof of Theorem 3

• SimGD-A converges when L is convex-concave with a saddle point, p∈(1/2,1), and γ≥2.The proof outline establishes bounded iterates and controls the discrete second difference before reproducing the continuous-time argument.Source: §D.3 · pp. 21–22
• The discrete proof controls ∥z_{k+1}−2z_k+z_{k−1}∥^2, the discrete analogue of the continuous-time second derivative.Lemma 16 makes this higher-order contribution small enough to support the descent analysis.Source: §D.3 · p. 22
• The argument derives boundedness and convergence through weighted summation, Young’s inequality, monotonicity, and the sequence lemmas.The proof reorganizes the resulting inequalities to bound gradient norms and apply Lemma 13.Source: §D.3 · pp. 22–26

E Analysis of Theorem 4

• SSSGD-A converges when p∈(1/2,1), ε∈(0,1/2), and γ>0 under assumptions (A0) and (A2).The result explicitly does not require L to be differentiable.Source: E Analysis of Theorem 4 · p. 26
• The proof defines ζ_k as a fixed-point-like target and shows the stochastic iterates shrink toward it while ζ_k slowly converges to a solution.This moving-target argument combines contraction toward ζ_k with the stability of the target sequence.Source: E Analysis of Theorem 4 · p. 26
• ζ_k is not an actual fixed point because SSSGD-A includes noise and G may be multivalued.The analysis therefore treats ζ_k as an equivalent auxiliary construction rather than a literal fixed point of the stochastic update.Source: E Analysis of Theorem 4 · p. 26

E.1 Proof of Theorem 4

• A maximal-monotone resolvent result supplies convergence of the auxiliary target toward the solution set.The cited lemma states that (I+τG)^−1(z0) converges to the projection onto Zer(G).Source: E Analysis of Theorem 4 · p. 26