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 , where 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 on a convex and compact domain such that for any time , the KKT gap of FTRL with Euclidean regularization on 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 (Lemma 3.1), thereby approaching the limit set . 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).

Figure 1. Schematic illustration of the trajectory of FTRL on the curve . The color indicates the gradient observed on the axis, which is perpendicular to the page. Our argument shows that FTRL never acts upon the positive gradient on the 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 plane, where the potential function is essentially flat when approaches 1. At the same time, after a short transient phase, there will always be a direction perpendicular to the 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 and 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 , 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 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 plane—we incorporate an additional term in the objective value that induces large negative gradients in the beginning of the trajectory, but vanishes as .
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 be a convex and compact subset of a Euclidean space, and let be a function to be maximized. will generally be nonconcave, making global optimization intractable. Instead, the main goal will be to compute a first-order stationary point of , in a sense formally specified below (Definition 2.1). is assumed to be smooth, meaning that there exists a parameter such that for any . In fact, as we shall see, our lower bound applies even when , which is to say that the th derivatives of are continuous for any .
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 defined on a convex and compact domain , the KKT gap of a point is defined as
An equivalent definition is in terms of the fixed-point gap of the gradient ascent operator , where denotes the Euclidean projection [16].
We will be interested in the case where the constraint set can be decomposed as the Cartesian product . In that case, the KKT gap per (1) of a point can be equivalently expressed as . In particular, the KKT gap will be large if there is a considerable first-order deviation benefit for at least a single component ; 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 -player potential games, can be decomposed as a Cartesian product of probability simplices, and 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
where is the differentiable objective function; in particular, if , (2) prescribes initializing at . Equivalently, (2) can be expressed as
With an arbitrary initialization , the update is . Unless stated otherwise, we assume zero initialization.
A key property of continuous-time FTRL is that it can never decrease the value of . In other words, as one would expect, 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 , the objective value is nondecreasing, and for almost every ,
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
where denotes the tangent cone of at . When the maximum in (2) is consistently attained in the interior of , 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 (by the chain rule and standard properties of the tangent cone projection). Integrating yields since is bounded. Importantly, the norm of the velocity under (constrained) gradient flow satisfies 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 while perpetually oscillating in the -coordinate. For , we set
Here, measures the proximity to the boundary , is the total phase of the oscillation, and is the signed deviation from the oscillatory curve . The goal is to construct a potential whose gradient flow maintains the invariance . To this end, we let
and we define by
At the boundary , we define by the limit of the right-hand side of (4), which is . 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 and , and set for ; this extension is by the same argument. The role of the linear term in (4) is to make the oscillatory curve forward invariant under the gradient flow. As we shall show, along this curve, the dynamics reduce to the scalar differential equation , so increases monotonically and the trajectory moves through successive oscillations while approaching the boundary .
In the remainder of this section, we first formalize that the oscillatory curve 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 . Then is forward invariant under the gradient flow on .
We state two immediate corollaries stemming from Lemma 3.1.
Corollary 3.2. If gradient flow is initialized at , then for all . Moreover, , so is strictly increasing.
Corollary 3.3 (Limit sets). If gradient flow is initialized on , then and . Moreover, the -limit set reads .
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 . During the th oscillation, with , we write
In words, represents the local phase, while is the absolute phase. For , we let
Here, is the window length and is the shift between consecutive windows, so adjacent windows overlap by . Furthermore, for , we define the non-wrapping windows . The final window crosses , and is written as , where the wrapping is understood modulo , so both pieces lie within the same oscillation. Figure 2 contains a visualization of the phase windows.

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 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 -coordinate rather than phase windows. To this end, for each phase window , , we define the associated -level set by
which is the corresponding interval in the -coordinate. Then, during the th oscillation, we let denote the amount of time for which , and let denote the amount of time for which .
Lemma 3.4 (Dwell-time bounds in terms of -level sets). Suppose that the gradient flow is initialized on the invariant curve . Then, for every , , and ,
For the construction in § 4, the time spent in bounds the time during which the corresponding auxiliary gradient is positive; throughout the complementary time , this gradient is strictly negative. When is large, (5) shows that 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 are the original variables of gradient flow, while the remaining coordinates serve an auxiliary role. The key invariance we will establish is that for any and , so FTRL in this higher-dimensional space will remain trapped in the plane, mimicking the trajectory of gradient flow. In accordance with the dwell-time bounds of Lemma 3.4, we associate with the th -level interval. The constraint set is defined as the product of intervals , where and ; this guarantees that constrained gradient flow with respect to 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 determines the interval
In particular, for the wrapping window, we have . For each , write for its length. We introduce a corresponding trimmed interval , whose role will become clear shortly. If lies strictly inside , we remove one quarter of its length from each endpoint, so that
and hence . The only intervals that need separate treatment are the endpoint intervals, which come in two types: those reaching and those reaching . For , no interval reaches both endpoints because each phase window has length at most . For the endpoint intervals, we modify the construction slightly. At the endpoint or , 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 defined below is strictly positive at the corresponding endpoint , which is needed for a uniformly positive KKT gap. That is, if , we set , while if , we set ; in either case, .
We associate with the interval the quadratic term , so that the initial potential function per (4) in § 3 is now recast as
As a result, the gradient of (6) with respect to is precisely . We can now explain the role of the trimmed intervals: they allow us to explicitly bound the positive values of inside and obtain a uniform strictly negative upper bound on . 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 -trajectory since the added contribution to 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 , FTRL can be decomposed as for each coordinate (Corollary A.1). The first direct consequence of this decomposition is that maintaining the invariance reduces to showing that the observed cumulative gradient is nonpositive—the projection of any nonpositive number into is 0.
Claim 4.1. For , if for any , then .
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 and an index . We recall that is the length of . The quadratic function satisfies the following bounds. First, if contains neither endpoint nor , then
Hence, by concavity, whenever . For the endpoint intervals,
and concavity gives whenever . Let denote the time at which , so that and the th oscillation corresponds to . Since attains its global maximum at the midpoint of , the positive upper bounds above also hold throughout . We therefore use the corresponding positive bound over the time spent inside and the negative bound over the complementary time , obtaining
By Lemma 3.4, both bounds are negative for and , since and . 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 evolves as the (unconstrained) gradient flow executed on (4). If in (6), then for every and .
Initialization To complete the construction, we need to handle the initialization. To do so, we incorporate an additional term in (6), namely
where is a sufficiently large constant and for , while for ; this extension is . The role of the last term in (7) is this: when is large enough, each coordinate will observe a large negative gradient in the beginning (so it will remain at ), but as approaches that term will quickly vanish and become negligible. As before, this additional term will not affect the gradient observed by or as long as all auxiliary coordinates remain zero.
Choosing 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 . This leads to the following lemma, whose proof is given in Section A.
Lemma 4.3. Suppose that evolves as the (unconstrained) gradient flow executed on (4). If and is large enough, for any and .
For the remainder of the construction, we fix . Combining this lemma with Claim 4.1 shows that for any and . What remains to argue is that on the 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 and constraint set such that for each , is always in the interior of . For each coordinate , .
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 such that for every (Lemma A.5). We choose such that for all . For the final objective , an auxiliary coordinate then gives a KKT gap of at least . On , 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 . 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 be a nonempty compact polytope, and let be real analytic on an open neighborhood of . Continuous-time FTRL with Euclidean regularization has finite trajectory length, , and thereby converges to a point with .
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
where is the smallest face of containing and 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 (Lemma B.3). Namely, writing , where is the objective value in the limit, we obtain almost everywhere for some and , assuming is large enough and ; crucially, this holds even when the active face keeps changing. Combining it with the fact that almost everywhere and integrating implies finite length and thereby convergence to a KKT point .
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 , the objective value is nondecreasing, and for almost every ,
Proof. Let , so that and . Both trajectories are Lipschitz, and hence differentiable almost everywhere. Firm nonexpansiveness of the Euclidean projection implies
Dividing by and taking the limit yields
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 , then FTRL can be equivalently expressed as
Lemma A.2 (Smoothness of ). defined in (4) is up to the boundary .
Proof. For , the function is smooth. Indeed, it is obtained by composition, addition, multiplication, and division of smooth functions, and the denominator in , , is strictly positive. Thus, the only issue is smoothness at the boundary , which corresponds to .
To argue about this, we will use the standard fact that exponential decay dominates polynomial growth: for every , as . This implies that any expression of the form , where grows at most polynomially in , tends to zero as , since and are bounded. For the expressions appearing below, this decay persists under differentiation. Each expression is a finite sum of terms , with a polynomial and an integer. The operator preserves this form, so every derivative with respect to is still bounded by an exponentially decaying factor times a polynomial in , and therefore tends to zero.
We now apply this observation to the three terms in (4), which we recall here for completeness:
First, is flat at . That is, all of its -derivatives are of the form , where is a polynomial. Thus, all of them tend to zero as . Next, we consider the linear term . Since
and the denominator is bounded below by 1, the factor contains the exponentially decaying factor . Therefore , together with all of its derivatives with respect to , tends to zero as . Moreover, . Differentiating with respect to only produces polynomial powers of and bounded trigonometric factors. So, by the product rule, every -derivative of is a finite sum of terms of the form , where grows at most polynomially in . Thus, all such derivatives tend to zero as . Finally, we consider the quadratic term . The factor is flat at the boundary. Differentiating with respect to produces only polynomial powers of , powers of , and bounded trigonometric factors. Since smoothness is a local property in the -variable, we may restrict to a compact set; on such a set, is bounded. Therefore, every -derivative of also tends to zero as .
It remains to consider differentiation with respect to . Since depends at most quadratically on , these derivatives can be computed immediately and read as follows.
Now, each of these expressions, and each of their derivatives with respect to , tends to zero as by the preceding argument. Therefore, every mixed partial derivative has a continuous extension to , and its boundary value is zero. Thus, the extension defined by is up to the boundary
Lemma 3.1 (Forward invariance). Let . Then is forward invariant under the gradient flow on .
Proof. We work with the gradient-ascent dynamics , where
To prove that is forward invariant, it is enough to show that whenever . We first compute the two velocity components on . Since $\partial_{x_2}\delta=1,
on . For the -component, we use the fact that , , and thus
On , all terms in containing an explicit factor of vanish, so
Since and , we get
Substituting ,
By the definition of
we have . Therefore, we conclude that on . It remains to check that the tracking error is preserved. Differentiating along the flow gives
Combining with (8), we obtain
on . This is zero because . Thus, whenever , so is forward invariant, and along .
Corollary 3.3 (Limit sets). If gradient flow is initialized on , then and . Moreover, the -limit set reads .
Proof. By Corollary 3.2, if the trajectory is initialized on , then it remains on for all future times, and holds. Moreover, is bounded for , so cannot diverge in finite time. We now show that cannot converge to a finite value. Suppose, for the sake of contradiction, that . Since is increasing, this would mean that the trajectory approaches a finite point on the invariant curve. But is continuous and strictly positive at , by definition. Therefore, there exists such that, for all sufficiently large , . This is incompatible with the fact that converges to the finite value , thereby implying . Since , we immediately obtain . It remains to identify the accumulation set in the -coordinate. Since , the phase also tends to . Moreover, is continuous and strictly increasing because , so the phase passes through infinitely many full periods. Along the invariant curve, , so has every value in as an accumulation point.
In particular, let us fix any , and choose such that . Since is continuous, strictly increasing, and tends to , for every sufficiently large integer there is a time such that . Then, while . Therefore,
Since was arbitrary, every point of is an accumulation point. Conversely, every accumulation point must lie in , because and . Therefore, , as claimed.
Lemma 3.4 (Dwell-time bounds in terms of -level sets). Suppose that the gradient flow is initialized on the invariant curve . Then, for every , , and ,
Proof. By Corollary 3.2, the phase satisfies
Thus, we can compute dwell times by changing variables from time to phase. During the th oscillation, and , so the time density is
In particular, is the time spent while the local phase moves through the infinitesimal interval . On the invariant curve, during each oscillation. For each , we let
Since , this set is the union of and its reflection , interpreted modulo . The union has measure at most , including for wrapping windows and windows containing extrema. Thus,
Since , we have , so the formula for the density gives
As a result,
while
Using and , we obtain
This proves the claimed bound for every , with both dwell times measured during the same oscillation.
Lemma 4.3. Suppose that evolves as the (unconstrained) gradient flow executed on (4). If and is large enough, for any and .
Proof. Fix and . We set and let
denote the cumulative gradient of coordinate . Since along the trajectory, choosing
ensures that, on the first two oscillations,
because on this interval. In particular, for every . The bounds preceding Lemma 4.2, together with Lemma 3.4, imply that, for every ,
Moreover, the density formula (11) and give . Since the phase set corresponding to is the same in each oscillation, it follows that
Along the trajectory, can be positive only when , and is bounded above by . Thus, for any part of the th oscillation,
We now argue by induction. Suppose that and for all . Since the correction term is nonpositive and , the bound for the preceding complete oscillation gives
As a result, for ,
where the second inequality uses . The last inequality holds because implies . The base case holds on , so induction proves the claim for all . ∎
Lemma A.3 (Coverage and overlap of the trimmed intervals). For every , the trimmed intervals cover , and consecutive intervals overlap by at least
That is, with indices interpreted modulo ,
Proof. Since the phase windows cover one full period and along the invariant curve, the intervals cover . It remains to check that passing from to the trimmed intervals 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 and whose union lies on a monotone branch of :
Suppose first that is increasing on . Then
Using
for , the overlap length is
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 , and is at least . Therefore,
The case where is decreasing on is identical, with the order of the endpoints reversed. It remains to check the pairs near the extrema of . We treat the maximum ; the minimum is symmetric. Let . The phase windows whose -intervals contain are those with indices , , and . By the endpoint rule, these intervals are trimmed on the side away from and extended on the side beyond . Thus, is strictly inside each of the corresponding
-intervals, so these endpoint intervals overlap with one another. Their pairwise overlap has length at least , since .
We only need to check the overlap with the adjacent ordinary intervals. Consider the left adjacent pair and . Since , we have
Thus, the overlap length is at least
Using the identity
this becomes
The right adjacent pair around the maximum is handled by symmetry around . The minimum is handled in the same way by symmetry around . Finally, the wrapping pair is covered by the monotone-branch argument after identifying
with the interval . Its union with lies on a monotone branch of for . The other pair involving the wrapping window follows by reflection about phase zero. For , both overlaps involving the wrapping window have length .
Thus, every consecutive pair of trimmed intervals overlaps by at least . In particular, the intervals form an overlapping chain whose union contains both endpoints and . Therefore, they cover the trajectory’s -range:
The preceding lemma shows that the trimmed intervals cover the trajectory’s -range with positive overlaps. Each interval is paired with the auxiliary coordinate , for . In the augmented potential (6), this coordinate is coupled to the quadratic function
Thus, whenever lies in the interior of the interval , the coordinate receives a positive gradient: increasing from the boundary value is a feasible improving deviation. Outside , the quadratic is always nonpositive; in fact, for , 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 with a constant KKTGap. The point of Lemma A.3 is that such an index always exists. Indeed, the trimmed intervals cover the trajectory’s -range, and consecutive intervals overlap by at least . Thus, cannot pass from one interval to the next only through points where all adjacent quadratics vanish. Moreover, at the endpoints , 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 from (6).
Lemma A.4. Fix and . Suppose that the auxiliary coordinate is kept at the boundary value . If , then the coordinate-wise first-order gap of is strictly positive:
Proof. By construction,
Since , choosing any feasible gives
and the claim follows.
Lemma A.5 (Uniformly positive KKTGap). Fix , and suppose that the auxiliary coordinates are kept at for all . There is a constant such that, at every time ,
Proof. Since the trajectory always satisfies , it is enough to find one auxiliary coordinate whose quadratic gate is strictly positive. By Lemma A.3, the intervals cover , and consecutive intervals overlap by at least . Therefore, for every , there exists an index such that . For points in the interior of , this follows from the nontrivial overlap of consecutive trimmed intervals. At the endpoint values , it follows from our convention for the endpoint intervals.
We conclude that the continuous function is positive on the compact interval , so . Choosing for a maximizing index gives .
:::
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 be a nonempty compact polytope, and let be real analytic on an open neighborhood of . Continuous-time FTRL with Euclidean regularization has finite trajectory length, , and thereby converges to a point with .
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
for the normal cone and
for the tangent cone. For , a standard property of the Euclidean projection implies that the residual belongs to . The associated critical cone is , 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 , let and . Then, for every ,
Proof. Let and . Nonexpansiveness of the Euclidean projection implies , so every sequence admits a subsequence along which converges. Moreover, since . Given that and , we have
Thus,
so every limit point of as belongs to . Now, for any , polyhedrality ensures that for all sufficiently small : active linear constraints remain satisfied because belongs to the tangent cone, and inactive constraints have positive slack. Since ,
Expanding,
so since . Thus, every limit point minimizes distance to over , and the claim follows.
Throughout this section, the nonempty faces of include itself, as well as all its proper nonempty faces. For each such face , let , where . is the linear subspace of directions parallel to . We define , the gradient of restricted to the affine hull of . The relative interiors of the nonempty faces partition , so each lies in the relative interior of exactly one face, denoted by . Equivalently, is the smallest face of containing , in the sense that for every face of containing . In particular, whenever lies in the relative interior of .
Lemma B.2. Under the assumptions of Theorem 5.1, for almost every ,
Proof. The vector field is Lipschitz and bounded, so there is a unique solution , and the projected trajectory is Lipschitz. By Lemma B.1 and nonexpansiveness, for almost every ,
where . The first-order optimality condition yields
Since is a cone, both and belong to it. Substituting these two choices for implies
By the chain rule, this yields almost everywhere.
We next argue that . Since lies in the relative interior of , for every , the points belong to this face for sufficiently small . Thus, . Moreover, since , it follows that , so both and belong to . Substituting and into the first-order optimality condition,
Therefore, is orthogonal to every vector in . Thus,
We conclude that . □
Analyticity enters through the Łojasiewicz gradient inequality [1] (Łojasiewicz 1984). Its local form states that, near a critical point of a real analytic function , there are parameters and such that . Using this crucial property, we obtain the following.
Lemma B.3. For every , there exist , , and such that, for every nonempty face and every with ,
Proof. For a nonempty face , we consider the compact level set . If is empty, we can set , , and ; the assertion is then vacuous. If is a vertex and is nonempty, we can take , again giving a vacuous assertion. Otherwise, we first establish gradient bounds near each point of , and then show that these bounds cover all points of whose potential value is sufficiently close to .
At each that is a critical point of the restriction of to the affine hull of , the Łojasiewicz gradient inequality gives on a relatively open neighborhood of , with and . At each noncritical point , continuity gives a relatively open neighborhood on which . Shrinking this neighborhood so that yields the same inequality with . By compactness, finitely many of these neighborhoods cover . Let be the minimum among and the maximum among . We have throughout their union whenever . By compactness, we can choose so that every with belongs to one of the chosen neighborhoods. This proves the desired bound on . Finally, since has finitely many nonempty faces, we may take , , and , which give the asserted inequality simultaneously on every nonempty face.
Proof of Theorem 5.1. By Lemma B.2 and compactness, for some . We set , so almost everywhere. For all sufficiently large , Lemmas B.2 and B.3 give
almost everywhere whenever . Thus,
Integrating bounds the remaining path length of by . If reaches zero, it follows that will be constant thereafter, and the same bound follows by integration up to that time. Since is Lipschitz, we conclude that its total length is finite. It therefore converges to some , with
for all sufficiently large . Finally, to establish stationarity, we use continuity of to obtain
Taking the limit yields for every . Thus, .
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]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]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]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]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]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]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]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]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]Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
- [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]Noam Brown and Tuomas Sandholm. Superhuman AI for multiplayer poker. Science, 365 (6456):885–890, 2019.DOI
- [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]Ozan Candogan, Asuman E. Ozdaglar, and Pablo A. Parrilo. Dynamics in near-potential games. Games Econ. Behav., 82:66–90, 2013.
- [14]Constantinos Daskalakis and Christos Papadimitriou. Continuous local search. In Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2011.
- [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]Francisco Facchinei and Jong-Shi Pang. Finite-dimensional variational inequalities and complementarity problems. Springer, 2003.
- [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]John Fearnley, Paul Goldberg, Alexandros Hollender, and Rahul Savani. The complexity of gradient descent: CLS = PPAD ∩ PLS. JACM, 70(1):1–74, 2022.
- [19]Sergiu Hart and Andreu Mas-Colell. Regret-based continuous-time dynamics. Games and Economic Behavior, 45(2):375–394, 2003.
- [20]Elad Hazan. Introduction to online convex optimization. Foundations and Trends in Optimization, 2(3-4):157–325, 2016.
- [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]Adam Kalai and Santosh Vempala. Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 71:291–307, 2005.
- [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]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]Nick Littlestone and M. K. Warmuth. The weighted majority algorithm. Information and Computation, 108(2):212–261, 1994.
- [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
- [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.
- [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.
- [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.
- [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
- [32]Dov Monderer and Lloyd S. Shapley. Potential games. Games and Economic Behavior, 14(1):124–143, 1996.DOI
- [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
- [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
- [35]John Nash. Equilibrium points in n-person games. Proceedings of the National Academy of Sciences, 36:48–49, 1950.
- [36]Arkadij Semenovič Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. 1983.
- [37]Yurii Nesterov. Introductory Lectures on Convex Optimization: A Basic Course. Kluwer Academic Publishers, 2004.
- [38]Francesco Orabona. Last-iterate convergence of optimistic multiplicative weight update. arXiv:2606.11773, 2026.arxiv.org/abs/2606.11773
- [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
- [40]J Jr Palis and Wellington De Melo. Geometric theory of dynamical systems: an introduction. Springer Science & Business Media, 2012.
- [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
- [42]Julia Robinson. An iterative method of solving a game. Annals of Mathematics, 54:296–301, 1951.
- [43]Robert W Rosenthal. A class of games possessing pure-strategy Nash equilibria. International journal of game theory, 2(1):65–67, 1973.DOI
- [44]Shai Shalev-Shwartz. Online learning and online convex optimization. Foundations and Trends in Machine Learning, 4, 2012.
- [45]Alexander Shapiro. Differentiability properties of metric projections onto convex sets. Journal of Optimization Theory and Applications, 169(3):953–964, 2016.DOI
- [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.
- [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.
- [48]Lin Xiao. Dual averaging methods for regularized stochastic learning and online optimization. Journal of Machine Learning Research, 11(Oct):2543–2596, 2010.
- [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.
- [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