PaperlayerView exact revision on arXiv

Source-linked AI summary

Follow the Regularized Leader Does Not Converge in Constrained Optimization

Ioannis Anagnostides, Ioannis Panageas, Nikolas Patris, Tuomas Sandholm

arXiv:2610.35004v1cs.GTmath.OC

TL;DR

Whether FTRL converges to first-order stationary points in constrained optimization has remained poorly understood. The paper constructs an infinitely smooth counterexample for continuous-time FTRL and proves convergence for analytic objectives on compact polytopes. Thus FTRL can fail to reach first-order stationarity despite monotonic objective improvement, while analyticity yields convergence to a KKT point.

  • Problem

    Whether FTRL converges to first-order stationary points in constrained optimization has remained poorly understood, unlike the established convergence of mirror descent in such settings.

    Source: §1 · p. 2

  • Method

    The paper embeds a non-pointwise-convergent gradient-flow trajectory into higher-dimensional continuous-time FTRL dynamics and separately analyzes analytic objectives on compact polytopes.

    Source: §1.1 · p. 4, §3 · p. 8, §4 · p. 10

  • Results

    For an infinitely differentiable objective in constant dimensions, FTRL's KKT gap can remain bounded away from zero at every time, whereas for analytic objectives on compact polytopes FTRL converges to a KKT point.

    Source: §1.1 · pp. 3–4

  • Takeaways & Limitations

    Analyticity governs FTRL convergence to first-order stationarity: smoothness alone does not prevent a persistent KKT gap.

    Source: §1.1 · pp. 3–4, §6 · p. 14

    The counterexample is developed for Euclidean regularization; extending it to steep regularizers such as negative entropy requires additional ideas.

    Source: §6 · p. 14

Abstract

from arXiv · show

Follow the regularized leader (FTRL) is a foundational algorithm in online learning whose regret properties have been extensively studied for decades. However, in stark contrast to mirror descent---and gradient descent in particular---the convergence of FTRL to first-order stationary points in constrained nonconvex optimization was not well understood. In this paper, we show that continuous-time FTRL can fail to converge even asymptotically in infinitely smooth constrained optimization problems: its Karush-Kuhn-Tucker (KKT) gap can remain bounded away from zero indefinitely. This is especially surprising in light of the fact that continuous-time FTRL guarantees a monotonic improvement of the objective value. As a result, we establish that non-convergent behavior of no-regret dynamics---which besets general variational inequality problems---can occur even in potential systems. From a technical standpoint, our construction relies on an infinitely differentiable function where the gradient flow dynamics exhibit decelerating oscillations without ever converging pointwise, which we in turn embed into higher-dimensional FTRL dynamics that sustain a perpetually large KKT gap. We complement our negative result by showing that FTRL with Euclidean regularization does converge when the objective function is analytic. This shows that the analytic property plays a more fundamental role for FTRL than for gradient flow: it governs not only pointwise convergence, but convergence to first-order stationarity itself.

1 Introduction

The introduction asks whether FTRL converges to first-order stationary points in constrained optimization and answers no for some infinitely smooth objectives. It also presents convergence for analytic objectives and places the results alongside work on potential games and no-regret dynamics.

1.2 Further related work

  • An earlier exponential lower bound for FTRL in potential games left eventual convergence open; this paper shows that asymptotic convergence can fail altogether.The paper distinguishes this from nonconvergence caused by large learning rates in discrete-time FTRL.Source: §1 · p. 2, §1.1 · p. 3

1.1 Our results

  • Continuous-time FTRL can improve the objective monotonically while its stationarity gap stays positive, because it responds to cumulative rather than instantaneous gradients.Projected gradient flow, in contrast, moves immediately along a feasible direction with positive instantaneous gradient.Source: §1.1 · pp. 2–3
  • FTRL with Euclidean regularization can have a KKT gap bounded away from zero at every time, even for an infinitely differentiable objective in constant dimensions.This establishes a separation from mirror descent and first-order stationarity guarantees.Source: §1 · p. 2, §1.1 · p. 3
  • The counterexample embeds a non-pointwise-convergent gradient-flow trajectory in higher-dimensional FTRL dynamics, using auxiliary coordinates to sustain a large KKT gap.Oscillations keep negative cumulative gradients on inactive coordinates despite periods of positive instantaneous gradients.Source: §1.1 · pp. 3–4
  • For analytic objectives on compact polytopes, FTRL converges to a KKT point, and the proof establishes pointwise convergence.The result also yields convergence to Nash equilibrium in finite potential games.Source: §1.1 · p. 4, §1.2 · p. 5

