Dynamic Regret in Online Convex Optimization with Indicator Switching Costs

1 Introduction

• Indicator switching costs charge a penalty whenever consecutive actions differ, regardless of change magnitude, and on bounded domains they subsume norm-based switching costs.The penalty models reconfiguration overheads such as server activation, cache updates, and model redeployment.Source: §1 · p. 1
• Existing OCO guarantees for indicator switching costs address static regret, while recursive updates in OMD obstruct the pointwise densities needed for maximal coupling.The dynamic-regret case also remains open for FTRL: history-pruning enhancements linearize the objective and make the iterate recursive.Source: §1 · p. 2

1.1 Contributions

• Perturbed FTRL with fixed restarts still fails to achieve optimal sublinear dynamic regret, and without restarts it incurs Ω(T) regret even against a comparator with one switch.The paper argues that a different architecture beyond a single FTRL run is required.Source: §1 · p. 2, §1.1 · p. 3
• A comparator-oblivious algorithm combines restarted FPRLL learners at dyadic scales with a discounted-normal master to obtain strongly adaptive regret across intervals.The guarantee is uniform over comparator actions and intervals.Source: §1.1 · p. 3
• For piecewise-constant comparators, a segmentation reduction yields dynamic regret matching the minimax tracking rate up to logarithmic factors, without prior knowledge of the switch count.The supplied passages identify this as the piecewise-constant branch of the guarantee.Source: §1.1 · p. 3
• The same algorithm also guarantees a path-length-based bound for the larger comparator class, which includes sequences that move slightly at every round.The authors note that this indicator-cost bound does not match the unified norm-based path-length bound; attaining that stronger result remains open because the learner pays per change while the comparator is charged by total movement.Source: §1.1 · p. 3

1.2 Overview of the approach

• At each dyadic scale, restarted FPRLL trades responsiveness against frequent switching, while the master mixes proposal densities and samples consecutive actions by maximal coupling.The master scores scales using expected loss plus the switching cost they would incur, and discounted-normal prediction controls transitions between scales.Source: §1.2 · p. 4

Minimizers and their densities

• Random Laplace perturbations define minimizers whose induced densities can be evaluated pointwise, supporting lazy coupling of consecutive draws.The resulting probability of switching is the total variation distance between consecutive action distributions.Source: §2 · pp. 4–5

Regret guarantees

• FPRLL's dynamic-regret statement is explicit in its tuning parameters and the comparator path budget.The supplied passage identifies this guarantee but does not include its full bound.Source: §2 · p. 5
• O(Cbase k) static regret with indicator switching cost is the stated bound for FPRLL on a full restart block.This fixed-comparator block guarantee is used as a primitive in the multiscale analysis.Source: §2 · p. 5

Tracking cost

• Long restart periods can miss comparator switches within a block, creating a tracking cost.The tracking lower-bound construction uses losses on [-1, 1] and a comparator with S_T = τ and P_T = 2τ.Source: §2 · p. 6

Laziness cost

• Short restart periods incur repeated-start laziness costs, which improve as the restart period k grows.Replaying a hard instance across T/k blocks yields a lower bound against a stationary comparator with S_T = P_T = 0.Source: §2 · p. 6

3 Meta-learning framework

• The master combines restarted FPRLL experts at dyadic scales, assigning each scale a surrogate loss that includes its expected loss and switching cost.There are O(log T) dyadic scales; each base expert restarts every H rounds.Source: §3 · pp. 6–7
• Every interval admits a short cover by consecutive dyadic intervals, letting the analysis match each covered block to an expert with the corresponding restart period.The dyadic lengths are H = {2^j : 0 ≤ j ≤ ⌊log2 T⌋}.Source: §3 · p. 6
• A density-mixture master samples actions by lazy coupling consecutive mixtures, preserving the mixture marginals and making its switching probability equal to their total variation distance.The master therefore operates on expert weights while actions are sampled from the corresponding mixture distributions.Source: §3 · pp. 6–7
• The implementation updates O(log T) FPRLL learners per round, adds O(log^2 T) meta-level overhead, and can use sampled surrogates with computable conditional-mean upper bounds.The paper gives the exact surrogate losses for analysis but describes sampled surrogates for implementation.Source: §3 · p. 7
• The reduction charges the master for expert movement through surrogate losses and for its own weight movement in ℓ1, yielding an experts problem with switching-cost parameter λ/2.Competing with an expert’s cumulative surrogate carries over that expert’s prediction and switching guarantees.Source: §3 · pp. 7–8
• A strongly adaptive algorithm aggregates the scale experts and competes with the best expert on every interval while controlling switches among experts.The surrogate range needed by its guarantees is ensured by Assumptions 3 and 4.Source: §3 · p. 8

