Last-Iterate Guarantees for Learning in Co-coercive Games

1. Problem Statement

The paper addresses the problem of decentralized learning in multi-agent continuous games where agents seek to reach a Nash Equilibrium (NE) using Vanilla Stochastic Gradient Descent (SGD).

• Context: In many real-world applications (e.g., resource allocation, pricing), agents update their actions based on noisy local gradient information.
• The Gap: Existing convergence guarantees for SGD in games largely rely on Strong Monotonicity, which ensures a unique NE and fast convergence ($O(1/k)$). However, many practical games are not strongly monotone.
• The Specific Challenge: The authors focus on Co-coercive games, a broader class that includes games with multiple equilibria (non-singleton NE sets) and negative semidefinite interaction matrices.
• The Noise Model: Prior work on co-coercive games often assumes a relative noise model, where the noise variance vanishes as the iterates approach equilibrium. This is often unrealistic in practice, especially with unbounded action spaces. The paper tackles the more difficult non-vanishing noise scenario where the noise variance scales affinely with the squared norm of the iterates ($E[\|M_{t+1}\|^2] \leq \sigma^2(1 + \|x_t\|^2)$).

Goal: Establish finite-time last-iterate convergence guarantees (bounds on the error of the final iterate $x_t$, not just the time-average) for vanilla SGD in co-coercive games under this general, non-vanishing noise model.

2. Methodology

The authors employ a rigorous probabilistic analysis combining stochastic approximation theory with techniques from fixed-point iterations.

• Game Definition:
  • A game is defined as $\lambda$-co-coercive if the gradient operator $v(x)$ satisfies:
    $$\langle x' - x, v(x') - v(x) \rangle \leq -\lambda \|v(x') - v(x)\|^2$$
  • This implies $-v(\cdot)$ is co-coercive, a condition weaker than strong monotonicity but stronger than simple monotonicity.
• Algorithm: Vanilla SGD (Gradient Ascent for utility maximization):
  $$x_{n, t+1} = x_{n, t} + \beta_t \hat{v}_{n, t}$$
  where $\hat{v}_{n, t} = v_n(x_t) + M_{n, t+1}$ is the noisy gradient.
• Stepsize Schedule: The analysis uses a polynomially decaying stepsize $\beta_t = (t + T_0)^{-b}$ with $0.5 < b < 1$.
• Proof Strategy:
  1. Almost Sure Stability: Using the Robbins-Siegmund Theorem, the authors prove that the iterates are almost surely bounded, which is a prerequisite for convergence analysis.
  2. Modified Iterates (Key Innovation): To handle the non-vanishing noise in the last-iterate bound, the authors introduce an auxiliary sequence. They define an error sequence $U_t$ related to the martingale noise and a modified iterate $z_t = x_t - U_t$.
  3. Decoupling Noise: They show that the distance between the actual iterate $x_t$ and the modified iterate $z_t$ decays sufficiently fast ($O(\beta_t)$). This allows them to analyze the convergence of $z_t$ (which behaves more like a deterministic iteration) and then map the bounds back to $x_t$.
  4. Inexact Krasnosel'skii-Mann (KM) Iterations: The proof draws inspiration from the analysis of inexact KM iterations, extending these arguments to handle the specific structure of co-coercive operators and the affine noise scaling.

3. Key Contributions

1. First Last-Iterate Bound for Co-coercive Games with Non-Vanishing Noise: This is the first work to establish a finite-time last-iterate convergence rate for vanilla SGD in co-coercive games without assuming the noise vanishes near the equilibrium.
2. General Noise Model: The paper relaxes the noise assumption from "relative noise" (vanishing) to a general model where noise variance scales with the iterate norm. This is crucial for modeling learning in unbounded action spaces.
3. Handling Non-Singleton Equilibria: The analysis accommodates games where the set of Nash Equilibria is not a single point (e.g., potential games with concave potentials), proving convergence to the set of equilibria.
4. Novel Proof Technique: The introduction of the modified iterate $z_t$ to decouple the martingale noise from the last-iterate analysis is a significant methodological contribution.

4. Main Results

The paper establishes the following convergence rates for the mean-square residual $\mathbb{E}[\|v(x_t)\|^2]$, where $v(x)$ is the game gradient (zero at NE):

• Almost Sure Convergence: The iterates $x_t$ converge almost surely to the set of Nash Equilibria $X^*$.

• Time-Average Convergence: The time-averaged residual converges at a rate of $O(1/t^{1-b})$.

• Last-Iterate Convergence (Main Theorem):
  The convergence rate depends on the stepsize parameter $b$:

  • If $b \in (1/2, 2/3)$: Rate is $O(t^{-(2b-1)})$.
  • If $b = 2/3$: Rate is $O(\frac{\log t}{t^{1/3}})$.
  • If $b \in (2/3, 1)$: Rate is $O(t^{-(1-b)})$.

  Optimal Rate: The best achievable rate is $O(\frac{\log t}{t^{1/3}})$ by choosing $b=2/3$.

5. Significance

• Theoretical Advancement: Prior to this work, last-iterate guarantees for co-coercive games were limited to settings with vanishing noise or required modified algorithms (like Extragradient or Optimistic Gradient). This paper proves that Vanilla SGD is sufficient for last-iterate convergence even under realistic, non-vanishing noise conditions.
• Practical Relevance: The noise model used (affine scaling with iterate norm) is more realistic for applications with unbounded action spaces (e.g., power control, financial markets) where variance does not naturally shrink to zero.
• Broad Applicability: The results apply to important classes of games previously difficult to analyze with simple gradient methods, including:
  • Quadratic games with negative semidefinite interaction matrices.
  • Potential games with smooth concave potentials.
• Foundation for Future Work: The techniques developed (specifically the modified iterate approach) provide a framework for analyzing other learning dynamics in games with complex noise structures or weaker monotonicity conditions.

In summary, this paper bridges a critical gap in game-theoretic learning theory by proving that simple, decentralized gradient learning converges to equilibrium in a broad class of games, even when the environment is noisy and the equilibrium is not unique.