1.2 Further related work

  • The results show that nonconvergent no-regret dynamics can occur in potential systems, while finite potential games fall within the analytic-objective convergence guarantee.The paper also contrasts its result with lazy FTRL, which converges for smooth potentials and eventually stops in the nearly flat region used by the counterexample.Source: §1.2 · pp. 5–6

2 Preliminaries

The preliminaries set up smooth constrained optimization, define the KKT gap as a stationarity measure, and introduce continuous-time FTRL. They contrast its monotonic potential property with the relation between gradient-flow speed and stationarity.

2.1 Constrained optimization and KKT gap

  • The paper studies maximizing a generally nonconcave smooth function over a convex compact domain, with first-order stationarity measured by the KKT gap.The lower bound applies even to infinitely differentiable objectives.Source: §2.1 · p. 6
  • For product constraint sets, the KKT gap can be expressed through coordinate-wise deviation benefits, so one component with a substantial improvement direction suffices for a large gap.Potential games are a special case: their strategy sets are products of probability simplices and their potential is multilinear in each player's strategy.Source: §2.1 · p. 7

2.2 Follow the regularized leader and the potential property

  • Continuous-time FTRL with Euclidean regularization uses the cumulative gradient to select a feasible strategy, with the paper assuming zero initialization unless stated otherwise.The continuous-time dynamics are the limiting case of discrete-time FTRL as the learning rate approaches zero.Source: §2.2 · p. 7
  • FTRL's objective value is nondecreasing, but unlike constrained gradient flow, its stationarity gap is not bounded by the dynamics' speed.For gradient flow, the KKT gap is at most the domain diameter times the velocity norm almost everywhere.Source: §2.2 · pp. 7–8

3 Gradient flow without pointwise convergence

The section constructs a smooth two-dimensional gradient-flow trajectory that approaches a boundary while oscillating without pointwise convergence. Dwell-time bounds on its oscillations support its later embedding into FTRL.

3 Gradient flow without pointwise convergence

  • The trajectory approaches x1 = 1 while perpetually oscillating in x2, yielding a gradient-flow instance that does not converge pointwise.The construction uses an oscillatory curve that approaches the boundary from the left.Source: §3 · p. 8

3.1 Invariant oscillatory curve

  • The curve x2 = sin(π/(1−x1)) is forward invariant, and trajectories initialized on it have limit set {1} × [−1,1].Along the curve, u increases monotonically while x1 approaches 1.Source: §3.1 · p. 9

3.2 Dwell-time bounds

  • Dwell-time bounds quantify how long the flow spends in x2-level intervals, controlling positive versus negative auxiliary gradients in the later FTRL construction.For large m, the time in the positive-gradient region is a small fraction of an oscillation.Source: §3.2 · pp. 9–10

4 Main result: from gradient flow to FTRL

The construction embeds an oscillatory gradient-flow trajectory in higher-dimensional FTRL while keeping auxiliary coordinates fixed at zero. The resulting dynamics retain a KKT gap bounded away from zero at every time.

4 Main result: from gradient flow to FTRL

  • The construction assigns auxiliary coordinates to x2-level intervals so their cumulative gradients stay nonpositive, keeping them fixed at zero.Dwell-time bounds ensure that negative contributions outweigh positive contributions over each complete oscillation.Source: §4 · pp. 10–12
  • An initialization term makes auxiliary cumulative gradients nonpositive during the first two oscillations and later vanishes as x1 approaches 1.For m ≥ 8, prior negative contributions also outweigh positive contributions during any part of a later oscillation.Source: §4 · pp. 12–13
  • With auxiliary coordinates fixed at zero, the first two coordinates follow gradient flow because they remain in the constraint set’s interior.The proof combines the auxiliary-coordinate invariance with the interior equivalence between gradient flow and FTRL.Source: §4 · p. 13
  • A higher-dimensional FTRL instance reproduces the oscillatory trajectory while maintaining a KKT gap uniformly bounded away from zero.Auxiliary coordinates remain zero, while at least one supplies a positive gradient; the first two coordinates follow the embedded trajectory.Source: §4 · p. 13

5 Convergence for analytic objectives

For analytic objectives on compact polytopes, continuous-time FTRL with Euclidean regularization converges to a KKT point. The proof establishes finite trajectory length using a Łojasiewicz gradient inequality across the polytope’s faces.

