From Non-Convex to Strongly Convex: Curvature-Adaptive FTPL for Online Optimization

# Curvature-Adaptive FTPL for Online Optimization
Source: [https://arxiv.org/html/2606.02948](https://arxiv.org/html/2606.02948)
## From Non\-Convex to Strongly Convex: Curvature\-Adaptive FTPL for Online Optimization

Chirag PabbarajuStanford University\. Email:cpabbara@cs\.stanford\.edu\.Ambuj TewariUniversity of Michigan, Ann Arbor\. Email:tewaria@umich\.edu\.

###### Abstract

Curvature adaptivity is a classical theme in online optimization: for convex Lipschitz losses, adaptive methods interpolate between the optimalO​\(T\)O\(\\sqrt\{T\}\)regret for general convex losses andO​\(log⁡T\)O\(\\log T\)regret under strong convexity\. Recent work has shown that Follow\-the\-Perturbed\-Leader \(FTPL\) achieves optimalO​\(T\)O\(\\sqrt\{T\}\)regret even for online non\-convex Lipschitz losses, assuming access to an approximate offline\-optimization oracle, but these guarantees do not exploit curvature\. We show that FTPL can be made curvature\-adaptive in the non\-convex setting, without knowing in advance how curvature will accumulate over time\. Our algorithm replaces the fixed perturbation scale of standard FTPL with a time\-varying scale chosen using only past information\. We give a simple follow\-the\-leader tuning rule for this scale and show that it competes, up to constants, with the best choice in hindsight\. The resulting method achievesO​\(T\)O\(\\sqrt\{T\}\)regret for arbitrary non\-convex Lipschitz losses and improves as cumulative curvature grows; with sufficiently accurate oracle calls, it achievesO​\(log⁡T\)O\(\\log T\)regret when cumulative curvature grows linearly, which includes the classical strongly convex regime\. We complement these upper bounds with matching lower bounds for prescribed cumulative\-curvature sequences, already for one\-dimensional convex losses, showing that the tradeoff between worst\-case non\-convex regret and curvature\-driven fast rates is intrinsic\.

## 1Introduction

A central question in online optimization is how regret scales with the number of roundsTT\. Two classical results characterize this dependence: for convex and Lipschitz losses, the optimal regret isO​\(T\)O\(\\sqrt\{T\}\)\(Zinkevich,[2003](https://arxiv.org/html/2606.02948#bib.bib11)\), while for strongly convex and Lipschitz losses, it improves toO​\(log⁡T\)O\(\\log T\)\(Hazanet al\.,[2006](https://arxiv.org/html/2606.02948#bib.bib12)\)\. Both rates are known to be tight\(Abernethyet al\.,[2008](https://arxiv.org/html/2606.02948#bib.bib7)\)\.

A natural goal, therefore, is to design algorithms whose guarantees adapt to the curvature of the loss sequence\. In a seminal work,Bartlettet al\.\([2007](https://arxiv.org/html/2606.02948#bib.bib20)\)introduced adaptive gradient methods for online*convex*optimization whose regret seamlessly interpolates betweenO​\(T\)O\(\\sqrt\{T\}\)andO​\(log⁡T\)O\(\\log T\)depending on the cumulative strong convexity in the sequence\. These ideas have since influenced widely used methods such as Adagrad\(Duchiet al\.,[2011](https://arxiv.org/html/2606.02948#bib.bib9)\)and Adam\(Kingma and Ba,[2015](https://arxiv.org/html/2606.02948#bib.bib8)\)\. More recently,Suggala and Netrapalli \([2020](https://arxiv.org/html/2606.02948#bib.bib17)\)showed that the Follow\-the\-Perturbed\-Leader \(FTPL\) framework achievesO​\(T\)O\(\\sqrt\{T\}\)regret even for*non\-convex*Lipschitz losses, assuming access to an oracle that solves perturbed offline problems\.

These results naturally raise the following question:

> *Can FTPL be made adaptive to curvature, achievingO​\(T\)O\(\\sqrt\{T\}\)regret for general non\-convex Lipschitz losses while improving toO​\(log⁡T\)O\(\\log T\)when sufficient strong convexity is present?*

In this paper, we answer this question in the affirmative\. Our approach is based on introducing a time\-varying noise scale in the FTPL perturbations, chosen adaptively using only past information\. We first derive a general regret bound parameterized by this sequence of noise scales\. We then show that selecting these parameters can itself be cast as a meta online learning problem, for which a simple FTL approach achieves a constant competitive ratio\. The resulting algorithm achieves regret that interpolates betweenO​\(T\)O\(\\sqrt\{T\}\)andO​\(log⁡T\)O\(\\log T\), without prior knowledge of the curvature of the losses\. We further complement our upper bounds with matching lower bounds, showing that the bounds we meta\-optimize are intrinsic to the problem and not an artifact of our method\.

Beyond its theoretical interest, our setting is motivated by a broad class of problems where the learner encounters composite losses of the form

ft=gt\+rt,f\_\{t\}=g\_\{t\}\+r\_\{t\},wheregtg\_\{t\}is a data\-dependent term that may be non\-convex, andrtr\_\{t\}is a strongly convex regularizer\. Such composite structures are ubiquitous in modern machine learning and optimization\.

One prominent example arises in continual learning\(Kirkpatricket al\.,[2017](https://arxiv.org/html/2606.02948#bib.bib2)\), wheregtg\_\{t\}represents a task\-specific loss, typically non\-convex due to neural network parameterizations, andrtr\_\{t\}is a regularizer that*tethers the current iterate to previously learned models*, thereby mitigating catastrophic forgetting\. In contrast, in online robust regression\(Maronnaet al\.,[2019](https://arxiv.org/html/2606.02948#bib.bib1)\), even with a linear model, the lossgtg\_\{t\}can be non\-convex when using robust losses such as the Tukey biweight function, whilertr\_\{t\}is typically a strongly convex shrinkage term \(e\.g\.,ℓ2\\ell\_\{2\}regularization\) that*tethers the iterate to a fixed reference point*, such as the origin\.

In these settings, the effective curvature of the loss sequence depends on the interplay between the non\-convex data term and the accumulated regularization\. In favorable regimes, the regularizer dominates and the problem behaves like a strongly convex one; in adversarial regimes, the non\-convexity prevails\. Since this balance is typically unknown a priori, it is essential to design algorithms that automatically adapt, achievingO​\(T\)O\(\\sqrt\{T\}\)regret in the worst case while improving toO​\(log⁡T\)O\(\\log T\)whenever sufficient curvature emerges\.

Our key contributions are as follows\.

- •Curvature\-adaptive FTPL across non\-convex to strongly convex regimes\.We design an FTPL algorithm with a time\-varying perturbation scale that adapts to the curvature of the loss sequence, achieving regret that interpolates fromO​\(T\)O\(\\sqrt\{T\}\)for arbitrary non\-convex Lipschitz losses toO​\(log⁡T\)O\(\\log T\)when sufficient strong convexity is present\. To our knowledge, this is the first FTPL method that achieves such curvature adaptivity in the non\-convex regime, bridging the gap between prior adaptive methods for online convex optimization \(e\.g\.,\(Bartlettet al\.,[2007](https://arxiv.org/html/2606.02948#bib.bib20)\)\) and non\-convex but non\-adaptive FTPL guarantees \(e\.g\.,\(Suggala and Netrapalli,[2020](https://arxiv.org/html/2606.02948#bib.bib17)\)\)\.
- •Meta\-online tuning and optimality guarantees\.We derive a regret bound parameterized by the perturbation schedule and show that selecting this schedule can be cast as a meta online learning problem\. We give a simple constant\-competitive strategy for this problem, yielding near\-optimal tuning without prior knowledge of the loss sequence\. We also prove matching lower bounds, showing that the bounds we meta\-optimize are intrinsic to the problem\.
- •Empirical validation\.We empirically evaluate our method on representative problems with composite non\-convex and strongly convex structure, demonstrating improved performance over non\-adaptive FTPL and baseline methods in regimes with varying curvature\.

## 2Related Works

#### Oracles in Online Optimization\.

The FTPL algorithm\(Hannan,[1957](https://arxiv.org/html/2606.02948#bib.bib15); Kalai and Vempala,[2005](https://arxiv.org/html/2606.02948#bib.bib13)\)is especially attractive for efficient online learning over structured decision sets\. The main computational burden in FTPL at each round is solving a perturbed offline problem\. If the cost functions and perturbation are both linear, then the perturbed offline problem becomes an instance of the offline optimization problem itself\. However, for general decision sets, there is known to be an exponential \(in the ambient dimensiondd\) gap in the oracle complexities of online and statistical learning if the learner is only provided access to the offline optimization oracle\(Hazan and Koren,[2016](https://arxiv.org/html/2606.02948#bib.bib14)\)\. For decision classes with exponentially many experts in the ambient dimension, the lower bound ofHazan and Koren \([2016](https://arxiv.org/html/2606.02948#bib.bib14)\)implies that no algorithm using only a standard offline optimization oracle and polynomial additional computation can achieveO​\(poly​\(d\)​Tα\)O\(\\mathrm\{poly\}\(d\)T^\{\\alpha\}\)regret for anyα<1\\alpha<1\. It was therefore surprising whenAgarwalet al\.\([2019](https://arxiv.org/html/2606.02948#bib.bib16)\)showed that FTPL with linear perturbations, which makes one call per time step to a*linearly perturbed*offline optimization oracle, achievesO​\(poly​\(d\)​T2/3\)O\(\\mathrm\{poly\}\(d\)T^\{2/3\}\)cumulative regret against*non\-convex*Lipschitz functions on a bounded decision set\. TheO​\(poly​\(d\)​T2/3\)O\(\\mathrm\{poly\}\(d\)T^\{2/3\}\)rate was later improved toO​\(poly​\(d\)​T\)O\(\\mathrm\{poly\}\(d\)\\sqrt\{T\}\)bySuggala and Netrapalli \([2020](https://arxiv.org/html/2606.02948#bib.bib17)\)\.

#### Adaptive Step\-Sizes and Regularization\.

Online gradient algorithms with different step\-size schedules achieveO​\(T\)O\(\\sqrt\{T\}\)andO​\(log⁡T\)O\(\\log T\)regret against convex Lipschitz and strongly convex Lipschitz functions respectively\(Zinkevich,[2003](https://arxiv.org/html/2606.02948#bib.bib11); Hazanet al\.,[2006](https://arxiv.org/html/2606.02948#bib.bib12)\)\.Bartlettet al\.\([2007](https://arxiv.org/html/2606.02948#bib.bib20)\)designed a single adaptive algorithm that interpolates between these rates and automatically adapts to the actual amount of curvature present in the adversary’s*convex*functions\. Some related lower bounds can be found in the work ofAbernethyet al\.\([2008](https://arxiv.org/html/2606.02948#bib.bib7)\)\. Subsequent work developed a broader theory of adaptive regularization and adaptive first\-order methods, including AdaGrad\-style algorithms\(Duchiet al\.,[2011](https://arxiv.org/html/2606.02948#bib.bib9); McMahan and Streeter,[2010](https://arxiv.org/html/2606.02948#bib.bib5)\)and adaptive FTRL/mirror\-descent frameworks\(McMahan,[2017](https://arxiv.org/html/2606.02948#bib.bib10)\)\. These ideas later influenced practical optimization methods for deep learning such as Adam\(Kingma and Ba,[2015](https://arxiv.org/html/2606.02948#bib.bib8)\)\. While adaptive step\-size methods are also widely studied for stochastic non\-convex optimization\(Li and Orabona,[2019](https://arxiv.org/html/2606.02948#bib.bib4); Wardet al\.,[2020](https://arxiv.org/html/2606.02948#bib.bib3)\), their guarantees are typically formulated in terms of convergence to stationary points rather than regret minimization\. Also note that, as observed byAgarwalet al\.\([2019](https://arxiv.org/html/2606.02948#bib.bib16)\), standard FTRL\-style regularization does not necessarily stabilize the minimizers of non\-convex objectives, limiting the direct applicability of FTRL\-based approaches for provable regret guarantees in the non\-convex regime\.

#### Adaptive Perturbation\.

Adaptive variants of FTPL have previously been studied through adaptive learning\-rate schedules, data\-dependent perturbation magnitudes, and generalized FTPL frameworks for oracle\-efficient online learning\(Hutter and Poland,[2005](https://arxiv.org/html/2606.02948#bib.bib18); Wanget al\.,[2022](https://arxiv.org/html/2606.02948#bib.bib6)\)\. Existing works primarily focus on adapting to favorable data sequences, for example when the loss of the best expert is small or the adversary is stochastic, while retaining the classicalO​\(T\)O\(\\sqrt\{T\}\)dependence on the horizon\. In contrast, our goal is to adapt to curvature itself\. To the best of our knowledge, no prior online optimization algorithm, let alone one that is perturbation\-based for oracle\-efficiency, achieves a full interpolation between the optimalO​\(T\)O\(\\sqrt\{T\}\)regret for Lipschitz non\-convex losses and theO​\(log⁡T\)O\(\\log T\)regret achievable for strongly convex losses\.

#### Problem Setup\.

The setup comprises of an online game between anadversaryand alearnerthat proceeds in rounds\. At roundtt, the learner chooses somext∈𝒳x\_\{t\}\\in\\mathcal\{X\}, where𝒳\\mathcal\{X\}is a bounded space; simultaneously, the adversary picks a functionft:𝒳→ℝf\_\{t\}:\\mathcal\{X\}\\to\\mathds\{R\}\. Both the learner’s and adversary’s choices at roundttcan depend on the entire history of the game up until roundt−1t\-1\. Thereafter, the choices made by the learner and adversary are revealed to each other, and the learner suffers a lossft​\(xt\)f\_\{t\}\(x\_\{t\}\)\. The learner’s objective is to minimize theirregretat the end of the game; that is, the learner aims to minimize the cumulative loss they suffer at the end ofTTrounds, relative to the single bestx∈𝒳x\\in\\mathcal\{X\}they could have played at each round in hindsight\. Formally, define the regret of a sequence of movesx1:T:=x1,…,xTx\_\{1:T\}:=x\_\{1\},\\dots,x\_\{T\}with respect to a sequence of functionsf1:T:=f1,…,fTf\_\{1:T\}:=f\_\{1\},\\dots,f\_\{T\}as

RegretT​\(f1:T;x1:T\):=∑t=1Tft​\(xt\)−infx∈𝒳∑t=1Tft​\(x\)\.\\displaystyle\\mathrm\{Regret\}\_\{T\}\(f\_\{1:T\};x\_\{1:T\}\):=\\sum\_\{t=1\}^\{T\}f\_\{t\}\(x\_\{t\}\)\-\\inf\_\{x\\in\\mathcal\{X\}\}\\sum\_\{t=1\}^\{T\}f\_\{t\}\(x\)\.\(1\)We will assume that𝒳⊆ℝd\\mathcal\{X\}\\subseteq\\mathds\{R\}^\{d\}withℓ∞\\ell\_\{\\infty\}diameterD<∞D<\\infty\. We will also assume that the functionsftf\_\{t\}that the adversary can play are guaranteed to beLL\-Lipschitz with respect to theℓ1\\ell\_\{1\}norm\. That is, for everyx,y∈𝒳x,y\\in\\mathcal\{X\}, and for everytt,\|ft​\(x\)−ft​\(y\)\|≤L​‖x−y‖1\|f\_\{t\}\(x\)\-f\_\{t\}\(y\)\|\\leq L\\\|x\-y\\\|\_\{1\}\.

#### Curvature\.

We say that a functionf:𝒳→ℝf:\\mathcal\{X\}\\to\\mathds\{R\}has strong convexity constantμ\>0\\mu\>0\(with respect toℓ1\\ell\_\{1\}\) if for everyx,y∈𝒳x,y\\in\\mathcal\{X\}, it holds that

f​\(y\)≥f​\(x\)\+⟨∇f​\(x\),y−x⟩\+μ2​‖y−x‖12\.\\displaystyle f\(y\)\\geq f\(x\)\+\\langle\\nabla f\(x\),y\-x\\rangle\+\\frac\{\\mu\}\{2\}\\\|y\-x\\\|\_\{1\}^\{2\}\.\(2\)We use the convention thatμ=0\\mu=0if \([2](https://arxiv.org/html/2606.02948#S3.E2)\) above does not hold forfffor anyμ\>0\\mu\>0\.

#### Approximate Optimization Oracle\.

As inSuggala and Netrapalli \([2020](https://arxiv.org/html/2606.02948#bib.bib17)\), we assume that the learner has access to an “\(α,β\)\(\\alpha,\\beta\)\-approximate optimization oracle”\. Given a functionf:𝒳→ℝf:\\mathcal\{X\}\\to\\mathds\{R\}and a vectorσ∈ℝd\\sigma\\in\\mathds\{R\}^\{d\}, the oracle𝒪α,β​\(f,σ\)\\mathcal\{O\}\_\{\\alpha,\\beta\}\(f,\\sigma\)returnsx^∈𝒳\\hat\{x\}\\in\\mathcal\{X\}satisfying

f​\(x^\)−⟨σ,x^⟩≤infx∈𝒳\(f​\(x\)−⟨σ,x⟩\)\+\(α\+β​‖σ‖1\)\.\\displaystyle f\(\\hat\{x\}\)\-\\langle\\sigma,\\hat\{x\}\\rangle\\leq\\inf\_\{x\\in\\mathcal\{X\}\}\\left\(f\(x\)\-\\langle\\sigma,x\\rangle\\right\)\+\(\\alpha\+\\beta\\\|\\sigma\\\|\_\{1\}\)\.\(3\)
We can now state our main Adaptive FTPL algorithm, which takes as input the oracle𝒪α,β\\mathcal\{O\}\_\{\\alpha,\\beta\}, and a non\-decreasing scheduleρ1,ρ2,…\\rho\_\{1\},\\rho\_\{2\},\\dotsofnoise scalesto invoke the oracle with\.

Algorithm 1Adaptive Follow the Perturbed Leader \(AdaFTPL\)1:Input:Approximate optimization oracle

𝒪α,β\\mathcal\{O\}\_\{\\alpha,\\beta\}, non\-decreasing noise scale schedule

ρ1,ρ2​…,\\rho\_\{1\},\\rho\_\{2\}\\dots,
2:for

t=1​…​Tt=1\\dots Tdo

3:Generate random vector

σt\\sigma\_\{t\}such that

\{σt,j\}j=1d∼i\.i\.d\.Exp​\(1\)\\\{\\sigma\_\{t,j\}\\\}\_\{j=1\}^\{d\}\\stackrel\{\{\\scriptstyle\\mathrm\{i\.i\.d\.\}\}\}\{\{\\sim\}\}\\text\{Exp\}\(1\)111A random variableX∼Exp​\(η\)X\\sim\\mathrm\{Exp\}\(\\eta\)if for everys≥0s\\geq 0,Pr⁡\[X≥s\]=exp⁡\(−η​s\)\\operatorname\{\{Pr\}\}\[X\\geq s\]=\\exp\(\-\\eta s\)\.

4:Let

Ft−1=∑i=1t−1fiF\_\{t\-1\}=\\sum\_\{i=1\}^\{t\-1\}f\_\{i\}; predict

xtx\_\{t\}as

xt=𝒪α,β​\(Ft−1,ρt​σt\)x\_\{t\}=\\mathcal\{O\}\_\{\\alpha,\\beta\}\\left\(F\_\{t\-1\},\\,\\rho\_\{t\}\\sigma\_\{t\}\\right\)
5:Observe loss function

ftf\_\{t\}
6:endfor

We are now ready to state our main regret guarantee for Adaptive FTPL\. We note that throughout the paper, we will use the convention1/0=\+∞1/0=\+\\infty\.

###### Theorem 1\(Adaptive FTPL Regret\)\.

LetDDbe theℓ∞\\ell\_\{\\infty\}diameter of𝒳\\mathcal\{X\}, and suppose that the functionsf1,…,fTf\_\{1\},\\dots,f\_\{T\}encountered by Adaptive FTPL \([Algorithm1](https://arxiv.org/html/2606.02948#alg1)\) areLL\-Lipschitz with respect to theℓ1\\ell\_\{1\}norm\. Furthermore, letStS\_\{t\}be the strong convexity constant ofFt=∑i=1tfiF\_\{t\}=\\sum\_\{i=1\}^\{t\}f\_\{i\}\. Then, the algorithm has the following regret guarantee:

𝔼σ⁡\[RegretT​\(f1:T;x1:T\)\]≤\\displaystyle\\operatorname\{\{\\mathds\{E\}\}\}\_\{\\sigma\}\\left\[\\mathrm\{Regret\}\_\{T\}\(f\_\{1:T\};x\_\{1:T\}\)\\right\]\\leq∑t=1Tmin⁡\{125​L2​d2​Dρt\+α\+β​ρt​d20\+2​β​d​L,2​L2St\+2​L​2​\(α\+β​ρt​d\)St\}\\displaystyle\\sum\_\{t=1\}^\{T\}\\min\\left\\\{\\frac\{125L^\{2\}d^\{2\}D\}\{\\rho\_\{t\}\}\+\\frac\{\\alpha\+\\beta\\rho\_\{t\}d\}\{20\}\+2\\beta dL,\\frac\{2L^\{2\}\}\{S\_\{t\}\}\+2L\\sqrt\{\\frac\{2\(\\alpha\+\\beta\\rho\_\{t\}d\)\}\{S\_\{t\}\}\}\\right\\\}\+d​D​ρT\+α​T\+d​β​∑t=1Tρt\.\\displaystyle\\qquad\+dD\\rho\_\{T\}\+\\alpha T\+d\\beta\\sum\_\{t=1\}^\{T\}\\rho\_\{t\}\.\(4\)

We give the complete proof of[Theorem1](https://arxiv.org/html/2606.02948#Thmtheorem1)in[AppendixA](https://arxiv.org/html/2606.02948#A1), but provide a detailed sketch here\.

#### Proof Sketch\.

By a standard argument for FTPL \(e\.g\., see Lemma 12 inHutter and Poland \([2005](https://arxiv.org/html/2606.02948#bib.bib18)\), Chapter 4 inCesa\-Bianchi and Lugosi \([2006](https://arxiv.org/html/2606.02948#bib.bib19)\)\), it suffices to consider the setting where the functionsf1,…,fTf\_\{1\},\\dots,f\_\{T\}are specified upfront by anobliviousadversary, and show the regret bound for every fixedf1,…,fTf\_\{1\},\\dots,f\_\{T\}\. With obliviously specified functions, it furthermore suffices in[Algorithm1](https://arxiv.org/html/2606.02948#alg1)to simply draw a random vectorσ=\{σj\}j=1d∼i\.i\.d\.Exp​\(1\)\\sigma=\\\{\\sigma\_\{j\}\\\}\_\{j=1\}^\{d\}\\stackrel\{\{\\scriptstyle\\mathrm\{i\.i\.d\.\}\}\}\{\{\\sim\}\}\\text\{Exp\}\(1\)once at the start and reuse it at every time step, instead of drawing a freshσt\\sigma\_\{t\}at each step\. With these considerations, our goal is to upper bound the regret in the left\-hand side of \([1](https://arxiv.org/html/2606.02948#S3.Ex3)\) for fixedf1,…,fTf\_\{1\},\\dots,f\_\{T\}, where the expectation is only with respect toσ\\sigmadrawn at the start by the algorithm\.

The key object that enables the analysis is a “ghost” movex¯t\+1=𝒪α,β​\(Ft,ρt​σ\)\\bar\{x\}\_\{t\+1\}=\\mathcal\{O\}\_\{\\alpha,\\beta\}\(F\_\{t\},\\rho\_\{t\}\\sigma\)\. Note thatx¯t\+1\\bar\{x\}\_\{t\+1\}is separate fromxt=𝒪α,β​\(Ft−1,ρt​σ\)x\_\{t\}=\\mathcal\{O\}\_\{\\alpha,\\beta\}\(F\_\{t\-1\},\\,\\rho\_\{t\}\\sigma\)which the algorithm plays at timett,as well asxt\+1=𝒪α,β​\(Ft,ρt\+1​σ\)x\_\{t\+1\}=\\mathcal\{O\}\_\{\\alpha,\\beta\}\(F\_\{t\},\\,\\rho\_\{t\+1\}\\sigma\)which the algorithm plays at time stept\+1t\+1\. We introducex¯t\+1\\bar\{x\}\_\{t\+1\}solely for the sake of analysis, and for the reason that it uses a noise vector whose scalematchesthat of the noise vector used in theprevioustime step\. This will help us \(1\) establish a standard decomposition of the regret into astabilityandperturbationterm, and \(2\) directly utilize the bound on the stability term fromSuggala and Netrapalli \([2020](https://arxiv.org/html/2606.02948#bib.bib17)\)\.

Namely, we show that

𝔼σ⁡\[RegretT​\(f1:T;x1:T\)\]≤L​∑t=1T𝔼σ⁡\[‖xt−x¯t\+1‖1\]⏟stability\+dDρT\+αT\+dβ∑t=1Tρt\.⏟perturbation\\displaystyle\\operatorname\{\{\\mathds\{E\}\}\}\_\{\\sigma\}\\left\[\\mathrm\{Regret\}\_\{T\}\(f\_\{1:T\};x\_\{1:T\}\)\\right\]\\leq\\underbrace\{L\\sum\_\{t=1\}^\{T\}\\operatorname\{\{\\mathds\{E\}\}\}\_\{\\sigma\}\\left\[\\left\\\|x\_\{t\}\-\\bar\{x\}\_\{t\+1\}\\right\\\|\_\{1\}\\right\]\}\_\{\\text\{stability\}\}\+\\underbrace\{dD\\rho\_\{T\}\+\\alpha T\+d\\beta\\sum\_\{t=1\}^\{T\}\\rho\_\{t\}\.\}\_\{\\text\{perturbation\}\}\(5\)This decomposition follows a standard analysis once the ghost objectx¯t\+1\\bar\{x\}\_\{t\+1\}has been defined\. The stability term arises directly from Lipschitzness\. In order to bound the rest of the perturbation terms, we crucially observe thatx¯t\+1\\bar\{x\}\_\{t\+1\}is a move that the learner would haveliked to playat time steptt, but cannot do so, since it does not knowftf\_\{t\}\. Thus, we can employ a standard “be\-the\-leader” analysis forx¯t\+1\\bar\{x\}\_\{t\+1\}to bound the perturbation terms in the desired form\.

It then remains to bound the stability terms𝔼σ⁡\[‖xt−x¯t\+1‖1\]\\operatorname\{\{\\mathds\{E\}\}\}\_\{\\sigma\}\\left\[\\\|x\_\{t\}\-\\bar\{x\}\_\{t\+1\}\\\|\_\{1\}\\right\]\. We do this in two ways, allowing us to interpolate between non\-convexity and strong convexity\. First, we observe again that bothxtx\_\{t\}andx¯t\+1\\bar\{x\}\_\{t\+1\}use a noise vector having the same scaleρt\\rho\_\{t\}; the only difference is thatxtx\_\{t\}invokes the oracle withFt−1F\_\{t\-1\}, whereasx¯t\+1\\bar\{x\}\_\{t\+1\}invokes the oracle withFtF\_\{t\}\. But this means that we can directly use the analysis ofSuggala and Netrapalli \([2020](https://arxiv.org/html/2606.02948#bib.bib17)\)— in their setting, they upper\-bound𝔼σ⁡\[‖xt−xt\+1‖1\]\\operatorname\{\{\\mathds\{E\}\}\}\_\{\\sigma\}\\left\[\\\|x\_\{t\}\-x\_\{t\+1\}\\\|\_\{1\}\\right\]where bothxtx\_\{t\}andxt\+1x\_\{t\+1\}use the same noise vector; the same upper bound goes through for us, provided we replacext\+1x\_\{t\+1\}withx¯t\+1\\bar\{x\}\_\{t\+1\}\.

Second, we use a different upper bound on‖xt−x¯t\+1‖\\\|x\_\{t\}\-\\bar\{x\}\_\{t\+1\}\\\|arising from the analysis of follow\-the\-leader \(FTL\) for strongly convex online optimization\. Namely, if we assume that the strong convexity constant of the cumulative functionFtF\_\{t\}isStS\_\{t\}, then‖xt−x¯t\+1‖\\\|x\_\{t\}\-\\bar\{x\}\_\{t\+1\}\\\|can be upper\-bounded asO​\(L/St\)O\(L/S\_\{t\}\)\. This gives a different, curvature\-cognizant upper bound on the perturbation term\. This bound is vacuous whenFtF\_\{t\}is not strongly convex \(given that we are using the convention1/0=\+∞1/0=\+\\infty\), but it nevertheless always applies\.

Finally, given that we have two upper bounds for the stability term, both of which always hold, we can use theminimumof these two\. This gives us the final regret upper bound in[Theorem1](https://arxiv.org/html/2606.02948#Thmtheorem1)\. ∎

### 3\.1A meta\-online learning problem to chooseρt\\rho\_\{t\}

Observe that the regret bound in[Theorem1](https://arxiv.org/html/2606.02948#Thmtheorem1)holds for any non\-decreasingρ1,…,ρT\\rho\_\{1\},\\dots,\\rho\_\{T\}\. We now consider the problem of optimally choosing this sequence\. A natural way to do this is to optimize the upper bound that we obtain, as a function ofρ1,…,ρT\\rho\_\{1\},\\dots,\\rho\_\{T\}\.

Namely, for any horizonTT, and error parametersα,β\\alpha,\\beta, define theofflineoptimal value of the regret upper bound over all possible non\-decreasing noise scale schedulesρ1≤⋯≤ρT\\rho\_\{1\}\\leq\\dots\\leq\\rho\_\{T\}that are lower\-bounded byr≥0r\\geq 0\(i\.e\.,r≤ρ1r\\leq\\rho\_\{1\}\), as:

OPTTα,β​\(r\):=infr≤ρ1≤⋯≤ρT\\displaystyle\\mathrm\{OPT\}^\{\\alpha,\\beta\}\_\{T\}\(r\):=\\inf\_\{r\\leq\\rho\_\{1\}\\leq\\dots\\leq\\rho\_\{T\}\}\[∑t=1Tmin\{125​L2​d2​Dρt\+β​ρt​d20\+2Lβd\+α20,2​L2St\+2L2​\(α\+β​ρt​d\)St\}\\displaystyle\\left\[\\sum\_\{t=1\}^\{T\}\\min\\left\\\{\\frac\{125L^\{2\}d^\{2\}D\}\{\\rho\_\{t\}\}\+\\frac\{\\beta\\rho\_\{t\}d\}\{20\}\+2L\\beta d\+\\frac\{\\alpha\}\{20\},\\frac\{2L^\{2\}\}\{S\_\{t\}\}\+2L\\sqrt\{\\frac\{2\(\\alpha\+\\beta\\rho\_\{t\}d\)\}\{S\_\{t\}\}\}\\right\\\}\\right\.\+dDρT\+αT\+dβ∑t=1Tρt\]\.\\displaystyle\\qquad\\qquad\\left\.\+\\,dD\\rho\_\{T\}\+\\alpha T\+d\\beta\\sum\_\{t=1\}^\{T\}\\rho\_\{t\}\\right\]\.\(6\)Whenα=β=0\\alpha=\\beta=0, we denote the quantity above simply asOPTT0​\(r\)\\mathrm\{OPT\}^\{0\}\_\{T\}\(r\)\. In this case, a single consistent choice ofρ\\rhoat all time steps suffices, i\.e\.,

OPTT0​\(r\)=infρ≥r\[∑t=1Tmin⁡\{125​L2​d2​Dρ,2​L2St\}\+d​D​ρ\]\.\\displaystyle\\mathrm\{OPT\}^\{0\}\_\{T\}\(r\)=\\inf\_\{\\rho\\geq r\}\\left\[\\sum\_\{t=1\}^\{T\}\\min\\left\\\{\\frac\{125L^\{2\}d^\{2\}D\}\{\\rho\},\\frac\{2L^\{2\}\}\{S\_\{t\}\}\\right\\\}\+dD\\rho\\right\]\.\(7\)This follows by noting that, for every feasibler≤ρ1≤⋯≤ρTr\\leq\\rho\_\{1\}\\leq\\dots\\leq\\rho\_\{T\}, we can simply setρt=ρT\\rho\_\{t\}=\\rho\_\{T\}for everytt; this keeps the sequence feasible, and does not increase any individual term inside the summation\.

Given this, a naturalρt\\rho\_\{t\}that the algorithm can choose, solely as a function of the information it has seen so far, isOPTt−10​\(r\)\\mathrm\{OPT\}^\{0\}\_\{t\-1\}\(r\)\. This is the value ofρt\\rho\_\{t\}that would realize the best offline regret in hindsight, had the game been stopped before roundtt, and corresponds to an FTL move itself in the space of noise schedules\. This choice ofρt\\rho\_\{t\}turns out to be non\-decreasing; more interestingly, we can show that the regret of[Algorithm1](https://arxiv.org/html/2606.02948#alg1)instantiated with this choice ofρt\\rho\_\{t\}is constant\-factor competitive withOPTTα,β​\(r\)\\mathrm\{OPT\}^\{\\alpha,\\beta\}\_\{T\}\(r\)\.

###### Theorem 2\(FTL for Noise Scale Schedule\)\.

Fixr\>0r\>0\. Letρ1=r\\rho\_\{1\}=r, and fort≥2t\\geq 2,

ρt=min​arg​infρ≥r⁡\[∑i=1t−1min⁡\{125​L2​d2​Dρ,2​L2Si\}\+d​D​ρ\],\\displaystyle\\rho\_\{t\}=\\min\\operatorname\*\{arg\\,inf\}\_\{\\rho\\geq r\}\\left\[\\sum\_\{i=1\}^\{t\-1\}\\min\\left\\\{\\frac\{125L^\{2\}d^\{2\}D\}\{\\rho\},\\frac\{2L^\{2\}\}\{S\_\{i\}\}\\right\\\}\+dD\\rho\\right\],\(8\)Then,

1. 1\.ρ1≤⋯≤ρT\\rho\_\{1\}\\leq\\dots\\leq\\rho\_\{T\}, and everyρt\\rho\_\{t\}depends only onS1,…,St−1S\_\{1\},\\dots,S\_\{t\-1\}\.
2. 2\.For this noise scale schedule, assuming that the error parameterβ≤c/T\\beta\\leq c/T,[Algorithm1](https://arxiv.org/html/2606.02948#alg1)has the following regret guarantee: 𝔼σ⁡\[RegretT​\(f1:T;x1:T\)\]≤C1⋅OPTT0​\(r\)≤C2⋅OPTTα,β​\(r\)\.\\displaystyle\\operatorname\{\{\\mathds\{E\}\}\}\_\{\\sigma\}\\left\[\\mathrm\{Regret\}\_\{T\}\(f\_\{1:T\};x\_\{1:T\}\)\\right\]\\leq C\_\{1\}\\cdot\\mathrm\{OPT\}^\{0\}\_\{T\}\(r\)\\leq C\_\{2\}\\cdot\\mathrm\{OPT\}^\{\\alpha,\\beta\}\_\{T\}\(r\)\.Here,C1C\_\{1\}andC2C\_\{2\}are constants depending only ond,D,L,rd,D,L,r, andcc\.

We note thatρt\\rho\_\{t\}as given by \([8](https://arxiv.org/html/2606.02948#S3.E8)\) can be efficiently computed, provided that we are given the valuesS1,…,St−1S\_\{1\},\\dots,S\_\{t\-1\}\. To see this, for eachSiS\_\{i\}, considerbi=125​L2​d2​D2​L2/Sib\_\{i\}=\\frac\{125L^\{2\}d^\{2\}D\}\{2L^\{2\}/S\_\{i\}\}\(wherebi=0b\_\{i\}=0ifSi=0S\_\{i\}=0\), and sort thebib\_\{i\}values, so thatbi1≤bi2≤⋯≤bit−1b\_\{i\_\{1\}\}\\leq b\_\{i\_\{2\}\}\\leq\\dots\\leq b\_\{i\_\{t\-1\}\}\. Furthermore, setbi0=0b\_\{i\_\{0\}\}=0andbit=∞b\_\{i\_\{t\}\}=\\infty, and consider the intervals\[b~i0,bi1\),\[b~i1,bi2\),…,\[b~it−1,bit\)\[\\tilde\{b\}\_\{i\_\{0\}\},b\_\{i\_\{1\}\}\),\[\\tilde\{b\}\_\{i\_\{1\}\},b\_\{i\_\{2\}\}\),\\dots,\[\\tilde\{b\}\_\{i\_\{t\-1\}\},b\_\{i\_\{t\}\}\), whereb~ij=max⁡\(bij,r\)\\tilde\{b\}\_\{i\_\{j\}\}=\\max\(b\_\{i\_\{j\}\},r\)\. For anyρ∈\[b~ij,bij\+1\)\\rho\\in\[\\tilde\{b\}\_\{i\_\{j\}\},b\_\{i\_\{j\+1\}\}\), observe that the objective function in \([8](https://arxiv.org/html/2606.02948#S3.E8)\) evaluates to

125​j​L2​d2​Dρ\+d​D​ρ\+∑k<t:bik\>ρ2​L2Si\.\\displaystyle\\frac\{125jL^\{2\}d^\{2\}D\}\{\\rho\}\+dD\\rho\+\\sum\_\{k<t:b\_\{i\_\{k\}\}\>\\rho\}\\frac\{2L^\{2\}\}\{S\_\{i\}\}\.Note that the last term is constant for everyρ∈\[b~ij,bij\+1\)\\rho\\in\[\\tilde\{b\}\_\{i\_\{j\}\},b\_\{i\_\{j\+1\}\}\)\. Thus, the “unconstrained” minimizer for this interval balances the first two terms, giving

ρ^j=125​j​L2​d\.\\displaystyle\\hat\{\\rho\}\_\{j\}=\\sqrt\{125jL^\{2\}d\}\.This is a valid value forρ^j\\hat\{\\rho\}\_\{j\}, provided125​j​L2​d∈\[b~ij,bij\+1\)\\sqrt\{125jL^\{2\}d\}\\in\[\\tilde\{b\}\_\{i\_\{j\}\},b\_\{i\_\{j\+1\}\}\)\. However, if125​j​L2​d∉\[b~ij,bij\+1\)\\sqrt\{125jL^\{2\}d\}\\notin\[\\tilde\{b\}\_\{i\_\{j\}\},b\_\{i\_\{j\+1\}\}\), we simply setρ^j\\hat\{\\rho\}\_\{j\}to be eitherb~ij\\tilde\{b\}\_\{i\_\{j\}\}orbij\+1b\_\{i\_\{j\+1\}\}, based on whichever of the two evaluates to a smaller objective in \([8](https://arxiv.org/html/2606.02948#S3.E8)\)\. Finally, we setρt\\rho\_\{t\}to be theρ^j\\hat\{\\rho\}\_\{j\}value which realizes the smallest objective among allρ^j\\hat\{\\rho\}\_\{j\}’s\.

We give the complete proof of[Theorem2](https://arxiv.org/html/2606.02948#Thmtheorem2)in[AppendixA](https://arxiv.org/html/2606.02948#A1), which goes through a be\-the\-leader analysis again\. Namely, it considers the regret of the algorithm, had it chosenρt\+1\\rho\_\{t\+1\}instead ofρt\\rho\_\{t\}at time steptt\(it cannot do so, since it does not knowftf\_\{t\}\)\. Thereafter, it bounds the cost of instead having playedρt\\rho\_\{t\}, by using the specific form of the objective function\.

[Theorem2](https://arxiv.org/html/2606.02948#Thmtheorem2)allows us to derive precise regret guarantees of[Algorithm1](https://arxiv.org/html/2606.02948#alg1), with the choice ofρt\\rho\_\{t\}given in \([8](https://arxiv.org/html/2606.02948#S3.E8)\), for different curvature regimes\.

###### Corollary 3\.1\(Curvature\-adaptive Regret\)\.

Consider[Algorithm1](https://arxiv.org/html/2606.02948#alg1)instantiated with the noise scheduleρt\\rho\_\{t\}given in \([8](https://arxiv.org/html/2606.02948#S3.E8)\), and suppose thatα,β=O​\(1/T\)\\alpha,\\beta=O\(1/T\)\. Then, the following guarantee always holds:

𝔼σ⁡\[RegretT​\(f1:T;x1:T\)\]≤O​\(T\)\.\\displaystyle\\operatorname\{\{\\mathds\{E\}\}\}\_\{\\sigma\}\[\\mathrm\{Regret\}\_\{T\}\(f\_\{1:T\};x\_\{1:T\}\)\]\\leq O\(\\sqrt\{T\}\)\.Additionally, if the cumulative curvature satisfiesSt≥tγS\_\{t\}\\geq t^\{\\gamma\}, we have that

𝔼σ⁡\[RegretT​\(f1:T;x1:T\)\]\\displaystyle\\operatorname\{\{\\mathds\{E\}\}\}\_\{\\sigma\}\[\\mathrm\{Regret\}\_\{T\}\(f\_\{1:T\};x\_\{1:T\}\)\]=\{O​\(T\),γ≤12,O​\(T1−γ\),12<γ<1,O​\(log⁡T\),γ=1,O​\(1\),γ\>1\.\\displaystyle=\\begin\{cases\}O\(\\sqrt\{T\}\),&\\gamma\\leq\\frac\{1\}\{2\},\\\\ O\(T^\{1\-\\gamma\}\),&\\frac\{1\}\{2\}<\\gamma<1,\\\\ O\(\\log T\),&\\gamma=1,\\\\ O\(1\),&\\gamma\>1\.\\end\{cases\}

The proof of[Corollary3\.1](https://arxiv.org/html/2606.02948#S3.Thmlemma1)is a calculation upper\-boundingOPTTα,β​\(r\)\\mathrm\{OPT\}^\{\\alpha,\\beta\}\_\{T\}\(r\)in each of the regimes, and is given in[AppendixA](https://arxiv.org/html/2606.02948#A1)\.

It is instructive to compare the regime\-wise guarantees above to the regime\-wise guarantees given in Corollary 3\.3 inBartlettet al\.\([2007](https://arxiv.org/html/2606.02948#bib.bib20)\)for onlineconvexoptimization\. Specifically,Bartlettet al\.\([2007](https://arxiv.org/html/2606.02948#bib.bib20)\)consider the setting where every individualftf\_\{t\}has curvaturet−λt^\{\-\\lambda\}\(which implies thatSt≈t1−λS\_\{t\}\\approx t^\{1\-\\lambda\}\), and do casework onλ\\lambda\. Mapping their cases to our cases above yields identical regret bounds as theirs\. In this way,[Corollary3\.1](https://arxiv.org/html/2606.02948#S3.Thmlemma1)generalizes their guarantees by analyzing different regimes ofcumulativecurvature, which allows non\-convex functions too\.

Lastly, we comment about the setting of the error parametersα,β\\alpha,\\betain our results\.[Theorem2](https://arxiv.org/html/2606.02948#Thmtheorem2)required no condition onα\\alpha, but requiredβ=O​\(1/T\)\\beta=O\(1/T\)\. On the other hand,[Corollary3\.1](https://arxiv.org/html/2606.02948#S3.Thmlemma1)requiredα=O​\(1/T\)\\alpha=O\(1/T\)as well\. Similar conditions on the error parameters were required bySuggala and Netrapalli \([2020](https://arxiv.org/html/2606.02948#bib.bib17)\)as well\. In particular,Suggala and Netrapalli \([2020](https://arxiv.org/html/2606.02948#bib.bib17)\)required settingα=O​\(1/T\)\\alpha=O\(1/\\sqrt\{T\}\)andβ=O​\(1/T\)\\beta=O\(1/T\)in order to guaranteeO​\(T\)O\(\\sqrt\{T\}\)regret\. This suffices for us as well for the purposes of getting a uniformO​\(T\)O\(\\sqrt\{T\}\)regret guarantee\. However, since we are aiming foro​\(T\)o\(\\sqrt\{T\}\)regret in the cases where curvature is ample, we requireα\\alphato be smaller\. This is made clear by considering the expression \([3\.1](https://arxiv.org/html/2606.02948#S3.Ex4)\) forOPTTα,β​\(r\)\\mathrm\{OPT\}^\{\\alpha,\\beta\}\_\{T\}\(r\), which explicitly contains anα​T\\alpha Tterm\.

## 4Lower Bound

The previous section showed that the regret of our algorithm, instantiated with the suggested noise scale schedule, is at mostO​\(OPTT0​\(r\)\)O\(\\mathrm\{OPT\}^\{0\}\_\{T\}\(r\)\)\. In fact, it holds thatOPTT0​\(r\)≤OPTT0​\(0\)\+d​D​r\\mathrm\{OPT\}^\{0\}\_\{T\}\(r\)\\leq\\mathrm\{OPT\}^\{0\}\_\{T\}\(0\)\+dDr\(see[B\.3](https://arxiv.org/html/2606.02948#A2.Thmlemma3)\), which means that, holdingr,D,Lr,D,Lfixed, the regret of our algorithm grows withTTasO​\(OPTT0​\(0\)\)O\(\\mathrm\{OPT\}^\{0\}\_\{T\}\(0\)\)\. We will now show that a regret ofΩ​\(OPTT0​\(0\)\)\\Omega\(\\mathrm\{OPT\}^\{0\}\_\{T\}\(0\)\)is necessary in the worst case foranyalgorithm\. This shows that theO​\(OPTT0​\(0\)\)O\(\\mathrm\{OPT\}^\{0\}\_\{T\}\(0\)\)regret bound that we obtained above is not just a consequence of our analysis, but is in fact inherent\. Moreover, it also shows that our algorithm achieves a minimax optimal regret\.

Our lower bound holds for any given sequence of cumulative curvatures satisfying0=s0≤s1≤s2≤⋯≤sT0=s\_\{0\}\\leq s\_\{1\}\\leq s\_\{2\}\\leq\\dots\\leq s\_\{T\}\. In particular, this means that anΩ​\(OPTT0​\(0\)\)\\Omega\(\\mathrm\{OPT\}^\{0\}\_\{T\}\(0\)\)regret is necessary already for a sequence ofconvexfunctions\. Given such a curvature sequence, we derive a sequence of functionsf1,…,fTf\_\{1\},\\dots,f\_\{T\}that areLL\-Lipschitz on𝒳\\mathcal\{X\}, and have cumulative curvatureSt=stS\_\{t\}=s\_\{t\}for alltt\.

More concretely, define the minimax regret for a cumulative curvature sequences1:T=s1,…,sTs\_\{1:T\}=s\_\{1\},\\dots,s\_\{T\}to be

ℜT​\(s1:T\):=inf𝒜supf1,…,fT​​L​\-Lipschitzon​𝒳St=st​for all​t𝔼𝒜⁡\[RegretT​\(f1:T;x1:T\)\]\.\\displaystyle\\mathfrak\{R\}\_\{T\}\(s\_\{1:T\}\):=\\inf\_\{\\mathcal\{A\}\}\\sup\_\{\\begin\{subarray\}\{c\}f\_\{1\},\\ldots,f\_\{T\}\\text\{ \}L\\text\{\-Lipschitz\}\\text\{ on \}\\mathcal\{X\}\\\\ S\_\{t\}=s\_\{t\}\\text\{ for all \}t\\end\{subarray\}\}\\operatorname\{\{\\mathds\{E\}\}\}\_\{\\mathcal\{A\}\}\\left\[\\mathrm\{Regret\}\_\{T\}\(f\_\{1:T\};x\_\{1:T\}\)\\right\]\.\(9\)
###### Theorem 3\(Curvature\-specific Lower Bound\)\.

Fix the dimensiond=1d=1\. There is a universal constantc\>0c\>0, such that for everyT≥1T\\geq 1and every non\-decreasing sequence0=s0≤s1≤⋯≤sT0=s\_\{0\}\\leq s\_\{1\}\\leq\\dots\\leq s\_\{T\}satisfyingst−st−1≤L2​Ds\_\{t\}\-s\_\{t\-1\}\\leq\\frac\{L\}\{2D\}for allt∈\[T\]t\\in\[T\],

ℜT​\(s1:T\)\\displaystyle\\mathfrak\{R\}\_\{T\}\(s\_\{1:T\}\)≥c⋅infρ≥0\[∑t=1Tmin⁡\{L2​Dρ,L2st\}\+D​ρ\]=Ω​\(OPTT0​\(0\)\)\.\\displaystyle\\geq c\\cdot\\inf\_\{\\rho\\geq 0\}\\left\[\\sum\_\{t=1\}^\{T\}\\min\\left\\\{\\frac\{L^\{2\}D\}\{\\rho\},\\frac\{L^\{2\}\}\{s\_\{t\}\}\\right\\\}\+D\\rho\\right\]=\\Omega\\left\(\\mathrm\{OPT\}^\{0\}\_\{T\}\(0\)\\right\)\.\(10\)

As discussed above, since our algorithm always has a regret guarantee ofO​\(OPTT0​\(0\)\)O\(\\mathrm\{OPT\}^\{0\}\_\{T\}\(0\)\), we thus have that the minimax regret satisfiesℜT​\(s1:T\)=Θ​\(OPTT0​\(0\)\)\\mathfrak\{R\}\_\{T\}\(s\_\{1:T\}\)=\\Theta\(\\mathrm\{OPT\}^\{0\}\_\{T\}\(0\)\)\.

The entire proof of[Theorem3](https://arxiv.org/html/2606.02948#Thmtheorem3)comprises of several intricate steps, and we defer the details to[AppendixB](https://arxiv.org/html/2606.02948#A2)\. Here, we highlight some salient aspects of the construction\. Previous work byAbernethyet al\.\([2008](https://arxiv.org/html/2606.02948#bib.bib7)\)shows a minimax lower bound ofΩ​\(T\)\\Omega\(\\sqrt\{T\}\)for generic online convex optimization, as well as a lower bound ofΩ​\(log⁡T\)\\Omega\(\\log T\)for strongly convex online optimization\. These constructions use \(1\) a sequence of random linear functions for the general convex case, and \(2\) a sequence of quadratics with drifting centers for the strongly convex case\.

Neither of these constructions, by themselves, directly extend to our case, where we wish to show a lower bound for an arbitrary sequence of non\-negative and non\-decreasing cumulative curvatures\. Nevertheless, a natural strategy would be to carefully mix in both the above components\. That is, we choose everyftf\_\{t\}to comprise of a random linear term, together with a quadratic function whose centerztz\_\{t\}follows a suitably chosen random process\. The curvature constraints imply that the coefficient on the quadratic term ought to beat=st−st−1a\_\{t\}=s\_\{t\}\-s\_\{t\-1\}\. The main technical innovation in the analysis is the construction of fictitious functionsGt​\(x\)G\_\{t\}\(x\)that are regularized forms of the cumulative functionsFt​\(x\)F\_\{t\}\(x\)\. These functions enable lower\-bounding the regret of any algorithm by relating the best\-in\-hindsight loss onFTF\_\{T\}to the telescoping summation ofGt​\(zt\)−Gt−1​\(zt−1\)G\_\{t\}\(z\_\{t\}\)\-G\_\{t\-1\}\(z\_\{t\-1\}\)\.

Finally, in[SectionB\.1](https://arxiv.org/html/2606.02948#A2.SS1), we complement the regime\-specific regret upper bounds given in[Corollary3\.1](https://arxiv.org/html/2606.02948#S3.Thmlemma1)with matching lower bounds\. This shows that the guarantees for our algorithm given in[Corollary3\.1](https://arxiv.org/html/2606.02948#S3.Thmlemma1)are optimal\.

## 5Simulations

![Refer to caption](https://arxiv.org/html/2606.02948v1/x1.png)\(a\)
![Refer to caption](https://arxiv.org/html/2606.02948v1/x2.png)\(b\)
![Refer to caption](https://arxiv.org/html/2606.02948v1/x3.png)\(c\)
![Refer to caption](https://arxiv.org/html/2606.02948v1/x4.png)\(d\)
![Refer to caption](https://arxiv.org/html/2606.02948v1/x5.png)\(e\)
![Refer to caption](https://arxiv.org/html/2606.02948v1/x6.png)\(f\)
![Refer to caption](https://arxiv.org/html/2606.02948v1/x7.png)\(g\)
![Refer to caption](https://arxiv.org/html/2606.02948v1/x8.png)\(h\)

Figure 1:\(a\)\-\(e\) We gradually increase curvature\. \(f\),\(g\) Curvature is introduced/taken away in the middle\. \(h\) Adversarial sequence that causes FTL to oscillate heavily and incur linear regret\.We perform synthetic experiments on a sequence of quadratic functions, and compare the regret of three algorithms: FTL, FTPL and AdaFTPL\. We specifically choose quadratics to have precise control on the cumulative curvatures, and also because the optimization oracle for all the algorithms can be computed exactly in closed form\. Concretely, we setd=10d=10, and consider𝒳=\[−D/2,D/2\]d\\mathcal\{X\}=\[\-D/2,D/2\]^\{d\}\. Eachftf\_\{t\}is of the form

ft​\(x\):=κt​∑i=1dat,i​\(xi−bt,i\)2,\\displaystyle f\_\{t\}\(x\):=\\kappa\_\{t\}\\sum\_\{i=1\}^\{d\}a\_\{t,i\}\(x\_\{i\}\-b\_\{t,i\}\)^\{2\},\(11\)whereκt∈\{\+1,−1\}\\kappa\_\{t\}\\in\\\{\+1,\-1\\\}is set to be\+1\+1with probabilityp\+p\_\{\+\}, and−1\-1otherwise\. Eachat,i∼\[0,1/2​D\]a\_\{t,i\}\\sim\[0,1/2D\], andbt,i∼\[−D/2,D/2\]b\_\{t,i\}\\sim\[\-D/2,D/2\]uniformly at random, which ensures thatftf\_\{t\}is 1\-Lipschitz on𝒳\\mathcal\{X\}\. Note that ifp\+=0p\_\{\+\}=0, everyftf\_\{t\}is non\-convex, and asp\+p\_\{\+\}increases, the cumulative curvature builds up, with all the functions being strongly convex atp\+=1p\_\{\+\}=1\. We consider horizons ranging fromT=1T=1toT=3000T=3000\. For each horizonTT, we run each of the algorithms on the sequencef1,…,fTf\_\{1\},\\dots,f\_\{T\}, and compute its final regret\. Recall that FTPL as given bySuggala and Netrapalli \([2020](https://arxiv.org/html/2606.02948#bib.bib17)\)is simply AdaFTPL withρt=ρ\\rho\_\{t\}=\\rhofor alltt\. We setρ=T\\rho=\\sqrt\{T\}as suggested bySuggala and Netrapalli \([2020](https://arxiv.org/html/2606.02948#bib.bib17)\), which guarantees anO​\(T\)O\(\\sqrt\{T\}\)regret bound\. For AdaFTPL, we setρt\\rho\_\{t\}according to the noise scale schedule in[Theorem2](https://arxiv.org/html/2606.02948#Thmtheorem2)\. Figures[1\(a\)](https://arxiv.org/html/2606.02948#S5.F1.sf1)\-[1\(e\)](https://arxiv.org/html/2606.02948#S5.F1.sf5)plot the regret of the algorithms \(averaged over 10 random runs\) against the time horizonTT\.

We can observe that whenp\+p\_\{\+\}is small, all the three algorithms perform similarly\. Asp\+p\_\{\+\}increases, and curvature starts showing up in the function sequence, AdaFTPL adapts to this, and achieves much better regret than FTPL\. In fact, in the cases wherep\+=0\.75p\_\{\+\}=0\.75andp\+=1p\_\{\+\}=1, the regret of AdaFTPL grows similarly to the regret of FTL \(∼log⁡T\\sim\\log T\), whereas the regret of FTPL grows significantly worse \(∼T\\sim\\sqrt\{T\}\)\.

To highlight the adaptive behavior of AdaFTPL, we also consider: \(1\) a sequence wherep\+=0\.5p\_\{\+\}=0\.5for the first10001000functions, andp\+=1p\_\{\+\}=1for the rest of the functions, and \(2\) a sequence wherep\+=1p\_\{\+\}=1for the first10001000functions, andp\+=0\.5p\_\{\+\}=0\.5for the rest of the functions\. The coefficientsat,ia\_\{t,i\}for the first 1000 functions are scaled down; the idea is to either introduce/take away positive curvature in the middle of the sequence, and see if AdaFTPL adapts to it as expected\. We can see in Figures[1\(f\)](https://arxiv.org/html/2606.02948#S5.F1.sf6)and[1\(g\)](https://arxiv.org/html/2606.02948#S5.F1.sf7)that this is indeed so: in the first case, beyondT=1000T=1000, the regret of AdaFTPL grows akin to FTL, and much slower than FTPL\. In the latter case, AdaFTPL exploits the available curvature in the first 1000 steps, and thereafter still maintains its conservative regret guarantee\.

Finally, we also include an example \(Figure[1\(h\)](https://arxiv.org/html/2606.02948#S5.F1.sf8)\) of an adversarial sequence of functions \(withd=1d=1\) that has alternatingκt\\kappa\_\{t\}signs, a standard and well\-known failure case for FTL\. For this sequence, FTL plays a sequence of moves that oscillates a lot, causing linear regret, whereas both FTPL and AdaFTPL, by virtue of their perturbations, play stable moves that result in sublinear regret\. This example highlights how FTL failsdrasticallyin the worst case, even if it may work well in other problem instances\.

## 6Conclusion

In this work, we derived an Adaptive FTPL algorithm that uses time\-varying perturbations, and enjoys regret guarantees that interpolate betweenO​\(log⁡T\)O\(\\log T\)andO​\(T\)O\(\\sqrt\{T\}\)based on the curvature present in the function sequence\. We also obtained an intuitive and efficient method to set the noise scale of the perturbation at each round, as a function of the curvatures of the functions seen so far\. We give a matching lower bound construction which shows that our regret guarantees are optimal\. Our work thus extends adaptive regret rates in the theory of online optimization significantly beyond online convex optimization\.

### Acknowledgements

This work is supported by Moses Charikar’s and Gregory Valiant’s Simons Investigator Awards, and a Google PhD Fellowship\. ChatGPT was routinely used in the development and understanding of ideas used in the paper

## References

- J\. Abernethy, P\. L\. Bartlett, A\. Rakhlin, and A\. Tewari \(2008\)Optimal strategies and minimax lower bounds for online convex games\.InProceedings of the 21st Annual Conference on Learning Theory,pp\. 414–424\.Cited by:[§1](https://arxiv.org/html/2606.02948#S1.p1.3),[§2](https://arxiv.org/html/2606.02948#S2.SS0.SSS0.Px2.p1.2),[§4](https://arxiv.org/html/2606.02948#S4.p5.2)\.
- N\. Agarwal, A\. Gonen, and E\. Hazan \(2019\)Learning in non\-convex games with an optimization oracle\.InConference on Learning Theory,pp\. 18–29\.Cited by:[§2](https://arxiv.org/html/2606.02948#S2.SS0.SSS0.Px1.p1.6),[§2](https://arxiv.org/html/2606.02948#S2.SS0.SSS0.Px2.p1.2)\.
- P\. Bartlett, E\. Hazan, and A\. Rakhlin \(2007\)Adaptive online gradient descent\.Advances in neural information processing systems20\.Cited by:[1st item](https://arxiv.org/html/2606.02948#S1.I1.i1.p1.2),[§1](https://arxiv.org/html/2606.02948#S1.p2.3),[§2](https://arxiv.org/html/2606.02948#S2.SS0.SSS0.Px2.p1.2),[§3\.1](https://arxiv.org/html/2606.02948#S3.SS1.p8.4)\.
- P\. Billingsley \(2017\)Probability and measure\.John Wiley & Sons\.Cited by:[Appendix B](https://arxiv.org/html/2606.02948#A2.SSx6.p1.10)\.
- N\. Cesa\-Bianchi and G\. Lugosi \(2006\)Prediction, learning, and games\.Cambridge University Press\.Cited by:[Appendix A](https://arxiv.org/html/2606.02948#A1.1.p1.5),[§3](https://arxiv.org/html/2606.02948#S3.SS0.SSS0.Px4.p1.6)\.
- J\. Duchi, E\. Hazan, and Y\. Singer \(2011\)Adaptive subgradient methods for online learning and stochastic optimization\.\.Journal of machine learning research12\(7\)\.Cited by:[§1](https://arxiv.org/html/2606.02948#S1.p2.3),[§2](https://arxiv.org/html/2606.02948#S2.SS0.SSS0.Px2.p1.2)\.
- J\. Hannan \(1957\)Approximation to bayes risk in repeated play\.InContributions to the Theory of Games III,M\. Dresher, A\. W\. Tucker, and P\. Wolfe \(Eds\.\),Annals of Mathematics Studies, Vol\.3,pp\. 97–139\.Cited by:[§2](https://arxiv.org/html/2606.02948#S2.SS0.SSS0.Px1.p1.6)\.
- E\. Hazan, A\. Kalai, S\. Kale, and A\. Agarwal \(2006\)Logarithmic regret algorithms for online convex optimization\.InConference on Learning Theory,pp\. 499–513\.Cited by:[§1](https://arxiv.org/html/2606.02948#S1.p1.3),[§2](https://arxiv.org/html/2606.02948#S2.SS0.SSS0.Px2.p1.2)\.
- E\. Hazan and T\. Koren \(2016\)The computational power of optimization in online learning\.InProceedings of the forty\-eighth annual ACM symposium on Theory of Computing,pp\. 128–141\.Cited by:[§2](https://arxiv.org/html/2606.02948#S2.SS0.SSS0.Px1.p1.6)\.
- M\. Hutter and J\. Poland \(2005\)Adaptive online prediction by following the perturbed leader\.Cited by:[Appendix A](https://arxiv.org/html/2606.02948#A1.1.p1.5),[§2](https://arxiv.org/html/2606.02948#S2.SS0.SSS0.Px3.p1.3),[§3](https://arxiv.org/html/2606.02948#S3.SS0.SSS0.Px4.p1.6)\.
- A\. Kalai and S\. Vempala \(2005\)Efficient algorithms for online decision problems\.Journal of Computer and System Sciences71\(3\),pp\. 291–307\.Cited by:[§2](https://arxiv.org/html/2606.02948#S2.SS0.SSS0.Px1.p1.6)\.
- D\. P\. Kingma and J\. Ba \(2015\)Adam: a method for stochastic optimization\.InInternational Conference on Learning Representations \(ICLR\),Cited by:[§1](https://arxiv.org/html/2606.02948#S1.p2.3),[§2](https://arxiv.org/html/2606.02948#S2.SS0.SSS0.Px2.p1.2)\.
- J\. Kirkpatrick, R\. Pascanu, N\. Rabinowitz, J\. Veness, G\. Desjardins, A\. A\. Rusu, K\. Milan, J\. Quan, T\. Ramalho, A\. Grabska\-Barwińska, D\. Hassabis, C\. Clopath, D\. Kumaran, and R\. Hadsell \(2017\)Overcoming catastrophic forgetting in neural networks\.Proceedings of the National Academy of Sciences114\(13\),pp\. 3521–3526\.Cited by:[§1](https://arxiv.org/html/2606.02948#S1.p6.5)\.
- X\. Li and F\. Orabona \(2019\)On the convergence of stochastic gradient descent with adaptive stepsizes\.InThe 22nd international conference on artificial intelligence and statistics,pp\. 983–992\.Cited by:[§2](https://arxiv.org/html/2606.02948#S2.SS0.SSS0.Px2.p1.2)\.
- R\. A\. Maronna, R\. D\. Martin, V\. J\. Yohai, and M\. Salibián\-Barrera \(2019\)Robust statistics: theory and methods \(with r\)\.2 edition,Wiley\.Cited by:[§1](https://arxiv.org/html/2606.02948#S1.p6.5)\.
- H\. B\. McMahan and M\. Streeter \(2010\)Adaptive bound optimization for online convex optimization\.arXiv preprint arXiv:1002\.4908\.Cited by:[§2](https://arxiv.org/html/2606.02948#S2.SS0.SSS0.Px2.p1.2)\.
- H\. B\. McMahan \(2017\)A survey of algorithms and analysis for adaptive online learning\.Journal of Machine Learning Research18\(90\),pp\. 1–50\.Cited by:[§2](https://arxiv.org/html/2606.02948#S2.SS0.SSS0.Px2.p1.2)\.
- A\. S\. Suggala and P\. Netrapalli \(2020\)Online non\-convex learning: following the perturbed leader is optimal\.InAlgorithmic Learning Theory,pp\. 845–861\.Cited by:[Appendix A](https://arxiv.org/html/2606.02948#A1.2.p2.6),[Appendix A](https://arxiv.org/html/2606.02948#A1.4.p4.4),[1st item](https://arxiv.org/html/2606.02948#S1.I1.i1.p1.2),[§1](https://arxiv.org/html/2606.02948#S1.p2.3),[§2](https://arxiv.org/html/2606.02948#S2.SS0.SSS0.Px1.p1.6),[§3](https://arxiv.org/html/2606.02948#S3.SS0.SSS0.Px3.p1.5),[§3](https://arxiv.org/html/2606.02948#S3.SS0.SSS0.Px4.p2.7),[§3](https://arxiv.org/html/2606.02948#S3.SS0.SSS0.Px4.p4.13),[§3\.1](https://arxiv.org/html/2606.02948#S3.SS1.p9.12),[§5](https://arxiv.org/html/2606.02948#S5.p1.25),[footnote 2](https://arxiv.org/html/2606.02948#footnote2)\.
- G\. Wang, Z\. Hu, V\. Muthukumar, and J\. D\. Abernethy \(2022\)Adaptive oracle\-efficient online learning\.Advances in Neural Information Processing Systems35,pp\. 23398–23411\.Cited by:[§2](https://arxiv.org/html/2606.02948#S2.SS0.SSS0.Px3.p1.3)\.
- R\. Ward, X\. Wu, and L\. Bottou \(2020\)Adagrad stepsizes: sharp convergence over nonconvex landscapes\.Journal of Machine Learning Research21\(219\),pp\. 1–30\.Cited by:[§2](https://arxiv.org/html/2606.02948#S2.SS0.SSS0.Px2.p1.2)\.
- A\. C\. Yao \(1983\)Lower bounds by probabilistic arguments\.In24th Annual Symposium on Foundations of Computer Science \(sfcs 1983\),pp\. 420–428\.Cited by:[Appendix B](https://arxiv.org/html/2606.02948#A2.SSx8.p2.5)\.
- M\. Zinkevich \(2003\)Online convex programming and generalized infinitesimal gradient ascent\.InProceedings of the 20th international conference on machine learning \(icml\-03\),pp\. 928–936\.Cited by:[§1](https://arxiv.org/html/2606.02948#S1.p1.3),[§2](https://arxiv.org/html/2606.02948#S2.SS0.SSS0.Px2.p1.2)\.

## Appendix AProofs from[Section3](https://arxiv.org/html/2606.02948#S3)

We restate and prove[Theorem1](https://arxiv.org/html/2606.02948#Thmtheorem1)\. See[1](https://arxiv.org/html/2606.02948#Thmtheorem1)

###### Proof\.

By a standard argument for FTPL \(e\.g\., see Lemma 12 inHutter and Poland \[[2005](https://arxiv.org/html/2606.02948#bib.bib18)\], Chapter 4 inCesa\-Bianchi and Lugosi \[[2006](https://arxiv.org/html/2606.02948#bib.bib19)\]\), it suffices to consider the setting where the functions are specified upfront by anobliviousadversary, and show the regret bound for every fixedf1,…,fTf\_\{1\},\\dots,f\_\{T\}\. With obliviously specified functions, it furthermore suffices in[Algorithm1](https://arxiv.org/html/2606.02948#alg1)to simply draw a random vectorσ=\{σj\}j=1d∼i\.i\.d\.Exp​\(1\)\\sigma=\\\{\\sigma\_\{j\}\\\}\_\{j=1\}^\{d\}\\stackrel\{\{\\scriptstyle\\mathrm\{i\.i\.d\.\}\}\}\{\{\\sim\}\}\\text\{Exp\}\(1\)once at the start and reuse it at every time step, instead of drawing a freshσt\\sigma\_\{t\}at each step\. With these considerations, our goal is to upper bound the regret in the left\-hand side of \([1](https://arxiv.org/html/2606.02948#S3.Ex3)\) for fixedf1,…,fTf\_\{1\},\\dots,f\_\{T\}, where the expectation is only with respect toσ\\sigmadrawn at the start of the game\.

We begin by defining a key quantity in the analysis: for anyt=1,…,Tt=1,\\dots,T, letx¯t\+1=𝒪α,β​\(Ft,ρt​σ\)\\bar\{x\}\_\{t\+1\}=\\mathcal\{O\}\_\{\\alpha,\\beta\}\(F\_\{t\},\\rho\_\{t\}\\sigma\)\. Note thatx¯t\+1\\bar\{x\}\_\{t\+1\}is separate fromxt\+1=𝒪α,β​\(Ft,ρt\+1​σ\)x\_\{t\+1\}=\\mathcal\{O\}\_\{\\alpha,\\beta\}\(F\_\{t\},\\,\\rho\_\{t\+1\}\\sigma\)that the algorithm plays at time stept\+1t\+1\. We introducex¯t\+1\\bar\{x\}\_\{t\+1\}, which uses the noise vector from theprevioustime step, solely for the sake of analysis\. This will help us \(1\) establish a standard decomposition of the regret into astabilityandperturbationterm, and \(2\) directly utilize the bound on the stability term fromSuggala and Netrapalli \[[2020](https://arxiv.org/html/2606.02948#bib.bib17)\]\.

We now claim that222We note that settingρ1=⋯=ρT=1η\\rho\_\{1\}=\\dots=\\rho\_\{T\}=\\frac\{1\}\{\\eta\}recovers the bound inSuggala and Netrapalli \[[2020](https://arxiv.org/html/2606.02948#bib.bib17)\]\.:

𝔼σ⁡\[∑t=1Tft​\(xt\)−infx∈𝒳∑t=1Tft​\(x\)\]≤L​∑t=1T𝔼σ⁡\[‖xt−x¯t\+1‖1\]⏟stability\+dDρT\+αT\+dβ∑t=1Tρt\.⏟perturbation\\displaystyle\\operatorname\{\{\\mathds\{E\}\}\}\_\{\\sigma\}\\left\[\\sum\_\{t=1\}^\{T\}f\_\{t\}\(x\_\{t\}\)\-\\inf\_\{x\\in\\mathcal\{X\}\}\\sum\_\{t=1\}^\{T\}f\_\{t\}\(x\)\\right\]\\leq\\underbrace\{L\\sum\_\{t=1\}^\{T\}\\operatorname\{\{\\mathds\{E\}\}\}\_\{\\sigma\}\\left\[\\left\\\|x\_\{t\}\-\\bar\{x\}\_\{t\+1\}\\right\\\|\_\{1\}\\right\]\}\_\{\\text\{stability\}\}\+\\underbrace\{dD\\rho\_\{T\}\+\\alpha T\+d\\beta\\sum\_\{t=1\}^\{T\}\\rho\_\{t\}\.\}\_\{\\text\{perturbation\}\}\(12\)To see this, fix anyx⋆∈𝒳x^\{\\star\}\\in\\mathcal\{X\}\. We have that

∑t=1Tft​\(xt\)−∑t=1Tft​\(x⋆\)\\displaystyle\\sum\_\{t=1\}^\{T\}f\_\{t\}\(x\_\{t\}\)\-\\sum\_\{t=1\}^\{T\}f\_\{t\}\(x^\{\\star\}\)=∑t=1T\(ft​\(xt\)−ft​\(x¯t\+1\)\)\+∑t=1T\(ft​\(x¯t\+1\)−ft​\(x⋆\)\)\\displaystyle=\\sum\_\{t=1\}^\{T\}\(f\_\{t\}\(x\_\{t\}\)\-f\_\{t\}\(\\bar\{x\}\_\{t\+1\}\)\)\+\\sum\_\{t=1\}^\{T\}\(f\_\{t\}\(\\bar\{x\}\_\{t\+1\}\)\-f\_\{t\}\(x^\{\\star\}\)\)≤L​∑t=1T‖xt−x¯t\+1‖1\+∑t=1T\(ft​\(x¯t\+1\)−ft​\(x⋆\)\),\\displaystyle\\leq L\\sum\_\{t=1\}^\{T\}\\left\\\|x\_\{t\}\-\\bar\{x\}\_\{t\+1\}\\right\\\|\_\{1\}\+\\sum\_\{t=1\}^\{T\}\(f\_\{t\}\(\\bar\{x\}\_\{t\+1\}\)\-f\_\{t\}\(x^\{\\star\}\)\),\(13\)where the inequality follows by the Lipschitzness assumption\. We thus proceed to bound the second term in \([13](https://arxiv.org/html/2606.02948#A1.E13)\)\. With a view to apply the “be\-the\-leader” inequality, define

gt​\(x\):=ft​\(x\)−⟨\(ρt−ρt−1\)​σ,x⟩,\\displaystyle g\_\{t\}\(x\):=f\_\{t\}\(x\)\-\\langle\(\\rho\_\{t\}\-\\rho\_\{t\-1\}\)\\sigma,x\\rangle,\(whereρ0=0\\rho\_\{0\}=0\), and observe that

∑i=1tgi​\(x\)=∑i=1tfi​\(x\)−⟨ρt​σ,x⟩=Ft​\(x\)−⟨ρt​σ,x⟩\.\\displaystyle\\sum\_\{i=1\}^\{t\}g\_\{i\}\(x\)=\\sum\_\{i=1\}^\{t\}f\_\{i\}\(x\)\-\\langle\\rho\_\{t\}\\sigma,x\\rangle=F\_\{t\}\(x\)\-\\langle\\rho\_\{t\}\\sigma,x\\rangle\.So, by the definition ofx¯t\+1\\bar\{x\}\_\{t\+1\}, we have thatx¯t\+1\\bar\{x\}\_\{t\+1\}is the \(approximate\) minimizer of∑i=1tgi​\(x\)\\sum\_\{i=1\}^\{t\}g\_\{i\}\(x\), where the summation crucially includesi=ti=t\. Namely, for anyt=1,…,Tt=1,\\dots,T,

∑i=1tgi​\(x¯t\+1\)\\displaystyle\\sum\_\{i=1\}^\{t\}g\_\{i\}\(\\bar\{x\}\_\{t\+1\}\)=Ft​\(x¯t\+1\)−⟨ρt​σ,x¯t\+1⟩\\displaystyle=F\_\{t\}\(\\bar\{x\}\_\{t\+1\}\)\-\\langle\\rho\_\{t\}\\sigma,\\bar\{x\}\_\{t\+1\}\\rangle≤infx∈𝒳\(Ft​\(x\)−⟨ρt​σ,x⟩\)\+\(α\+β​‖ρt​σ‖1\)=infx∈𝒳∑i=1tgi​\(x\)\+\(α\+β​‖ρt​σ‖1\)\.\\displaystyle\\leq\\inf\_\{x\\in\\mathcal\{X\}\}\\left\(F\_\{t\}\(x\)\-\\langle\\rho\_\{t\}\\sigma,x\\rangle\\right\)\+\(\\alpha\+\\beta\\\|\\rho\_\{t\}\\sigma\\\|\_\{1\}\)=\\inf\_\{x\\in\\mathcal\{X\}\}\\sum\_\{i=1\}^\{t\}g\_\{i\}\(x\)\+\(\\alpha\+\\beta\\\|\\rho\_\{t\}\\sigma\\\|\_\{1\}\)\.\(14\)We can thus instantiate the standard “be\-the\-leader” inequality to obtain that∑t=1Tgt​\(x¯t\+1\)≲infx∈𝒳∑t=1Tgt​\(x\)\\sum\_\{t=1\}^\{T\}g\_\{t\}\(\\bar\{x\}\_\{t\+1\}\)\\lesssim\\inf\_\{x\\in\\mathcal\{X\}\}\\sum\_\{t=1\}^\{T\}g\_\{t\}\(x\)\. In more detail,

∑t=1Tgt​\(x¯t\+1\)−infx∈𝒳∑t=1Tgt​\(x\)\\displaystyle\\sum\_\{t=1\}^\{T\}g\_\{t\}\(\\bar\{x\}\_\{t\+1\}\)\-\\inf\_\{x\\in\\mathcal\{X\}\}\\sum\_\{t=1\}^\{T\}g\_\{t\}\(x\)≤∑t=1Tgt​\(x¯t\+1\)−∑t=1Tgt​\(x¯T\+1\)\+\(α\+β​‖ρT​σ‖1\)\\displaystyle\\leq\\sum\_\{t=1\}^\{T\}g\_\{t\}\(\\bar\{x\}\_\{t\+1\}\)\-\\sum\_\{t=1\}^\{T\}g\_\{t\}\(\\bar\{x\}\_\{T\+1\}\)\+\(\\alpha\+\\beta\\\|\\rho\_\{T\}\\sigma\\\|\_\{1\}\)\(pluggingt=Tt=Tin \([14](https://arxiv.org/html/2606.02948#A1.E14)\)\)=∑t=1T−1gt​\(x¯t\+1\)−∑t=1T−1gt​\(x¯T\+1\)\+\(α\+β​‖ρT​σ‖1\)\\displaystyle=\\sum\_\{t=1\}^\{T\-1\}g\_\{t\}\(\\bar\{x\}\_\{t\+1\}\)\-\\sum\_\{t=1\}^\{T\-1\}g\_\{t\}\(\\bar\{x\}\_\{T\+1\}\)\+\(\\alpha\+\\beta\\\|\\rho\_\{T\}\\sigma\\\|\_\{1\}\)≤∑t=1T−1gt​\(x¯t\+1\)−∑t=1T−1gt​\(x¯T\)\+\(α\+β​‖ρT−1​σ‖1\)\+\(α\+β​‖ρT​σ‖1\)\\displaystyle\\leq\\sum\_\{t=1\}^\{T\-1\}g\_\{t\}\(\\bar\{x\}\_\{t\+1\}\)\-\\sum\_\{t=1\}^\{T\-1\}g\_\{t\}\(\\bar\{x\}\_\{T\}\)\+\(\\alpha\+\\beta\\\|\\rho\_\{T\-1\}\\sigma\\\|\_\{1\}\)\+\(\\alpha\+\\beta\\\|\\rho\_\{T\}\\sigma\\\|\_\{1\}\)\(pluggingt=T−1t=T\-1in \([14](https://arxiv.org/html/2606.02948#A1.E14)\)\)=∑t=1T−2gt​\(x¯t\+1\)−∑t=1T−2gt​\(x¯T\)\+\(α\+β​‖ρT−1​σ‖1\)\+\(α\+β​‖ρT​σ‖1\)\\displaystyle=\\sum\_\{t=1\}^\{T\-2\}g\_\{t\}\(\\bar\{x\}\_\{t\+1\}\)\-\\sum\_\{t=1\}^\{T\-2\}g\_\{t\}\(\\bar\{x\}\_\{T\}\)\+\(\\alpha\+\\beta\\\|\\rho\_\{T\-1\}\\sigma\\\|\_\{1\}\)\+\(\\alpha\+\\beta\\\|\\rho\_\{T\}\\sigma\\\|\_\{1\}\)⋮\\displaystyle\\;\\;\\vdots\(repeating all the way down\)≤g1​\(x¯2\)−g1​\(x¯3\)\+∑t=2T\(α\+β​‖ρt​σ‖1\)\\displaystyle\\leq g\_\{1\}\(\\bar\{x\}\_\{2\}\)\-g\_\{1\}\(\\bar\{x\}\_\{3\}\)\+\\sum\_\{t=2\}^\{T\}\(\\alpha\+\\beta\\\|\\rho\_\{t\}\\sigma\\\|\_\{1\}\)≤∑t=1T\(α\+β​‖ρt​σ‖1\)\\displaystyle\\leq\\sum\_\{t=1\}^\{T\}\(\\alpha\+\\beta\\\|\\rho\_\{t\}\\sigma\\\|\_\{1\}\)\(pluggingt=1t=1in \([14](https://arxiv.org/html/2606.02948#A1.E14)\)\)=α​T\+β​‖σ‖1​∑t=1Tρt\.\\displaystyle=\\alpha T\+\\beta\\\|\\sigma\\\|\_\{1\}\\sum\_\{t=1\}^\{T\}\\rho\_\{t\}\.\(eachρt≥0\\rho\_\{t\}\\geq 0\)Instantiating the above inequality withx=x⋆x=x^\{\\star\}, we get

∑t=1Tgt​\(x¯t\+1\)≤∑t=1Tgt​\(x⋆\)\+α​T\+β​‖σ‖1​∑t=1Tρt\\displaystyle\\sum\_\{t=1\}^\{T\}g\_\{t\}\(\\bar\{x\}\_\{t\+1\}\)\\leq\\sum\_\{t=1\}^\{T\}g\_\{t\}\(x^\{\\star\}\)\+\\alpha T\+\\beta\\\|\\sigma\\\|\_\{1\}\\sum\_\{t=1\}^\{T\}\\rho\_\{t\}⟹\\displaystyle\\implies\\quad∑t=1Tft​\(x¯t\+1\)−∑t=1T⟨\(ρt−ρt−1\)​σ,x¯t\+1⟩≤∑t=1Tft​\(x⋆\)−∑t=1T⟨\(ρt−ρt−1\)​σ,x⋆⟩\+α​T\+β​‖σ‖1​∑t=1Tρt\\displaystyle\\sum\_\{t=1\}^\{T\}f\_\{t\}\(\\bar\{x\}\_\{t\+1\}\)\-\\sum\_\{t=1\}^\{T\}\\langle\(\\rho\_\{t\}\-\\rho\_\{t\-1\}\)\\sigma,\\bar\{x\}\_\{t\+1\}\\rangle\\leq\\sum\_\{t=1\}^\{T\}f\_\{t\}\(x^\{\\star\}\)\-\\sum\_\{t=1\}^\{T\}\\langle\(\\rho\_\{t\}\-\\rho\_\{t\-1\}\)\\sigma,x^\{\\star\}\\rangle\+\\alpha T\+\\beta\\\|\\sigma\\\|\_\{1\}\\sum\_\{t=1\}^\{T\}\\rho\_\{t\}⟹\\displaystyle\\implies\\quad∑t=1T\(ft​\(x¯t\+1\)−ft​\(x⋆\)\)≤∑t=1T⟨\(ρt−ρt−1\)​σ,x¯t\+1−x⋆⟩\+α​T\+β​‖σ‖1​∑t=1Tρt\\displaystyle\\sum\_\{t=1\}^\{T\}\(f\_\{t\}\(\\bar\{x\}\_\{t\+1\}\)\-f\_\{t\}\(x^\{\\star\}\)\)\\leq\\sum\_\{t=1\}^\{T\}\\langle\(\\rho\_\{t\}\-\\rho\_\{t\-1\}\)\\sigma,\\bar\{x\}\_\{t\+1\}\-x^\{\\star\}\\rangle\+\\alpha T\+\\beta\\\|\\sigma\\\|\_\{1\}\\sum\_\{t=1\}^\{T\}\\rho\_\{t\}⟹\\displaystyle\\implies\\quad∑t=1T\(ft​\(x¯t\+1\)−ft​\(x⋆\)\)≤∑t=1T\|ρt−ρt−1\|​‖σ‖1​‖x¯t\+1−x⋆‖∞\+α​T\+β​‖σ‖1​∑t=1Tρt\\displaystyle\\sum\_\{t=1\}^\{T\}\(f\_\{t\}\(\\bar\{x\}\_\{t\+1\}\)\-f\_\{t\}\(x^\{\\star\}\)\)\\leq\\sum\_\{t=1\}^\{T\}\|\\rho\_\{t\}\-\\rho\_\{t\-1\}\|\\\|\\sigma\\\|\_\{1\}\\\|\\bar\{x\}\_\{t\+1\}\-x^\{\\star\}\\\|\_\{\\infty\}\+\\alpha T\+\\beta\\\|\\sigma\\\|\_\{1\}\\sum\_\{t=1\}^\{T\}\\rho\_\{t\}\(Hölder’s inequality\)⟹\\displaystyle\\implies\\quad∑t=1T\(ft​\(x¯t\+1\)−ft​\(x⋆\)\)≤D​‖σ‖1​ρT\+α​T\+β​‖σ‖1​∑t=1Tρt,\\displaystyle\\sum\_\{t=1\}^\{T\}\(f\_\{t\}\(\\bar\{x\}\_\{t\+1\}\)\-f\_\{t\}\(x^\{\\star\}\)\)\\leq D\\\|\\sigma\\\|\_\{1\}\\rho\_\{T\}\+\\alpha T\+\\beta\\\|\\sigma\\\|\_\{1\}\\sum\_\{t=1\}^\{T\}\\rho\_\{t\},where we used that𝒳\\mathcal\{X\}hasℓ∞\\ell\_\{\\infty\}diameterDD, and thatρ0,…,ρT\\rho\_\{0\},\\dots,\\rho\_\{T\}are non\-negative and non\-decreasing, withρ0=0\\rho\_\{0\}=0\. Substituting the bound above in \([13](https://arxiv.org/html/2606.02948#A1.E13)\), and taking expectation with respect toσ\\sigma, we get

𝔼σ⁡\[∑t=1Tft​\(xt\)−∑t=1Tft​\(x⋆\)\]\\displaystyle\\operatorname\{\{\\mathds\{E\}\}\}\_\{\\sigma\}\\left\[\\sum\_\{t=1\}^\{T\}f\_\{t\}\(x\_\{t\}\)\-\\sum\_\{t=1\}^\{T\}f\_\{t\}\(x^\{\\star\}\)\\right\]≤L​∑t=1T𝔼σ⁡\[‖xt−x¯t\+1‖1\]\+D​ρT​𝔼σ⁡\[‖σ‖1\]\+α​T\+𝔼σ⁡\[‖σ‖1\]⋅β​∑t=1Tρt\\displaystyle\\leq L\\sum\_\{t=1\}^\{T\}\\operatorname\{\{\\mathds\{E\}\}\}\_\{\\sigma\}\\left\[\\left\\\|x\_\{t\}\-\\bar\{x\}\_\{t\+1\}\\right\\\|\_\{1\}\\right\]\+D\\rho\_\{T\}\\operatorname\{\{\\mathds\{E\}\}\}\_\{\\sigma\}\\left\[\\\|\\sigma\\\|\_\{1\}\\right\]\+\\alpha T\+\\operatorname\{\{\\mathds\{E\}\}\}\_\{\\sigma\}\\left\[\\\|\\sigma\\\|\_\{1\}\\right\]\\cdot\\beta\\sum\_\{t=1\}^\{T\}\\rho\_\{t\}=L​∑t=1T𝔼σ⁡\[‖xt−x¯t\+1‖1\]\+d​D​ρT\+α​T\+d​β​∑t=1Tρt,\\displaystyle=L\\sum\_\{t=1\}^\{T\}\\operatorname\{\{\\mathds\{E\}\}\}\_\{\\sigma\}\\left\[\\left\\\|x\_\{t\}\-\\bar\{x\}\_\{t\+1\}\\right\\\|\_\{1\}\\right\]\+dD\\rho\_\{T\}\+\\alpha T\+d\\beta\\sum\_\{t=1\}^\{T\}\\rho\_\{t\},which was the claimed stability\-perturbation decomposition in \([12](https://arxiv.org/html/2606.02948#A1.E12)\)\.

Now, sincextx\_\{t\}andx¯t\+1\\bar\{x\}\_\{t\+1\}both use thesamenoise vectorρt​σ\\rho\_\{t\}\\sigma\(whose entries are i\.i\.d\. exponential random variables with parameter1/ρt1/\\rho\_\{t\}\), we can directly use the bound on the stability term established inSuggala and Netrapalli \[[2020](https://arxiv.org/html/2606.02948#bib.bib17), Theorem 1\]\. Specifically, they show that:

𝔼σ⁡\[‖xt−x¯t\+1‖1\]\\displaystyle\\operatorname\{\{\\mathds\{E\}\}\}\_\{\\sigma\}\\left\[\\left\\\|x\_\{t\}\-\\bar\{x\}\_\{t\+1\}\\right\\\|\_\{1\}\\right\]≤125​L​d2​Dρt\+β​ρt​d20​L\+2​β​d\+α20​L\.\\displaystyle\\leq\\frac\{125Ld^\{2\}D\}\{\\rho\_\{t\}\}\+\\frac\{\\beta\\rho\_\{t\}d\}\{20L\}\+2\\beta d\+\\frac\{\\alpha\}\{20L\}\.\(NC\)
On the other hand, we can also bound this term differently by considering the curvature ofFt=∑i=1tfiF\_\{t\}=\\sum\_\{i=1\}^\{t\}f\_\{i\}\. Namely, letStS\_\{t\}be the strong convexity constant ofFtF\_\{t\}with respect toℓ1\\ell\_\{1\}\(whereSt=0S\_\{t\}=0ifFtF\_\{t\}is not strongly convex\)\. Then note that the functionΦ​\(x\)=Ft​\(x\)−⟨ρt​σ,x⟩\\Phi\(x\)=F\_\{t\}\(x\)\-\\langle\\rho\_\{t\}\\sigma,x\\ranglealso has strong convexity constantStS\_\{t\}\.

Letzt∈arg​minx∈𝒳⁡Φ​\(x\)z\_\{t\}\\in\\operatorname\*\{arg\\,min\}\_\{x\\in\\mathcal\{X\}\}\\Phi\(x\)\. Sincex¯t\+1\\bar\{x\}\_\{t\+1\}also approximately minimizesΦ​\(x\)\\Phi\(x\), we have thatΦ​\(x¯t\+1\)−Φ​\(zt\)≤α\+β​‖ρt​σ‖1\\Phi\(\\bar\{x\}\_\{t\+1\}\)\-\\Phi\(z\_\{t\}\)\\leq\\alpha\+\\beta\\\|\\rho\_\{t\}\\sigma\\\|\_\{1\}\. Invoking the strong convexity inequality \([2](https://arxiv.org/html/2606.02948#S3.E2)\) withy=x¯t\+1y=\\bar\{x\}\_\{t\+1\}andx=ztx=z\_\{t\}, and using thatΦ​\(x\)\\Phi\(x\)is minimized atztz\_\{t\}, we get

Φ​\(x¯t\+1\)≥Φ​\(zt\)\+St2​‖x¯t\+1−zt‖12\\displaystyle\\Phi\(\\bar\{x\}\_\{t\+1\}\)\\geq\\Phi\(z\_\{t\}\)\+\\frac\{S\_\{t\}\}\{2\}\\\|\\bar\{x\}\_\{t\+1\}\-z\_\{t\}\\\|\_\{1\}^\{2\}⟹St2​‖x¯t\+1−zt‖12≤Φ​\(x¯t\+1\)−Φ​\(zt\)≤α\+β​‖ρt​σ‖1\\displaystyle\\implies\\,\\frac\{S\_\{t\}\}\{2\}\\\|\\bar\{x\}\_\{t\+1\}\-z\_\{t\}\\\|\_\{1\}^\{2\}\\leq\\Phi\(\\bar\{x\}\_\{t\+1\}\)\-\\Phi\(z\_\{t\}\)\\leq\\alpha\+\\beta\\\|\\rho\_\{t\}\\sigma\\\|\_\{1\}⟹‖x¯t\+1−zt‖1≤2​\(α\+β​‖ρt​σ‖1\)St\.\\displaystyle\\implies\\,\\\|\\bar\{x\}\_\{t\+1\}\-z\_\{t\}\\\|\_\{1\}\\leq\\sqrt\{\\frac\{2\(\\alpha\+\\beta\\\|\\rho\_\{t\}\\sigma\\\|\_\{1\}\)\}\{S\_\{t\}\}\}\.\(15\)But note also thatxtx\_\{t\}approximately minimizesFt−1​\(x\)−⟨ρt​σ,x⟩=Φ​\(x\)−ft​\(x\)F\_\{t\-1\}\(x\)\-\\langle\\rho\_\{t\}\\sigma,x\\rangle=\\Phi\(x\)\-f\_\{t\}\(x\)\. That is,

Φ​\(xt\)−ft​\(xt\)≤infx∈𝒳\(Φ​\(x\)−ft​\(x\)\)\+α\+β​‖ρt​σ‖1≤Φ​\(zt\)−ft​\(zt\)\+α\+β​‖ρt​σ‖1\.\\displaystyle\\Phi\(x\_\{t\}\)\-f\_\{t\}\(x\_\{t\}\)\\leq\\inf\_\{x\\in\\mathcal\{X\}\}\(\\Phi\(x\)\-f\_\{t\}\(x\)\)\+\\alpha\+\\beta\\\|\\rho\_\{t\}\\sigma\\\|\_\{1\}\\leq\\Phi\(z\_\{t\}\)\-f\_\{t\}\(z\_\{t\}\)\+\\alpha\+\\beta\\\|\\rho\_\{t\}\\sigma\\\|\_\{1\}\.This means that

Φ​\(xt\)−Φ​\(zt\)≤α\+β​‖ρt​σ‖1\+ft​\(xt\)−ft​\(zt\)≤α\+β​‖ρt​σ‖1\+L​‖xt−zt‖1,\\displaystyle\\Phi\(x\_\{t\}\)\-\\Phi\(z\_\{t\}\)\\leq\\alpha\+\\beta\\\|\\rho\_\{t\}\\sigma\\\|\_\{1\}\+f\_\{t\}\(x\_\{t\}\)\-f\_\{t\}\(z\_\{t\}\)\\leq\\alpha\+\\beta\\\|\\rho\_\{t\}\\sigma\\\|\_\{1\}\+L\\\|x\_\{t\}\-z\_\{t\}\\\|\_\{1\},\(16\)where we used Lipschitzness in the last inequality\. Invoking the strong convexity inequality \([2](https://arxiv.org/html/2606.02948#S3.E2)\) again withy=xty=x\_\{t\}andx=ztx=z\_\{t\}, and using thatΦ​\(x\)\\Phi\(x\)is minimized atztz\_\{t\}, we get

Φ​\(xt\)≥Φ​\(zt\)\+St2​‖xt−zt‖12\\displaystyle\\Phi\(x\_\{t\}\)\\geq\\Phi\(z\_\{t\}\)\+\\frac\{S\_\{t\}\}\{2\}\\\|x\_\{t\}\-z\_\{t\}\\\|\_\{1\}^\{2\}⟹St2​‖xt−zt‖12≤Φ​\(xt\)−Φ​\(zt\)\\displaystyle\\implies\\,\\frac\{S\_\{t\}\}\{2\}\\\|x\_\{t\}\-z\_\{t\}\\\|\_\{1\}^\{2\}\\leq\\Phi\(x\_\{t\}\)\-\\Phi\(z\_\{t\}\)⟹St2​‖xt−zt‖12≤α\+β​‖ρt​σ‖1\+L​‖xt−zt‖1\\displaystyle\\implies\\,\\frac\{S\_\{t\}\}\{2\}\\\|x\_\{t\}\-z\_\{t\}\\\|\_\{1\}^\{2\}\\leq\\alpha\+\\beta\\\|\\rho\_\{t\}\\sigma\\\|\_\{1\}\+L\\\|x\_\{t\}\-z\_\{t\}\\\|\_\{1\}\(using \([16](https://arxiv.org/html/2606.02948#A1.E16)\)\)⟹‖xt−zt‖1≤L\+L2\+2​St​\(α\+β​‖ρt​σ‖1\)St\\displaystyle\\implies\\,\\\|x\_\{t\}\-z\_\{t\}\\\|\_\{1\}\\leq\\frac\{L\+\\sqrt\{L^\{2\}\+2S\_\{t\}\(\\alpha\+\\beta\\\|\\rho\_\{t\}\\sigma\\\|\_\{1\}\)\}\}\{S\_\{t\}\}⟹‖xt−zt‖1≤2​LSt\+2​\(α\+β​‖ρt​σ‖1\)St,\\displaystyle\\implies\\,\\\|x\_\{t\}\-z\_\{t\}\\\|\_\{1\}\\leq\\frac\{2L\}\{S\_\{t\}\}\+\\sqrt\{\\frac\{2\(\\alpha\+\\beta\\\|\\rho\_\{t\}\\sigma\\\|\_\{1\}\)\}\{S\_\{t\}\}\},\(17\)where in the second\-to\-last step, we solved a quadratic inequality in the variable‖xt−zt‖1\\\|x\_\{t\}\-z\_\{t\}\\\|\_\{1\}, and in the last step, we used thata\+b≤a\+b\\sqrt\{a\+b\}\\leq\\sqrt\{a\}\+\\sqrt\{b\}\.

Combining \([15](https://arxiv.org/html/2606.02948#A1.E15)\) and \([17](https://arxiv.org/html/2606.02948#A1.E17)\) with the triangle inequality, we get that

‖xt−x¯t\+1‖1≤2​LSt\+2​2​\(α\+β​‖ρt​σ‖1\)St\.\\displaystyle\\\|x\_\{t\}\-\\bar\{x\}\_\{t\+1\}\\\|\_\{1\}\\leq\\frac\{2L\}\{S\_\{t\}\}\+2\\sqrt\{\\frac\{2\(\\alpha\+\\beta\\\|\\rho\_\{t\}\\sigma\\\|\_\{1\}\)\}\{S\_\{t\}\}\}\.Taking expectation with respect toσ\\sigma, we get

𝔼σ⁡\[‖xt−x¯t\+1‖1\]\\displaystyle\\operatorname\{\{\\mathds\{E\}\}\}\_\{\\sigma\}\\left\[\\left\\\|x\_\{t\}\-\\bar\{x\}\_\{t\+1\}\\right\\\|\_\{1\}\\right\]≤2​LSt\+2​2St⋅𝔼σ⁡\[α\+β​‖ρt​σ‖1\]\\displaystyle\\leq\\frac\{2L\}\{S\_\{t\}\}\+2\\sqrt\{\\frac\{2\}\{S\_\{t\}\}\}\\cdot\\operatorname\{\{\\mathds\{E\}\}\}\_\{\\sigma\}\\left\[\\sqrt\{\\alpha\+\\beta\\\|\\rho\_\{t\}\\sigma\\\|\_\{1\}\}\\right\]≤2​LSt\+2​2St⋅𝔼σ⁡\[α\+β​‖ρt​σ‖1\]\\displaystyle\\leq\\frac\{2L\}\{S\_\{t\}\}\+2\\sqrt\{\\frac\{2\}\{S\_\{t\}\}\}\\cdot\\sqrt\{\\operatorname\{\{\\mathds\{E\}\}\}\_\{\\sigma\}\\left\[\\alpha\+\\beta\\\|\\rho\_\{t\}\\sigma\\\|\_\{1\}\\right\]\}\(Jensen’s inequality\)=2​LSt\+2​2​\(α\+β​ρt​d\)St\.\\displaystyle=\\frac\{2L\}\{S\_\{t\}\}\+2\\sqrt\{\\frac\{2\(\\alpha\+\\beta\\rho\_\{t\}d\)\}\{S\_\{t\}\}\}\.\(SC\)Combining this strongly\-convex stability bound \(SC\) with the fallback non\-convex stability bound \(NC\) from above, and substituting into the stability\-perturbation decomposition \([12](https://arxiv.org/html/2606.02948#A1.E12)\) of the regret, we get that

𝔼σ⁡\[∑t=1Tft​\(xt\)−infx∈𝒳∑t=1Tft​\(x\)\]≤\\displaystyle\\operatorname\{\{\\mathds\{E\}\}\}\_\{\\sigma\}\\left\[\\sum\_\{t=1\}^\{T\}f\_\{t\}\(x\_\{t\}\)\-\\inf\_\{x\\in\\mathcal\{X\}\}\\sum\_\{t=1\}^\{T\}f\_\{t\}\(x\)\\right\]\\leq∑t=1Tmin⁡\{125​L2​d2​Dρt\+α\+β​ρt​d20\+2​β​d​L,2​L2St\+2​L​2​\(α\+β​ρt​d\)St\}\\displaystyle\\sum\_\{t=1\}^\{T\}\\min\\left\\\{\\frac\{125L^\{2\}d^\{2\}D\}\{\\rho\_\{t\}\}\+\\frac\{\\alpha\+\\beta\\rho\_\{t\}d\}\{20\}\+2\\beta dL,\\frac\{2L^\{2\}\}\{S\_\{t\}\}\+2L\\sqrt\{\\frac\{2\(\\alpha\+\\beta\\rho\_\{t\}d\)\}\{S\_\{t\}\}\}\\right\\\}\+d​D​ρT\+α​T\+d​β​∑t=1Tρt,\\displaystyle\\qquad\+dD\\rho\_\{T\}\+\\alpha T\+d\\beta\\sum\_\{t=1\}^\{T\}\\rho\_\{t\},which is the desired bound\. ∎

We next restate and prove[Theorem2](https://arxiv.org/html/2606.02948#Thmtheorem2)\.

See[2](https://arxiv.org/html/2606.02948#Thmtheorem2)

###### Proof\.

Recall that we setρ1=r\\rho\_\{1\}=r, and fort≥2t\\geq 2,

ρt=min​arg​infρ≥r⁡\[∑i=1t−1min⁡\{125​L2​d2​Dρ,2​L2Si\}\+d​D​ρ\]⏟:=Ψt−1​\(ρ\),\\displaystyle\\rho\_\{t\}=\\min\\operatorname\*\{arg\\,inf\}\_\{\\rho\\geq r\}\\underbrace\{\\left\[\\sum\_\{i=1\}^\{t\-1\}\\min\\left\\\{\\frac\{125L^\{2\}d^\{2\}D\}\{\\rho\},\\frac\{2L^\{2\}\}\{S\_\{i\}\}\\right\\\}\+dD\\rho\\right\]\}\_\{:=\\Psi\_\{t\-1\}\(\\rho\)\},where we defined the objective function inside the parentheses to beΨt−1​\(ρ\)\\Psi\_\{t\-1\}\(\\rho\)\. It is clear thatρt\\rho\_\{t\}depends only onS1,…,St−1S\_\{1\},\\dots,S\_\{t\-1\}\. We will now argue thatρ1≤⋯≤ρT\\rho\_\{1\}\\leq\\dots\\leq\\rho\_\{T\}\. Note thatr=ρ1≤ρ2r=\\rho\_\{1\}\\leq\\rho\_\{2\}holds immediately, since the minimization is overρ≥r\\rho\\geq r\.

Now, fixt≥3t\\geq 3, and consider anyy∈\[r,ρt−1\)y\\in\[r,\\rho\_\{t\-1\}\)\. Sinceρt−1\\rho\_\{t\-1\}is thesmallestinfimizer ofΨt−2​\(ρ\)\\Psi\_\{t\-2\}\(\\rho\), it must be the case that

Ψt−2​\(y\)\>Ψt−2​\(ρt−1\)\.\\displaystyle\\Psi\_\{t\-2\}\(y\)\>\\Psi\_\{t\-2\}\(\\rho\_\{t\-1\}\)\.Therefore,

Ψt−1​\(y\)\\displaystyle\\Psi\_\{t\-1\}\(y\)=Ψt−2​\(y\)\+min⁡\{125​L2​d2​Dy,2​L2St−1\}\\displaystyle=\\Psi\_\{t\-2\}\(y\)\+\\min\\left\\\{\\frac\{125L^\{2\}d^\{2\}D\}\{y\},\\frac\{2L^\{2\}\}\{S\_\{t\-1\}\}\\right\\\}\>Ψt−2​\(ρt−1\)\+min⁡\{125​L2​d2​Dρt−1,2​L2St−1\}=Ψt−1​\(ρt−1\),\\displaystyle\>\\Psi\_\{t\-2\}\(\\rho\_\{t\-1\}\)\+\\min\\left\\\{\\frac\{125L^\{2\}d^\{2\}D\}\{\\rho\_\{t\-1\}\},\\frac\{2L^\{2\}\}\{S\_\{t\-1\}\}\\right\\\}=\\Psi\_\{t\-1\}\(\\rho\_\{t\-1\}\),where we used that the functionmin⁡\{125​L2​d2​Dρ,2​L2St−1\}\\min\\left\\\{\\frac\{125L^\{2\}d^\{2\}D\}\{\\rho\},\\frac\{2L^\{2\}\}\{S\_\{t\-1\}\}\\right\\\}is non\-increasing inρ\\rho\. Thus, any feasible minimizer ofΨt−1\\Psi\_\{t\-1\}must at least beρt−1\\rho\_\{t\-1\}, implying thatρt≥ρt−1\\rho\_\{t\}\\geq\\rho\_\{t\-1\}\.

Now, define thecleanoffline optimum, namely the best regret upper bound in hindsight without any error terms, to be

OPTT0​\(r\):=infr≤ρ1≤⋯≤ρT\[∑t=1Tmin⁡\{125​L2​d2​Dρt,2​L2St\}\+d​D​ρT\]\.\\displaystyle\\mathrm\{OPT\}^\{0\}\_\{T\}\(r\):=\\inf\_\{r\\leq\\rho\_\{1\}\\leq\\dots\\leq\\rho\_\{T\}\}\\left\[\\sum\_\{t=1\}^\{T\}\\min\\left\\\{\\frac\{125L^\{2\}d^\{2\}D\}\{\\rho\_\{t\}\},\\frac\{2L^\{2\}\}\{S\_\{t\}\}\\right\\\}\+dD\\rho\_\{T\}\\right\]\.\(18\)We claim that

OPTT0​\(r\)=infρ≥r\[∑t=1Tmin⁡\{125​L2​d2​Dρ,2​L2St\}\+d​D​ρ\]=infρ≥rΨT​\(ρ\)\.\\displaystyle\\mathrm\{OPT\}^\{0\}\_\{T\}\(r\)=\\inf\_\{\\rho\\geq r\}\\left\[\\sum\_\{t=1\}^\{T\}\\min\\left\\\{\\frac\{125L^\{2\}d^\{2\}D\}\{\\rho\},\\frac\{2L^\{2\}\}\{S\_\{t\}\}\\right\\\}\+dD\\rho\\right\]=\\inf\_\{\\rho\\geq r\}\\Psi\_\{T\}\(\\rho\)\.\(19\)This follows simply by noting that, for every feasibler≤ρ1≤⋯≤ρTr\\leq\\rho\_\{1\}\\leq\\dots\\leq\\rho\_\{T\}, we can simply setρt=ρT\\rho\_\{t\}=\\rho\_\{T\}for everytt; this keeps the sequence feasible, and does not increase any individual term inside the summation\.

#### Be\-the\-leader on clean sequence\.

We will now argue that the sequence ofρt\\rho\_\{t\}’s above has small regret on the sequence of clean objective functions, compared toOPTT0​\(r\)\\mathrm\{OPT\}^\{0\}\_\{T\}\(r\)\. This is the standard be\-the\-leader analysis, and proceeds as follows: letg0​\(ρ\):=d​D​ρg\_\{0\}\(\\rho\):=dD\\rho, andgt​\(ρ\)=min⁡\{125​L2​d2​Dρ,2​L2St\}g\_\{t\}\(\\rho\)=\\min\\left\\\{\\frac\{125L^\{2\}d^\{2\}D\}\{\\rho\},\\frac\{2L^\{2\}\}\{S\_\{t\}\}\\right\\\}fort≥1t\\geq 1\. By definition, for anyi∈\{1,…,T\}i\\in\\\{1,\\dots,T\\\}:

∑t=0igt​\(ρi\+1\)=Ψi​\(ρi\+1\)=infρ≥rΨi​\(ρ\),\\displaystyle\\sum\_\{t=0\}^\{i\}g\_\{t\}\(\\rho\_\{i\+1\}\)=\\Psi\_\{i\}\(\\rho\_\{i\+1\}\)=\\inf\_\{\\rho\\geq r\}\\Psi\_\{i\}\(\\rho\),\(20\)and therefore,

∑t=0Tgt​\(ρt\+1\)−infρ≥rΨT​\(ρ\)\\displaystyle\\sum\_\{t=0\}^\{T\}g\_\{t\}\(\\rho\_\{t\+1\}\)\-\\inf\_\{\\rho\\geq r\}\\Psi\_\{T\}\(\\rho\)=∑t=0Tgt​\(ρt\+1\)−∑t=0Tgt​\(ρT\+1\)\\displaystyle=\\sum\_\{t=0\}^\{T\}g\_\{t\}\(\\rho\_\{t\+1\}\)\-\\sum\_\{t=0\}^\{T\}g\_\{t\}\(\\rho\_\{T\+1\}\)=∑t=0T−1gt​\(ρt\+1\)−∑t=0T−1gt​\(ρT\+1\)\\displaystyle=\\sum\_\{t=0\}^\{T\-1\}g\_\{t\}\(\\rho\_\{t\+1\}\)\-\\sum\_\{t=0\}^\{T\-1\}g\_\{t\}\(\\rho\_\{T\+1\}\)≤∑t=0T−1gt​\(ρt\+1\)−∑t=0T−1gt​\(ρT\)\\displaystyle\\leq\\sum\_\{t=0\}^\{T\-1\}g\_\{t\}\(\\rho\_\{t\+1\}\)\-\\sum\_\{t=0\}^\{T\-1\}g\_\{t\}\(\\rho\_\{T\}\)\(from \([20](https://arxiv.org/html/2606.02948#A1.E20)\)\)=∑t=0T−2gt​\(ρt\+1\)−∑t=0T−2gt​\(ρT\)\\displaystyle=\\sum\_\{t=0\}^\{T\-2\}g\_\{t\}\(\\rho\_\{t\+1\}\)\-\\sum\_\{t=0\}^\{T\-2\}g\_\{t\}\(\\rho\_\{T\}\)⋮\\displaystyle\\;\\;\\vdots\(repeating all the way down\)≤g0​\(ρ1\)−g0​\(ρ2\)\\displaystyle\\leq g\_\{0\}\(\\rho\_\{1\}\)\-g\_\{0\}\(\\rho\_\{2\}\)=d​D​\(ρ1−ρ2\)\\displaystyle=dD\(\\rho\_\{1\}\-\\rho\_\{2\}\)=d​D​\(r−ρ2\)≤0\.\\displaystyle=dD\(r\-\\rho\_\{2\}\)\\leq 0\.\(sinceρ1=r\\rho\_\{1\}=r\)Thus, we get that

g0​\(ρ1\)\+∑t=1Tgt​\(ρt\+1\)−OPTT0​\(r\)≤0⟹∑t=1Tgt​\(ρt\+1\)≤OPTT0​\(r\)−d​D​r\.\\displaystyle g\_\{0\}\(\\rho\_\{1\}\)\+\\sum\_\{t=1\}^\{T\}g\_\{t\}\(\\rho\_\{t\+1\}\)\-\\mathrm\{OPT\}^\{0\}\_\{T\}\(r\)\\leq 0\\quad\\implies\\quad\\sum\_\{t=1\}^\{T\}g\_\{t\}\(\\rho\_\{t\+1\}\)\\leq\\mathrm\{OPT\}^\{0\}\_\{T\}\(r\)\-dDr\.\(21\)

#### Actual regret on clean sequence\.

Note that \([21](https://arxiv.org/html/2606.02948#A1.E21)\) benchmarks the performance of playingρt\+1\\rho\_\{t\+1\}at time steptt, but actually, we want to benchmark the performance of playingρt\\rho\_\{t\}\. For this, observe that for anyt≥1t\\geq 1,

gt​\(ρt\)−gt​\(ρt\+1\)\\displaystyle g\_\{t\}\(\\rho\_\{t\}\)\-g\_\{t\}\(\\rho\_\{t\+1\}\)=min⁡\{125​L2​d2​Dρt,2​L2St\}−min⁡\{125​L2​d2​Dρt\+1,2​L2St\}\\displaystyle=\\min\\left\\\{\\frac\{125L^\{2\}d^\{2\}D\}\{\\rho\_\{t\}\},\\frac\{2L^\{2\}\}\{S\_\{t\}\}\\right\\\}\-\\min\\left\\\{\\frac\{125L^\{2\}d^\{2\}D\}\{\\rho\_\{t\+1\}\},\\frac\{2L^\{2\}\}\{S\_\{t\}\}\\right\\\}≤125​L2​d2​Dρt−125​L2​d2​Dρt\+1,\\displaystyle\\leq\\frac\{125L^\{2\}d^\{2\}D\}\{\\rho\_\{t\}\}\-\\frac\{125L^\{2\}d^\{2\}D\}\{\\rho\_\{t\+1\}\},where we used thatρt≤ρt\+1\\rho\_\{t\}\\leq\\rho\_\{t\+1\}\. Summing overtt, the sum telescopes, and we get

∑t=1T\(gt​\(ρt\)−gt​\(ρt\+1\)\)≤125​L2​d2​Dρ1−125​L2​d2​DρT\+1≤125​L2​d2​Dr\.\\displaystyle\\sum\_\{t=1\}^\{T\}\\left\(g\_\{t\}\(\\rho\_\{t\}\)\-g\_\{t\}\(\\rho\_\{t\+1\}\)\\right\)\\leq\\frac\{125L^\{2\}d^\{2\}D\}\{\\rho\_\{1\}\}\-\\frac\{125L^\{2\}d^\{2\}D\}\{\\rho\_\{T\+1\}\}\\leq\\frac\{125L^\{2\}d^\{2\}D\}\{r\}\.Substituting this in \([21](https://arxiv.org/html/2606.02948#A1.E21)\), we get

∑t=1Tgt​\(ρt\)\\displaystyle\\sum\_\{t=1\}^\{T\}g\_\{t\}\(\\rho\_\{t\}\)≤OPTT0​\(r\)−d​D​r\+125​L2​d2​Dr\.\\displaystyle\\leq\\mathrm\{OPT\}^\{0\}\_\{T\}\(r\)\-dDr\+\\frac\{125L^\{2\}d^\{2\}D\}\{r\}\.Folding in the terminal termd​D​ρTdD\\rho\_\{T\}on both sides gives

d​D​ρT\+∑t=1Tgt​\(ρt\)\\displaystyle dD\\rho\_\{T\}\+\\sum\_\{t=1\}^\{T\}g\_\{t\}\(\\rho\_\{t\}\)≤OPTT0​\(r\)−d​D​r\+125​L2​d2​Dr\+d​D​ρT\\displaystyle\\leq\\mathrm\{OPT\}^\{0\}\_\{T\}\(r\)\-dDr\+\\frac\{125L^\{2\}d^\{2\}D\}\{r\}\+dD\\rho\_\{T\}≤OPTT0​\(r\)−d​D​r\+125​L2​d2​Dr\+d​D​ρT\+1\\displaystyle\\leq\\mathrm\{OPT\}^\{0\}\_\{T\}\(r\)\-dDr\+\\frac\{125L^\{2\}d^\{2\}D\}\{r\}\+dD\\rho\_\{T\+1\}≤OPTT0​\(r\)−d​D​r\+125​L2​d2​Dr\+d​D​ρT\+1\+∑t=1Tgt​\(ρT\+1\)\\displaystyle\\leq\\mathrm\{OPT\}^\{0\}\_\{T\}\(r\)\-dDr\+\\frac\{125L^\{2\}d^\{2\}D\}\{r\}\+dD\\rho\_\{T\+1\}\+\\sum\_\{t=1\}^\{T\}g\_\{t\}\(\\rho\_\{T\+1\}\)=2​O​P​TT0​\(r\)−d​D​r\+125​L2​d2​Dr\.\\displaystyle=2\\mathrm\{OPT\}^\{0\}\_\{T\}\(r\)\-dDr\+\\frac\{125L^\{2\}d^\{2\}D\}\{r\}\.\(by definition ofρT\+1\\rho\_\{T\+1\}andOPTT0​\(r\)\\mathrm\{OPT\}^\{0\}\_\{T\}\(r\)\)Usingd​D​r≤OPTT0​\(r\)dDr\\leq\\mathrm\{OPT\}^\{0\}\_\{T\}\(r\)further gives

d​D​ρT\+∑t=1Tgt​\(ρt\)≤C⋅OPTT0​\(r\),\\displaystyle dD\\rho\_\{T\}\+\\sum\_\{t=1\}^\{T\}g\_\{t\}\(\\rho\_\{t\}\)\\leq C\\cdot\\mathrm\{OPT\}^\{0\}\_\{T\}\(r\),\(22\)whereC=max⁡\(2,1\+125​L2​dr2\)C=\\max\\left\(2,1\+\\frac\{125L^\{2\}d\}\{r^\{2\}\}\\right\)\.

#### RelatingOPTT0​\(r\)\\mathrm\{OPT\}^\{0\}\_\{T\}\(r\)toOPTTα,β​\(r\)\\mathrm\{OPT\}^\{\\alpha,\\beta\}\_\{T\}\(r\)\.

Recall the definition ofOPTTα,β​\(r\)\\mathrm\{OPT\}^\{\\alpha,\\beta\}\_\{T\}\(r\):

OPTTα,β​\(r\):=infr≤ρ1≤⋯≤ρT\\displaystyle\\mathrm\{OPT\}^\{\\alpha,\\beta\}\_\{T\}\(r\):=\\inf\_\{r\\leq\\rho\_\{1\}\\leq\\dots\\leq\\rho\_\{T\}\}\[∑t=1Tmin\{125​L2​d2​Dρt\+β​ρt​d20\+2Lβd\+α20,2​L2St\+2L2​\(α\+β​ρt​d\)St\}\\displaystyle\\left\[\\sum\_\{t=1\}^\{T\}\\min\\left\\\{\\frac\{125L^\{2\}d^\{2\}D\}\{\\rho\_\{t\}\}\+\\frac\{\\beta\\rho\_\{t\}d\}\{20\}\+2L\\beta d\+\\frac\{\\alpha\}\{20\},\\frac\{2L^\{2\}\}\{S\_\{t\}\}\+2L\\sqrt\{\\frac\{2\(\\alpha\+\\beta\\rho\_\{t\}d\)\}\{S\_\{t\}\}\}\\right\\\}\\right\.\+dDρT\+αT\+dβ∑t=1Tρt\],\\displaystyle\\qquad\\qquad\\left\.\+\\,dD\\rho\_\{T\}\+\\alpha T\+d\\beta\\sum\_\{t=1\}^\{T\}\\rho\_\{t\}\\right\],and note that for every feasibleρ1≤⋯≤ρT\\rho\_\{1\}\\leq\\dots\\leq\\rho\_\{T\},

∑t=1Tmin⁡\{125​L2​d2​Dρt\+β​ρt​d20\+2​L​β​d\+α20,2​L2St\+2​L​2​\(α\+β​ρt​d\)St\}\+d​D​ρT\+α​T\+d​β​∑t=1Tρt\\displaystyle\\sum\_\{t=1\}^\{T\}\\min\\left\\\{\\frac\{125L^\{2\}d^\{2\}D\}\{\\rho\_\{t\}\}\+\\frac\{\\beta\\rho\_\{t\}d\}\{20\}\+2L\\beta d\+\\frac\{\\alpha\}\{20\},\\frac\{2L^\{2\}\}\{S\_\{t\}\}\+2L\\sqrt\{\\frac\{2\(\\alpha\+\\beta\\rho\_\{t\}d\)\}\{S\_\{t\}\}\}\\right\\\}\+dD\\rho\_\{T\}\+\\alpha T\+d\\beta\\sum\_\{t=1\}^\{T\}\\rho\_\{t\}≥∑t=1Tgt​\(ρt\)\+d​D​ρT≥∑t=1Tgt​\(ρT\)\+d​D​ρT≥OPTT0​\(r\),\\displaystyle\\geq\\sum\_\{t=1\}^\{T\}g\_\{t\}\(\\rho\_\{t\}\)\+dD\\rho\_\{T\}\\geq\\sum\_\{t=1\}^\{T\}g\_\{t\}\(\\rho\_\{T\}\)\+dD\\rho\_\{T\}\\geq\\mathrm\{OPT\}^\{0\}\_\{T\}\(r\),where we used thatgtg\_\{t\}is non\-increasing\. Infimizing over all feasibleρ1≤⋯≤ρT\\rho\_\{1\}\\leq\\dots\\leq\\rho\_\{T\}, we get that

OPTTα,β​\(r\)≥OPTT0​\(r\)\.\\displaystyle\\mathrm\{OPT\}^\{\\alpha,\\beta\}\_\{T\}\(r\)\\geq\\mathrm\{OPT\}^\{0\}\_\{T\}\(r\)\.\(23\)

#### Upper\-bounding the regret with respect toOPTTα,β​\(r\)\\mathrm\{OPT\}^\{\\alpha,\\beta\}\_\{T\}\(r\)\.

Recall that we upper\-bounded the “clean terms” of the regret of ourρt\\rho\_\{t\}schedule in terms of the clean offline optimum in \([22](https://arxiv.org/html/2606.02948#A1.E22)\)\. Furthermore, we upper\-bounded the clean offline optimum with the true offline optimum in \([23](https://arxiv.org/html/2606.02948#A1.E23)\)\. It remains to fold in the “non\-clean” terms that appear in the regret of ourρt\\rho\_\{t\}schedule, and upper\-bound these in terms ofOPTTα,β​\(r\)\\mathrm\{OPT\}^\{\\alpha,\\beta\}\_\{T\}\(r\)\.

Towards this, forρ≥r\\rho\\geq r, consider the function

Mt​\(ρ\):=min⁡\{125​L2​d2​Dρ\+β​ρ​d20\+2​L​β​d\+α20,2​L2St\+2​L​2​\(α\+β​ρ​d\)St\}\.\\displaystyle M\_\{t\}\(\\rho\):=\\min\\left\\\{\\frac\{125L^\{2\}d^\{2\}D\}\{\\rho\}\+\\frac\{\\beta\\rho d\}\{20\}\+2L\\beta d\+\\frac\{\\alpha\}\{20\},\\frac\{2L^\{2\}\}\{S\_\{t\}\}\+2L\\sqrt\{\\frac\{2\(\\alpha\+\\beta\\rho d\)\}\{S\_\{t\}\}\}\\right\\\}\.Recall thatgt​\(ρ\)=min⁡\{125​L2​d2​Dρ,2​L2St\}g\_\{t\}\(\\rho\)=\\min\\left\\\{\\frac\{125L^\{2\}d^\{2\}D\}\{\\rho\},\\frac\{2L^\{2\}\}\{S\_\{t\}\}\\right\\\}\. Suppose it is the case that125​L2​d2​Dρ≤2​L2St\\frac\{125L^\{2\}d^\{2\}D\}\{\\rho\}\\leq\\frac\{2L^\{2\}\}\{S\_\{t\}\}\. Then,

Mt​\(ρ\)≤125​L2​d2​Dρ\+β​ρ​d20\+2​L​β​d\+α20=gt​\(ρ\)\+β​ρ​d20\+2​L​β​d\+α20\.\\displaystyle M\_\{t\}\(\\rho\)\\leq\\frac\{125L^\{2\}d^\{2\}D\}\{\\rho\}\+\\frac\{\\beta\\rho d\}\{20\}\+2L\\beta d\+\\frac\{\\alpha\}\{20\}=g\_\{t\}\(\\rho\)\+\\frac\{\\beta\\rho d\}\{20\}\+2L\\beta d\+\\frac\{\\alpha\}\{20\}\.On the other hand, suppose that125​L2​d2​Dρ\>2​L2St\\frac\{125L^\{2\}d^\{2\}D\}\{\\rho\}\>\\frac\{2L^\{2\}\}\{S\_\{t\}\}\. Then,

Mt​\(ρ\)≤2​L2St\+2​L​2​\(α\+β​ρ​d\)St=gt​\(ρ\)\+2​gt​\(ρ\)​\(α\+β​ρ​d\)\.\\displaystyle M\_\{t\}\(\\rho\)\\leq\\frac\{2L^\{2\}\}\{S\_\{t\}\}\+2L\\sqrt\{\\frac\{2\(\\alpha\+\\beta\\rho d\)\}\{S\_\{t\}\}\}=g\_\{t\}\(\\rho\)\+2\\sqrt\{g\_\{t\}\(\\rho\)\(\\alpha\+\\beta\\rho d\)\}\.Therefore, the following bound always holds:

Mt​\(ρ\)≤gt​\(ρ\)\+β​ρ​d20\+2​L​β​d\+α20\+2​gt​\(ρ\)​\(α\+β​ρ​d\)\.\\displaystyle M\_\{t\}\(\\rho\)\\leq g\_\{t\}\(\\rho\)\+\\frac\{\\beta\\rho d\}\{20\}\+2L\\beta d\+\\frac\{\\alpha\}\{20\}\+2\\sqrt\{g\_\{t\}\(\\rho\)\(\\alpha\+\\beta\\rho d\)\}\.Instantiating this inequality for our noise\-scale scheduleρ1,…,ρT\\rho\_\{1\},\\dots,\\rho\_\{T\}, and summing, we get

∑t=1TMt​\(ρt\)\\displaystyle\\sum\_\{t=1\}^\{T\}M\_\{t\}\(\\rho\_\{t\}\)≤∑t=1Tgt​\(ρt\)\+β​d20​∑t=1Tρt\+2​L​β​d​T\+α​T20\+2​∑t=1Tgt​\(ρt\)​\(α\+β​ρt​d\)\\displaystyle\\leq\\sum\_\{t=1\}^\{T\}g\_\{t\}\(\\rho\_\{t\}\)\+\\frac\{\\beta d\}\{20\}\\sum\_\{t=1\}^\{T\}\\rho\_\{t\}\+2L\\beta dT\+\\frac\{\\alpha T\}\{20\}\+2\\sum\_\{t=1\}^\{T\}\\sqrt\{g\_\{t\}\(\\rho\_\{t\}\)\(\\alpha\+\\beta\\rho\_\{t\}d\)\}≤∑t=1Tgt​\(ρt\)\+β​d20​∑t=1Tρt\+2​L​β​d​T\+α​T20\+2​\(∑t=1Tgt​\(ρt\)\)​\(∑t=1T\(α\+β​ρt​d\)\)\.\\displaystyle\\leq\\sum\_\{t=1\}^\{T\}g\_\{t\}\(\\rho\_\{t\}\)\+\\frac\{\\beta d\}\{20\}\\sum\_\{t=1\}^\{T\}\\rho\_\{t\}\+2L\\beta dT\+\\frac\{\\alpha T\}\{20\}\+2\\sqrt\{\\left\(\\sum\_\{t=1\}^\{T\}g\_\{t\}\(\\rho\_\{t\}\)\\right\)\\left\(\\sum\_\{t=1\}^\{T\}\(\\alpha\+\\beta\\rho\_\{t\}d\)\\right\)\}\.\(Cauchy\-Schwarz inequality\)Adding in the perturbation terms from \([12](https://arxiv.org/html/2606.02948#A1.E12)\), we get that

∑t=1TMt​\(ρt\)\+d​D​ρT\+α​T\+d​β​∑t=1Tρt\\displaystyle\\sum\_\{t=1\}^\{T\}M\_\{t\}\(\\rho\_\{t\}\)\+dD\\rho\_\{T\}\+\\alpha T\+d\\beta\\sum\_\{t=1\}^\{T\}\\rho\_\{t\}≤∑t=1Tgt​\(ρt\)\+d​D​ρT\+21​β​d20​∑t=1Tρt\+2​L​β​d​T\+21​α​T20\+2​\(∑t=1Tgt​\(ρt\)\)​\(∑t=1T\(α\+β​ρt​d\)\)\\displaystyle\\leq\\sum\_\{t=1\}^\{T\}g\_\{t\}\(\\rho\_\{t\}\)\+dD\\rho\_\{T\}\+\\frac\{21\\beta d\}\{20\}\\sum\_\{t=1\}^\{T\}\\rho\_\{t\}\+2L\\beta dT\+\\frac\{21\\alpha T\}\{20\}\+2\\sqrt\{\\left\(\\sum\_\{t=1\}^\{T\}g\_\{t\}\(\\rho\_\{t\}\)\\right\)\\left\(\\sum\_\{t=1\}^\{T\}\(\\alpha\+\\beta\\rho\_\{t\}d\)\\right\)\}≤∑t=1Tgt​\(ρt\)\+d​D​ρT⏟clean regret from \([22](https://arxiv.org/html/2606.02948#A1.E22)\)\+21​β​d20​∑t=1Tρt\+2​L​β​d​T\+21​α​T20\+2​\(∑t=1Tgt​\(ρt\)\+d​D​ρT\)⏟clean regret from \([22](https://arxiv.org/html/2606.02948#A1.E22)\)​\(∑t=1T\(α\+β​ρt​d\)\)\\displaystyle\\leq\\underbrace\{\\sum\_\{t=1\}^\{T\}g\_\{t\}\(\\rho\_\{t\}\)\+dD\\rho\_\{T\}\}\_\{\\text\{clean regret from \\eqref\{eqn:ftl\-clean\-sequence\-regret\-ub\}\}\}\+\\frac\{21\\beta d\}\{20\}\\sum\_\{t=1\}^\{T\}\\rho\_\{t\}\+2L\\beta dT\+\\frac\{21\\alpha T\}\{20\}\+2\\sqrt\{\\underbrace\{\\left\(\\sum\_\{t=1\}^\{T\}g\_\{t\}\(\\rho\_\{t\}\)\+dD\\rho\_\{T\}\\right\)\}\_\{\\text\{clean regret from \\eqref\{eqn:ftl\-clean\-sequence\-regret\-ub\}\}\}\\left\(\\sum\_\{t=1\}^\{T\}\(\\alpha\+\\beta\\rho\_\{t\}d\)\\right\)\}≤C⋅OPTTα,β​\(r\)\+21​β​d20​∑t=1Tρt\+2​L​β​d​T\+21​α​T20⏟:=ET\+2​C⋅OPTTα,β​\(r\)​\(∑t=1T\(α\+β​ρt​d\)\)\\displaystyle\\leq C\\cdot\\mathrm\{OPT\}^\{\\alpha,\\beta\}\_\{T\}\(r\)\+\\underbrace\{\\frac\{21\\beta d\}\{20\}\\sum\_\{t=1\}^\{T\}\\rho\_\{t\}\+2L\\beta dT\+\\frac\{21\\alpha T\}\{20\}\}\_\{:=\\,E\_\{T\}\}\+2\\sqrt\{C\\cdot\\mathrm\{OPT\}^\{\\alpha,\\beta\}\_\{T\}\(r\)\\left\(\\sum\_\{t=1\}^\{T\}\(\\alpha\+\\beta\\rho\_\{t\}d\)\\right\)\}≤C⋅OPTTα,β​\(r\)\+ET\+2​C⋅OPTTα,β​\(r\)⋅ET\.\\displaystyle\\leq C\\cdot\\mathrm\{OPT\}^\{\\alpha,\\beta\}\_\{T\}\(r\)\+E\_\{T\}\+2\\sqrt\{C\\cdot\\mathrm\{OPT\}^\{\\alpha,\\beta\}\_\{T\}\(r\)\\cdot E\_\{T\}\}\.\(24\)

#### BoundingETE\_\{T\}\.

Finally, we aim to upper\-boundETE\_\{T\}in terms ofOPTTα,β​\(r\)\\mathrm\{OPT\}^\{\\alpha,\\beta\}\_\{T\}\(r\)\. We have

ET\\displaystyle E\_\{T\}=21​β​d20​∑t=1Tρt\+2​L​β​d​T\+21​α​T20\\displaystyle=\\frac\{21\\beta d\}\{20\}\\sum\_\{t=1\}^\{T\}\\rho\_\{t\}\+2L\\beta dT\+\\frac\{21\\alpha T\}\{20\}≤21​β​d​T​ρT20\+2​L​β​d​T\+21​α​T20\.\\displaystyle\\leq\\frac\{21\\beta dT\\rho\_\{T\}\}\{20\}\+2L\\beta dT\+\\frac\{21\\alpha T\}\{20\}\.\(sinceρt\\rho\_\{t\}is non\-decreasing\)Now, observe thatα​T≤OPTTα,β​\(r\)\\alpha T\\leq\\mathrm\{OPT\}^\{\\alpha,\\beta\}\_\{T\}\(r\)\. Furthermore, from \([22](https://arxiv.org/html/2606.02948#A1.E22)\) and \([23](https://arxiv.org/html/2606.02948#A1.E23)\),

d​D​ρT≤d​D​ρT\+∑t=1Tgt​\(ρt\)≤C⋅OPTT0​\(r\)≤C⋅OPTTα,β​\(r\)\.\\displaystyle dD\\rho\_\{T\}\\leq dD\\rho\_\{T\}\+\\sum\_\{t=1\}^\{T\}g\_\{t\}\(\\rho\_\{t\}\)\\leq C\\cdot\\mathrm\{OPT\}^\{0\}\_\{T\}\(r\)\\leq C\\cdot\\mathrm\{OPT\}^\{\\alpha,\\beta\}\_\{T\}\(r\)\.Finally, since it also holds thatd​D​r≤OPTTα,β​\(r\)dDr\\leq\\mathrm\{OPT\}^\{\\alpha,\\beta\}\_\{T\}\(r\), we have thatL​β​d​T≤L​β​TD​r⋅OPTTα,β​\(r\)L\\beta dT\\leq\\frac\{L\\beta T\}\{Dr\}\\cdot\\mathrm\{OPT\}^\{\\alpha,\\beta\}\_\{T\}\(r\)\. Combining all this, we get

ET\\displaystyle E\_\{T\}≤\(21​C​β​T20​D\+2​L​β​TD​r\+2120\)⋅OPTTα,β​\(r\)\.\\displaystyle\\leq\\left\(\\frac\{21C\\beta T\}\{20D\}\+\\frac\{2L\\beta T\}\{Dr\}\+\\frac\{21\}\{20\}\\right\)\\cdot\\mathrm\{OPT\}^\{\\alpha,\\beta\}\_\{T\}\(r\)\.

#### Plugging inβ=O​\(1/T\)\\beta=O\(1/T\)\.

Note thatβ≤c/T\\beta\\leq c/Tsuffices to getET≤C′⋅OPTTα,β​\(r\)E\_\{T\}\\leq C^\{\\prime\}\\cdot\\mathrm\{OPT\}^\{\\alpha,\\beta\}\_\{T\}\(r\), whereC′C^\{\\prime\}is a constant depending onL,D,d,rL,D,d,randcc\. Finally, plugging this back in \([24](https://arxiv.org/html/2606.02948#A1.E24)\), we get

∑t=1TMt​\(ρt\)\+d​D​ρT\+α​T\+d​β​∑t=1Tρt≤C′′⋅OPTTα,β​\(r\),\\displaystyle\\sum\_\{t=1\}^\{T\}M\_\{t\}\(\\rho\_\{t\}\)\+dD\\rho\_\{T\}\+\\alpha T\+d\\beta\\sum\_\{t=1\}^\{T\}\\rho\_\{t\}\\leq C^\{\\prime\\prime\}\\cdot\\mathrm\{OPT\}^\{\\alpha,\\beta\}\_\{T\}\(r\),whereC′′C^\{\\prime\\prime\}is a constant depending onL,D,d,rL,D,d,randcc\. Recalling that the quantity on the left\-hand side above is precisely the upper\-bound on regret shown in[Theorem1](https://arxiv.org/html/2606.02948#Thmtheorem1)completes the proof\. ∎

See[3\.1](https://arxiv.org/html/2606.02948#S3.Thmlemma1)

###### Proof\.

In view of[Theorem2](https://arxiv.org/html/2606.02948#Thmtheorem2), it suffices to upper\-boundOPTTα,β​\(r\)\\mathrm\{OPT\}^\{\\alpha,\\beta\}\_\{T\}\(r\), where

OPTTα,β​\(r\):=infr≤ρ1≤⋯≤ρT\\displaystyle\\mathrm\{OPT\}^\{\\alpha,\\beta\}\_\{T\}\(r\):=\\inf\_\{r\\leq\\rho\_\{1\}\\leq\\dots\\leq\\rho\_\{T\}\}\[∑t=1Tmin\{125​L2​d2​Dρt\+β​ρt​d20\+2Lβd\+α20,2​L2St\+2L2​\(α\+β​ρt​d\)St\}\\displaystyle\\left\[\\sum\_\{t=1\}^\{T\}\\min\\left\\\{\\frac\{125L^\{2\}d^\{2\}D\}\{\\rho\_\{t\}\}\+\\frac\{\\beta\\rho\_\{t\}d\}\{20\}\+2L\\beta d\+\\frac\{\\alpha\}\{20\},\\frac\{2L^\{2\}\}\{S\_\{t\}\}\+2L\\sqrt\{\\frac\{2\(\\alpha\+\\beta\\rho\_\{t\}d\)\}\{S\_\{t\}\}\}\\right\\\}\\right\.\+dDρT\+αT\+dβ∑t=1Tρt\]\.\\displaystyle\\qquad\\qquad\\left\.\+\\,dD\\rho\_\{T\}\+\\alpha T\+d\\beta\\sum\_\{t=1\}^\{T\}\\rho\_\{t\}\\right\]\.Chooseρt=ρ\\rho\_\{t\}=\\rhofor alltt\. By taking the non\-convex branch in the min, we have that

OPTTα,β​\(r\)\\displaystyle\\mathrm\{OPT\}^\{\\alpha,\\beta\}\_\{T\}\(r\)≤∑t=1T\(125​L2​d2​Dρ\+β​ρ​d20\+2​L​β​d\+α20\)\+d​D​ρ\+α​T\+d​β​T​ρ\\displaystyle\\leq\\sum\_\{t=1\}^\{T\}\\left\(\\frac\{125L^\{2\}d^\{2\}D\}\{\\rho\}\+\\frac\{\\beta\\rho d\}\{20\}\+2L\\beta d\+\\frac\{\\alpha\}\{20\}\\right\)\+dD\\rho\+\\alpha T\+d\\beta T\\rho=125​L2​d2​D​Tρ\+21​β​ρ​d​T20\+2​L​β​d​T\+d​D​ρ\+21​α​T20\\displaystyle=\\frac\{125L^\{2\}d^\{2\}DT\}\{\\rho\}\+\\frac\{21\\beta\\rho dT\}\{20\}\+2L\\beta dT\+dD\\rho\+\\frac\{21\\alpha T\}\{20\}=O​\(Tρ\+ρ\)\.\\displaystyle=O\\left\(\\frac\{T\}\{\\rho\}\+\\rho\\right\)\.\(substitutingα,β=O​\(1/T\)\\alpha,\\beta=O\(1/T\)\)Settingr=1r=1andρ=T\\rho=\\sqrt\{T\}givesOPTTα,β​\(r\)≤O​\(T\)\\mathrm\{OPT\}^\{\\alpha,\\beta\}\_\{T\}\(r\)\\leq O\(\\sqrt\{T\}\)\.

Now, suppose thatSt≥tγS\_\{t\}\\geq t^\{\\gamma\}\. Whenγ≤1/2\\gamma\\leq 1/2, we already have theO​\(T\)O\(\\sqrt\{T\}\)regret bound from above\.

#### Regime12<γ<1\\frac\{1\}\{2\}<\\gamma<1\.

Chooser=1r=1andρt=ρ=1\\rho\_\{t\}=\\rho=1for alltt\. By taking the strongly\-convex branch in the min, we have that

OPTTα,β​\(r\)\\displaystyle\\mathrm\{OPT\}^\{\\alpha,\\beta\}\_\{T\}\(r\)≤∑t=1T\(2​L2St\+2​L​2​\(α\+β​ρ​d\)St\)\+d​D​ρ\+α​T\+d​β​T​ρ\\displaystyle\\leq\\sum\_\{t=1\}^\{T\}\\left\(\\frac\{2L^\{2\}\}\{S\_\{t\}\}\+2L\\sqrt\{\\frac\{2\(\\alpha\+\\beta\\rho d\)\}\{S\_\{t\}\}\}\\right\)\+dD\\rho\+\\alpha T\+d\\beta T\\rho≤O​\(∑t=1Tt−γ\+T−1/2​∑t=1Tt−γ/2\)\\displaystyle\\leq O\\left\(\\sum\_\{t=1\}^\{T\}t^\{\-\\gamma\}\+T^\{\-1/2\}\\sum\_\{t=1\}^\{T\}t^\{\-\\gamma/2\}\\right\)≤O​\(T1−γ\+T1/2−γ/2\)=O​\(T1−γ\)\.\\displaystyle\\leq O\\left\(T^\{1\-\\gamma\}\+T^\{1/2\-\\gamma/2\}\\right\)=O\(T^\{1\-\\gamma\}\)\.

#### Regimeγ=1\\gamma=1\.

Chooser=1r=1andρt=ρ=1\\rho\_\{t\}=\\rho=1for alltt\. By taking the strongly\-convex branch in the min, we have that

OPTTα,β​\(r\)\\displaystyle\\mathrm\{OPT\}^\{\\alpha,\\beta\}\_\{T\}\(r\)≤∑t=1T\(2​L2St\+2​L​2​\(α\+β​ρ​d\)St\)\+d​D​ρ\+α​T\+d​β​T​ρ\\displaystyle\\leq\\sum\_\{t=1\}^\{T\}\\left\(\\frac\{2L^\{2\}\}\{S\_\{t\}\}\+2L\\sqrt\{\\frac\{2\(\\alpha\+\\beta\\rho d\)\}\{S\_\{t\}\}\}\\right\)\+dD\\rho\+\\alpha T\+d\\beta T\\rho=O​\(∑t=1T1t\+T−1/2​∑t=1Tt−1/2\)=O​\(log⁡T\)\.\\displaystyle=O\\left\(\\sum\_\{t=1\}^\{T\}\\frac\{1\}\{t\}\+T^\{\-1/2\}\\sum\_\{t=1\}^\{T\}t^\{\-1/2\}\\right\)=O\(\\log T\)\.

#### Regimeγ\>1\\gamma\>1\.

Chooser=1r=1andρt=ρ=1\\rho\_\{t\}=\\rho=1for alltt\. By taking the strongly\-convex branch in the min, we have that

OPTTα,β​\(r\)\\displaystyle\\mathrm\{OPT\}^\{\\alpha,\\beta\}\_\{T\}\(r\)≤∑t=1T\(2​L2St\+2​L​2​\(α\+β​ρ​d\)St\)\+d​D​ρ\+α​T\+d​β​T​ρ\\displaystyle\\leq\\sum\_\{t=1\}^\{T\}\\left\(\\frac\{2L^\{2\}\}\{S\_\{t\}\}\+2L\\sqrt\{\\frac\{2\(\\alpha\+\\beta\\rho d\)\}\{S\_\{t\}\}\}\\right\)\+dD\\rho\+\\alpha T\+d\\beta T\\rho=O​\(∑t=1Tt−γ\+T−1/2​∑t=1Tt−γ/2\)=O​\(1\)\.∎\\displaystyle=O\\left\(\\sum\_\{t=1\}^\{T\}t^\{\-\\gamma\}\+T^\{\-1/2\}\\sum\_\{t=1\}^\{T\}t^\{\-\\gamma/2\}\\right\)=O\(1\)\.\\qed

## Appendix BProofs from[Section4](https://arxiv.org/html/2606.02948#S4)

We restate and prove[Theorem3](https://arxiv.org/html/2606.02948#Thmtheorem3)\.

See[3](https://arxiv.org/html/2606.02948#Thmtheorem3)

#### Setup\.

Fix𝒳\\mathcal\{X\}to be the interval\[−D/2,D/2\]⊆ℝ\[\-D/2,D/2\]\\subseteq\\mathds\{R\}\. Let0=s0≤s1≤⋯≤sT0=s\_\{0\}\\leq s\_\{1\}\\leq\\dots\\leq s\_\{T\}be the given sequence of cumulative curvatures\. For anyt∈\[T\]t\\in\[T\], let

at:=st−st−1≥0\.\\displaystyle a\_\{t\}:=s\_\{t\}\-s\_\{t\-1\}\\geq 0\.The lower bound of[Theorem3](https://arxiv.org/html/2606.02948#Thmtheorem3)holds for any sequence satisfying thatat≤L/2​Da\_\{t\}\\leq L/2Dfor alltt\. As will become clearer, this condition is used solely to ensure that the functions used in the lower bound are allLL\-Lipschitz on𝒳\\mathcal\{X\}\.

Recall that

ℜT​\(s1:T\):=inf𝒜supf1,…,fT​​L​\-Lipschitzon​𝒳St=st​for all​t𝔼𝒜⁡\[RegretT​\(f1:T;x1:T\)\]\.\\displaystyle\\mathfrak\{R\}\_\{T\}\(s\_\{1:T\}\):=\\inf\_\{\\mathcal\{A\}\}\\sup\_\{\\begin\{subarray\}\{c\}f\_\{1\},\\ldots,f\_\{T\}\\text\{ \}L\\text\{\-Lipschitz\}\\text\{ on \}\\mathcal\{X\}\\\\ S\_\{t\}=s\_\{t\}\\text\{ for all \}t\\end\{subarray\}\}\\operatorname\{\{\\mathds\{E\}\}\}\_\{\\mathcal\{A\}\}\\left\[\\mathrm\{Regret\}\_\{T\}\(f\_\{1:T\};x\_\{1:T\}\)\\right\]\.\(25\)and we seek to show that

ℜT​\(s1:T\)\\displaystyle\\mathfrak\{R\}\_\{T\}\(s\_\{1:T\}\)≥c⋅infρ≥0\[L2​∑t=1Tmin⁡\{Dρ,1st\}\+D​ρ\]\.\\displaystyle\\geq c\\cdot\\inf\_\{\\rho\\geq 0\}\\left\[L^\{2\}\\sum\_\{t=1\}^\{T\}\\min\\left\\\{\\frac\{D\}\{\\rho\},\\frac\{1\}\{s\_\{t\}\}\\right\\\}\+D\\rho\\right\]\.\(26\)It will be convenient to instead lower boundℜT​\(s1:T\)\\mathfrak\{R\}\_\{T\}\(s\_\{1:T\}\)by the quantity:

infγ≥0\[D2​γ\+L2​∑t=1T1st\+γ\]\.\\displaystyle\\inf\_\{\\gamma\\geq 0\}\\left\[D^\{2\}\\gamma\+L^\{2\}\\sum\_\{t=1\}^\{T\}\\frac\{1\}\{s\_\{t\}\+\\gamma\}\\right\]\.\(27\)Indeed, this will be sufficient, due to the following claim:

###### Claim B\.1\.

For everys≥0s\\geq 0andγ≥0\\gamma\\geq 0,

12​min⁡\{1s,1γ\}≤1s\+γ≤min⁡\{1s,1γ\},\\frac\{1\}\{2\}\\min\\left\\\{\\frac\{1\}\{s\},\\frac\{1\}\{\\gamma\}\\right\\\}\\leq\\frac\{1\}\{s\+\\gamma\}\\leq\\min\\left\\\{\\frac\{1\}\{s\},\\frac\{1\}\{\\gamma\}\\right\\\},with the convention1/0=∞1/0=\\infty\.

###### Proof\.

The upper bound follows becauses\+γ≥ss\+\\gamma\\geq sands\+γ≥γs\+\\gamma\\geq\\gamma\. The lower bound follows becauses\+γ≤2​max⁡\{s,γ\}s\+\\gamma\\leq 2\\max\\\{s,\\gamma\\\}\. ∎

Hence, if we lower\-boundℜT​\(s1:T\)\\mathfrak\{R\}\_\{T\}\(s\_\{1:T\}\)in terms of the quantity in \([27](https://arxiv.org/html/2606.02948#A2.E27)\), the desired lower bound in \([26](https://arxiv.org/html/2606.02948#A2.E26)\) will follow by the change of variableγ=ρ/D\\gamma=\\rho/D\.

We thus proceed to lower\-boundℜT​\(s1:T\)\\mathfrak\{R\}\_\{T\}\(s\_\{1:T\}\)byinfγ≥0\{D2​γ\+L2​∑t=1T1st\+γ\}\\inf\_\{\\gamma\\geq 0\}\\left\\\{D^\{2\}\\gamma\+L^\{2\}\\sum\_\{t=1\}^\{T\}\\frac\{1\}\{s\_\{t\}\+\\gamma\}\\right\\\}, and divide the proof into 8 steps:

### Step 1: Defining the hard distribution for a fixedγ\\gamma

Fix an arbitrary deterministic learner\. Also, fixγ≥0\\gamma\\geq 0which satisfies:

1. 1\.st\+γ\>0s\_\{t\}\+\\gamma\>0for everytt\.
2. 2\.H2​\(γ\):=∑t=1T1\(st\+γ\)2≤D2L2H\_\{2\}\(\\gamma\):=\\sum\_\{t=1\}^\{T\}\\frac\{1\}\{\(s\_\{t\}\+\\gamma\)^\{2\}\}\\leq\\frac\{D^\{2\}\}\{L^\{2\}\}

We will later choose an optimal value ofγ\\gammawhich satisfies these conditions\.

Letε1,…,εT\\varepsilon\_\{1\},\\dots,\\varepsilon\_\{T\}be independent Rademacher random variables in\{−1,\+1\}\\\{\-1,\+1\\\}\. Set

g:=L8\.\\displaystyle g:=\\frac\{L\}\{8\}\.
The functionsf1,…,fTf\_\{1\},\\dots,f\_\{T\}will be a sequence of carefully chosen quadratics, where eachftf\_\{t\}has curvatureata\_\{t\}\(and sinceat≥0a\_\{t\}\\geq 0, each quadratic is convex\)\. The centers and linear tiltsℓt\\ell\_\{t\}of eachftf\_\{t\}are specified by the following process\.

Initializez0=0z\_\{0\}=0, and declare the process to be active\. For each roundt=1,2,…,Tt=1,2,\\dots,T:

1. 1\.If the process is active before roundtt, setℓt=g​εt\\ell\_\{t\}=g\\varepsilon\_\{t\}; if it has been declared inactive, setℓt=0\\ell\_\{t\}=0\.
2. 2\.Set ft​\(x\):=at2​\(x−zt−1\)2−ℓt​\(x−zt−1\)\.f\_\{t\}\(x\):=\\frac\{a\_\{t\}\}\{2\}\(x\-z\_\{t\-1\}\)^\{2\}\-\\ell\_\{t\}\(x\-z\_\{t\-1\}\)\.\(28\)
3. 3\.Update zt=zt−1\+ℓtst\+γ\.z\_\{t\}=z\_\{t\-1\}\+\\frac\{\\ell\_\{t\}\}\{s\_\{t\}\+\\gamma\}\.\(29\)
4. 4\.If the process was active before roundttand\|zt\|\>D/4\|z\_\{t\}\|\>D/4, declare the process inactive\.

Observe that once the process above becomes inactive, all future linear tilts are zero and the center stays constant\. Note also that all the functionsf1,…,fTf\_\{1\},\\dots,f\_\{T\}are determined as a function ofγ\\gammaand the sequencess1,…,sTs\_\{1\},\\dots,s\_\{T\}andε1,…,εT\\varepsilon\_\{1\},\\dots,\\varepsilon\_\{T\}\.

### Step 2: Feasibility of centers and functions

We first argue that all the centersz0,…,zTz\_\{0\},\\dots,z\_\{T\}belong to𝒳=\[−D/2,D/2\]\\mathcal\{X\}=\[\-D/2,D/2\]\. For this, note that assuming the bound onH2​\(γ\)H\_\{2\}\(\\gamma\)given in[Item2](https://arxiv.org/html/2606.02948#A2.I1.i2), the magnitude of each update satisfies

\|ℓtst\+γ\|≤g​H2​\(γ\)≤L8⋅DL=D8\.\\left\|\\frac\{\\ell\_\{t\}\}\{s\_\{t\}\+\\gamma\}\\right\|\\leq g\\sqrt\{H\_\{2\}\(\\gamma\)\}\\leq\\frac\{L\}\{8\}\\cdot\\frac\{D\}\{L\}=\\frac\{D\}\{8\}\.Now observe thatz0=0z\_\{0\}=0, and for anyttwhere the process is active before roundtt, we have\|zt−1\|≤D/4\|z\_\{t\-1\}\|\\leq D/4\. Furthermore, if at roundtt,\|zt\|\|z\_\{t\}\|becomes larger thanD/4D/4causing the process to become inactive, we have

\|zt\|≤\|zt−1\|\+D/4≤D/4\+D/8=3​D/8<D/2\.\|z\_\{t\}\|\\leq\|z\_\{t\-1\}\|\+D/4\\leq D/4\+D/8=3D/8<D/2\.Thereafter, the center remains fixed, and hencezt∈𝒳z\_\{t\}\\in\\mathcal\{X\}for allt∈\{0,1,…,T\}t\\in\\\{0,1,\\dots,T\\\}\.

We now argue that all the functions are feasible\. Observe that even if the process has been declared inactive, the quadratic terms with coefficientsata\_\{t\}are still played\. Thus, for every round,

ft′′​\(x\)=at≥0,f\_\{t\}^\{\\prime\\prime\}\(x\)=a\_\{t\}\\geq 0,softf\_\{t\}is convex\. The cumulative lossFt=∑i=1tfiF\_\{t\}=\\sum\_\{i=1\}^\{t\}f\_\{i\}satisfies

Ft′′​\(x\)=∑i=1tai=st,F\_\{t\}^\{\\prime\\prime\}\(x\)=\\sum\_\{i=1\}^\{t\}a\_\{i\}=s\_\{t\},so the cumulative curvature is exactly the prescribed valuests\_\{t\}\.

Since all the centers lie in𝒳\\mathcal\{X\}, for everyx∈𝒳x\\in\\mathcal\{X\},

\|ft′​\(x\)\|=\|at​\(x−zt−1\)−ℓt\|≤at​D\+\|ℓt\|\.\|f\_\{t\}^\{\\prime\}\(x\)\|=\|a\_\{t\}\(x\-z\_\{t\-1\}\)\-\\ell\_\{t\}\|\\leq a\_\{t\}D\+\|\\ell\_\{t\}\|\.Sinceat≤L/2​Da\_\{t\}\\leq L/2Dand\|ℓt\|≤g=L/8\|\\ell\_\{t\}\|\\leq g=L/8,

\|ft′​\(x\)\|≤L2\+L8<L\.\|f\_\{t\}^\{\\prime\}\(x\)\|\\leq\\frac\{L\}\{2\}\+\\frac\{L\}\{8\}<L\.\(30\)Thus, everyftf\_\{t\}is convex,LL\-Lipschitz on𝒳\\mathcal\{X\}, and has the required cumulative curvature schedule\.

### Step 3: The learner’s expected cumulative loss is nonnegative

For anytt, observe that conditioned onε1,…,εt−1\\varepsilon\_\{1\},\\dots,\\varepsilon\_\{t\-1\}, the learner’s movextx\_\{t\}is determined \(since it is deterministic\)\. Furthermore, the centerzt−1z\_\{t\-1\}, as well as whether the process remains active/has been declared inactive before roundttis also determined\. We consider the two cases separately\.

#### Case 1: The process is active before roundtt\.

Thenℓt=g​εt\\ell\_\{t\}=g\\varepsilon\_\{t\}, whereεt\\varepsilon\_\{t\}is independent ofε1,…,εt−1\\varepsilon\_\{1\},\\dots,\\varepsilon\_\{t\-1\}, and has mean zero\. Hence,

𝔼⁡\[ℓt∣ε1,…,εt−1\]=0\.\\operatorname\{\{\\mathds\{E\}\}\}\[\\ell\_\{t\}\\mid\\varepsilon\_\{1\},\\dots,\\varepsilon\_\{t\-1\}\]=0\.By definition offtf\_\{t\}\([28](https://arxiv.org/html/2606.02948#A2.E28)\),

𝔼⁡\[ft​\(xt\)∣ε1,…,εt−1\]=at2​\(xt−zt−1\)2≥0\.\\operatorname\{\{\\mathds\{E\}\}\}\[f\_\{t\}\(x\_\{t\}\)\\mid\\varepsilon\_\{1\},\\dots,\\varepsilon\_\{t\-1\}\]=\\frac\{a\_\{t\}\}\{2\}\(x\_\{t\}\-z\_\{t\-1\}\)^\{2\}\\geq 0\.

#### Case 2: The process has become inactive before roundtt\.

Thenℓt=0\\ell\_\{t\}=0, so

ft​\(xt\)=at2​\(xt−zt−1\)2≥0,f\_\{t\}\(x\_\{t\}\)=\\frac\{a\_\{t\}\}\{2\}\(x\_\{t\}\-z\_\{t\-1\}\)^\{2\}\\geq 0,and therefore

𝔼⁡\[ft​\(xt\)∣ε1,…,εt−1\]≥0\.\\operatorname\{\{\\mathds\{E\}\}\}\[f\_\{t\}\(x\_\{t\}\)\\mid\\varepsilon\_\{1\},\\dots,\\varepsilon\_\{t\-1\}\]\\geq 0\.In both cases,

𝔼⁡\[ft​\(xt\)∣ε1,…,εt−1\]≥0\.\\operatorname\{\{\\mathds\{E\}\}\}\[f\_\{t\}\(x\_\{t\}\)\\mid\\varepsilon\_\{1\},\\dots,\\varepsilon\_\{t\-1\}\]\\geq 0\.Thus, we get that

𝔼⁡\[∑t=1Tft​\(xt\)\]\\displaystyle\\operatorname\{\{\\mathds\{E\}\}\}\\left\[\\sum\_\{t=1\}^\{T\}f\_\{t\}\(x\_\{t\}\)\\right\]=∑t=1T𝔼⁡\[ft​\(xt\)\]=∑t=1T𝔼ε1,…,εt−1⁡𝔼⁡\[ft​\(xt\)∣ε1,…,εt−1\]≥0\.\\displaystyle=\\sum\_\{t=1\}^\{T\}\\operatorname\{\{\\mathds\{E\}\}\}\[f\_\{t\}\(x\_\{t\}\)\]=\\sum\_\{t=1\}^\{T\}\\operatorname\{\{\\mathds\{E\}\}\}\_\{\\varepsilon\_\{1\},\\dots,\\varepsilon\_\{t\-1\}\}\\operatorname\{\{\\mathds\{E\}\}\}\[f\_\{t\}\(x\_\{t\}\)\\mid\\varepsilon\_\{1\},\\dots,\\varepsilon\_\{t\-1\}\]\\geq 0\.\(31\)

### Step 4: A regularized cumulative loss that has an exact quadratic invariant

Define the fictitiously regularized cumulative loss

Gt​\(x\):=Ft​\(x\)\+γ2​x2\.G\_\{t\}\(x\):=F\_\{t\}\(x\)\+\\frac\{\\gamma\}\{2\}x^\{2\}\.We claim that, for allt≥0t\\geq 0,

Gt​\(x\)=Gt​\(zt\)\+st\+γ2​\(x−zt\)2,G\_\{t\}\(x\)=G\_\{t\}\(z\_\{t\}\)\+\\frac\{s\_\{t\}\+\\gamma\}\{2\}\(x\-z\_\{t\}\)^\{2\},\(32\)and fort≥1t\\geq 1,

Gt​\(zt\)=Gt−1​\(zt−1\)−ℓt22​\(st\+γ\)\.G\_\{t\}\(z\_\{t\}\)=G\_\{t\-1\}\(z\_\{t\-1\}\)\-\\frac\{\\ell\_\{t\}^\{2\}\}\{2\(s\_\{t\}\+\\gamma\)\}\.\(33\)To see this, observe that fort=0t=0,G0​\(x\)=γ2​x2G\_\{0\}\(x\)=\\frac\{\\gamma\}\{2\}x^\{2\}, and sincez0=0z\_\{0\}=0ands0=0s\_\{0\}=0, \([32](https://arxiv.org/html/2606.02948#A2.E32)\) holds\. Now, lett≥1t\\geq 1, and suppose that \([32](https://arxiv.org/html/2606.02948#A2.E32)\) holds fort−1t\-1\. Then, we have that

Gt​\(x\)\\displaystyle G\_\{t\}\(x\)=Gt−1​\(x\)\+ft​\(x\)\\displaystyle=G\_\{t\-1\}\(x\)\+f\_\{t\}\(x\)=Gt−1​\(zt−1\)\+st−1\+γ2​\(x−zt−1\)2\+at2​\(x−zt−1\)2−ℓt​\(x−zt−1\)\\displaystyle=G\_\{t\-1\}\(z\_\{t\-1\}\)\+\\frac\{s\_\{t\-1\}\+\\gamma\}\{2\}\(x\-z\_\{t\-1\}\)^\{2\}\+\\frac\{a\_\{t\}\}\{2\}\(x\-z\_\{t\-1\}\)^\{2\}\-\\ell\_\{t\}\(x\-z\_\{t\-1\}\)\(by definition offtf\_\{t\}\)=Gt−1​\(zt−1\)\+st\+γ2​\(x−zt−1\)2−ℓt​\(x−zt−1\)\.\\displaystyle=G\_\{t\-1\}\(z\_\{t\-1\}\)\+\\frac\{s\_\{t\}\+\\gamma\}\{2\}\(x\-z\_\{t\-1\}\)^\{2\}\-\\ell\_\{t\}\(x\-z\_\{t\-1\}\)\.\(using thatat=st−st−1a\_\{t\}=s\_\{t\}\-s\_\{t\-1\}\)=Gt−1\(zt−1\)\+st\+γ2\[\(x−zt−1−ℓtst\+γ\]2−ℓt22​\(st\+γ\)\.\\displaystyle=G\_\{t\-1\}\(z\_\{t\-1\}\)\+\\frac\{s\_\{t\}\+\\gamma\}\{2\}\\left\[\(x\-z\_\{t\-1\}\-\\frac\{\\ell\_\{t\}\}\{s\_\{t\}\+\\gamma\}\\right\]^\{2\}\-\\frac\{\\ell\_\{t\}^\{2\}\}\{2\(s\_\{t\}\+\\gamma\)\}\.\(completing the square\)Substitutingx=ztx=z\_\{t\}, and recalling the center update from \([29](https://arxiv.org/html/2606.02948#A2.E29)\) gives \([33](https://arxiv.org/html/2606.02948#A2.E33)\)\. Thereafter, substituting the expression forGt​\(zt\)G\_\{t\}\(z\_\{t\}\)from \([33](https://arxiv.org/html/2606.02948#A2.E33)\) back in the above gives \([32](https://arxiv.org/html/2606.02948#A2.E32)\)\.

### Step 5: Telescoping the regularized cumulative loss

Telescoping \([33](https://arxiv.org/html/2606.02948#A2.E33)\) gives

GT​\(zT\)=−∑t=1Tℓt22​\(st\+γ\)\.G\_\{T\}\(z\_\{T\}\)=\-\\sum\_\{t=1\}^\{T\}\\frac\{\\ell\_\{t\}^\{2\}\}\{2\(s\_\{t\}\+\\gamma\)\}\.\(34\)SincezT∈𝒳z\_\{T\}\\in\\mathcal\{X\}, and using thatFT​\(x\)=GT​\(x\)−\(γ/2\)​x2≤GT​\(x\)F\_\{T\}\(x\)=G\_\{T\}\(x\)\-\(\\gamma/2\)x^\{2\}\\leq G\_\{T\}\(x\),

infx∈𝒳FT​\(x\)≤FT​\(zT\)≤GT​\(zT\)\.\\inf\_\{x\\in\\mathcal\{X\}\}F\_\{T\}\(x\)\\leq F\_\{T\}\(z\_\{T\}\)\\leq G\_\{T\}\(z\_\{T\}\)\.Therefore,

−infx∈𝒳FT​\(x\)≥−GT​\(zT\)=∑t=1Tℓt22​\(st\+γ\)\.\-\\inf\_\{x\\in\\mathcal\{X\}\}F\_\{T\}\(x\)\\geq\-G\_\{T\}\(z\_\{T\}\)=\\sum\_\{t=1\}^\{T\}\\frac\{\\ell\_\{t\}^\{2\}\}\{2\(s\_\{t\}\+\\gamma\)\}\.\(35\)Taking expectation, and combining \([31](https://arxiv.org/html/2606.02948#A2.E31)\), \([35](https://arxiv.org/html/2606.02948#A2.E35)\), we get

𝔼⁡\[RegretT​\(f1:T;x1:T\)\]≥𝔼⁡\[∑t=1Tℓt22​\(st\+γ\)\]\.\\operatorname\{\{\\mathds\{E\}\}\}\\left\[\\mathrm\{Regret\}\_\{T\}\(f\_\{1:T\};x\_\{1:T\}\)\\right\]\\geq\\operatorname\{\{\\mathds\{E\}\}\}\\left\[\\sum\_\{t=1\}^\{T\}\\frac\{\\ell\_\{t\}^\{2\}\}\{2\(s\_\{t\}\+\\gamma\)\}\\right\]\.\(36\)Note that the sole randomness in the expectations above is fromε1,…,εT\\varepsilon\_\{1\},\\dots,\\varepsilon\_\{T\}\.

### Step 6: Process remains active throughout with constant probability

Observe that the centersz0,z1,…,zTz\_\{0\},z\_\{1\},\\dots,z\_\{T\}follow a random process, and if the process is active before roundtt,

zt=∑i=1tℓisi\+γ\.z\_\{t\}=\\sum\_\{i=1\}^\{t\}\\frac\{\\ell\_\{i\}\}\{s\_\{i\}\+\\gamma\}\.Consider a coupling\(zt,mt\)\(z\_\{t\},m\_\{t\}\), wheremt=ztm\_\{t\}=z\_\{t\}up until the time the process becomes inactive, but thereafter,mtm\_\{t\}continues to evolve as above even afterztz\_\{t\}has become constant\. That is, for everytt,

mt=∑i=1tℓisi\+γ\.\\displaystyle m\_\{t\}=\\sum\_\{i=1\}^\{t\}\\frac\{\\ell\_\{i\}\}\{s\_\{i\}\+\\gamma\}\.Note that each term in the sum above has mean0\. Furthermore, the variance ofmTm\_\{T\}is

Var⁡\[mT\]=𝔼⁡\[mT2\]\\displaystyle\\operatorname\{\{Var\}\}\[m\_\{T\}\]=\\operatorname\{\{\\mathds\{E\}\}\}\[m\_\{T\}^\{2\}\]=g2​∑t=1T1\(st\+γ\)2\.\\displaystyle=g^\{2\}\\sum\_\{t=1\}^\{T\}\\frac\{1\}\{\(s\_\{t\}\+\\gamma\)^\{2\}\}\.We are now in a position to invoke Kolmogorov’s maximal inequality\[Billingsley,[2017](https://arxiv.org/html/2606.02948#bib.bib21), Theorem 22\.4\]\.

###### Proposition B\.2\(Kolmogorov’s maximal inequality\)\.

Letmt=∑i=1txim\_\{t\}=\\sum\_\{i=1\}^\{t\}x\_\{i\}, wherex1,…,xTx\_\{1\},\\ldots,x\_\{T\}are independent mean\-zero random variables with finite variance\. Then, for everyr\>0r\>0,

Pr⁡\[max1≤t≤T⁡\|mt\|≥r\]≤𝔼⁡\[mT2\]r2\.\\operatorname\{\{Pr\}\}\\left\[\\max\_\{1\\leq t\\leq T\}\|m\_\{t\}\|\\geq r\\right\]\\leq\\frac\{\\operatorname\{\{\\mathds\{E\}\}\}\[m\_\{T\}^\{2\}\]\}\{r^\{2\}\}\.

By[PropositionB\.2](https://arxiv.org/html/2606.02948#A2.Thmlemma2)applied to our sequencem1,…,mTm\_\{1\},\\dots,m\_\{T\}, we get that

Pr⁡\[max1≤t≤T⁡\|mt\|≥D/4\]≤16​g2D2​∑t=1T1\(st\+γ\)2≤14,\\operatorname\{\{Pr\}\}\\left\[\\max\_\{1\\leq t\\leq T\}\|m\_\{t\}\|\\geq D/4\\right\]\\leq\\frac\{16g^\{2\}\}\{D^\{2\}\}\\sum\_\{t=1\}^\{T\}\\frac\{1\}\{\(s\_\{t\}\+\\gamma\)^\{2\}\}\\leq\\frac\{1\}\{4\},\(37\)where we used the assumed bound from[Item2](https://arxiv.org/html/2606.02948#A2.I1.i2)onH2​\(γ\)H\_\{2\}\(\\gamma\), and recalled thatg=L/8g=L/8\. Thus, with probability at least3/43/4, the sequencemtm\_\{t\}never exceedsD/4D/4in absolute value\. But on this event,mtm\_\{t\}coincides withztz\_\{t\}\. We therefore conclude that with probability at least3/43/4, the process stays active throughout, i\.e\., everyℓt=g​εt\\ell\_\{t\}=g\\varepsilon\_\{t\}; letAAdenote this event\. Recalling the lower bound on regret from \([36](https://arxiv.org/html/2606.02948#A2.E36)\), we get

𝔼⁡\[RegretT​\(f1:T;x1:T\)\]\\displaystyle\\operatorname\{\{\\mathds\{E\}\}\}\\left\[\\mathrm\{Regret\}\_\{T\}\(f\_\{1:T\};x\_\{1:T\}\)\\right\]≥𝔼⁡\[∑t=1Tℓt22​\(st\+γ\)\]\\displaystyle\\geq\\operatorname\{\{\\mathds\{E\}\}\}\\left\[\\sum\_\{t=1\}^\{T\}\\frac\{\\ell\_\{t\}^\{2\}\}\{2\(s\_\{t\}\+\\gamma\)\}\\right\]=Pr⁡\[A\]⋅𝔼⁡\[∑t=1Tℓt22​\(st\+γ\)\|A\]\+Pr⁡\[¬A\]⋅𝔼⁡\[∑t=1Tℓt22​\(st\+γ\)\|¬A\]⏟≥0\\displaystyle=\\operatorname\{\{Pr\}\}\[A\]\\cdot\\operatorname\{\{\\mathds\{E\}\}\}\\left\[\\sum\_\{t=1\}^\{T\}\\frac\{\\ell\_\{t\}^\{2\}\}\{2\(s\_\{t\}\+\\gamma\)\}\\Bigm\|A\\right\]\+\\underbrace\{\\operatorname\{\{Pr\}\}\[\\neg A\]\\cdot\\operatorname\{\{\\mathds\{E\}\}\}\\left\[\\sum\_\{t=1\}^\{T\}\\frac\{\\ell\_\{t\}^\{2\}\}\{2\(s\_\{t\}\+\\gamma\)\}\\Bigm\|\\neg A\\right\]\}\_\{\\geq 0\}≥3​L2512​∑t=1T1st\+γ\.\\displaystyle\\geq\\frac\{3L^\{2\}\}\{512\}\\sum\_\{t=1\}^\{T\}\\frac\{1\}\{s\_\{t\}\+\\gamma\}\.\(38\)

### Step 7: Choosingγ\\gamma

We now chooseγ\\gammaappropriately, so that both[Items1](https://arxiv.org/html/2606.02948#A2.I1.i1)and[2](https://arxiv.org/html/2606.02948#A2.I1.i2)hold\. Let

Ψ​\(γ\):=D2​γ\+L2​∑t=1T1st\+γ,γ≥0\.\\displaystyle\\Psi\(\\gamma\):=D^\{2\}\\gamma\+L^\{2\}\\sum\_\{t=1\}^\{T\}\\frac\{1\}\{s\_\{t\}\+\\gamma\},\\qquad\\gamma\\geq 0\.We claim thatinfγ≥0Ψ​\(γ\)\\inf\_\{\\gamma\\geq 0\}\\Psi\(\\gamma\)is attained at someγ⋆≥0\\gamma\_\{\\star\}\\geq 0, andγ⋆\\gamma\_\{\\star\}satisfies both the required conditions \(hence, we will chooseγ=γ⋆\\gamma=\\gamma\_\{\\star\}\)\. To see this, note first that

Ψ​\(2​L/D\)\\displaystyle\\Psi\(2L/D\)=2​L​D\+L2​∑t=1T1st\+2​L/D<∞,\\displaystyle=2LD\+L^\{2\}\\sum\_\{t=1\}^\{T\}\\frac\{1\}\{s\_\{t\}\+2L/D\}<\\infty,so letB:=Ψ​\(2​L/D\)<∞B:=\\Psi\(2L/D\)<\\infty\. Note thatB≥2​L​DB\\geq 2LD\. Then, for anyγ\>B\+1D2\\gamma\>\\frac\{B\+1\}\{D^\{2\}\},

Ψ​\(γ\)\\displaystyle\\Psi\(\\gamma\)≥D2​γ\>D2​\(B\+1D2\)=B\+1\>B\.\\displaystyle\\geq D^\{2\}\\gamma\>D^\{2\}\\left\(\\frac\{B\+1\}\{D^\{2\}\}\\right\)=B\+1\>B\.Thus, if the infimuminfγ≥0Ψ​\(γ\)\\inf\_\{\\gamma\\geq 0\}\\Psi\(\\gamma\)is attained at all, it is attained in\[0,B\+1D2\]\[0,\\frac\{B\+1\}\{D^\{2\}\}\], which includes2​L/D2L/D\.

Now note that if everyst\>0s\_\{t\}\>0, thenΨ​\(γ\)\\Psi\(\\gamma\)is continuous on\[0,B\+1D2\]\[0,\\frac\{B\+1\}\{D^\{2\}\}\]\. However, if anyst=0s\_\{t\}=0, then the term1st\+γ\\frac\{1\}\{s\_\{t\}\+\\gamma\}blows up atγ=0\\gamma=0\. Nevertheless, note in this case that for anyγ\>0\\gamma\>0,

Ψ​\(γ\)≥L2st\+γ=L2γ\.\\displaystyle\\Psi\(\\gamma\)\\geq\\frac\{L^\{2\}\}\{s\_\{t\}\+\\gamma\}=\\frac\{L^\{2\}\}\{\\gamma\}\.So, if we setδ:=L2B\+1\\delta:=\\frac\{L^\{2\}\}\{B\+1\}, then for any0<γ<δ0<\\gamma<\\delta,

Ψ​\(γ\)≥L2γ\>L2δ=B\+1\.\\displaystyle\\Psi\(\\gamma\)\\geq\\frac\{L^\{2\}\}\{\\gamma\}\>\\frac\{L^\{2\}\}\{\\delta\}=B\+1\.Furthermore,δ=L2B\+1≤L22​L​D\+1≤L22​L​D<2​L/D\\delta=\\frac\{L^\{2\}\}\{B\+1\}\\leq\\frac\{L^\{2\}\}\{2LD\+1\}\\leq\\frac\{L^\{2\}\}\{2LD\}<2L/D\. Thus, in this case, if the infimuminfγ≥0Ψ​\(γ\)\\inf\_\{\\gamma\\geq 0\}\\Psi\(\\gamma\)is attained at all, it is attained in\[δ,B\+1D2\]\[\\delta,\\frac\{B\+1\}\{D^\{2\}\}\]\. Furthermore,Ψ\\Psiis continuous on this interval\.

So, define the closed and bounded intervalK⊆\[0,∞\)K\\subseteq\[0,\\infty\)as

K=\{\[0,B\+1D2\]ifst\>0for allt,\[δ,B\+1D2\]otherwise\.\\displaystyle K=\\begin\{cases\}\\left\[0,\\frac\{B\+1\}\{D^\{2\}\}\\right\]&\\text\{if $s\_\{t\}\>0$ for all $t$\},\\\\ \\left\[\\delta,\\frac\{B\+1\}\{D^\{2\}\}\\right\]&\\text\{otherwise\}\.\\end\{cases\}\(39\)Then, it always holds that

- •2​L/D∈K2L/D\\in K\.
- •For anyγ≥0\\gamma\\geq 0such thatγ∉K\\gamma\\notin K,Ψ​\(γ\)\>Ψ​\(2​L/D\)\\Psi\(\\gamma\)\>\\Psi\(2L/D\)\.
- •Ψ\\Psiis continuous onKK\.

Then, by the extreme value theorem, there existsγ⋆∈K\\gamma\_\{\\star\}\\in Ksuch that

Ψ​\(γ⋆\)=minγ∈K⁡Ψ​\(γ\)≤Ψ​\(2​L/D\)\.\\displaystyle\\Psi\(\\gamma\_\{\\star\}\)=\\min\_\{\\gamma\\in K\}\\Psi\(\\gamma\)\\leq\\Psi\(2L/D\)\.Together with the properties ofKKabove, we have shown thatγ⋆\\gamma\_\{\\star\}attainsinfγ≥0Ψ​\(γ\)\\inf\_\{\\gamma\\geq 0\}\\Psi\(\\gamma\)\.

We now check[Items1](https://arxiv.org/html/2606.02948#A2.I1.i1)and[2](https://arxiv.org/html/2606.02948#A2.I1.i2)forγ=γ⋆\\gamma=\\gamma\_\{\\star\}\. Note that ifst\>0s\_\{t\}\>0for alltt, it immediately holds thatst\+γ⋆\>0s\_\{t\}\+\\gamma\_\{\\star\}\>0for alltt\. On the hand, if somest=0s\_\{t\}=0, thenγ⋆\>0\\gamma\_\{\\star\}\>0, and we again get thatst\+γ⋆\>0s\_\{t\}\+\\gamma\_\{\\star\}\>0for alltt\. Thus,[Item1](https://arxiv.org/html/2606.02948#A2.I1.i1)holds\.

Now, forγ\>0\\gamma\>0, we have that

Ψ′​\(γ\)=D2−L2​∑t=1T1\(st\+γ\)2=D2−L2​H2​\(γ\)\.\\displaystyle\\Psi^\{\\prime\}\(\\gamma\)=D^\{2\}\-L^\{2\}\\sum\_\{t=1\}^\{T\}\\frac\{1\}\{\(s\_\{t\}\+\\gamma\)^\{2\}\}=D^\{2\}\-L^\{2\}H\_\{2\}\(\\gamma\)\.Ifγ⋆\>0\\gamma\_\{\\star\}\>0, by the first\-order optimality condition, we have that

H2​\(γ⋆\)=D2L2\.\\displaystyle H\_\{2\}\(\\gamma\_\{\\star\}\)=\\frac\{D^\{2\}\}\{L^\{2\}\}\.\(40\)On the other hand, ifγ⋆=0\\gamma\_\{\\star\}=0, the right derivative ofΨ\\Psiatγ=0\\gamma=0must be non\-negative, which gives

H2​\(γ⋆\)≤D2L2\\displaystyle H\_\{2\}\(\\gamma\_\{\\star\}\)\\leq\\frac\{D^\{2\}\}\{L^\{2\}\}Thus, we have shown that[Item2](https://arxiv.org/html/2606.02948#A2.I1.i2)holds\.

### Step 8: Putting things together, and concluding

Recalling the regret lower bound \([38](https://arxiv.org/html/2606.02948#A2.E38)\), and plugging inγ⋆\\gamma\_\{\\star\}, we have that

𝔼⁡\[RegretT​\(f1:T;x1:T\)\]\\displaystyle\\operatorname\{\{\\mathds\{E\}\}\}\\left\[\\mathrm\{Regret\}\_\{T\}\(f\_\{1:T\};x\_\{1:T\}\)\\right\]≥3​L2512​∑t=1T1st\+γ⋆\.\\displaystyle\\geq\\frac\{3L^\{2\}\}\{512\}\\sum\_\{t=1\}^\{T\}\\frac\{1\}\{s\_\{t\}\+\\gamma\_\{\\star\}\}\.We now wish to further lower bound the right\-hand side above withΨ​\(γ⋆\)\\Psi\(\\gamma\_\{\\star\}\)\. For this, suppose thatγ⋆=0\\gamma\_\{\\star\}=0\. In this case,

Ψ​\(γ⋆\)=L2​∑t=1T1st\+γ⋆\.\\displaystyle\\Psi\(\\gamma\_\{\\star\}\)=L^\{2\}\\sum\_\{t=1\}^\{T\}\\frac\{1\}\{s\_\{t\}\+\\gamma\_\{\\star\}\}\.On the other hand, ifγ⋆\>0\\gamma\_\{\\star\}\>0, we have by the first\-order optimality condition \([40](https://arxiv.org/html/2606.02948#A2.E40)\) that

D2=L2​∑t=1T1\(st\+γ⋆\)2\\displaystyle D^\{2\}=L^\{2\}\\sum\_\{t=1\}^\{T\}\\frac\{1\}\{\(s\_\{t\}\+\\gamma\_\{\\star\}\)^\{2\}\}⟹\\displaystyle\\quad\\impliesD2​γ⋆=L2​∑t=1Tγ⋆\(st\+γ⋆\)2=L2​∑t=1T1st\+γ⋆⋅γ⋆st\+γ⋆≤L2​∑t=1T1st\+γ⋆,\\displaystyle D^\{2\}\\gamma\_\{\\star\}=L^\{2\}\\sum\_\{t=1\}^\{T\}\\frac\{\\gamma\_\{\\star\}\}\{\(s\_\{t\}\+\\gamma\_\{\\star\}\)^\{2\}\}=L^\{2\}\\sum\_\{t=1\}^\{T\}\\frac\{1\}\{s\_\{t\}\+\\gamma\_\{\\star\}\}\\cdot\\frac\{\\gamma\_\{\\star\}\}\{s\_\{t\}\+\\gamma\_\{\\star\}\}\\leq L^\{2\}\\sum\_\{t=1\}^\{T\}\\frac\{1\}\{s\_\{t\}\+\\gamma\_\{\\star\}\},and hence,

Ψ​\(γ⋆\)=D2​γ⋆\+L2​∑t=1T1st\+γ⋆≤2​L2​∑t=1T1st\+γ⋆\.\\displaystyle\\Psi\(\\gamma\_\{\\star\}\)=D^\{2\}\\gamma\_\{\\star\}\+L^\{2\}\\sum\_\{t=1\}^\{T\}\\frac\{1\}\{s\_\{t\}\+\\gamma\_\{\\star\}\}\\leq 2L^\{2\}\\sum\_\{t=1\}^\{T\}\\frac\{1\}\{s\_\{t\}\+\\gamma\_\{\\star\}\}\.In either case, we are guaranteed thatΨ​\(γ⋆\)≤2​L2​∑t=1T1st\+γ⋆\\Psi\(\\gamma\_\{\\star\}\)\\leq 2L^\{2\}\\sum\_\{t=1\}^\{T\}\\frac\{1\}\{s\_\{t\}\+\\gamma\_\{\\star\}\}; substituting this in our regret bound above, we get

𝔼⁡\[RegretT​\(f1:T;x1:T\)\]\\displaystyle\\operatorname\{\{\\mathds\{E\}\}\}\\left\[\\mathrm\{Regret\}\_\{T\}\(f\_\{1:T\};x\_\{1:T\}\)\\right\]≥31024​Ψ​\(γ⋆\)=31024⋅infγ≥0\[D2​γ\+L2​∑t=1T1st\+γ\]\.\\displaystyle\\geq\\frac\{3\}\{1024\}\\Psi\(\\gamma\_\{\\star\}\)=\\frac\{3\}\{1024\}\\cdot\\inf\_\{\\gamma\\geq 0\}\\left\[D^\{2\}\\gamma\+L^\{2\}\\sum\_\{t=1\}^\{T\}\\frac\{1\}\{s\_\{t\}\+\\gamma\}\\right\]\.\(41\)
The bound above holds for every deterministic learning algorithm, over the randomness ofε1,…,εT\\varepsilon\_\{1\},\\dots,\\varepsilon\_\{T\}\. This implies a corresponding lower bound for any randomized algorithm, by the standard Yao argument\[Yao,[1983](https://arxiv.org/html/2606.02948#bib.bib22)\]\. Concretely, let𝒜\\mathcal\{A\}be any randomized algorithm\. Conditioned on any fixed realizationrrof its randomness, the algorithm𝒜r\\mathcal\{A\}\_\{r\}is deterministic\. Thus, we can invoke the lower bound in \([41](https://arxiv.org/html/2606.02948#A2.E41)\) for𝒜r\\mathcal\{A\}\_\{r\}, to get

𝔼ε1:T⁡\[Regret𝒜r,T​\(f1:T;x1:T\)\]\\displaystyle\\operatorname\{\{\\mathds\{E\}\}\}\_\{\\varepsilon\_\{1:T\}\}\\left\[\\mathrm\{Regret\}\_\{\\mathcal\{A\}\_\{r\},T\}\(f\_\{1:T\};x\_\{1:T\}\)\\right\]≥31024⋅infγ≥0\[D2​γ\+L2​∑t=1T1st\+γ\]\.\\displaystyle\\geq\\frac\{3\}\{1024\}\\cdot\\inf\_\{\\gamma\\geq 0\}\\left\[D^\{2\}\\gamma\+L^\{2\}\\sum\_\{t=1\}^\{T\}\\frac\{1\}\{s\_\{t\}\+\\gamma\}\\right\]\.Averaging over the randomnessrrthen gives that

𝔼r⁡𝔼ε1:T⁡\[Regret𝒜r,T​\(f1:T;x1:T\)\]=\\displaystyle\\operatorname\{\{\\mathds\{E\}\}\}\_\{r\}\\operatorname\{\{\\mathds\{E\}\}\}\_\{\\varepsilon\_\{1:T\}\}\\left\[\\mathrm\{Regret\}\_\{\\mathcal\{A\}\_\{r\},T\}\(f\_\{1:T\};x\_\{1:T\}\)\\right\]=𝔼ε1:T⁡𝔼r⁡\[Regret𝒜r,T​\(f1:T;x1:T\)\]≥31024⋅infγ≥0\[D2​γ\+L2​∑t=1T1st\+γ\]\.\\displaystyle\\operatorname\{\{\\mathds\{E\}\}\}\_\{\\varepsilon\_\{1:T\}\}\\operatorname\{\{\\mathds\{E\}\}\}\_\{r\}\\left\[\\mathrm\{Regret\}\_\{\\mathcal\{A\}\_\{r\},T\}\(f\_\{1:T\};x\_\{1:T\}\)\\right\]\\geq\\frac\{3\}\{1024\}\\cdot\\inf\_\{\\gamma\\geq 0\}\\left\[D^\{2\}\\gamma\+L^\{2\}\\sum\_\{t=1\}^\{T\}\\frac\{1\}\{s\_\{t\}\+\\gamma\}\\right\]\.In particular, this implies the existence of a fixed sequenceε1,…,εT\\varepsilon\_\{1\},\\dots,\\varepsilon\_\{T\}, and corresponding functionsf1,…,fTf\_\{1\},\\dots,f\_\{T\}, such that

𝔼r⁡\[Regret𝒜r,T​\(f1:T;x1:T\)\]≥31024⋅infγ≥0\[D2​γ\+L2​∑t=1T1st\+γ\]\.\\displaystyle\\operatorname\{\{\\mathds\{E\}\}\}\_\{r\}\\left\[\\mathrm\{Regret\}\_\{\\mathcal\{A\}\_\{r\},T\}\(f\_\{1:T\};x\_\{1:T\}\)\\right\]\\geq\\frac\{3\}\{1024\}\\cdot\\inf\_\{\\gamma\\geq 0\}\\left\[D^\{2\}\\gamma\+L^\{2\}\\sum\_\{t=1\}^\{T\}\\frac\{1\}\{s\_\{t\}\+\\gamma\}\\right\]\.Since the lower bound above holds for every randomized learning algorithm𝒜\\mathcal\{A\}, we get

ℜT​\(s1:T\)\\displaystyle\\mathfrak\{R\}\_\{T\}\(s\_\{1:T\}\)≥31024⋅infγ≥0\[D2​γ\+L2​∑t=1T1st\+γ\]\\displaystyle\\geq\\frac\{3\}\{1024\}\\cdot\\inf\_\{\\gamma\\geq 0\}\\left\[D^\{2\}\\gamma\+L^\{2\}\\sum\_\{t=1\}^\{T\}\\frac\{1\}\{s\_\{t\}\+\\gamma\}\\right\]≥c⋅infρ≥0\[L2​∑t=1Tmin⁡\{Dρ,1st\}\+D​ρ\]\.\\displaystyle\\geq c\\cdot\\inf\_\{\\rho\\geq 0\}\\left\[L^\{2\}\\sum\_\{t=1\}^\{T\}\\min\\left\\\{\\frac\{D\}\{\\rho\},\\frac\{1\}\{s\_\{t\}\}\\right\\\}\+D\\rho\\right\]\.\(using[B\.1](https://arxiv.org/html/2606.02948#A2.Thmlemma1)\)This concludes the proof of[Theorem3](https://arxiv.org/html/2606.02948#Thmtheorem3)\. ∎

### B\.1Optimality of regime\-specific rates

Here, we argue that the rates obtained by our algorithm in the different curvature in[Corollary3\.1](https://arxiv.org/html/2606.02948#S3.Thmlemma1)are optimal\.

Recall from[Theorem3](https://arxiv.org/html/2606.02948#Thmtheorem3)that the minimax regret is lower bounded \(upto constant factors\) byOPTT0​\(0\)\\mathrm\{OPT\}^\{0\}\_\{T\}\(0\), where

OPTT0​\(0\)≥c⋅infρ≥0\[∑t=1Tmin\{1ρ,1St\}\+ρ\]\.⏟:=Ψ​\(ρ\)\\displaystyle\\mathrm\{OPT\}^\{0\}\_\{T\}\(0\)\\geq c\\cdot\\underbrace\{\\inf\_\{\\rho\\geq 0\}\\left\[\\sum\_\{t=1\}^\{T\}\\min\\left\\\{\\frac\{1\}\{\\rho\},\\frac\{1\}\{S\_\{t\}\}\\right\\\}\+\\rho\\right\]\.\}\_\{:=\\Psi\(\\rho\)\}Here, the constantcchides a dependence ond,D,Ld,D,L\. It thus suffices to calculateΨ​\(ρ\)\\Psi\(\\rho\)in the regimes whereSt=tγS\_\{t\}=t^\{\\gamma\}\(forγ≥1/2\\gamma\\geq 1/2\), and show a matching characterization as that in[Corollary3\.1](https://arxiv.org/html/2606.02948#S3.Thmlemma1)\.

Consider

Ψ​\(ρ\)=infρ≥0\[∑t=1Tmin⁡\{1ρ,1St\}\+ρ\],\\displaystyle\\Psi\(\\rho\)=\\inf\_\{\\rho\\geq 0\}\\left\[\\sum\_\{t=1\}^\{T\}\\min\\left\\\{\\frac\{1\}\{\\rho\},\\frac\{1\}\{S\_\{t\}\}\\right\\\}\+\\rho\\right\],forSt=tγS\_\{t\}=t^\{\\gamma\}\.

Towards this, we first further characterize the precise form ofΨ​\(ρ\)\\Psi\(\\rho\)\. For0≤t<T0\\leq t<T, consider the intervalsIt=\[tγ,\(t\+1\)γ\)I\_\{t\}=\[t^\{\\gamma\},\(t\+1\)^\{\\gamma\}\), and letIT=\[Tγ,∞\)I\_\{T\}=\[T^\{\\gamma\},\\infty\)\. For anyρ∈It\\rho\\in I\_\{t\}, observe thatΨ​\(ρ\)\\Psi\(\\rho\)evaluates to

tρ\+ρ\+∑t<i≤Ti−γ\.\\displaystyle\\frac\{t\}\{\\rho\}\+\\rho\+\\sum\_\{t<i\\leq T\}i^\{\-\\gamma\}\.Note that the last term is constant for everyρ∈It\\rho\\in I\_\{t\}\. Thus, the “unconstrained” minimizer for this interval balances the first two terms, giving

ρ^t=t\.\\displaystyle\\hat\{\\rho\}\_\{t\}=\\sqrt\{t\}\.This is a valid value forρ^t\\hat\{\\rho\}\_\{t\}, providedt∈It\\sqrt\{t\}\\in I\_\{t\}\. However, ift∉It\\sqrt\{t\}\\notin I\_\{t\}, we simply setρ^t\\hat\{\\rho\}\_\{t\}to be eithertγt^\{\\gamma\}or\(t\+1\)γ\(t\+1\)^\{\\gamma\}, based on whichever of the two evaluates to a smallerΨ​\(ρ\)\\Psi\(\\rho\)\. Thus, we get that

infρ≥0Ψ​\(ρ\)=min0≤t≤T⁡\(tρ^t\+ρ^t\+∑t<i≤Ti−γ\)\.\\displaystyle\\inf\_\{\\rho\\geq 0\}\\Psi\(\\rho\)=\\min\_\{0\\leq t\\leq T\}\\left\(\\frac\{t\}\{\\hat\{\\rho\}\_\{t\}\}\+\\hat\{\\rho\}\_\{t\}\+\\sum\_\{t<i\\leq T\}i^\{\-\\gamma\}\\right\)\.\(42\)Whenγ<1/2\\gamma<1/2, it may be verified that the minimum above gets achieved att=Tt=T\(for large enoughTT\), wherebyρ^T=T\\hat\{\\rho\}\_\{T\}=\\sqrt\{T\}, giving that the quantity in \([42](https://arxiv.org/html/2606.02948#A2.E42)\) is at leastT/T\+T=Ω​\(T\)T/\\sqrt\{T\}\+\\sqrt\{T\}=\\Omega\(\\sqrt\{T\}\)\. Whenγ≥1/2\\gamma\\geq 1/2, the minimum in \([42](https://arxiv.org/html/2606.02948#A2.E42)\) gets achieved att=0t=0asρ^0→0\\hat\{\\rho\}\_\{0\}\\to 0, whereby the quantity in \([42](https://arxiv.org/html/2606.02948#A2.E42)\) is at least∑i=1Ti−γ\\sum\_\{i=1\}^\{T\}i^\{\-\\gamma\}, which gives the claimed lower bounds on the rates in each regime ofγ\\gamma\.

### B\.2RelatingOPTT0​\(r\)\\mathrm\{OPT\}^\{0\}\_\{T\}\(r\)andOPTT0​\(0\)\\mathrm\{OPT\}^\{0\}\_\{T\}\(0\)

###### Claim B\.3\.

Recall the definition ofOPTT0​\(r\)\\mathrm\{OPT\}^\{0\}\_\{T\}\(r\):

OPTT0​\(r\)=infρ≥r\[∑t=1Tmin⁡\{125​L2​d2​Dρ,2​L2St\}\+d​D​ρ\]\.\\displaystyle\\mathrm\{OPT\}^\{0\}\_\{T\}\(r\)=\\inf\_\{\\rho\\geq r\}\\left\[\\sum\_\{t=1\}^\{T\}\\min\\left\\\{\\frac\{125L^\{2\}d^\{2\}D\}\{\\rho\},\\frac\{2L^\{2\}\}\{S\_\{t\}\}\\right\\\}\+dD\\rho\\right\]\.For anyr≥0r\\geq 0, it holds that

OPTT0​\(r\)\\displaystyle\\mathrm\{OPT\}^\{0\}\_\{T\}\(r\)≤OPTT0​\(0\)\+d​D​r\.\\displaystyle\\leq\\mathrm\{OPT\}^\{0\}\_\{T\}\(0\)\+dDr\.

###### Proof\.

For anyρ≥0\\rho\\geq 0, letρ~=max⁡\(r,ρ\)\\tilde\{\\rho\}=\\max\(r,\\rho\)\. Then observe that for anytt,

min⁡\{125​L2​d2​Dρ~,2​L2St\}\\displaystyle\\min\\left\\\{\\frac\{125L^\{2\}d^\{2\}D\}\{\\tilde\{\\rho\}\},\\frac\{2L^\{2\}\}\{S\_\{t\}\}\\right\\\}≤min⁡\{125​L2​d2​Dρ,2​L2St\}\.\\displaystyle\\leq\\min\\left\\\{\\frac\{125L^\{2\}d^\{2\}D\}\{\\rho\},\\frac\{2L^\{2\}\}\{S\_\{t\}\}\\right\\\}\.Furthermore,

d​D​ρ~≤d​D​ρ\+d​D​r\.\\displaystyle dD\\tilde\{\\rho\}\\leq dD\\rho\+dDr\.Therefore,

∑t=1Tmin⁡\{125​L2​d2​Dρ~,2​L2St\}\+d​D​ρ~\\displaystyle\\sum\_\{t=1\}^\{T\}\\min\\left\\\{\\frac\{125L^\{2\}d^\{2\}D\}\{\\tilde\{\\rho\}\},\\frac\{2L^\{2\}\}\{S\_\{t\}\}\\right\\\}\+dD\\tilde\{\\rho\}≤∑t=1Tmin⁡\{125​L2​d2​Dρ,2​L2St\}\+d​D​ρ\+d​D​r\.\\displaystyle\\leq\\sum\_\{t=1\}^\{T\}\\min\\left\\\{\\frac\{125L^\{2\}d^\{2\}D\}\{\\rho\},\\frac\{2L^\{2\}\}\{S\_\{t\}\}\\right\\\}\+dD\\rho\+dDr\.Infimizing overρ≥0\\rho\\geq 0gives,

infρ≥0\[∑t=1Tmin⁡\{125​L2​d2​Dρ~,2​L2St\}\+d​D​ρ~\]≤infρ≥0\[∑t=1Tmin⁡\{125​L2​d2​Dρ,2​L2St\}\+d​D​ρ\+d​D​r\]\\displaystyle\\inf\_\{\\rho\\geq 0\}\\left\[\\sum\_\{t=1\}^\{T\}\\min\\left\\\{\\frac\{125L^\{2\}d^\{2\}D\}\{\\tilde\{\\rho\}\},\\frac\{2L^\{2\}\}\{S\_\{t\}\}\\right\\\}\+dD\\tilde\{\\rho\}\\right\]\\leq\\inf\_\{\\rho\\geq 0\}\\left\[\\sum\_\{t=1\}^\{T\}\\min\\left\\\{\\frac\{125L^\{2\}d^\{2\}D\}\{\\rho\},\\frac\{2L^\{2\}\}\{S\_\{t\}\}\\right\\\}\+dD\\rho\+dDr\\right\]⟹\\displaystyle\\impliesinfρ≥r\[∑t=1Tmin⁡\{125​L2​d2​Dρ,2​L2St\}\+d​D​ρ\]≤infρ≥0\[∑t=1Tmin⁡\{125​L2​d2​Dρ,2​L2St\}\+d​D​ρ\]\+d​D​r\\displaystyle\\inf\_\{\\rho\\geq r\}\\left\[\\sum\_\{t=1\}^\{T\}\\min\\left\\\{\\frac\{125L^\{2\}d^\{2\}D\}\{\\rho\},\\frac\{2L^\{2\}\}\{S\_\{t\}\}\\right\\\}\+dD\\rho\\right\]\\leq\\inf\_\{\\rho\\geq 0\}\\left\[\\sum\_\{t=1\}^\{T\}\\min\\left\\\{\\frac\{125L^\{2\}d^\{2\}D\}\{\\rho\},\\frac\{2L^\{2\}\}\{S\_\{t\}\}\\right\\\}\+dD\\rho\\right\]\+dDr⟹\\displaystyle\\impliesOPTT0​\(r\)≤OPTT0​\(0\)\+d​D​r\.∎\\displaystyle\\mathrm\{OPT\}^\{0\}\_\{T\}\(r\)\\leq\\mathrm\{OPT\}^\{0\}\_\{T\}\(0\)\+dDr\.\\qed