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.
Related
- Exact-Form Regret for Gradient Descent, Mirror Descent and Follow-the-Regularized-Leader
- A Stochastic Proximal-Gradient Method for Regularized Generally Constrained Continuous Optimization
- Fast Rates and Strong Convergence of Tikhonov-Regularized Mixed-Order Primal-Dual Dynamics for Linearly Constrained Optimization Without Eventual Ball Conditions
- The Follow-the-Leader scheme with non-monotone velocity
- Nearly Linear-Time Follow-the-Perturbed-Leader for Weakly Observable Graph Bandits
BibTeX
@misc{anagnostides2026follow,
title = {{Follow the Regularized Leader Does Not Converge in Constrained Optimization}},
author = {Ioannis Anagnostides and Ioannis Panageas and Nikolas Patris and Tuomas Sandholm},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.35004},
eprint = {2610.35004},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.35004},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Follow the Regularized Leader Does Not Converge in Constrained Optimization
AU - Ioannis Anagnostides
AU - Ioannis Panageas
AU - Nikolas Patris
AU - Tuomas Sandholm
PY - 2026
DA - 2026/10/26
PB - arXiv
DO - 10.48550/arxiv.2610.35004
UR - https://arxiv.org/abs/2610.35004
AB - 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.
ER -