betaFeedback

WorksComputer Science

Follow the Regularized Leader Does Not Converge in Constrained Optimization

Abstract

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.

Introduction

Follow the regularized leader (FTRL) is a premier online optimization algorithm that has shaped modern machine learning [22, 44, 20]. The regret properties of FTRL—and variations thereof such as follow the perturbed leader [22]—have engendered a vibrant area of research in the last two decades, and are by now well understood. On top of establishing minimax optimal regret bounds, FTRL provides a broad, unifying framework, encompassing celebrated algorithms such as multiplicative weights update [25, 4]. As such, FTRL has driven empirical breakthroughs in complex domains, serving as the engine for large-scale click-through rate (CTR) prediction [30], and being at the heart of AI milestones in solving zero-sum games [33, 10, 11, 17, 49, 46].

However, despite the tremendous amount of interest FTRL has received, its convergence properties as a first-order optimization algorithm have remained poorly understood. This is in sharp contrast to (online) mirror descent (MD) [36], another seminal class of algorithms in online learning. Indeed, different incarnations of MD algorithms are known to converge to first-order stationary points in time polynomial in 1/ϵ1/\epsilon, where ϵ\epsilon is the stationarity gap. For example, the convergence of gradient descent—which can be viewed as MD endowed with Euclidean regularization—even in nonconvex problems is a cornerstone in optimization theory [37]. This raises the following fundamental question:

Does FTRL converge to first-order stationary points in constrained optimization?