4.1 Piecewise-constant comparators via strongly adaptive regret

• Strongly adaptive regret is applied on intervals and combined with a restarted base learner’s static-regret guarantee to obtain a bound for piecewise-constant comparators.The proof uses a dyadic cover of each interval and compares each block with the expert whose restart period matches that block.Source: §4.1 · p. 8
• Segmenting at comparator switch points reduces the strongly adaptive guarantee to the dynamic-regret branch for piecewise-constant comparators, with a non-dominant λS_T term.The resulting branch is stated in Corollary 13.Source: §4.1 · p. 8

4.2 Path-varying comparators

• For bounded-path-length comparators, the analysis uses the base learner’s dynamic-regret bound at the dyadic restart scale that matches comparator drift, rather than segmenting at switch points.This branch accommodates comparator sequences that may drift by small amounts at every round.Source: §4.2 · p. 9

5 Related work

• Prior work studies few-switch learners against static comparators and dynamic regret with norm-based movement costs, but generally does not combine these guarantees for general OCO.Related directions include strongly adaptive methods, privacy-motivated few-change learning, and restarting perturbed leaders without switching costs.Source: §5 · p. 9

Appendix

• The appendix organizes technical proofs around fresh-minimizer density, lazy sampling, lower bounds, base-learner guarantees, dyadic interval covering, and meta-learner reductions.These results lead to the strongly adaptive and dynamic-regret guarantees.Source: Appendix · p. 12

A.1 Change of variable formula

• A change-of-variables calculation gives the density of the fresh perturbed minimizer.The appendix derives this density from the minimizer map.Source: §A.1 · p. 12

A.2 Lazy sampling

• The lazy-sampling routine realizes maximal coupling while preserving marginals and controlling switches, and Algorithm 1 instantiates it with consecutive FPRLL marginals.When the keep test fails, the next FPRLL minimizer is sampled using fresh perturbation; the density formula supports pointwise comparisons.Source: §A.2 · p. 13

B Lower bounds

• For the one-dimensional problem on X = [−1, 1] with linear losses, the no-restart FPRLL dynamic-regret result gives E[R_k] ≥ 1 for every k = 1, …, n.Source: B Lower bounds · p. 13, Let the learner predict at each round · p. 15

Let the learner predict at each round

• Alternating gadgets at restart scales yield a dynamic-regret lower-bound construction: each uncut gadget contributes expected regret at least h*, while a separate stationary-comparator construction uses independently sampled restart blocks.In the stationary-comparator branch, the same expected-loss minimizer is retained across blocks, and indicator switching costs only add nonnegative cost.Source: Let the learner predict at each round · pp. 16–17
• For fixed restart period k, the adversary chooses one of two branches uniformly at time 0 and plays it throughout the horizon.The comparator sequence is associated with the realized branch, and the mixed adversary may depend on k through the Sherman branch.Source: Let the learner predict at each round · p. 17
• Ω(kτ/log(T/τ)) is the lower bound from Theorem 8 on the C=0 branch; the C=1 bound from Lemma 19 is truncated in the supplied text.Conditioning further on k0=k, the passage reports that this event has probability Θ(1/log T), but its resulting lower-bound expression is also truncated.Source: Let the learner predict at each round · p. 18

C Proofs for the base learner

• Lemma 21 decomposes expected dynamic regret into static and dynamic terms, extending the decomposition in to the perturbed, barrier-regularized setting.The proof of Theorem 5 combines four intermediate lemmas.Source: C Proofs for the base learner · p. 18
• Lemma 22 bounds the static term while explicitly accounting for Laplace perturbations under the stated strong-convexity conditions.The lemma assumes the functions F_t are σ-strongly convex.Source: C Proofs for the base learner · pp. 18, 20
• Lemma 23 bounds the dynamic term’s dependence on comparator drift through the barrier geometry.Its proof uses properties of the scaled barrier on the shrunk domain.Source: C Proofs for the base learner · pp. 18, 21, 22
• Lemma 24 bounds total variation between consecutive sampling distributions for convex, G-Lipschitz, β-smooth losses, controlling the switching-cost contribution.Only this total-variation bound follows the general approach of; the other three lemmas are specific to this setting.Source: C Proofs for the base learner · pp. 18, 22
• The main theorem follows by combining the static and dynamic bounds with lazy sampling and the consecutive-distribution total-variation bound.The excerpt states that this yields the claimed result but does not provide its explicit bound.Source: C Proofs for the base learner · pp. 18, 23

C.1 Proof of Theorem 7