5 Convergence for analytic objectives

  • For a real analytic objective on a compact polytope, continuous-time FTRL with Euclidean regularization has finite trajectory length and converges to a KKT point.The theorem allows any nonempty compact polytope and an objective analytic on an open neighborhood of it.Source: §5 · p. 13
  • In every finite potential game, continuous-time FTRL with Euclidean regularization and arbitrary initialization converges to a Nash equilibrium.Source: §5 · p. 13
  • A Łojasiewicz gradient inequality yields a lower bound across the polytope’s faces, including when the active face changes.Combined with the velocity-energy relation, the bound implies finite trajectory length and convergence.Source: §5 · pp. 13–14

6 Conclusions

The paper shows that FTRL can fail to converge to first-order stationary points in constrained optimization, while analyticity restores convergence. The counterexample focuses on Euclidean regularization, with extension to steep regularizers left unresolved.

6 Conclusions

  • FTRL can fail to converge to first-order stationary points in constrained optimization, while the analytic property restores convergence.Source: §6 · p. 14
  • The counterexample focuses on Euclidean regularization; extending it to steep regularizers such as negative entropy would require additional ideas.The authors expect extension to regularizers that keep coordinates at the boundary when cumulative gradients are sufficiently negative.Source: §6 · p. 14

A Omitted proofs

The omitted proofs substantiate the paper’s claims about FTRL’s monotone objective property, nonconvergent trajectories, and a uniformly positive KKT gap. They also establish uniform positivity of an auxiliary quadratic gate along the trajectory’s bounded second coordinate.

A Omitted proofs

  • For continuous-time FTRL on a C1 objective, the objective value is nondecreasing.Source: A Omitted proofs · p. 19
  • The constructed potential Φ is C∞ up to the boundary x1 = 1.The proof shows its derivatives extend continuously there, with boundary value zero.Source: A Omitted proofs · pp. 19–20
  • From any initialization on the invariant curve M, gradient flow has ω-limit set {1} × [−1,1].Along M, u tends to +∞ and x1 tends to 1, while x2 accumulates at every value in [−1,1].Source: A Omitted proofs · p. 21
  • For m ≥ 8 and sufficiently large C, each specified auxiliary coordinate’s cumulative gradient remains nonpositive throughout the unconstrained gradient-flow trajectory.The proof establishes the bound by induction across oscillations.Source: A Omitted proofs · p. 23
  • The trimmed x2-level intervals cover [−1,1] and consecutive intervals overlap positively, ensuring that some auxiliary coordinate retains a constant KKT gap throughout the execution.The overlap and endpoint convention prevent transitions through points where all adjacent quadratics vanish.Source: A Omitted proofs · pp. 25–26
  • Because x2(t) stays in [-1,1], overlapping trimmed intervals and endpoint conventions ensure some q_i^(m)(x2(t)) is positive, giving a positive uniform minimum γ_m.The intervals cover [-1,1], and compactness makes the minimum over z of the maximum gate value strictly positive.Source: A Omitted proofs · p. 26

B Convergence for analytic objectives

For continuous-time FTRL with Euclidean regularization, an analytic objective on a compact polytope guarantees convergence to a KKT point. Analyticity yields finite trajectory length, and the result also applies to finite potential games.

B Convergence for analytic objectives

  • Analytic objectives on compact polytopes give finite-length trajectories that converge to a point with zero KKT gap under continuous-time FTRL with Euclidean regularization.The theorem assumes the objective is real analytic on an open neighborhood of the polytope.Source: B Convergence for analytic objectives · p. 26
  • The proof bounds trajectory speed using the gradient along a face, then applies analyticity to show that the total trajectory length is finite.The Łojasiewicz gradient inequality supplies the analytic-function property used in this argument.Source: B Convergence for analytic objectives · pp. 26, 28, 29
  • Finite trajectory length implies convergence, and continuity of the gradient establishes that the limit has zero KKT gap.The proof takes the limit in the first-order inequality to establish stationarity.Source: B Convergence for analytic objectives · p. 29
  • The theorem applies to compact boxes, ruling out the nonconvergent construction for analytic objectives with Euclidean regularization.It also establishes convergence to a Nash equilibrium for continuous-time FTRL with Euclidean regularization in every finite potential game.Source: B Convergence for analytic objectives · p. 29
Loading 2610.35004v1…