For unconstrained problems, there is a well-known equivalence between FTRL and MD, which holds more generally even in the constrained setting under suitable assumptions on the regularizer (e.g., [29]). This implies that FTRL inherits the convergence of MD in such settings. However, the general question beyond such special cases has remained wide open despite decades of research on the behavior of FTRL. Recent work by Anagnostides et al. [ [2] established an exponential lower bound for FTRL in potential games, which can be viewed as a special case of constrained (nonconvex) optimization problems. Potential games have played a central role in the development of game theory since the pathbreaking work of Rosenthal [ [43], and the convergence of FTRL to Nash equilibria—the natural counterpart of first-order stationary points in the case of games—has received considerable attention (we elaborate on related work in § 1.2). While that result exposes severe inefficiency of FTRL, it leaves open the possibility of eventual convergence.

In this paper, we take a significant step further: we show that FTRL can fail to converge even asymptotically in constrained optimization problems, revealing a more fundamental separation between FTRL and MD.

Our results

In more detail, we examine the convergence of continuous-time FTRL in constrained optimization problems. We focus on the continuous-time version of FTRL because it always has the potential property (Lemma 2.2), in that it can never decrease the value of the potential function (which is to be maximized). As a result, one would expect that the stationarity gap of the dynamics would asymptotically be driven to zero; this would indeed be in line with prior results showing that MWU—an incarnation of FTRL—converges to Nash equilibria in (generic) potential games [24, 39]. On the other hand, the discrete-time version of FTRL only has the potential property when the learning rate is sufficiently small [2]; indeed, FTRL with a large learning rate is known to exhibit a wide spectrum of non-convergent behavior, such as Li-Yorke chaos [39, 7]; those results do not apply in our setting because we examine the limiting case where the learning rate tends to zero.

As alluded to, the notion of convergence we consider is measured in terms of the Karush-Kuhn-Tucker (KKT) gap (Definition 2.1), which is the standard notion of first-order suboptimality in optimization. This is weaker than pointwise convergence; as we shall see, dynamics such as gradient flow always converge in terms of the KKT gap but can still admit non-trivial limit sets.

In this context, our main result is summarized below.

Theorem 1.1. There exists an infinitely differentiable function Φ∈C∞\Phi\in C^{\infty} on a convex and compact domain such that for any time tt, the KKT gap of FTRL with Euclidean regularization on Φ\Phi is at least some constant bounded away from 0. This holds even in constant dimensions.

This result contributes to the fundamental understanding of the convergence of learning algorithms—and FTRL in particular—in nonconvex constrained optimization problems, establishing that FTRL is inherently incapable of serving as a first-order optimizer.

Before we provide a detailed overview of our construction, we first highlight the intuition behind it. First-order stationarity is determined by the instantaneous gradient, whereas FTRL chooses its strategy using the cumulative gradient. As a result, for FTRL to act upon a positive gradient, it must first offset the negative gradients accumulated earlier. Our construction sustains this mismatch between instantaneous and cumulative gradient indefinitely, which explains how FTRL can keep improving the objective while failing to approach first-order stationarity. In contrast, projected gradient flow moves immediately along a feasible direction with positive instantaneous gradient.

Proof overview. The starting point of our construction concerns (continuous-time) gradient flow. Specifically, we rely on an instance in which gradient flow does not converge pointwise—but does converge in terms of the KKT gap. The fact that this phenomenon can occur is well known in the theory of dynamical systems [40]; to foreshadow our main positive result, we recall that—by virtue of the Łojasiewicz inequality [1] (Łojasiewicz 1984)—this can only happen under a non-analytic (but infinitely differentiable) function. In more detail, we first show that gradient flow follows the trajectory shown in Figure 1, governed by x2=sin⁡(πx11−x1)x_2 = \sin\left(\frac{\pi x_1}{1-x_1}\right) (Lemma 3.1), thereby approaching the limit set {1}×[−1,1]\{1\} \times[-1,1]. As time goes by, the dynamics in this instance move ever so slowly as the KKT gap approaches zero. The stalling of the dynamics notwithstanding, a critical property for the purpose of our construction is that the dynamics do not decelerate too quickly (Lemma 3.4).

Schematic illustration of the trajectory of FTRL

Figure 1. Schematic illustration of the trajectory of FTRL on the curve x2=sin⁡(πx11−x1)x_2 = \sin\left(\frac{\pi x_1}{1-x_1}\right). The color indicates the gradient observed on the x3x_3 axis, which is perpendicular to the page. Our argument shows that FTRL never acts upon the positive gradient on the x3x_3 axis.

Our next step is to embed this instance into FTRL dynamics executed on a higher-dimensional space. The upshot is that we will force FTRL to always move on the (x1,x2)(x_1,x_2) plane, where the potential function is essentially flat when x1x_1 approaches 1. At the same time, after a short transient phase, there will always be a direction perpendicular to the (x1,x2)(x_1,x_2) plane in which FTRL will observe a large KKT gap, but will still never act upon it. To realize this counterintuitive behavior, we maintain the invariance that the x1x_1 and x2x_2 coordinates of FTRL remain in the interior throughout, whereas the rest of the coordinates always remain inactive, in that they are stuck at zero. For the active coordinates, namely (x1,x2)(x_1,x_2), it is easy to show that FTRL is equivalent to gradient flow (Claim 4.4), matching the trajectory shown in Figure 1. The more interesting claim is that at least one of the rest of the coordinates will observe a large KKT gap. The reason why this happens is because the cumulative gradient observed by each inactive coordinate will be negative throughout, even though for a constant fraction of the time the instantaneous gradient is positive. This is where the oscillating pattern in the (x1,x2)(x_1,x_2) plane becomes critical: the key idea is to create a large negative gradient in some region of the space that neutralizes the positive gradient in aggregate (Figure 1).

To arrive at Theorem 1.1, we need to tie two loose ends. First, we need to guarantee that for any time the KKT gap of FTRL is at least some constant bounded away from zero. To do so, we lift not just to three dimensions, as shown in Figure 1, but to higher dimensions so that there is always a direction of improvement. Second, to argue about the basis of the induction—that movement only occurs on the (x1,x2)(x_1,x_2) plane—we incorporate an additional term in the objective value that induces large negative gradients in the beginning of the trajectory, but vanishes as x1→1x_1 \to1.

These steps are formalized and described in more detail in § 3 and § 4.

Convergence for analytic objectives Finally, we show that the distinction between smooth and analytic objectives is fundamental for the convergence of FTRL, establishing a positive counterpart to Theorem 1.1.

Theorem 1.2. For any analytic objective on a compact polytope, FTRL converges to a KKT point. In particular, these dynamics converge to a Nash equilibrium in finite potential games.

In a nutshell, the proof—discussed at greater length in § 5—combines the geometry of Euclidean projection onto a polytope with a tailored Łojasiewicz gradient inequality. In fact, our argument establishes pointwise convergence, not just convergence to the set of KKT points.

Further related work

We conclude this section by highlighting some key lines of research closely related to our paper.

Learning in potential games The convergence of learning dynamics in potential games has been a fruitful area of research. Potential games can be viewed as the special case of constrained optimization where the potential function is multilinear (§ 2.1). In that class of games, as discussed, first-order stationary points amount to Nash equilibria [35]. Many natural learning algorithms have been analyzed in potential games [32, 13, 21, 19, 41, 3, 39, 24, 27, 28, 50]. It is worth clarifying that these results concern specifically (last-)iterate convergence to Nash equilibria; a well-known fact is that the average correlated distribution induced by any no-regret dynamics converges to the set of coarse correlated equilibria [34], which is a weaker solution concept—not least in terms of worst-case welfare [8]. Our main result does not apply to finite potential games because there the potential function is a polynomial, and thus analytic—so gradient flow always converges pointwise [1] (Łojasiewicz 1984). For Euclidean regularization, we establish convergence to a single KKT point for analytic objectives on compact polytopes (Theorem 5.1), and hence convergence to Nash equilibrium in every finite potential game (Corollary 5.2). A key reference point is the result of Kleinberg et al. [ [24], which showed that continuous-time multiplicative weights update—the special case of FTRL under entropic regularization—converges to the set of weakly stable Nash equilibria in congestion games from almost every initialization; for almost every choice of congestion costs, all such equilibria are pure. Also, Anagnostides et al. [ [2] showed that a lazy version of FTRL—in which a step is only taken if it is bound to improve the potential by a sufficient amount—always converges when the potential function is smooth. Lazy updates preclude our counterexample as the dynamics would eventually stop moving in the direction where the potential function is essentially flat.

FTRL and sparsity Beyond regret guarantees, FTRL offers an advantage relative to MD in promoting sparsity [48, 29]. For example, this practical benefit has been demonstrated in large-scale click-through rate prediction [30]. Intuitively, FTRL can result in sparser solutions because it allows coordinates to remain inactive despite occasional gradients favoring activation. Our result exposes a limitation of this persistence in constrained nonconvex optimization.

Complexity of constrained optimization From a complexity standpoint, computing a first-order stationary point of a smooth function is complete for the class CLS, which stands for continuous local search [14, 18]. This result holds even in two dimensions and provides strong evidence that no polynomial-time algorithm exists. Related hardness results have been established for computing Nash equilibria in potential games [5, 6]. Indeed, while projected gradient descent converges in such problems, the number of iterations need not be polynomially bounded in the input encoding length. In contrast, our result concerning FTRL applies even when both the number of dimensions and the stationarity gap are absolute constants.

Nonconvergence in games From a broader standpoint, our main result shows that, surprisingly, natural no-regret dynamics can exhibit nonconvergent oscillations even when there is an underlying potential. It is well known that learning dynamics can fail to converge in general-sum games; for example, Daskalakis et al. [ [15] gave an example where multiplicative weights update can fail to converge to Nash equilibria, and there is a rich literature on this subject (e.g., Mertikopoulos et al., [31]; Vlatakis-Gkaragkounis et al. [47]). Our work significantly refines those prior results by reconciling such counterexamples with the potential property, albeit applying beyond finite games. On the other hand, it is worth pointing out that FTRL has been shown to converge in more structured classes of problems, such as bargaining games [23].

Forgetfulness and speed of convergence Finally, Cai et al. [ [12] established a separation between optimistic variants of FTRL and MD in zero-sum games. Their main finding, that fast convergence requires forgetfulness, mirrors our main result. We take a step further by showing that FTRL does not merely suffer from slow convergence, but can fail to converge altogether. Also, our result concerns a fundamentally different class of problems and algorithms compared to Cai et al. [ [12]. In fact, Orabona [ [38] recently showed that optimistic multiplicative weights does converge in convex-concave problems.

Preliminaries

Before we dive into our analysis, in this section, we provide the necessary background on constrained optimization problems (§ 2.1) and follow the regularized leader (§ 2.2).

Constrained optimization and KKT gap

We begin by introducing the underlying class of problems in which we are interested. We let X\mathcal{X} be a convex and compact subset of a Euclidean space, and let Φ:X→R\Phi:\mathcal{X}\to\mathbb{R} be a function to be maximized. Φ\Phi will generally be nonconcave, making global optimization intractable. Instead, the main goal will be to compute a first-order stationary point of Φ\Phi, in a sense formally specified below (Definition 2.1). Φ\Phi is assumed to be smooth, meaning that there exists a parameter L>0L>0 such that ∥∇Φ(x)−∇Φ(x′)∥2≤L∥x−x′∥2\lVert\nabla\Phi(x)-\nabla\Phi(x')\rVert_2\le L\lVert x-x'\rVert_2 for any x,x′∈Xx,x'\in\mathcal{X}. In fact, as we shall see, our lower bound applies even when Φ∈C∞\Phi\in C^\infty, which is to say that the kkth derivatives of Φ\Phi are continuous for any k∈Nk\in\mathbb{N}.

We measure local suboptimality in terms of the Karush-Kuhn-Tucker (KKT) gap [9]. There are multiple equivalent ways (up to polynomial factors) of defining the KKT gap; in this paper, we make use of the following definition.

Definition 2.1 (KKT gap). For a function Φ∈C1\Phi\in C^1 defined on a convex and compact domain X\mathcal{X}, the KKT gap of a point x∈Xx\in\mathcal{X} is defined as

KKTGap⁡(x)≔max⁡x′∈X⟨x′−x,∇Φ(x)⟩.(1)\operatorname{KKTGap}(x) \coloneqq\max_{x'\in\mathcal{X}}\langle x'-x,\nabla\Phi(x)\rangle. \tag*{(1)}

An equivalent definition is in terms of the fixed-point gap of the gradient ascent operator x↦ΠX(x+η∇Φ(x))x\mapsto\Pi_{\mathcal{X}}(x+\eta\nabla\Phi(x)), where ΠX(⋅)\Pi_{\mathcal{X}}(\cdot) denotes the Euclidean projection [16].

We will be interested in the case where the constraint set X\mathcal{X} can be decomposed as the Cartesian product X:=X1×⋯×Xn\mathcal{X} := \mathcal{X}_1 \times\cdots\times\mathcal{X}_n. In that case, the KKT gap per (1) of a point x=(x1,…,xn)x = (x_1, \ldots, x_n) can be equivalently expressed as ∑i=1nmax⁡xi′∈Xi⟨xi′−xi,∇xiΦ(x)⟩\sum_{i=1}^{n} \max_{x_i' \in\mathcal{X}_i} \langle x_i' - x_i, \nabla_{x_i}\Phi(x)\rangle. In particular, the KKT gap will be large if there is a considerable first-order deviation benefit for at least a single component i∈[n]i \in[n]; our lower bound relies on this simple fact.

As discussed, a special case of computing KKT points in constrained optimization is identifying Nash equilibria in potential games [43, 32]. Specifically, in nn-player potential games, X\mathcal{X} can be decomposed as a Cartesian product of nn probability simplices, and Φ\Phi is a multilinear function with respect to the strategies of each player.

Follow the regularized leader and the potential property

We proceed by introducing follow the regularized leader (FTRL) [20]. We focus on the continuous-time version of FTRL, which can be thought of as the limit case of discrete-time FTRL when the learning rate approaches zero. To put this into context, it is worth reiterating that FTRL with a large learning rate is known to exhibit non-convergent behavior [39, 7]; our result is fundamentally different as it is not an artifact of a poorly tuned learning rate. FTRL was historically developed as a regularized version of fictitious play [42], the foundational algorithm in learning in games. Fictitious play can be viewed as the extreme version of FTRL when the learning rate is arbitrarily large; unlike FTRL, fictitious play does not guarantee the no-regret property.

In this context, continuous-time FTRL with Euclidean regularization can be defined as

x(t)=arg⁡max⁡x′∈X{⟨x′,∫0t∇xΦ(x(τ)) dτ⟩−12∥x′∥22}.(2)x(t) = \underset{x' \in\mathcal{X}}{\arg\max}\left\{\left\langle x', \int_0^t \nabla_x \Phi(x(\tau))\,\mathrm{d}\tau\right\rangle- \frac{1}{2}\lVert x' \rVert_2^2\right\}. \tag*{(2)}

where Φ\Phi is the differentiable objective function; in particular, if 0∈X\boldsymbol{0} \in\mathcal{X}, (2) prescribes initializing at 0\boldsymbol{0}. Equivalently, (2) can be expressed as

x(t)=arg⁡min⁡x′∈X∥x′−∫0t∇xΦ(x(τ)) dτ∥2=ΠX(∫0t∇xΦ(x(τ)) dτ).(3)x(t) = \underset{x' \in\mathcal{X}}{\arg\min}\left\lVert x' - \int_0^t \nabla_x \Phi(x(\tau))\,\mathrm{d}\tau\right\rVert_2 = \Pi_{\mathcal{X}}\left(\int_0^t \nabla_x \Phi(x(\tau))\,\mathrm{d}\tau\right). \tag*{(3)}

With an arbitrary initialization y0y_0, the update is x(t)=ΠX(y0+∫0t∇Φ(x(τ)) dτ)x(t) = \Pi_{\mathcal{X}}\left(y_0 + \int_0^t \nabla\Phi(x(\tau))\,\mathrm{d}\tau\right). Unless stated otherwise, we assume zero initialization.

A key property of continuous-time FTRL is that it can never decrease the value of Φ\Phi. In other words, as one would expect, Φ\Phi serves as a potential under the FTRL dynamics; for the discrete-time version of this property when the learning rate is small enough, we refer to Anagnostides et al. [ [2].

Lemma 2.2 (Potential property for FTRL). For FTRL on Φ∈C1\Phi\in C^1, the objective value Φ(x(t))\Phi(x(t)) is nondecreasing, and for almost every t≥0t \ge0,

ddtΦ(x(t))≥0.\frac{d}{dt}\Phi(x(t)) \ge0.

We provide the simple proof of this property in Section A. As a result, Lemma 2.2 reassures us that the potential value is monotonically nondecreasing over time.

Gradient flow Before we proceed, it is worth comparing FTRL with the (projected) gradient flow dynamics, whereby

x˙(t)=ΠTX(x(t))(∇xΦ(x(t))),\dot{x}(t) = \Pi_{T_{\mathcal{X}}(x(t))}(\nabla_x\Phi(x(t))),

where TX(x)T_{\mathcal{X}}(x) denotes the tangent cone of X\mathcal{X} at xx. When the maximum in (2) is consistently attained in the interior of X\mathcal{X}, the first-order optimality conditions imply that FTRL coincides with (unconstrained) gradient flow; we will use this simple observation in our counterexample (Claim 4.4). Gradient flow also enjoys the potential property, as it guarantees ddtΦ(x(t))=⟨x˙,∇xΦ(x(t))⟩≥∥x˙(t)∥22\frac{d}{dt}\Phi(x(t)) = \langle\dot{x},\nabla_x\Phi(x(t))\rangle\geq\|\dot{x}(t)\|_2^2 (by the chain rule and standard properties of the tangent cone projection). Integrating yields ∫0∞∥x˙(t)∥22 dt≤O(1)\int_0^\infty\|\dot{x}(t)\|_2^2\,dt \leq O(1) since Φ\Phi is bounded. Importantly, the norm of the velocity ∥x˙(t)∥2\|\dot{x}(t)\|_2 under (constrained) gradient flow satisfies KKTGap⁡(x(t))≤diam⁡(X)∥x˙(t)∥2\operatorname{KKTGap}(x(t)) \leq\operatorname{diam}(\mathcal{X})\|\dot{x}(t)\|_2 almost everywhere, implying first-order stationarity as the dynamics go along. As we shall see, this is not so for FTRL.

Gradient flow without pointwise convergence

The starting point of our construction is a two-dimensional instance in which gradient flow does not converge pointwise. The fact that this phenomenon can occur is well known in dynamical systems [40], but the point of this section is to establish some key properties that we rely on when we turn to FTRL on a higher-dimensional space (§ 4).

We begin by defining the potential. It is designed so that the trajectory approaches (from the left) the boundary x1=1x_1 = 1 while perpetually oscillating in the x2x_2-coordinate. For x1<1x_1 < 1, we set

u=11−x1,v=π(u−1),δ=x2−sin⁡v.u = \frac{1}{1-x_1}, \qquad v = \pi(u-1), \qquad\delta= x_2-\sin v.

Here, uu measures the proximity to the boundary x1=1x_1 = 1, vv is the total phase of the oscillation, and δ\delta is the signed deviation from the oscillatory curve x2=sin⁡vx_2 = \sin v. The goal is to construct a potential whose gradient flow maintains the invariance δ(t)=0\delta(t) = 0. To this end, we let

a(u):=u4e−u1+π2u4cos⁡2vandL(u):=−πa(u)cos⁡v,a(u) := \frac{u^4e^{-u}}{1+\pi^2u^4\cos^2v} \quad\text{and}\quad L(u):=-\pi a(u)\cos v,

and we define Φ:[0,1]×[−1,1]→R\Phi: [0,1]\times[-1,1]\to\mathbb{R} by

Φ(x1,x2):=−e−u−L(u)δ−12e−uδ2,x1<1.(4)\Phi(x_1,x_2):=-e^{-u}-L(u)\delta-\frac{1}{2}e^{-u}\delta^2,\qquad x_1<1. \tag*{(4)}

At the boundary x1=1x_1 = 1, we define Φ(1,x2)\Phi(1,x_2) by the limit x1→1−x_1\to1^- of the right-hand side of (4), which is 00. The resulting potential is smooth up to the boundary (Lemma A.2). For the enlarged constraint set used in § 4, we extend the same formula to all x1<1x_1<1 and x2∈Rx_2\in\mathbb{R}, and set Φ(x1,x2)=0\Phi(x_1,x_2)=0 for x1≥1x_1\geq1; this extension is C∞C^\infty by the same argument. The role of the linear term L(u)δL(u)\delta in (4) is to make the oscillatory curve M={δ=0}\mathcal{M}=\{\delta=0\} forward invariant under the gradient flow. As we shall show, along this curve, the dynamics reduce to the scalar differential equation u˙=a(u)>0\dot{u}=a(u)>0, so u(t)u(t) increases monotonically and the trajectory moves through successive oscillations while approaching the boundary x1=1x_1=1.

In the remainder of this section, we first formalize that the oscillatory curve {δ=0}\{\delta=0\} is forward invariant (Lemma 3.1). The second and more involved step involves obtaining dwell-time estimates for the motion through each oscillation (Lemma 3.4). All proofs are deferred to Section A.

Invariant oscillatory curve

We first show that the potential function constructed in (4) guarantees the following key invariance.

Lemma 3.1 (Forward invariance). Let M:={(x1,x2):δ=0}={(x1,x2):x2=sin⁡(πx11−x1)}\mathcal{M} := \{(x_1,x_2): \delta= 0\} = \{(x_1,x_2): x_2 = \sin\left(\frac{\pi x_1}{1-x_1}\right)\}. Then M\mathcal{M} is forward invariant under the gradient flow on Φ\Phi.

We state two immediate corollaries stemming from Lemma 3.1.

Corollary 3.2. If gradient flow is initialized at (x1(0),x2(0))=(0,0)(x_1(0),x_2(0)) = (0,0), then δ(t)=0\delta(t) = 0 for all t≥0t \ge0. Moreover, u˙(t)=a(u)>0\dot{u}(t) = a(u) > 0, so u(t)u(t) is strictly increasing.

Corollary 3.3 (Limit sets). If gradient flow is initialized on M\mathcal{M}, then u(t)→+∞u(t) \to+\infty and x1(t)→1x_1(t) \to1. Moreover, the ω\omega-limit set reads ω(x(0))={1}×[−1,1]\omega(x(0)) = \{1\} \times[-1,1].

Dwell-time bounds

Next, we estimate how much time the gradient flow spends in different parts of each oscillation. These dwell-time bounds will be crucial when we embed the two-dimensional gradient flow instance into the higher-dimensional FTRL dynamics, as they allow us to control the cumulative gradient observed by each auxiliary coordinate. Referring back to Figure 1, the key requirement is that, within each oscillation, the positive cumulative gradient is subsumed by the negative cumulative gradient. This requires the flow to spend sufficiently little time in the positive-gradient region; this subsection sets the groundwork for establishing that property.

Phase windows We first introduce the phase windows. We assume that the gradient flow is initialized on the invariant curve M\mathcal{M}. During the kkth oscillation, with k≥2k \ge2, we write

v=2π(k−1)+ϕ,ϕ∈[0,2π],Uk:=2k−1.v = 2\pi(k-1) + \phi,\qquad\phi\in[0,2\pi],\qquad U_k := 2k-1.

In words, ϕ\phi represents the local phase, while vv is the absolute phase. For m≥1m \ge1, we let

ℓ(m):=π2m,h(m):=ℓ(m)2=π2m+1,N(m):=2πh(m)=2m+2.\ell^{(m)} := \frac{\pi}{2^m},\qquad h^{(m)} := \frac{\ell^{(m)}}{2} = \frac{\pi}{2^{m+1}},\qquad N^{(m)} := \frac{2\pi}{h^{(m)}} = 2^{m+2}.

Here, ℓ(m)\ell^{(m)} is the window length and h(m)h^{(m)} is the shift between consecutive windows, so adjacent windows overlap by h(m)h^{(m)}. Furthermore, for i∈{0,…,N(m)−2}i \in\{0,\ldots,N^{(m)}-2\}, we define the non-wrapping windows Ii(m):=[ih(m),ih(m)+ℓ(m)]⊂[0,2π]I_i^{(m)} := [ih^{(m)},ih^{(m)}+\ell^{(m)}] \subset[0,2\pi]. The final window crosses 2π2\pi, and is written as IN(m)−1(m):=[2π−h(m),2π]∪[0,h(m)]I_{N^{(m)}-1}^{(m)} := [2\pi-h^{(m)},2\pi] \cup[0,h^{(m)}], where the wrapping is understood modulo 2π2\pi, so both pieces lie within the same oscillation. Figure 2 contains a visualization of the phase windows.

Overlapping phase windows of decreasing size

Figure 2. Overlapping phase windows of decreasing size. The part shown in teal is the final wrapped part of the last phase window, represented modulo 2π2\pi within the same oscillation.

Dwell times For the construction of the potential in § 4, we express the dwell time in terms of level sets of the x2x_2-coordinate rather than phase windows. To this end, for each phase window Ii(m)I_i^{(m)}, i∈{0,…,N(m)−1}i \in\{0,\ldots,N^{(m)}-1\}, we define the associated x2x_2-level set by

Ai(m):=sin⁡(Ii(m)):={x2∈[−1,1]:x2=sin⁡ϕ for some ϕ∈Ii(m)},A_i^{(m)} := \sin\left(I_i^{(m)}\right) := \{x_2 \in[-1,1] : x_2 = \sin\phi\text{ for some } \phi\in I_i^{(m)}\},

which is the corresponding interval in the x2x_2-coordinate. Then, during the kkth oscillation, we let Tk,i(m)T_{k,i}^{(m)} denote the amount of time for which x2(t)∈Ai(m)x_2(t) \in A_i^{(m)}, and let Qk,i(m)Q_{k,i}^{(m)} denote the amount of time for which x2(t)∉Ai(m)x_2(t) \notin A_i^{(m)}.

Lemma 3.4 (Dwell-time bounds in terms of x2x_2-level sets). Suppose that the gradient flow is initialized on the invariant curve M\mathcal{M}. Then, for every k≥2k \ge2, m≥5m \ge5, and i∈{0,…,N(m)−1}i \in\{0,\ldots,N^{(m)}-1\},

Tk,i(m)≤162mQk,i(m).(5)T_{k,i}^{(m)} \le\frac{16}{2^m}Q_{k,i}^{(m)}. \tag*{(5)}

For the construction in § 4, the time Tk,i(m)T_{k,i}^{(m)} spent in Ai(m)A_i^{(m)} bounds the time during which the corresponding auxiliary gradient is positive; throughout the complementary time Qk,i(m)Q_{k,i}^{(m)}, this gradient is strictly negative. When mm is large, (5) shows that Tk,i(m)T_{k,i}^{(m)} is a small fraction of the oscillation’s duration.

Main result: from gradient flow to FTRL

To obtain our main result, we now embed the gradient flow dynamics of § 3 into a higher-dimensional space. Specifically, the first two coordinates (x1,x2)(x_1,x_2) are the original variables of gradient flow, while the remaining coordinates (x3,…,xN(m)+2)(x_3,\ldots,x_{N^{(m)}+2}) serve an auxiliary role. The key invariance we will establish is that xi(t)=0x_i(t)=0 for any i∈{3,…,N(m)+2}i \in\{3,\ldots,N^{(m)}+2\} and t≥0t \ge0, so FTRL in this higher-dimensional space will remain trapped in the (x1,x2)(x_1,x_2) plane, mimicking the trajectory of gradient flow. In accordance with the dwell-time bounds of Lemma 3.4, we associate x3+ix_{3+i} with the iith x2x_2-level interval. The constraint set is defined as the product of intervals X1×X2×[0,1]×⋯×[0,1]\mathcal{X}_1 \times\mathcal{X}_2 \times[0,1] \times\cdots\times[0,1], where X1=[−1,2]\mathcal{X}_1=[-1,2] and X2=[−2,2]\mathcal{X}_2=[-2,2]; this guarantees that constrained gradient flow with respect to (x1,x2)(x_1,x_2) coincides with the unconstrained gradient flow by virtue of Lemma 3.1.

Higher-dimensional potential We now introduce the augmented potential function. We recall from § 3.2 that each phase window Ii(m)I_i^{(m)} determines the interval

Ai(m)=[αi(m),βi(m)],where αi(m)≔min⁡ϕ∈Ii(m)sin⁡ϕ, βi(m)≔max⁡ϕ∈Ii(m)sin⁡ϕ.A_i^{(m)} = [\alpha_i^{(m)},\beta_i^{(m)}], \qquad\text{where }\alpha_i^{(m)} \coloneqq\min_{\phi\in I_i^{(m)}} \sin\phi,\ \beta_i^{(m)} \coloneqq\max_{\phi\in I_i^{(m)}} \sin\phi.

In particular, for the wrapping window, we have AN(m)−1(m)=sin⁡([2π−h(m),2π]∪[0,h(m)])=[−sin⁡h(m),sin⁡h(m)]A_{N^{(m)}-1}^{(m)}=\sin([2\pi-h^{(m)},2\pi]\cup[0,h^{(m)}])=[-\sin h^{(m)},\sin h^{(m)}]. For each Ai(m)A_i^{(m)}, write Δi(m):=βi(m)−αi(m)>0\Delta_i^{(m)}:=\beta_i^{(m)}-\alpha_i^{(m)}>0 for its length. We introduce a corresponding trimmed interval A~i(m):=[α~i(m),β~i(m)]\widetilde{A}_i^{(m)}:=[\widetilde{\alpha}_i^{(m)},\widetilde{\beta}_i^{(m)}], whose role will become clear shortly. If Ai(m)A_i^{(m)} lies strictly inside [−1,1][-1,1], we remove one quarter of its length from each endpoint, so that

A~i(m):=[αi(m)+Δi(m)4,βi(m)−Δi(m)4].\widetilde{A}_i^{(m)}:=\left[\alpha_i^{(m)}+\frac{\Delta_i^{(m)}}{4},\beta_i^{(m)}-\frac{\Delta_i^{(m)}}{4}\right].

and hence ∣A~i(m)∣=∣Ai(m)∣/2|\widetilde{A}_i^{(m)}|=|A_i^{(m)}|/2. The only intervals that need separate treatment are the endpoint intervals, which come in two types: those reaching 11 and those reaching −1-1. For m≥1m\ge1, no interval reaches both endpoints because each phase window has length at most π/2\pi/2. For the endpoint intervals, we modify the construction slightly. At the endpoint −1-1 or 11, we extend the interval by one quarter of its original length, while trimming the opposite side by one quarter. This extension ensures that the quadratic qi(m)q_i^{(m)} defined below is strictly positive at the corresponding endpoint x2=±1x_2=\pm1, which is needed for a uniformly positive KKT gap. That is, if βi(m)=1\beta_i^{(m)}=1, we set A~i(m):=[αi(m)+Δi(m)/4,βi(m)+Δi(m)/4]\widetilde{A}_i^{(m)}:=\left[\alpha_i^{(m)}+\Delta_i^{(m)}/4,\beta_i^{(m)}+\Delta_i^{(m)}/4\right], while if αi(m)=−1\alpha_i^{(m)}=-1, we set A~i(m):=[αi(m)−Δi(m)/4,βi(m)−Δi(m)/4]\widetilde{A}_i^{(m)}:=\left[\alpha_i^{(m)}-\Delta_i^{(m)}/4,\beta_i^{(m)}-\Delta_i^{(m)}/4\right]; in either case, ∣A~i(m)∣=∣Ai(m)∣|\widetilde{A}_i^{(m)}|=|A_i^{(m)}|.

We associate with the interval A~i(m)\widetilde{A}_i^{(m)} the quadratic term qi(m)(x2):=(x2−α~i(m))(β~i(m)−x2)q_i^{(m)}(x_2):=(x_2-\widetilde{\alpha}_i^{(m)})(\widetilde{\beta}_i^{(m)}-x_2), so that the initial potential function Φ\Phi per (4) in § 3 is now recast as

Φ~(x1,x2,x3,…,xN(m)+2):=Φ(x1,x2)+∑i=0N(m)−1x3+iqi(m)(x2).(6)\widetilde{\Phi}(x_1,x_2,x_3,\ldots,x_{N^{(m)}+2}):=\Phi(x_1,x_2)+\sum_{i=0}^{N^{(m)}-1}x_{3+i}q_i^{(m)}(x_2). \tag*{(6)}

As a result, the gradient of (6) with respect to x3+ix_{3+i} is precisely qi(m)(x2)q_i^{(m)}(x_2). We can now explain the role of the trimmed intervals: they allow us to explicitly bound the positive values of qi(m)q_i^{(m)} inside Ai(m)A_i^{(m)} and obtain a uniform strictly negative upper bound on [−1,1]∖Ai(m)[-1,1]\setminus A_i^{(m)}. Combined with the dwell-time estimate, these bounds will show that its integral over a complete oscillation is negative. At the same time, as long as all auxiliary coordinates remain zero, the added terms do not change the (x1,x2)(x_1,x_2)-trajectory since the added contribution to ∂Φ~/∂x2\partial\widetilde{\Phi}/\partial x_2 is always multiplied by one of the auxiliary variables. Furthermore, the intervals constructed above are such that at any point in time at least one coordinate will observe a positive gradient (Lemma A.5), so FTRL will experience a large KKT gap.

Now, under the constraint set X1×X2×[0,1]×⋯×[0,1]X_1\times X_2\times[0,1]\times\cdots\times[0,1], FTRL can be decomposed as xi(t)=ΠXi(∫0t∇xiΦ~(x(τ)) dτ)x_i(t)=\Pi_{X_i}\left(\int_0^t\nabla_{x_i}\widetilde{\Phi}(x(\tau))\,d\tau\right) for each coordinate ii (Corollary A.1). The first direct consequence of this decomposition is that maintaining the invariance x3+i=0x_{3+i}=0 reduces to showing that the observed cumulative gradient is nonpositive—the projection of any nonpositive number into [0,1][0,1] is 0.

Claim 4.1. For i∈{3,…,N(m)+2}i\in\{3,\ldots,N^{(m)}+2\}, if ∫0t∇xiΦ~(x(τ)) dτ≤0\int_0^t\nabla_{x_i}\widetilde{\Phi}(x(\tau))\,d\tau\le0 for any t≥0t\ge0, then xi(t)=0x_i(t)=0.

Bounding the cumulative gradients We now employ the dwell-time estimate from Lemma 3.4 to control the cumulative gradient observed by each auxiliary coordinate. We fix an oscillation kk and an index i∈{0,…,N(m)−1}i\in\{0,\ldots,N^{(m)}-1\}. We recall that Δi(m)=βi(m)−αi(m)>0\Delta_i^{(m)}=\beta_i^{(m)}-\alpha_i^{(m)}>0 is the length of Ai(m)A_i^{(m)}. The quadratic function qi(m)(x2)q_i^{(m)}(x_2) satisfies the following bounds. First, if Ai(m)A_i^{(m)} contains neither endpoint 11 nor −1-1, then

max⁡x2∈A~i(m)qi(m)(x2)=(Δi(m))216andqi(m)(αi(m))=qi(m)(βi(m))=−3(Δi(m))216.\max_{x_2\in\widetilde{A}_i^{(m)}}q_i^{(m)}(x_2)=\frac{(\Delta_i^{(m)})^2}{16}\quad\text{and}\quad q_i^{(m)}(\alpha_i^{(m)})=q_i^{(m)}(\beta_i^{(m)})=-\frac{3(\Delta_i^{(m)})^2}{16}.

Hence, by concavity, qi(m)(x2)≤−3(Δi(m))2/16q_i^{(m)}(x_2)\leq-3(\Delta_i^{(m)})^2/16 whenever x2∉Ai(m)x_2\notin A_i^{(m)}. For the endpoint intervals,

max⁡x2∈A~i(m)qi(m)(x2)=(Δi(m))24,\max_{x_2\in\widetilde{A}_i^{(m)}}q_i^{(m)}(x_2)=\frac{(\Delta_i^{(m)})^2}{4},

and concavity gives qi(m)(x2)≤−5(Δi(m))2/16q_i^{(m)}(x_2)\leq-5(\Delta_i^{(m)})^2/16 whenever x2∈[−1,1]∖Ai(m)x_2\in[-1,1]\setminus A_i^{(m)}. Let tkt_k denote the time at which u(tk)=2k−1u(t_k)=2k-1, so that t1=0t_1=0 and the kkth oscillation corresponds to [tk,tk+1][t_k,t_{k+1}]. Since qi(m)q_i^{(m)} attains its global maximum at the midpoint of A~i(m)\widetilde{A}_i^{(m)}, the positive upper bounds above also hold throughout Ai(m)A_i^{(m)}. We therefore use the corresponding positive bound over the time Tk,i(m)T_{k,i}^{(m)} spent inside Ai(m)A_i^{(m)} and the negative bound over the complementary time Qk,i(m)Q_{k,i}^{(m)}, obtaining

∫tktk+1qi(m)(x2(t)) dt≤max⁡x2∈A~i(m)qi(m)(x2)Tk,i(m)+sup⁡x2∈[−1,1]∖Ai(m)qi(m)(x2)Qk,i(m)≤(Δi(m))216{Tk,i(m)−3Qk,i(m)if Ai(m)⊂(−1,1),4Tk,i(m)−5Qk,i(m)otherwise.\begin{aligned} \int_{t_k}^{t_{k+1}}q_i^{(m)}(x_2(t))\,\mathrm{d}t\leq\max_{x_2\in\widetilde{A}_i^{(m)}}q_i^{(m)}(x_2)T_{k,i}^{(m)}+\sup_{x_2\in[-1,1]\setminus A_i^{(m)}}q_i^{(m)}(x_2)Q_{k,i}^{(m)} \\ &\leq\frac{(\Delta_i^{(m)})^2}{16} \begin{cases} T_{k,i}^{(m)}-3Q_{k,i}^{(m)} & \text{if } A_i^{(m)}\subset(-1,1),\\ 4T_{k,i}^{(m)}-5Q_{k,i}^{(m)} & \text{otherwise.} \end{cases} \end{aligned}

By Lemma 3.4, both bounds are negative for k≥2k\geq2 and m≥5m\geq5, since Tk,i(m)≤16 2−mQk,i(m)T_{k,i}^{(m)}\leq16\,2^{-m}Q_{k,i}^{(m)} and 16 2−m<116\,2^{-m}<1. Thus, over each complete oscillation, the positive contribution is outweighed by the negative contribution. We summarize this property in the lemma below.

Lemma 4.2. Suppose that (x1(t),x2(t))(x_1(t),x_2(t)) evolves as the (unconstrained) gradient flow executed on (4). If m≥5m\geq5 in (6), then ∫tktk+1qi(m)(x2(t)) dt<0\int_{t_k}^{t_{k+1}}q_i^{(m)}(x_2(t))\,\mathrm{d}t<0 for every k≥2k\geq2 and i∈{0,…,N(m)−1}i\in\{0,\ldots,N^{(m)}-1\}.

Initialization To complete the construction, we need to handle the initialization. To do so, we incorporate an additional term in (6), namely

Φ~′(x1,x2,x3,…,xN(m)+2)≔Φ~(x1,x2,x3,…,xN(m)+2)−C∑i=0N(m)−1x3+iψ(x1),(7)\widetilde{\Phi}'(x_1,x_2,x_3,\ldots,x_{N^{(m)}+2})\coloneqq\widetilde{\Phi}(x_1,x_2,x_3,\ldots,x_{N^{(m)}+2})-C\sum_{i=0}^{N^{(m)}-1}x_{3+i}\psi(x_1), \tag*{(7)}

where C>0C>0 is a sufficiently large constant and ψ(x1)=e−1/(1−x1)\psi(x_1)=e^{-1/(1-x_1)} for x1<1x_1<1, while ψ(x1)=0\psi(x_1)=0 for x1≥1x_1\geq1; this extension is C∞C^\infty. The role of the last term in (7) is this: when CC is large enough, each coordinate x3+ix_{3+i} will observe a large negative gradient in the beginning (so it will remain at 00), but as x1x_1 approaches 11 that term will quickly vanish and become negligible. As before, this additional term will not affect the gradient observed by x1x_1 or x2x_2 as long as all auxiliary coordinates remain zero.

Choosing CC large enough makes the cumulative gradients nonpositive during the first two oscillations. For later oscillations, the negative contribution accumulated during the preceding complete oscillation outweighs the positive contribution during any part of the current one, provided that m≥8m\geq8. This leads to the following lemma, whose proof is given in Section A.

Lemma 4.3. Suppose that (x1(t),x2(t))(x_1(t),x_2(t)) evolves as the (unconstrained) gradient flow executed on (4). If m≥8m \ge8 and C>0C > 0 is large enough, ∫0t∇xiΦ~′(x(τ)) dτ≤0\int_0^t \nabla_{x_i}\widetilde{\Phi}'(x(\tau))\,\mathrm{d}\tau\le0 for any i∈{3,…,N(m)+2}i \in\{3,\ldots,N^{(m)}+2\} and t≥0t \ge0.

For the remainder of the construction, we fix m=8m=8. Combining this lemma with Claim 4.1 shows that xi(t)=0x_i(t)=0 for any t≥0t \ge0 and i∈{3,…,N(m)+2}i \in\{3,\ldots,N^{(m)}+2\}. What remains to argue is that on the (x1,x2)(x_1,x_2) plane, FTRL executed on (7) adheres to the motion described in Lemma 3.1. This follows from the equivalence of FTRL and gradient flow when the latter remains in the interior of the constraint set, as we point out below; the proof follows by simply integrating.

Claim 4.4 (Equivalence of gradient flow to FTRL in the interior). Consider gradient flow on a function Φ\Phi and constraint set X=X1×⋯×Xn\mathcal{X}=\mathcal{X}_1 \times\cdots\times\mathcal{X}_n such that for each i∈S⊆[n]i \in S \subseteq[n], xi(t)x_i(t) is always in the interior of Xi\mathcal{X}_i. For each coordinate i∈Si \in S, xi(t)=∫0t∇xiΦ(x(τ)) dτ=ΠXi(∫0t∇xiΦ(x(τ)) dτ)x_i(t)=\int_0^t \nabla_{x_i}\Phi(x(\tau))\,\mathrm{d}\tau=\Pi_{\mathcal{X}_i}\left(\int_0^t \nabla_{x_i}\Phi(x(\tau))\,\mathrm{d}\tau\right).

To conclude, we start from the oscillatory gradient-flow trajectory from Lemma 3.1, augmented with auxiliary coordinates fixed at zero. This higher-dimensional trajectory is precisely FTRL: Lemma 4.3 together with Claim 4.1 shows this for the auxiliary coordinates, while Claim 4.4 shows it for the first two coordinates. As a result, there is a constant γm>0\gamma_m>0 such that max⁡iqi(m)(x2)≥γm\max_i q_i^{(m)}(x_2) \ge\gamma_m for every x2∈[−1,1]x_2 \in[-1,1] (Lemma A.5). We choose TT such that Cψ(x1(t))≤γm/2C\psi(x_1(t)) \le\gamma_m/2 for all t≥Tt \ge T. For the final objective Φ~′\widetilde{\Phi}', an auxiliary coordinate then gives a KKT gap of at least γm/2\gamma_m/2. On [0,T][0,T], the first two coordinates have a nonzero gradient and remain in the interior, again implying a strictly positive lower bound for the KKT gap. The smaller of these two constants is a uniform lower bound for all t≥0t \ge0. Together, these observations establish Theorem 1.1.

Convergence for analytic objectives

Our counterexample relies on a smooth objective that is not analytic. In this section, we establish that this distinction is fundamental: FTRL run on an analytic objective defined on a polyhedral set is guaranteed to converge to a KKT point.

Theorem 5.1. Let X⊂Rd\mathcal{X} \subset\mathbb{R}^d be a nonempty compact polytope, and let Φ\Phi be real analytic on an open neighborhood of X\mathcal{X}. Continuous-time FTRL with Euclidean regularization has finite trajectory length, ∫0∞∥x˙(t)∥2 dt<∞\int_0^\infty\|\dot{x}(t)\|_2\,\mathrm{d}t < \infty, and thereby converges to a point x∗∈Xx^* \in\mathcal{X} with KKTGap⁡(x∗)=0\operatorname{KKTGap}(x^*)=0.

In particular, any finite potential game admits a polynomial (in fact, multilinear) potential defined on products of simplices, giving the following consequence.

Corollary 5.2. In every finite potential game, continuous-time FTRL with Euclidean regularization and arbitrary initialization converges to a Nash equilibrium.

The detailed proof of Theorem 5.1 is deferred to Section B, but here we provide an overview. The first key claim, established through some basic projection geometry, is that the velocity satisfies almost everywhere

∥x˙(t)∥2≥∥∇F(x(t))Φ(x(t))∥2,\|\dot{x}(t)\|_2 \ge\|\nabla_{F(x(t))}\Phi(x(t))\|_2,

where F(x)F(x) is the smallest face of X\mathcal{X} containing xx and ∇FΦ\nabla_F\Phi is the gradient restricted to its affine hull (Lemma B.2). Second, the Łojasiewicz gradient inequality can be leveraged to establish a lower bound uniformly across all the faces of X\mathcal{X} (Lemma B.3). Namely, writing E(t)=ℓ−Φ(x(t))E(t) = \ell- \Phi(x(t)), where ℓ\ell is the objective value in the limit, we obtain ∥x˙(t)∥2≥cE(t)θ\lVert\dot{x}(t)\rVert_{2} \ge cE(t)^{\theta} almost everywhere for some c>0c > 0 and θ∈[1/2,1)\theta\in[1/2,1), assuming tt is large enough and E(t)>0E(t) > 0; crucially, this holds even when the active face keeps changing. Combining it with the fact that E˙=−∥x˙∥22\dot{E} = -\lVert\dot{x}\rVert_{2}^{2} almost everywhere and integrating implies finite length and thereby convergence to a KKT point x∗x^{*}.

Conclusions

In conclusion, we showed that follow the regularized leader (FTRL) can fail to converge even asymptotically to first-order stationary points in constrained optimization. This establishes a strong separation between the convergence of FTRL and mirror descent (MD), and shows that lack of convergence of no-regret dynamics can manifest itself even in potential systems. On the positive side, we showed that the analytic property restores convergence for FTRL.

Although we focused on Euclidean regularization, we expect the construction to readily extend to broader classes of regularizers that maintain coordinates fixed at the boundary when their cumulative gradients are negative enough. For steep regularizers such as negative entropy, however, the strategy will always be an interior point for any finite time, so extending our construction would require additional ideas.

Acknowledgments

Ioannis Panageas was supported by NSF grant CCF-2454115. Tuomas Sandholm is supported by NIH award A240108S001, the Vannevar Bush Faculty Fellowship ONR N00014-23-1-2876, and National Science Foundation grant RI-2312342. Ioannis Anagnostides is grateful to Emanuel Tewolde and Brian Hu Zhang for helpful discussions. We also thank anonymous NeurIPS reviewers for many helpful comments.

AI disclosure The first version of this paper was prepared without AI assistance. In subsequent revisions, we used various versions of GPT to simplify the arguments, mainly in the proof of our positive convergence result, and identify relatively minor technical issues.

Omitted proofs

This section contains the omitted proofs. We begin by showing that continuous-time FTRL has the potential property.

Lemma 2.2 (Potential property for FTRL). For FTRL on Φ∈C1\Phi\in C^1, the objective value Φ(x(t))\Phi(x(t)) is nondecreasing, and for almost every t≥0t \ge0,

ddtΦ(x(t))≥0.\frac{d}{dt}\Phi(x(t)) \ge0.

Proof. Let y(t)=∫0t∇Φ(x(τ)) dτy(t)=\int_0^t \nabla\Phi(x(\tau))\,d\tau, so that y˙(t)=∇Φ(x(t))\dot{y}(t)=\nabla\Phi(x(t)) and x(t)=ΠX(y(t))x(t)=\Pi_{\mathcal{X}}(y(t)). Both trajectories are Lipschitz, and hence differentiable almost everywhere. Firm nonexpansiveness of the Euclidean projection implies

⟨y(t+h)−y(t),x(t+h)−x(t)⟩≥∥x(t+h)−x(t)∥22.\langle y(t+h)-y(t),x(t+h)-x(t)\rangle\ge\lVert x(t+h)-x(t)\rVert_2^2.

Dividing by h2h^2 and taking the limit h→0h\to0 yields

ddtΦ(x(t))=⟨y˙(t),x˙(t)⟩≥∥x˙(t)∥22≥0.\frac{d}{dt}\Phi(x(t))=\langle\dot{y}(t),\dot{x}(t)\rangle\ge\lVert\dot{x}(t)\rVert_2^2 \ge0.

This concludes the proof. □

We next point out a simple decomposition property of FTRL when the constraint set is a Cartesian product; the proof is immediate.

Corollary A.1. If X=X1×X2×⋯×Xn\mathcal{X}=\mathcal{X}_1\times\mathcal{X}_2\times\cdots\times\mathcal{X}_n, then FTRL can be equivalently expressed as

xi(t)=argmax⁡xi′∈Xi{⟨xi′,∫0t∇xiΦ(x(τ)) dτ⟩−12∥xi′∥22}∀i∈[n].x_i(t)=\underset{x'_i\in\mathcal{X}_i}{\operatorname{argmax}}\left\{\left\langle x'_i,\int_0^t\nabla_{x_i}\Phi(x(\tau))\,d\tau\right\rangle-\frac{1}{2}\lVert x'_i\rVert_2^2\right\}\quad\forall i\in[n].

Lemma A.2 (Smoothness of Φ\Phi). Φ\Phi defined in (4) is C∞C^\infty up to the boundary x1=1x_1=1.

Proof. For x1<1x_1<1, the function Φ\Phi is smooth. Indeed, it is obtained by composition, addition, multiplication, and division of smooth functions, and the denominator in L(u)L(u), 1+π2u4cos⁡2v1+\pi^2u^4\cos^2v, is strictly positive. Thus, the only issue is smoothness at the boundary x1=1x_1=1, which corresponds to u→+∞u\to+\infty.

To argue about this, we will use the standard fact that exponential decay dominates polynomial growth: for every M>0M>0, uMe−u→0u^M e^{-u}\to0 as u→+∞u\to+\infty. This implies that any expression of the form e−uR(u,sin⁡v,cos⁡v)e^{-u}R(u,\sin v,\cos v), where RR grows at most polynomially in uu, tends to zero as u→+∞u\to+\infty, since sin⁡v\sin v and cos⁡v\cos v are bounded. For the expressions appearing below, this decay persists under differentiation. Each expression is a finite sum of terms e−uP(u,sin⁡v,cos⁡v)/(1+π2u4cos⁡2v)je^{-u}P(u,\sin v,\cos v)/(1+\pi^2u^4\cos^2v)^j, with PP a polynomial and j≥0j\ge0 an integer. The operator ∂x1=u2∂u\partial_{x_1}=u^2\partial_u preserves this form, so every derivative with respect to x1x_1 is still bounded by an exponentially decaying factor times a polynomial in uu, and therefore tends to zero.

We now apply this observation to the three terms in (4), which we recall here for completeness:

Φ=−e−u−L(u)δ−12e−uδ2.\Phi=-e^{-u}-L(u)\delta-\frac{1}{2}e^{-u}\delta^2.

First, −e−u-e^{-u} is flat at x1=1x_1=1. That is, all of its x1x_1-derivatives are of the form e−uP(u)e^{-u}P(u), where PP is a polynomial. Thus, all of them tend to zero as u→+∞u \to+\infty. Next, we consider the linear term −L(u)δ-L(u)\delta. Since

L(u)=−πu4e−ucos⁡v1+π2u4cos⁡2v,L(u)=-\frac{\pi u^4e^{-u}\cos v}{1+\pi^2u^4\cos^2v},

and the denominator is bounded below by 1, the factor L(u)L(u) contains the exponentially decaying factor e−ue^{-u}. Therefore L(u)L(u), together with all of its derivatives with respect to x1x_1, tends to zero as u→+∞u \to+\infty. Moreover, δ=x2−sin⁡v\delta=x_2-\sin v. Differentiating δ\delta with respect to x1x_1 only produces polynomial powers of uu and bounded trigonometric factors. So, by the product rule, every x1x_1-derivative of L(u)δL(u)\delta is a finite sum of terms of the form e−uR(u,sin⁡v,cos⁡v,x2)e^{-u}R(u,\sin v,\cos v,x_2), where RR grows at most polynomially in uu. Thus, all such derivatives tend to zero as u→+∞u \to+\infty. Finally, we consider the quadratic term −12e−uδ2-\frac{1}{2}e^{-u}\delta^2. The factor e−ue^{-u} is flat at the boundary. Differentiating δ2\delta^2 with respect to x1x_1 produces only polynomial powers of uu, powers of δ\delta, and bounded trigonometric factors. Since smoothness is a local property in the x2x_2-variable, we may restrict x2x_2 to a compact set; on such a set, δ=x2−sin⁡v\delta=x_2-\sin v is bounded. Therefore, every x1x_1-derivative of e−uδ2e^{-u}\delta^2 also tends to zero as u→+∞u \to+\infty.

It remains to consider differentiation with respect to x2x_2. Since Φ\Phi depends at most quadratically on x2x_2, these derivatives can be computed immediately and read as follows.

∂x2Φ=−L(u)−e−uδ,∂x22Φ=−e−u,∂x2kΦ=0for all k≥3.\partial_{x_2}\Phi=-L(u)-e^{-u}\delta,\qquad\partial_{x_2}^2\Phi=-e^{-u},\qquad\partial_{x_2}^k\Phi=0\quad\text{for all }k\geq3.

Now, each of these expressions, and each of their derivatives with respect to x1x_1, tends to zero as u→+∞u \to+\infty by the preceding argument. Therefore, every mixed partial derivative ∂x1α∂x2βΦ\partial_{x_1}^{\alpha}\partial_{x_2}^{\beta}\Phi has a continuous extension to x1=1x_1=1, and its boundary value is zero. Thus, the extension defined by Φ(1,x2)=0\Phi(1,x_2)=0 is C∞C^\infty up to the boundary x1=1.x_1=1.

Lemma 3.1 (Forward invariance). Let M:={(x1,x2):δ=0}={(x1,x2):x2=sin⁡(πx11−x1)}\mathcal{M}:=\{(x_1,x_2):\delta=0\}=\{(x_1,x_2):x_2=\sin\left(\frac{\pi x_1}{1-x_1}\right)\}. Then M\mathcal{M} is forward invariant under the gradient flow on Φ\Phi.

Proof. We work with the gradient-ascent dynamics x˙=∇Φ(x)\dot{x}=\nabla\Phi(x), where

Φ=−e−u−L(u)δ−12e−uδ2,δ=x2−sin⁡v,v=π(u−1).\Phi=-e^{-u}-L(u)\delta-\frac{1}{2}e^{-u}\delta^2,\qquad\delta=x_2-\sin v,\qquad v=\pi(u-1).

To prove that M={δ=0}\mathcal{M}=\{\delta=0\} is forward invariant, it is enough to show that δ˙=0\dot{\delta}=0 whenever δ=0\delta=0. We first compute the two velocity components on M\mathcal{M}. Since $\partial_{x_2}\delta=1,

x˙2=∂x2Φ=−L(u)−e−uδ=−L(u)(8)\dot{x}_2=\partial_{x_2}\Phi=-L(u)-e^{-u}\delta=-L(u) \tag*{(8)}

on M\mathcal{M}. For the x1x_1-component, we use the fact that ∂u/∂x1=u2\partial u/\partial x_1=u^2, ∂v/∂x1=πu2\partial v/\partial x_1=\pi u^2, and thus

∂δ∂x1=−πu2cos⁡v.\frac{\partial\delta}{\partial x_1}=-\pi u^2\cos v.

On M\mathcal{M}, all terms in ∂x1Φ\partial_{x_1}\Phi containing an explicit factor of δ\delta vanish, so

∂x1Φ=u2e−u−L(u)∂δ∂x1=u2e−u+πu2L(u)cos⁡v.\partial_{x_1}\Phi=u^2e^{-u}-L(u)\frac{\partial\delta}{\partial x_1}=u^2e^{-u}+\pi u^2L(u)\cos v.

Since x˙1=∂x1Φ\dot{x}_1=\partial_{x_1}\Phi and u˙=u2x˙1\dot{u}=u^2\dot{x}_1, we get

u˙=u4e−u+πu4L(u)cos⁡v.(9)\dot{u}=u^4e^{-u}+\pi u^4L(u)\cos v. \tag*{(9)}

Substituting L(u)=−πa(u)cos⁡vL(u)=-\pi a(u)\cos v,

u˙=u4e−u−π2u4a(u)cos⁡2v.\dot{u}=u^4e^{-u}-\pi^2u^4a(u)\cos^2v.

By the definition of

a(u)=u4e−u1+π2u4cos⁡2v,a(u)=\frac{u^4e^{-u}}{1+\pi^2u^4\cos^2v},

we have u4e−u=a(u)(1+π2u4cos⁡2v)u^4e^{-u}=a(u)(1+\pi^2u^4\cos^2v). Therefore, we conclude that u˙=a(u)>0\dot{u}=a(u)>0 on M\mathcal{M}. It remains to check that the tracking error is preserved. Differentiating δ=x2−sin⁡v\delta=x_2-\sin v along the flow gives

δ˙=x˙2−cos⁡v v˙=x˙2−πcos⁡v u˙.(10)\dot{\delta}=\dot{x}_2-\cos v\,\dot{v}=\dot{x}_2-\pi\cos v\,\dot{u}. \tag*{(10)}

Combining with (8), we obtain

δ˙=−L(u)−πa(u)cos⁡v\dot{\delta}=-L(u)-\pi a(u)\cos v

on M\mathcal{M}. This is zero because L(u)=−πa(u)cos⁡vL(u)=-\pi a(u)\cos v. Thus, δ˙=0\dot{\delta}=0 whenever δ=0\delta=0, so M\mathcal{M} is forward invariant, and u˙=a(u)>0\dot{u}=a(u)>0 along M\mathcal{M}.

Corollary 3.3 (Limit sets). If gradient flow is initialized on M\mathcal{M}, then u(t)→+∞u(t)\to+\infty and x1(t)→1x_1(t)\to1. Moreover, the ω\omega-limit set reads ω(x(0))={1}×[−1,1]\omega(x(0))=\{1\}\times[-1,1].

Proof. By Corollary 3.2, if the trajectory is initialized on M\mathcal{M}, then it remains on M\mathcal{M} for all future times, and u˙>0\dot{u}>0 holds. Moreover, 0<a(u)≤u4e−u0<a(u)\le u^4e^{-u} is bounded for u≥1u\ge1, so u(t)u(t) cannot diverge in finite time. We now show that u(t)u(t) cannot converge to a finite value. Suppose, for the sake of contradiction, that u(t)→u∗<+∞u(t)\to u_*<+\infty. Since u(t)u(t) is increasing, this would mean that the trajectory approaches a finite point on the invariant curve. But u˙\dot{u} is continuous and strictly positive at u∗u_*, by definition. Therefore, there exists η>0\eta>0 such that, for all sufficiently large tt, u˙(t)≥η>0\dot{u}(t)\ge\eta>0. This is incompatible with the fact that u(t)u(t) converges to the finite value u∗u_*, thereby implying u(t)→+∞u(t)\to+\infty. Since x1(t)=1−1/u(t)x_1(t)=1-1/u(t), we immediately obtain x1(t)→1x_1(t)\to1. It remains to identify the accumulation set in the x2x_2-coordinate. Since u(t)→+∞u(t)\to+\infty, the phase v(t)=π(u(t)−1)v(t)=\pi(u(t)-1) also tends to +∞+\infty. Moreover, v(t)v(t) is continuous and strictly increasing because v˙(t)=πu˙(t)>0\dot{v}(t)=\pi\dot{u}(t)>0, so the phase passes through infinitely many full periods. Along the invariant curve, x2(t)=sin⁡(v(t))x_2(t)=\sin(v(t)), so x2(t)x_2(t) has every value in [−1,1][-1,1] as an accumulation point.

In particular, let us fix any y∈[−1,1]y\in[-1,1], and choose α∈[−π/2,π/2]\alpha\in[-\pi/2,\pi/2] such that sin⁡α=y\sin\alpha=y. Since v(t)v(t) is continuous, strictly increasing, and tends to +∞+\infty, for every sufficiently large integer nn there is a time tnt_n such that v(tn)=α+2πnv(t_n)=\alpha+2\pi n. Then, x2(tn)=sin⁡(v(tn))=yx_2(t_n)=\sin(v(t_n))=y while x1(tn)→1x_1(t_n)\to1. Therefore,

(x1(tn),x2(tn))→(1,y).(x_1(t_n),x_2(t_n))\to(1,y).

Since y∈[−1,1]y\in[-1,1] was arbitrary, every point of {1}×[−1,1]\{1\}\times[-1,1] is an accumulation point. Conversely, every accumulation point must lie in {1}×[−1,1]\{1\}\times[-1,1], because x1(t)→1x_1(t)\to1 and x2(t)∈[−1,1]x_2(t)\in[-1,1]. Therefore, ω(x(0))={1}×[−1,1]\omega(x(0))=\{1\}\times[-1,1], as claimed.

Lemma 3.4 (Dwell-time bounds in terms of x2x_2-level sets). Suppose that the gradient flow is initialized on the invariant curve M\mathcal{M}. Then, for every k≥2k \ge2, m≥5m \ge5, and i∈{0,…,N(m)−1}i \in\{0,\ldots,N^{(m)}-1\},

Tk,i(m)≤162mQk,i(m).(11)T_{k,i}^{(m)} \le\frac{16}{2^m}Q_{k,i}^{(m)}. \tag*{(11)}

Proof. By Corollary 3.2, the phase satisfies

ϕ˙=v˙=πu˙=πa(u)=πu4e−u1+π2u4cos⁡2v>0.\dot{\phi}=\dot{v}=\pi\dot{u}=\pi a(u)=\frac{\pi u^4 e^{-u}}{1+\pi^2u^4\cos^2v}>0.

Thus, we can compute dwell times by changing variables from time to phase. During the kkth oscillation, u=Uk+ϕ/πu=U_k+\phi/\pi and cos⁡v=cos⁡ϕ\cos v=\cos\phi, so the time density is

gk(ϕ):=dtdϕ=1v˙=euπu4+πeucos⁡2ϕ.(12)g_k(\phi):=\frac{dt}{d\phi}=\frac{1}{\dot{v}}=\frac{e^u}{\pi u^4}+\pi e^u\cos^2\phi. \tag*{(12)}

In particular, gk(ϕ) dϕg_k(\phi)\,d\phi is the time spent while the local phase moves through the infinitesimal interval dϕd\phi. On the invariant curve, x2(t)=sin⁡ϕ(t)x_2(t)=\sin\phi(t) during each oscillation. For each ii, we let

Si:={ϕ∈[0,2π]:sin⁡ϕ∈Ai(m)}.S_i:=\{\phi\in[0,2\pi]:\sin\phi\in A_i^{(m)}\}.

Since sin⁡ϕ=sin⁡(π−ϕ)\sin\phi=\sin(\pi-\phi), this set is the union of Ii(m)I_i^{(m)} and its reflection π−Ii(m)\pi-I_i^{(m)}, interpreted modulo 2π2\pi. The union has measure at most 2ℓ(m)2\ell^{(m)}, including for wrapping windows and windows containing extrema. Thus,

Tk,i(m)=∫Sigk(ϕ) dϕandQk,i(m)=∫[0,2π]∖Sigk(ϕ) dϕ.T_{k,i}^{(m)}=\int_{S_i}g_k(\phi)\,d\phi \quad\text{and}\quad Q_{k,i}^{(m)}=\int_{[0,2\pi]\setminus S_i}g_k(\phi)\,d\phi.

Since k≥2k\ge2, we have Uk≥3U_k\ge3, so the formula for the density gives

gk(ϕ)≤eUke2(181π+π)andgk(ϕ)≥eUkπcos⁡2ϕ.g_k(\phi)\le e^{U_k}e^2\left(\frac{1}{81\pi}+\pi\right) \quad\text{and}\quad g_k(\phi)\ge e^{U_k}\pi\cos^2\phi.

As a result,

Tk,i(m)≤eUke2(181π+π)2ℓ(m),T_{k,i}^{(m)}\le e^{U_k}e^2\left(\frac{1}{81\pi}+\pi\right)2\ell^{(m)},

while

Qk,i(m)≥eUkπ(∫02πcos⁡2ϕ dϕ−∫Sicos⁡2ϕ dϕ)≥eUkπ(π−2ℓ(m)).\begin{aligned} Q_{k,i}^{(m)} &\ge e^{U_k}\pi\left(\int_0^{2\pi}\cos^2\phi\,d\phi-\int_{S_i}\cos^2\phi\,d\phi\right)\\ &\ge e^{U_k}\pi\left(\pi-2\ell^{(m)}\right). \end{aligned}

Using ℓ(m)=π2−m\ell^{(m)}=\pi2^{-m} and m≥5m\ge5, we obtain

Tk,i(m)Qk,i(m)≤2e2(1+1/(81π2))1−21−m2−m<16 2−m.\frac{T_{k,i}^{(m)}}{Q_{k,i}^{(m)}}\le \frac{2e^2(1+1/(81\pi^2))}{1-2^{1-m}}2^{-m}<16\,2^{-m}.

This proves the claimed bound for every i∈{0,…,N(m)−1}i\in\{0,\ldots,N^{(m)}-1\}, with both dwell times measured during the same oscillation.

Lemma 4.3. Suppose that (x1(t),x2(t))(x_1(t),x_2(t)) evolves as the (unconstrained) gradient flow executed on (4). If m≥8m \ge8 and C>0C > 0 is large enough, ∫0t∇xiΦ~′(x(τ)) dτ≤0\int_0^t \nabla_{x_i}\widetilde{\Phi}'(x(\tau))\,\mathrm{d}\tau\le0 for any i∈{3,…,N(m)+2}i \in\{3,\ldots,N^{(m)}+2\} and t≥0t \ge0.

Proof. Fix m≥8m \ge8 and i∈{0,…,N(m)−1}i \in\{0,\ldots,N^{(m)}-1\}. We set r:=16 2−mr := 16\,2^{-m} and let

Ri(t):=∫0t(qi(m)(x2(τ))−Cψ(x1(τ))) dτR_i(t) := \int_0^t \left(q_i^{(m)}(x_2(\tau))-C\psi(x_1(\tau))\right)\,\mathrm{d}\tau

denote the cumulative gradient of coordinate x3+ix_{3+i}. Since ψ(x1(t))=e−u(t)\psi(x_1(t))=e^{-u(t)} along the trajectory, choosing

M:=max⁡0≤j<N(m)z∈[−1,1]max⁡{qj(m)(z),0}andC≥e5(M+1)M := \max_{\substack{0\le j<N^{(m)}\\ z\in[-1,1]}}\max\{q_j^{(m)}(z),0\} \qquad\text{and}\qquad C\ge e^5(M+1)

ensures that, on the first two oscillations,

qi(m)(x2(t))−Cψ(x1(t))≤M−Ce−5≤−1,0≤t≤t3,q_i^{(m)}(x_2(t))-C\psi(x_1(t))\le M-Ce^{-5}\le-1,\qquad0\le t\le t_3,

because 1≤u(t)≤51\le u(t)\le5 on this interval. In particular, Ri(t)≤0R_i(t)\le0 for every t∈[0,t3]t\in[0,t_3]. The bounds preceding Lemma 4.2, together with Lemma 3.4, imply that, for every k≥2k\ge2,

∫tktk+1qi(m)(x2(t)) dt≤(Δi(m))216(4Tk,i(m)−3Qk,i(m))≤−(Δi(m))216(3−4r)Qk,i(m).\int_{t_k}^{t_{k+1}}q_i^{(m)}(x_2(t))\,\mathrm{d}t \le\frac{(\Delta_i^{(m)})^2}{16}\left(4T_{k,i}^{(m)}-3Q_{k,i}^{(m)}\right) \le-\frac{(\Delta_i^{(m)})^2}{16}(3-4r)Q_{k,i}^{(m)}.

Moreover, the density formula (11) and Uk+1=Uk+2U_{k+1}=U_k+2 give gk+1(ϕ)≤e2gk(ϕ)g_{k+1}(\phi)\le e^2g_k(\phi). Since the phase set corresponding to Ai(m)A_i^{(m)} is the same in each oscillation, it follows that

Tk+1,i(m)≤e2Tk,i(m).T_{k+1,i}^{(m)}\le e^2T_{k,i}^{(m)}.

Along the trajectory, qi(m)(x2)q_i^{(m)}(x_2) can be positive only when x2∈Ai(m)x_2\in A_i^{(m)}, and is bounded above by (Δi(m))2/4(\Delta_i^{(m)})^2/4. Thus, for any part of the kkth oscillation,

∫tktqi(m)(x2(τ)) dτ≤(Δi(m))24Tk,i(m),t∈[tk,tk+1].\int_{t_k}^{t}q_i^{(m)}(x_2(\tau))\,\mathrm{d}\tau \le\frac{(\Delta_i^{(m)})^2}{4}T_{k,i}^{(m)},\qquad t\in[t_k,t_{k+1}].

We now argue by induction. Suppose that k≥3k\ge3 and Ri(t)≤0R_i(t)\le0 for all t≤tkt\le t_k. Since the correction term is nonpositive and Ri(tk−1)≤0R_i(t_{k-1})\le0, the bound for the preceding complete oscillation gives

Ri(tk)≤−(Δi(m))216(3−4r)Qk−1,i(m).R_i(t_k)\le-\frac{(\Delta_i^{(m)})^2}{16}(3-4r)Q_{k-1,i}^{(m)}.

As a result, for t∈[tk,tk+1]t\in[t_k,t_{k+1}],

Ri(t)≤−(Δi(m))216(3−4r)Qk−1,i(m)+(Δi(m))24Tk,i(m)≤(Δi(m))216(−(3−4r)+4e2r)Qk−1,i(m)≤0,\begin{aligned} R_i(t)\le-\frac{(\Delta_i^{(m)})^2}{16}(3-4r)Q_{k-1,i}^{(m)} +\frac{(\Delta_i^{(m)})^2}{4}T_{k,i}^{(m)} \\ &\le\frac{(\Delta_i^{(m)})^2}{16}\left(-(3-4r)+4e^{2}r\right)Q_{k-1,i}^{(m)}\le0, \end{aligned}

where the second inequality uses Tk,i(m)≤e2Tk−1,i(m)≤e2rQk−1,i(m)T_{k,i}^{(m)}\le e^2T_{k-1,i}^{(m)}\le e^2rQ_{k-1,i}^{(m)}. The last inequality holds because m≥8m\ge8 implies 2m>643(1+e2)2^m>\frac{64}{3}(1+e^2). The base case holds on [0,t3][0,t_3], so induction proves the claim for all t≥0t\ge0. ∎

Lemma A.3 (Coverage and overlap of the trimmed intervals). For every m≥1m \ge1, the trimmed intervals A~i(m)\widetilde{A}^{(m)}_i cover [−1,1][-1,1], and consecutive intervals overlap by at least

ω(m):=2sin⁡3(h(m)2)sin⁡(3h(m)2)>0.\omega^{(m)} := 2\sin^3\left(\frac{h^{(m)}}{2}\right)\sin\left(\frac{3h^{(m)}}{2}\right)>0.

That is, with indices interpreted modulo N(m)N^{(m)},

∣A~i(m)∩A~i+1(m)∣≥ω(m)for every i∈{0,…,N(m)−1}.\left|\widetilde{A}^{(m)}_i\cap\widetilde{A}^{(m)}_{i+1}\right|\ge\omega^{(m)} \quad\text{for every }i\in\{0,\ldots,N^{(m)}-1\}.

Proof. Since the phase windows Ii(m)I^{(m)}_i cover one full period and x2=sin⁡ϕx_2=\sin\phi along the invariant curve, the intervals Ai(m)=sin⁡(Ii(m))A^{(m)}_i=\sin\left(I^{(m)}_i\right) cover [−1,1][-1,1]. It remains to check that passing from Ai(m)A^{(m)}_i to the trimmed intervals A~i(m)\widetilde{A}^{(m)}_i does not create gaps, and in fact leaves a uniformly positive overlap between consecutive trimmed intervals.

We first consider two consecutive non-wrapping phase windows whose images avoid ±1\pm1 and whose union lies on a monotone branch of sin⁡\sin:

Ii(m)=[ih(m),(i+2)h(m)],Ii+1(m)=[(i+1)h(m),(i+3)h(m)].I^{(m)}_i=[ih^{(m)},(i+2)h^{(m)}],\qquad I^{(m)}_{i+1}=[(i+1)h^{(m)},(i+3)h^{(m)}].

Suppose first that sin⁡\sin is increasing on [ih(m),(i+3)h(m)][ih^{(m)},(i+3)h^{(m)}]. Then

Ai(m)=[sin⁡(ih(m)),sin⁡((i+2)h(m))],Ai+1(m)=[sin⁡((i+1)h(m)),sin⁡((i+3)h(m))].A^{(m)}_i=[\sin(ih^{(m)}),\sin((i+2)h^{(m)})],\qquad A^{(m)}_{i+1}=[\sin((i+1)h^{(m)}),\sin((i+3)h^{(m)})].

Using

A~j(m)=[αj(m)+Δj(m)4,βj(m)−Δj(m)4]=[3αj(m)+βj(m)4,αj(m)+3βj(m)4]\widetilde{A}^{(m)}_j=\left[\alpha^{(m)}_j+\frac{\Delta^{(m)}_j}{4},\beta^{(m)}_j-\frac{\Delta^{(m)}_j}{4}\right]=\left[\frac{3\alpha^{(m)}_j+\beta^{(m)}_j}{4},\frac{\alpha^{(m)}_j+3\beta^{(m)}_j}{4}\right]

for j∈{i,i+1}j\in\{i,i+1\}, the overlap length is

∣A~i(m)∩A~i+1(m)∣=sin⁡(ih(m))+3sin⁡((i+2)h(m))−3sin⁡((i+1)h(m))−sin⁡((i+3)h(m))4\left|\widetilde{A}^{(m)}_i\cap\widetilde{A}^{(m)}_{i+1}\right| =\frac{\sin(ih^{(m)})+3\sin((i+2)h^{(m)})-3\sin((i+1)h^{(m)})-\sin((i+3)h^{(m)})}{4}
=2sin⁡3(h(m)2)cos⁡((i+32)h(m)).=2\sin^3\left(\frac{h^{(m)}}{2}\right)\cos\left(\left(i+\frac{3}{2}\right)h^{(m)}\right).

On a monotone increasing branch, the cosine factor is nonnegative. Moreover, for the monotone pairs under consideration, its smallest possible value occurs for the pair closest to a critical point of sin⁡\sin, and is at least sin⁡(3h(m)/2)\sin(3h^{(m)}/2). Therefore,

∣A~i(m)∩A~i+1(m)∣≥2sin⁡3(h(m)2)sin⁡(3h(m)2)=ω(m).\left|\widetilde{A}^{(m)}_i\cap\widetilde{A}^{(m)}_{i+1}\right|\ge2\sin^3\left(\frac{h^{(m)}}{2}\right)\sin\left(\frac{3h^{(m)}}{2}\right)=\omega^{(m)}.

The case where sin⁡\sin is decreasing on [ih(m),(i+3)h(m)][ih^{(m)},(i+3)h^{(m)}] is identical, with the order of the endpoints reversed. It remains to check the pairs near the extrema of sin⁡\sin. We treat the maximum 11; the minimum −1-1 is symmetric. Let r:=2mr:=2^m. The phase windows whose AA-intervals contain 11 are those with indices r−2r-2, r−1r-1, and rr. By the endpoint rule, these intervals are trimmed on the side away from 11 and extended on the side beyond 11. Thus, 11 is strictly inside each of the corresponding

A~\widetilde{A}-intervals, so these endpoint intervals overlap with one another. Their pairwise overlap has length at least 1−cos⁡h(m)≥ω(m)1-\cos h^{(m)} \ge\omega^{(m)}, since ω(m)=(1−cos⁡h(m))sin⁡(h(m)/2)sin⁡(3h(m)/2)\omega^{(m)}=(1-\cos h^{(m)})\sin(h^{(m)}/2)\sin(3h^{(m)}/2).

We only need to check the overlap with the adjacent ordinary intervals. Consider the left adjacent pair A~r−3(m)\widetilde{A}_{r-3}^{(m)} and A~r−2(m)\widetilde{A}_{r-2}^{(m)}. Since rh(m)=π/2rh^{(m)}=\pi/2, we have

Ar−3(m)=[cos⁡(3h(m)),cos⁡h(m)],Ar−2(m)=[cos⁡(2h(m)),1].A_{r-3}^{(m)}=[\cos(3h^{(m)}),\cos h^{(m)}],\qquad A_{r-2}^{(m)}=[\cos(2h^{(m)}),1].

Thus, the overlap length is at least

cos⁡(3h(m))+3cos⁡h(m)−3cos⁡(2h(m))−14.\frac{\cos(3h^{(m)})+3\cos h^{(m)}-3\cos(2h^{(m)})-1}{4}.

Using the identity

cos⁡(3h(m))+3cos⁡h(m)−3cos⁡(2h(m))−1=2(1−cos⁡h(m))2(2cos⁡h(m)+1),\cos(3h^{(m)})+3\cos h^{(m)}-3\cos(2h^{(m)})-1=2(1-\cos h^{(m)})^2(2\cos h^{(m)}+1),

this becomes

12(1−cos⁡h(m))2(2cos⁡h(m)+1)=2sin⁡3(h(m)2)sin⁡(3h(m)2)=ω(m).\frac{1}{2}(1-\cos h^{(m)})^2(2\cos h^{(m)}+1)=2\sin^3\left(\frac{h^{(m)}}{2}\right)\sin\left(\frac{3h^{(m)}}{2}\right)=\omega^{(m)}.

The right adjacent pair around the maximum is handled by symmetry around π/2\pi/2. The minimum −1-1 is handled in the same way by symmetry around 3π/23\pi/2. Finally, the wrapping pair is covered by the monotone-branch argument after identifying

IN(m)−1(m)=[2π−h(m),2π]∪[0,h(m)]I_{N^{(m)}-1}^{(m)}=[2\pi-h^{(m)},2\pi]\cup[0,h^{(m)}]

with the interval [−h(m),h(m)][-h^{(m)},h^{(m)}]. Its union with I0(m)=[0,2h(m)]I_0^{(m)}=[0,2h^{(m)}] lies on a monotone branch of sin⁡\sin for m≥2m\ge2. The other pair involving the wrapping window follows by reflection about phase zero. For m=1m=1, both overlaps involving the wrapping window have length (2−1)/4=ω(1)(\sqrt{2}-1)/4=\omega^{(1)}.

Thus, every consecutive pair of trimmed intervals overlaps by at least ω(m)>0\omega^{(m)}>0. In particular, the intervals form an overlapping chain whose union contains both endpoints −1-1 and 11. Therefore, they cover the trajectory’s x2x_2-range:

[−1,1]⊆⋃i=0N(m)−1A~i(m).[-1,1]\subseteq\bigcup_{i=0}^{N^{(m)}-1}\widetilde{A}_i^{(m)}.

The preceding lemma shows that the trimmed intervals cover the trajectory’s x2x_2-range with positive overlaps. Each interval A~i(m)=[α~i(m),β~i(m)]\widetilde{A}_i^{(m)}=[\widetilde{\alpha}_i^{(m)},\widetilde{\beta}_i^{(m)}] is paired with the auxiliary coordinate x3+ix_{3+i}, for i∈{0,…,N(m)−1}i\in\{0,\ldots,N^{(m)}-1\}. In the augmented potential (6), this coordinate is coupled to the quadratic function

qi(m)(x2):=(x2−α~i(m))(β~i(m)−x2).q_i^{(m)}(x_2):=(x_2-\widetilde{\alpha}_i^{(m)})(\widetilde{\beta}_i^{(m)}-x_2).

Thus, whenever x2x_2 lies in the interior of the interval A~i(m)\widetilde{A}_i^{(m)}, the coordinate x3+ix_{3+i} receives a positive gradient: increasing x3+ix_{3+i} from the boundary value 00 is a feasible improving deviation. Outside A~i(m)\widetilde{A}_i^{(m)}, the quadratic is always nonpositive; in fact, for x2∈[−1,1]∖Ai(m)x_2\in[-1,1]\setminus A_i^{(m)}, it is strictly negative. This structure is what allows the cumulative negative contribution to dominate the cumulative positive contribution in the dwell-time argument, as shown in § 4.

It remains to show that, throughout the execution of FTRL, there are always variables x3+ix_{3+i} with a constant KKTGap. The point of Lemma A.3 is that such an index ii always exists. Indeed, the trimmed intervals cover the trajectory’s x2x_2-range, and consecutive intervals overlap by at least ω(m)>0\omega^{(m)} > 0. Thus, x2x_2 cannot pass from one interval to the next only through points where all adjacent quadratics vanish. Moreover, at the endpoints ±1\pm1, our convention ensures that the corresponding endpoint term remains strictly positive. We split the proof into two parts. Both lemmas below concern the intermediate objective Φ~\widetilde{\Phi} from (6).

Lemma A.4. Fix m≥1m \ge1 and i∈{0,…,N(m)−1}i \in\{0,\ldots,N^{(m)}-1\}. Suppose that the auxiliary coordinate x3+ix_{3+i} is kept at the boundary value 00. If qi(m)(x2(t))>0q_i^{(m)}(x_2(t)) > 0, then the coordinate-wise first-order gap of x3+ix_{3+i} is strictly positive:

max⁡x3+i′∈X3+i⟨x3+i′−x3+i,∇x3+iΦ~(x(t))⟩>0.\max_{x'_{3+i}\in\mathcal{X}_{3+i}}\left\langle x'_{3+i}-x_{3+i},\nabla_{x_{3+i}}\widetilde{\Phi}(x(t))\right\rangle> 0.

Proof. By construction,

∇x3+iΦ~(x(t))=qi(m)(x2(t)).\nabla_{x_{3+i}}\widetilde{\Phi}(x(t))=q_i^{(m)}(x_2(t)).

Since x3+i=0x_{3+i}=0, choosing any feasible x3+i′>0x'_{3+i}>0 gives

⟨x3+i′−x3+i,∇x3+iΦ~(x(t))⟩=x3+i′qi(m)(x2(t))>0,\left\langle x'_{3+i}-x_{3+i},\nabla_{x_{3+i}}\widetilde{\Phi}(x(t))\right\rangle=x'_{3+i}q_i^{(m)}(x_2(t))>0,

and the claim follows.

Lemma A.5 (Uniformly positive KKTGap). Fix m≥1m \ge1, and suppose that the auxiliary coordinates are kept at x3+i=0x_{3+i}=0 for all i∈{0,…,N(m)−1}i\in\{0,\ldots,N^{(m)}-1\}. There is a constant γm>0\gamma_m>0 such that, at every time tt,

KKTGap⁡(x(t))≥γm>0.\operatorname{KKTGap}(x(t))\ge\gamma_m>0.

Proof. Since the trajectory always satisfies x2(t)∈[−1,1]x_2(t)\in[-1,1], it is enough to find one auxiliary coordinate whose quadratic gate is strictly positive. By Lemma A.3, the intervals A~i(m)\widetilde{A}^{(m)}_i cover [−1,1][-1,1], and consecutive intervals overlap by at least ω(m)>0\omega^{(m)}>0. Therefore, for every x2(t)∈[−1,1]x_2(t)\in[-1,1], there exists an index i∈{0,…,N(m)−1}i\in\{0,\ldots,N^{(m)}-1\} such that qi(m)(x2(t))>0q_i^{(m)}(x_2(t))>0. For points in the interior of [−1,1][-1,1], this follows from the nontrivial overlap of consecutive trimmed intervals. At the endpoint values x2(t)=±1x_2(t)=\pm1, it follows from our convention for the endpoint intervals.

We conclude that the continuous function z↦max⁡iqi(m)(z)z\mapsto\max_i q_i^{(m)}(z) is positive on the compact interval [−1,1][-1,1], so γm:=min⁡z∈[−1,1]max⁡iqi(m)(z)>0\gamma_m:=\min_{z\in[-1,1]}\max_i q_i^{(m)}(z)>0. Choosing x3+i′=1x'_{3+i}=1 for a maximizing index ii gives KKTGap⁡(x(t))≥γm\operatorname{KKTGap}(x(t))\ge\gamma_m.

:::

Convergence for analytic objectives

Our counterexample relies on an infinitely differentiable objective that is not analytic. In this section, we show that, in contrast, analyticity does guarantee convergence to a single KKT point. In particular, our goal is to establish the following.

Theorem 5.1. Let X⊂Rd\mathcal{X}\subset\mathbb{R}^d be a nonempty compact polytope, and let Φ\Phi be real analytic on an open neighborhood of X\mathcal{X}. Continuous-time FTRL with Euclidean regularization has finite trajectory length, ∫0∞∥x˙(t)∥2 dt<∞\int_0^\infty\|\dot{x}(t)\|_2\,\mathrm{d}t<\infty, and thereby converges to a point x⋆∈Xx^\star\in\mathcal{X} with KKTGap⁡(x⋆)=0\operatorname{KKTGap}(x^\star)=0.

The proof proceeds by relating the trajectory speed to the gradient along a certain face of the set, using basic projection geometry. Then, we use analyticity to show that the trajectory length is finite, as claimed in Theorem 5.1.

In what follows, we write

NX(x):={n:⟨n,x′−x⟩≤0 for all x′∈X}N_{\mathcal{X}}(x) := \{n : \langle n, x' - x\rangle\le0 \text{ for all } x' \in\mathcal{X}\}

for the normal cone and

TX(x):={α(x′−x):α≥0, x′∈X}T_{\mathcal{X}}(x) := \{\alpha(x' - x) : \alpha\ge0,\ x' \in\mathcal{X}\}

for the tangent cone. For x=ΠX(y)x = \Pi_{\mathcal{X}}(y), a standard property of the Euclidean projection implies that the residual n=y−xn = y - x belongs to NX(x)N_{\mathcal{X}}(x). The associated critical cone is K=TX(x)∩n⊥\mathcal{K} = T_{\mathcal{X}}(x) \cap n^\perp, which retains the feasible directions orthogonal to the residual. The lemma below can be obtained as a special case of Shapiro [ [45], specialized to polyhedral sets; we provide the simpler proof for completeness.

Lemma B.1. For a nonempty closed polyhedron X\mathcal{X}, let x=ΠX(y)x = \Pi_{\mathcal{X}}(y) and K=TX(x)∩(y−x)⊥\mathcal{K} = T_{\mathcal{X}}(x) \cap(y - x)^\perp. Then, for every v∈Rdv \in\mathbb{R}^d,

lim⁡h↓0ΠX(y+hv)−xh=ΠK(v).\lim_{h \downarrow0} \frac{\Pi_{\mathcal{X}}(y + hv) - x}{h} = \Pi_{\mathcal{K}}(v).

Proof. Let n=y−xn = y - x and wh=(ΠX(y+hv)−x)/hw_h = (\Pi_{\mathcal{X}}(y + hv) - x)/h. Nonexpansiveness of the Euclidean projection implies ∥wh∥2≤∥v∥2\|w_h\|_2 \le\|v\|_2, so every sequence hk↓0h_k \downarrow0 admits a subsequence along which whkw_{h_k} converges. Moreover, ⟨n,wh⟩≤0\langle n, w_h\rangle\le0 since n∈NX(x)n \in N_{\mathcal{X}}(x). Given that x+hwh=ΠX(y+hv)x + hw_h = \Pi_{\mathcal{X}}(y + hv) and x∈Xx \in\mathcal{X}, we have

∥(y+hv)−(x+hwh)∥22≤∥(y+hv)−x∥22.\|(y + hv) - (x + hw_h)\|_2^2 \le\|(y + hv) - x\|_2^2.

Thus,

0≤−2⟨n,wh⟩≤h(∥v∥22−∥v−wh∥22)≤h∥v∥22,0 \le-2\langle n, w_h\rangle\le h(\|v\|_2^2 - \|v - w_h\|_2^2) \le h\|v\|_2^2,

so every limit point of whw_h as h↓0h \downarrow0 belongs to K\mathcal{K}. Now, for any q∈Kq \in\mathcal{K}, polyhedrality ensures that x+hq∈Xx + hq \in\mathcal{X} for all sufficiently small h>0h > 0: active linear constraints remain satisfied because qq belongs to the tangent cone, and inactive constraints have positive slack. Since x+hwh=ΠX(y+hv)x + hw_h = \Pi_{\mathcal{X}}(y + hv),

∥(y+hv)−(x+hwh)∥22≤∥(y+hv)−(x+hq)∥22.\|(y + hv) - (x + hw_h)\|_2^2 \le\|(y + hv) - (x + hq)\|_2^2.

Expanding,

−2h⟨n,wh⟩+∥v−wh∥22≤∥v−q∥22,-\frac{2}{h}\langle n, w_h\rangle+ \|v - w_h\|_2^2 \le\|v - q\|_2^2,

so ∥v−wh∥22≤∥v−q∥22\|v - w_h\|_2^2 \le\|v - q\|_2^2 since ⟨n,wh⟩≤0\langle n, w_h\rangle\le0. Thus, every limit point minimizes distance to vv over K\mathcal{K}, and the claim follows.

Throughout this section, the nonempty faces of X\mathcal{X} include X\mathcal{X} itself, as well as all its proper nonempty faces. For each such face FF, let LF:=span⁡(F−F)\mathcal{L}_F := \operatorname{span}(F - F), where F−F={u−v:u,v∈F}F - F = \{u - v : u, v \in F\}. LF\mathcal{L}_F is the linear subspace of directions parallel to FF. We define ∇FΦ(x):=ΠLF(∇Φ(x))\nabla_F \Phi(x) := \Pi_{\mathcal{L}_F}(\nabla\Phi(x)), the gradient of Φ\Phi restricted to the affine hull of FF. The relative interiors of the nonempty faces partition X\mathcal{X}, so each x∈Xx \in\mathcal{X} lies in the relative interior of exactly one face, denoted by F(x)F(x). Equivalently, F(x)F(x) is the smallest face of X\mathcal{X} containing xx, in the sense that F(x)⊆FF(x) \subseteq F for every face of X\mathcal{X} containing xx. In particular, F(x)=XF(x) = \mathcal{X} whenever xx lies in the relative interior of X\mathcal{X}.

Lemma B.2. Under the assumptions of Theorem 5.1, for almost every t≥0t \ge0,

∥x˙(t)∥2≥∥∇F(x(t))Φ(x(t))∥2.\|\dot{x}(t)\|_2 \ge\|\nabla_{F(x(t))}\Phi(x(t))\|_2.

Proof. The vector field y↦∇Φ(ΠX(y))y \mapsto\nabla\Phi(\Pi_X(y)) is Lipschitz and bounded, so there is a unique solution y(t)y(t), and the projected trajectory x(t)=ΠX(y(t))x(t)=\Pi_X(y(t)) is Lipschitz. By Lemma B.1 and nonexpansiveness, for almost every tt,

x˙(t)=ΠK(t)(∇Φ(x(t))),\dot{x}(t)=\Pi_{K(t)}(\nabla\Phi(x(t))),

where K(t)=TX(x(t))∩(y(t)−x(t))⊥K(t)=T_X(x(t))\cap(y(t)-x(t))^\perp. The first-order optimality condition yields

⟨∇Φ(x(t))−x˙(t),v−x˙(t)⟩≤0for every v∈K(t).\langle\nabla\Phi(x(t))-\dot{x}(t),v-\dot{x}(t)\rangle\le0 \quad\text{for every }v\in K(t).

Since K(t)K(t) is a cone, both 00 and 2x˙(t)2\dot{x}(t) belong to it. Substituting these two choices for vv implies

⟨∇Φ(x(t))−x˙(t),x˙(t)⟩=0.\langle\nabla\Phi(x(t))-\dot{x}(t),\dot{x}(t)\rangle=0.

By the chain rule, this yields ddtΦ(x(t))=∥x˙(t)∥22\frac{d}{dt}\Phi(x(t))=\lVert\dot{x}(t)\rVert_2^2 almost everywhere.

We next argue that LF(x(t))⊆K(t)\mathcal{L}_{F(x(t))}\subseteq K(t). Since x(t)x(t) lies in the relative interior of F(x(t))F(x(t)), for every u∈LF(x(t))u\in\mathcal{L}_{F(x(t))}, the points x(t)±ϵux(t)\pm\epsilon u belong to this face for sufficiently small ϵ>0\epsilon>0. Thus, ±u∈TX(x(t))\pm u\in T_X(x(t)). Moreover, since y(t)−x(t)∈NX(x(t))y(t)-x(t)\in N_X(x(t)), it follows that ⟨y(t)−x(t),u⟩=0\langle y(t)-x(t),u\rangle=0, so both uu and −u-u belong to K(t)K(t). Substituting v=uv=u and v=−uv=-u into the first-order optimality condition,

⟨∇Φ(x(t))−x˙(t),u⟩≤0,−⟨∇Φ(x(t))−x˙(t),u⟩≤0.\langle\nabla\Phi(x(t))-\dot{x}(t),u\rangle\le0,\qquad-\langle\nabla\Phi(x(t))-\dot{x}(t),u\rangle\le0.

Therefore, ∇Φ(x(t))−x˙(t)\nabla\Phi(x(t))-\dot{x}(t) is orthogonal to every vector in LF(x(t))\mathcal{L}_{F(x(t))}. Thus,

∇F(x(t))Φ(x(t))=ΠLF(x(t))(∇Φ(x(t)))=ΠLF(x(t))(x˙(t)).\nabla_{F(x(t))}\Phi(x(t))=\Pi_{\mathcal{L}_{F(x(t))}}(\nabla\Phi(x(t)))=\Pi_{\mathcal{L}_{F(x(t))}}(\dot{x}(t)).

We conclude that ∥x˙(t)∥2≥∥ΠLF(x(t))(x˙(t))∥2=∥∇F(x(t))Φ(x(t))∥2\lVert\dot{x}(t)\rVert_2\ge\lVert\Pi_{\mathcal{L}_{F(x(t))}}(\dot{x}(t))\rVert_2=\lVert\nabla_{F(x(t))}\Phi(x(t))\rVert_2. □

Analyticity enters through the Łojasiewicz gradient inequality [1] (Łojasiewicz 1984). Its local form states that, near a critical point pp of a real analytic function ff, there are parameters c>0c>0 and θ∈[1/2,1)\theta\in[1/2,1) such that ∥∇f(x)∥2≥c∣f(x)−f(p)∣θ\lVert\nabla f(x)\rVert_2\ge c\lvert f(x)-f(p)\rvert^\theta. Using this crucial property, we obtain the following.

Lemma B.3. For every ℓ∈R\ell\in\mathbb{R}, there exist c>0c>0, η∈(0,1]\eta\in(0,1], and θ∈[1/2,1)\theta\in[1/2,1) such that, for every nonempty face FF and every x∈Fx\in F with 0<∣Φ(x)−ℓ∣<η0<\lvert\Phi(x)-\ell\rvert<\eta,

∥∇FΦ(x)∥2≥c∣Φ(x)−ℓ∣θ.\lVert\nabla_F\Phi(x)\rVert_2\ge c\lvert\Phi(x)-\ell\rvert^\theta.

Proof. For a nonempty face FF, we consider the compact level set SF:={p∈F:Φ(p)=ℓ}S_F:=\{p\in F:\Phi(p)=\ell\}. If SFS_F is empty, we can set cF=1c_F=1, θF=1/2\theta_F=1/2, and ηF=min⁡{1,12min⁡x∈F∣Φ(x)−ℓ∣}>0\eta_F=\min\{1,\frac{1}{2}\min_{x\in F}\lvert\Phi(x)-\ell\rvert\}>0; the assertion is then vacuous. If FF is a vertex and SFS_F is nonempty, we can take (cF,ηF,θF)=(1,1,1/2)(c_F,\eta_F,\theta_F)=(1,1,1/2), again giving a vacuous assertion. Otherwise, we first establish gradient bounds near each point of SFS_F, and then show that these bounds cover all points of FF whose potential value is sufficiently close to ℓ\ell.

At each p∈SFp\in S_F that is a critical point of the restriction of Φ\Phi to the affine hull of FF, the Łojasiewicz gradient inequality gives ∥∇FΦ(x)∥2≥cp∣Φ(x)−Φ(p)∣θp=cp∣Φ(x)−ℓ∣θp\lVert\nabla_F\Phi(x)\rVert_2\ge c_p\lvert\Phi(x)-\Phi(p)\rvert^{\theta_p}=c_p\lvert\Phi(x)-\ell\rvert^{\theta_p} on a relatively open neighborhood of pp, with cp>0c_p>0 and θp∈[1/2,1)\theta_p\in[1/2,1). At each noncritical point p∈SFp\in S_F, continuity gives a relatively open neighborhood on which ∥∇FΦ∥2≥cp>0\lVert\nabla_F\Phi\rVert_2\ge c_p>0. Shrinking this neighborhood so that ∣Φ−ℓ∣<1\lvert\Phi-\ell\rvert<1 yields the same inequality with θp=1/2\theta_p=1/2. By compactness, finitely many of these neighborhoods cover SFS_F. Let cFc_F be the minimum among {cp}\{c_p\} and θF\theta_F the maximum among {θp}\{\theta_p\}. We have ∥∇FΦ(x)∥2≥cF∣Φ(x)−ℓ∣θF\|\nabla_F\Phi(x)\|_2 \ge c_F|\Phi(x)-\ell|^{\theta_F} throughout their union whenever 0<∣Φ(x)−ℓ∣<10<|\Phi(x)-\ell|<1. By compactness, we can choose ηF∈(0,1]\eta_F\in(0,1] so that every x∈Fx\in F with ∣Φ(x)−ℓ∣<ηF|\Phi(x)-\ell|<\eta_F belongs to one of the chosen neighborhoods. This proves the desired bound on FF. Finally, since X\mathcal{X} has finitely many nonempty faces, we may take c:=min⁡FcF>0c:=\min_F c_F>0, η:=min⁡FηF>0\eta:=\min_F\eta_F>0, and θ:=max⁡FθF∈[1/2,1)\theta:=\max_F\theta_F\in[1/2,1), which give the asserted inequality simultaneously on every nonempty face.

Proof of Theorem 5.1. By Lemma B.2 and compactness, Φ(x(t))↑ℓ\Phi(x(t))\mathrel{\uparrow}\ell for some ℓ∈R\ell\in\mathbb{R}. We set E(t):=ℓ−Φ(x(t))E(t):=\ell-\Phi(x(t)), so E˙(t)=−∥x˙(t)∥22\dot{E}(t)=-\|\dot{x}(t)\|_2^2 almost everywhere. For all sufficiently large tt, Lemmas B.2 and B.3 give

∥x˙(t)∥2≥cE(t)θ\|\dot{x}(t)\|_2\ge cE(t)^\theta

almost everywhere whenever E(t)>0E(t)>0. Thus,

−ddtE(t)1−θ=(1−θ)E(t)−θ∥x˙(t)∥22≥c(1−θ)∥x˙(t)∥2.-\frac{d}{dt}E(t)^{1-\theta}=(1-\theta)E(t)^{-\theta}\|\dot{x}(t)\|_2^2\ge c(1-\theta)\|\dot{x}(t)\|_2.

Integrating bounds the remaining path length of x(t)x(t) by E(t)1−θ/(c(1−θ))E(t)^{1-\theta}/(c(1-\theta)). If E(t)E(t) reaches zero, it follows that x(t)x(t) will be constant thereafter, and the same bound follows by integration up to that time. Since x(t)x(t) is Lipschitz, we conclude that its total length is finite. It therefore converges to some x⋆∈Xx^\star\in\mathcal{X}, with

∥x(t)−x⋆∥2≤∫t∞∥x˙(τ)∥2 dτ≤E(t)1−θc(1−θ).\|x(t)-x^\star\|_2\le\int_t^\infty\|\dot{x}(\tau)\|_2\,d\tau\le\frac{E(t)^{1-\theta}}{c(1-\theta)}.

for all sufficiently large tt. Finally, to establish stationarity, we use continuity of ∇Φ\nabla\Phi to obtain

y(t)t=y0t+1t∫0t∇Φ(x(τ)) dτ⟶∇Φ(x⋆).\frac{y(t)}{t}=\frac{y_0}{t}+\frac{1}{t}\int_0^t\nabla\Phi(x(\tau))\,d\tau\longrightarrow\nabla\Phi(x^\star).

Taking the limit yields ⟨∇Φ(x⋆),x′−x⋆⟩≤0\langle\nabla\Phi(x^\star),x'-x^\star\rangle\le0 for every x′∈Xx'\in\mathcal{X}. Thus, KKTGap⁡(x⋆)=0\operatorname{KKTGap}(x^\star)=0.

In particular, Theorem 5.1 applies to compact boxes, so our nonconvergent construction cannot be made analytic while retaining Euclidean regularization. It also establishes convergence for finite potential games.

Corollary 5.2. In every finite potential game, continuous-time FTRL with Euclidean regularization and arbitrary initialization converges to a Nash equilibrium.

References

  1. [1]Pierre-Antoine Absil, Robert Mahony, and Ben Andrews. Convergence of the iterates of descent methods for analytic cost functions. SIAM Journal on Optimization, 16(2):531–547, 2005.DOI
  2. [2]Ioannis Anagnostides, Ioannis Panageas, Nikolas Patris, and Tuomas Sandholm. (Doubly) exponential lower bounds for follow the regularized leader in potential games. In International Conference on Machine Learning (ICML), 2026a.
  3. [3]Ioannis Anagnostides, Emanuel Tewolde, Brian Hu Zhang, Ioannis Panageas, Vincent Conitzer, and Tuomas Sandholm. Convergence of regret matching in potential games and constrained optimization. In International Conference on Learning Representations (ICLR), 2026b.arxiv.org/abs/2510.17067
  4. [4]Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: a meta-algorithm and applications. Theory of Computing, 8(1):121–164, 2012.
  5. [5]Yakov Babichenko and Aviad Rubinstein. Communication complexity of Nash equilibrium in potential games. In Proceedings of the Annual Symposium on Foundations of Computer Science (FOCS), 2020.arxiv.org/abs/2011.06660
  6. [6]Yakov Babichenko and Aviad Rubinstein. Settling the complexity of Nash equilibrium in congestion games. In Proceedings of the Annual Symposium on Theory of Computing (STOC), 2021.arxiv.org/abs/2012.04327
  7. [7]Jakub Bielawski, Thiparat Chotibut, Fryderyk Falniowski, Grzegorz Kosiorowski, Michal Misiurewicz, and Georgios Piliouras. Follow-the-regularized-leader routes to chaos in routing games. In International Conference on Machine Learning (ICML), 2021.arxiv.org/abs/2102.07974
  8. [8]Avrim Blum, MohammadTaghi Hajiaghayi, Katrina Ligett, and Aaron Roth. Regret minimization and the price of total anarchy. In Proceedings of the Annual Symposium on Theory of Computing (STOC), 2008.DOI
  9. [9]Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
  10. [10]Noam Brown and Tuomas Sandholm. Superhuman AI for heads-up no-limit poker: Libratus beats top professionals. Science, 359(6374):418–424, 2018.DOI
  11. [11]Noam Brown and Tuomas Sandholm. Superhuman AI for multiplayer poker. Science, 365 (6456):885–890, 2019.DOI
  12. [12]Yang Cai, Gabriele Farina, Julien Grand-Clément, Christian Kroer, Chung-Wei Lee, Haipeng Luo, and Weiqiang Zheng. Fast last-iterate convergence of learning in games requires forgetful algorithms. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), 2024.arxiv.org/abs/2406.10631
  13. [13]Ozan Candogan, Asuman E. Ozdaglar, and Pablo A. Parrilo. Dynamics in near-potential games. Games Econ. Behav., 82:66–90, 2013.
  14. [14]Constantinos Daskalakis and Christos Papadimitriou. Continuous local search. In Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2011.
  15. [15]Constantinos Daskalakis, Rafael M. Frongillo, Christos H. Papadimitriou, George Pierrakos, and Gregory Valiant. On learning algorithms for Nash equilibria. In International Symposium on Algorithmic Game Theory (SAGT), 2010.
  16. [16]Francisco Facchinei and Jong-Shi Pang. Finite-dimensional variational inequalities and complementarity problems. Springer, 2003.
  17. [17]Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Faster game solving via predictive blackwell approachability: Connecting regret matching and mirror descent. In Conference on Artificial Intelligence (AAAI), 2021.arxiv.org/abs/2007.14358
  18. [18]John Fearnley, Paul Goldberg, Alexandros Hollender, and Rahul Savani. The complexity of gradient descent: CLS = PPAD ∩ PLS. JACM, 70(1):1–74, 2022.
  19. [19]Sergiu Hart and Andreu Mas-Colell. Regret-based continuous-time dynamics. Games and Economic Behavior, 45(2):375–394, 2003.
  20. [20]Elad Hazan. Introduction to online convex optimization. Foundations and Trends in Optimization, 2(3-4):157–325, 2016.
  21. [21]Amélie Héliou, Johanne Cohen, and Panayotis Mertikopoulos. Learning with bandit feedback in potential games. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), 2017.
  22. [22]Adam Kalai and Santosh Vempala. Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 71:291–307, 2005.
  23. [23]Serafina Kamp, Reese Liebman, and Benjamin Fish. Last-iterate convergence of no-regret learning for equilibria in bargaining games. arXiv:2507.03150, 2025.arxiv.org/abs/2507.03150
  24. [24]Robert Kleinberg, Georgios Piliouras, and Éva Tardos. Multiplicative updates outperform generic no-regret learning in congestion games: extended abstract. In Proceedings of the Annual Symposium on Theory of Computing (STOC), 2009.DOI
  25. [25]Nick Littlestone and M. K. Warmuth. The weighted majority algorithm. Information and Computation, 108(2):212–261, 1994.
  26. [27]Chinmay Maheshwari, Manxi Wu, Druv Pai, and Shankar Sastry. Independent and decentralized learning in Markov potential games. IEEE Transactions on Automatic Control, 2025.arxiv.org/abs/2205.14590
  27. [28]Jason R. Marden, Gürdal Arslan, and Jeff S. Shamma. Regret based dynamics: convergence in weakly acyclic games. In Autonomous Agents and Multi-Agent Systems, 2007.
  28. [29]H. Brendan McMahan. Follow-the-regularized-leader and mirror descent: Equivalence theorems and L1 regularization. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2011.
  29. [30]H. Brendan McMahan, Gary Holt, David Sculley, Michael Young, Dietmar Ebner, Julian Grady, Lan Nie, Todd Phillips, Eugene Davydov, Daniel Golovin, Sharat Chikkerur, Dan Liu, Martin Wattenberg, Arnar Mar Hrafnkelsson, Tom Boulos, and Jeremy Kubica. Ad click prediction: a view from the trenches. In Conference on Knowledge Discovery and Data Mining (KDD), 2013.
  30. [31]Panayotis Mertikopoulos, Christos H. Papadimitriou, and Georgios Piliouras. Cycles in adversarial regularized learning. In Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2018.arxiv.org/abs/1709.02738
  31. [32]Dov Monderer and Lloyd S. Shapley. Potential games. Games and Economic Behavior, 14(1):124–143, 1996.DOI
  32. [33]Matej Moravčík, Martin Schmid, Neil Burch, Viliam Lisý, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, and Michael Bowling. Deepstack: Expert-level artificial intelligence in heads-up no-limit poker. Science, 356(6337):508–513, 2017.DOI
  33. [34]H. Moulin and J.-P. Vial. Strategically zero-sum games: The class of games whose completely mixed equilibria cannot be improved upon. International Journal of Game Theory, 7(3-4): 201–221, 1978.DOI
  34. [35]John Nash. Equilibrium points in n-person games. Proceedings of the National Academy of Sciences, 36:48–49, 1950.
  35. [36]Arkadij Semenovič Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. 1983.
  36. [37]Yurii Nesterov. Introductory Lectures on Convex Optimization: A Basic Course. Kluwer Academic Publishers, 2004.
  37. [38]Francesco Orabona. Last-iterate convergence of optimistic multiplicative weight update. arXiv:2606.11773, 2026.arxiv.org/abs/2606.11773
  38. [39]Gerasimos Palaiopanos, Ioannis Panageas, and Georgios Piliouras. Multiplicative weights update with constant step-size in congestion games: Convergence, limit cycles and chaos. In Proceedings of the Annual Conference on Neural Information Processing Systems (NIPS), 2017.arxiv.org/abs/1703.01138
  39. [40]J Jr Palis and Wellington De Melo. Geometric theory of dynamical systems: an introduction. Springer Science & Business Media, 2012.
  40. [41]Ioannis Panageas, Nikolas Patris, Stratis Skoulakis, and Volkan Cevher. Exponential lower bounds for fictitious play in potential games. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), 2023.arxiv.org/abs/2310.02387
  41. [42]Julia Robinson. An iterative method of solving a game. Annals of Mathematics, 54:296–301, 1951.
  42. [43]Robert W Rosenthal. A class of games possessing pure-strategy Nash equilibria. International journal of game theory, 2(1):65–67, 1973.DOI
  43. [44]Shai Shalev-Shwartz. Online learning and online convex optimization. Foundations and Trends in Machine Learning, 4, 2012.
  44. [45]Alexander Shapiro. Differentiability properties of metric projections onto convex sets. Journal of Optimization Theory and Applications, 169(3):953–964, 2016.DOI
  45. [46]Samuel Sokota, Eugene Vinitsky, Hengyuan Hu, Zhiyuan Fan, J. Zico Kolter, and Gabriele Farina. Scalable decision-making for games of imperfect information. Nature, 658:55–59, 2026.
  46. [47]Emmanouil-Vasileios Vlatakis-Gkaragkounis, Lampros Flokas, Thanasis Lianeas, Panayotis Mertikopoulos, and Georgios Piliouras. No-regret learning and mixed nash equilibria: They do not mix. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), 2020.
  47. [48]Lin Xiao. Dual averaging methods for regularized stochastic learning and online optimization. Journal of Machine Learning Research, 11(Oct):2543–2596, 2010.
  48. [49]Brian Hu Zhang and Tuomas Sandholm. General search techniques without common knowledge for imperfect-information games, and applications to superhuman fog of war chess. In International Conference on Learning Representations (ICLR), 2026.
  49. [50]Itai Zilberstein, Pranav Rajbhandari, Steve Chien, and Tuomas Sandholm. Distributed constraint optimization via online learning and iterative pricing with application to large-scale satellite scheduling. arXiv:2607.25835, 2026.arxiv.org/abs/2607.25835

Paper details

vlnc:W_ffwwqf2j
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 7

downloads · 3

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

GPT (multiple versions)

View statement
Looking for related papers…
Contents