Dynamic Regret in Online Convex Optimization with Indicator Switching Costs

# Dynamic Regret in Online Convex Optimization with Indicator Switching Costs
Source: [https://arxiv.org/html/2609.30556](https://arxiv.org/html/2609.30556)
George IosifidisAffiliation:TU Delft, Netherlands

###### Abstract

We study dynamic regret in online convex optimization with an*indicator switching cost*: a fixed penalty incurred whenever two consecutive decisions differ\. This captures startup overheads such as server activation, model deployment, and cache updates, and on a bounded domain it recovers norm\-based movement costs as a special case\. Existing guarantees for indicator costs handle only static comparators\. We show that a direct extension of these techniques to dynamic regret provably fails, motivating a different approach\. We propose a meta\-learning framework: a set of randomized lazy FTRL base learners restarted at dyadic time scales, aggregated by a movement\-aware master that mixes their proposal densities and samples actions via maximal coupling of consecutive mixtures\. The resulting algorithm satisfies, in expectation,ℛT𝟏≤𝒪~​\(min⁡\{T⁡\(ST\+1\),T2/3​\(PT\+1\)1/3\}\)\\mathcal\{R\}^\{\\mathbf\{1\}\}\_\{T\}\\leq\\tilde\{\\mathcal\{O\}\}\(\\min\\\{\\sqrt\{T\(S\_\{T\}\{\+\}1\)\},T^\{2/3\}\(P\_\{T\}\+1\)^\{1/3\}\\\}\), whereℛT𝟏\\mathcal\{R\}^\{\\mathbf\{1\}\}\_\{T\}is the dynamic regret plus the cumulative indicator switching cost,STS\_\{T\}counts comparator switches, andPTP\_\{T\}is the comparator path length\. The bound holds simultaneously for all sequences and requires no prior knowledge ofSTS\_\{T\}orPTP\_\{T\}: it is minimax\-optimal \(up to logarithmic factors\) for tracking piecewise\-constant comparators, and also captures frequently moving comparators with small total path length\.

## 1Introduction

We study Online Convex Optimization \(OCO\) in non\-stationary environments\. At each roundt∈\[T\]t\\in\[T\], a learner selects an action𝒙t∈𝒳\\bm\{x\}\_\{t\}\\in\\mathcal\{X\}*before*observing the convex lossft​\(⋅\)f\_\{t\}\(\\cdot\), and incursft​\(𝒙t\)f\_\{t\}\(\\bm\{x\}\_\{t\}\)\. A central performance criterion in this setting is*dynamic regret*, which compares the learner against a time\-varying comparator sequence\{𝒖t\}t=1T\\\{\\bm\{u\}\_\{t\}\\\}\_\{t=1\}^\{T\}\. To capture stability requirements, dynamic regret is often augmented with a*switching cost*mt​\(𝒙t,𝒙t−1\)m\_\{t\}\(\\bm\{x\}\_\{t\},\\bm\{x\}\_\{t\-1\}\)that penalizes changes between consecutive actions\. The augmented formulation, known as*smoothed*OCO \(SOCO\), models the central tradeoff between responsiveness to non\-stationarity and stability of the decision sequence\. While this tradeoff is well understood for switching costs that are norm\-based, the regime in which any reconfiguration incurs an overhead independent of the magnitude of the change remains underexplored\.

In many practical problems, the switching cost is modeled as an*indicator switching cost*\[[6](https://arxiv.org/html/2609.30556#bib.bib8),[13](https://arxiv.org/html/2609.30556#bib.bib23),[18](https://arxiv.org/html/2609.30556#bib.bib12)\]:λt1\{𝒙t≠𝒙t−1\},\\lambda\_\{t\}\\,\\mathbf\{1\}\\\{\\bm\{x\}\_\{t\}\\neq\\bm\{x\}\_\{t\-1\}\\\},which charges a \(possibly time\-varying\) penaltyλt\\lambda\_\{t\}whenever𝒙t≠𝒙t−1\\bm\{x\}\_\{t\}\\neq\\bm\{x\}\_\{t\-1\}, regardless of how large the change is\. Such costs arise whenever any reconfiguration triggers a one\-shot overhead: server activation in cloud scheduling, cache updates in networks, model redeployment in production ML pipelines, retraining\-trigger costs in continual learning, and the per\-iteration privacy budget in differentially private learning\[[3](https://arxiv.org/html/2609.30556#bib.bib14)\]\. The indicator switching cost is, in fact, the*more demanding*primitive\. Settingλt=‖𝒙t−𝒙t−1‖\\lambda\_\{t\}=\\\|\\bm\{x\}\_\{t\}\-\\bm\{x\}\_\{t\-1\}\\\|recovers the norm\-based switching cost as a special case, and on a bounded domain∥𝒙t−𝒙t−1∥≤D1\{𝒙t≠𝒙t−1\}\\\|\\bm\{x\}\_\{t\}\-\\bm\{x\}\_\{t\-1\}\\\|\\leq D\\,\\mathbf\{1\}\\\{\\bm\{x\}\_\{t\}\\neq\\bm\{x\}\_\{t\-1\}\\\}whereD≐diam⁡\(𝒳\)D\\doteq\\mathrm\{diam\}\(\\mathcal\{X\}\)is the diameter of the set𝒳\\mathcal\{X\}, so any algorithm that controls the indicator switching cost automatically controls the norm\-based one \(up to the factorDD\), but not vice versa\. In this sense indicator switching costs subsume norm\-based ones and impose a strictly stronger notion of stability\.

In Learning with Expert Advice \(LEA\), where the decision set is the simplex and losses are linear, indicator switching costs admit a useful reduction\. Under a maximal coupling111Specifically, under such a coupling,Pr⁡\(𝒙t≠𝒙t−1\)=12​‖𝒙t−𝒙t−1‖1\\Pr\(\\bm\{x\}\_\{t\}\\neq\\bm\{x\}\_\{t\-1\}\)=\\tfrac\{1\}\{2\}\\\|\\bm\{x\}\_\{t\}\-\\bm\{x\}\_\{t\-1\}\\\|\_\{1\}; see, e\.g\.,\[[10](https://arxiv.org/html/2609.30556#bib.bib19), Sec\. 5\.2\]\., the expected number of switches is exactly theℓ1\\ell\_\{1\}movement of the played distributions, so the problem reduces to controllingℓ1\\ell\_\{1\}norm on the simplex, and both static\[[4](https://arxiv.org/html/2609.30556#bib.bib25)\]and dynamic222In LEA, Dynamic regret is known as tracking regret\. Also, strongly adaptive regret implies tracking regret\[[9](https://arxiv.org/html/2609.30556#bib.bib21), Sec\. 3\]\.\[[10](https://arxiv.org/html/2609.30556#bib.bib19)\]regret bounds follow from standard algorithms such as exponentiated gradient and fixed\-share\. In general OCO, a line of work has nevertheless made progress on this harder regime via the FTRL framework, obtaining minimax\-optimal*static*regret under indicator switching costs\[[19](https://arxiv.org/html/2609.30556#bib.bib13),[3](https://arxiv.org/html/2609.30556#bib.bib14)\]\. These remain the only available results in OCO, because the other main framework, Online Mirror Descent \(OMD\), defines each iterate recursively from the previous one via a Bregman divergence term \(see, e\.g\.,\[[14](https://arxiv.org/html/2609.30556#bib.bib2), Sec\. 6\]\)\. This recursive dependence of each action on its predecessor precludes a closed\-form density that can be evaluated pointwise, which is necessary for the maximal coupling used to control indicator switches\.

The dynamic\-regret case has thus remained open, and the difficulty traces back to the FTRL framework itself\. Even without switching costs, vanilla FTRL is suboptimal for dynamic regret\[[12](https://arxiv.org/html/2609.30556#bib.bib5)\]; prior work has recovered dynamic\-regret guarantees through enhancements such as history pruning\[[15](https://arxiv.org/html/2609.30556#bib.bib10),[16](https://arxiv.org/html/2609.30556#bib.bib18)\], but these methods proceed by linearizing the FTRL objective, after which the iterate also becomes a recursive update, inheriting the same difficulty as OMD in deriving the density\. Our first contribution shows that even when assisted with perturbations and fixed restarts \(which can be viewed as the analogue of history pruning but without linearization\) FTRL still fails to deliver \(optimal\) sublinear dynamic regret\. A different architecture beyond a single FTRL run is therefore required\.

The natural question is thus:*can one obtain dynamic regret guarantees in OCO when the learner pays indicator switching costs, and if so, against which comparator classes?*We answer this in the affirmative for the two canonical comparator classes in the dynamic regret literature: piecewise\-constant comparators that change at mostSTS\_\{T\}times, and comparators whose total variation is bounded byPTP\_\{T\}\. As we detail later in the contributions, the bounded\-variation class is the larger of the two, and it further admits comparators that change at every round while moving only slightly, sequences against which the switch countSTS\_\{T\}is uninformative\. Against the first class, we obtain order\-optimal dynamic regret of𝒪~​\(\(ST\+1\)​T\)\\tilde\{\\mathcal\{O\}\}\(\\sqrt\{\(S\_\{T\}\+1\)\\,T\}\), matching the minimax rate up to logarithmic factors\. Against the second, the same algorithm attains𝒪~​\(T2/3​PT1/3\)\\tilde\{\\mathcal\{O\}\}\(T^\{2/3\}P\_\{T\}^\{1/3\}\)\. A single comparator\-oblivious algorithm thus handles both canonical forms of non\-stationarity simultaneously\. The approach section below details how this is achieved through a multiscale meta\-learner over restarted lazy randomized FTRL experts\.

### 1\.1Contributions

We first state the standing assumptions used throughout the paper\.

###### Assumption 1\.

The set𝒳⊂ℝd\\mathcal\{X\}\\subset\\mathbb\{R\}^\{d\}is convex and bounded with diameterD≐sup𝐱,𝐲∈𝒳‖𝐱−𝐲‖D\\doteq\\sup\_\{\\bm\{x\},\\bm\{y\}\\in\\mathcal\{X\}\}\\\|\\bm\{x\}\-\\bm\{y\}\\\|and radiusR≐sup𝐱∈𝒳‖𝐱‖R\\doteq\\sup\_\{\\bm\{x\}\\in\\mathcal\{X\}\}\\\|\\bm\{x\}\\\|\.

###### Assumption 2\.

The lossft:𝒳→ℝf\_\{t\}:\\mathcal\{X\}\\to\\mathbb\{R\}is twice differentiable, convex,GG\-Lipschitz, andβ\\beta\-smooth; i\.e\.,

‖∇ft​\(𝒙\)‖≤G,∇2ft​\(𝒙\)⪯β​I,∀t∈\[T\],𝒙∈𝒳\.\\\|\\nabla f\_\{t\}\(\\bm\{x\}\)\\\|\\leq G,\\qquad\\nabla^\{2\}f\_\{t\}\(\\bm\{x\}\)\\preceq\\beta I,\\qquad\\forall t\\in\[T\],\\bm\{x\}\\in\\mathcal\{X\}\.

###### Assumption 3\.

The switching coefficients\{λt\}t=2T\\\{\\lambda\_\{t\}\\\}\_\{t=2\}^\{T\}satisfy0<λt≤λ0<\\lambda\_\{t\}\\leq\\lambdafor a known constantλ\>0\\lambda\>0\.

###### Assumption 4\.

There existsMf\>0M\_\{f\}\>0such that0≤ft​\(𝐱\)≤Mf,∀t∈\[T\],𝐱∈𝒳0\\leq f\_\{t\}\(\\bm\{x\}\)\\leq M\_\{f\},\\quad\\forall t\\in\[T\],\\bm\{x\}\\in\\mathcal\{X\}\.

Our performance criterion is the*dynamic regret with indicator switching cost*ℛT𝟏\\mathcal\{R\}^\{\\mathbf\{1\}\}\_\{T\}, defined as:

ℛT𝟏\(\{𝒖t\}t=1T\)≐∑t=1T\(ft\(𝒙t\)−ft\(𝒖t\)\)\+∑t=2Tλt1\{𝒙t≠𝒙t−1\},\\displaystyle\\mathcal\{R\}^\{\\mathbf\{1\}\}\_\{T\}\(\\\{\\bm\{u\}\_\{t\}\\\}\_\{t=1\}^\{T\}\)\\doteq\\sum\_\{t=1\}^\{T\}\\bigl\(f\_\{t\}\(\\bm\{x\}\_\{t\}\)\-f\_\{t\}\(\\bm\{u\}\_\{t\}\)\\bigr\)\+\\sum\_\{t=2\}^\{T\}\\lambda\_\{t\}\\,\\mathbf\{1\}\\\{\\bm\{x\}\_\{t\}\\neq\\bm\{x\}\_\{t\-1\}\\\},When clear from context, we drop\{𝒖t\}t=1T\\\{\\bm\{u\}\_\{t\}\\\}\_\{t=1\}^\{T\}from the argument\.ℛT𝟏\\mathcal\{R\}^\{\\mathbf\{1\}\}\_\{T\}compares the learner against a time\-varying comparator sequence\{𝒖t\}t=1T=\(𝒖1,…,𝒖T\)\\\{\\bm\{u\}\_\{t\}\\\}\_\{t=1\}^\{T\}=\(\\bm\{u\}\_\{1\},\\ldots,\\bm\{u\}\_\{T\}\)while charging the learner for its own switches\. We measure the complexity of the comparator sequence through two canonical quantities:

ST\(\{𝒖t\}t=1T\)≐∑t=2T𝟏\{𝒖t≠𝒖t−1\},PT\(\{𝒖t\}t=1T\)≐∑t=2T∥𝒖t−𝒖t−1∥,\\displaystyle S\_\{T\}\(\\\{\\bm\{u\}\_\{t\}\\\}\_\{t=1\}^\{T\}\)\\doteq\\sum\_\{t=2\}^\{T\}\\mathbf\{1\}\\\{\\bm\{u\}\_\{t\}\\neq\\bm\{u\}\_\{t\-1\}\\\},\\qquad P\_\{T\}\(\\\{\\bm\{u\}\_\{t\}\\\}\_\{t=1\}^\{T\}\)\\doteq\\sum\_\{t=2\}^\{T\}\\\|\\bm\{u\}\_\{t\}\-\\bm\{u\}\_\{t\-1\}\\\|,These measures induce two comparator classes,

𝒰S​\(s\)≐\{\{𝒖t\}t=1T:ST​\(\{𝒖t\}t=1T\)≤s\},𝒰P​\(p\)≐\{\{𝒖t\}t=1T:PT​\(\{𝒖t\}t=1T\)≤p\}\.\\mathcal\{U\}\_\{S\}\(s\)\\doteq\\\{\\\{\\bm\{u\}\_\{t\}\\\}\_\{t=1\}^\{T\}:S\_\{T\}\(\\\{\\bm\{u\}\_\{t\}\\\}\_\{t=1\}^\{T\}\)\\leq s\\\},\\qquad\\mathcal\{U\}\_\{P\}\(p\)\\doteq\\\{\\\{\\bm\{u\}\_\{t\}\\\}\_\{t=1\}^\{T\}:P\_\{T\}\(\\\{\\bm\{u\}\_\{t\}\\\}\_\{t=1\}^\{T\}\)\\leq p\\\}\.These classes capture different forms of non\-stationarity\.𝒰S​\(s\)\\mathcal\{U\}\_\{S\}\(s\)allows the comparator to change at mostsstimes, regardless of the magnitude\.𝒰P​\(p\)\\mathcal\{U\}\_\{P\}\(p\)instead places no limit on how often the comparator changes, only on the total magnitude of changes, which cannot exceedpp\. Since any sequence withsschanges has total movement at mostD​sDs, we have𝒰S​\(s\)⊆𝒰P​\(D​s\)\\mathcal\{U\}\_\{S\}\(s\)\\subseteq\\mathcal\{U\}\_\{P\}\(Ds\); but𝒰P\\mathcal\{U\}\_\{P\}also contains sequences that, e\.g\., move at every round by small amounts, for whichSTS\_\{T\}becomes uninformative\. Our guarantees are therefore stated simultaneously for every sequence as functions ofSTS\_\{T\}andPTP\_\{T\}, with the algorithm itself oblivious to which complexity is smaller\. The contributions are listed below\.

An impossibility for randomized FTRL\.We first show that the existing machinery for indicator switching costs, known as FPRLL\[[18](https://arxiv.org/html/2609.30556#bib.bib12),[19](https://arxiv.org/html/2609.30556#bib.bib13),[3](https://arxiv.org/html/2609.30556#bib.bib14)\]333These works use different names for essentially the same algorithm: FTRL with perturbations and a barrier; see the Addendum section of\[[19](https://arxiv.org/html/2609.30556#bib.bib13)\]\., cannot deliver optimal dynamic regret:

1. \(a\)​​​​Without restarts, FPRLL suffersΩ⁡\(T\)\\Omega\(T\)dynamic regret even on𝒰S​\(1\)\\mathcal\{U\}\_\{S\}\(1\)\.
2. \(b\)​​​​With any fixed restart periodkk, FPRLL\(k\)\(k\)suffersΩ⁡\(T2/3​τ1/3/log⁡T\)\\Omega\\bigl\(T^\{2/3\}\\tau^\{1/3\}/\\log T\\bigr\)dynamic regret on𝒰S​\(τ\)\\mathcal\{U\}\_\{S\}\(\\tau\)\.

Note that the same lower bounds remain valid for the larger class𝒰P​\(⋅\)\\mathcal\{U\}\_\{P\}\(\\cdot\)\.

Strongly adaptive regret\.We introduce a comparator\-oblivious algorithm that combines restarted FPRLL base learners at all dyadic time scales, aggregated by the discounted\-normal predictor of\[[10](https://arxiv.org/html/2609.30556#bib.bib19)\]\. For every intervalI=\[s,e\]⊆\[T\]I=\[s,e\]\\subseteq\[T\]of lengthLL,

ℛI𝟏\(𝒖\)≐𝔼\[∑t∈I\(ft\(𝒙t\)−ft\(𝒖\)\)\+∑t=s\+1eλt1\{𝒙t≠𝒙t−1\}\]≤𝒪~\(L\)\\displaystyle\\mathcal\{R\}^\{\\mathbf\{1\}\}\_\{I\}\(\\bm\{u\}\)\\doteq\\mathbb\{E\}\\Biggl\[\\sum\_\{t\\in I\}\\bigl\(f\_\{t\}\(\\bm\{x\}\_\{t\}\)\-f\_\{t\}\(\\bm\{u\}\)\\bigr\)\+\\sum\_\{t=s\+1\}^\{e\}\\lambda\_\{t\}\\,\\mathbf\{1\}\\\{\\bm\{x\}\_\{t\}\\neq\\bm\{x\}\_\{t\-1\}\\\}\\Biggr\]\\;\\leq\\;\\tilde\{\\mathcal\{O\}\}\(\\sqrt\{L\}\)\([Theorem12](https://arxiv.org/html/2609.30556#Thmtheorem12)\)uniformly in𝒖∈𝒳\\bm\{u\}\\in\\mathcal\{X\}and in the intervalII\. To our knowledge, this is the first strongly adaptive regret guarantee under indicator switching costs for OCO, and may be of independent interest\.

Optimal dynamic regret for piecewise\-constant comparators\.A standard reduction along the time segmentation of\{𝒖t\}t=1T\\\{\\bm\{u\}\_\{t\}\\\}\_\{t=1\}^\{T\}converts the strongly adaptive bound above into a dynamic regret guarantee:

𝔼\[ℛT𝟏\]≤𝒪~​\(\(ST\+1\)​T\),\\displaystyle\\mathop\{\\mathbb\{E\}\}\\left\[\{\\mathcal\{R\}^\{\\mathbf\{1\}\}\_\{T\}\}\\right\]\\;\\leq\\;\\tilde\{\\mathcal\{O\}\}\\bigl\(\\sqrt\{\(S\_\{T\}\+1\)\\,T\}\\bigr\),\([Corollary13](https://arxiv.org/html/2609.30556#Thmtheorem13)\)without prior knowledge ofSTS\_\{T\}\. This matches, up to logarithmic factors, the minimax rate for tracking moving comparators\[[24](https://arxiv.org/html/2609.30556#bib.bib3)\], despite the learner incurring an additional cost for its indicator switches\.

Path\-length refinement and a unified bound\.The same algorithm is adaptive to path measure:

𝔼⁡\[ℛT𝟏\]≤𝒪~​\(max⁡\{PT1/3​T2/3,T\}\)\.\\displaystyle\\mathbb\{E\}\\bigl\[\\mathcal\{R\}^\{\\mathbf\{1\}\}\_\{T\}\\bigr\]\\;\\leq\\;\\tilde\{\\mathcal\{O\}\}\\\!\\left\(\\max\\\{P\_\{T\}^\{1/3\}T^\{2/3\}\\\!\\\!,\\;\\sqrt\{T\}\\\}\\right\)\.\([Theorem14](https://arxiv.org/html/2609.30556#Thmtheorem14)\)Combining the two yields the unified guarantee

𝔼⁡\[ℛT𝟏\]≤𝒪~​\(min⁡\{\(ST\+1\)​T,\(PT\+1\)1/3​T2/3\}\)\.\\displaystyle\\mathbb\{E\}\\bigl\[\\mathcal\{R\}^\{\\mathbf\{1\}\}\_\{T\}\\bigr\]\\;\\leq\\;\\tilde\{\\mathcal\{O\}\}\\\!\\left\(\\min\\Bigl\\\{\\sqrt\{\(S\_\{T\}\+1\)\\,T\},\\;\\;\(P\_\{T\}\+1\)^\{1/3\}\\,T^\{2/3\}\\Bigr\\\}\\right\)\.\(1\)
Limitation\.In norm\-based SOCO, the bound𝒪⁡\(T⁡\(1\+PT\)\)\{\\mathcal\{O\}\}\(\\sqrt\{T\(1\+P\_\{T\}\)\}\)is attainable on the larger class𝒰P\\mathcal\{U\}\_\{P\}, and since𝒰S​\(s\)⊆𝒰P​\(D​s\)\\mathcal\{U\}\_\{S\}\(s\)\\subseteq\\mathcal\{U\}\_\{P\}\(Ds\), that single bound automatically yields the optimal𝒪⁡\(T⁡\(1\+ST\)\)\{\\mathcal\{O\}\}\(\\sqrt\{T\(1\+S\_\{T\}\)\}\)on𝒰S\\mathcal\{U\}\_\{S\}\. Under indicator switching costs we do not preserve this unification: we recover𝒪~​\(T⁡\(ST\+1\)\)\\tilde\{\\mathcal\{O\}\}\(\\sqrt\{T\(S\_\{T\}\+1\)\}\)on𝒰S\\mathcal\{U\}\_\{S\}, but on𝒰P\\mathcal\{U\}\_\{P\}our bound degrades to𝒪~​\(T2/3​PT1/3\)\\tilde\{\\mathcal\{O\}\}\(T^\{2/3\}P\_\{T\}^\{1/3\}\)\. Whether𝒪~​\(T⁡\(1\+PT\)\)\\tilde\{\\mathcal\{O\}\}\(\\sqrt\{T\(1\+P\_\{T\}\)\}\)is achievable under indicator switching remains open\. The difficulty is that the learner is charged per change, whereas the comparator is charged only by total movementPTP\_\{T\}\.

### 1\.2Overview of the approach

To streamline presentation, we sketch here the algorithmic structure and analysis strategy\. The algorithm has two layers: a base layer of restarted lazy randomized FTRL learners, one per dyadic scale, and a meta layer that aggregates them based on their expected loss and decision change\.

Base layer\.For each dyadic scaleH∈ℋ≐\{1,2,4,…,2⌊log2⁡T⌋\}H\\in\\mathcal\{H\}\\doteq\\\{1,2,4,\\dots,2^\{\\lfloor\\log\_\{2\}T\\rfloor\}\\\}, we run a fresh copy of FPRLL that restarts at the beginning of every block of lengthHH\. Each copy maintains a probability density𝒬t\(H\)\\mathcal\{Q\}\_\{t\}^\{\(H\)\}over𝒳\\mathcal\{X\}, induced by a perturbed FTRL objective\. Small scales adapt quickly but restart, and hence switch, often; large scales are stable but slow to respond to non\-stationarity\. The base layer thus spans the full tradeoff between responsiveness and switching control\.

Meta layer:At each roundtt, the master maintains weights𝒗t∈Δℋ\\bm\{v\}\_\{t\}\\in\\Delta\_\{\\mathcal\{H\}\}and forms the mixture density

𝒫t≐∑H∈ℋvt,H​𝒬t\(H\)\.\\displaystyle\{\\mathcal\{P\}\}\_\{t\}\\;\\doteq\\;\\sum\_\{H\\in\\mathcal\{H\}\}v\_\{t,H\}\\,\\mathcal\{Q\}\_\{t\}^\{\(H\)\}\.\(2\)Action𝒙t\\bm\{x\}\_\{t\}is sampled from𝒫t\{\\mathcal\{P\}\}\_\{t\}via maximal coupling with𝒫t−1\{\\mathcal\{P\}\}\_\{t\-1\}, so thatPr⁡\(𝒙t≠𝒙t−1\)=‖𝒫t−𝒫t−1‖TV\\Pr\(\\bm\{x\}\_\{t\}\\neq\\bm\{x\}\_\{t\-1\}\)\\\!=\\\!\\\|\{\\mathcal\{P\}\}\_\{t\}\\\!\-\\\!\{\\mathcal\{P\}\}\_\{t\-1\}\\\|\_\{\\mathrm\{TV\}\}, where∥⋅∥TV\\\|\\cdot\\\|\_\{\\mathrm\{TV\}\}is total variation distance\. After observingftf\_\{t\}, the master scores each scaleHHby the surrogate lossgt\(H\)≐𝔼𝒙∼𝒬t\(H\)​\[ft​\(𝒙\)\]\+λ​‖𝒬t\(H\)−𝒬t−1\(H\)‖TV,g\_\{t\}^\{\(H\)\}\\\!\\doteq\\\!\\mathbb\{E\}\_\{\\bm\{x\}\\sim\\mathcal\{Q\}\_\{t\}^\{\(H\)\}\}\[f\_\{t\}\(\\bm\{x\}\)\]\\\!\+\\\!\\lambda\\,\\\|\\mathcal\{Q\}\_\{t\}^\{\(H\)\}\\\!\-\\\!\\mathcal\{Q\}\_\{t\-1\}^\{\(H\)\}\\\|\_\{\\mathrm\{TV\}\},which charges each scale for both its expected loss and the switching cost it would have incurred had the learner followed it alone\.

We learn the mixing weights using the discounted\-normal predictor of\[[10](https://arxiv.org/html/2609.30556#bib.bib19)\]\. It achieves strongly adaptive regret, hence competing with every sub\-interval, while also controlling the number of transitions between experts within it\. In our setting, this ensures the master performs nearly as the best restart scale for that interval, without paying an uncontrolled cost for switching between scales\.

Analytically, at the base layer, we fix a dyadic scaleHHand characterize the dynamic regret of FPRLL restarted everyHHrounds \([Theorem7](https://arxiv.org/html/2609.30556#Thmtheorem7)\)\. The resulting bound exposes the tradeoff between the cost of restarts and the cost of comparator variation\. At the meta layer, a total\-variation decomposition of the combined actions, and the surrogate loss design, enable a reduction to the “HH\-expertsλ/2\\lambda/2\-switching” problem onℋ\\mathcal\{H\}\([Lemma10](https://arxiv.org/html/2609.30556#Thmtheorem10)\), which is handled via the discounted\-normal predictor to obtain a strongly adaptive guarantee at the meta level\. Combining the two layers yields our two branches in \([1](https://arxiv.org/html/2609.30556#S1.E1)\): for𝒰S\\mathcal\{U\}\_\{S\}, we partition the horizon into piecewise\-constant segments, cover each by its dyadic decomposition, and sum the base regret against the segment’s static comparator, giving𝒪~​\(\(ST\+1\)​T\)\\tilde\{\\mathcal\{O\}\}\(\\sqrt\{\(S\_\{T\}\+1\)T\}\)\. For𝒰P\\mathcal\{U\}\_\{P\}, sparsity is uninformative, but some dyadic scale inℋ\\mathcal\{H\}always matches the local rate of comparator drift; the master tracks it, yielding𝒪~​\(T2/3​PT1/3\)\\tilde\{\\mathcal\{O\}\}\(T^\{2/3\}P\_\{T\}^\{1/3\}\)\.

## 2The FPRLL base learner

Setup\.Let𝒳≐\{𝒙∈ℝd:sc\(𝒙\)≥0,c=1,…,C\}\\mathcal\{X\}\\doteq\\\{\\bm\{x\}\\in\\mathbb\{R\}^\{d\}:s\_\{c\}\(\\bm\{x\}\)\\geq 0,\\ c=1,\\dots,C\\\}with eachscs\_\{c\}concave \(so𝒳\\mathcal\{X\}is convex\)\. Without loss of generality,𝟎\\bm\{0\}is strictly feasible andsc​\(𝟎\)=1s\_\{c\}\(\\bm\{0\}\)=1\. Forγ∈\(0,1\)\\gamma\\in\(0,1\), we define the shrunk domain𝒳γ≐\(1−γ\)​𝒳\\mathcal\{X\}^\{\\gamma\}\\doteq\(1\-\\gamma\)\\mathcal\{X\}and the scaled log\-barrier:

bγ​\(𝒙\)≐b⁡\(𝒙\)Mγ,b⁡\(𝒙\)≐∑c=1Clog⁡s¯csc​\(𝒙\),s¯c≐sup𝒛∈𝒳sc​\(𝒛\),Mγ≐max⁡\{1,sup𝒛∈𝒳γb⁡\(𝒛\)\}\.b\_\{\\gamma\}\(\\bm\{x\}\)\\doteq\\frac\{b\(\\bm\{x\}\)\}\{M\_\{\\gamma\}\},\\qquad b\(\\bm\{x\}\)\\doteq\\sum\_\{c=1\}^\{C\}\\log\\\!\\frac\{\\bar\{s\}\_\{c\}\}\{s\_\{c\}\(\\bm\{x\}\)\},\\qquad\\bar\{s\}\_\{c\}\\doteq\\sup\_\{\\bm\{z\}\\in\\mathcal\{X\}\}s\_\{c\}\(\\bm\{z\}\),\\qquad M\_\{\\gamma\}\\doteq\\max\\Bigl\\\{1,\\,\\sup\_\{\\bm\{z\}\\in\\mathcal\{X\}^\{\\gamma\}\}b\(\\bm\{z\}\)\\Bigr\\\}\.This is the standard logarithmic barrier, shifted to makeb≥0b\\geq 0on𝒳\\mathcal\{X\}and scaled so thatbγ≤1b\_\{\\gamma\}\\leq 1on𝒳γ\\mathcal\{X\}^\{\\gamma\}, as in\[[19](https://arxiv.org/html/2609.30556#bib.bib13)\]\. We letGc≐sup𝒙∈𝒳γ‖∇sc​\(𝒙\)‖,∀cG\_\{c\}\\\!\\doteq\\\!\\sup\_\{\\bm\{x\}\\in\\mathcal\{X\}^\{\\gamma\}\}\\\!\\\|\\nabla s\_\{c\}\(\\bm\{x\}\)\\\|,\\forall c\. Next, we define theσ\\sigma\-strongly convex functionFtF\_\{t\}:

Ft≐∑τ=0tfτ,withf0≐r\+bγ,r⁡\(𝒙\)≐σ2​‖𝒙‖2\.\\displaystyle F\_\{t\}\\doteq\\sum\_\{\\tau=0\}^\{t\}f\_\{\\tau\},\\quad\\text\{with\}\\quad f\_\{0\}\\doteq r\+b\_\{\\gamma\},\\quad r\(\\bm\{x\}\)\\doteq\\tfrac\{\\sigma\}\{2\}\\\|\\bm\{x\}\\\|^\{2\}\.\(3\)
Minimizers and their densities\.Let𝒑∼Lap⁡\(μ\)\\bm\{p\}\\sim\\mathrm\{Lap\}\(\\mu\)have densityν\(𝒑\)=\(2μ\)−dexp\(−∥𝒑∥1/μ\)\\nu\(\\bm\{p\}\)=\(2\\mu\)^\{\-d\}\\exp\(\-\\\|\\bm\{p\}\\\|\_\{1\}/\\mu\)\. The*fresh\-perturbation minimizer*at roundttis

𝒙~t\+1≐argmin𝒙∈𝒳\{Ft​\(𝒙\)\+⟨𝒑t,𝒙⟩\},\\displaystyle\\tilde\{\\bm\{x\}\}\_\{t\+1\}\\doteq\\argmin\_\{\\bm\{x\}\\in\\mathcal\{X\}\}\\bigl\\\{F\_\{t\}\(\\bm\{x\}\)\+\\langle\\bm\{p\}\_\{t\},\\bm\{x\}\\rangle\\bigr\\\},\(4\)with induced distribution𝒬t\+1\\mathcal\{Q\}\_\{t\+1\}\. Strong convexity makes𝒙↦−∇Ft​\(𝒙\)\\bm\{x\}\\mapsto\-\\nabla F\_\{t\}\(\\bm\{x\}\)a smooth bijection onint⁡\(𝒳\)\\mathrm\{int\}\(\\mathcal\{X\}\), so the change\-of\-variables formula \([Lemma15](https://arxiv.org/html/2609.30556#Thmtheorem15)\) gives

𝒬t​\(𝒙\)=ν⁡\(−∇Ft−1​\(𝒙\)\)​\|det\(−∇2Ft−1​\(𝒙\)\)\|,𝒙∈int⁡\(𝒳\)\.\\displaystyle\\mathcal\{Q\}\_\{t\}\(\\bm\{x\}\)=\\nu\\bigl\(\-\\nabla F\_\{t\-1\}\(\\bm\{x\}\)\\bigr\)\\,\\bigl\|\\det\\bigl\(\-\\nabla^\{2\}F\_\{t\-1\}\(\\bm\{x\}\)\\bigr\)\\bigr\|,\\qquad\\bm\{x\}\\in\\mathrm\{int\}\(\\mathcal\{X\}\)\.\(5\)The closed form lets us evaluate𝒬t\\mathcal\{Q\}\_\{t\}*pointwise*, which the lazy coupling below exploits directly\.

Two perspectives\.[Algorithm1](https://arxiv.org/html/2609.30556#alg1)can be deployed in two ways\. As a standalone algorithm, it lazy\-samples an action𝒙t∼𝒬t\\bm\{x\}\_\{t\}\\sim\\mathcal\{Q\}\_\{t\}at each round \(lines 5–12\),*maximally coupling*consecutive draws so thatPr⁡\(𝒙t\+1≠𝒙t\)=‖𝒬t−𝒬t\+1‖TV\.\\Pr\(\\bm\{x\}\_\{t\+1\}\\neq\\bm\{x\}\_\{t\}\)\\;=\\;\\\|\\mathcal\{Q\}\_\{t\}\-\\mathcal\{Q\}\_\{t\+1\}\\\|\_\{\\mathrm\{TV\}\}\.Alternatively, the meta\-algorithm of[Section3](https://arxiv.org/html/2609.30556#S3)consumes[Algorithm1](https://arxiv.org/html/2609.30556#alg1)as a*density oracle*: it queries𝒬t\\mathcal\{Q\}\_\{t\}without invoking the sampler, and lazy\-samples instead at the mixture level\. Either way, the analysis below targets the same per\-round quantity,

𝔼𝒙∼𝒬t​\[ft​\(𝒙\)\]\+‖𝒬t−𝒬t−1‖TV,\\displaystyle\\mathbb\{E\}\_\{\\bm\{x\}\\sim\\mathcal\{Q\}\_\{t\}\}\[f\_\{t\}\(\\bm\{x\}\)\]\\;\+\\;\\\|\\mathcal\{Q\}\_\{t\}\-\\mathcal\{Q\}\_\{t\-1\}\\\|\_\{\\mathrm\{TV\}\},which is the expected regret\-plus\-switching cost when the algorithm is run standalone, and also the surrogate score charged to each base learner by the meta\-algorithm\.

Algorithm 1Follow the Perturbed Regularized Lazy Leader \(FPRLL\)1:horizon

TT, domain

𝒳\\mathcal\{X\}, parameters

γ,σ,μ\>0\\gamma,\\sigma,\\mu\>0
2:actions

𝒙1,…,𝒙T\\bm\{x\}\_\{1\},\\dots,\\bm\{x\}\_\{T\}
3:Sample

𝒑0∼Lap⁡\(μ\)\\bm\{p\}\_\{0\}\\sim\\mathrm\{Lap\}\(\\mu\); set

𝒙1←argmin𝒙∈𝒳\{f0​\(𝒙\)\+⟨𝒑0,𝒙⟩\}\\bm\{x\}\_\{1\}\\leftarrow\\argmin\_\{\\bm\{x\}\\in\\mathcal\{X\}\}\\\{f\_\{0\}\(\\bm\{x\}\)\+\\langle\\bm\{p\}\_\{0\},\\bm\{x\}\\rangle\\\}
4:for

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

5:Play

𝒙t\\bm\{x\}\_\{t\}; observe

ftf\_\{t\}and incur loss

ft​\(𝒙t\)f\_\{t\}\(\\bm\{x\}\_\{t\}\)
6:Evaluate

𝒬t​\(𝒙t\)\\mathcal\{Q\}\_\{t\}\(\\bm\{x\}\_\{t\}\)and

𝒬t\+1​\(𝒙t\)\\mathcal\{Q\}\_\{t\+1\}\(\\bm\{x\}\_\{t\}\)via \([5](https://arxiv.org/html/2609.30556#S2.E5)\); sample

z∼Unif⁡\[0,𝒬t​\(𝒙t\)\]z\\sim\\mathrm\{Unif\}\[0,\\,\\mathcal\{Q\}\_\{t\}\(\\bm\{x\}\_\{t\}\)\]
7:if

z<𝒬t\+1​\(𝒙t\)z<\\mathcal\{Q\}\_\{t\+1\}\(\\bm\{x\}\_\{t\}\)then

8:

𝒙t\+1←𝒙t\\bm\{x\}\_\{t\+1\}\\leftarrow\\bm\{x\}\_\{t\}⊳\\trianglerightretain: switching probability=0=0here

9:else

10:repeat⊳\\trianglerightsample from residual of𝒬t\+1\\mathcal\{Q\}\_\{t\+1\}

11:Sample

𝒑∼Lap⁡\(μ\)\\bm\{p\}\\sim\\mathrm\{Lap\}\(\\mu\); solve

𝒚←argmin𝒙∈𝒳\{Ft​\(𝒙\)\+⟨𝒑,𝒙⟩\}\\bm\{y\}\\leftarrow\\argmin\_\{\\bm\{x\}\\in\\mathcal\{X\}\}\\\{F\_\{t\}\(\\bm\{x\}\)\+\\langle\\bm\{p\},\\bm\{x\}\\rangle\\\}
12:Evaluate

𝒬t\+1​\(𝒚\)\\mathcal\{Q\}\_\{t\+1\}\(\\bm\{y\}\)and

𝒬t​\(𝒚\)\\mathcal\{Q\}\_\{t\}\(\\bm\{y\}\)via \([5](https://arxiv.org/html/2609.30556#S2.E5)\); sample

z′∼Unif⁡\[0,𝒬t\+1​\(𝒚\)\]z^\{\\prime\}\\sim\\mathrm\{Unif\}\[0,\\,\\mathcal\{Q\}\_\{t\+1\}\(\\bm\{y\}\)\]
13:until

z′\>𝒬t​\(𝒚\)z^\{\\prime\}\>\\mathcal\{Q\}\_\{t\}\(\\bm\{y\}\)
14:

𝒙t\+1←𝒚\\bm\{x\}\_\{t\+1\}\\leftarrow\\bm\{y\}
15:endif

16:endfor

Regret guarantees\.The following statements characterize the performance of FPRLL and its restarted variants\. The first statement describes dynamic\-regret of FPRLL, explicit in all tunable parameters\(σ,μ\)\(\\sigma,\\mu\)and the comparator path budgetPTP\_\{T\}\.

###### Theorem 5\(Dynamic regret of FPRLL\)\.

IfFPRLL\\mathrm\{FPRLL\}is run withγ=1T\\gamma=\\frac\{1\}\{\\sqrt\{T\}\}, then for anyσ,μ\>0\\sigma,\\mu\>0,

𝔼\[ℛT𝟏\]≤G22​σ​T\+R​2​d​μ\+\(T​G\+σ​R\)​PT\+\(C​Gc​PT\+G​R\)​T\+λ​T​\(β​dσ\+d​Gμ\)\+σ2​R2\+1\.\\mathop\{\\mathbb\{E\}\}\\left\[\{\\mathcal\{R\}^\{\\mathbf\{1\}\}\_\{T\}\}\\right\]\\leq\\frac\{G^\{2\}\}\{2\\sigma\}T\+R\\sqrt\{2d\}\\,\\mu\+\(TG\+\\sigma R\)P\_\{T\}\+\\bigl\(CG\_\{c\}P\_\{T\}\+GR\\bigr\)\\sqrt\{T\}\+\\lambda T\\Big\(\\frac\{\\beta d\}\{\\sigma\}\{\+\}\\frac\{\\sqrt\{d\}\\,G\}\{\\mu\}\\Big\)\+\\frac\{\\sigma\}\{2\}R^\{2\}\+1\.In particular, choosingμ⋆=λ​G​TR​2,σ⋆=\(G2\+2​λ​β​d\)​TR2,\\mu^\{\\star\}=\\sqrt\{\\frac\{\\lambda GT\}\{R\\sqrt\{2\}\}\},\\qquad\\sigma^\{\\star\}=\\sqrt\{\\frac\{\(G^\{2\}\+2\\lambda\\beta d\)\\,T\}\{R^\{2\}\}\},yields

𝔼\[ℛT𝟏\]≤\(R\+PT\)​\(G2\+2​λ​β​d\)​T\+3​λ​d​R​G​T\+T​G​PT\+\(C​Gc​PT\+G​R\)​T\+1\.\\mathop\{\\mathbb\{E\}\}\\left\[\{\\mathcal\{R\}^\{\\mathbf\{1\}\}\_\{T\}\}\\right\]\\leq\(R\+P\_\{T\}\)\\sqrt\{\(G^\{2\}\+2\\lambda\\beta d\)\\,T\}\+3\\sqrt\{\\lambda dRGT\}\+TG\\,P\_\{T\}\+\\bigl\(CG\_\{c\}P\_\{T\}\+GR\\bigr\)\\sqrt\{T\}\+1\.

Specializing the above result to a*fixed*comparator on a length\-kkblock and optimizing\(γ,σ,μ\)\(\\gamma,\\sigma,\\mu\)accordingly yields an𝒪⁡\(Cbase​k\)\\mathcal\{O\}\(C\_\{\\mathrm\{base\}\}\\sqrt\{k\}\)static\-regret bound with indicator switching cost, which is a per\-block primitive used throughout the multiscale analysis\.

###### Corollary 6\(Static regret on a block\)\.

ConsiderFPRLL\\mathrm\{FPRLL\}, and letI=\{\(j−1\)​k\+1,…,j​k\}I=\\\{\(j\-1\)k\+1,\\dots,jk\\\}be any full restart block\. On this block, the algorithm is restarted and run withγ=1k,μk⋆=λ​G​kR​2,σk⋆=\(G2\+2​λ​β​d\)​kR\.\\gamma=\\frac\{1\}\{\\sqrt\{k\}\},\\mu^\{\\star\}\_\{k\}=\\sqrt\{\\frac\{\\lambda Gk\}\{R\\sqrt\{2\}\}\},\\sigma^\{\\star\}\_\{k\}=\\frac\{\\sqrt\{\(G^\{2\}\+2\\lambda\\beta d\)\\,k\}\}\{R\}\.Then, for every fixed comparator𝐮∈𝒳\\bm\{u\}\\in\\mathcal\{X\},

𝔼\[ℛI𝟏​\(𝒖\)\]\\displaystyle\\mathop\{\\mathbb\{E\}\}\\left\[\{\\mathcal\{R\}^\{\\mathbf\{1\}\}\_\{I\}\(\\bm\{u\}\)\}\\right\]≐𝔼\[∑t∈I\(ft\(𝒙t\)−ft\(𝒖\)\)\+λ∑t=\(j−1\)​k\+1j​k𝟏\{xt≠xt−1\}\]\\displaystyle\\doteq\\mathbb\{E\}\\Big\[\\sum\_\{t\\in I\}\\bigl\(f\_\{t\}\(\\bm\{x\}\_\{t\}\)\-f\_\{t\}\(\\bm\{u\}\)\\bigr\)\+\\lambda\\sum\_\{t=\(j\-1\)k\+1\}^\{jk\}\\mathbf\{1\}\\\{x\_\{t\}\\neq x\_\{t\-1\}\\\}\\Big\]≤R​\(G2\+2​λ​β​d\)​k\+3​λ​d​R​G​k\+G​R​k\+λ\+1=Cbase​k,\\displaystyle\\leq R\\sqrt\{\(G^\{2\}\+2\\lambda\\beta d\)\\,k\}\+3\\sqrt\{\\lambda dRG\\,k\}\+GR\\sqrt\{k\}\+\\lambda\+1=C\_\{\\mathrm\{base\}\}\\sqrt\{k\},whereCbase≐R​G2\+2​λ​β​d\+3​λ​d​R​G\+G​R\+λ\+1\.C\_\{\\mathrm\{base\}\}\\doteq R\\sqrt\{G^\{2\}\+2\\lambda\\beta d\}\+3\\sqrt\{\\lambda dRG\}\+GR\+\\lambda\+1\.

For eachkk, let FPRLL\(k\)\(k\)denote the algorithm that restarts FPRLL everykkrounds, and letℛ𝟏,k≐𝔼\[ℛT𝟏​\(\{𝒖t\}t=1T\)\]\\mathcal\{R\}^\{\\mathbf\{1\},\{\{k\}\}\}\\doteq\\mathop\{\\mathbb\{E\}\}\\left\[\{\\mathcal\{R\}^\{\\mathbf\{1\}\}\_\{T\}\(\\\{\\bm\{u\}\_\{t\}\\\}\_\{t=1\}^\{T\}\)\}\\right\]be its expected dynamic regret against\{𝒖t\}t=1T\\\{\\bm\{u\}\_\{t\}\\\}\_\{t=1\}^\{T\}\. The following theorem shows that, among the dyadic restart periodsk∈ℋk\\in\\mathcal\{H\}, there always exists one that achieves a balance between laziness cost and tracking cost\.

###### Theorem 7\(A dyadic restart scale\)\.

Assume for simplicity thatTTis a power of two, and letℋ≐\{1,2,4,…,T\}\\mathcal\{H\}\\doteq\\\{1,2,4,\\dots,T\\\}\. For eachk∈ℋk\\in\\mathcal\{H\}, FPRLL\(k\)\(k\)uses within each block the tuningγ=1k,μk⋆=λ​G​kR​2,σk⋆=\(G2\+2​λ​β​d\)​kR\.\\gamma=\\frac\{1\}\{\\sqrt\{k\}\},\\ \\mu^\{\\star\}\_\{k\}=\\sqrt\{\\frac\{\\lambda Gk\}\{R\\sqrt\{2\}\}\},\\ \\sigma^\{\\star\}\_\{k\}=\\frac\{\\sqrt\{\(G^\{2\}\+2\\lambda\\beta d\)\\,k\}\}\{R\}\.Define the constantsA≐Cbase\+λ,B≐G2\+2​λ​β​d\+C​Gc\.A\\doteq C\_\{\\mathrm\{base\}\}\+\\lambda,\\ B\\doteq\\sqrt\{G^\{2\}\+2\\lambda\\beta d\}\+CG\_\{c\}\.Then there exists a dyadic restart scalek†∈ℋk^\{\\dagger\}\\in\\mathcal\{H\}such that

ℛT𝟏,k†≤2​min1≤k≤T⁡\(A​Tk\+\(B\+G\)​PT​k\)\.\\mathcal\{R\}^\{\\mathbf\{1\},\{\{k^\{\\dagger\}\}\}\}\_\{T\}\\;\\leq\\;\\sqrt\{2\}\\,\\min\_\{1\\leq k\\leq T\}\\left\(A\\frac\{T\}\{\\sqrt\{k\}\}\+\(B\+G\)P\_\{T\}\\,k\\right\)\.In particular, forPT=𝒪⁡\(Tα\)P\_\{T\}=\\mathcal\{O\}\(T^\{\\alpha\}\),α∈\[0,1\)\\alpha\\in\[0,1\),ℛ𝟏,k†=𝒪⁡\(T2/3​PT1/3\)\.\\mathcal\{R\}^\{\\mathbf\{1\},\{\{k^\{\\dagger\}\}\}\}=\\mathcal\{O\}\\big\(T^\{2/3\}P\_\{T\}^\{1/3\}\\big\)\.

We complement[Theorem7](https://arxiv.org/html/2609.30556#Thmtheorem7)with a matching lower bound, up to logarithmic factors, for restarted randomized lazy learners of the form in[Algorithm1](https://arxiv.org/html/2609.30556#alg1)\. The lower bound exposes a tradeoff in the restart periodkkbetween tracking \(ft​\(𝒙t\)−ft​\(𝒖t\)f\_\{t\}\(\\bm\{x\}\_\{t\}\)\-f\_\{t\}\(\\bm\{u\}\_\{t\}\)\), and laziness costs𝟏\{𝒙t≠𝒙t−1\}\\mathbf\{1\}\\\{\\bm\{x\}\_\{t\}\\neq\\bm\{x\}\_\{t\-1\}\\\}\.

Tracking cost\.A long restart period prevents the learner from reacting to comparator switches that occur inside a block\. The next theorem captures this through a single oblivious distribution that is hard simultaneously for allkk\.

###### Theorem 8\(Tracking lower bound\)\.

Consider online linear optimization on𝒳=\[−1,1\]\\mathcal\{X\}=\[\-1,1\]with lossesft​\(x\)=gt​xf\_\{t\}\(x\)=g\_\{t\}x,gt∈\{−1,\+1\}g\_\{t\}\\in\\\{\-1,\+1\\\}\. Letτ≥1\\tau\\geq 1andT≥4​τT\\geq 4\\tau\. There exists a distribution𝒟\\mathcal\{D\}over oblivious loss sequences such that, for every integerk∈\[4,T/τ\]k\\in\[4,\\,T/\\tau\], FPRLL\(k\)\(k\)run against𝒟\\mathcal\{D\}satisfies

𝔼\[ℛT𝟏\(u1:T\)\]=Ω\(k​τlog⁡\(T/τ\)\)\\mathbb\{E\}\\bigl\[\\mathcal\{R\}^\{\\mathbf\{1\}\}\_\{T\}\(u\_\{1:T\}\)\\bigr\]\\;=\\;\\Omega\\left\(\\frac\{k\\tau\}\{\\log\(T/\\tau\)\}\\right\)for the associated comparator sequence withST\(u1:T\)=τS\_\{T\}\(u\_\{1:T\}\)=\\tauandPT\(u1:T\)=2τP\_\{T\}\(u\_\{1:T\}\)=2\\tau\.

Thus the tracking term isΩ⁡\(k​τ/log⁡\(T/τ\)\)\\Omega\(k\\tau/\\log\(T/\\tau\)\), which worsens withkk\.

Laziness cost\.A short restart period forces repeated starts from scratch\. Adapting\[[19](https://arxiv.org/html/2609.30556#bib.bib13), Thm\. 4\], on a length\-kkblock, each algorithm that makesO⁡\(k\)O\(\\sqrt\{k\}\)expected switches must incurΩ⁡\(k\)\\Omega\(\\sqrt\{k\}\)expected regret against a fixed comparator\. Replaying this hard instance over theT/kT/kblocks givesΩ⁡\(T/k\)\\Omega\(T/\\sqrt\{k\}\)regret against a stationary comparator withST=PT=0S\_\{T\}\\\!=\\\!P\_\{T\}\\\!=\\\!0; see[Lemma19](https://arxiv.org/html/2609.30556#Thmtheorem19)\. This term improves withkk\.

For every fixedkk, mixing the tracking adversary with the laziness adversary tuned to that scale gives

𝔼⁡\[ℛT𝟏\]=Ω⁡\(k​τlog⁡\(T/τ\)\+Tk\)\.\\mathbb\{E\}\\bigl\[\\mathcal\{R\}^\{\\mathbf\{1\}\}\_\{T\}\\bigr\]\\;=\\;\\Omega\\left\(\\frac\{k\\tau\}\{\\log\(T/\\tau\)\}\+\\frac\{T\}\{\\sqrt\{k\}\}\\right\)\.\([Proposition20](https://arxiv.org/html/2609.30556#Thmtheorem20)\)

## 3Meta\-learning framework

We now construct a meta\-learner on top of a number of restarted base experts\. First, we invoke a geometric cover fact that controls how intervals decompose across dyadic scales\. Second, we model each scaleH∈ℋH\\in\\mathcal\{H\}as an expert that restarts everyHHrounds\. Third, we attach to each expert a surrogate loss that combines its expected loss with its switching cost, aggregate the experts into a mixture𝒫t\\mathcal\{P\}\_\{t\}, and sample via lazy coupling of the mixtures, reducing the master to online linear optimization on the simplex with anℓ1\\ell\_\{1\}switching penalty\. Finally, we solve this reduced problem with the strongly adaptive algorithm of\[[10](https://arxiv.org/html/2609.30556#bib.bib19)\]\.

Dyadic schedule and a geometric cover\.Forj=0,1,…,⌊log2⁡T⌋j=0,1,\\dots,\\lfloor\\log\_\{2\}T\\rfloor, define the family of level\-jjdyadic intervals𝒢j≐\{\[\(i−1\)2j\+1,i2j\]:i∈ℕ,i2j≤T\}\\mathcal\{G\}\_\{j\}\\doteq\\bigl\\\{\[\(i\-1\)2^\{j\}\+1,\\,i2^\{j\}\]:i\\in\\mathbb\{N\},\\ i2^\{j\}\\leq T\\bigr\\\}, and collect

𝒢≐⋃j=0⌊log2⁡T⌋𝒢j,ℋ≐\{2j:0≤j≤⌊log2⁡T⌋\},K≐\|ℋ\|=⌊log2⁡T⌋\+1\.\\mathcal\{G\}\\doteq\\bigcup\_\{j=0\}^\{\\lfloor\\log\_\{2\}T\\rfloor\}\\mathcal\{G\}\_\{j\},\\qquad\\mathcal\{H\}\\doteq\\\{2^\{j\}:0\\leq j\\leq\\lfloor\\log\_\{2\}T\\rfloor\\\},\\qquad K\\doteq\|\\mathcal\{H\}\|=\\lfloor\\log\_\{2\}T\\rfloor\+1\.Thus𝒢\\mathcal\{G\}is the set of all dyadic intervals contained in\[T\]\[T\], andℋ\\mathcal\{H\}is the set of dyadic*lengths*\. The following standard combinatorial fact shows that every interval in\[T\]\[T\]admits a short dyadic cover whose lengths sum to a term of the orderL\\sqrt\{L\}\.

###### Lemma 9\(Dyadic geometric cover\)\.

For every intervalI=\[s,e\]⊆\[T\]I=\[s,e\]\\subseteq\[T\]of lengthL=e−s\+1L=e\-s\+1, there exist consecutive dyadic intervalsJ1,…,Jm∈𝒢J\_\{1\},\\dots,J\_\{m\}\\in\\mathcal\{G\}partitioningIIsuch that

m≤2​⌈log2⁡L⌉\+2and∑r=1m\|Jr\|≤Cgc​L,Cgc≐2\+2\.m\\leq 2\\lceil\\log\_\{2\}L\\rceil\+2\\qquad\\text\{and\}\\qquad\\sum\_\{r=1\}^\{m\}\\sqrt\{\|J\_\{r\}\|\}\\leq C\_\{\\mathrm\{gc\}\}\\sqrt\{L\},\\qquad C\_\{\\mathrm\{gc\}\}\\doteq 2\+\\sqrt\{2\}\.\(6\)

Restarted FPRLL base at each dyadic scale\.For each dyadic scaleH∈ℋH\\in\\mathcal\{H\}, we define a base expertℰH\\mathcal\{E\}\_\{H\}that runs a fresh FPRLL\(H\)\(H\)instance on every consecutive block of lengthHH, restarting at the beginning of each new block \([Corollary6](https://arxiv.org/html/2609.30556#Thmtheorem6)\)\. Let𝒬t\(H\)\\mathcal\{Q\}\_\{t\}^\{\(H\)\}denote the marginal law ofℰH\\mathcal\{E\}\_\{H\}’s action at roundtt\. We attach to each expert its instantaneous expected loss, TV movement, and surrogate loss:

ℓt\(H\)≐𝔼𝒙∼𝒬t\(H\)​\[ft​\(𝒙\)\],ct\(H\)≐‖𝒬t\(H\)−𝒬t−1\(H\)‖TV,gt\(H\)≐ℓt\(H\)\+λ​ct\(H\),\\ell\_\{t\}^\{\(H\)\}\\doteq\\mathbb\{E\}\_\{\\bm\{x\}\\sim\\mathcal\{Q\}\_\{t\}^\{\(H\)\}\}\[f\_\{t\}\(\\bm\{x\}\)\],\\qquad c\_\{t\}^\{\(H\)\}\\doteq\\\|\\mathcal\{Q\}\_\{t\}^\{\(H\)\}\-\\mathcal\{Q\}\_\{t\-1\}^\{\(H\)\}\\\|\_\{\\mathrm\{TV\}\},\\qquad g\_\{t\}^\{\(H\)\}\\doteq\\ell\_\{t\}^\{\(H\)\}\+\\lambda\\,c\_\{t\}^\{\(H\)\},\(7\)with the conventionc1\(H\)≐0c\_\{1\}^\{\(H\)\}\\doteq 0\. We state the main analysis using the exact quantitiesℓt\(H\)\\ell\_\{t\}^\{\(H\)\}andct\(H\)c\_\{t\}^\{\(H\)\}for clarity\. In practice, these quantities need not be available in closed form; a practical implementation can therefore feed the meta\-learner a sampled surrogate whose conditional mean is an easily computable upper bound ongt\(H\)g\_\{t\}^\{\(H\)\}\. Details are deferred to[AppendixF](https://arxiv.org/html/2609.30556#A6)\.

The surrogategt\(H\)g\_\{t\}^\{\(H\)\}is the natural expert loss for our problem: it already prices in the switching cost that the expert would incur if the master followed it exclusively\. Indeed, if actions were sampled directly from𝒬t\(H\)\\mathcal\{Q\}\_\{t\}^\{\(H\)\}under the lazy coupling of[Lemma16](https://arxiv.org/html/2609.30556#Thmtheorem16), thenPr⁡\(𝒙t≠𝒙t−1\)=ct\(H\)\\Pr\(\\bm\{x\}\_\{t\}\\neq\\bm\{x\}\_\{t\-1\}\)=c\_\{t\}^\{\(H\)\}, and therefore for every comparator\{𝒖t\}t=1T∈𝒳T\\\{\\bm\{u\}\_\{t\}\\\}\_\{t=1\}^\{T\}\\in\\mathcal\{X\}^\{T\},

𝔼\[∑t=1Tft\(𝒙t\)\+λ∑t=2T𝟏\{𝒙t≠𝒙t−1\}\]−∑t=1Tft\(𝒖t\)=∑t=1T\(gt\(H\)−ft\(𝒖t\)\)=ℛT𝟏,H\.\\mathbb\{E\}\\left\[\\sum\_\{t=1\}^\{T\}f\_\{t\}\(\\bm\{x\}\_\{t\}\)\+\\lambda\\sum\_\{t=2\}^\{T\}\\mathbf\{1\}\\\{\\bm\{x\}\_\{t\}\\neq\\bm\{x\}\_\{t\-1\}\\\}\\right\]\-\\sum\_\{t=1\}^\{T\}f\_\{t\}\(\\bm\{u\}\_\{t\}\)=\\sum\_\{t=1\}^\{T\}\\bigl\(g\_\{t\}^\{\(H\)\}\-f\_\{t\}\(\\bm\{u\}\_\{t\}\)\\bigr\)=\\mathcal\{R\}^\{\\mathbf\{1\},\{\{H\}\}\}\_\{T\}\.\(8\)Hence a meta\-learner that competes with the best cumulative surrogate automatically inherits both the prediction*and*the switching guarantees of the corresponding expert\.

Density\-mixture master and the reduction\.At roundtt, the meta\-learner plays a weight vector𝒗t∈ΔK≐\{𝒗∈ℝ\+ℋ:∑H∈ℋvH=1\},\\bm\{v\}\_\{t\}\\in\\Delta\_\{K\}\\doteq\\Bigl\\\{\\bm\{v\}\\in\\mathbb\{R\}\_\{\+\}^\{\\mathcal\{H\}\}:\\textstyle\\sum\_\{H\\in\\mathcal\{H\}\}v\_\{H\}=1\\Bigr\\\},and forms the mixture marginal as in[Eq\.2](https://arxiv.org/html/2609.30556#S1.E2)The played action𝒙t\\bm\{x\}\_\{t\}is then drawn from𝒫t\\mathcal\{P\}\_\{t\}via the lazy coupling with𝒫t−1\\mathcal\{P\}\_\{t\-1\}, which guarantees𝒙t∼𝒫t\\bm\{x\}\_\{t\}\\sim\\mathcal\{P\}\_\{t\}andPr⁡\(𝒙t≠𝒙t−1\)=‖𝒫t−𝒫t−1‖TV\\Pr\(\\bm\{x\}\_\{t\}\\neq\\bm\{x\}\_\{t\-1\}\)=\\\|\\mathcal\{P\}\_\{t\}\-\\mathcal\{P\}\_\{t\-1\}\\\|\_\{\\mathrm\{TV\}\}\. The full procedure is summarized in[Algorithm2](https://arxiv.org/html/2609.30556#alg2)below\.

Algorithm 2Density\-mixture master \(instantiation of the reduction\)1:base experts

\{ℰH\}H∈ℋ\\\{\\mathcal\{E\}\_\{H\}\\\}\_\{H\\in\\mathcal\{H\}\}; meta\-learner

ℳ\\mathcal\{M\}satisfying[Lemma26](https://arxiv.org/html/2609.30556#Thmtheorem26)with

N=KN=Kexperts and switching cost

D=λ/MD=\\lambda/M
2:actions

𝒙1,…,𝒙T\\bm\{x\}\_\{1\},\\dots,\\bm\{x\}\_\{T\}
3:Sample

𝒙1∼𝒫1\\bm\{x\}\_\{1\}\\sim\\mathcal\{P\}\_\{1\}
4:for

t=1,2,…,Tt=1,2,\\dots,Tdo

5:Play

𝒙t\\bm\{x\}\_\{t\}, observe

ftf\_\{t\}
6:For each

H∈ℋH\\in\\mathcal\{H\}: update

ℰH\\mathcal\{E\}\_\{H\}to obtain

𝒬t\+1\(H\)\\mathcal\{Q\}\_\{t\+1\}^\{\(H\)\}⊳\\trianglerightrestarted FPRLL\(H\)\(H\)

7:Form surrogate losses

gt\(H\)=𝔼𝒬t\(H\)​\[ft\]\+λ​‖𝒬t\(H\)−𝒬t−1\(H\)‖TVg\_\{t\}^\{\(H\)\}=\\mathbb\{E\}\_\{\\mathcal\{Q\}\_\{t\}^\{\(H\)\}\}\[f\_\{t\}\]\+\\lambda\\,\\\|\\mathcal\{Q\}\_\{t\}^\{\(H\)\}\-\\mathcal\{Q\}\_\{t\-1\}^\{\(H\)\}\\\|\_\{\\mathrm\{TV\}\}
8:Feed

ℓt≐𝒈t/M∈\[0,1\]K\\bm\{\\ell\}\_\{t\}\\doteq\\bm\{g\}\_\{t\}/M\\in\[0,1\]^\{K\}to

ℳ\\mathcal\{M\}; receive

𝒗t\+1∈ΔK\\bm\{v\}\_\{t\+1\}\\in\\Delta\_\{K\}⊳\\triangleright[Algorithm6](https://arxiv.org/html/2609.30556#alg6)

9:Form mixture

𝒫t\+1←∑H∈ℋvt\+1,H​𝒬t\+1\(H\)\\mathcal\{P\}\_\{t\+1\}\\leftarrow\\sum\_\{H\\in\\mathcal\{H\}\}v\_\{t\+1,H\}\\,\\mathcal\{Q\}\_\{t\+1\}^\{\(H\)\}
10:

𝒙t\+1←LazySample​\(𝒙t,𝒫t,𝒫t\+1\)\\bm\{x\}\_\{t\+1\}\\leftarrow\\textsc\{LazySample\}\(\\bm\{x\}\_\{t\},\\mathcal\{P\}\_\{t\},\\mathcal\{P\}\_\{t\+1\}\)⊳\\triangleright[Algorithm3](https://arxiv.org/html/2609.30556#alg3)

11:endfor

[Algorithm2](https://arxiv.org/html/2609.30556#alg2)is also efficient\. The meta\-learner of[Daniely and Mansour \[10\]](https://arxiv.org/html/2609.30556#bib.bib19)has per\-round complexity𝒪⁡\(K​log⁡T\)\\mathcal\{O\}\(K\\log T\)forKKexperts, and in our constructionK=\|ℋ\|=𝒪⁡\(log⁡T\)K=\|\\mathcal\{H\}\|=\\mathcal\{O\}\(\\log T\)\. Thus the meta\-level overhead is𝒪⁡\(log2⁡T\)\\mathcal\{O\}\(\\log^\{2\}T\)per round\. The remaining cost is that of updating the𝒪⁡\(log⁡T\)\\mathcal\{O\}\(\\log T\)base learners, each a copy of FPRLL\. Although[Algorithm2](https://arxiv.org/html/2609.30556#alg2)writes the exact surrogate losses for ease of presentation, in implementation we feed the meta\-learner the sampled surrogate losses described in[AppendixF](https://arxiv.org/html/2609.30556#A6)\. Thus the per\-round cost is the cost of𝒪⁡\(log⁡T\)\\mathcal\{O\}\(\\log T\)FPRLL updates, plus an additional𝒪⁡\(log2⁡T\)\\mathcal\{O\}\(\\log^\{2\}T\)meta\-level overhead and the cost of computing the implementable surrogate losses\.

The next lemma is the structural backbone of the analysis: it decomposes the switching probability of the master into an*expert\-movement*term \(the average TV movement of the dyadic coordinates\) and a*weight\-movement*term \(theℓ1\\ell\_\{1\}movement of the meta weights\)\.

###### Lemma 10\(One\-step master reduction\)\.

Let𝐠t≐\(gt\(H\)\)H∈ℋ\\bm\{g\}\_\{t\}\\doteq\(g\_\{t\}^\{\(H\)\}\)\_\{H\\in\\mathcal\{H\}\}\. For everyt≥2t\\geq 2,

‖𝒫t−𝒫t−1‖TV≤∑H∈ℋvt,H​ct\(H\)\+12​‖𝒗t−𝒗t−1‖1,\\\|\{\\mathcal\{P\}\}\_\{t\}\-\{\\mathcal\{P\}\}\_\{t\-1\}\\\|\_\{\\mathrm\{TV\}\}\\;\\leq\\;\\sum\_\{H\\in\\mathcal\{H\}\}v\_\{t,H\}\\,c\_\{t\}^\{\(H\)\}\+\\tfrac\{1\}\{2\}\\\|\\bm\{v\}\_\{t\}\-\\bm\{v\}\_\{t\-1\}\\\|\_\{1\},\(9\)and consequently𝔼⁡\[ft​\(𝒙t\)\]\+λ​Pr⁡\(𝒙t≠𝒙t−1\)≤⟨𝒗t,𝒈t⟩\+λ2​‖𝒗t−𝒗t−1‖1\.\\displaystyle\\text\{and consequently\}\\qquad\\mathbb\{E\}\[f\_\{t\}\(\\bm\{x\}\_\{t\}\)\]\+\\lambda\\Pr\(\\bm\{x\}\_\{t\}\\neq\\bm\{x\}\_\{t\-1\}\)\\;\\leq\\;\\langle\\bm\{v\}\_\{t\},\\bm\{g\}\_\{t\}\\rangle\+\\tfrac\{\\lambda\}\{2\}\\\|\\bm\{v\}\_\{t\}\-\\bm\{v\}\_\{t\-1\}\\\|\_\{1\}\.\(10\)

The interpretation of[Eq\.10](https://arxiv.org/html/2609.30556#S3.E10)is immediate: the meta\-learner sees expert losses𝒈t\\bm\{g\}\_\{t\}that already price in each expert’s own TV movement, and pays only for its own weight movement inℓ1\\ell\_\{1\}\. We have therefore reduced the master problem to an*experts\-with\-switching\-costs*problem over theK=𝒪⁡\(log⁡T\)K=\\mathcal\{O\}\(\\log T\)dyadic scales, with switching\-cost parameterλ/2\\lambda/2\.

Strongly adaptive guarantee for the meta\-learner\.To realize the reduction, we feed the surrogate losses\{𝒈t\}\\\{\\bm\{g\}\_\{t\}\\\}into the strongly adaptive algorithm of\[[10](https://arxiv.org/html/2609.30556#bib.bib19)\], which competes with the best expert on*every*interval while controlling switches among experts\. Its guarantees require a bounded surrogate range, which is ensured by[Assumption4](https://arxiv.org/html/2609.30556#Thmtheorem4)and[Assumption3](https://arxiv.org/html/2609.30556#Thmtheorem3)\. Hence,gt\(H\)≤Mf\+λ≐Mg\_\{t\}^\{\(H\)\}\\leq M\_\{f\}\+\\lambda\\doteq M\.

###### Lemma 11\(Meta\-regret\)\.

There exists an online algorithm producing weights𝐯t∈ΔK\\bm\{v\}\_\{t\}\\\!\\in\\\!\\Delta\_\{K\}such that for every interval\[s,e\]⊆\[T\]\[s,e\]\\subseteq\[T\]of lengthL=e−s\+1L\\\!=\\\!e\\\!\-s\\\!\+1, there is a universal constantCdm\>0C\_\{\\mathrm\{dm\}\}\>0for which:

∑t=se⟨𝒗t,𝒈t⟩\+λ2​∑t=s\+1e‖𝒗t−𝒗t−1‖1≤min⁡∑t=seH∈ℋ⁡gt\(H\)\+Cdm​M⁡\(M\+λ\)​L​log⁡\(K​T\),\\sum\_\{t=s\}^\{e\}\\langle\\bm\{v\}\_\{t\},\\bm\{g\}\_\{t\}\\rangle\+\\tfrac\{\\lambda\}\{2\}\\sum\_\{t=s\+1\}^\{e\}\\\|\\bm\{v\}\_\{t\}\-\\bm\{v\}\_\{t\-1\}\\\|\_\{1\}\\;\\leq\\;\\min\_\{H\\in\\mathcal\{H\}\}\\sum\_\{t=s\}^\{e\}g\_\{t\}^\{\(H\)\}\+C\_\{\\mathrm\{dm\}\}\\sqrt\{M\(M\+\\lambda\)\\,L\\log\(KT\)\},\(11\)

## 4Regret guarantees

We now combine the base\-learner analysis of[Section2](https://arxiv.org/html/2609.30556#S2)with the meta\-learner of[Section3](https://arxiv.org/html/2609.30556#S3)to derive our main regret bounds\. The argument exploits the meta\-learner’s strongly adaptive property in two distinct ways\. First, pairing it with the*static*\-regret guarantee of the base learner on each restart block yields a strongly adaptive regret \(SAR\) bound, which in turn implies a dynamic\-regret bound against piecewise\-constant comparators\. Second, pairing it with the*dynamic*\-regret guarantee of the base learner at the best dyadic restart scale yields a path\-length\-based bound against arbitrary comparators\.

### 4\.1Piecewise\-constant comparators via strongly adaptive regret

The interval regret with indicator switching penalty onI=\[s,e\]⊆\[T\]I=\[s,e\]\\subseteq\[T\]is

SARI\(𝒖\)≐𝔼\[∑t=seft\(𝒙t\)\+λ∑t=s\+1e𝟏\{𝒙t≠𝒙t−1\}\]−∑t=seft\(𝒖\)\.\\displaystyle\\mathrm\{SAR\}\_\{I\}\(\\bm\{u\}\)\\doteq\\mathbb\{E\}\\left\[\\sum\_\{t=s\}^\{e\}f\_\{t\}\(\\bm\{x\}\_\{t\}\)\+\\lambda\\sum\_\{t=s\+1\}^\{e\}\\mathbf\{1\}\\\{\\bm\{x\}\_\{t\}\\neq\\bm\{x\}\_\{t\-1\}\\\}\\right\]\-\\sum\_\{t=s\}^\{e\}f\_\{t\}\(\\bm\{u\}\)\.\(12\)
[Algorithm2](https://arxiv.org/html/2609.30556#alg2)attainsSARI​\(𝒖\)=𝒪~​\(L\)\\mathrm\{SAR\}\_\{I\}\(\\bm\{u\}\)=\\tilde\{\\mathcal\{O\}\}\(\\sqrt\{L\}\)*simultaneously*on all intervals of lengthLL\.

###### Theorem 12\(Strongly adaptive regret\)\.

For every intervalI=\[s,e\]⊆\[T\]I=\[s,e\]\\subseteq\[T\]of lengthL=e−s\+1L=e\-s\+1,

SARI​\(𝒖\)≤Cbase​Cgc​L\+Cdm​Cgc​M⁡\(M\+λ\)​L​log⁡\(K​T\)\+λ⁡\(2​⌈log2⁡L⌉\+1\)=𝒪~​\(L\)\.\\mathrm\{SAR\}\_\{I\}\(\\bm\{u\}\)\\leq C\_\{\\mathrm\{base\}\}C\_\{\\mathrm\{gc\}\}\\sqrt\{L\}\+C\_\{\\mathrm\{dm\}\}\\,C\_\{\\mathrm\{gc\}\}\\sqrt\{M\(M\+\\lambda\)L\\log\(KT\)\}\+\\lambda\\bigl\(2\\lceil\\log\_\{2\}L\\rceil\+1\\bigr\)=\\tilde\{\\mathcal\{O\}\}\(\\sqrt\{L\}\)\.\(13\)

###### Proof sketch\.

The bound combines three ingredients already established:\(i\)*Dyadic cover*:[Lemma9](https://arxiv.org/html/2609.30556#Thmtheorem9)partitionsIIintom=𝒪⁡\(log⁡L\)m=\\mathcal\{O\}\(\\log L\)consecutive dyadic blocksJ1,…,Jm∈𝒢J\_\{1\},\\dots,J\_\{m\}\\in\\mathcal\{G\}with∑r=1m\|Jr\|≤Cgc​L\\sum\_\{r=1\}^\{m\}\\sqrt\{\|J\_\{r\}\|\}\\leq C\_\{\\mathrm\{gc\}\}\\sqrt\{L\}\.\(ii\)*Meta\-level interval regret*: applied blockwise,[Lemma11](https://arxiv.org/html/2609.30556#Thmtheorem11)ensures that on eachJrJ\_\{r\}the meta\-learner competes with the unique dyadic expert whose restart period equals\|Jr\|\|J\_\{r\}\|, at an𝒪~​\(\|Jr\|\)\\tilde\{\\mathcal\{O\}\}\(\\sqrt\{\|J\_\{r\}\|\}\)cost\.\(iii\)*Base\-level static regret*: on its matched restart block, that expert is by definition a fresh run of FPRLL on a horizon of length\|Jr\|\|J\_\{r\}\|, which by[Corollary6](https://arxiv.org/html/2609.30556#Thmtheorem6)has static regret at mostCbase​\|Jr\|C\_\{\\mathrm\{base\}\}\\sqrt\{\|J\_\{r\}\|\}\.

The one\-step bound of[Lemma10](https://arxiv.org/html/2609.30556#Thmtheorem10)lifts the meta inner\-product bound to the master cost, and boundary movement of𝒗t\\bm\{v\}\_\{t\}across blocks is controlled by the simplex bound‖𝒗t−𝒗t−1‖1≤2\\\|\\bm\{v\}\_\{t\}\-\\bm\{v\}\_\{t\-1\}\\\|\_\{1\}\\leq 2\. Summing \(i\)–\(iii\) yields[Eq\.13](https://arxiv.org/html/2609.30556#S4.E13); the full argument is given in[SectionE\.4](https://arxiv.org/html/2609.30556#A5.SS4)\. ∎

A SAR\-to\-dynamic\-regret reduction based on segmenting the comparator at its switch points \(paying a non\-dominantλ​ST\\lambda S\_\{T\}term\) yields the piecewise\-constant branch of our guarantee \(see[SectionE\.5](https://arxiv.org/html/2609.30556#A5.SS5)\):

###### Corollary 13\(Dynamic regret,STS\_\{T\}branch\)\.

For every comparator sequence,[Algorithm2](https://arxiv.org/html/2609.30556#alg2)attains

𝔼⁡\[ℛT𝟏​\(\{𝒖t\}t=1T\)\]≤𝒪~​\(\(ST\+1\)​T\)\+λ​ST\.\\mathbb\{E\}\\bigl\[\\mathcal\{R\}^\{\\mathbf\{1\}\}\_\{T\}\(\\\{\\bm\{u\}\_\{t\}\\\}\_\{t=1\}^\{T\}\)\\bigr\]\\;\\leq\\;\\tilde\{\\mathcal\{O\}\}\\left\(\\sqrt\{\(S\_\{T\}\+1\)\\,T\}\\right\)\+\\lambda\\,S\_\{T\}\.

### 4\.2Path\-varying comparators

For comparators with bounded path length, segmenting at switch points is no longer informative since𝒖t\\bm\{u\}\_\{t\}may drift by arbitrarily small amounts at every round\. Instead, we invoke the base learner’s dynamic\-regret characterization \([Theorem7](https://arxiv.org/html/2609.30556#Thmtheorem7)\), which identifies the optimal dyadic restart scalek†∈ℋk^\{\\dagger\}\\in\\mathcal\{H\}matching the comparator’s drift\. For the meta\-learner notation, this is the expert with scaleH=k†H=k^\{\\dagger\}\.

###### Theorem 14\(Dynamic regret,PTP\_\{T\}branch\)\.

For every comparator sequence,[Algorithm2](https://arxiv.org/html/2609.30556#alg2)attains

𝔼⁡\[ℛT𝟏​\(\{𝒖t\}t=1T\)\]≤minH∈ℋ⁡\(∑t=1Tgt\(H\)−∑t=1Tft​\(𝒖t\)\)\+Cdm​M⁡\(M\+λ\)​T​log⁡\(K​T\)\.\\mathbb\{E\}\\bigl\[\\mathcal\{R\}^\{\\mathbf\{1\}\}\_\{T\}\(\\\{\\bm\{u\}\_\{t\}\\\}\_\{t=1\}^\{T\}\)\\bigr\]\\;\\leq\\;\\min\_\{H\\in\\mathcal\{H\}\}\\left\(\\sum\_\{t=1\}^\{T\}g\_\{t\}^\{\(H\)\}\-\\sum\_\{t=1\}^\{T\}f\_\{t\}\(\\bm\{u\}\_\{t\}\)\\right\)\\;\+\\;C\_\{\\mathrm\{dm\}\}\\sqrt\{M\(M\+\\lambda\)\\,T\\log\(KT\)\}\.\(14\)In particular, forH=k†H=k^\{\\dagger\}from[Theorem7](https://arxiv.org/html/2609.30556#Thmtheorem7), we obtain

𝔼⁡\[ℛT𝟏​\(\{𝒖t\}t=1T\)\]=𝒪~​\(max⁡\{T2/3​PT1/3,T\}\)\.\\displaystyle\\mathbb\{E\}\\bigl\[\\mathcal\{R\}^\{\\mathbf\{1\}\}\_\{T\}\(\\\{\\bm\{u\}\_\{t\}\\\}\_\{t=1\}^\{T\}\)\\bigr\]\\;=\\;\\tilde\{\\mathcal\{O\}\}\\left\(\\max\\left\\\{T^\{2/3\}P\_\{T\}^\{1/3\},\\,\\sqrt\{T\}\\right\\\}\\right\)\.\(15\)

###### Proof sketch\.

The one\-step bound \([Lemma10](https://arxiv.org/html/2609.30556#Thmtheorem10)\), summed overt=1,…,Tt=1,\\dots,T, reduces the master cost to the meta inner\-product loss plus a TV movement term\. Applying[Lemma11](https://arxiv.org/html/2609.30556#Thmtheorem11)on the full interval\[1,T\]\[1,T\]yields[Eq\.14](https://arxiv.org/html/2609.30556#S4.E14)\. SubstitutingH=k†H=k^\{\\dagger\}and invoking the base\-level dynamic regret bound of[Theorem7](https://arxiv.org/html/2609.30556#Thmtheorem7)gives[Eq\.15](https://arxiv.org/html/2609.30556#S4.E15)\. See[SectionE\.6](https://arxiv.org/html/2609.30556#A5.SS6)for details\. ∎

## 5Related work

Our work connects two largely separate lines of research: algorithms with few learner decision*changes*, and algorithms with guarantees against*moving*comparators\. Existing results typically provide one of these guarantees, but not both, for general OCO\.

Lazy OCO\.A line of work studies online learners constrained to switcho⁡\(T\)o\(T\)times against a*static*comparator\.\[[5](https://arxiv.org/html/2609.30556#bib.bib16)\]obtainedd​T\+d​T/S\\sqrt\{dT\}\+dT/Sregret withSSexpected switches\.\[[13](https://arxiv.org/html/2609.30556#bib.bib23)\]studied this setting under the name “consistent” online optimization and used Poisson Process schedules, but obtained a weaker tradeoff in terms ofTT\.\[[18](https://arxiv.org/html/2609.30556#bib.bib12)\]and\[[3](https://arxiv.org/html/2609.30556#bib.bib14)\]improved the\[[5](https://arxiv.org/html/2609.30556#bib.bib16)\]guarantee toT\+d​T/S\\sqrt\{T\}\+dT/S, and\[[2](https://arxiv.org/html/2609.30556#bib.bib20)\]sharpened this toT\+d​T/S\\sqrt\{T\}\+\\sqrt\{d\}T/Swhile removing smoothness assumptions via log\-concave sampling\.\[[20](https://arxiv.org/html/2609.30556#bib.bib22)\]obtained the sameT/ST/S\-type dependence forSSswitches deterministically, but under a continuous norm\-based switching constraint\. These works typically present regret and switching count separately; we report their sum, which is equivalent via standard reductions\[[18](https://arxiv.org/html/2609.30556#bib.bib12), Lem\. 17\]and directly captures the optimal joint tradeoff\. For the*strongly*convex case,\[[18](https://arxiv.org/html/2609.30556#bib.bib12)\]obtains better bounds of order𝒪~​\(T/S2\)\\widetilde\{\\mathcal\{O\}\}\(T/S^\{2\}\)\. Against*adaptive*adversaries, the problem is provably harder:\[[7](https://arxiv.org/html/2609.30556#bib.bib17)\]established aΘ⁡\(T/S\)\\Theta\(T/\\sqrt\{S\}\)minimax rate for an expectedSSswitches\. All of these results target a static comparator across the time horizon\.

Moving comparators and switching costs\.A second line studies dynamic regret under*norm\-based*movement penalties‖𝒙t−𝒙t−1‖\\\|\\bm\{x\}\_\{t\}\-\\bm\{x\}\_\{t\-1\}\\\|or other Lipschitz switching costs\[[8](https://arxiv.org/html/2609.30556#bib.bib9),[27](https://arxiv.org/html/2609.30556#bib.bib7),[22](https://arxiv.org/html/2609.30556#bib.bib6),[16](https://arxiv.org/html/2609.30556#bib.bib18)\]\.\[[22](https://arxiv.org/html/2609.30556#bib.bib6)\]achieved the optimal𝒪⁡\(T⁡\(1\+PT\)\)\\mathcal\{O\}\(\\sqrt\{T\(1\+P\_\{T\}\)\}\)dynamic regret by incorporating switching cost into a meta\-aggregation loss\. Our approach is similar in spirit, but aggregates over total\-variation distance and uses different meta\- and base\-learners\. Most recently,\[[16](https://arxiv.org/html/2609.30556#bib.bib18)\]showed that FTRL itself can attain dynamic\-regret guarantees with additional laziness properties such as staleness\. Relatedly,\[[26](https://arxiv.org/html/2609.30556#bib.bib11)\]studies unbounded comparators, and\[[11](https://arxiv.org/html/2609.30556#bib.bib24)\]extends this setting to moving unbounded comparators with bounds adaptive to individual switching\-cost parametersλt\\lambda\_\{t\}\. However, these costs remain norm\-based, and the resulting algorithms may still change decisions every round\. Strongly adaptive methods provide another route to dynamic or tracking regret:\[[9](https://arxiv.org/html/2609.30556#bib.bib21)\]introduced geometric\-covering reductions from static regret to strongly adaptive regret, and\[[25](https://arxiv.org/html/2609.30556#bib.bib4)\]showed that strongly adaptive regret implies dynamic\-regret bounds in OCO, typically with an additional function\-variation term\.\[[23](https://arxiv.org/html/2609.30556#bib.bib15)\]extends this perspective to OCO with switching costs, but again under norm\-based costs\.

Beyond the two lines above, our framework draws on adjacent threads\. Differentially private online learning naturally incentivizes few decision changes, since each update consumes privacy budget, and hence algorithms developed in one setting often transfer to the other\[[3](https://arxiv.org/html/2609.30556#bib.bib14)\]\. On the algorithmic side, our master/base design follows the meta\-learning\-over\-restarting\-experts line of Follow\-the\-Leading\-History and the sleeping\-experts perspective\[[1](https://arxiv.org/html/2609.30556#bib.bib26)\]\. Restarting a randomized \(perturbed\) leader to obtain dynamic and strongly adaptive regret was recently considered by\[[21](https://arxiv.org/html/2609.30556#bib.bib27)\], but without switching costs of any kind \(deterministic, indicator, or normed\) and without accompanying lower bounds\.

## References

- \[1\]D\. Adamskiy, W\. M\. Koolen, A\. Chernov, and V\. Vovk\(2012\)A closer look at adaptive regret\.InProc\. of ALT,Cited by:[§5](https://arxiv.org/html/2609.30556#S5.p4.1)\.
- \[2\]N\. Agarwal, S\. Kale, K\. Singh, and A\. G\. Thakurta\(2024\)Improved differentially private and lazy online convex optimization: lower regret without smoothness requirements\.InProc\. of ICML,Cited by:[§5](https://arxiv.org/html/2609.30556#S5.p2.1)\.
- \[3\]N\. Agarwal, S\. Kale, K\. Singh, and A\. Thakurta\(2023\)Differentially private and lazy online convex optimization\.InProc\. of COLT,Cited by:[§1\.1](https://arxiv.org/html/2609.30556#S1.SS1.p3.1),[§1](https://arxiv.org/html/2609.30556#S1.p2.1),[§1](https://arxiv.org/html/2609.30556#S1.p3.1),[§5](https://arxiv.org/html/2609.30556#S5.p2.1),[§5](https://arxiv.org/html/2609.30556#S5.p4.1)\.
- \[4\]J\. Altschuler and K\. Talwar\(2018\)Online learning over a finite action set with limited switching\.InProc\. of COLT,Cited by:[§1](https://arxiv.org/html/2609.30556#S1.p3.1)\.
- \[5\]O\. Anava, E\. Hazan, and S\. Mannor\(2015\)Online learning for adversaries with memory: price of past mistakes\.InProc\. of NeurIPS,Cited by:[§5](https://arxiv.org/html/2609.30556#S5.p2.1)\.
- \[6\]N\. Cesa\-Bianchi, O\. Dekel, and O\. Shamir\(2013\)Online learning with switching costs and other adaptive adversaries\.InProc\. of NeurIPS,Cited by:[§1](https://arxiv.org/html/2609.30556#S1.p2.1)\.
- \[7\]L\. Chen, Q\. Yu, H\. Lawrence, and A\. Karbasi\(2020\)Minimax regret of switching\-constrained online convex optimization: no phase transition\.InProc\. of NeurIPS,Cited by:[§5](https://arxiv.org/html/2609.30556#S5.p2.1)\.
- \[8\]N\. Chen, G\. Goel, and A\. Wierman\(2018\)Smoothed online convex optimization in high dimensions via online balanced descent\.InProc\. of COLT,Cited by:[§5](https://arxiv.org/html/2609.30556#S5.p3.1)\.
- \[9\]A\. Daniely, A\. Gonen, and S\. Shalev\-Shwartz\(2015\)Strongly adaptive online learning\.InProc\. of ICML,Cited by:[§5](https://arxiv.org/html/2609.30556#S5.p3.1),[footnote 2](https://arxiv.org/html/2609.30556#footnote2)\.
- \[10\]A\. Daniely and Y\. Mansour\(2019\)Competitive ratio vs regret minimization: achieving the best of both worlds\.InProc\. of ALT,Cited by:[item 4](https://arxiv.org/html/2609.30556#A5.I2.i4.p1.1),[§E\.2](https://arxiv.org/html/2609.30556#A5.SS2.p1.1),[§E\.3](https://arxiv.org/html/2609.30556#A5.SS3),[§E\.3](https://arxiv.org/html/2609.30556#A5.SS3.SSS0.Px2.p2.1),[§E\.3](https://arxiv.org/html/2609.30556#A5.SS3.p1.1),[§E\.3](https://arxiv.org/html/2609.30556#A5.SS3.p3.1),[§1\.1](https://arxiv.org/html/2609.30556#S1.SS1.p4.1),[§1\.2](https://arxiv.org/html/2609.30556#S1.SS2.p4.1),[§1](https://arxiv.org/html/2609.30556#S1.p3.1),[§3](https://arxiv.org/html/2609.30556#S3.p1.1),[§3](https://arxiv.org/html/2609.30556#S3.p6.1),[§3](https://arxiv.org/html/2609.30556#S3.p9.1),[Lemma 26](https://arxiv.org/html/2609.30556#Thmtheorem26),[footnote 1](https://arxiv.org/html/2609.30556#footnote1)\.
- \[11\]E\. Esposito, A\. Jacobsen, H\. Qiu, and M\. Zhang\(2026\)Parameter\-free dynamic regret: time\-varying movement costs, delayed feedback, and memory\.InProc\. of ICML,Cited by:[§5](https://arxiv.org/html/2609.30556#S5.p3.1)\.
- \[12\]A\. Jacobsen and A\. Cutkosky\(2022\)Parameter\-free mirror descent\.InProc\. of COLT,Cited by:[§1](https://arxiv.org/html/2609.30556#S1.p4.1)\.
- \[13\]M\. R\. K\. Jaghargh, A\. Krause, S\. Lattanzi, and S\. Vassilvtiskii\(2019\)Consistent online optimization: convex and submodular\.InProc\. of AISTATS,Cited by:[§1](https://arxiv.org/html/2609.30556#S1.p2.1),[§5](https://arxiv.org/html/2609.30556#S5.p2.1)\.
- \[14\]H\. B\. McMahan\(2017\)A Survey of Algorithms and Analysis for Adaptive Online Learning\.J\. Mach\. Learn\. Res\.18\(1\),pp\. 3117–3166\.Cited by:[§1](https://arxiv.org/html/2609.30556#S1.p3.1)\.
- \[15\]N\. Mhaisen and G\. Iosifidis\(2025\)On the dynamic regret of following the regularized leader: optimism with history pruning\.InProc\. of ICML,Cited by:[1st item](https://arxiv.org/html/2609.30556#A3.I1.i1.p1.1),[§1](https://arxiv.org/html/2609.30556#S1.p4.1)\.
- \[16\]N\. Mhaisen and G\. Iosifidis\(2026\)Partially lazy gradient descent for smoothed online learning\.InProc\. of AISTATS,Cited by:[§1](https://arxiv.org/html/2609.30556#S1.p4.1),[§5](https://arxiv.org/html/2609.30556#S5.p3.1)\.
- \[17\]F\. Orabona\(2022\)A Modern Introduction to Online Learning\.arXiv\.1912\.13213\.Cited by:[Lemma 25](https://arxiv.org/html/2609.30556#Thmtheorem25.p1.1)\.
- \[18\]U\. Sherman and T\. Koren\(2021\)Lazy oco: online convex optimization on a switching budget\.InProc\. of COLT,Cited by:[§A\.2](https://arxiv.org/html/2609.30556#A1.SS2.p1.1),[Appendix C](https://arxiv.org/html/2609.30556#A3.p3.1),[§1\.1](https://arxiv.org/html/2609.30556#S1.SS1.p3.1),[§1](https://arxiv.org/html/2609.30556#S1.p2.1),[§5](https://arxiv.org/html/2609.30556#S5.p2.1)\.
- \[19\]U\. Sherman and T\. Koren\(2023\)Lazy oco: online convex optimization on a switching budget\.arXiv 2102\.03803\.Cited by:[Appendix B](https://arxiv.org/html/2609.30556#A2.SS0.SSS0.Px8.p6.1.1),[§1\.1](https://arxiv.org/html/2609.30556#S1.SS1.p3.1),[§1](https://arxiv.org/html/2609.30556#S1.p3.1),[§2](https://arxiv.org/html/2609.30556#S2.p1.2),[§2](https://arxiv.org/html/2609.30556#S2.p10.1),[footnote 3](https://arxiv.org/html/2609.30556#footnote3)\.
- \[20\]G\. Wang, Y\. Wan, T\. Yang, and L\. Zhang\(2021\)Online convex optimization with continuous switching constraint\.InProc\. of NeurIPS,Cited by:[§5](https://arxiv.org/html/2609.30556#S5.p2.1)\.
- \[21\]Z\. Xu and L\. Zhang\(2024\)Online non\-convex learning in dynamic environments\.InProc\. of NeurIPS,pp\. 51930–51962\.Cited by:[§5](https://arxiv.org/html/2609.30556#S5.p4.1)\.
- \[22\]L\. Zhang, W\. Jiang, S\. Lu, and T\. Yang\(2021\)Revisiting smoothed online learning\.InProc\. of NeurIPS,Cited by:[§5](https://arxiv.org/html/2609.30556#S5.p3.1)\.
- \[23\]L\. Zhang, W\. Jiang, J\. Yi, and T\. Yang\(2022\)Smoothed online convex optimization based on discounted\-normal\-predictor\.InProc\. of NeurIPS,Cited by:[§5](https://arxiv.org/html/2609.30556#S5.p3.1)\.
- \[24\]L\. Zhang, S\. Lu, and Z\. Zhou\(2018\)Adaptive online learning in dynamic environments\.InProc\. of NeurIPS,Cited by:[§1\.1](https://arxiv.org/html/2609.30556#S1.SS1.p5.2)\.
- \[25\]L\. Zhang, T\. Yang, Z\. Zhou,et al\.\(2018\)Dynamic regret of strongly adaptive methods\.InInternational conference on machine learning,pp\. 5882–5891\.Cited by:[§5](https://arxiv.org/html/2609.30556#S5.p3.1)\.
- \[26\]Z\. Zhang, A\. Cutkosky, and Y\. Paschalidis\(2022\)Optimal comparator adaptive online learning with switching cost\.InProc\. of NeurIPS,Cited by:[§5](https://arxiv.org/html/2609.30556#S5.p3.1)\.
- \[27\]Y\. Zhao, Q\. Zhao, X\. Zhang, E\. Zhu, X\. Liu, and J\. Yin\(2020\)Understand dynamic regret with switching cost for online decision making\.ACM Trans\. on Intelligent Systems and Technology11\(3\)\.Cited by:[§5](https://arxiv.org/html/2609.30556#S5.p3.1)\.

## Appendix

This appendix contains the technical details omitted from the main text\. We first derive the change\-of\-variables formula underlying the fresh perturbed minimizer distribution and recall the lazy\-sampling coupling used to preserve the correct marginals while controlling switches\. We then prove the lower bounds, the base\-learner guarantees, the dyadic restart and interval\-covering results, and finally the meta\-learner reductions leading to the strongly adaptive and dynamic\-regret guarantees\.

#### Contents\.

- •[AppendixA](https://arxiv.org/html/2609.30556#A1): change of variables and lazy sampling\.
- •[AppendixB](https://arxiv.org/html/2609.30556#A2): lower bounds for restart\-based FPRLL\.
- •[AppendixC](https://arxiv.org/html/2609.30556#A3): proofs for the base learner\.
- •[AppendixD](https://arxiv.org/html/2609.30556#A4): dyadic interval covering\.
- •[AppendixE](https://arxiv.org/html/2609.30556#A5): proofs for the meta\-learner and reductions\.

## Appendix AChange of variable and lazy sampling

### A\.1Change of variable formula

###### Lemma 15\(Density of the fresh minimizer\)\.

Let

𝒙~t≐arg⁡min𝒙∈𝒳​\{Ft−1​\(𝒙\)\+⟨𝒑t,𝒙⟩\},𝒑t∼Lap⁡\(μ\),\\tilde\{\\bm\{x\}\}\_\{t\}~\\doteq~\\arg\\min\_\{\\bm\{x\}\\in\\mathcal\{X\}\}\\Bigl\\\{F\_\{t\-1\}\(\\bm\{x\}\)\+\\langle\\bm\{p\}\_\{t\},\\bm\{x\}\\rangle\\Bigr\\\},\\qquad\\bm\{p\}\_\{t\}\\sim\\mathrm\{Lap\}\(\\mu\),where

ν⁡\(𝒑\)=1\(2​μ\)d​exp⁡\(−‖𝒑‖1μ\)\.\\nu\(\\bm\{p\}\)=\\frac\{1\}\{\(2\\mu\)^\{d\}\}\\exp\\left\(\-\\frac\{\\\|\\bm\{p\}\\\|\_\{1\}\}\{\\mu\}\\right\)\.Then𝐱~t\\tilde\{\\bm\{x\}\}\_\{t\}has density

𝒬t​\(𝒙\)\\displaystyle\\mathcal\{Q\}\_\{t\}\(\\bm\{x\}\)=ν⁡\(−∇Ft−1​\(𝒙\)\)​\|det\(−∇2Ft−1​\(𝒙\)\)\|,𝒙∈int⁡\(𝒳\)\.\\displaystyle=\\nu\\left\(\-\\nabla F\_\{t\-1\}\(\\bm\{x\}\)\\right\)\\,\\left\|\\det\\left\(\-\\nabla^\{2\}F\_\{t\-1\}\(\\bm\{x\}\)\\right\)\\right\|,\\qquad\\bm\{x\}\\in\\mathrm\{int\}\(\\mathcal\{X\}\)\.\(16\)

###### Proof\.

By optimality of𝒙~t\\tilde\{\\bm\{x\}\}\_\{t\},

∇Ft−1​\(𝒙~t\)\+𝒑t=0,\\nabla F\_\{t\-1\}\(\\tilde\{\\bm\{x\}\}\_\{t\}\)\+\\bm\{p\}\_\{t\}=0,hence

𝒑t=−∇Ft−1​\(𝒙~t\)\.\\bm\{p\}\_\{t\}=\-\\nabla F\_\{t\-1\}\(\\tilde\{\\bm\{x\}\}\_\{t\}\)\.Define

Tt​\(𝒙\)≐−∇Ft−1​\(𝒙\)\.T\_\{t\}\(\\bm\{x\}\)\\doteq\-\\nabla F\_\{t\-1\}\(\\bm\{x\}\)\.
SinceFt−1F\_\{t\-1\}is strongly convex, its conjugateFt−1∗F\_\{t\-1\}^\{\*\}is differentiable and

∇Ft−1∗=\(∇Ft−1\)−1\.\\nabla F\_\{t\-1\}^\{\*\}=\(\\nabla F\_\{t\-1\}\)^\{\-1\}\.Therefore

Tt−1​\(𝒑\)=∇Ft−1∗​\(−𝒑\)\.T\_\{t\}^\{\-1\}\(\\bm\{p\}\)=\\nabla F\_\{t\-1\}^\{\*\}\(\-\\bm\{p\}\)\.So𝒙~t=Tt−1​\(𝒑t\)\\tilde\{\\bm\{x\}\}\_\{t\}=T\_\{t\}^\{\-1\}\(\\bm\{p\}\_\{t\}\)\.

Applying the change\-of\-variables formula to the mapTtT\_\{t\}, the density of𝒙~t\\tilde\{\\bm\{x\}\}\_\{t\}is

𝒬t​\(𝒙\)=ν⁡\(Tt​\(𝒙\)\)​\|detD​Tt​\(𝒙\)\|\.\\mathcal\{Q\}\_\{t\}\(\\bm\{x\}\)=\\nu\(T\_\{t\}\(\\bm\{x\}\)\)\\left\|\\det DT\_\{t\}\(\\bm\{x\}\)\\right\|\.Using

Tt​\(𝒙\)=−∇Ft−1​\(𝒙\),D​Tt​\(𝒙\)=−∇2Ft−1​\(𝒙\),T\_\{t\}\(\\bm\{x\}\)=\-\\nabla F\_\{t\-1\}\(\\bm\{x\}\),\\qquad DT\_\{t\}\(\\bm\{x\}\)=\-\\nabla^\{2\}F\_\{t\-1\}\(\\bm\{x\}\),we obtain

𝒬t​\(𝒙\)=ν⁡\(−∇Ft−1​\(𝒙\)\)​\|det\(−∇2Ft−1​\(𝒙\)\)\|,\\mathcal\{Q\}\_\{t\}\(\\bm\{x\}\)=\\nu\\left\(\-\\nabla F\_\{t\-1\}\(\\bm\{x\}\)\\right\)\\,\\left\|\\det\\left\(\-\\nabla^\{2\}F\_\{t\-1\}\(\\bm\{x\}\)\\right\)\\right\|,as claimed\. ∎

### A\.2Lazy sampling

We recall a standard lazy\-sampling routine for realizing a maximal coupling between two distributions\. We use it only through the marginal\-preservation and switching identities in[Lemma16](https://arxiv.org/html/2609.30556#Thmtheorem16); the results \(and their proof\) are standard and can be found in\[[18](https://arxiv.org/html/2609.30556#bib.bib12)\]\.

Algorithm 3LazySample1:Input:current action

𝒙\\bm\{x\}, current distribution

𝒬\\mathcal\{Q\}, next distribution

𝒫\\mathcal\{P\}
2:Output:next action

𝒚\\bm\{y\}
3:Sample

z∼Unif⁡\[0,𝒬⁡\(𝒙\)\]z\\sim\\mathrm\{Unif\}\[0,\\,\\mathcal\{Q\}\(\\bm\{x\}\)\]
4:if

z<𝒫⁡\(𝒙\)z<\\mathcal\{P\}\(\\bm\{x\}\)then⊳\\trianglerightKeep the same action

5:Set

𝒚=𝒙\\bm\{y\}=\\bm\{x\}
6:else⊳\\trianglerightSample a new action

7:repeat

8:Sample

𝒚∼𝒫\\bm\{y\}\\sim\\mathcal\{P\}
9:Sample

z′∼Unif⁡\[0,𝒫⁡\(𝒚\)\]z^\{\\prime\}\\sim\\mathrm\{Unif\}\[0,\\,\\mathcal\{P\}\(\\bm\{y\}\)\]
10:until

z′\>𝒬⁡\(𝒚\)z^\{\\prime\}\>\\mathcal\{Q\}\(\\bm\{y\}\)
11:endif

12:return

𝒚\\bm\{y\}

###### Lemma 16\(Standard lazy\-sampling identities\)\.

Let𝐗∼𝒬\\bm\{X\}\\sim\\mathcal\{Q\}, and let

𝒀∼LazySample​\(𝑿,𝒬,𝒫\)\.\\bm\{Y\}\\sim\\textsc\{LazySample\}\(\\bm\{X\},\\mathcal\{Q\},\\mathcal\{P\}\)\.Then:

𝒀\\displaystyle\\bm\{Y\}∼𝒫,\\displaystyle\\sim\\mathcal\{P\},\(17\)Pr⁡\(𝒀≠𝑿\)\\displaystyle\\Pr\(\\bm\{Y\}\\neq\\bm\{X\}\)=‖𝒫−𝒬‖TV\.\\displaystyle=\\\|\\mathcal\{P\}\-\\mathcal\{Q\}\\\|\_\{\\mathrm\{TV\}\}\.\(18\)

#### Correspondence with[Algorithm1](https://arxiv.org/html/2609.30556#alg1)\.

[Algorithm1](https://arxiv.org/html/2609.30556#alg1)is preciselyLazySampleinstantiated with the consecutive FPRLL marginals\(𝒬t,𝒬t\+1\)\(\\mathcal\{Q\}\_\{t\},\\mathcal\{Q\}\_\{t\+1\}\)\. In this correspondence, the current state is𝒙t\\bm\{x\}\_\{t\}, the current and next distributions are𝒬t\\mathcal\{Q\}\_\{t\}and𝒬t\+1\\mathcal\{Q\}\_\{t\+1\}, and the output is𝒙t\+1\\bm\{x\}\_\{t\+1\}\. The “keep” test in[Algorithm1](https://arxiv.org/html/2609.30556#alg1)matches the first branch of[Algorithm3](https://arxiv.org/html/2609.30556#alg3)\. If that test fails, the algorithm must draw a fresh sample from𝒬t\+1\\mathcal\{Q\}\_\{t\+1\}; in our setting this is implemented by drawing𝒑∼Lap⁡\(μ\)\\bm\{p\}\\sim\\mathrm\{Lap\}\(\\mu\)and solving the perturbed optimization problem, whose minimizer has law𝒬t\+1\\mathcal\{Q\}\_\{t\+1\}by definition\. Finally,[Lemma15](https://arxiv.org/html/2609.30556#Thmtheorem15)supplies a closed\-form expression for these densities, so the comparisons involving𝒬t​\(⋅\)\\mathcal\{Q\}\_\{t\}\(\\cdot\)and𝒬t\+1​\(⋅\)\\mathcal\{Q\}\_\{t\+1\}\(\\cdot\)required by lazy sampling can be evaluated pointwise\.

## Appendix BLower bounds

First, we need the following tool, which lower bounds FPRLL dynamic regret without restarts:

###### Theorem 17\.

Consider the one\-dimensional problem on𝒳=\[−1,1\]\\mathcal\{X\}=\[\-1,1\]with linear losses

ft​\(x\)=gt​x,gt∈\{−1,\+1\}\.f\_\{t\}\(x\)=g\_\{t\}x,\\qquad g\_\{t\}\\in\\\{\-1,\+1\\\}\.Let the learner predict at each round

xt≐argminx∈\(−1,1\)\{Ft​\(x\)\+⟨G0\+pt,x⟩\}=argminx∈\(−1,1\)\{⟨Gt−1\+pt,x⟩\+rt​\(x\)\+b⁡\(x\)\},\\displaystyle x\_\{t\}\\doteq\\argmin\_\{x\\in\(\-1,1\)\}\\Big\\\{F\_\{t\}\(x\)\+\\langle\{G\_\{0\}\+p\_\{t\}\},\{x\}\\rangle\\Big\\\}=\\argmin\_\{x\\in\(\-1,1\)\}\\Big\\\{\\langle\{G\_\{t\-1\}\+p\_\{t\}\},\{x\}\\rangle\+r\_\{t\}\(x\)\+b\(x\)\\Big\\\},\(19\)whereGt−1=G0\+∑i=1t−1giG\_\{t\-1\}=G\_\{0\}\+\\sum\_\{i=1\}^\{t\-1\}g\_\{i\}, for an arbitraryG0∈ℝG\_\{0\}\\in\\mathbb\{R\},

b⁡\(x\)=−1Mγ​log⁡\(1−x2\)b\(x\)=\-\\frac\{1\}\{M\_\{\\gamma\}\}\\log\(1\-x^\{2\}\)is the logarithmic barrier for𝒳\\mathcal\{X\},rt​\(x\)=σt2​x2r\_\{t\}\(x\)=\\frac\{\\sigma\_\{t\}\}\{2\}x^\{2\}withσt≥0\\sigma\_\{t\}\\geq 0, andptp\_\{t\}are arbitrary symmetric perturbations\.

Then, there exists an oblivious loss sequence and a one\-switch comparator sequence such that

𝔼⁡\[∑t=1T\(ft​\(xt\)−ft​\(ut\)\)\]≥T2\.\\mathbb\{E\}\\left\[\\sum\_\{t=1\}^\{T\}\\bigl\(f\_\{t\}\(x\_\{t\}\)\-f\_\{t\}\(u\_\{t\}\)\\bigr\)\\right\]\\;\\geq\\;\\frac\{T\}\{2\}\.

###### Proof\.

FixT=2​nT=2nand consider the oblivious loss sequence

gt=\{\+1,t≤n,−1,t\>n,ut=−gt\.g\_\{t\}=\\begin\{cases\}\+1,&t\\leq n,\\\\ \-1,&t\>n,\\end\{cases\}\\qquad u\_\{t\}=\-g\_\{t\}\.
Define the cumulative gradients

Gt≐G0\+∑i=1tgi\.G\_\{t\}\\doteq G\_\{0\}\+\\sum\_\{i=1\}^\{t\}g\_\{i\}\.

#### Step 1: Structure of the prediction\.

For each roundtt, define

Ht​\(x\)≐rt′​\(x\)\+b′​\(x\)=σt​x\+2​xMγ​\(1−x2\)=x⁡\(σt\+2Mγ​\(1−x2\)\),x∈\(−1,1\)\.H\_\{t\}\(x\)\\doteq r\_\{t\}^\{\\prime\}\(x\)\+b^\{\\prime\}\(x\)=\\sigma\_\{t\}x\+\\frac\{2x\}\{M\_\{\\gamma\}\(1\-x^\{2\}\)\}=x\\left\(\\sigma\_\{t\}\+\\frac\{2\}\{M\_\{\\gamma\}\(1\-x^\{2\}\)\}\\right\),\\qquad x\\in\(\-1,1\)\.Sinceσt≥0\\sigma\_\{t\}\\geq 0,

Ht′​\(x\)=σt\+2​\(1\+x2\)Mγ​\(1−x2\)2\>0,H\_\{t\}^\{\\prime\}\(x\)=\\sigma\_\{t\}\+\\frac\{2\(1\+x^\{2\}\)\}\{M\_\{\\gamma\}\(1\-x^\{2\}\)^\{2\}\}\>0,soHtH\_\{t\}is strictly increasing\. Moreover,HtH\_\{t\}is odd and satisfies

limx→−1\+Ht​\(x\)=−∞,limx→1−Ht​\(x\)=\+∞\.\\lim\_\{x\\to\-1^\{\+\}\}H\_\{t\}\(x\)=\-\\infty,\\qquad\\lim\_\{x\\to 1^\{\-\}\}H\_\{t\}\(x\)=\+\\infty\.ThusHtH\_\{t\}is a bijection from\(−1,1\)\(\-1,1\)ontoℝ\\mathbb\{R\}, and its inverseHt−1H\_\{t\}^\{\-1\}is odd and strictly increasing\.

By first\-order optimality of the FTRL objective,

Ht​\(xt\)=−\(Gt−1\+pt\),H\_\{t\}\(x\_\{t\}\)=\-\(G\_\{t\-1\}\+p\_\{t\}\),and therefore

xt=−Ht−1​\(Gt−1\+pt\)\.x\_\{t\}=\-\\,H\_\{t\}^\{\-1\}\(G\_\{t\-1\}\+p\_\{t\}\)\.

#### Step 2: Sign of the expectation\.

Define

mt​\(c\)≐𝔼⁡\[Ht−1​\(c\+pt\)\]\.m\_\{t\}\(c\)\\doteq\\mathbb\{E\}\\bigl\[H\_\{t\}^\{\-1\}\(c\+p\_\{t\}\)\\bigr\]\.SinceHt−1H\_\{t\}^\{\-1\}is increasing,mtm\_\{t\}is increasing\. SinceHt−1H\_\{t\}^\{\-1\}is odd andptp\_\{t\}is symmetric,mtm\_\{t\}is odd:

mt​\(−c\)=−mt​\(c\)\.m\_\{t\}\(\-c\)=\-m\_\{t\}\(c\)\.Hence

c≥0⇒mt​\(c\)≥0,c≤0⇒mt​\(c\)≤0\.c\\geq 0\\;\\Rightarrow\\;m\_\{t\}\(c\)\\geq 0,\\qquad c\\leq 0\\;\\Rightarrow\\;m\_\{t\}\(c\)\\leq 0\.Usingxt=−Ht−1​\(Gt−1\+pt\)x\_\{t\}=\-H\_\{t\}^\{\-1\}\(G\_\{t\-1\}\+p\_\{t\}\),

𝔼⁡\[xt\]=−mt​\(Gt−1\),\\mathbb\{E\}\[x\_\{t\}\]=\-\\,m\_\{t\}\(G\_\{t\-1\}\),which implies

Gt−1≥0⇒𝔼⁡\[xt\]≤0,Gt−1≤0⇒𝔼⁡\[xt\]≥0\.G\_\{t\-1\}\\geq 0\\;\\Rightarrow\\;\\mathbb\{E\}\[x\_\{t\}\]\\leq 0,\\qquad G\_\{t\-1\}\\leq 0\\;\\Rightarrow\\;\\mathbb\{E\}\[x\_\{t\}\]\\geq 0\.

#### Step 3: Pairing argument\.

For eachk∈\{1,…,n\}k\\in\\\{1,\\dots,n\\\}, pair roundkkwith round2​n−k\+12n\-k\+1, and define

Rk≐\(fk​\(xk\)−fk​\(uk\)\)\+\(f2​n−k\+1​\(x2​n−k\+1\)−f2​n−k\+1​\(u2​n−k\+1\)\)\.R\_\{k\}\\doteq\(f\_\{k\}\(x\_\{k\}\)\-f\_\{k\}\(u\_\{k\}\)\)\+\(f\_\{2n\-k\+1\}\(x\_\{2n\-k\+1\}\)\-f\_\{2n\-k\+1\}\(u\_\{2n\-k\+1\}\)\)\.Sincegk=\+1g\_\{k\}=\+1andg2​n−k\+1=−1g\_\{2n\-k\+1\}=\-1,

Rk=\(1\+xk\)\+\(1−x2​n−k\+1\)\.R\_\{k\}=\(1\+x\_\{k\}\)\+\(1\-x\_\{2n\-k\+1\}\)\.Both terms are nonnegative sincext∈\[−1,1\]x\_\{t\}\\in\[\-1,1\]\.

The cumulative gradients before the two rounds are

Ak≐Gk−1=G0\+k−1,Bk≐G2​n−k=G0\+k=Ak\+1\.A\_\{k\}\\doteq G\_\{k\-1\}=G\_\{0\}\+k\-1,\\qquad B\_\{k\}\\doteq G\_\{2n\-k\}=G\_\{0\}\+k=A\_\{k\}\+1\.

#### Step 4: Lower bounding each pair\.

We distinguish two cases\.

Case 1:Ak≤0A\_\{k\}\\leq 0\.Then𝔼⁡\[xk\]≥0\\mathbb\{E\}\[x\_\{k\}\]\\geq 0, so

𝔼⁡\[1\+xk\]≥1,\\mathbb\{E\}\[1\+x\_\{k\}\]\\geq 1,and since1−x2​n−k\+1≥01\-x\_\{2n\-k\+1\}\\geq 0,

𝔼⁡\[Rk\]≥1\.\\mathbb\{E\}\[R\_\{k\}\]\\geq 1\.
Case 2:Ak\>0A\_\{k\}\>0\.ThenBk\>0B\_\{k\}\>0, so𝔼⁡\[x2​n−k\+1\]≤0\\mathbb\{E\}\[x\_\{2n\-k\+1\}\]\\leq 0, and thus

𝔼⁡\[1−x2​n−k\+1\]≥1\.\\mathbb\{E\}\[1\-x\_\{2n\-k\+1\}\]\\geq 1\.Since1\+xk≥01\+x\_\{k\}\\geq 0,

𝔼⁡\[Rk\]≥1\.\\mathbb\{E\}\[R\_\{k\}\]\\geq 1\.
In all cases,𝔼⁡\[Rk\]≥1\\mathbb\{E\}\[R\_\{k\}\]\\geq 1for everykk\. Summing overk=1,…,nk=1,\\dots,n,

𝔼⁡\[∑t=1T\(ft​\(xt\)−ft​\(ut\)\)\]=∑k=1n𝔼⁡\[Rk\]≥n=T2\.\\mathbb\{E\}\\left\[\\sum\_\{t=1\}^\{T\}\\bigl\(f\_\{t\}\(x\_\{t\}\)\-f\_\{t\}\(u\_\{t\}\)\\bigr\)\\right\]=\\sum\_\{k=1\}^\{n\}\\mathbb\{E\}\[R\_\{k\}\]\\geq n=\\frac\{T\}\{2\}\.∎ Note that starting with positive wave is not necessary, since what matters is the switch, as shown next\.

###### Corollary 18\.

Under the assumptions of Theorem[17](https://arxiv.org/html/2609.30556#Thmtheorem17), letT=2​nT=2nand consider the oblivious loss sequence

gt=\{−1,t≤n,\+1,t\>n,ut=−gt\.g\_\{t\}=\\begin\{cases\}\-1,&t\\leq n,\\\\ \+1,&t\>n,\\end\{cases\}\\qquad u\_\{t\}=\-g\_\{t\}\.Then

𝔼⁡\[∑t=1T\(ft​\(xt\)−ft​\(ut\)\)\]≥T2\.\\mathbb\{E\}\\left\[\\sum\_\{t=1\}^\{T\}\\bigl\(f\_\{t\}\(x\_\{t\}\)\-f\_\{t\}\(u\_\{t\}\)\\bigr\)\\right\]\\;\\geq\\;\\frac\{T\}\{2\}\.

###### Proof\.

The proof is identical to that of Theorem[17](https://arxiv.org/html/2609.30556#Thmtheorem17), except that in the pairing step33, we have

Rk≐\(fk​\(xk\)−fk​\(uk\)\)\+\(f2​n−k\+1​\(x2​n−k\+1\)−f2​n−k\+1​\(u2​n−k\+1\)\)\.R\_\{k\}\\doteq\(f\_\{k\}\(x\_\{k\}\)\-f\_\{k\}\(u\_\{k\}\)\)\+\(f\_\{2n\-k\+1\}\(x\_\{2n\-k\+1\}\)\-f\_\{2n\-k\+1\}\(u\_\{2n\-k\+1\}\)\)\.Since nowgk=−1g\_\{k\}=\-1andg2​n−k\+1=\+1g\_\{2n\-k\+1\}=\+1,

Rk=\(1−xk\)\+\(1\+x2​n−k\+1\)\.R\_\{k\}=\(1\-x\_\{k\}\)\+\(1\+x\_\{2n\-k\+1\}\)\.The cumulative gradients before the two rounds are

Ak≐Gk−1=G0−\(k−1\),Bk≐G2​n−k=G0−k=Ak−1\.A\_\{k\}\\doteq G\_\{k\-1\}=G\_\{0\}\-\(k\-1\),\\qquad B\_\{k\}\\doteq G\_\{2n\-k\}=G\_\{0\}\-k=A\_\{k\}\-1\.IfAk≥0A\_\{k\}\\geq 0, then𝔼\[xk\]≤0\\mathop\{\\mathbb\{E\}\}\\left\[\{x\_\{k\}\}\\right\]\\leq 0, so𝔼\[1−xk\]≥1\\mathop\{\\mathbb\{E\}\}\\left\[\{1\-x\_\{k\}\}\\right\]\\geq 1\. IfAk<0A\_\{k\}<0, thenBk<0B\_\{k\}<0, so𝔼\[x2​n−k\+1\]≥0\\mathop\{\\mathbb\{E\}\}\\left\[\{x\_\{2n\-k\+1\}\}\\right\]\\geq 0, and hence𝔼\[1\+x2​n−k\+1\]≥1\\mathop\{\\mathbb\{E\}\}\\left\[\{1\+x\_\{2n\-k\+1\}\}\\right\]\\geq 1\. Since both terms are always nonnegative, in either case𝔼\[Rk\]≥1\\mathop\{\\mathbb\{E\}\}\\left\[\{R\_\{k\}\}\\right\]\\geq 1\. Summing overk=1,…,nk=1,\\dots,nyields the claim\. ∎

Now we are ready to prove[Theorem8](https://arxiv.org/html/2609.30556#Thmtheorem8):

###### Proof\.

The adversary samples a half\-gadget lengthhhuniformly fromℋ\\mathcal\{H\}\. It then builds the loss sequence by concatenatingτ\\taugadgets of length2​h2h, with alternating orientation: for oddm∈\{1,…,τ\}m\\in\\\{1,\\dots,\\tau\\\}, themm\-th gadget is

\(\+1,…,\+1⏟h​rounds,−1,…,−1⏟h​rounds\),\(\\underbrace\{\+1,\\dots,\+1\}\_\{h\\text\{ rounds\}\},\\underbrace\{\-1,\\dots,\-1\}\_\{h\\text\{ rounds\}\}\),and for evenm∈\{1,…,τ\}m\\in\\\{1,\\dots,\\tau\\\}, themm\-th gadget is

\(−1,…,−1⏟h​rounds,\+1,…,\+1⏟h​rounds\)\.\(\\underbrace\{\-1,\\dots,\-1\}\_\{h\\text\{ rounds\}\},\\underbrace\{\+1,\\dots,\+1\}\_\{h\\text\{ rounds\}\}\)\.Sinceh≤η​T/τh\\leq\\eta T/\\tauandη<1/2\\eta<1/2, the total length of theseτ\\taugadgets is at most

2​h​τ≤2​η​T≤T,2h\\tau\\leq 2\\eta T\\leq T,so the construction fits in the horizon\. For the remaining roundst\>2​h​τt\>2h\\tau, define

gt≐g2​h​τ\.g\_\{t\}\\doteq g\_\{2h\\tau\}\.Finally, set the comparator to oppose the losses \(for each realized randomization\):

ut≐−gtfor all​t=1,…,T\.u\_\{t\}\\doteq\-g\_\{t\}\\qquad\\text\{for all \}t=1,\\dots,T\.

#### Comparator path length\.

Inside each gadget, the comparator switches exactly once at the midpoint\. The padded rounds are constant and create no further switches\. Therefore

PT​\(u\)=2​τ\.P\_\{T\}\(u\)=2\\tau\.
Note that for every roundtt, sinceut=−gtu\_\{t\}=\-g\_\{t\}andxt∈\[−1,1\]x\_\{t\}\\in\[\-1,1\],

ft​\(xt\)−ft​\(ut\)=gt​xt−gt​ut=gt​xt\+1≥0\.f\_\{t\}\(x\_\{t\}\)\-f\_\{t\}\(u\_\{t\}\)=g\_\{t\}x\_\{t\}\-g\_\{t\}u\_\{t\}=g\_\{t\}x\_\{t\}\+1\\geq 0\.Hence𝔼\[ℛT\]≥0\\mathop\{\\mathbb\{E\}\}\\left\[\{\\mathcal\{R\}\_\{T\}\}\\right\]\\geq 0for every realization of the randomness\.

#### Choose the dyadic scale\.

Now fix any restart periodkksatisfying1/η≤k≤T/τ1/\\eta\\leq k\\leq T/\\tau, and define

h⋆≐2⌊log2⁡\(η​k\)⌋\.h^\{\\star\}\\doteq 2^\{\\lfloor\\log\_\{2\}\(\\eta k\)\\rfloor\}\.Sinceη​k≥1\\eta k\\geq 1, we haveh⋆≥1h^\{\\star\}\\geq 1, and sinceη​k≤η​T/τ\\eta k\\leq\\eta T/\\tau, we haveh⋆∈ℋh^\{\\star\}\\in\\mathcal\{H\}\. By construction,

η​k2<h⋆≤η​k\.\\frac\{\\eta k\}\{2\}<h^\{\\star\}\\leq\\eta k\.This is key: the gadget half\-length is within a constant factor of \(a fraction of\) the restart period:

2​h⋆≤2​η​k<k\.2h^\{\\star\}\\leq 2\\eta k<k\.Thus each gadget is strictly shorter than one restart block\.

LetA≐\{h=h⋆\}\.A\\doteq\\\{h=h^\{\\star\}\\\}\.Becausehhis drawn uniformly fromℋ\\mathcal\{H\},

Pr⁡\(A\)=1J\+1,J≐⌊log2⁡\(η​T/τ\)⌋\.\\Pr\(A\)=\\frac\{1\}\{J\+1\},\\quad J\\doteq\\left\\lfloor\\log\_\{2\}\\left\(\\eta T/\\tau\\right\)\\right\\rfloor\.

#### Number of uncut gadgets

Condition on the eventAA\. The active gadget region has total length

2​h⋆​τ≤2​η​k​τ\.2h^\{\\star\}\\tau\\leq 2\\eta k\\tau\.Since restart boundaries occur everykkrounds, the number of restart boundaries falling inside this active region is at most

⌊2​h⋆​τk⌋≤2​h⋆​τk≤2​η​τ\.\\left\\lfloor\\frac\{2h^\{\\star\}\\tau\}\{k\}\\right\\rfloor\\leq\\frac\{2h^\{\\star\}\\tau\}\{k\}\\leq 2\\eta\\tau\.
Because every gadget has length2​h⋆<k2h^\{\\star\}<k, a single restart boundary can intersect the interior of at most one gadget, and a single gadget can contain at most one restart boundary\. Therefore at most2​η​τ2\\eta\\taugadgets are cut by a restart, and at least

τ−2​η​τ=\(1−2​η\)​τ\\tau\-2\\eta\\tau=\(1\-2\\eta\)\\taugadgets are fully contained in a single restart block\.

#### Regret from each uncut gadget\.

Consider any gadget that is not cut by a restart\. Over that gadget, the learner runs continuously with no reset\. Reindex the gadget as a fresh2​h⋆2h^\{\\star\}\-round instance\. The state at the beginning of the gadget simply becomes the initial gradientG0G\_\{0\}for that local instance\.

For an odd gadget, the loss sequence is precisely the two\-phase sequence used in the proof of Thm\.[17](https://arxiv.org/html/2609.30556#Thmtheorem17)\. Hence that gadget contributes expected dynamic regret at least2​h⋆2=h⋆\.\\frac\{2h^\{\\star\}\}\{2\}=h^\{\\star\}\.For an even gadget, the same lower bound follows from Corollary[18](https://arxiv.org/html/2609.30556#Thmtheorem18)\.

Summing over the at least\(1−2​η\)​τ\(1\-2\\eta\)\\tauuncut gadgets yields

𝔼\[ℛT∣A\]≥\(1−2​η\)​τ​h⋆≥η⁡\(1−2​η\)2​k​τ\.\\mathop\{\\mathbb\{E\}\}\\left\[\{\\mathcal\{R\}\_\{T\}\\mid A\}\\right\]\\;\\geq\\;\(1\-2\\eta\)\\tau\\,h^\{\\star\}\\geq\\frac\{\\eta\(1\-2\\eta\)\}\{2\}\\,k\\tau\.
We expand the unconditional expectation:

𝔼\[ℛT\]=Pr⁡\(A\)​𝔼\[ℛT∣A\]\+Pr⁡\(Ac\)​𝔼\[ℛT∣Ac\]\.\\mathop\{\\mathbb\{E\}\}\\left\[\{\\mathcal\{R\}\_\{T\}\}\\right\]=\\Pr\(A\)\\,\\mathop\{\\mathbb\{E\}\}\\left\[\{\\mathcal\{R\}\_\{T\}\\mid A\}\\right\]\+\\Pr\(A^\{c\}\)\\,\\mathop\{\\mathbb\{E\}\}\\left\[\{\\mathcal\{R\}\_\{T\}\\mid A^\{c\}\}\\right\]\.Since𝔼\[ℛT\]≥0\\mathop\{\\mathbb\{E\}\}\\left\[\{\\mathcal\{R\}\_\{T\}\}\\right\]\\geq 0, both conditional expectations are nonnegative, and in particular

Pr⁡\(Ac\)​𝔼\[ℛT∣Ac\]≥0\.\\Pr\(A^\{c\}\)\\,\\mathop\{\\mathbb\{E\}\}\\left\[\{\\mathcal\{R\}\_\{T\}\\mid A^\{c\}\}\\right\]\\geq 0\.Therefore we may drop this second term and obtain the lower bound

𝔼\[ℛT\]≥Pr⁡\(A\)​𝔼\[ℛT∣A\]\.\\mathop\{\\mathbb\{E\}\}\\left\[\{\\mathcal\{R\}\_\{T\}\}\\right\]\\;\\geq\\;\\Pr\(A\)\\,\\mathop\{\\mathbb\{E\}\}\\left\[\{\\mathcal\{R\}\_\{T\}\\mid A\}\\right\]\.UsingPr⁡\(A\)=1/\(J\+1\)\\Pr\(A\)=1/\(J\+1\)and the conditional lower bound above gives

𝔼\[ℛT\]≥1J\+1⋅η⁡\(1−2​η\)2​k​τ\.\\mathop\{\\mathbb\{E\}\}\\left\[\{\\mathcal\{R\}\_\{T\}\}\\right\]\\;\\geq\\;\\frac\{1\}\{J\+1\}\\cdot\\frac\{\\eta\(1\-2\\eta\)\}\{2\}\\,k\\tau\.
Finally, sinceη∈\(0,1/2\)\\eta\\in\(0,1/2\)is a fixed constant,

J\+1=1\+⌊log2⁡\(η​Tτ\)⌋=Θ⁡\(log⁡\(T/τ\)\)\.J\+1=1\+\\left\\lfloor\\log\_\{2\}\\left\(\\eta\\frac\{T\}\{\\tau\}\\right\)\\right\\rfloor=\\Theta\(\\log\(T/\\tau\)\)\.Hence𝔼\[ℛT\]=Ω⁡\(k​τlog⁡\(T/τ\)\)\.\\mathop\{\\mathbb\{E\}\}\\left\[\{\\mathcal\{R\}\_\{T\}\}\\right\]=\\Omega\\left\(\\frac\{k\\tau\}\{\\log\(T/\\tau\)\}\\right\)\.This completes the proof\. ∎

###### Lemma 19\(Sherman branch\)\.

Suppose that a fresh run of FPRLL\(k\)\(k\)makes at mostC​kC\\sqrt\{k\}expected switches on each length\-kkblock, for a constantC\>0C\>0\. Then there exists an oblivious distribution overTT\-round loss sequences and a fixed comparatoru⋆∈\[−1,1\]u^\{\\star\}\\in\[\-1,1\]such that

𝔼\[ℛT𝟏​\(u⋆,…,u⋆\)\]=Ω⁡\(Tk\)\.\\mathop\{\\mathbb\{E\}\}\\left\[\{\\mathcal\{R\}^\{\\mathbf\{1\}\}\_\{T\}\(u^\{\\star\},\\ldots,u^\{\\star\}\)\}\\right\]=\\Omega\\left\(\\frac\{T\}\{\\sqrt\{k\}\}\\right\)\.

###### Proof\.

We use the following consequence of[Sherman and Koren \[19, Thm\. 4\]](https://arxiv.org/html/2609.30556#bib.bib13): for a length\-kkonline linear problem on\[−1,1\]\[\-1,1\], there exist a stochastic loss distribution𝒟k\\mathcal\{D\}\_\{k\}and a comparatoru⋆∈\[−1,1\]u^\{\\star\}\\in\[\-1,1\], fixed as a minimizer of the expected loss under𝒟k\\mathcal\{D\}\_\{k\}, such that any algorithm making𝒪⁡\(k\)\\mathcal\{O\}\(\\sqrt\{k\}\)expected switches incursΩ⁡\(k\)\\Omega\(\\sqrt\{k\}\)expected static regret againstu⋆u^\{\\star\}\.

Construct theTT\-round adversary by drawing, independently on each full restart block, a fresh length\-kksample from this same distribution𝒟k\\mathcal\{D\}\_\{k\}\. Although the realized losses differ from block to block, the comparator remains the sameu⋆u^\{\\star\}, sinceu⋆u^\{\\star\}is defined by𝒟k\\mathcal\{D\}\_\{k\}, not by the realized sample\.

Thus every full block contributesΩ⁡\(k\)\\Omega\(\\sqrt\{k\}\)expected static regret\. SinceℛT𝟏\\mathcal\{R\}^\{\\mathbf\{1\}\}\_\{T\}only adds the learner’s nonnegative indicator switching cost, the same lower bound holds forℛT𝟏\\mathcal\{R\}^\{\\mathbf\{1\}\}\_\{T\}\. Therefore

𝔼\[ℛT𝟏​\(u⋆,…,u⋆\)\]≥⌊Tk⌋​Ω​\(k\)=Ω⁡\(Tk\),\\mathop\{\\mathbb\{E\}\}\\left\[\{\\mathcal\{R\}^\{\\mathbf\{1\}\}\_\{T\}\(u^\{\\star\},\\ldots,u^\{\\star\}\)\}\\right\]\\geq\\left\\lfloor\\frac\{T\}\{k\}\\right\\rfloor\\Omega\(\\sqrt\{k\}\)=\\Omega\\left\(\\frac\{T\}\{\\sqrt\{k\}\}\\right\),wherek≤Tk\\leq T\. The comparator is stationary throughout, soST=PT=0S\_\{T\}=P\_\{T\}=0\. ∎

###### Proposition 20\(Combined lower bound\)\.

Consider the following two full\-horizon adversaries:

1. 1\.the adversary from[Theorem8](https://arxiv.org/html/2609.30556#Thmtheorem8), together with comparator sequenceugad1:Tu^\{\\mathrm\{gad\}\}\_\{1:T\}, for which ST\(u1:Tgad\)=τ,PT\(u1:Tgad\)=2τ,S\_\{T\}\(u^\{\\mathrm\{gad\}\}\_\{1:T\}\)=\\tau,\\qquad P\_\{T\}\(u^\{\\mathrm\{gad\}\}\_\{1:T\}\)=2\\tau,and 𝔼\[ℛT𝟏\(u1:Tgad\)\]=Ω\(k​τlog⁡\(T/τ\)\);\\mathop\{\\mathbb\{E\}\}\\left\[\{\\mathcal\{R\}^\{\\mathbf\{1\}\}\_\{T\}\(u^\{\\mathrm\{gad\}\}\_\{1:T\}\)\}\\right\]=\\Omega\\left\(\\frac\{k\\tau\}\{\\log\(T/\\tau\)\}\\right\);
2. 2\.the adversary from[Lemma19](https://arxiv.org/html/2609.30556#Thmtheorem19), together with the stationary comparator sequenceush1:T≡u⋆u^\{\\mathrm\{sh\}\}\_\{1:T\}\\equiv u^\{\\star\}, for which ST\(u1:Tsh\)=0,PT\(u1:Tsh\)=0,S\_\{T\}\(u^\{\\mathrm\{sh\}\}\_\{1:T\}\)=0,\\qquad P\_\{T\}\(u^\{\\mathrm\{sh\}\}\_\{1:T\}\)=0,and 𝔼\[ℛT𝟏\(u1:Tsh\)\]=Ω\(Tk\)\.\\mathop\{\\mathbb\{E\}\}\\left\[\{\\mathcal\{R\}^\{\\mathbf\{1\}\}\_\{T\}\(u^\{\\mathrm\{sh\}\}\_\{1:T\}\)\}\\right\]=\\Omega\\left\(\\frac\{T\}\{\\sqrt\{k\}\}\\right\)\.

For the fixed restart periodkk, define a mixed adversary that, at time00, chooses one of these two branches uniformly at random and then plays the chosen branch for the entire horizon\. The resulting mixed adversary may depend onkkthrough the Sherman branch\. Letu1:Tu\_\{1:T\}denote the comparator sequence associated with the realized branch\. Then

𝔼\[ℛT𝟏\(u1:T\)\]=Ω\(k​τlog⁡\(T/τ\)\+Tk\)\.\\mathop\{\\mathbb\{E\}\}\\left\[\{\\mathcal\{R\}^\{\\mathbf\{1\}\}\_\{T\}\(u\_\{1:T\}\)\}\\right\]=\\Omega\\left\(\\frac\{k\\tau\}\{\\log\(T/\\tau\)\}\+\\frac\{T\}\{\\sqrt\{k\}\}\\right\)\.

###### Proof\.

Conditioning on the branch chosen by the adversary gives

𝔼\[ℛT𝟏\(u1:T\)\]=12𝔼\[ℛT𝟏\(u1:Tgad\)\]\+12𝔼\[ℛT𝟏\(u1:Tsh\)\]\.\\mathop\{\\mathbb\{E\}\}\\left\[\{\\mathcal\{R\}^\{\\mathbf\{1\}\}\_\{T\}\(u\_\{1:T\}\)\}\\right\]=\\frac\{1\}\{2\}\\mathop\{\\mathbb\{E\}\}\\left\[\{\\mathcal\{R\}^\{\\mathbf\{1\}\}\_\{T\}\(u^\{\\mathrm\{gad\}\}\_\{1:T\}\)\}\\right\]\+\\frac\{1\}\{2\}\\mathop\{\\mathbb\{E\}\}\\left\[\{\\mathcal\{R\}^\{\\mathbf\{1\}\}\_\{T\}\(u^\{\\mathrm\{sh\}\}\_\{1:T\}\)\}\\right\]\.Applying[Theorem8](https://arxiv.org/html/2609.30556#Thmtheorem8)to the first term and[Lemma19](https://arxiv.org/html/2609.30556#Thmtheorem19)to the second term yields the claim\. ∎

###### Proof\.

Condition onCC\. TheC=0C\{=\}0branch isk0k\_\{0\}\-independent, and[Theorem8](https://arxiv.org/html/2609.30556#Thmtheorem8)givesΩ⁡\(k​τ/log⁡\(T/τ\)\)\\Omega\(k\\tau/\\log\(T/\\tau\)\)\. ForC=1C\{=\}1, condition further onk0k\_\{0\}: on\{k0=k\}\\\{k\_\{0\}=k\\\},[Lemma19](https://arxiv.org/html/2609.30556#Thmtheorem19)yieldsΩ⁡\(T/k\)\\Omega\(T/\\sqrt\{k\}\); on\{k0≠k\}\\\{k\_\{0\}\\neq k\\\},𝔼⁡\[ℛT𝟏\]≥0\\mathbb\{E\}\[\\mathcal\{R\}^\{\\mathbf\{1\}\}\_\{T\}\]\\geq 0sinceuk0⋆u^\{\\star\}\_\{k\_\{0\}\}is the per\-round expected\-loss minimizer of𝒟k0sh\\mathcal\{D\}^\{\\mathrm\{sh\}\}\_\{k\_\{0\}\}\. AsPr⁡\(k0=k\)=1/\|ℋ\|=Θ⁡\(1/log⁡T\)\\Pr\(k\_\{0\}=k\)=1/\|\\mathcal\{H\}\|=\\Theta\(1/\\log T\), theC=1C\{=\}1branch contributesΩ⁡\(T/\(k​log⁡T\)\)\\Omega\(T/\(\\sqrt\{k\}\\log T\)\)\. ∎

## Appendix CProofs for the base learner

To prove[Theorem5](https://arxiv.org/html/2609.30556#Thmtheorem5), we establish four intermediate lemmas and then combine them\.

- •[Lemma21](https://arxiv.org/html/2609.30556#Thmtheorem21)gives the main regret decomposition, splitting the expected dynamic regret into a*static*term\(𝐈\)\\mathbf\{\(I\)\}and a*dynamic*term\(𝐈𝐈\)\\mathbf\{\(II\)\}\. This extends the decomposition in\[[15](https://arxiv.org/html/2609.30556#bib.bib10)\]to our perturbed, barrier\-regularized setting\.
- •[Lemma22](https://arxiv.org/html/2609.30556#Thmtheorem22)bounds the static term\(𝐈\)\\mathbf\{\(I\)\}, explicitly accounting for the effect of the Laplace perturbations\.
- •[Lemma23](https://arxiv.org/html/2609.30556#Thmtheorem23)bounds the dynamic term\(𝐈𝐈\)\\mathbf\{\(II\)\}, capturing the dependence on comparator drift through the barrier geometry\.
- •[Lemma24](https://arxiv.org/html/2609.30556#Thmtheorem24)controls the total variation distance between consecutive sampling distributions, which we use to bound the switching\-cost contribution\.

Among these ingredients, only the total\-variation bound in[Lemma24](https://arxiv.org/html/2609.30556#Thmtheorem24)follows the general approach of\[[18](https://arxiv.org/html/2609.30556#bib.bib12)\]; the other three lemmas are specific to our setting\.

###### Lemma 21\.

Let\{ft​\(⋅\)\}t=1T\\\{f\_\{t\}\(\\cdot\)\\\}\_\{t=1\}^\{T\}be an arbitrary set of functions\. Let𝐩t∼Lap​\(μ\)\\bm\{p\}\_\{t\}\\sim\\text\{Lap\}\(\\mu\)\. Assume that for alltt, the fresh perturbed minimizer

𝒙~t\+1≐argmin𝒙Ft​\(𝒙\)\+⟨𝒑t,𝒙⟩\\tilde\{\\bm\{x\}\}\_\{t\+1\}\\doteq\\argmin\_\{\\bm\{x\}\}F\_\{t\}\(\\bm\{x\}\)\+\\langle\{\\bm\{p\}\_\{t\}\},\{\\bm\{x\}\}\\rangleis well\-defined\. Define the loss part ofℛT𝟏​\(\{𝐮t\}t=1T\)\\mathcal\{R\}^\{\\mathbf\{1\}\}\_\{T\}\(\\\{\\bm\{u\}\_\{t\}\\\}\_\{t=1\}^\{T\}\)as

ℛT​\(\{𝒖t\}t=1T\)=∑t=1T\(ft​\(𝒙t\)−ft​\(𝒖t\)\)\\mathcal\{R\}\_\{T\}\(\\\{\\bm\{u\}\_\{t\}\\\}\_\{t=1\}^\{T\}\)=\\sum\_\{t=1\}^\{T\}\\left\(f\_\{t\}\(\\bm\{x\}\_\{t\}\)\-f\_\{t\}\(\\bm\{u\}\_\{t\}\)\\right\), where𝐱t\\bm\{x\}\_\{t\}are the output of[Algorithm1](https://arxiv.org/html/2609.30556#alg1)\. Then, the algorithm that selects the actions𝐱~t\+1,∀t\\tilde\{\\bm\{x\}\}\_\{t\+1\},\\forall tachieves the following dynamic regret bound:

𝔼\[ℛT\]≤∑t=1TFt​\(𝒙~t\)−Ft​\(𝒙~t\+1\)⏞\(𝐈\)\+∑t=1T−1Ft​\(𝒖t\+1γ\)−Ft​\(𝒖tγ\)⏟\(𝐈𝐈\)\+r⁡\(𝒖1γ\)\+1\+G​γ​R​T\.\\mathop\{\\mathbb\{E\}\}\\left\[\{\\mathcal\{R\}\_\{T\}\}\\right\]\\leq\\overbrace\{\\sum\_\{t=1\}^\{T\}F\_\{t\}\(\\bm\{\\tilde\{x\}\}\_\{t\}\)\-F\_\{t\}\(\\bm\{\\tilde\{x\}\}\_\{t\+1\}\)\}^\{\\mathbf\{\(I\)\}\}\\ \+\\ \\underbrace\{\\sum\_\{t=1\}^\{T\-1\}F\_\{t\}\(\\bm\{u\}^\{\\gamma\}\_\{t\+1\}\)\-F\_\{t\}\(\\bm\{u\}^\{\\gamma\}\_\{t\}\)\}\_\{\\mathbf\{\(II\)\}\}\\ \+\\ r\(\\bm\{u\}^\{\\gamma\}\_\{1\}\)\+1\+G\\gamma R\\,T\.\(20\)

###### Proof of[Lemma21](https://arxiv.org/html/2609.30556#Thmtheorem21)\.

∑t=1Tft​\(𝒙~t\)−∑t=1Tft​\(𝒖t\)−⟨𝒑T,𝒖Tγ⟩\\displaystyle\\sum\_\{t=1\}^\{T\}f\_\{t\}\(\\tilde\{\\bm\{x\}\}\_\{t\}\)\-\\sum\_\{t=1\}^\{T\}f\_\{t\}\(\\bm\{u\}\_\{t\}\)\-\\langle\{\\bm\{p\}\_\{T\}\},\{\\bm\{u\}^\{\\gamma\}\_\{T\}\}\\rangle=∑t=1Tft​\(𝒙~t\)−∑t=1Tft​\(𝒖tγ\)−⟨𝒑T,𝒖Tγ⟩\+∑t=1T\(ft​\(𝒖tγ\)−ft​\(𝒖t\)⏞at\)\\displaystyle=\\sum\_\{t=1\}^\{T\}f\_\{t\}\(\\tilde\{\\bm\{x\}\}\_\{t\}\)\-\\sum\_\{t=1\}^\{T\}f\_\{t\}\(\\bm\{u\}^\{\\gamma\}\_\{t\}\)\-\\langle\{\\bm\{p\}\_\{T\}\},\{\\bm\{u\}^\{\\gamma\}\_\{T\}\}\\rangle\\;\+\\;\\sum\_\{t=1\}^\{T\}\\big\(\\overbrace\{f\_\{t\}\(\\bm\{u\}^\{\\gamma\}\_\{t\}\)\-f\_\{t\}\(\\bm\{u\}\_\{t\}\)\}^\{\\text\{$a\_\{t\}$\}\}\\big\)=∑t=1T\(Ft\(𝒙~t\)−Ft−1\(𝒙~t\)\)−\(∑t=1T\(Ft\(𝒖tγ\)−Ft−1\(𝒖tγ\)\)\+⟨𝒑T,𝒖Tγ⟩\)\+a1:T\\displaystyle=\\sum\_\{t=1\}^\{T\}\\left\(F\_\{t\}\(\\tilde\{\\bm\{x\}\}\_\{t\}\)\-F\_\{t\-1\}\(\\tilde\{\\bm\{x\}\}\_\{t\}\)\\right\)\-\\left\(\\sum\_\{t=1\}^\{T\}\\left\(F\_\{t\}\(\\bm\{u\}^\{\\gamma\}\_\{t\}\)\-F\_\{t\-1\}\(\\bm\{u\}^\{\\gamma\}\_\{t\}\)\\right\)\+\\langle\{\\bm\{p\}\_\{T\}\},\{\\bm\{u\}^\{\\gamma\}\_\{T\}\}\\rangle\\right\)\\,\+\\,a\_\{1:T\}=∑t=1TFt\(𝒙~t\)−∑t=1TFt−1\(𝒙~t\)−\(∑t=1TFt\(𝒖tγ\)\+⟨𝒑T,𝒖Tγ⟩−∑t=1TFt−1\(𝒖tγ\)\)\+a1:T\\displaystyle=\\sum\_\{t=1\}^\{T\}F\_\{t\}\(\\tilde\{\\bm\{x\}\}\_\{t\}\)\-\\sum\_\{t=1\}^\{T\}F\_\{t\-1\}\(\\tilde\{\\bm\{x\}\}\_\{t\}\)\-\\left\(\\sum\_\{t=1\}^\{T\}F\_\{t\}\(\\bm\{u\}^\{\\gamma\}\_\{t\}\)\+\\langle\{\\bm\{p\}\_\{T\}\},\{\\bm\{u\}^\{\\gamma\}\_\{T\}\}\\rangle\-\\sum\_\{t=1\}^\{T\}F\_\{t\-1\}\(\\bm\{u\}^\{\\gamma\}\_\{t\}\)\\right\)\+a\_\{1:T\}=∑t=1TFt​\(𝒙~t\)−∑t=0T−1Ft​\(𝒙~t\+1\)−\(FT​\(𝒖Tγ\)\+⟨𝒑T,𝒖Tγ⟩\+∑t=1T−1Ft​\(𝒖tγ\)−∑t=0T−1Ft​\(𝒖t\+1γ\)\)\\displaystyle=\\sum\_\{t=1\}^\{T\}F\_\{t\}\(\\tilde\{\\bm\{x\}\}\_\{t\}\)\-\\sum\_\{t=0\}^\{T\-1\}F\_\{t\}\(\\tilde\{\\bm\{x\}\}\_\{t\+1\}\)\-\\left\(F\_\{T\}\(\\bm\{u\}^\{\\gamma\}\_\{T\}\)\+\\langle\{\\bm\{p\}\_\{T\}\},\{\\bm\{u\}^\{\\gamma\}\_\{T\}\}\\rangle\+\\sum\_\{t=1\}^\{T\-1\}F\_\{t\}\(\\bm\{u\}^\{\\gamma\}\_\{t\}\)\-\\sum\_\{t=0\}^\{T\-1\}F\_\{t\}\(\\bm\{u\}^\{\\gamma\}\_\{t\+1\}\)\\right\)\+a1:T\\displaystyle\\qquad\+a\_\{1:T\}≤∑t=1TFt​\(𝒙~t\)−∑t=1T−1Ft​\(𝒙~t\+1\)−\(FT​\(𝒙T\+1\)\+⟨𝒑T,𝒙T\+1⟩\+∑t=1T−1Ft​\(𝒖tγ\)−∑t=1T−1Ft​\(𝒖t\+1γ\)\)\\displaystyle\\leq\\sum\_\{t=1\}^\{T\}F\_\{t\}\(\\tilde\{\\bm\{x\}\}\_\{t\}\)\-\\sum\_\{t=1\}^\{T\-1\}F\_\{t\}\(\\tilde\{\\bm\{x\}\}\_\{t\+1\}\)\-\\left\(F\_\{T\}\(\\bm\{x\}\_\{T\+1\}\)\+\\langle\{\\bm\{p\}\_\{T\}\},\{\\bm\{x\}\_\{T\+1\}\}\\rangle\+\\sum\_\{t=1\}^\{T\-1\}F\_\{t\}\(\\bm\{u\}^\{\\gamma\}\_\{t\}\)\-\\sum\_\{t=1\}^\{T\-1\}F\_\{t\}\(\\bm\{u\}^\{\\gamma\}\_\{t\+1\}\)\\right\)\+a1:T\+f0\(𝒖1γ\)\\displaystyle\\qquad\+a\_\{1:T\}\+f\_\{0\}\(\\bm\{u\}^\{\\gamma\}\_\{1\}\)≤∑t=1TFt\(𝒙~t\)−∑t=1TFt\(𝒙~t\+1\)−\(∑t=1T−1Ft\(𝒖tγ\)−∑t=1T−1Ft\(𝒖t\+1γ\)\)−⟨𝒑T,𝒙T\+1⟩\+a1:T\+r\(𝒖1γ\)\+1\.\\displaystyle\\leq\\sum\_\{t=1\}^\{T\}F\_\{t\}\(\\tilde\{\\bm\{x\}\}\_\{t\}\)\-\\sum\_\{t=1\}^\{T\}F\_\{t\}\(\\tilde\{\\bm\{x\}\}\_\{t\+1\}\)\-\\left\(\\sum\_\{t=1\}^\{T\-1\}F\_\{t\}\(\\bm\{u\}^\{\\gamma\}\_\{t\}\)\-\\sum\_\{t=1\}^\{T\-1\}F\_\{t\}\(\\bm\{u\}^\{\\gamma\}\_\{t\+1\}\)\\right\)\-\\langle\{\\bm\{p\}\_\{T\}\},\{\\bm\{x\}\_\{T\+1\}\}\\rangle\+a\_\{1:T\}\+r\(\\bm\{u\}^\{\\gamma\}\_\{1\}\)\+1\.The first inequality uses the update\-rule optimality

FT​\(𝒙T\+1\)\+⟨𝒑T,𝒙T\+1⟩≤FT​\(𝒖Tγ\)\+⟨𝒑T,𝒖Tγ⟩,F\_\{T\}\(\\bm\{x\}\_\{T\+1\}\)\+\\langle\{\\bm\{p\}\_\{T\}\},\{\\bm\{x\}\_\{T\+1\}\}\\rangle\\leq F\_\{T\}\(\\bm\{u\}^\{\\gamma\}\_\{T\}\)\+\\langle\{\\bm\{p\}\_\{T\}\},\{\\bm\{u\}^\{\\gamma\}\_\{T\}\}\\rangle,and−F0​\(𝒙~1\)≤0\-F\_\{0\}\(\\tilde\{\\bm\{x\}\}\_\{1\}\)\\leq 0\(sincer≥0r\\geq 0andbγ≥0b\_\{\\gamma\}\\geq 0on𝒳\\mathcal\{X\}\)\. The second inequality usesbγ≤1b\_\{\\gamma\}\\leq 1on𝒳γ\\mathcal\{X\}^\{\\gamma\}, givingf0​\(𝒖1γ\)≤r⁡\(𝒖1γ\)\+1f\_\{0\}\(\\bm\{u\}^\{\\gamma\}\_\{1\}\)\\leq r\(\\bm\{u\}^\{\\gamma\}\_\{1\}\)\+1\. Overall

∑t=1T\\displaystyle\\sum\_\{t=1\}^\{T\}\(ft​\(𝒙~t\)−ft​\(𝒖t\)\)−⟨𝒑T,𝒖Tγ⟩\\displaystyle\\left\(f\_\{t\}\(\\tilde\{\\bm\{x\}\}\_\{t\}\)\-f\_\{t\}\(\\bm\{u\}\_\{t\}\)\\right\)\-\\langle\{\\bm\{p\}\_\{T\}\},\{\\bm\{u\}^\{\\gamma\}\_\{T\}\}\\rangle≤∑t=1T\(Ft\(𝒙~t\)−Ft\(𝒙~t\+1\)\)\+∑t=1T−1\(Ft\(𝒖t\+1γ\)−Ft\(𝒖tγ\)\)\+r\(𝒖1\)\+1\+a1:T−⟨𝒑T,𝒙T\+1⟩\.\\displaystyle\\leq\\sum\_\{t=1\}^\{T\}\\left\(F\_\{t\}\(\\tilde\{\\bm\{x\}\}\_\{t\}\)\-F\_\{t\}\(\\tilde\{\\bm\{x\}\}\_\{t\+1\}\)\\right\)\+\\sum\_\{t=1\}^\{T\-1\}\\left\(F\_\{t\}\(\\bm\{u\}^\{\\gamma\}\_\{t\+1\}\)\-F\_\{t\}\(\\bm\{u\}^\{\\gamma\}\_\{t\}\)\\right\)\+r\(\\bm\{u\}\_\{1\}\)\+1\+a\_\{1:T\}\-\\langle\{\\bm\{p\}\_\{T\}\},\{\\bm\{x\}\_\{T\+1\}\}\\rangle\.Since the terminal perturbation and terminal point are used only for analysis and are never played by the algorithm, we set𝒑T=𝟎\\bm\{p\}\_\{T\}=\\bm\{0\}and choose𝒙T\+1=argmin𝒙∈𝒳FT​\(𝒙\)\\bm\{x\}\_\{T\+1\}=\\argmin\_\{\\bm\{x\}\\in\\mathcal\{X\}\}F\_\{T\}\(\\bm\{x\}\)\. Then the preceding optimality inequality remains valid, and both terminal inner\-product terms vanish\. In addition, by Lipschitzness:

a1:T=∑t=1Tft\(𝒖tγ\)−ft\(𝒖t\)≤∑t=1TG∥𝒖tγ−𝒖t∥≤GγRT\.\\displaystyle a\_\{1:T\}=\\sum\_\{t=1\}^\{T\}f\_\{t\}\(\\bm\{u\}^\{\\gamma\}\_\{t\}\)\-f\_\{t\}\(\\bm\{u\}\_\{t\}\)\\leq\\sum\_\{t=1\}^\{T\}G\\\|\\bm\{u\}^\{\\gamma\}\_\{t\}\-\\bm\{u\}\_\{t\}\\\|\\leq G\\gamma R\\,T\.\(21\)
Finally: Note since𝒙t\\bm\{x\}\_\{t\}and𝒙~t\\tilde\{\\bm\{x\}\}\_\{t\}have the same density for alltt, we have

𝔼\[ft​\(𝒙t\)\]=𝔼\[ft​\(𝒙t~\)\]\\displaystyle\\mathop\{\\mathbb\{E\}\}\\left\[\{f\_\{t\}\(\\bm\{x\}\_\{t\}\)\}\\right\]=\\mathop\{\\mathbb\{E\}\}\\left\[\{f\_\{t\}\(\\tilde\{\\bm\{x\}\_\{t\}\}\)\}\\right\]\(22\)The above property is guaranteed by the lazy sampling procedure: the fresh minimizer and the \(potentially\) kept one share the same density\.

Hence

𝔼\[ℛT\]\\displaystyle\\mathop\{\\mathbb\{E\}\}\\left\[\{\\mathcal\{R\}\_\{T\}\}\\right\]=𝔼\[∑t=1Tft​\(𝒙t\)−ft​\(𝒖t\)\]=𝔼\[∑t=1Tft​\(𝒙~t\)−ft​\(𝒖t\)\]\\displaystyle=\\mathop\{\\mathbb\{E\}\}\\left\[\{\\sum\_\{t=1\}^\{T\}f\_\{t\}\(\\bm\{x\}\_\{t\}\)\-f\_\{t\}\(\\bm\{u\}\_\{t\}\)\}\\right\]=\\mathop\{\\mathbb\{E\}\}\\left\[\{\\sum\_\{t=1\}^\{T\}f\_\{t\}\(\\tilde\{\\bm\{x\}\}\_\{t\}\)\-f\_\{t\}\(\\bm\{u\}\_\{t\}\)\}\\right\]≤∑t=1T𝔼\[\(Ft​\(𝒙~t\)−Ft​\(𝒙~t\+1\)\)\]\+∑t=1T−1\(Ft​\(𝒖t\+1γ\)−Ft​\(𝒖tγ\)\)\+r⁡\(𝒖1\)\+1\+G​γ​R​T\.\\displaystyle\\leq\\sum\_\{t=1\}^\{T\}\\mathop\{\\mathbb\{E\}\}\\left\[\{\\left\(F\_\{t\}\(\\tilde\{\\bm\{x\}\}\_\{t\}\)\-F\_\{t\}\(\\tilde\{\\bm\{x\}\}\_\{t\+1\}\)\\right\)\}\\right\]\\;\+\\;\\sum\_\{t=1\}^\{T\-1\}\\left\(F\_\{t\}\(\\bm\{u\}^\{\\gamma\}\_\{t\+1\}\)\-F\_\{t\}\(\\bm\{u\}^\{\\gamma\}\_\{t\}\)\\right\)\\;\+\\;r\(\\bm\{u\}\_\{1\}\)\+1\+G\\gamma R\\,T\.∎

###### Lemma 22\.

Under the same conditions as[Lemma21](https://arxiv.org/html/2609.30556#Thmtheorem21), if we further assume thatFtF\_\{t\}isσ\\sigma\-strongly convex for alltt, then

\(𝐈\)≤G22​σ​T\+R​2​d​μ\.\\mathbf\{\(I\)\}\\leq\\tfrac\{G^\{2\}\}\{2\\sigma\}\\,T\\;\+\\;R\\sqrt\{2d\}\\,\\mu\., whereμ\\muis the scale parameter of the Laplace distribution\.

###### Proof of[Lemma22](https://arxiv.org/html/2609.30556#Thmtheorem22)\.

For eachtt, define

F~t​\(⋅\)≐Ft​\(⋅\)\+⟨𝒑t−1,⋅⟩\.\\displaystyle\\tilde\{F\}\_\{t\}\(\\cdot\)\\doteq F\_\{t\}\(\\cdot\)\+\\langle\{\\bm\{p\}\_\{t\-1\}\},\{\\cdot\}\\rangle\.\(23\)Then,

Ft​\(𝒙~t\)−Ft​\(𝒙~t\+1\)\\displaystyle F\_\{t\}\(\\tilde\{\\bm\{x\}\}\_\{t\}\)\-F\_\{t\}\(\\tilde\{\\bm\{x\}\}\_\{t\+1\}\)\(24\)=Ft​\(𝒙~t\)\+⟨𝒑t−1,𝒙~t⟩−\(Ft​\(𝒙~t\+1\)\+⟨𝒑t−1,𝒙~t\+1⟩\)\+⟨𝒑t−1,𝒙~t\+1−𝒙~t⟩\\displaystyle=F\_\{t\}\(\\tilde\{\\bm\{x\}\}\_\{t\}\)\+\\langle\{\\bm\{p\}\_\{t\-1\}\},\{\\tilde\{\\bm\{x\}\}\_\{t\}\}\\rangle\-\\Big\(F\_\{t\}\(\\tilde\{\\bm\{x\}\}\_\{t\+1\}\)\+\\langle\{\\bm\{p\}\_\{t\-1\}\},\{\\tilde\{\\bm\{x\}\}\_\{t\+1\}\}\\rangle\\Big\)\+\\langle\{\\bm\{p\}\_\{t\-1\}\},\{\\tilde\{\\bm\{x\}\}\_\{t\+1\}\-\\tilde\{\\bm\{x\}\}\_\{t\}\}\\rangle\(25\)=F~t​\(𝒙~t\)−F~t​\(𝒙~t\+1\)\+⟨𝒑t−1,𝒙~t\+1−𝒙~t⟩\.\\displaystyle=\\tilde\{F\}\_\{t\}\(\\tilde\{\\bm\{x\}\}\_\{t\}\)\-\\tilde\{F\}\_\{t\}\(\\tilde\{\\bm\{x\}\}\_\{t\+1\}\)\+\\langle\{\\bm\{p\}\_\{t\-1\}\},\{\\tilde\{\\bm\{x\}\}\_\{t\+1\}\-\\tilde\{\\bm\{x\}\}\_\{t\}\}\\rangle\.\(26\)
By strong convexity ofF~t\\tilde\{F\}\_\{t\}, for

𝒔t≐∇Ft​\(𝒙~t\)\+𝒑t−1,\\bm\{s\}\_\{t\}\\doteq\\nabla F\_\{t\}\(\\tilde\{\\bm\{x\}\}\_\{t\}\)\+\\bm\{p\}\_\{t\-1\},we have

F~t​\(𝒙~t\)−F~t​\(𝒙~t\+1\)≤⟨𝒔t,𝒙~t−𝒙~t\+1⟩−σ2​δt2,\\displaystyle\\tilde\{F\}\_\{t\}\(\\tilde\{\\bm\{x\}\}\_\{t\}\)\-\\tilde\{F\}\_\{t\}\(\\tilde\{\\bm\{x\}\}\_\{t\+1\}\)\\;\\leq\\;\\langle\{\\bm\{s\}\_\{t\}\},\{\\tilde\{\\bm\{x\}\}\_\{t\}\-\\tilde\{\\bm\{x\}\}\_\{t\+1\}\}\\rangle\-\\frac\{\\sigma\}\{2\}\\delta\_\{t\}^\{2\},\(27\)where

δt≐‖𝒙~t\+1−𝒙~t‖\.\\delta\_\{t\}\\doteq\\\|\\tilde\{\\bm\{x\}\}\_\{t\+1\}\-\\tilde\{\\bm\{x\}\}\_\{t\}\\\|\.
The optimality condition of the update step at𝒙~t\\tilde\{\\bm\{x\}\}\_\{t\}gives

0=∇Ft−1​\(𝒙~t\)\+𝒑t−1,0=\\nabla F\_\{t\-1\}\(\\tilde\{\\bm\{x\}\}\_\{t\}\)\+\\bm\{p\}\_\{t\-1\},and therefore

∇ft​\(𝒙~t\)=∇Ft​\(𝒙~t\)\+𝒑t−1=𝒔t\.\\nabla f\_\{t\}\(\\tilde\{\\bm\{x\}\}\_\{t\}\)=\\nabla F\_\{t\}\(\\tilde\{\\bm\{x\}\}\_\{t\}\)\+\\bm\{p\}\_\{t\-1\}=\\bm\{s\}\_\{t\}\.Thus, substituting into \([27](https://arxiv.org/html/2609.30556#A3.E27)\) yields

F~t​\(𝒙~t\)−F~t​\(𝒙~t\+1\)\\displaystyle\\tilde\{F\}\_\{t\}\(\\tilde\{\\bm\{x\}\}\_\{t\}\)\-\\tilde\{F\}\_\{t\}\(\\tilde\{\\bm\{x\}\}\_\{t\+1\}\)≤⟨𝒈t,𝒙~t−𝒙~t\+1⟩−σ2​δt2\\displaystyle\\leq\\langle\{\\bm\{g\}\_\{t\}\},\{\\tilde\{\\bm\{x\}\}\_\{t\}\-\\tilde\{\\bm\{x\}\}\_\{t\+1\}\}\\rangle\-\\frac\{\\sigma\}\{2\}\\delta\_\{t\}^\{2\}\(28\)≤G​δt−σ2​δt2≤G22​σ,\\displaystyle\\leq G\\delta\_\{t\}\-\\frac\{\\sigma\}\{2\}\\delta\_\{t\}^\{2\}\\leq\\frac\{G^\{2\}\}\{2\\sigma\},\(29\)where𝒈t≐∇ft​\(𝒙~t\)\\bm\{g\}\_\{t\}\\doteq\\nabla f\_\{t\}\(\\tilde\{\\bm\{x\}\}\_\{t\}\)\. The second inequality follows from Cauchy–Schwarz and Lipschitzness, and the third from the elementary inequality

a​x−b2​x2≤a22​b,a,b\>0\.ax\-\\frac\{b\}\{2\}x^\{2\}\\leq\\frac\{a^\{2\}\}\{2b\},\\qquad a,b\>0\.
Combining \([26](https://arxiv.org/html/2609.30556#A3.E26)\) and \([29](https://arxiv.org/html/2609.30556#A3.E29)\), and summing overt=1,…,Tt=1,\\dots,T, we obtain the following pathwise bound:

∑t=1T\(Ft​\(𝒙~t\)−Ft​\(𝒙~t\+1\)\)≤G22​σ​T\+∑t=1T⟨𝒑t−1,𝒙~t\+1−𝒙~t⟩\.\\displaystyle\\sum\_\{t=1\}^\{T\}\\Big\(F\_\{t\}\(\\tilde\{\\bm\{x\}\}\_\{t\}\)\-F\_\{t\}\(\\tilde\{\\bm\{x\}\}\_\{t\+1\}\)\\Big\)\\leq\\frac\{G^\{2\}\}\{2\\sigma\}T\+\\sum\_\{t=1\}^\{T\}\\langle\{\\bm\{p\}\_\{t\-1\}\},\{\\tilde\{\\bm\{x\}\}\_\{t\+1\}\-\\tilde\{\\bm\{x\}\}\_\{t\}\}\\rangle\.\(30\)
Now let𝒜\\mathcal\{A\}denote the original perturbation law, under which the vectors\{𝒑t\}t=0T−1\\\{\\bm\{p\}\_\{t\}\\\}\_\{t=0\}^\{T\-1\}are i\.i\.d\. Laplace\. Letℬ\\mathcal\{B\}be any other law on the perturbations such that each𝒑t\\bm\{p\}\_\{t\}has the same marginal distribution as under𝒜\\mathcal\{A\}\.

Recall that𝒙~t\\tilde\{\\bm\{x\}\}\_\{t\}, by definition, depends only on the randomness of𝒑t−1\\bm\{p\}\_\{t\-1\}\. Therefore, as long as the perturbation marginals coincide, the induced marginal distribution of each𝒙~t\\tilde\{\\bm\{x\}\}\_\{t\}is identical under𝒜\\mathcal\{A\}andℬ\\mathcal\{B\}\. Hence,

∑t=1T𝔼𝒜\[Ft​\(𝒙~t\)−Ft​\(𝒙~t\+1\)\]=∑t=1T𝔼ℬ\[Ft​\(𝒙~t\)−Ft​\(𝒙~t\+1\)\]\.\\displaystyle\\sum\_\{t=1\}^\{T\}\\mathop\{\\mathbb\{E\}\}\_\{\\mathcal\{A\}\}\\left\[\{F\_\{t\}\(\\tilde\{\\bm\{x\}\}\_\{t\}\)\-F\_\{t\}\(\\tilde\{\\bm\{x\}\}\_\{t\+1\}\)\}\\right\]=\\sum\_\{t=1\}^\{T\}\\mathop\{\\mathbb\{E\}\}\_\{\\mathcal\{B\}\}\\left\[\{F\_\{t\}\(\\tilde\{\\bm\{x\}\}\_\{t\}\)\-F\_\{t\}\(\\tilde\{\\bm\{x\}\}\_\{t\+1\}\)\}\\right\]\.\(31\)
We now chooseℬ\\mathcal\{B\}to simplify the perturbation term in \([30](https://arxiv.org/html/2609.30556#A3.E30)\)\. Namely, letℬ\\mathcal\{B\}be the law defined by

𝒑0∼Lap⁡\(μ\),𝒑t=𝒑0∀t∈\[T−1\]\.\\displaystyle\\bm\{p\}\_\{0\}\\sim\\mathrm\{Lap\}\(\\mu\),\\qquad\\bm\{p\}\_\{t\}=\\bm\{p\}\_\{0\}\\quad\\forall t\\in\[T\{\-\}1\]\.\(32\)This law matches the single\-time marginal distribution of each𝒑t\\bm\{p\}\_\{t\}under𝒜\\mathcal\{A\}, since under𝒜\\mathcal\{A\}the perturbations𝒑t\\bm\{p\}\_\{t\}are i\.i\.d\. Laplace\.

Taking expectation of \([30](https://arxiv.org/html/2609.30556#A3.E30)\) underℬ\\mathcal\{B\}, and using \([31](https://arxiv.org/html/2609.30556#A3.E31)\), gives

\(𝐈\)\\displaystyle\\mathbf\{\(I\)\}=∑t=1T𝔼𝒜\[Ft​\(𝒙~t\)−Ft​\(𝒙~t\+1\)\]\\displaystyle=\\sum\_\{t=1\}^\{T\}\\mathop\{\\mathbb\{E\}\}\_\{\\mathcal\{A\}\}\\left\[\{F\_\{t\}\(\\tilde\{\\bm\{x\}\}\_\{t\}\)\-F\_\{t\}\(\\tilde\{\\bm\{x\}\}\_\{t\+1\}\)\}\\right\]\(33\)=∑t=1T𝔼ℬ\[Ft​\(𝒙~t\)−Ft​\(𝒙~t\+1\)\]≤G22​σ​T\+∑t=1T𝔼ℬ\[⟨𝒑t−1,𝒙~t\+1−𝒙~t⟩\]\.\\displaystyle=\\sum\_\{t=1\}^\{T\}\\mathop\{\\mathbb\{E\}\}\_\{\\mathcal\{B\}\}\\left\[\{F\_\{t\}\(\\tilde\{\\bm\{x\}\}\_\{t\}\)\-F\_\{t\}\(\\tilde\{\\bm\{x\}\}\_\{t\+1\}\)\}\\right\]\\leq\\frac\{G^\{2\}\}\{2\\sigma\}T\+\\sum\_\{t=1\}^\{T\}\\mathop\{\\mathbb\{E\}\}\_\{\\mathcal\{B\}\}\\left\[\{\\langle\{\\bm\{p\}\_\{t\-1\}\},\{\\tilde\{\\bm\{x\}\}\_\{t\+1\}\-\\tilde\{\\bm\{x\}\}\_\{t\}\}\\rangle\}\\right\]\.\(34\)
To bound the remaining sum, we rewrite it as

∑t=1T⟨𝒑t−1,𝒙~t\+1−𝒙~t⟩=⟨𝒑T−1,𝒙~T\+1⟩−⟨𝒑0,𝒙~1⟩−∑t=2T⟨𝒑t−1−𝒑t−2,𝒙~t⟩\.\\displaystyle\\sum\_\{t=1\}^\{T\}\\langle\{\\bm\{p\}\_\{t\-1\}\},\{\\tilde\{\\bm\{x\}\}\_\{t\+1\}\-\\tilde\{\\bm\{x\}\}\_\{t\}\}\\rangle=\\langle\{\\bm\{p\}\_\{T\-1\}\},\{\\tilde\{\\bm\{x\}\}\_\{T\+1\}\}\\rangle\-\\langle\{\\bm\{p\}\_\{0\}\},\{\\tilde\{\\bm\{x\}\}\_\{1\}\}\\rangle\-\\sum\_\{t=2\}^\{T\}\\langle\{\\bm\{p\}\_\{t\-1\}\-\\bm\{p\}\_\{t\-2\}\},\{\\tilde\{\\bm\{x\}\}\_\{t\}\}\\rangle\.\(35\)Underℬ\\mathcal\{B\}, we have𝒑t−1−𝒑t−2=0\\bm\{p\}\_\{t\-1\}\-\\bm\{p\}\_\{t\-2\}=0for allt≥2t\\geq 2, hence

∑t=1T𝔼ℬ\[⟨𝒑t−1,𝒙~t\+1−𝒙~t⟩\]\\displaystyle\\sum\_\{t=1\}^\{T\}\\mathop\{\\mathbb\{E\}\}\_\{\\mathcal\{B\}\}\\left\[\{\\langle\{\\bm\{p\}\_\{t\-1\}\},\{\\tilde\{\\bm\{x\}\}\_\{t\+1\}\-\\tilde\{\\bm\{x\}\}\_\{t\}\}\\rangle\}\\right\]=𝔼ℬ\[⟨𝒑0,𝒙~T\+1−𝒙~1⟩\]\.\\displaystyle=\\mathop\{\\mathbb\{E\}\}\_\{\\mathcal\{B\}\}\\left\[\{\\langle\{\\bm\{p\}\_\{0\}\},\{\\tilde\{\\bm\{x\}\}\_\{T\+1\}\-\\tilde\{\\bm\{x\}\}\_\{1\}\}\\rangle\}\\right\]\.\(36\)Therefore,

\|∑t=1T𝔼ℬ\[⟨𝒑t−1,𝒙~t\+1−𝒙~t⟩\]\|\\displaystyle\\left\|\\sum\_\{t=1\}^\{T\}\\mathop\{\\mathbb\{E\}\}\_\{\\mathcal\{B\}\}\\left\[\{\\langle\{\\bm\{p\}\_\{t\-1\}\},\{\\tilde\{\\bm\{x\}\}\_\{t\+1\}\-\\tilde\{\\bm\{x\}\}\_\{t\}\}\\rangle\}\\right\]\\right\|≤𝔼ℬ\[‖𝒑0‖​‖𝒙~T\+1−𝒙~1‖\]\\displaystyle\\leq\\mathop\{\\mathbb\{E\}\}\_\{\\mathcal\{B\}\}\\left\[\{\\\|\\bm\{p\}\_\{0\}\\\|\\,\\\|\\tilde\{\\bm\{x\}\}\_\{T\+1\}\-\\tilde\{\\bm\{x\}\}\_\{1\}\\\|\}\\right\]\(37\)≤R​𝔼\[‖𝒑0‖\]\\displaystyle\\leq R\\,\\mathop\{\\mathbb\{E\}\}\\left\[\{\\\|\\bm\{p\}\_\{0\}\\\|\}\\right\]\(38\)≤R​2​d​μ,\\displaystyle\\leq R\\sqrt\{2d\}\\,\\mu,\(39\)where the last inequality follows from the bound on the first absolute moment,

𝔼​‖𝒑0‖≤2​d​μ,\\mathbb\{E\}\\\|\\bm\{p\}\_\{0\}\\\|\\leq\\sqrt\{2d\}\\,\\mu,of add\-dimensional Laplace distribution with scale parameterμ\\mu\.

Substituting this into \([34](https://arxiv.org/html/2609.30556#A3.E34)\) completes the proof\. ∎

###### Lemma 23\.

Under the same conditions as[Lemma22](https://arxiv.org/html/2609.30556#Thmtheorem22), we have that

\(𝐈𝐈\)≤\(T​G\+σ​R\+C​Gc​T\)​PT\\displaystyle\\mathbf\{\(II\)\}\\leq\(TG\+\\sigma R\+CG\_\{c\}\\sqrt\{T\}\)\\;P\_\{T\}\(40\)

###### Proof of[Lemma23](https://arxiv.org/html/2609.30556#Thmtheorem23)\.

From strong convexity

Ft​\(𝒖t\+1γ\)−Ft​\(𝒖tγ\)≤‖𝒒t‖​‖𝒖t\+1γ−𝒖tγ‖−σ2​‖𝒖t\+1γ−𝒖tγ‖2,\\displaystyle F\_\{t\}\(\\bm\{u\}^\{\\gamma\}\_\{t\+1\}\)\-F\_\{t\}\(\\bm\{u\}^\{\\gamma\}\_\{t\}\)\\leq\\\|\\bm\{q\}\_\{t\}\\\|\\\|\\bm\{u\}^\{\\gamma\}\_\{t\+1\}\-\\bm\{u\}^\{\\gamma\}\_\{t\}\\\|\-\\frac\{\\sigma\}\{2\}\\\|\\bm\{u\}^\{\\gamma\}\_\{t\+1\}\-\\bm\{u\}^\{\\gamma\}\_\{t\}\\\|^\{2\},\(41\)where𝒒t=∇Ft​\(𝒖t\+1γ\)\\bm\{q\}\_\{t\}=\\nabla F\_\{t\}\(\\bm\{u\}^\{\\gamma\}\_\{t\+1\}\)\.

To bound‖𝒒t‖\\\|\\bm\{q\}\_\{t\}\\\|:

∇Ft​\(𝒙\)\\displaystyle\\nabla F\_\{t\}\(\\bm\{x\}\)=∇f1:t\(𝒙\)\+σ𝒙\+∇bγ\(𝒙\)\.\\displaystyle=\\nabla f\_\{1:t\}\(\\bm\{x\}\)\+\\sigma\\bm\{x\}\+\\nabla b\_\{\\gamma\}\(\\bm\{x\}\)\.\(42\)=∇f1:t\(𝒙\)\+σ𝒙−∑c=1C1Mγ​sc​\(𝒙\)∇sc\(𝒙\)\.\\displaystyle=\\nabla f\_\{1:t\}\(\\bm\{x\}\)\+\\sigma\\bm\{x\}\-\\sum\_\{c=1\}^\{C\}\\frac\{1\}\{M\_\{\\gamma\}s\_\{c\}\(\\bm\{x\}\)\}\\nabla s\_\{c\}\(\\bm\{x\}\)\.\(43\)
∙\\bulletFor‖∇bγ​\(𝒖t\+1γ\)‖\\\|\\nabla b\_\{\\gamma\}\(\\bm\{u\}\_\{t\+1\}^\{\\gamma\}\)\\\|:

By definition, any𝒚∈𝒳γ\\bm\{y\}\\in\\mathcal\{X\}^\{\\gamma\}can be written as𝒚=\(1−γ\)​𝒙\\bm\{y\}=\(1\-\\gamma\)\\bm\{x\}for some𝒙∈𝒳\\bm\{x\}\\in\\mathcal\{X\}, hence𝒚=\(1−γ\)​𝒙\+γ​𝟎\\bm\{y\}=\(1\-\\gamma\)\\bm\{x\}\+\\gamma\\bm\{0\}\. Sincescs\_\{c\}is concave,

sc​\(𝒚\)≥\(1−γ\)​sc​\(𝒙\)\+γ​sc​\(𝟎\)≥γ,s\_\{c\}\(\\bm\{y\}\)\\geq\(1\-\\gamma\)s\_\{c\}\(\\bm\{x\}\)\+\\gamma s\_\{c\}\(\\bm\{0\}\)\\geq\\gamma,where we usedsc​\(𝒙\)≥0s\_\{c\}\(\\bm\{x\}\)\\geq 0for𝒙∈𝒳\\bm\{x\}\\in\\mathcal\{X\}and the normalizationsc​\(𝟎\)=1s\_\{c\}\(\\bm\{0\}\)=1\.

The gradient of the scaled barrier is

∇bγ\(𝒙\)=−1Mγ∑c=1C1sc​\(𝒙\)∇sc\(𝒙\)\.\\nabla b\_\{\\gamma\}\(\\bm\{x\}\)=\-\\frac\{1\}\{M\_\{\\gamma\}\}\\sum\_\{c=1\}^\{C\}\\frac\{1\}\{s\_\{c\}\(\\bm\{x\}\)\}\\,\\nabla s\_\{c\}\(\\bm\{x\}\)\.Since‖∇sc​\(𝒙\)‖≤Gc\\\|\\nabla s\_\{c\}\(\\bm\{x\}\)\\\|\\leq G\_\{c\}for all vectors in the shrunk set𝒙∈𝒳γ\\bm\{x\}\\in\\mathcal\{X\}^\{\\gamma\}, then usingsc​\(𝒙\)≥γs\_\{c\}\(\\bm\{x\}\)\\geq\\gammaon𝒳γ\\mathcal\{X\}^\{\\gamma\}yields

sup𝒙∈𝒳γ‖∇bγ​\(𝒙\)‖≤1Mγ​∑c=1CGcγ=1γ​Mγ​∑c=1CGc≤C​Gcγ\.\\sup\_\{\\bm\{x\}\\in\\mathcal\{X\}^\{\\gamma\}\}\\\|\\nabla b\_\{\\gamma\}\(\\bm\{x\}\)\\\|\\leq\\frac\{1\}\{M\_\{\\gamma\}\}\\sum\_\{c=1\}^\{C\}\\frac\{G\_\{c\}\}\{\\gamma\}=\\frac\{1\}\{\\gamma M\_\{\\gamma\}\}\\sum\_\{c=1\}^\{C\}G\_\{c\}\\leq\\frac\{CG\_\{c\}\}\{\\gamma\}\.
Finally, settingγ=1/T\\gamma=1/\\sqrt\{T\}, we get‖∇bγ​\(𝒖t\+1γ\)‖≤C​Gc​T\\\|\\nabla b\_\{\\gamma\}\(\\bm\{u\}\_\{t\+1\}^\{\\gamma\}\)\\\|\\leq CG\_\{c\}\\sqrt\{T\}\.

∙\\bulletForσ​‖𝒖t\+1γ‖≤\(1−γ\)​σ​R≤σ​R\\sigma\\\|\\bm\{u\}\_\{t\+1\}^\{\\gamma\}\\\|\\leq\(1\-\\gamma\)\\sigma R\\leq\\sigma R

∙\\bulletFor∥∇f1:t\(𝒖t\+1γ\)∥\\\|\\nabla f\_\{1:t\}\(\\bm\{u\}\_\{t\+1\}^\{\\gamma\}\)\\\|, we can only do∥∇f1:t\(𝒖t\+1γ\)∥≤tG≤TG\\\|\\nabla f\_\{1:t\}\(\\bm\{u\}\_\{t\+1\}^\{\\gamma\}\)\\\|\\leq tG\\leq TG\.

Combining the three bounds gives

‖𝒒t‖≤T​G\+σ​R\+C​Gc​T\.\\\|\\bm\{q\}\_\{t\}\\\|\\leq TG\+\\sigma R\+CG\_\{c\}\\sqrt\{T\}\.Substituting this into \([41](https://arxiv.org/html/2609.30556#A3.E41)\), dropping the negative quadratic term, and summing overt=1,…,T−1t=1,\\dots,T\-1, we obtain

\(𝐈𝐈\)≤\(T​G\+σ​R\+C​Gc​T\)​∑t=1T−1‖𝒖t\+1γ−𝒖tγ‖\.\\mathbf\{\(II\)\}\\leq\(TG\+\\sigma R\+CG\_\{c\}\\sqrt\{T\}\)\\sum\_\{t=1\}^\{T\-1\}\\\|\\bm\{u\}\_\{t\+1\}^\{\\gamma\}\-\\bm\{u\}\_\{t\}^\{\\gamma\}\\\|\.Since∑t=1T−1‖𝒖t\+1γ−𝒖tγ‖≤PT\\sum\_\{t=1\}^\{T\-1\}\\\|\\bm\{u\}\_\{t\+1\}^\{\\gamma\}\-\\bm\{u\}\_\{t\}^\{\\gamma\}\\\|\\leq P\_\{T\}, the result follows\. ∎

###### Lemma 24\.

Suppose the loss sequence\{ft\}\\\{f\_\{t\}\\\}consists of convex,GG\-Lipschitz, andβ\\beta\-smooth functions\. Then, the total variation distance between𝒬t\\mathcal\{Q\}\_\{t\}and𝒬t\+1\\mathcal\{Q\}\_\{t\+1\}is bounded by

‖𝒬t\+1−𝒬t‖T​V≤β​dσ\+d​Gμ\.\\\|\\mathcal\{Q\}\_\{t\+1\}\-\\mathcal\{Q\}\_\{t\}\\\|\_\{TV\}\\leq\\frac\{\\beta d\}\{\\sigma\}\+\\frac\{\\sqrt\{d\}\\,G\}\{\\mu\}\.

###### Proof of[Lemma24](https://arxiv.org/html/2609.30556#Thmtheorem24)\.

By the change of variables formula, the density ratio satisfies

𝒬t\+1​\(𝒙\)𝒬t​\(𝒙\)=ν​\(−∇Ft​\(𝒙\)\)ν​\(−∇Ft−1​\(𝒙\)\)⋅\|det\(−∇2Ft​\(𝒙\)\)det\(−∇2Ft−1​\(𝒙\)\)\|\\frac\{\\mathcal\{Q\}\_\{t\+1\}\(\\bm\{x\}\)\}\{\\mathcal\{Q\}\_\{t\}\(\\bm\{x\}\)\}=\\frac\{\\nu\(\-\\nabla F\_\{t\}\(\\bm\{x\}\)\)\}\{\\nu\(\-\\nabla F\_\{t\-1\}\(\\bm\{x\}\)\)\}\\cdot\\Big\|\\frac\{\\det\(\-\\nabla^\{2\}F\_\{t\}\(\\bm\{x\}\)\)\}\{\\det\(\-\\nabla^\{2\}F\_\{t\-1\}\(\\bm\{x\}\)\)\}\\Big\|
We bound each component separately\.

Determinant ratio\.Letλi,t\\lambda\_\{i,t\}denote theii\-th largest eigenvalue of the symmetric matrix∇2Ft​\(𝒙\)\\nabla^\{2\}F\_\{t\}\(\\bm\{x\}\)\. Because the newly revealed loss functionftf\_\{t\}isβ\\beta\-smooth, the spectral norm \(operator norm\) of its Hessian is bounded byβ\\beta\. By applying Weyl’s inequality, which bounds the change in eigenvalues by the spectral norm of the difference, we obtain

\|λi,t−λi,t−1\|≤‖∇2Ft​\(𝒙\)−∇2Ft−1​\(𝒙\)‖op=‖∇2ft​\(𝒙\)‖op≤β\|\\lambda\_\{i,t\}\-\\lambda\_\{i,t\-1\}\|\\leq\\\|\\nabla^\{2\}F\_\{t\}\(\\bm\{x\}\)\-\\nabla^\{2\}F\_\{t\-1\}\(\\bm\{x\}\)\\\|\_\{\\mathrm\{op\}\}=\\\|\\nabla^\{2\}f\_\{t\}\(\\bm\{x\}\)\\\|\_\{\\mathrm\{op\}\}\\leq\\beta
Furthermore, sinceFtF\_\{t\}is alsoσ\\sigma\-strongly convex, all eigenvalues satisfyλi,t≥σ\>0,∀t\\lambda\_\{i,t\}\\geq\\sigma\>0,\\forall t\. Therefore,

det\(∇2Ft​\(𝒙\)\)det\(∇2Ft−1​\(𝒙\)\)≤∏i=1d\(λi,t−1\+βλi,t−1\)≤∏i=1d\(1\+βσ\)=\(1\+βσ\)d≤exp⁡\(β​dσ\)\.\\frac\{\\det\(\\nabla^\{2\}F\_\{t\}\(\\bm\{x\}\)\)\}\{\\det\(\\nabla^\{2\}F\_\{t\-1\}\(\\bm\{x\}\)\)\}\\leq\\prod\_\{i=1\}^\{d\}\\left\(\\frac\{\\lambda\_\{i,t\-1\}\+\\beta\}\{\\lambda\_\{i,t\-1\}\}\\right\)\\leq\\prod\_\{i=1\}^\{d\}\\left\(1\+\\frac\{\\beta\}\{\\sigma\}\\right\)=\\left\(1\+\\frac\{\\beta\}\{\\sigma\}\\right\)^\{d\}\\leq\\exp\\left\(\\frac\{\\beta d\}\{\\sigma\}\\right\)\.
Density ratio\.Using theL1L\_\{1\}structure of the Laplace distribution and the reverse triangle inequality,

ν​\(−∇Ft​\(𝒙\)\)ν​\(−∇Ft−1​\(𝒙\)\)=exp⁡\(‖∇Ft−1​\(𝒙\)‖1−‖∇Ft​\(𝒙\)‖1μ\)≤exp⁡\(‖∇Ft−1​\(𝒙\)−∇Ft​\(𝒙\)‖1μ\)=exp⁡\(‖∇ft​\(𝒙\)‖1μ\)\.\\frac\{\\nu\(\-\\nabla F\_\{t\}\(\\bm\{x\}\)\)\}\{\\nu\(\-\\nabla F\_\{t\-1\}\(\\bm\{x\}\)\)\}=\\exp\\left\(\\frac\{\\\|\\nabla F\_\{t\-1\}\(\\bm\{x\}\)\\\|\_\{1\}\-\\\|\\nabla F\_\{t\}\(\\bm\{x\}\)\\\|\_\{1\}\}\{\\mu\}\\right\)\\leq\\exp\\left\(\\frac\{\\\|\\nabla F\_\{t\-1\}\(\\bm\{x\}\)\-\\nabla F\_\{t\}\(\\bm\{x\}\)\\\|\_\{1\}\}\{\\mu\}\\right\)=\\exp\\left\(\\frac\{\\\|\\nabla f\_\{t\}\(\\bm\{x\}\)\\\|\_\{1\}\}\{\\mu\}\\right\)\.
Sinceftf\_\{t\}isGG\-Lipschitz,

‖∇ft​\(𝒙\)‖1≤d​‖∇ft​\(𝒙\)‖2≤d​G\.\\\|\\nabla f\_\{t\}\(\\bm\{x\}\)\\\|\_\{1\}\\leq\\sqrt\{d\}\\,\\\|\\nabla f\_\{t\}\(\\bm\{x\}\)\\\|\_\{2\}\\leq\\sqrt\{d\}\\,G\.Thus,

ν​\(−∇Ft​\(𝒙\)\)ν​\(−∇Ft−1​\(𝒙\)\)≤exp⁡\(d​Gμ\)\.\\frac\{\\nu\(\-\\nabla F\_\{t\}\(\\bm\{x\}\)\)\}\{\\nu\(\-\\nabla F\_\{t\-1\}\(\\bm\{x\}\)\)\}\\leq\\exp\\left\(\\frac\{\\sqrt\{d\}\\,G\}\{\\mu\}\\right\)\.
Combining both bounds,

𝒬t\+1​\(𝒙\)𝒬t​\(𝒙\)≤exp⁡\(β​dσ\+d​Gμ\)=exp⁡\(ϵ\),\\frac\{\\mathcal\{Q\}\_\{t\+1\}\(\\bm\{x\}\)\}\{\\mathcal\{Q\}\_\{t\}\(\\bm\{x\}\)\}\\leq\\exp\\left\(\\frac\{\\beta d\}\{\\sigma\}\+\\frac\{\\sqrt\{d\}\\,G\}\{\\mu\}\\right\)=\\exp\(\\epsilon\),where

ϵ≐β​dσ\+d​Gμ\.\\epsilon\\doteq\\frac\{\\beta d\}\{\\sigma\}\+\\frac\{\\sqrt\{d\}\\,G\}\{\\mu\}\.
Taking reciprocals gives

𝒬t​\(𝒙\)𝒬t\+1​\(𝒙\)≥exp⁡\(−ϵ\),\\frac\{\\mathcal\{Q\}\_\{t\}\(\\bm\{x\}\)\}\{\\mathcal\{Q\}\_\{t\+1\}\(\\bm\{x\}\)\}\\geq\\exp\(\-\\epsilon\),which implies

𝒬t\+1​\(𝒙\)−𝒬t​\(𝒙\)≤\(1−e−ϵ\)​𝒬t\+1​\(𝒙\)\.\\mathcal\{Q\}\_\{t\+1\}\(\\bm\{x\}\)\-\\mathcal\{Q\}\_\{t\}\(\\bm\{x\}\)\\leq\(1\-e^\{\-\\epsilon\}\)\\,\\mathcal\{Q\}\_\{t\+1\}\(\\bm\{x\}\)\.Integrating over any measurable setEEyields

𝒬t\+1​\(E\)−𝒬t​\(E\)≤1−e−ϵ≤ϵ\.\\mathcal\{Q\}\_\{t\+1\}\(E\)\-\\mathcal\{Q\}\_\{t\}\(E\)\\leq 1\-e^\{\-\\epsilon\}\\leq\\epsilon\.
To also get𝒬t​\(E\)−𝒬t\+1​\(E\)≤ϵ\\mathcal\{Q\}\_\{t\}\(E\)\-\\mathcal\{Q\}\_\{t\+1\}\(E\)\\leq\\epsilonwe start the proof again but with the reciprocal bound𝒬t​\(𝒙\)/𝒬t\+1​\(𝒙\)\\mathcal\{Q\}\_\{t\}\(\\bm\{x\}\)/\\mathcal\{Q\}\_\{t\+1\}\(\\bm\{x\}\), and using\|λi,t−λi,t−1\|≤β\|\\lambda\_\{i,t\}\-\\lambda\_\{i,t\-1\}\|\\leq\\beta, we get

det\(∇2Ft−1​\(𝒙\)\)det\(∇2Ft​\(𝒙\)\)≤∏i=1d\(λi,t\+βλi,t\)≤exp⁡\(β​dσ\)\.\\frac\{\\det\(\\nabla^\{2\}F\_\{t\-1\}\(\\bm\{x\}\)\)\}\{\\det\(\\nabla^\{2\}F\_\{t\}\(\\bm\{x\}\)\)\}\\leq\\prod\_\{i=1\}^\{d\}\\left\(\\frac\{\\lambda\_\{i,t\}\+\\beta\}\{\\lambda\_\{i,t\}\}\\right\)\\leq\\exp\\left\(\\frac\{\\beta d\}\{\\sigma\}\\right\)\.The remaining proof steps are the same thereafter, and we get the same boundϵ\\epsilon\. Hence, we have

‖𝒬t\+1−𝒬t‖T​V≤ϵ\.\\\|\\mathcal\{Q\}\_\{t\+1\}\-\\mathcal\{Q\}\_\{t\}\\\|\_\{TV\}\\leq\\epsilon\.∎

Now we are ready to prove the main theorem\.

###### Proof of[Theorem5](https://arxiv.org/html/2609.30556#Thmtheorem5)\.

By linearity of expectation,

𝔼\[ℛT𝟏\]=𝔼\[ℛT\]\+λ∑t=2T𝔼\[𝟏\{𝒙t≠𝒙t−1\}\]\.\\mathop\{\\mathbb\{E\}\}\\left\[\{\\mathcal\{R\}^\{\\mathbf\{1\}\}\_\{T\}\}\\right\]=\\mathop\{\\mathbb\{E\}\}\\left\[\{\\mathcal\{R\}\_\{T\}\}\\right\]\+\\lambda\\sum\_\{t=2\}^\{T\}\\mathop\{\\mathbb\{E\}\}\\left\[\{\\mathbf\{1\}\\\{\\bm\{x\}\_\{t\}\\neq\\bm\{x\}\_\{t\-1\}\\\}\}\\right\]\.The bound on𝔼\[ℛT\]\\mathop\{\\mathbb\{E\}\}\\left\[\{\\mathcal\{R\}\_\{T\}\}\\right\]follows by combining[Lemma22](https://arxiv.org/html/2609.30556#Thmtheorem22)and[Lemma23](https://arxiv.org/html/2609.30556#Thmtheorem23)\. For the second term, the lazy sampling procedure implies

𝔼\[𝟏\{𝒙t≠𝒙t−1\}\]=Pr\(𝒙t≠𝒙t−1\)=∥𝒬t−𝒬t−1∥TV\.\\mathop\{\\mathbb\{E\}\}\\left\[\{\\mathbf\{1\}\\\{\\bm\{x\}\_\{t\}\\neq\\bm\{x\}\_\{t\-1\}\\\}\}\\right\]=\\Pr\(\\bm\{x\}\_\{t\}\\neq\\bm\{x\}\_\{t\-1\}\)=\\\|\\mathcal\{Q\}\_\{t\}\-\\mathcal\{Q\}\_\{t\-1\}\\\|\_\{\\mathrm\{TV\}\}\.Applying the bound on‖𝒬t−𝒬t−1‖TV\\\|\\mathcal\{Q\}\_\{t\}\-\\mathcal\{Q\}\_\{t\-1\}\\\|\_\{\\mathrm\{TV\}\}from[Lemma24](https://arxiv.org/html/2609.30556#Thmtheorem24)yields the claimed result\. ∎

### C\.1Proof of[Theorem7](https://arxiv.org/html/2609.30556#Thmtheorem7)

###### Proof\.

Fix any dyadic scalek∈ℋk\\in\\mathcal\{H\}, and partition the horizon intom=T/km=T/kconsecutive blocks

Bi=\{\(i−1\)k\+1,…,ik\},i=1,…,m\.B\_\{i\}=\\\{\(i\-1\)k\+1,\\dots,ik\\\},\\qquad i=1,\\dots,m\.For each block, define the within\-block path budget

Pi≐∑t=\(i−1\)​k\+2i​k‖𝒖t−𝒖t−1‖\.P\_\{i\}\\doteq\\sum\_\{t=\(i\-1\)k\+2\}^\{ik\}\\\|\\bm\{u\}\_\{t\}\-\\bm\{u\}\_\{t\-1\}\\\|\.Applying Theorem[5](https://arxiv.org/html/2609.30556#Thmtheorem5)on each block with horizonkkand the given choices of\(γ,μ,σ\)\(\\gamma,\\mu,\\sigma\), we obtain

𝔼\[ℛT𝟏​\(\{𝒖t\}t=1T\)\]≤∑i=1m\[\(R\+Pi\)​\(G2\+2​λ​β​d\)​k\+25/4​λ​d​R​G​k\+G​k​Pi\+\(C​Gc​Pi\+G​R\)​k\+1\]\+λ⁡\(m−1\),\\mathop\{\\mathbb\{E\}\}\\left\[\{\\mathcal\{R\}^\{\\mathbf\{1\}\}\_\{T\}\(\\\{\\bm\{u\}\_\{t\}\\\}\_\{t=1\}^\{T\}\)\}\\right\]\\leq\\sum\_\{i=1\}^\{m\}\\left\[\(R\+P\_\{i\}\)\\sqrt\{\(G^\{2\}\+2\\lambda\\beta d\)\\,k\}\+2^\{5/4\}\\sqrt\{\\lambda dRG\\,k\}\+GkP\_\{i\}\+\\bigl\(CG\_\{c\}P\_\{i\}\+GR\\bigr\)\\sqrt\{k\}\+1\\right\]\+\\lambda\(m\-1\),where theλ⁡\(m−1\)\\lambda\(m\-1\)term comes from the switching cost at the restart boundaries\. Since25/4<32^\{5/4\}<3,∑i=1mPi≤PT\\sum\_\{i=1\}^\{m\}P\_\{i\}\\leq P\_\{T\}, andm=T/km=T/k, this implies

𝔼\[ℛT𝟏​\(\{𝒖t\}t=1T\)\]≤A​Tk\+B​PT​k\+G​PT​k\.\\mathop\{\\mathbb\{E\}\}\\left\[\{\\mathcal\{R\}^\{\\mathbf\{1\}\}\_\{T\}\(\\\{\\bm\{u\}\_\{t\}\\\}\_\{t=1\}^\{T\}\)\}\\right\]\\leq A\\,\\frac\{T\}\{\\sqrt\{k\}\}\+B\\,P\_\{T\}\\sqrt\{k\}\+GP\_\{T\}k\.Becausek≥1k\\geq 1, we havek≤k\\sqrt\{k\}\\leq k, and therefore

𝔼\[ℛT𝟏​\(\{𝒖t\}t=1T\)\]≤ϕ⁡\(k\)≐A​Tk\+\(B\+G\)​PT​k\.\\mathop\{\\mathbb\{E\}\}\\left\[\{\\mathcal\{R\}^\{\\mathbf\{1\}\}\_\{T\}\(\\\{\\bm\{u\}\_\{t\}\\\}\_\{t=1\}^\{T\}\)\}\\right\]\\leq\\phi\(k\)\\doteq A\\,\\frac\{T\}\{\\sqrt\{k\}\}\+\(B\+G\)P\_\{T\}\\,k\.
We now optimizeϕ\\phioverk\>0k\>0\. Differentiating gives

ϕ′\(k\)=−12ATk−3/2\+\(B\+G\)PT,\\phi^\{\\prime\}\(k\)=\-\\frac\{1\}\{2\}AT\\,k^\{\-3/2\}\+\(B\+G\)P\_\{T\},so the unique stationary point is

k¯=\(A​T2​\(B\+G\)​PT\)2/3\.\\bar\{k\}=\\left\(\\frac\{AT\}\{2\(B\+G\)P\_\{T\}\}\\right\)^\{2/3\}\.After clipping to the admissible range\[1,T\]\[1,T\], define

k⋆≐min⁡\{T,max⁡\{1,k¯\}\}\.k^\{\\star\}\\doteq\\min\\\{T,\\max\\\{1,\\bar\{k\}\\\}\\\}\.Sinceℋ\\mathcal\{H\}is dyadic, there exists

k†≐2⌊log2⁡k⋆⌋∈ℋk^\{\\dagger\}\\doteq 2^\{\\lfloor\\log\_\{2\}k^\{\\star\}\\rfloor\}\\in\\mathcal\{H\}such that

k⋆2≤k†≤k⋆\.\\frac\{k^\{\\star\}\}\{2\}\\leq k^\{\\dagger\}\\leq k^\{\\star\}\.Hence

ϕ⁡\(k†\)≤2​A​Tk⋆\+\(B\+G\)​PT​k⋆,\\phi\(k^\{\\dagger\}\)\\leq\\sqrt\{2\}\\,A\\,\\frac\{T\}\{\\sqrt\{k^\{\\star\}\}\}\+\(B\+G\)P\_\{T\}\\,k^\{\\star\},which proves the first claim\.

It remains to simplify the three regimes\. If1≤k¯≤T1\\leq\\bar\{k\}\\leq T, thenk⋆=k¯k^\{\\star\}=\\bar\{k\}, and substitutingk¯\\bar\{k\}into the display above yields

𝔼\[ℛT𝟏​\(\{𝒖t\}t=1T\)\]=𝒪⁡\(A2/3​\(B\+G\)1/3​T2/3​PT1/3\)\.\\mathop\{\\mathbb\{E\}\}\\left\[\{\\mathcal\{R\}^\{\\mathbf\{1\}\}\_\{T\}\(\\\{\\bm\{u\}\_\{t\}\\\}\_\{t=1\}^\{T\}\)\}\\right\]=\\mathcal\{O\}\\left\(A^\{2/3\}\(B\+G\)^\{1/3\}T^\{2/3\}P\_\{T\}^\{1/3\}\\right\)\.Ifk¯<1\\bar\{k\}<1, thenA​T<2​\(B\+G\)​PTAT<2\(B\+G\)P\_\{T\}, sok⋆=1k^\{\\star\}=1and

𝔼\[ℛT𝟏​\(\{𝒖t\}t=1T\)\]≤2​A​T\+\(B\+G\)​PT=𝒪⁡\(\(B\+G\)​PT\)\.\\mathop\{\\mathbb\{E\}\}\\left\[\{\\mathcal\{R\}^\{\\mathbf\{1\}\}\_\{T\}\(\\\{\\bm\{u\}\_\{t\}\\\}\_\{t=1\}^\{T\}\)\}\\right\]\\leq\\sqrt\{2\}AT\+\(B\+G\)P\_\{T\}=\\mathcal\{O\}\\left\(\(B\+G\)P\_\{T\}\\right\)\.Ifk¯\>T\\bar\{k\}\>T, thenA​T\>2​\(B\+G\)​PT​T3/2AT\>2\(B\+G\)P\_\{T\}T^\{3/2\}, sok⋆=Tk^\{\\star\}=Tand

\(B\+G\)​PT​T≤A2​T\.\(B\+G\)P\_\{T\}T\\leq\\frac\{A\}\{2\}\\sqrt\{T\}\.Therefore,

𝔼\[ℛT𝟏\(u1:T\)\]≤2AT\+\(B\+G\)PTT=𝒪\(AT\)\.\\mathbb\{E\}\\left\[\\mathcal\{R\}\_\{T\}^\{\\mathbf\{1\}\}\(u\_\{1:T\}\)\\right\]\\leq\\sqrt\{2\}A\\sqrt\{T\}\+\(B\+G\)P\_\{T\}T=\\mathcal\{O\}\\left\(A\\sqrt\{T\}\\right\)\.
Finally, ifPT=TαP\_\{T\}=T^\{\\alpha\}withα∈\[0,1\]\\alpha\\in\[0,1\], then

PT=Tα≤T\(2\+α\)/3andT≤T\(2\+α\)/3,P\_\{T\}=T^\{\\alpha\}\\leq T^\{\(2\+\\alpha\)/3\}\\qquad\\text\{and\}\\qquad\\sqrt\{T\}\\leq T^\{\(2\+\\alpha\)/3\},so both boundary branches are dominated by the interior rate

T\(2\+α\)/3=T2/3​PT1/3\.T^\{\(2\+\\alpha\)/3\}=T^\{2/3\}P\_\{T\}^\{1/3\}\.This proves the final claim\. ∎

## Appendix DDyadic intervals

### D\.1Proof of[Lemma9](https://arxiv.org/html/2609.30556#Thmtheorem9)

To prove the given expression, we need the following geometric covering fact about intervals:

###### Lemma 25\.

[Orabona \[17, Thm\. 15\.9\]](https://arxiv.org/html/2609.30556#bib.bib1)LetJ=\[q,r\]⊆ℕJ=\[q,r\]\\subseteq\\mathbb\{N\}be an arbitrary interval\. ThenJJcan be partitioned into two finite sequences of disjoint and consecutive intervals,

\(J−k,…,J0\)⊆ℐ\|J,\(J1,…,Jp\)⊆ℐ\|J,\(J\_\{\-k\},\\dots,J\_\{0\}\)\\subseteq\\mathcal\{I\}\|\_\{J\},\\qquad\(J\_\{1\},\\dots,J\_\{p\}\)\\subseteq\\mathcal\{I\}\|\_\{J\},such that

1. 1\.the intervalsJ−k,…,J0,J1,…,JpJ\_\{\-k\},\\dots,J\_\{0\},J\_\{1\},\\dots,J\_\{p\}are consecutive and their union isJJ;
2. 2\.\|J−i\|/\|J−i\+1\|≤1/2\|J\_\{\-i\}\|/\|J\_\{\-i\+1\}\|\\leq 1/2for everyi≥1i\\geq 1;
3. 3\.\|Ji\|/\|Ji−1\|≤1/2\|J\_\{i\}\|/\|J\_\{i\-1\}\|\\leq 1/2for everyi≥2i\\geq 2\.

###### Proof\.

Apply[Lemma25](https://arxiv.org/html/2609.30556#Thmtheorem25)toI=\[s,e\]I=\[s,e\]\. We obtain two sequences

\(J−k,…,J0\)⊆ℐ\|I,\(J1,…,Jp\)⊆ℐ\|I,\(J\_\{\-k\},\\dots,J\_\{0\}\)\\subseteq\\mathcal\{I\}\|\_\{I\},\\qquad\(J\_\{1\},\\dots,J\_\{p\}\)\\subseteq\\mathcal\{I\}\|\_\{I\},whose union isII\. Relabeling from left to right gives a partitionJ1,…,Jm∈𝒢J\_\{1\},\\dots,J\_\{m\}\\in\\mathcal\{G\}, wherem=k\+p\+1m=k\+p\+1\.

Since every interval inℐ\\mathcal\{I\}has dyadic length, and the ratios in[Lemma25](https://arxiv.org/html/2609.30556#Thmtheorem25)are at most1/21/2, the block lengths on each side lie on distinct dyadic scales\. As every block has length at mostLL, each side contains at most⌈log2⁡L⌉\+1\\lceil\\log\_\{2\}L\\rceil\+1blocks\. Therefore

m≤2​⌈log2⁡L⌉\+2,m\\leq 2\\lceil\\log\_\{2\}L\\rceil\+2,
It remains to bound the sum of square roots\. For the left side, write

ai≐\|J−i\|,i=0,…,k,a\_\{i\}\\doteq\|J\_\{\-i\}\|,\\qquad i=0,\\dots,k,and define the tail sums

Si≐∑j=ikaj,i=0,…,k,Sk\+1≐0\.S\_\{i\}\\doteq\\sum\_\{j=i\}^\{k\}a\_\{j\},\\qquad i=0,\\dots,k,\\qquad S\_\{k\+1\}\\doteq 0\.Because the lengths decrease geometrically,

Si\+1≤∑r≥1ai2r≤ai\.S\_\{i\+1\}\\leq\\sum\_\{r\\geq 1\}\\frac\{a\_\{i\}\}\{2^\{r\}\}\\leq a\_\{i\}\.Hence

Si=ai\+Si\+1≤2​aiS\_\{i\}=a\_\{i\}\+S\_\{i\+1\}\\leq 2a\_\{i\}Therefore

Si\+Si\+1≤\(2\+1\)​ai,\\sqrt\{S\_\{i\}\}\+\\sqrt\{S\_\{i\+1\}\}\\leq\(\\sqrt\{2\}\+1\)\\sqrt\{a\_\{i\}\},Multiplying both sides by\(Si−Si\+1\)/ai\(\\sqrt\{S\_\{i\}\}\-\\sqrt\{S\_\{i\+1\}\}\)/\\sqrt\{a\_\{i\}\}allows us to boundai\\sqrt\{a\_\{i\}\}as follows:

ai≤\(1\+2\)​\(Si−Si\+1\)\.\\sqrt\{a\_\{i\}\}\\leq\(1\+\\sqrt\{2\}\)\\bigl\(\\sqrt\{S\_\{i\}\}\-\\sqrt\{S\_\{i\+1\}\}\\bigr\)\.Summing overi=0,…,ki=0,\\dots,kyields

∑i=0k\|J−i\|≤\(1\+2\)​∑i=0k\(Si−Si\+1\)=\(1\+2\)​S0\.\\sum\_\{i=0\}^\{k\}\\sqrt\{\|J\_\{\-i\}\|\}\\leq\(1\+\\sqrt\{2\}\)\\sum\_\{i=0\}^\{k\}\\bigl\(\\sqrt\{S\_\{i\}\}\-\\sqrt\{S\_\{i\+1\}\}\\bigr\)=\(1\+\\sqrt\{2\}\)\\sqrt\{S\_\{0\}\}\.If we set

A≐∑i=0k\|J−i\|,B≐∑i=1p\|Ji\|,A\\doteq\\sum\_\{i=0\}^\{k\}\|J\_\{\-i\}\|,\\qquad B\\doteq\\sum\_\{i=1\}^\{p\}\|J\_\{i\}\|,thenS0=AS\_\{0\}=A, and the same argument on the right side gives

∑i=1p\|Ji\|≤\(1\+2\)​B\.\\sum\_\{i=1\}^\{p\}\\sqrt\{\|J\_\{i\}\|\}\\leq\(1\+\\sqrt\{2\}\)\\sqrt\{B\}\.SinceA\+B=LA\+B=L, we conclude

∑r=1m\|Jr\|≤\(1\+2\)​\(A\+B\)≤\(1\+2\)​2​\(A\+B\)=\(2\+2\)​L\.\\sum\_\{r=1\}^\{m\}\\sqrt\{\|J\_\{r\}\|\}\\leq\(1\+\\sqrt\{2\}\)\(\\sqrt\{A\}\+\\sqrt\{B\}\)\\leq\(1\+\\sqrt\{2\}\)\\sqrt\{2\(A\+B\)\}=\(2\+\\sqrt\{2\}\)\\sqrt\{L\}\.∎

## Appendix EProofs for meta\-learner

### E\.1Proof for the one step

###### Proof of[Lemma10](https://arxiv.org/html/2609.30556#Thmtheorem10)\.

Write

𝒫t−𝒫t−1=∑H∈ℋvt,H​\(𝒬t\(H\)−𝒬t−1\(H\)\)\+∑H∈ℋ\(vt,H−vt−1,H\)​𝒬t−1\(H\)\.\\mathcal\{P\}\_\{t\}\-\\mathcal\{P\}\_\{t\-1\}=\\sum\_\{H\\in\\mathcal\{H\}\}v\_\{t,H\}\\bigl\(\\mathcal\{Q\}\_\{t\}^\{\(H\)\}\-\\mathcal\{Q\}\_\{t\-1\}^\{\(H\)\}\\bigr\)\+\\sum\_\{H\\in\\mathcal\{H\}\}\(v\_\{t,H\}\-v\_\{t\-1,H\}\)\\,\\mathcal\{Q\}\_\{t\-1\}^\{\(H\)\}\.Taking total variation and using the triangle inequality yields

‖𝒫t−𝒫t−1‖TV≤∑H∈ℋvt,H​‖𝒬t\(H\)−𝒬t−1\(H\)‖TV\+‖∑H∈ℋ\(vt,H−vt−1,H\)​𝒬t−1\(H\)‖TV\.\\left\\lVert\\mathcal\{P\}\_\{t\}\-\\mathcal\{P\}\_\{t\-1\}\\right\\rVert\_\{\\mathrm\{TV\}\}\\leq\\sum\_\{H\\in\\mathcal\{H\}\}v\_\{t,H\}\\left\\lVert\\mathcal\{Q\}\_\{t\}^\{\(H\)\}\-\\mathcal\{Q\}\_\{t\-1\}^\{\(H\)\}\\right\\rVert\_\{\\mathrm\{TV\}\}\+\\left\\lVert\\sum\_\{H\\in\\mathcal\{H\}\}\(v\_\{t,H\}\-v\_\{t\-1,H\}\)\\mathcal\{Q\}\_\{t\-1\}^\{\(H\)\}\\right\\rVert\_\{\\mathrm\{TV\}\}\.The first term is exactly

∑H∈ℋvt,H​ct\(H\)\.\\sum\_\{H\\in\\mathcal\{H\}\}v\_\{t,H\}\\,c\_\{t\}^\{\(H\)\}\.
For the second term, set

aH≐vt,H−vt−1,H,A\+≐\{H∈ℋ:aH\>0\},A−≐\{H∈ℋ:aH<0\}\.a\_\{H\}\\doteq v\_\{t,H\}\-v\_\{t\-1,H\},\\qquad A\_\{\+\}\\doteq\\\{H\\in\\mathcal\{H\}:a\_\{H\}\>0\\\},\\qquad A\_\{\-\}\\doteq\\\{H\\in\\mathcal\{H\}:a\_\{H\}<0\\\}\.Since both𝒗t\\bm\{v\}\_\{t\}and𝒗t−1\\bm\{v\}\_\{t\-1\}lie in the simplex,∑H∈ℋaH=0\\sum\_\{H\\in\\mathcal\{H\}\}a\_\{H\}=0\. Hence

α≐∑H∈A\+aH=−∑H∈A−aH=12∥𝒗t−𝒗t−1∥1\.\\alpha\\doteq\\sum\_\{H\\in A\_\{\+\}\}a\_\{H\}=\-\\sum\_\{H\\in A\_\{\-\}\}a\_\{H\}=\\frac\{1\}\{2\}\\\|\\bm\{v\}\_\{t\}\-\\bm\{v\}\_\{t\-1\}\\\|\_\{1\}\.Ifα=0\\alpha=0, there is nothing to prove\. Otherwise,

∑H∈ℋaH​𝒬t−1\(H\)=α⁡\(μ\+−μ−\),\\sum\_\{H\\in\\mathcal\{H\}\}a\_\{H\}\\mathcal\{Q\}\_\{t\-1\}^\{\(H\)\}=\\alpha\(\\mu\_\{\+\}\-\\mu\_\{\-\}\),where

μ\+≐∑H∈A\+aHα​𝒬t−1\(H\),μ−≐∑H∈A−−aHα​𝒬t−1\(H\)\\mu\_\{\+\}\\doteq\\sum\_\{H\\in A\_\{\+\}\}\\frac\{a\_\{H\}\}\{\\alpha\}\\,\\mathcal\{Q\}\_\{t\-1\}^\{\(H\)\},\\qquad\\mu\_\{\-\}\\doteq\\sum\_\{H\\in A\_\{\-\}\}\\frac\{\-a\_\{H\}\}\{\\alpha\}\\,\\mathcal\{Q\}\_\{t\-1\}^\{\(H\)\}are probability distributions \(convex combination of probability distributions\)\. Therefore,

‖∑H∈ℋaH​𝒬t−1\(H\)‖TV=α​‖μ\+−μ−‖TV≤α=12​‖𝒗t−𝒗t−1‖1\.\\left\\lVert\\sum\_\{H\\in\\mathcal\{H\}\}a\_\{H\}\\mathcal\{Q\}\_\{t\-1\}^\{\(H\)\}\\right\\rVert\_\{\\mathrm\{TV\}\}=\\alpha\\,\\left\\lVert\\mu\_\{\+\}\-\\mu\_\{\-\}\\right\\rVert\_\{\\mathrm\{TV\}\}\\leq\\alpha=\\frac\{1\}\{2\}\\\|\\bm\{v\}\_\{t\}\-\\bm\{v\}\_\{t\-1\}\\\|\_\{1\}\.This proves[Eq\.9](https://arxiv.org/html/2609.30556#S3.E9)\.

To pass from the meta dot product to the master expectation, define

ℓt≐\(ℓt\(H\)\)H∈ℋ,𝒄t≐\(ct\(H\)\)H∈ℋ,𝒈t=ℓt\+λ​𝒄t\.\\bm\{\\ell\}\_\{t\}\\doteq\\bigl\(\\ell\_\{t\}^\{\(H\)\}\\bigr\)\_\{H\\in\\mathcal\{H\}\}\\;,\\qquad\\bm\{c\}\_\{t\}\\doteq\\bigl\(c\_\{t\}^\{\(H\)\}\\bigr\)\_\{H\\in\\mathcal\{H\}\}\\;,\\qquad\\bm\{g\}\_\{t\}=\\bm\{\\ell\}\_\{t\}\+\\lambda\\bm\{c\}\_\{t\}\.By the lazy sampling properties \([Eq\.17](https://arxiv.org/html/2609.30556#A1.E17)\), we have𝒙t∼𝒫t\\bm\{x\}\_\{t\}\\sim\\mathcal\{P\}\_\{t\}\. Also, using linearity of integration gives:

⟨𝒗t,ℓt⟩\\displaystyle\\left\\langle\\bm\{v\}\_\{t\},\\bm\{\\ell\}\_\{t\}\\right\\rangle=∑H∈ℋvt,H​ℓt\(H\)=\(LOTUS\)∑H∈ℋvt,H​∫𝒳ft​\(𝒙\)​d​𝒬t\(H\)​\(𝒙\)=∫𝒳ft​\(𝒙\)​d​\(∑H∈ℋvt,H​𝒬t\(H\)\)​\(𝒙\)\\displaystyle=\\sum\_\{H\\in\\mathcal\{H\}\}v\_\{t,H\}\\,\\ell\_\{t\}^\{\(H\)\}\\stackrel\{\{\\scriptstyle\(\\text\{LOTUS\}\)\}\}\{\{=\}\}\\sum\_\{H\\in\\mathcal\{H\}\}v\_\{t,H\}\\int\_\{\\mathcal\{X\}\}f\_\{t\}\(\\bm\{x\}\)\\,d\\mathcal\{Q\}\_\{t\}^\{\(H\)\}\(\\bm\{x\}\)=\\int\_\{\\mathcal\{X\}\}f\_\{t\}\(\\bm\{x\}\)\\,d\\Bigl\(\\sum\_\{H\\in\\mathcal\{H\}\}v\_\{t,H\}\\mathcal\{Q\}\_\{t\}^\{\(H\)\}\\Bigr\)\(\\bm\{x\}\)\(44\)=[Eq\.2](https://arxiv.org/html/2609.30556#S1.E2)∫𝒳ft​\(𝒙\)​d​𝒫t​\(𝒙\)=\(LOTUS\)𝔼𝒙t∼𝒫t\[ft​\(𝒙t\)\]\\displaystyle\\stackrel\{\{\\scriptstyle\\lx@cref\{creftype~refnum\}\{eq:master\-mixture\}\}\}\{\{=\}\}\\int\_\{\\mathcal\{X\}\}f\_\{t\}\(\\bm\{x\}\)\\,d\\mathcal\{P\}\_\{t\}\(\\bm\{x\}\)\\stackrel\{\{\\scriptstyle\(\\text\{LOTUS\}\)\}\}\{\{=\}\}\\mathop\{\\mathbb\{E\}\}\_\{\\bm\{x\}\_\{t\}\\sim\\mathcal\{P\}\_\{t\}\}\\left\[\{f\_\{t\}\(\\bm\{x\}\_\{t\}\)\}\\right\]\(45\)
Also, again by the lazy coupling identity[Eq\.18](https://arxiv.org/html/2609.30556#A1.E18),

Pr⁡\(𝒙t≠𝒙t−1\)=‖𝒫t−𝒫t−1‖TV\.\\Pr\(\\bm\{x\}\_\{t\}\\neq\\bm\{x\}\_\{t\-1\}\)=\\left\\lVert\\mathcal\{P\}\_\{t\}\-\\mathcal\{P\}\_\{t\-1\}\\right\\rVert\_\{\\mathrm\{TV\}\}\.Combining these two identities with[Eq\.9](https://arxiv.org/html/2609.30556#S3.E9)yields

𝔼⁡\[ft​\(𝒙t\)\]\+λ​Pr⁡\(𝒙t≠𝒙t−1\)≤⟨𝒗t,ℓt⟩\+λ⁡⟨𝒗t,𝒄t⟩\+λ2​‖𝒗t−𝒗t−1‖1=⟨𝒗t,𝒈t⟩\+λ2​‖𝒗t−𝒗t−1‖1\.\\mathbb\{E\}\[f\_\{t\}\(\\bm\{x\}\_\{t\}\)\]\+\\lambda\\Pr\(\\bm\{x\}\_\{t\}\\neq\\bm\{x\}\_\{t\-1\}\)\\leq\\left\\langle\\bm\{v\}\_\{t\},\\bm\{\\ell\}\_\{t\}\\right\\rangle\+\\lambda\\left\\langle\\bm\{v\}\_\{t\},\\bm\{c\}\_\{t\}\\right\\rangle\+\\frac\{\\lambda\}\{2\}\\\|\\bm\{v\}\_\{t\}\-\\bm\{v\}\_\{t\-1\}\\\|\_\{1\}=\\left\\langle\\bm\{v\}\_\{t\},\\bm\{g\}\_\{t\}\\right\\rangle\+\\frac\{\\lambda\}\{2\}\\\|\\bm\{v\}\_\{t\}\-\\bm\{v\}\_\{t\-1\}\\\|\_\{1\}\.This proves[Eq\.10](https://arxiv.org/html/2609.30556#S3.E10)\. ∎

### E\.2The DM strongly adaptive regret result

We use the following result from\[[10](https://arxiv.org/html/2609.30556#bib.bib19)\]:

###### Lemma 26\(\[[10](https://arxiv.org/html/2609.30556#bib.bib19)\], Thm\. 1\)\.

Fix a horizonTT, a number of expertsNN, a switching costD≥0D\\geq 0, and an oblivious loss sequencel1,…,lT∈\[0,1\]Nl\_\{1\},\\dots,l\_\{T\}\\in\[0,1\]^\{N\}\. Then there exists a randomized online algorithm choosing expertsIt∈\[N\]I\_\{t\}\\in\[N\]such that for every interval\[s,e\]⊆\[T\]\[s,e\]\\subseteq\[T\]of lengthL=e−s\+1L=e\-s\+1,

𝔼\[∑t=selt\(It\)\+D∑t=s\+1e𝟏\{It≠It−1\}\]≤mini∈\[N\]∑t=selt\(i\)\+Cdm\(D\+1\)​L​log⁡\(N​T\),\\mathbb\{E\}\\left\[\\sum\_\{t=s\}^\{e\}l\_\{t\}\(I\_\{t\}\)\+D\\sum\_\{t=s\+1\}^\{e\}\\mathbf\{1\}\\\{I\_\{t\}\\neq I\_\{t\-1\}\\\}\\right\]\\leq\\min\_\{i\\in\[N\]\}\\sum\_\{t=s\}^\{e\}l\_\{t\}\(i\)\+C\_\{\\mathrm\{dm\}\}\\sqrt\{\(D\+1\)L\\log\(NT\)\},\(46\)whereCdm\>0C\_\{\\mathrm\{dm\}\}\>0is universal\.

### E\.3Algorithmic mechanism behind\[[10](https://arxiv.org/html/2609.30556#bib.bib19), Thm\. 1\]

We now review the algorithmic mechanism that yields the imported guarantee of\[[10](https://arxiv.org/html/2609.30556#bib.bib19), Thm\. 1\]\. Since our reduction works on the simplex, we state the construction in its simplex\-valued OLO form\.

A minor terminology warning is that The Daniely\-Mansour mechanism itself is already hierarchical: it has a family of scale\-dependent learners, together with an internal combination procedure that merges them across scales\. Thus, when we invoke the Daniely\-Mansour learner as our meta learner, that meta learner has its own internal base/meta structure\. We use the term*scale learner*below for the internal Daniely\-Mansour components to avoid confusion\.

For simplicity, this section follows the constructive proof convention of[Daniely and Mansour \[10\]](https://arxiv.org/html/2609.30556#bib.bib19): we describe the mechanism forT=2JT=2^\{J\}andD≥1D\\geq 1\. This restriction is only for the constructive review below; the imported guarantee in[Lemma26](https://arxiv.org/html/2609.30556#Thmtheorem26)is stated for allD≥0D\\geq 0, and the caseD<1D<1is handled in[Daniely and Mansour \[10\]](https://arxiv.org/html/2609.30556#bib.bib19)by reduction toD=1D=1\. The construction has three pieces:

1. 1\.a scale learner for each dyadic scaleτ\\tau;
2. 2\.a two\-way combiner that softly interpolates between two simplex\-valued algorithms;
3. 3\.a multiscale wrapper that combines the dyadic\-scale learners recursively\.

Intuitively, the scale\-τ\\taulearner is tuned to intervals of length aboutτ\\tau, while the combiner ensures that passing from coarse to fine scales preserves control of the switching cost\.

#### Gate function\.

For parametersτ≥1\\tau\\geq 1andZ∈\(0,1/e\]Z\\in\(0,1/e\], letg~τ,Z\\tilde\{g\}\_\{\\tau,Z\}solve

8​g~τ,Z′​\(x\)=xτ​g~τ,Z​\(x\)\+Z,g~τ,Z​\(0\)=0\.8\\tilde\{g\}^\{\\prime\}\_\{\\tau,Z\}\(x\)=\\frac\{x\}\{\\tau\}\\tilde\{g\}\_\{\\tau,Z\}\(x\)\+Z,\\qquad\\tilde\{g\}\_\{\\tau,Z\}\(0\)=0\.Define

gτ,Z​\(x\):=Π\[0,1\]​\(g~τ,Z​\(x\)\),Uτ,Z:=g~τ,Z−1​\(1\),g\_\{\\tau,Z\}\(x\):=\\Pi\_\{\[0,1\]\}\(\\tilde\{g\}\_\{\\tau,Z\}\(x\)\),\\qquad U\_\{\\tau,Z\}:=\\tilde\{g\}\_\{\\tau,Z\}^\{\-1\}\(1\),whereΠ\[a,b\]\\Pi\_\{\[a,b\]\}denotes projection onto\[a,b\]\[a,b\]\.

Algorithm 4Fixed\-Share scale learner at scaleτ\\tau1:scale

τ\\tau, switching cost

D≥1D\\geq 1
2:

η←log⁡\(N​τ\)D​τ\\eta\\leftarrow\\sqrt\{\\frac\{\\log\(N\\tau\)\}\{D\\tau\}\}
3:

z1←\(1/N,…,1/N\)∈ΔNz\_\{1\}\\leftarrow\(1/N,\\dots,1/N\)\\in\\Delta\_\{N\}
4:for

t=1,2,…,Tt=1,2,\\dots,Tdo

5:output

ztz\_\{t\}
6:observe loss vector

ℓt∈\[0,1\]N\\ell\_\{t\}\\in\[0,1\]^\{N\}
7:if

τ≥16​D​log⁡\(N​τ\)\\tau\\geq 16D\\log\(N\\tau\)then

8:update

zt\+1\(i\)=zt​\(i\)​e−η​ℓt​\(i\)\+1N​τ∑j=1N\(zt​\(j\)​e−η​ℓt​\(j\)\+1N​τ\),i=1,…,Nz\_\{t\+1\}\(i\)=\\frac\{z\_\{t\}\(i\)e^\{\-\\eta\\ell\_\{t\}\(i\)\}\+\\frac\{1\}\{N\\tau\}\}\{\\sum\_\{j=1\}^\{N\}\\left\(z\_\{t\}\(j\)e^\{\-\\eta\\ell\_\{t\}\(j\)\}\+\\frac\{1\}\{N\\tau\}\\right\)\},\\qquad i=1,\\dots,N
9:else

10:

zt\+1←ztz\_\{t\+1\}\\leftarrow z\_\{t\}
11:endif

12:endfor

Algorithm[4](https://arxiv.org/html/2609.30556#alg4)is the scale\-dependent learner used in the proof of Theorem 2\.1\.

Algorithm 5Two\-way combinerCombineτ,Z​\(P,Q\)\\mathrm\{Combine\}\_\{\\tau,Z\}\(P,Q\)1:simplex\-valued OLO algorithms

P,QP,Q, scale

τ\\tau, parameter

Z∈\(0,1/e\]Z\\in\(0,1/e\], switching cost

D≥1D\\geq 1
2:initialize

x1←0x\_\{1\}\\leftarrow 0
3:for

t=1,2,…,Tt=1,2,\\dots,Tdo

4:obtain current actions

pt∈ΔNp\_\{t\}\\in\\Delta\_\{N\}from

PPand

qt∈ΔNq\_\{t\}\\in\\Delta\_\{N\}from

QQ
5:if

τ≥64​D​log⁡\(1/Z\)\\tau\\geq 64D\\log\(1/Z\)then

6:

αt←gτ,Z​\(xt\)\\alpha\_\{t\}\\leftarrow g\_\{\\tau,Z\}\(x\_\{t\}\)
7:output

rt←αt​pt\+\(1−αt\)​qtr\_\{t\}\\leftarrow\\alpha\_\{t\}p\_\{t\}\+\(1\-\\alpha\_\{t\}\)q\_\{t\}
8:else

9:output

rt←ptr\_\{t\}\\leftarrow p\_\{t\}
10:endif

11:observe loss vector

ℓt\\ell\_\{t\}
12:let

pt\+1,qt\+1p\_\{t\+1\},q\_\{t\+1\}be the next actions of

P,QP,Q
13:define the surrogate losses

L~t​\(P\):=⟨ℓt,pt⟩\+D​‖pt\+1−pt‖TV3,L~t​\(Q\):=⟨ℓt,qt⟩\+D​‖qt\+1−qt‖TV3\\widetilde\{L\}\_\{t\}\(P\):=\\frac\{\\langle\\ell\_\{t\},p\_\{t\}\\rangle\+D\\\|p\_\{t\+1\}\-p\_\{t\}\\\|\_\{\\mathrm\{TV\}\}\}\{3\},\\qquad\\widetilde\{L\}\_\{t\}\(Q\):=\\frac\{\\langle\\ell\_\{t\},q\_\{t\}\\rangle\+D\\\|q\_\{t\+1\}\-q\_\{t\}\\\|\_\{\\mathrm\{TV\}\}\}\{3\}
14:set

bt:=L~t​\(P\)−L~t​\(Q\)D,xt\+1:=Π\[−2,Uτ,Z\+2\]​\(\(1−1τ\)​xt\+bt\)b\_\{t\}:=\\frac\{\\widetilde\{L\}\_\{t\}\(P\)\-\\widetilde\{L\}\_\{t\}\(Q\)\}\{\\sqrt\{D\}\},\\qquad x\_\{t\+1\}:=\\Pi\_\{\[\-2,U\_\{\\tau,Z\}\+2\]\}\\left\(\\left\(1\-\\frac\{1\}\{\\tau\}\\right\)x\_\{t\}\+b\_\{t\}\\right\)
15:endfor

16:returnalgorithm object

𝒞\\mathcal\{C\}with

𝒞\.Query​\(ℓt\)→rt\\mathcal\{C\}\.\\textsc\{Query\}\(\\ell\_\{t\}\)\\to r\_\{t\}

Algorithm[5](https://arxiv.org/html/2609.30556#alg5)is the key internal combination step\. It mixes the two input algorithms using the gate valuegτ,Z​\(xt\)g\_\{\\tau,Z\}\(x\_\{t\}\), where the scalar statextx\_\{t\}tracks the recent difference between their surrogate losses\.

Algorithm 6Multiscale OLO algorithm underlying Daniely–Mansour Thm\. 2\.11:horizon

T=2JT=2^\{J\}, number of experts

NN, switching cost

D≥1D\\geq 1
2:

Z←12​T​log⁡TZ\\leftarrow\\frac\{1\}\{2T\\log T\}
3:for

u=0,1,…,J−1u=0,1,\\dots,J\-1do

4:

τu←2−u​T\\tau\_\{u\}\\leftarrow 2^\{\-u\}T
5:

Au←Fixed\-Share​\(τu,D\)A\_\{u\}\\leftarrow\\textsc\{Fixed\-Share\}\(\\tau\_\{u\},D\)
6:endfor

7:

B0←A0B\_\{0\}\\leftarrow A\_\{0\}
8:for

u=1,2,…,J−1u=1,2,\\dots,J\-1do

9:

Bu←Combineτu,Z​\(Bu−1,Au\)B\_\{u\}\\leftarrow\\mathrm\{Combine\}\_\{\\tau\_\{u\},Z\}\(B\_\{u\-1\},A\_\{u\}\)
10:endfor

11:return

BJ−1B\_\{J\-1\}⊳\\trianglerightsame interface:BJ−1\.Query​\(ℓt\)→𝒗t∈ΔNB\_\{J\-1\}\.\\textsc\{Query\}\(\\ell\_\{t\}\)\\to\\bm\{v\}\_\{t\}\\in\\Delta\_\{N\}

Algorithm[6](https://arxiv.org/html/2609.30556#alg6)maintains one scale learner for each dyadic scale

T,T/2,T/4,…,2,T,\\ T/2,\\ T/4,\\ \\dots,\\ 2,and combines them recursively from coarse to fine scales\. On any intervalII, one of these scales is of the correct order of magnitude for\|I\|\|I\|, and the recursive combination guarantees that the final algorithm inherits that scale’s regret bound up to logarithmic overhead\. HereJJdenotes the logarithm of the DM horizon, whereasNNdenotes the number of experts in the DM subproblem\. In our meta\-learning application,N=K=\|ℋ\|N=K=\|\\mathcal\{H\}\|\.

#### Remarks\.

1. 1\.All three algorithms share the same interface: when queried withℓt∈\[0,1\]N\\ell\_\{t\}\\in\[0,1\]^\{N\}at roundtt, each returns a weight vector𝒗t∈ΔN\\bm\{v\}\_\{t\}\\in\\Delta\_\{N\}\.Combineis a constructor that takes two such objects and produces a third\.DM\-Multiscalereturns the root of the resulting recursion tree; querying it round by round on\(𝒈t/M\)\(\\bm\{g\}\_\{t\}/M\)is exactly what[Algorithm2](https://arxiv.org/html/2609.30556#alg2)does\.
2. 2\.The denominator33in Algorithm[5](https://arxiv.org/html/2609.30556#alg5)is the specialization of their factor\(M\+1\)\(M\{\+\}1\)to the caseM=2M=2, which is the value used in the proof of the multiscale combination theorem\.
3. 3\.The smallest dyadic scale is22, not11, since the construction usesτu=2−u​T\\tau\_\{u\}=2^\{\-u\}Tforu=0,…,J−1u=0,\\dots,J\-1\.
4. 4\.The output of Algorithm[6](https://arxiv.org/html/2609.30556#alg6)is a sequence\(pt\)t=1T⊆ΔN\(p\_\{t\}\)\_\{t=1\}^\{T\}\\subseteq\\Delta\_\{N\}\. By the OLO/EXP equivalence in[Daniely and Mansour \[10, Sec 5\.2\]](https://arxiv.org/html/2609.30556#bib.bib19), this simplex\-valued algorithm can be converted into a randomized experts algorithm with the same expected loss switching cost\.

Now, we can prove the exact statement of[Lemma11](https://arxiv.org/html/2609.30556#Thmtheorem11)based on[Lemma26](https://arxiv.org/html/2609.30556#Thmtheorem26)\. We use[Lemma26](https://arxiv.org/html/2609.30556#Thmtheorem26)in its stated form for allD≥0D\\geq 0; the algorithmic description in[SectionE\.3](https://arxiv.org/html/2609.30556#A5.SS3)is included only to recall the constructive mechanism and follows theD≥1D\\geq 1proof convention of[Daniely and Mansour \[10\]](https://arxiv.org/html/2609.30556#bib.bib19)\.

###### Proof of[Lemma11](https://arxiv.org/html/2609.30556#Thmtheorem11)\.

We reduce our setting to the discrete expert problem by defining the number of expertsN≐\|ℋ\|N\\doteq\|\\mathcal\{H\}\|\. To accommodate the bounded surrogate rangeMM, we define the normalized oblivious loss sequencelt≐gt/M∈\[0,1\]Nl\_\{t\}\\doteq g\_\{t\}/M\\in\[0,1\]^\{N\}for allt∈\[T\]t\\in\[T\], and set the switching cost parameter toD≐λ/MD\\doteq\\lambda/M\.

LetIt∈\[N\]I\_\{t\}\\in\[N\]be the randomized expert chosen by the algorithm from[Lemma26](https://arxiv.org/html/2609.30556#Thmtheorem26)\. We define our meta\-learner’s distribution over the simplex asvt​\(i\)≐Pr⁡\(It=i\)v\_\{t\}\(i\)\\doteq\\Pr\(I\_\{t\}=i\)fori∈\[N\]i\\in\[N\]\. Because the losses are oblivious,vtv\_\{t\}is determined purely online from the past loss history and the algorithm’s internal randomness\.

For each steptt, the expected loss is exactly the inner product:

𝔼⁡\[lt​\(It\)\]=∑i=1Nvt​\(i\)​lt​\(i\)=⟨vt,lt⟩\.\\mathbb\{E\}\[l\_\{t\}\(I\_\{t\}\)\]=\\sum\_\{i=1\}^\{N\}v\_\{t\}\(i\)l\_\{t\}\(i\)=\\langle v\_\{t\},l\_\{t\}\\rangle\.
Furthermore, the joint law of\(It−1,It\)\(I\_\{t\-1\},I\_\{t\}\)is a coupling of the marginal distributionsvt−1v\_\{t\-1\}andvtv\_\{t\}\. For any coupling of two discrete distributions, the mismatch probability is lower bounded by their total variation distance\. Therefore,

Pr⁡\(It≠It−1\)≥TV⁡\(vt,vt−1\)=12​‖vt−vt−1‖1\.\\Pr\(I\_\{t\}\\neq I\_\{t\-1\}\)\\geq\\mathrm\{TV\}\(v\_\{t\},v\_\{t\-1\}\)=\\frac\{1\}\{2\}\\\|v\_\{t\}\-v\_\{t\-1\}\\\|\_\{1\}\.
Substituting these expected loss and mismatch probability bounds into the expectation on the left\-hand side of[Eq\.46](https://arxiv.org/html/2609.30556#A5.E46)yields a lower bound on the discrete algorithm’s cost:

∑t=se⟨vt,lt⟩\+D2∑t=s\+1e∥vt−vt−1∥1≤𝔼\[∑t=selt\(It\)\+D∑t=s\+1e𝟏\{It≠It−1\}\]\.\\sum\_\{t=s\}^\{e\}\\langle v\_\{t\},l\_\{t\}\\rangle\+\\frac\{D\}\{2\}\\sum\_\{t=s\+1\}^\{e\}\\\|v\_\{t\}\-v\_\{t\-1\}\\\|\_\{1\}\\leq\\mathbb\{E\}\\left\[\\sum\_\{t=s\}^\{e\}l\_\{t\}\(I\_\{t\}\)\+D\\sum\_\{t=s\+1\}^\{e\}\\mathbf\{1\}\\\{I\_\{t\}\\neq I\_\{t\-1\}\\\}\\right\]\.
By chaining this with the upper bound directly from[Lemma26](https://arxiv.org/html/2609.30556#Thmtheorem26), we obtain the simplex formulation of the regret:

∑t=se⟨vt,lt⟩\+D2​∑t=s\+1e‖vt−vt−1‖1≤min⁡∑t=sei∈\[N\]⁡lt​\(i\)\+Cdm​\(D\+1\)​L​log⁡\(N​T\)\.\\sum\_\{t=s\}^\{e\}\\langle v\_\{t\},l\_\{t\}\\rangle\+\\frac\{D\}\{2\}\\sum\_\{t=s\+1\}^\{e\}\\\|v\_\{t\}\-v\_\{t\-1\}\\\|\_\{1\}\\leq\\min\_\{i\\in\[N\]\}\\sum\_\{t=s\}^\{e\}l\_\{t\}\(i\)\+C\_\{\\mathrm\{dm\}\}\\sqrt\{\(D\+1\)L\\log\(NT\)\}\.
Finally, we substitutelt=gt/Ml\_\{t\}=g\_\{t\}/MandD=λ/MD=\\lambda/Minto the above inequality\. Multiplying both sides byMMscales the square root term as follows:

M⋅Cdm​\(λM\+1\)​L​log⁡\(N​T\)=Cdm​M2​\(λ\+MM\)​L​log⁡\(N​T\)=Cdm​M⁡\(M\+λ\)​L​log⁡\(N​T\)\.M\\cdot C\_\{\\mathrm\{dm\}\}\\sqrt\{\\left\(\\frac\{\\lambda\}\{M\}\+1\\right\)L\\log\(NT\)\}=C\_\{\\mathrm\{dm\}\}\\sqrt\{M^\{2\}\\left\(\\frac\{\\lambda\+M\}\{M\}\\right\)L\\log\(NT\)\}=C\_\{\\mathrm\{dm\}\}\\sqrt\{M\(M\+\\lambda\)L\\log\(NT\)\}\.This exactly recovers[Eq\.11](https://arxiv.org/html/2609.30556#S3.E11)and completes the proof\. ∎

### E\.4Proof of the SAR guarantee

###### Proof of[Theorem12](https://arxiv.org/html/2609.30556#Thmtheorem12)\.

WriteJr=\[ar,br\]J\_\{r\}=\[a\_\{r\},b\_\{r\}\], soa1=sa\_\{1\}=s,bm=eb\_\{m\}=e, andbr\+1=ar\+1b\_\{r\}\+1=a\_\{r\+1\}forr<mr<m\.

By[Eq\.45](https://arxiv.org/html/2609.30556#A5.E45):

𝔼⁡\[fs​\(𝒙s\)\]=⟨𝒗s,ℓs⟩≤⟨𝒗s,𝒈s⟩\.\\mathbb\{E\}\[f\_\{s\}\(\\bm\{x\}\_\{s\}\)\]=\\left\\langle\\bm\{v\}\_\{s\},\\bm\{\\ell\}\_\{s\}\\right\\rangle\\leq\\left\\langle\\bm\{v\}\_\{s\},\\bm\{g\}\_\{s\}\\right\\rangle\.Summing the one step bound in[Lemma10](https://arxiv.org/html/2609.30556#Thmtheorem10)overt=s\+1,…,et=s\+1,\\dots,e, and using the above inequality yields

𝔼\[∑t=seft\(𝒙t\)\+λ∑t=s\+1e𝟏\{𝒙t≠𝒙t−1\}\]≤∑t=se⟨𝒗t,𝒈t⟩\+λ2∑t=s\+1e∥𝒗t−𝒗t−1∥1\.\\mathbb\{E\}\\left\[\\sum\_\{t=s\}^\{e\}f\_\{t\}\(\\bm\{x\}\_\{t\}\)\+\\lambda\\sum\_\{t=s\+1\}^\{e\}\\mathbf\{1\}\\\{\\bm\{x\}\_\{t\}\\neq\\bm\{x\}\_\{t\-1\}\\\}\\right\]\\leq\\sum\_\{t=s\}^\{e\}\\left\\langle\\bm\{v\}\_\{t\},\\bm\{g\}\_\{t\}\\right\\rangle\+\\frac\{\\lambda\}\{2\}\\sum\_\{t=s\+1\}^\{e\}\\\|\\bm\{v\}\_\{t\}\-\\bm\{v\}\_\{t\-1\}\\\|\_\{1\}\.\(47\)
Since[Lemma11](https://arxiv.org/html/2609.30556#Thmtheorem11)holds simultaneously for every interval under the single run that generates\(𝒗t\)\(\\bm\{v\}\_\{t\}\), we may apply it to each blockJrJ\_\{r\}using the same sequence\(𝒗t\)\(\\bm\{v\}\_\{t\}\)\.

Since eachJrJ\_\{r\}is a dyadic block, defineHr≐\|Jr\|∈ℋH\_\{r\}\\doteq\|J\_\{r\}\|\\in\\mathcal\{H\}\. The expert with scaleHrH\_\{r\}restarts at the beginning ofJrJ\_\{r\}, so onJrJ\_\{r\}it is exactly a fresh FPRLL\(Hr\)\(H\_\{r\}\)run\.

Thus, for everyrr,

∑t=arbr⟨𝒗t,𝒈t⟩\+λ2​∑t=ar\+1br‖𝒗t−𝒗t−1‖1≤∑t=arbrgt\(Hr\)\+Cdm​M⁡\(M\+λ\)​\|Jr\|​log⁡\(K​T\)\.\\sum\_\{t=a\_\{r\}\}^\{b\_\{r\}\}\\left\\langle\\bm\{v\}\_\{t\},\\bm\{g\}\_\{t\}\\right\\rangle\+\\frac\{\\lambda\}\{2\}\\sum\_\{t=a\_\{r\}\+1\}^\{b\_\{r\}\}\\\|\\bm\{v\}\_\{t\}\-\\bm\{v\}\_\{t\-1\}\\\|\_\{1\}\\leq\\sum\_\{t=a\_\{r\}\}^\{b\_\{r\}\}g\_\{t\}^\{\(H\_\{r\}\)\}\+C\_\{\\mathrm\{dm\}\}\\sqrt\{M\(M\+\\lambda\)\|J\_\{r\}\|\\log\(KT\)\}\.\(48\)Summing[Eq\.48](https://arxiv.org/html/2609.30556#A5.E48)overr=1,…,mr=1,\\dots,mgives

∑r=1m∑t=arbr⟨vt,gt⟩\+λ2​∑r=1m∑t=ar\+1br‖vt−vt−1‖1\\displaystyle\\sum\_\{r=1\}^\{m\}\\sum\_\{t=a\_\{r\}\}^\{b\_\{r\}\}\\left\\langle v\_\{t\},g\_\{t\}\\right\\rangle\+\\frac\{\\lambda\}\{2\}\\sum\_\{r=1\}^\{m\}\\sum\_\{t=a\_\{r\}\+1\}^\{b\_\{r\}\}\\\|v\_\{t\}\-v\_\{t\-1\}\\\|\_\{1\}\(49\)≤∑r=1m∑t∈Jrgt\(Hr\)\+Cdm​M⁡\(M\+λ\)​log⁡\(K​T\)​∑r=1m\|Jr\|\.\\displaystyle\\qquad\\leq\\sum\_\{r=1\}^\{m\}\\sum\_\{t\\in J\_\{r\}\}g\_\{t\}^\{\(H\_\{r\}\)\}\+C\_\{\\mathrm\{dm\}\}\\sqrt\{M\(M\+\\lambda\)\\log\(KT\)\}\\sum\_\{r=1\}^\{m\}\\sqrt\{\|J\_\{r\}\|\}\.\(50\)Because the blocks are consecutive,

∑t=s\+1e‖vt−vt−1‖1=∑r=1m∑t=ar\+1br‖vt−vt−1‖1\+∑r=1m−1‖var\+1−var\+1−1‖1\.\\sum\_\{t=s\+1\}^\{e\}\\\|v\_\{t\}\-v\_\{t\-1\}\\\|\_\{1\}=\\sum\_\{r=1\}^\{m\}\\sum\_\{t=a\_\{r\}\+1\}^\{b\_\{r\}\}\\\|v\_\{t\}\-v\_\{t\-1\}\\\|\_\{1\}\+\\sum\_\{r=1\}^\{m\-1\}\\\|v\_\{a\_\{r\+1\}\}\-v\_\{a\_\{r\+1\}\-1\}\\\|\_\{1\}\.Therefore,

∑t=se⟨vt,gt⟩\+λ2​∑t=s\+1e‖vt−vt−1‖1\\displaystyle\\sum\_\{t=s\}^\{e\}\\left\\langle v\_\{t\},g\_\{t\}\\right\\rangle\+\\frac\{\\lambda\}\{2\}\\sum\_\{t=s\+1\}^\{e\}\\\|v\_\{t\}\-v\_\{t\-1\}\\\|\_\{1\}\(51\)≤∑r=1m∑t∈Jrgt\(Hr\)\+Cdm​M⁡\(M\+λ\)​log⁡\(K​T\)​∑r=1m\|Jr\|\+λ2​∑r=1m−1‖var\+1−var\+1−1‖1\.\\displaystyle\\qquad\\leq\\sum\_\{r=1\}^\{m\}\\sum\_\{t\\in J\_\{r\}\}g\_\{t\}^\{\(H\_\{r\}\)\}\+C\_\{\\mathrm\{dm\}\}\\sqrt\{M\(M\+\\lambda\)\\log\(KT\)\}\\sum\_\{r=1\}^\{m\}\\sqrt\{\|J\_\{r\}\|\}\+\\frac\{\\lambda\}\{2\}\\sum\_\{r=1\}^\{m\-1\}\\\|v\_\{a\_\{r\+1\}\}\-v\_\{a\_\{r\+1\}\-1\}\\\|\_\{1\}\.\(52\)Since𝒗t,𝒗t−1∈ΔN\\bm\{v\}\_\{t\},\\bm\{v\}\_\{t\-1\}\\in\\Delta\_\{N\}, one has‖𝒗t−𝒗t−1‖1≤2\\\|\\bm\{v\}\_\{t\}\-\\bm\{v\}\_\{t\-1\}\\\|\_\{1\}\\leq 2, so each boundary term is at mostλ\\lambda\. Thus

∑t=se⟨vt,gt⟩\+λ2​∑t=s\+1e‖𝒗t−𝒗t−1‖1≤∑r=1m∑t∈Jrgt\(Hr\)\+Cdm​M⁡\(M\+λ\)​log⁡\(K​T\)​∑r=1m\|Jr\|\+λ⁡\(m−1\)\.\\sum\_\{t=s\}^\{e\}\\left\\langle v\_\{t\},g\_\{t\}\\right\\rangle\+\\frac\{\\lambda\}\{2\}\\sum\_\{t=s\+1\}^\{e\}\\\|\\bm\{v\}\_\{t\}\-\\bm\{v\}\_\{t\-1\}\\\|\_\{1\}\\leq\\sum\_\{r=1\}^\{m\}\\sum\_\{t\\in J\_\{r\}\}g\_\{t\}^\{\(H\_\{r\}\)\}\+C\_\{\\mathrm\{dm\}\}\\sqrt\{M\(M\+\\lambda\)\\log\(KT\)\}\\sum\_\{r=1\}^\{m\}\\sqrt\{\|J\_\{r\}\|\}\+\\lambda\(m\-1\)\.\(53\)Combining[Eqs\.47](https://arxiv.org/html/2609.30556#A5.E47)and[53](https://arxiv.org/html/2609.30556#A5.E53), we obtain

𝔼\[∑t=seft\(xt\)\+λ∑t=s\+1e𝟏\{xt≠xt−1\}\]\\displaystyle\\mathbb\{E\}\\left\[\\sum\_\{t=s\}^\{e\}f\_\{t\}\(x\_\{t\}\)\+\\lambda\\sum\_\{t=s\+1\}^\{e\}\\mathbf\{1\}\\\{x\_\{t\}\\neq x\_\{t\-1\}\\\}\\right\]\(54\)≤∑r=1m∑t∈Jrgt\(Hr\)\+Cdm​M⁡\(M\+λ\)​log⁡\(K​T\)​∑r=1m\|Jr\|\+λ⁡\(m−1\)\.\\displaystyle\\qquad\\leq\\sum\_\{r=1\}^\{m\}\\sum\_\{t\\in J\_\{r\}\}g\_\{t\}^\{\(H\_\{r\}\)\}\+C\_\{\\mathrm\{dm\}\}\\sqrt\{M\(M\+\\lambda\)\\log\(KT\)\}\\sum\_\{r=1\}^\{m\}\\sqrt\{\|J\_\{r\}\|\}\+\\lambda\(m\-1\)\.\(55\)
By[Corollary6](https://arxiv.org/html/2609.30556#Thmtheorem6), for any𝒖∈𝒳\\bm\{u\}\\in\\mathcal\{X\}and everyrr,

∑t∈Jr\(gt\(Hr\)−ft​\(𝒖\)\)≤Cbase​\|Jr\|\.\\displaystyle\\sum\_\{t\\in J\_\{r\}\}\\bigl\(g\_\{t\}^\{\(H\_\{r\}\)\}\-f\_\{t\}\(\\bm\{u\}\)\\bigr\)\\leq C\_\{\\mathrm\{base\}\}\\sqrt\{\|J\_\{r\}\|\}\.\(56\)summing over all the dyadic intervals we obtain

∑r=1m∑t∈Jrgt\(Hr\)≤min⁡∑t=seu∈𝒳⁡ft​\(u\)\+Cbase​∑r=1m\|Jr\|\.\\displaystyle\\sum\_\{r=1\}^\{m\}\\sum\_\{t\\in J\_\{r\}\}g\_\{t\}^\{\(H\_\{r\}\)\}\\leq\\min\_\{u\\in\\mathcal\{X\}\}\\sum\_\{t=s\}^\{e\}f\_\{t\}\(u\)\+C\_\{\\text\{base\}\}\\sum\_\{r=1\}^\{m\}\\sqrt\{\|J\_\{r\}\|\}\.\(57\)
Substituting[Eq\.57](https://arxiv.org/html/2609.30556#A5.E57)into[Eq\.55](https://arxiv.org/html/2609.30556#A5.E55), subtracting the comparator term from both sides, and using:

λ⁡\(m−1\)≤λ⁡\(2​⌈log2⁡L⌉\+1\),by the first part of[Eq\.6](https://arxiv.org/html/2609.30556#S3.E6),\\lambda\(m\-1\)\\leq\\lambda\(2\\lceil\\log\_\{2\}L\\rceil\+1\),\\qquad\\text\{by the first part of \\lx@cref\{creftype~refnum\}\{eq:dyadic\-cover\}\},and

∑r=1m\|Jr\|≤Cgc​L,by the second part of[Eq\.6](https://arxiv.org/html/2609.30556#S3.E6),\\sum\_\{r=1\}^\{m\}\\sqrt\{\|J\_\{r\}\|\}\\leq C\_\{\\mathrm\{gc\}\}\\sqrt\{L\},\\qquad\\text\{by the second part of \\lx@cref\{creftype~refnum\}\{eq:dyadic\-cover\}\},the lemma statement follows ∎

### E\.5Proof of[Corollary13](https://arxiv.org/html/2609.30556#Thmtheorem13)

Let\{𝒖t\}t=1T∈𝒳T\\\{\\bm\{u\}\_\{t\}\\\}\_\{t=1\}^\{T\}\\in\\mathcal\{X\}^\{T\}be an arbitrary comparator sequence, and let

ST≐∑t=2T𝟏\{𝒖t≠𝒖t−1\}\.S\_\{T\}\\;\\doteq\\;\\sum\_\{t=2\}^\{T\}\\mathbf\{1\}\\\{\\bm\{u\}\_\{t\}\\neq\\bm\{u\}\_\{t\-1\}\\\}\.This sequence induces a partition of\[T\]\[T\]intoST\+1S\_\{T\}\+1maximal consecutive segments on which𝒖t\\bm\{u\}\_\{t\}is constant,

𝒮i=\[si,ei\],i=1,…,ST\+1,\\mathcal\{S\}\_\{i\}\\;=\\;\[s\_\{i\},e\_\{i\}\],\\qquad i=1,\\dots,S\_\{T\}\+1,withs1=1s\_\{1\}=1,eST\+1=Te\_\{S\_\{T\}\+1\}=T, andei\+1=si\+1e\_\{i\}\+1=s\_\{i\+1\}fori=1,…,STi=1,\\dots,S\_\{T\}\. Writing𝒖\(i\)\\bm\{u\}^\{\(i\)\}for the common value of𝒖t\\bm\{u\}\_\{t\}on𝒮i\\mathcal\{S\}\_\{i\},

∑t=1Tft​\(𝒖t\)=∑i=1ST\+1∑t∈𝒮ift​\(𝒖\(i\)\)≥∑i=1ST\+1min⁡∑t∈𝒮i𝒖∈𝒳⁡ft​\(𝒖\)\.\\sum\_\{t=1\}^\{T\}f\_\{t\}\(\\bm\{u\}\_\{t\}\)\\;=\\;\\sum\_\{i=1\}^\{S\_\{T\}\+1\}\\sum\_\{t\\in\\mathcal\{S\}\_\{i\}\}f\_\{t\}\(\\bm\{u\}^\{\(i\)\}\)\\;\\geq\\;\\sum\_\{i=1\}^\{S\_\{T\}\+1\}\\min\_\{\\bm\{u\}\\in\\mathcal\{X\}\}\\sum\_\{t\\in\\mathcal\{S\}\_\{i\}\}f\_\{t\}\(\\bm\{u\}\)\.\(58\)
#### Decomposing the switching cost along the partition\.

The total indicator switching cost splits into within\-segment and boundary contributions:

∑t=2T𝟏\{𝒙t≠𝒙t−1\}=∑i=1ST\+1∑t=si\+1ei𝟏\{𝒙t≠𝒙t−1\}⏟within segments\+∑i=2ST\+1𝟏\{𝒙si≠𝒙si−1\}⏟STboundary switches\.\\sum\_\{t=2\}^\{T\}\\mathbf\{1\}\\\{\\bm\{x\}\_\{t\}\\neq\\bm\{x\}\_\{t\-1\}\\\}\\;=\\;\\underbrace\{\\sum\_\{i=1\}^\{S\_\{T\}\+1\}\\sum\_\{t=s\_\{i\}\+1\}^\{e\_\{i\}\}\\mathbf\{1\}\\\{\\bm\{x\}\_\{t\}\\neq\\bm\{x\}\_\{t\-1\}\\\}\}\_\{\\text\{within segments\}\}\\;\+\\;\\underbrace\{\\sum\_\{i=2\}^\{S\_\{T\}\+1\}\\mathbf\{1\}\\\{\\bm\{x\}\_\{s\_\{i\}\}\\neq\\bm\{x\}\_\{s\_\{i\}\-1\}\\\}\}\_\{\\text\{$S\_\{T\}$ boundary switches\}\}\.\(59\)
Combining[Eqs\.58](https://arxiv.org/html/2609.30556#A5.E58)and[59](https://arxiv.org/html/2609.30556#A5.E59)and taking expectation,

𝔼⁡\[ℛT𝟏​\(\{𝒖t\}t=1T\)\]\\displaystyle\\mathbb\{E\}\\left\[\\mathcal\{R\}^\{\\mathbf\{1\}\}\_\{T\}\(\\\{\\bm\{u\}\_\{t\}\\\}\_\{t=1\}^\{T\}\)\\right\]≤∑i=1ST\+1\(𝔼\[∑t∈𝒮ift\(𝒙t\)\+λ∑t=si\+1ei𝟏\{𝒙t≠𝒙t−1\}\]−min𝒖∈𝒳∑t∈𝒮ift\(𝒖\)\)\\displaystyle\\;\\leq\\;\\sum\_\{i=1\}^\{S\_\{T\}\+1\}\\left\(\\mathbb\{E\}\\left\[\\sum\_\{t\\in\\mathcal\{S\}\_\{i\}\}f\_\{t\}\(\\bm\{x\}\_\{t\}\)\+\\lambda\\sum\_\{t=s\_\{i\}\+1\}^\{e\_\{i\}\}\\mathbf\{1\}\\\{\\bm\{x\}\_\{t\}\\neq\\bm\{x\}\_\{t\-1\}\\\}\\right\]\-\\min\_\{\\bm\{u\}\\in\\mathcal\{X\}\}\\sum\_\{t\\in\\mathcal\{S\}\_\{i\}\}f\_\{t\}\(\\bm\{u\}\)\\right\)\+λ∑i=2ST\+1Pr\(𝒙si≠𝒙si−1\)\\displaystyle\\qquad\+\\lambda\\sum\_\{i=2\}^\{S\_\{T\}\+1\}\\Pr\\left\(\\bm\{x\}\_\{s\_\{i\}\}\\neq\\bm\{x\}\_\{s\_\{i\}\-1\}\\right\)=∑i=1ST\+1SAR𝒮i​\(𝒖\(i\)\)\+λ​∑i=2ST\+1Pr⁡\(𝒙si≠𝒙si−1\),\\displaystyle\\;=\\;\\sum\_\{i=1\}^\{S\_\{T\}\+1\}\\mathrm\{SAR\}\_\{\\mathcal\{S\}\_\{i\}\}\(\\bm\{u\}^\{\(i\)\}\)\\;\+\\;\\lambda\\sum\_\{i=2\}^\{S\_\{T\}\+1\}\\Pr\\left\(\\bm\{x\}\_\{s\_\{i\}\}\\neq\\bm\{x\}\_\{s\_\{i\}\-1\}\\right\),\(60\)where the last equality uses the definition ofSAR\\mathrm\{SAR\}in[Eq\.12](https://arxiv.org/html/2609.30556#S4.E12)\. Each boundary probability is at most one, so the second sum is bounded byλ​ST\\lambda S\_\{T\}\.

#### Applying the SAR guarantee\.

By[Theorem12](https://arxiv.org/html/2609.30556#Thmtheorem12), for every segment𝒮i\\mathcal\{S\}\_\{i\},

SAR𝒮i​\(𝒖\(i\)\)=𝒪~​\(\|𝒮i\|\)\.\\mathrm\{SAR\}\_\{\\mathcal\{S\}\_\{i\}\}\(\\bm\{u\}^\{\(i\)\}\)\\;=\\;\\tilde\{\\mathcal\{O\}\}\\left\(\\sqrt\{\|\\mathcal\{S\}\_\{i\}\|\}\\right\)\.Summing overiiand applying Cauchy–Schwarz,

∑i=1ST\+1\|𝒮i\|≤ST\+1​∑i=1ST\+1\|𝒮i\|=\(ST\+1\)​T\.\\sum\_\{i=1\}^\{S\_\{T\}\+1\}\\sqrt\{\|\\mathcal\{S\}\_\{i\}\|\}\\;\\leq\\;\\sqrt\{S\_\{T\}\+1\}\\,\\sqrt\{\\sum\_\{i=1\}^\{S\_\{T\}\+1\}\|\\mathcal\{S\}\_\{i\}\|\}\\;=\\;\\sqrt\{\(S\_\{T\}\+1\)\\,T\}\.\(61\)
Substituting into[Eq\.60](https://arxiv.org/html/2609.30556#A5.E60),

𝔼⁡\[ℛT𝟏​\(\{𝒖t\}t=1T\)\]≤𝒪~​\(\(ST\+1\)​T\)\+λ​ST,\\mathbb\{E\}\\left\[\\mathcal\{R\}^\{\\mathbf\{1\}\}\_\{T\}\(\\\{\\bm\{u\}\_\{t\}\\\}\_\{t=1\}^\{T\}\)\\right\]\\;\\leq\\;\\tilde\{\\mathcal\{O\}\}\\left\(\\sqrt\{\(S\_\{T\}\+1\)\\,T\}\\right\)\\;\+\\;\\lambda S\_\{T\},which is the claimed bound\. ∎

### E\.6Proof for the DR guarantee

###### Proof of[Theorem14](https://arxiv.org/html/2609.30556#Thmtheorem14)\.

Fix any comparator sequence\{𝒖t\}t=1T⊆𝒳\\\{\\bm\{u\}\_\{t\}\\\}\_\{t=1\}^\{T\}\\subseteq\\mathcal\{X\}\. By definition,

𝔼\[ℛT𝟏​\(\{𝒖t\}t=1T\)\]=𝔼\[∑t=1Tft​\(𝒙t\)\]−∑t=1Tft​\(𝒖t\)\+λ​∑t=2TPr⁡\(𝒙t≠𝒙t−1\)\.\\mathop\{\\mathbb\{E\}\}\\left\[\{\\mathcal\{R\}^\{\\mathbf\{1\}\}\_\{T\}\(\\\{\\bm\{u\}\_\{t\}\\\}\_\{t=1\}^\{T\}\)\}\\right\]=\\mathop\{\\mathbb\{E\}\}\\left\[\{\\sum\_\{t=1\}^\{T\}f\_\{t\}\(\\bm\{x\}\_\{t\}\)\}\\right\]\-\\sum\_\{t=1\}^\{T\}f\_\{t\}\(\\bm\{u\}\_\{t\}\)\+\\lambda\\sum\_\{t=2\}^\{T\}\\Pr\(\\bm\{x\}\_\{t\}\\neq\\bm\{x\}\_\{t\-1\}\)\.Fort=1t=1, sincec1\(H\)=0c\_\{1\}^\{\(H\)\}=0for everyH∈ℋH\\in\\mathcal\{H\}, we haveg1\(H\)=ℓ1\(H\)g\_\{1\}^\{\(H\)\}=\\ell\_\{1\}^\{\(H\)\}, and therefore

𝔼\[f1​\(𝒙1\)\]=⟨v1,g1⟩\.\\mathop\{\\mathbb\{E\}\}\\left\[\{f\_\{1\}\(\\bm\{x\}\_\{1\}\)\}\\right\]=\\langle v\_\{1\},g\_\{1\}\\rangle\.For eacht≥2t\\geq 2,[Lemma10](https://arxiv.org/html/2609.30556#Thmtheorem10)gives

𝔼\[ft​\(𝒙t\)\]\+λ​Pr⁡\(𝒙t≠𝒙t−1\)≤⟨vt,gt⟩\+λ2​‖vt−vt−1‖1\.\\mathop\{\\mathbb\{E\}\}\\left\[\{f\_\{t\}\(\\bm\{x\}\_\{t\}\)\}\\right\]\+\\lambda\\Pr\(\\bm\{x\}\_\{t\}\\neq\\bm\{x\}\_\{t\-1\}\)\\leq\\langle v\_\{t\},g\_\{t\}\\rangle\+\\frac\{\\lambda\}\{2\}\\\|v\_\{t\}\-v\_\{t\-1\}\\\|\_\{1\}\.Summing overt=1,…,Tt=1,\\dots,T, we obtain

𝔼\[∑t=1Tft​\(𝒙t\)\]\+λ​∑t=2TPr⁡\(𝒙t≠𝒙t−1\)≤∑t=1T⟨vt,gt⟩\+λ2​∑t=2T‖vt−vt−1‖1\.\\mathop\{\\mathbb\{E\}\}\\left\[\{\\sum\_\{t=1\}^\{T\}f\_\{t\}\(\\bm\{x\}\_\{t\}\)\}\\right\]\+\\lambda\\sum\_\{t=2\}^\{T\}\\Pr\(\\bm\{x\}\_\{t\}\\neq\\bm\{x\}\_\{t\-1\}\)\\leq\\sum\_\{t=1\}^\{T\}\\langle v\_\{t\},g\_\{t\}\\rangle\+\\frac\{\\lambda\}\{2\}\\sum\_\{t=2\}^\{T\}\\\|v\_\{t\}\-v\_\{t\-1\}\\\|\_\{1\}\.Subtracting∑t=1Tft​\(𝒖t\)\\sum\_\{t=1\}^\{T\}f\_\{t\}\(\\bm\{u\}\_\{t\}\), we get

𝔼\[ℛT𝟏​\(\{𝒖t\}t=1T\)\]≤∑t=1T⟨vt,gt⟩\+λ2​∑t=2T‖vt−vt−1‖1−∑t=1Tft​\(𝒖t\)\.\\mathop\{\\mathbb\{E\}\}\\left\[\{\\mathcal\{R\}^\{\\mathbf\{1\}\}\_\{T\}\(\\\{\\bm\{u\}\_\{t\}\\\}\_\{t=1\}^\{T\}\)\}\\right\]\\leq\\sum\_\{t=1\}^\{T\}\\langle v\_\{t\},g\_\{t\}\\rangle\+\\frac\{\\lambda\}\{2\}\\sum\_\{t=2\}^\{T\}\\\|v\_\{t\}\-v\_\{t\-1\}\\\|\_\{1\}\-\\sum\_\{t=1\}^\{T\}f\_\{t\}\(\\bm\{u\}\_\{t\}\)\.\(62\)
Now fix anyH∈ℋH\\in\\mathcal\{H\}, and add and subtract∑t=1Tgt\(H\)\\sum\_\{t=1\}^\{T\}g\_\{t\}^\{\(H\)\}on the right\-hand side of[Eq\.62](https://arxiv.org/html/2609.30556#A5.E62)\. This yields

𝔼\[ℛT𝟏​\(\{𝒖t\}t=1T\)\]\\displaystyle\\mathop\{\\mathbb\{E\}\}\\left\[\{\\mathcal\{R\}^\{\\mathbf\{1\}\}\_\{T\}\(\\\{\\bm\{u\}\_\{t\}\\\}\_\{t=1\}^\{T\}\)\}\\right\]≤\(∑t=1T⟨vt,gt⟩\+λ2​∑t=2T‖vt−vt−1‖1−∑t=1Tgt\(H\)\)\\displaystyle\\leq\\left\(\\sum\_\{t=1\}^\{T\}\\langle v\_\{t\},g\_\{t\}\\rangle\+\\frac\{\\lambda\}\{2\}\\sum\_\{t=2\}^\{T\}\\\|v\_\{t\}\-v\_\{t\-1\}\\\|\_\{1\}\-\\sum\_\{t=1\}^\{T\}g\_\{t\}^\{\(H\)\}\\right\)\+\(∑t=1Tgt\(H\)−∑t=1Tft​\(𝒖t\)\)\.\\displaystyle\+\\left\(\\sum\_\{t=1\}^\{T\}g\_\{t\}^\{\(H\)\}\-\\sum\_\{t=1\}^\{T\}f\_\{t\}\(\\bm\{u\}\_\{t\}\)\\right\)\.We now control the two brackets separately\. The first is the regret of the meta\-learner relative to expertHH\. Applying[Lemma11](https://arxiv.org/html/2609.30556#Thmtheorem11)on the full interval\[1,T\]\[1,T\], whose length isTT, gives

∑t=1T⟨vt,gt⟩\+λ2​∑t=2T‖vt−vt−1‖1−∑t=1Tgt\(H\)≤Cdm​M⁡\(M\+λ\)​T​log⁡\(K​T\)\.\\sum\_\{t=1\}^\{T\}\\langle v\_\{t\},g\_\{t\}\\rangle\+\\frac\{\\lambda\}\{2\}\\sum\_\{t=2\}^\{T\}\\\|v\_\{t\}\-v\_\{t\-1\}\\\|\_\{1\}\-\\sum\_\{t=1\}^\{T\}g\_\{t\}^\{\(H\)\}\\leq C\_\{\\mathrm\{dm\}\}\\sqrt\{M\(M\+\\lambda\)\\,T\\log\(KT\)\}\.Hence, for everyH∈ℋH\\in\\mathcal\{H\},

𝔼\[ℛT𝟏​\(\{𝒖t\}t=1T\)\]≤∑t=1Tgt\(H\)−∑t=1Tft​\(𝒖t\)\+Cdm​M⁡\(M\+λ\)​T​log⁡\(K​T\)\.\\mathop\{\\mathbb\{E\}\}\\left\[\{\\mathcal\{R\}^\{\\mathbf\{1\}\}\_\{T\}\(\\\{\\bm\{u\}\_\{t\}\\\}\_\{t=1\}^\{T\}\)\}\\right\]\\leq\\sum\_\{t=1\}^\{T\}g\_\{t\}^\{\(H\)\}\-\\sum\_\{t=1\}^\{T\}f\_\{t\}\(\\bm\{u\}\_\{t\}\)\+C\_\{\\mathrm\{dm\}\}\\sqrt\{M\(M\+\\lambda\)\\,T\\log\(KT\)\}\.Taking the minimum overH∈ℋH\\in\\mathcal\{H\}proves[Eq\.14](https://arxiv.org/html/2609.30556#S4.E14)\.

It remains to instantiate the expert term\. By[Theorem7](https://arxiv.org/html/2609.30556#Thmtheorem7), there exists a dyadic restart scalek†∈ℋk^\{\\dagger\}\\in\\mathcal\{H\}such that

∑t=1Tgt\(k†\)−∑t=1Tft​\(𝒖t\)=ℛT𝟏,k†≤2​A​Tk⋆\+\(B\+G\)​PT​k⋆\.\\sum\_\{t=1\}^\{T\}g\_\{t\}^\{\(k^\{\\dagger\}\)\}\-\\sum\_\{t=1\}^\{T\}f\_\{t\}\(\\bm\{u\}\_\{t\}\)=\\mathcal\{R\}^\{\\mathbf\{1\},\{\{k^\{\\dagger\}\}\}\}\_\{T\}\\leq\\sqrt\{2\}\\,A\\,\\frac\{T\}\{\\sqrt\{k^\{\\star\}\}\}\+\(B\+G\)P\_\{T\}\\,k^\{\\star\}\.SubstitutingH=k†H=k^\{\\dagger\}into[Eq\.14](https://arxiv.org/html/2609.30556#S4.E14)gives[Eq\.15](https://arxiv.org/html/2609.30556#S4.E15)\. ∎

## Appendix FEstimating the surrogate

The surrogate

gt\(H\)=ℓt\(H\)\+λ​ct\(H\)g\_\{t\}^\{\(H\)\}=\\ell\_\{t\}^\{\(H\)\}\+\\lambda c\_\{t\}^\{\(H\)\}in[Eq\.7](https://arxiv.org/html/2609.30556#S3.E7)is convenient for analysis but is not directly computable\. Indeed,

ℓt\(H\)=𝔼𝒙∼𝒬t\(H\)​\[ft​\(𝒙\)\]\\ell\_\{t\}^\{\(H\)\}=\\mathbb\{E\}\_\{\\bm\{x\}\\sim\\mathcal\{Q\}\_\{t\}^\{\(H\)\}\}\[f\_\{t\}\(\\bm\{x\}\)\]is an expectation under the expert’s sampling distribution, while

ct\(H\)=‖𝒬t\(H\)−𝒬t−1\(H\)‖TVc\_\{t\}^\{\(H\)\}=\\left\\lVert\\mathcal\{Q\}\_\{t\}^\{\(H\)\}\-\\mathcal\{Q\}\_\{t\-1\}^\{\(H\)\}\\right\\rVert\_\{\\mathrm\{TV\}\}is a total\-variation distance between two high\-dimensional densities\. Neither quantity has a closed form in general\. We therefore use the following implementable surrogate\.

Let

ϵH≐β​dσH\+d​GμH\\epsilon\_\{H\}\\doteq\\frac\{\\beta d\}\{\\sigma\_\{H\}\}\+\\frac\{\\sqrt\{d\}\\,G\}\{\\mu\_\{H\}\}be the within\-block TV bound from[Lemma24](https://arxiv.org/html/2609.30556#Thmtheorem24)for the scale\-HHparameters used by FPRLL\(H\)\. Define

c^t\(H\)\\displaystyle\\hat\{c\}\_\{t\}^\{\(H\)\}≐\{0,t=1,min⁡\{ϵH,1\},t,t−1​lie in the same block of​ℰH,1,t​is the first round of a new block of​ℰH,\\displaystyle\\doteq\\begin\{cases\}0,&t=1,\\\\ \\min\\\{\\epsilon\_\{H\},1\\\},&t,t\-1\\text\{ lie in the same block of \}\\mathcal\{E\}\_\{H\},\\\\ 1,&t\\text\{ is the first round of a new block of \}\\mathcal\{E\}\_\{H\},\\end\{cases\}\(63\)ℓ^t\(H\)\\displaystyle\\hat\{\\ell\}\_\{t\}^\{\(H\)\}≐ft​\(𝒚t\(H\)\),𝒚t\(H\)∼𝒬t\(H\),\\displaystyle\\doteq f\_\{t\}\(\\bm\{y\}\_\{t\}^\{\(H\)\}\),\\qquad\\bm\{y\}\_\{t\}^\{\(H\)\}\\sim\\mathcal\{Q\}\_\{t\}^\{\(H\)\},\(64\)g^t\(H\)\\displaystyle\\hat\{g\}\_\{t\}^\{\(H\)\}≐ℓ^t\(H\)\+λ​c^t\(H\)\.\\displaystyle\\doteq\\hat\{\\ell\}\_\{t\}^\{\(H\)\}\+\\lambda\\hat\{c\}\_\{t\}^\{\(H\)\}\.\(65\)The auxiliary samples𝒚t\(H\)\\bm\{y\}\_\{t\}^\{\(H\)\}are drawn freshly for each round and scale, afterftf\_\{t\}is revealed, and independently of the current meta\-action conditional on the current history\. The meta\-learner in[Algorithm2](https://arxiv.org/html/2609.30556#alg2)is run with

𝒈^t≐\(g^t\(H\)\)H∈ℋ\\hat\{\\bm\{g\}\}\_\{t\}\\doteq\(\\hat\{g\}\_\{t\}^\{\(H\)\}\)\_\{H\\in\\mathcal\{H\}\}in place of the exact vector𝒈t\\bm\{g\}\_\{t\}\.

It is useful to separate the sampled surrogate from its conditional mean\. Define

g¯t\(H\)≐ℓt\(H\)\+λ​c^t\(H\)\.\\bar\{g\}\_\{t\}^\{\(H\)\}\\doteq\\ell\_\{t\}^\{\(H\)\}\+\\lambda\\hat\{c\}\_\{t\}^\{\(H\)\}\.Theng^t\(H\)\\hat\{g\}\_\{t\}^\{\(H\)\}is an unbiased estimate ofg¯t\(H\)\\bar\{g\}\_\{t\}^\{\(H\)\}, not necessarily ofgt\(H\)g\_\{t\}^\{\(H\)\}\. More precisely, conditional on the history afterftf\_\{t\}is revealed but before the auxiliary samples are drawn,

𝔼⁡\[g^t\(H\)\]=g¯t\(H\)\.\\mathbb\{E\}\[\\hat\{g\}\_\{t\}^\{\(H\)\}\]=\\bar\{g\}\_\{t\}^\{\(H\)\}\.Moreover,g¯t\(H\)\\bar\{g\}\_\{t\}^\{\(H\)\}upper\-bounds the exact surrogate\. Indeed,[Lemma24](https://arxiv.org/html/2609.30556#Thmtheorem24)givesct\(H\)≤ϵHc\_\{t\}^\{\(H\)\}\\leq\\epsilon\_\{H\}inside a restart block, while at restart boundaries we use the trivial boundct\(H\)≤1c\_\{t\}^\{\(H\)\}\\leq 1\. Hence

ct\(H\)≤c^t\(H\)and thereforegt\(H\)≤g¯t\(H\)\.c\_\{t\}^\{\(H\)\}\\leq\\hat\{c\}\_\{t\}^\{\(H\)\}\\qquad\\text\{and therefore\}\\qquad g\_\{t\}^\{\(H\)\}\\leq\\bar\{g\}\_\{t\}^\{\(H\)\}\.
We now explain why using𝒈^t\\hat\{\\bm\{g\}\}\_\{t\}does not change the guarantees\. The original analysis uses the surrogate vector in three places\.

#### 1\. The one\-step master reduction\.

The original one\-step bound is

𝔼⁡\[ft​\(𝒙t\)\]\+λ​Pr⁡\(𝒙t≠𝒙t−1\)≤⟨𝒗t,𝒈t⟩\+λ2​‖𝒗t−𝒗t−1‖1\.\\mathbb\{E\}\[f\_\{t\}\(\\bm\{x\}\_\{t\}\)\]\+\\lambda\\Pr\(\\bm\{x\}\_\{t\}\\neq\\bm\{x\}\_\{t\-1\}\)\\leq\\langle\\bm\{v\}\_\{t\},\\bm\{g\}\_\{t\}\\rangle\+\\frac\{\\lambda\}\{2\}\\\|\\bm\{v\}\_\{t\}\-\\bm\{v\}\_\{t\-1\}\\\|\_\{1\}\.Sincegt\(H\)≤g¯t\(H\)g\_\{t\}^\{\(H\)\}\\leq\\bar\{g\}\_\{t\}^\{\(H\)\}for everyHHand𝒗t∈ΔK\\bm\{v\}\_\{t\}\\in\\Delta\_\{K\},

⟨𝒗t,𝒈t⟩≤⟨𝒗t,𝒈¯t⟩\.\\langle\\bm\{v\}\_\{t\},\\bm\{g\}\_\{t\}\\rangle\\leq\\langle\\bm\{v\}\_\{t\},\\bar\{\\bm\{g\}\}\_\{t\}\\rangle\.Taking expectation over the auxiliary samples gives

𝔼⁡\[⟨𝒗t,𝒈^t⟩\]=𝔼⁡\[⟨𝒗t,𝒈¯t⟩\]\.\\mathbb\{E\}\[\\langle\\bm\{v\}\_\{t\},\\hat\{\\bm\{g\}\}\_\{t\}\\rangle\]=\\mathbb\{E\}\[\\langle\\bm\{v\}\_\{t\},\\bar\{\\bm\{g\}\}\_\{t\}\\rangle\]\.Therefore,

𝔼⁡\[ft​\(𝒙t\)\]\+λ​Pr⁡\(𝒙t≠𝒙t−1\)≤𝔼⁡\[⟨𝒗t,𝒈^t⟩\]\+λ2​𝔼​\[‖𝒗t−𝒗t−1‖1\]\.\\mathbb\{E\}\[f\_\{t\}\(\\bm\{x\}\_\{t\}\)\]\+\\lambda\\Pr\(\\bm\{x\}\_\{t\}\\neq\\bm\{x\}\_\{t\-1\}\)\\leq\\mathbb\{E\}\[\\langle\\bm\{v\}\_\{t\},\\hat\{\\bm\{g\}\}\_\{t\}\\rangle\]\+\\frac\{\\lambda\}\{2\}\\mathbb\{E\}\[\\\|\\bm\{v\}\_\{t\}\-\\bm\{v\}\_\{t\-1\}\\\|\_\{1\}\]\.Thus the real one\-step cost of the master is still controlled, in expectation, by the sampled surrogate losses fed to the meta\-learner\.

#### 2\. The meta\-regret bound\.

The meta\-regret lemma is applied directly to the realized sequence

𝒈^1,…,𝒈^T\.\\hat\{\\bm\{g\}\}\_\{1\},\\ldots,\\hat\{\\bm\{g\}\}\_\{T\}\.This sequence is valid full\-information feedback for the meta\-learner:𝒈^t\\hat\{\\bm\{g\}\}\_\{t\}is observed after the meta\-action is chosen, and it is generated independently of the current meta\-action conditional on the history\. Also, by boundedness of the losses,

0≤g^t\(H\)≤Mf\+λ≐M\.0\\leq\\hat\{g\}\_\{t\}^\{\(H\)\}\\leq M\_\{f\}\+\\lambda\\doteq M\.Therefore[Lemma11](https://arxiv.org/html/2609.30556#Thmtheorem11)applies with𝒈^t\\hat\{\\bm\{g\}\}\_\{t\}\. For any intervalI=\[s,e\]I=\[s,e\]of lengthLL,

∑t=se⟨𝒗t,𝒈^t⟩\+λ2​∑t=s\+1e‖𝒗t−𝒗t−1‖1≤min⁡∑t=seH∈ℋ⁡g^t\(H\)\+Cdm​M⁡\(M\+λ\)​L​log⁡\(K​T\)\.\\sum\_\{t=s\}^\{e\}\\langle\\bm\{v\}\_\{t\},\\hat\{\\bm\{g\}\}\_\{t\}\\rangle\+\\frac\{\\lambda\}\{2\}\\sum\_\{t=s\+1\}^\{e\}\\\|\\bm\{v\}\_\{t\}\-\\bm\{v\}\_\{t\-1\}\\\|\_\{1\}\\leq\\min\_\{H\\in\\mathcal\{H\}\}\\sum\_\{t=s\}^\{e\}\\hat\{g\}\_\{t\}^\{\(H\)\}\+C\_\{\\mathrm\{dm\}\}\\sqrt\{M\(M\+\\lambda\)L\\log\(KT\)\}\.Taking expectations and using

𝔼⁡\[minH⁡ZH\]≤minH⁡𝔼⁡\[ZH\],\\mathbb\{E\}\[\\min\_\{H\}Z\_\{H\}\]\\leq\\min\_\{H\}\\mathbb\{E\}\[Z\_\{H\}\],we obtain

𝔼⁡\[∑t=se⟨𝒗t,𝒈^t⟩\+λ2​∑t=s\+1e‖𝒗t−𝒗t−1‖1\]≤min⁡∑t=seH∈ℋ⁡\(ℓt\(H\)\+λ​c^t\(H\)\)\+Cdm​M⁡\(M\+λ\)​L​log⁡\(K​T\)\.\\mathbb\{E\}\\\!\\left\[\\sum\_\{t=s\}^\{e\}\\langle\\bm\{v\}\_\{t\},\\hat\{\\bm\{g\}\}\_\{t\}\\rangle\+\\frac\{\\lambda\}\{2\}\\sum\_\{t=s\+1\}^\{e\}\\\|\\bm\{v\}\_\{t\}\-\\bm\{v\}\_\{t\-1\}\\\|\_\{1\}\\right\]\\leq\\min\_\{H\\in\\mathcal\{H\}\}\\sum\_\{t=s\}^\{e\}\\left\(\\ell\_\{t\}^\{\(H\)\}\+\\lambda\\hat\{c\}\_\{t\}^\{\(H\)\}\\right\)\+C\_\{\\mathrm\{dm\}\}\\sqrt\{M\(M\+\\lambda\)L\\log\(KT\)\}\.

#### 3\. The best\-expert term after the meta\-regret bound\.

After applying the meta\-regret bound, the remaining quantity is the cost of the best scaleHH:

∑t\(ℓt\(H\)\+λ​c^t\(H\)\)\.\\sum\_\{t\}\\left\(\\ell\_\{t\}^\{\(H\)\}\+\\lambda\\hat\{c\}\_\{t\}^\{\(H\)\}\\right\)\.This differs from the original exact surrogate cost

∑tgt\(H\)=∑t\(ℓt\(H\)\+λ​ct\(H\)\)\\sum\_\{t\}g\_\{t\}^\{\(H\)\}=\\sum\_\{t\}\\left\(\\ell\_\{t\}^\{\(H\)\}\+\\lambda c\_\{t\}^\{\(H\)\}\\right\)only in the switching term\. The replacement is harmless becausec^t\(H\)\\hat\{c\}\_\{t\}^\{\(H\)\}is chosen to match the switching upper bounds already used in the base\-expert analysis\. Inside each restart block,

c^t\(H\)=min⁡\{ϵH,1\}≤ϵH,\\hat\{c\}\_\{t\}^\{\(H\)\}=\\min\\\{\\epsilon\_\{H\},1\\\}\\leq\\epsilon\_\{H\},which is the same within\-block movement bound used in[Corollary6](https://arxiv.org/html/2609.30556#Thmtheorem6)and[Theorem7](https://arxiv.org/html/2609.30556#Thmtheorem7)\. At a restart boundary,

c^t\(H\)=1,\\hat\{c\}\_\{t\}^\{\(H\)\}=1,so the contribution is at mostλ\\lambda, which is absorbed by the existing restart\-boundary terms\.

Consequently, the arguments of[Corollary6](https://arxiv.org/html/2609.30556#Thmtheorem6)and[Theorem7](https://arxiv.org/html/2609.30556#Thmtheorem7)give the same asymptotic bounds for

∑t\(ℓt\(H\)\+λ​c^t\(H\)\)−∑tft​\(𝒖t\)\\sum\_\{t\}\\left\(\\ell\_\{t\}^\{\(H\)\}\+\\lambda\\hat\{c\}\_\{t\}^\{\(H\)\}\\right\)\-\\sum\_\{t\}f\_\{t\}\(\\bm\{u\}\_\{t\}\)as for the original exact surrogate regret, up to universal constant changes in the existing restart\-boundary terms\.

Combining the three observations, the guarantees of[Theorem12](https://arxiv.org/html/2609.30556#Thmtheorem12),[Corollary13](https://arxiv.org/html/2609.30556#Thmtheorem13), and[Theorem14](https://arxiv.org/html/2609.30556#Thmtheorem14)continue to hold in expectation for the algorithm using𝒈^t\\hat\{\\bm\{g\}\}\_\{t\}, with the same rates\.