Revisiting Smoothed Online Learning: Competitive Ratio, Dynamic Regret with Switching Cost, and Best of Both Worlds

Lijun Zhang; Linzhe He; Wei Jiang; Shiyin Lu

cs.LGOct 17, 2026

Revisiting Smoothed Online Learning: Competitive Ratio, Dynamic Regret with Switching Cost, and Best of Both Worlds

Authors: Lijun Zhang, Linzhe He, Wei Jiang, Shiyin Lu

Organizations: State Key Laboratory of Novel Software Technology, Nanjing University, Nanjing 210023, China · School of Artificial Intelligence, Nanjing University, Nanjing 210023, China · School of Computer Science and Engineering, Nanjing University of Science and Technology, Nanjing 210094, China · Alibaba Group, Hangzhou 310052, China

Abstract

We revisit smoothed online learning and develop algorithms with improved competitive ratios, optimal dynamic regret with switching cost, and best-of-both-worlds guarantees. Surprisingly, minimizing the hitting cost alone is $\max(1,\frac{2}α)$ -competitive for $α$ -polyhedral functions under the $\ell_2$ -norm switching cost and $1+\frac{4}λ$ -competitive for $λ$ -quadratic growth functions under the squared $\ell_2$ -norm switching cost, significantly improving existing guarantees. The polyhedral bound is tight for this naive algorithm, and we establish a matching lower bound for $α\geq1$ . For convex $λ$ -quadratic growth hitting costs, minimizing a suitably weighted sum of hitting and squared $\ell_2$ -norm switching costs yields a competitive ratio of $1+\frac{2}{\sqrtλ}$ . For dynamic regret with the $\ell_2$ -norm switching cost, we develop Smoothed Ader (SAder), which achieves the optimal $O(\sqrt{T(1+P_T)})$ rate in the standard online convex optimization setting, where $P_T$ is the comparator's path-length. Its lookahead version removes the bounded-gradient assumption, and a matching lower bound establishes optimality in this setting. Finally, for convex hitting costs on a bounded convex domain, we develop UDNP to aggregate any two experts in the lookahead setting under both switching costs. Its additional cumulative cost is at most $O(1)$ relative to the first expert and $O(\sqrt{T\log T})$ relative to the second, yielding best-of-both-worlds guarantees without bounded gradients.

Figures & tables

Algorithm	Assumptions	Competitive Ratio
OBD ( Chen et al., 2018 )	$f_{t}(\cdot)$ is $\alpha$ -polyhedral	$\displaystyle 3+\frac{8}{\alpha}$
	$f_{t}(\cdot)$ is convex
	$\mathcal{X}$ is convex
The Naive Approach	$f_{t}(\cdot)$ is $\alpha$ -polyhedral	$\displaystyle 1+\frac{2}{\alpha}$
( Lin et al., 2020 , Lemma 1)
The Naive Approach		$\displaystyle\max\left(1,\frac{2}{\alpha}\right)$

Table 1: Competitive Ratios of OBD and Related Methods. All algorithms operate in the lookahead setting. The switching cost is the

\ell_{2}

-norm for the

\alpha

-polyhedral results and Constrained OBD, and the squared

\ell_{2}

-norm for all remaining results.

\mathbf{x}_{t+1}^{\eta}=\Pi_{\mathcal{X}}\big[\mathbf{x}_{t}^{\eta}-\eta\nabla f_{t}(\mathbf{x}_{t})\big]

Algorithm 2 SAder: Expert-algorithm

Competitive Analysis

Competitive analysis compares online decisions with an offline optimum to measure performance under worst-case inputs and imperfect information.

See all 17 papers

Sep 24, 2026

Dynamic Regret in Online Convex Optimization with Indicator Switching Costs