• The proof partitions the horizon into k-length blocks and applies Theorem 5 on each block.The blocks are consecutive, and the same parameter choices are used on each.Source: §C.1 · pp. 23–24
• The blockwise bound includes λ(m−1) for restart-boundary switching and terms involving the within-block path budgets and k.The proof sums the within-block contributions before optimizing the scale.Source: §C.1 · pp. 23–24
• The proof selects a stationary scale, clips it to [1, T], and shows that both boundary cases are dominated by the interior rate.It treats separately the cases where the unclipped scale is below 1 or above T.Source: §C.1 · p. 24

D.1 Proof of Lemma 9

• An arbitrary interval is partitioned into two sequences of disjoint, consecutive intervals whose union is the interval.The covering fact is attributed to Orabona [17, Thm. 15.9].Source: §D.1 · p. 25
• Each side uses at most ⌈log2 L⌉ + 1 blocks because its block lengths occupy distinct dyadic scales and are at most L.The proof applies this count to the relabeled partition.Source: §D.1 · p. 25
• The proof bounds the sum of square roots of block lengths by expressing the left-side lengths through tail sums and using geometric decrease.It applies the same argument to the right side.Source: §D.1 · p. 25

E.1 Proof for the one step

• Because lazy sampling gives xt ∼ Pt, linearity of integration identifies expected sampled loss with the master’s mixture loss.The proof defines the master expectation before applying this relation.Source: §E.1 · p. 26
• The one-step proof combines the lazy coupling identities with Eq. (9) to establish Eq. (10).It also uses total variation and the triangle inequality to bound a change between distributions.Source: §E.1 · p. 26

E.2 The DM strongly adaptive regret result

• The imported DM guarantee controls regret on every interval, with a bound scaling as (D + 1)L log(NT).Here L is the interval length; the result is cited from.Source: §E.2 · p. 27, §E.3 · p. 27

E.3 Algorithmic mechanism behind [9, Thm. 1]

• The multiscale mechanism recursively combines dyadic-scale learners from coarse to fine, so an interval can use a scale of the right order.The two-way combiner gates its mixture using a state tracking recent surrogate-loss differences.Source: §E.3 · p. 27

E.4 Proof of the SAR guarantee

• Each dyadic block is handled by the scale expert that restarts at its beginning, making it a fresh FPRLL run.The interval guarantee holds simultaneously for all blocks under the same sequence of meta-learner distributions.Source: §E.4 · p. 30
• Summing block bounds introduces boundary terms of at most λ because consecutive blocks meet and simplex distributions differ in L1 norm by at most 2.The proof sums the blockwise inequalities over the partition.Source: §E.4 · p. 30
• Combining the summed bounds yields the stated strongly adaptive regret guarantee.The proof obtains it by substituting the bound and subtracting the comparator term.Source: §E.4 · pp. 30–31

E.5 Proof of Corollary 13

• The comparator's S_T + 1 constant segments split indicator switching cost into within-segment and boundary contributions.The proof applies the SAR guarantee on each segment; each boundary probability is at most one, bounding the boundary term by λS_T.Source: §E.5 · p. 31
• Summing segment bounds, applying Cauchy–Schwarz, and substituting into the earlier inequality yields the claimed Corollary 13 bound.Source: §E.5 · p. 32

E.6 Proof for the DR guarantee

• The DR proof splits regret into the master’s regret against an expert and that expert’s cost, then minimizes over experts and instantiates a dyadic restart scale.The scale is chosen using Theorem 7; substituting it gives Eq. (15).Source: §E.6 · p. 32

• The total-variation quantities lack closed forms generally, so the paper replaces the analytically convenient surrogate with an implementable sampled estimate.The sampled estimate is unbiased for its conditional mean, which need not equal the exact quantity.Source: F Estimating the surrogate · p. 33
• The sampled surrogate upper-bounds the exact surrogate cost, with an ε_H bound within restart blocks and a trivial bound at restart boundaries.Source: F Estimating the surrogate · p. 33
• Taking expectation over auxiliary samples keeps the master's real one-step cost controlled by the sampled surrogate losses.Source: F Estimating the surrogate · p. 34
• The sampled sequence provides valid full-information feedback, allowing the meta-regret bound to apply on any interval.The estimate is observed after the meta-action and is conditionally independent of that action; bounded losses ensure the required range.Source: F Estimating the surrogate · p. 34
• Theorems 12, Corollary 13, and Theorem 14 retain their expected guarantees at the same rates under the sampled-surrogate algorithm.The surrogate replacement changes the switching term, but the within-block and restart-boundary bounds preserve the asymptotic rates.Source: F Estimating the surrogate · p. 34