Efficient Regret Minimization in Non-Convex Games

1 Introduction

• Repeated games with non-convex utilities model settings such as risk-averse multiplayer games and adversarial training, but standard regret minimization and equilibrium computation are hard.The paper therefore studies computationally tractable regret and equilibrium notions for these games.Source: §1 · p. 1
• Global regret is tractable when losses are convex or linear in a player's own actions, and its global optimality underlies convergence to standard equilibrium notions.The stated examples include Nash, correlated, and coarse correlated equilibrium.Source: §1 · p. 1
• Because global minimization of non-convex losses is NP-hard, the paper instead targets local optimality with a regret notion that guarantees convergence to a local minimum.This approach aligns with efficient non-convex optimization, which focuses on finding local minima.Source: §1 · p. 1

1.1 Related work

• Multiplicative-weights methods give near-optimal regret bounds for bounded costs and domains, but general versions can require exponential time.Efficient convex regret methods have consequently been prominent.Source: §1.1 · pp. 1–2
• Gradient-based non-convex methods have iteration guarantees for small gradients and stochastic gradients, while second-order methods also seek Hessians close to positive semidefinite [EM15] [CDHS16] [AAZB+16] [ABH16].Prior work also reports dimension-related accelerations via adaptive regularization.Source: §1.1 · p. 2

2 Setting

• In online play, a learner chooses an action from a convex set while an adversary selects a loss, and the learner receives first-order feedback over T rounds.The setting assumes regularity conditions including bounded loss.Source: §2 · p. 2

2.1 Projected gradients and constrained non-convex optimization

• A hidden-valley example shows that finding a vanishing gradient can require exponentially many evaluations, motivating projected gradients for constrained non-convex optimization.The example has a unique zero-gradient point in the valley and identical gradients outside it.Source: §2.1 · pp. 2–3
• A projected gradient implements a gradient step constrained to K; in the small-step limit it matches the interior gradient and removes the outward-facing boundary component.This corresponds to the first-order condition for a local minimum.Source: §2.1 · p. 3
• The projected-gradient norm is no larger than the ordinary gradient norm, and approximate local minima measured this way are robust to small perturbations.The paper notes that a small projected gradient can occur at a boundary point even without a hidden valley.Source: §2.1 · pp. 3–4

2.2 A local regret measure

• Local regret measures the objective of predicting points with small gradients on average, extending typical offline non-convex convergence guarantees.When local regret is sublinear, a randomly selected iterate has a small time-averaged gradient in expectation.Source: §2.2 · pp. 4–5

2.3 Why smoothing is necessary

• A time-smoothed performance measure is necessary in this setting, and the paper motivates using larger window sizes.The discussion also notes that when the window average approximates the current loss, local regret captures a guarantee of playing points with small gradients.Source: §2.3 · p. 5

3 An efficient non-convex regret minimization algorithm

• The algorithm approximates follow-the-leader iterates using projected gradient descent to achieve an optimal local-regret bound.It uses time-smoothed losses and stops each gradient-descent epoch when the projected gradient is sufficiently small.Source: §3 · p. 6
• Theorem 3.1 bounds both w-local regret and the total number of gradient steps for Algorithm 1.The supplied theorem passages do not provide the bound expressions.Source: §3 · p. 6
• With η = 1/β and δ = L, the method uses O(Tw) time-averaged gradient steps and O(Tw^2) gradient-oracle calls.For unconstrained domains, replacing the inner loop with non-convex SVRG yields O(Tw^(5/3)) gradient-oracle calls.Source: §3 · p. 7

4 Implications for offline and stochastic non-convex optimization

• The online framework transfers small local regret to convergence guarantees for offline and stochastic non-convex optimization.The section presents these settings as reductions from an online local-regret bound.Source: §4 · p. 8, §4.1 · p. 8, §4.2 · p. 9

4.1 Offline non-convex optimization

• Algorithm 1 finds an offline point with projected-gradient norm squared at most ε using O(1/ε) gradient-oracle calls.The passage states this matches the best known result for gradient-based convergence.Source: §4.1 · p. 8

4.2 Stochastic non-convex optimization

