Dynamic Regret via Discounted-to-Dynamic Reduction with Applications to Curved Losses and Adam Optimizer

We study dynamic regret minimization in non-stationary online learning, with a primary focus on follow-the-regularized-leader (FTRL) methods. FTRL is important for curved losses and for understanding adaptive optimizers such as Adam, yet existing dynamic regret analyses are less explored for FTRL. To address this, we build on the discounted-to-dynamic reduction and present a modular way to obtain dynamic regret bounds of FTRL-related problems. Specifically, we focus on two representative curved losses: linear regression and logistic regression. Our method not only simplifies existing proofs for the optimal dynamic regret of online linear regression, but also yields new dynamic regret guarantees for online logistic regression. Beyond online convex optimization, we apply the reduction to analyze the Adam optimizers, obtaining optimal convergence rates in stochastic, non-convex, and non-smooth settings. The reduction also enables a more detailed treatment of Adam with two discount parameters $(\beta_1,\beta_2)$, leading to new results for both clipped and clip-free variants of Adam optimizers.

Online learning provides a general framework for sequential decision making: at each round, a learner selects a decision, observes an outcome, and incurs a loss. In non-stationary settings where the environment can change over time, a widely used performance measure is dynamic regret, which compares the learner's cumulative loss against a time-varying sequence of comparators. Follow the regularized leader (FTRL) is a fundamental framework in online learning that selects decisions by minimizing a global objective over all past experience; familiar methods such as ridge regression can be seen as special cases. Because FTRL accumulates all past information, it can better exploit the structure of the losses, making it especially effective for problems that require fine-grained analysis, such as online linear regression and logistic regression with curved losses. However, this reliance on the full history can slow adaptation in non-stationary environments. Meanwhile, a recent result reveals that the Adam optimizer, one of the most widely used methods for training neural networks, can be viewed as an instance of FTRL that optimizes a dynamic regret. Therefore, establishing general dynamic regret guarantees for FTRL is important for analyzing both regression problems and modern optimizers. To this end, we develop a modular discounted-to-dynamic analysis, cast at the level of untuned upper-bound templates, that keeps key terms explicit throughout the reduction and is reusable across different settings. We apply this analysis in two directions. For curved losses, it streamlines existing proofs for online linear regression and yields new dynamic regret guarantees for logistic regression. For Adam in stochastic, non-convex, and non-smooth settings, it establishes optimal convergence rates under more flexible choices of the two momentum parameters than prior theory required, for both clipped and clip-free variants.