We study dynamic regret in online convex optimization with an indicator switching cost: a fixed penalty incurred whenever two consecutive decisions differ. This captures startup overheads such as server activation, model deployment, and cache updates, and on a bounded domain it recovers norm-based movement costs as a special case. Existing guarantees for indicator costs handle only static comparators. We show that a direct extension of these techniques to dynamic regret provably fails, motivating a different approach. We propose a meta-learning framework: a set of randomized lazy FTRL base learners restarted at dyadic time scales, aggregated by a movement-aware master that mixes their proposal densities and samples actions via maximal coupling of consecutive mixtures. The resulting algorithm satisfies, in expectation,

\mathcal{R}^{\mathbf{1}}_T \le \tilde{\mathcal{O}}(\min\{\sqrt{T(S_T{+}1)},T^{2/3}(P_T+1)^{1/3}\})

, where

\mathcal{R}^{\mathbf{1}}_T

is the dynamic regret plus the cumulative indicator switching cost,

S_T

counts comparator switches, and

P_T

is the comparator path length. The bound holds simultaneously for all sequences and requires no prior knowledge of

S_T

P_T

: it is minimax-optimal (up to logarithmic factors) for tracking piecewise-constant comparators, and also captures frequently moving comparators with small total path length.

Naram Mhaisen, George Iosifidis

Faculty of Electrical Engineering, Mathematics and Computer Science TU Delft, Netherlands

Online Convex Optimization Dynamic Regret Minimization

Ask PDF

Sep 17, 2026

From Switching to Dynamic Regret: A Simple Reduction via Unbiased Random Sequences

In non-stationary online learning, dynamic regret has attracted increasing attention as a measure of how well an online learner performs against a time-varying comparator sequence. Despite considerable advances, attaining optimal bounds for strongly convex and exp-concave losses often involves intricate analysis. In this paper, we present a simple framework that reduces dynamic regret minimization to switching regret minimization. As a result, we can derive dynamic regret bounds by using off-the-shelf algorithms with switching regret guarantees. The key idea of our reduction is to construct, for any comparator sequence, an auxiliary random sequence that is unbiased at each round, with the controlled variance and a manageable number of switches. Combining this construction with suitable surrogate losses, we can decompose dynamic regret into the expected switching regret against the random sequence and its controlled variance. Theoretically, for strongly convex and exp-concave losses, we establish the

\widetilde{O}(T^{1/3}P_T^{2/3})

dynamic regret bounds, where

T

denotes the time horizon and

P_T

denotes the path-length of the comparator sequence. Moreover, for general convex losses, the same reduction also recovers the

O(\sqrt{T(1+P_T)})

dynamic regret bound. Notably, all our findings match the minimax optimal results for these three types of losses, highlighting the versatility of our proposed framework.

Yibo Wang, Wenhao Yang, Sifan Yang +3

State Key Laboratory for Novel Software Technology, Nanjing University · School of Artificial Intelligence, Nanjing University · School of Software Technology, Zhejiang University

Online Convex Optimization Dynamic Regret Minimization Regret Minimization

Ask PDF

Jan 20, 2026

Small Gradient Norm Regret for Online Convex Optimization

This paper introduces a new problem-dependent regret measure for online convex optimization with smooth losses. The notion, which we call the

G^\star

regret, depends on the cumulative squared gradient norm evaluated at the decision in hindsight. We show that the

G^\star

regret strictly refines the existing

L^\star

(small loss) regret, and that it can be arbitrarily sharper when the losses have vanishing curvature around the hindsight decision. We establish upper and lower bounds on the

G^\star

regret and extend our results to dynamic regret and bandit settings. As a byproduct, we refine the existing convergence analysis of stochastic optimization algorithms in the interpolation regime. Some experiments validate our theoretical findings.

Wenzhi Gao, Chang He, Madeleine Udell

ICME, Stanford University · SIME, Shanghai University of Finance and Economics · Department of Management Science and Engineering, Stanford University

Online Convex Optimization Sequential Decision Making Regret Minimization

Ask PDF

Abstract

Competitive Analysis

Explore similar work

Dynamic Regret in Online Convex Optimization with Indicator Switching Costs

From Switching to Dynamic Regret: A Simple Reduction via Unbiased Random Sequences

Small Gradient Norm Regret for Online Convex Optimization