• The stochastic reduction applies only to the unconstrained case because projected gradients under noisy information are challenging to analyze.The setup uses noisy stochastic-gradient oracles; the paper notes the reduction recovers an optimal convergence rate in ε, but not σ².Source: §4.2 · p. 8
• Algorithm 2 uses O(Tw) stochastic-gradient-oracle calls in total.The supplied theorem and corollary passages do not include complete convergence-bound expressions.Source: §4.2 · p. 9

5 An efficient algorithm with second-order guarantees

• Using second-order information lets the online algorithm target approximate first-order critical points that are locally almost convex.The method replaces gradient-descent epochs with a cubic-regularized Newton method.Source: §5 · p. 10
• The analysis assumes unconstrained domains, twice-differentiable losses, and an L2-Lipschitz Hessian.It also assumes access to value, gradient, and Hessian oracles for each loss.Source: §5 · p. 10
• The second-order algorithm terminates each epoch using a stronger approximate-optimality condition that penalizes local concavity.The paper defines a quantity whose sum is lower bounded by the costs in local regret.Source: §5 · p. 10
• Theorem 5.2 characterizes the iterates and inner-loop iteration count under the stated assumptions.The supplied theorem passages do not include the bound expressions.Source: §5 · pp. 10–11

6 A solution concept for non-convex games

• The time-smoothed local equilibrium uses a window w: no player can improve average performance against opponents’ past w actions through small local deviations.The paper motivates this relaxed target because finding an approximate local equilibrium remains computationally intractable for non-convex utilities.Source: §6 · p. 12
• Algorithm 4 runs k copies of an online algorithm with a w-local regret bound, one for each player’s decision set.Each copy receives its player’s online loss during the repeated game.Source: §6 · p. 13
• For some round w ≤ t ≤ T, Algorithm 4 produces a joint strategy that is an ε-approximate (η, w)-smoothed local equilibrium.The error depends on the players’ local-regret guarantees.Source: §6 · p. 13

6.1 Experience replay for GAN training

• For GANs, a smoothed local equilibrium means the generator and discriminator encounter small averaged gradients on each other’s past w choices, making gradient-based training approximately stationary.GAN training resembles Algorithm 2 with w = 1, except its player updates are alternating rather than simultaneous.Source: §6.1 · p. 14
• Maintaining a buffer of past discriminators is a known GAN-stabilization technique, corresponding to experience replay in reinforcement learning.The paper frames its smoothed local equilibrium as a meaningful, attainable theoretical goal for addressing GAN training instability.Source: §6.1 · p. 14

• The framework permits efficient online and stochastic non-convex optimization algorithms that converge to first- and second-order local optima.Source: §7 · p. 14
• The paper introduces local equilibrium as a solution concept that is efficiently attainable in any non-convex game, unlike Nash equilibrium.Source: §7 · p. 14
• The work extends online learning theory to non-convex loss functions while permitting efficient algorithms.Source: §7 · p. 14

• The proof treats the iterates and gradient differences as stochastic variables because the iterates depend on gradient estimates.Source: A Proof of Theorem 4.4 · p. 16
• Each gradient difference averages w independently sampled unbiased gradient estimates, each with variance σ².Source: A Proof of Theorem 4.4 · p. 16
• Setting η = 1/β yields the claim, and the algorithm makes Tw noisy oracle calls across T rounds.Source: A Proof of Theorem 4.4 · p. 17

• For round t, the proof denotes by τ_t the number of inner-loop iterations used to generate iterate x_t.Source: B Proof of Theorem 5.1 (ii) · p. 17
• The termination argument uses that Φ(z) is at least δ³w³ before the inner loop terminates.Source: B Proof of Theorem 5.1 (ii) · p. 17
• The proof sums the inequality from Lemma B.1 across consecutive inner-loop iterates within an epoch.The analysis recalls that δ = β.Source: B Proof of Theorem 5.1 (ii) · p. 17

• The proof sums the w-regret bounds achieved by each A and truncates the first w−1 terms.Source: C Proof of Theorem 6.2 · p. 18
• The proof derives a property that holds for some t between w and T inclusive.Source: C Proof of Theorem 6.2 · p. 18