Follow the regularized leader may fail to find solutions in constrained problems
Follow the Regularized Leader Does Not Converge in Constrained Optimization
Computer Science and Game Theory
Summary
The paper finds that a popular algorithm called Follow the Regularized Leader (FTRL), used to make decisions step-by-step, can sometimes get stuck and never settle on a good solution in tricky problems with constraints. This is surprising because the algorithm always seems to improve the goal over time, yet it doesn’t actually reach a proper stopping point. The authors show this happens even in very smooth problems and explain why by studying mathematical examples where the algorithm oscillates endlessly. They also show that if the problem is especially nice (analytic), then FTRL does settle down properly.
What this means in practice
- •For optimization software engineers: Avoid using continuous-time FTRL for constrained nonconvex problems where convergence is critical, due to its possible failure to reach optimality conditions.
- •For machine learning system builders: Prefer gradient-based methods or analytic function assumptions for constrained optimization tasks when needing guaranteed convergence to stationarity.
A theory result. No direct application yet.
Authors
Ioannis Anagnostides, Ioannis Panageas, Nikolas Patris, Tuomas Sandholm
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.