NeurIPS 2026 (task-list archive; the version read is arXiv v1) Optimization online convex optimization dynamic regret indicator switching costs maximal coupling strongly adaptive regret

Dynamic Regret in Online Convex Optimization with Indicator Switching Costs¶

Conference: NeurIPS 2026 (task-list archive; the version read is arXiv v1)
arXiv: 2609.30556
Area: Optimization & Theory
Keywords: online convex optimization, dynamic regret, indicator switching costs, maximal coupling, strongly adaptive regret

TL;DR¶

The paper aggregates distributions from randomized lazy FTRL learners restarted at dyadic scales through a movement-aware meta-learner, uses maximal coupling to control actual action changes, and obtains near-optimal expected dynamic regret for piecewise-constant comparators alongside a separate guarantee for comparators with small path length.

Background & Motivation¶

In online convex optimization, the learner chooses an action before observing the current loss function. Dynamic regret permits a comparator to change over time, but model redeployment, cache updates, or server activation can charge a fixed fee for every change: even two nearly identical actions incur the fee. Norm-based switching costs allow small movements every round, whereas indicator switching costs require repeating exactly the same action. On a bounded-diameter domain, controlling the number of action changes controls norm movement, but the converse does not hold.

Existing lazy online convex optimization primarily addresses static comparators. FPRLL retains the full history, derives a pointwise-evaluable density for its randomized minimizer, and reduces changes through lazy sampling; accumulated history nevertheless makes it slow to react to reversals. The paper proves that without restarts, this algorithm family can suffer linear dynamic regret even against a comparator that switches only once. Fixed-period restarts encounter another obstacle: long periods miss changes inside a block, while short periods repeatedly incur the cost of starting over. Switching directly to recursive mirror descent updates also makes it difficult to obtain the action densities needed for maximal coupling.

The paper therefore maintains multiple restart periods instead of selecting one optimal period in advance, letting a meta-learner identify the appropriate scale on every local interval. Selecting experts solely by prediction loss is insufficient because both expert-internal changes and changes in expert weights can introduce switching costs. Core Idea: aggregate multiscale lazy FTRL in density space, include each expert's total variation in its surrogate loss, and control mixture-weight movement with a movement-aware strongly adaptive meta-learner.

Method¶

Overall Architecture¶

The inputs are a bounded convex decision domain and full convex loss functions revealed sequentially; the output is a randomized action sequence. There is no offline training dataset or neural-network training stage. The algorithm maintains dyadically restarted experts, obtains an FPRLL density from each expert, mixes the densities, and samples using maximal coupling between consecutive mixtures. After executing the action and observing the loss, the movement-aware meta-learner updates the next-round weights; each expert also updates its accumulated objective and restarts when scheduled.

The performance criterion charges switching costs to the learner, not to the comparator:

\[ \mathcal{R}^{\mathbf{1}}_T(u_{1:T})=\sum_{t=1}^{T}\bigl(f_t(x_t)-f_t(u_t)\bigr)+\sum_{t=2}^{T}\lambda_t\mathbf{1}\{x_t\ne x_{t-1}\}. \]

Two different quantities measure comparator complexity. The switch count records whether a change occurs, while path length sums Euclidean distances:

\[ S_T=\sum_{t=2}^{T}\mathbf{1}\{u_t\ne u_{t-1}\},\qquad P_T=\sum_{t=2}^{T}\|u_t-u_{t-1}\|. \]

For a domain of diameter \(D\), \(P_T\le DS_T\), but a comparator moving a tiny distance every round can have a large \(S_T\) and a small \(P_T\). The algorithm does not require either quantity in advance and is not rerun using whichever quantity turns out to be smaller.

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["Past losses and current round"] --> B["Dyadic restarts"]
    B --> C["FPRLL densities"]
    C --> D["Mixture maximal coupling"]
    D --> E["Execute action<br/>Then reveal the full loss"]
    E --> F["Movement-aware meta-learning"]
    C -. "Expert expected loss and TV<br/>or Appendix F surrogates" .-> F
    F -. "Next-round mixture weights" .-> D
    E -. "Update accumulated objectives" .-> A

Solid edges show the current-round decision and feedback order; dashed edges show expert scoring and next-round state updates. The algorithm mixes action distributions rather than averaging expert actions, which would generally still change every round on a continuous domain.

Key Designs¶

1. Dyadic restarts: provide an expert that starts at the right location for each local block

The algorithm maintains all periods in \(\mathcal{H}=\{1,2,4,\ldots,2^{\lfloor\log_2T\rfloor}\}\), giving \(K=\lfloor\log_2T\rfloor+1\) experts. An expert with period \(H\) discards its block history every \(H\) rounds and starts a fresh FPRLL run. Short-period experts quickly forget old environments, while long-period experts reduce restart costs; the algorithm is not given the unknown change points.

These scales cover arbitrary local intervals because any interval of length \(L\) can be partitioned into at most \(2\lceil\log_2L\rceil+2\) consecutive dyadic intervals. The sum of their square-root lengths is at most \((2+\sqrt{2})\sqrt{L}\). Each block has an expert that restarts exactly at its beginning with a period equal to its length. Interval regret therefore does not rely on the entire interval happening to fit inside one restart block; it relies on geometric covering and the meta-learner's competitiveness on each subinterval.

Appendix B explains the insufficiency of a fixed period through algorithm-family lower bounds. Without restarts, a two-phase linear-gradient sequence that first maintains one sign and then reverses it prevents a full-history leader from changing direction promptly; Theorem 17 uses symmetric perturbations and a pairing argument to establish expected loss regret of at least \(T/2\). Restarted variants face a conflict between long-period tracking costs and short-period static costs. These conclusions concern the analyzed FPRLL structure, not an impossibility for all online algorithms.

2. FPRLL densities: expose the distribution of a perturbed minimizer instead of recursive action updates

Each expert accumulates the original revealed losses within its current block and adds a quadratic regularizer and a scaled logarithmic barrier. The quadratic term makes the accumulated objective strongly convex, and the barrier keeps perturbed minimizers in the interior; newly revealed losses need only be convex, not strongly convex. The source represents the domain through finitely many concave constraints \(s_c(x)\ge0\), with a strictly feasible origin and \(s_c(0)=1\), to construct the barrier and shrunk comparators.

Let \(a\) be the current block's starting round, and let \(F_{t-1}\) denote the regularizer, barrier, and losses accumulated from \(a\) through \(t-1\). After drawing a Laplace perturbation \(p\), the expert minimizes the perturbed objective. Optimality and a change of variables yield:

\[ \tilde{x}_t=\arg\min_{x\in\mathcal{X}}\{F_{t-1}(x)+\langle p,x\rangle\},\qquad \mathcal{Q}_t(x)=\nu(-\nabla F_{t-1}(x))\,|\det(-\nabla^2F_{t-1}(x))|. \]

Here \(\nu(p)=(2\mu)^{-d}\exp(-\|p\|_1/\mu)\). This density formula does not imply inexpensive optimization; it enables comparison of old and new densities at a given location, precisely the pointwise access needed for maximal coupling. The meta-algorithm uses experts as density interfaces rather than first generating every expert's lazy action and then choosing one.

Within a block of length \(H\), each expert tunes the shrinkage parameter, regularization strength, and perturbation scale to the block length. The source uses \(\gamma=1/\sqrt{H}\), \(\mu_H=\sqrt{\lambda GH/(R\sqrt{2})}\), and \(\sigma_H=\sqrt{(G^2+2\lambda\beta d)H}/R\), where \(R\) is the domain radius, \(G\) the Lipschitz constant, and \(\beta\) the smoothness constant. Static block regret has square-root order, while regularization strength and perturbation scale control within-block total variation.

For the proof, Appendix C decomposes prediction regret into static stability, comparator drift, and shrinkage error, then adds the TV switching term. The drift term contains accumulated history length multiplied by path length, explaining why long-period experts suit stable intervals but a single long-running FPRLL does not automatically achieve optimal dynamic regret.

3. Mixture maximal coupling: convert density changes exactly into action-switch probabilities

The master forms a mixture density using weights \(v_t\). Independent resampling on a continuous domain almost surely changes the action, so two nearby distributions still cannot be sampled independently every round. Maximal coupling first attempts to reuse the preceding action and draws from the residual of the new distribution only when reuse fails.

\[ \mathcal{P}_t=\sum_{H\in\mathcal{H}}v_{t,H}\mathcal{Q}^{(H)}_t,\qquad \Pr(x_t\ne x_{t-1})=\|\mathcal{P}_t-\mathcal{P}_{t-1}\|_{\mathrm{TV}}. \]

Total variation distance is half the integral of the absolute difference between the two densities and lies in \([0,1]\). Specifically, the routine decides whether to retain the old action using the density ratio at that action. If retention fails, it repeatedly proposes samples from the new distribution and rejects proposals in the overlap of the old and new distributions. Lemma 16 in Appendix A establishes two facts: the next action retains the correct marginal distribution, and its change probability equals TV. This probability identity supports an expectation guarantee, not a deterministic guarantee for every randomized action trajectory.

Both expert-density movement and mixture-weight movement change the master distribution. Lemma 10 separates them:

\[ \|\mathcal{P}_t-\mathcal{P}_{t-1}\|_{\mathrm{TV}} \le\sum_Hv_{t,H}c_t^{(H)}+\frac12\|v_t-v_{t-1}\|_1, \qquad c_t^{(H)}=\|\mathcal{Q}_t^{(H)}-\mathcal{Q}_{t-1}^{(H)}\|_{\mathrm{TV}}. \]

The proof in Appendix E.1 adds and subtracts a mixture with new weights and old expert distributions, then applies the triangle inequality. Positive and negative mass in the weight change are equal, giving half the \(\ell_1\) weight movement rather than an arbitrary additional expert-switching budget.

4. Movement-aware meta-learning: track useful scales while paying for scale changes

Each expert's surrogate loss combines expected prediction loss with its own density-movement cost:

\[ g_t^{(H)}=\ell_t^{(H)}+\lambda c_t^{(H)},\qquad \ell_t^{(H)}=\mathbb{E}_{x\sim\mathcal{Q}_t^{(H)}}[f_t(x)],\qquad c_1^{(H)}=0. \]

Using the known upper bound \(\lambda\) rather than the actual round-specific fee \(\lambda_t\) makes this surrogate conservatively cover the learner's switching cost. The master's expected cost is consequently bounded by weighted surrogate loss plus \(\lambda\|v_t-v_{t-1}\|_1/2\). This reduces the continuous-action problem to movement-aware online linear optimization over finitely many experts, rather than a standard experts problem without movement penalties.

The meta-learner uses the Daniely–Mansour discounted-normal-predictor mechanism. Internally, it maintains fixed-share learners at multiple time scales and recursively merges them from coarse to fine with two-way soft combiners. A combiner adjusts its gate using discounted accumulated differences in surrogate loss while including internal weight-movement costs in scoring. These internal time scales and the outer FPRLL restart periods are distinct layers.

Bounded losses provide \(M=M_f+\lambda\) for normalizing the surrogate vector. Appendix E.3 uses discrete-expert switching parameter \(D_{\mathrm{meta}}=\lambda/M\), which becomes the \(\lambda/2\) coefficient above in simplex form. On every interval of length \(L\), Lemma 11 bounds the additional cost relative to the best fixed scale by \(C_{\mathrm{dm}}\sqrt{M(M+\lambda)L\log(KT)}\). This supplies the missing link between local block guarantees and strongly adaptive regret.

A Worked Example¶

Consider an illustrative run with \(T=8\) and outer expert periods \(1,2,4,8\). The period-\(2\) expert restarts at rounds \(1,3,5,7\), while the period-\(4\) expert restarts at rounds \(1,5\). If a new environmental phase begins at round \(5\), both experts can begin accumulating from that phase, whereas the period-\(8\) expert retains the earlier history.

This does not mean that the master necessarily changes actions at round \(5\). It first maximally couples the current and preceding mixture densities and may retain the old action. Only after the loss is revealed does it compute scale-specific feedback and adjust the weights for round \(6\). At an expert restart, the practical surrogate charges the TV upper bound \(1\), rather than claiming that its actual switch probability is \(1\). This is a timing illustration, not a paper experiment, and contains no measured gains.

Loss & Training¶

“Training” here means online updates, not offline fitting. The source assumes that the full loss function is revealed after action execution; this is not a bandit algorithm observing only the loss of the selected action. Exact expected losses and high-dimensional TV distances are generally not directly computable, so the exact surrogate in the main text primarily serves the analysis.

Appendix F estimates loss with independent auxiliary samples and substitutes a computable conservative quantity for TV. With \(\epsilon_H=\beta d/\sigma_H+\sqrt{d}G/\mu_H\), the rule is:

\[ \hat c_t^{(H)}=\begin{cases} 0,&t=1,\\ \min\{\epsilon_H,1\},&t,t-1\text{ in the same block},\\ 1,&t\text{ starts a new block}, \end{cases}\qquad \hat g_t^{(H)}=f_t(y_t^{(H)})+\lambda\hat c_t^{(H)},\quad y_t^{(H)}\sim\mathcal{Q}_t^{(H)}. \]

Auxiliary samples are drawn freshly for every round and scale after the loss is revealed and are conditionally independent of the current meta-action given the history. Their conditional mean is therefore \(\bar g_t^{(H)}=\ell_t^{(H)}+\lambda\hat c_t^{(H)}\ge g_t^{(H)}\): the estimator is unbiased for this upper bound, not for the exact surrogate. Appendix F explains that the within-block and restart-boundary upper bounds match costs already used in the base analysis, preserving the same expected rates.

Complexity must be described layer by layer: the additional meta-level overhead for \(K=\mathcal{O}(\log T)\) experts is \(\mathcal{O}(\log^2T)\) per round. Total cost also includes expert-objective updates, perturbed optimization, Hessian determinants/density evaluations, auxiliary samples, and rejection sampling for maximal coupling. The paper does not give a unified dimension-dependent runtime guarantee for all these operations together.

Key Experimental Results¶

The source has no empirical experiments; the following compare theoretical guarantees and assumptions.

Main Results¶

The following table compares theorems, not dataset scores. Expectations concern algorithmic randomness; lower bounds with randomized adversarial distributions also average over that randomness. The main upper bounds apply to every fixed comparator sequence and all intervals without requiring \(S_T\) or \(P_T\) in advance, but are not simultaneous high-probability statements about a single randomized run.

Theoretical result	Guarantee or lower bound	Scope and evidence
Strongly adaptive regret	\(\tilde{\mathcal{O}}(\sqrt{L})\)	Every interval and fixed comparator; Theorem 12, Appendix E.4
Piecewise-constant dynamic regret	\(\tilde{\mathcal{O}}(\sqrt{(S_T+1)T})+\lambda S_T\)	Every comparator sequence; Corollary 13, Appendix E.5
Path-length dynamic regret	\(\tilde{\mathcal{O}}(\max\{T^{2/3}P_T^{1/3},\sqrt{T}\})\)	Every comparator sequence; Theorem 14, Appendix E.6
FPRLL without restarts	Expected loss regret of at least \(T/2\)	One-dimensional linear losses, one comparator switch; Theorem 17
Fixed-period tracking lower bound	\(\Omega(k\tau/\log(T/\tau))\)	One oblivious distribution is hard for all integers \(4\le k\le T/\tau\), with \(T\ge4\tau\); Theorem 8
Fixed-period combined lower bound	\(\Omega(k\tau/\log(T/\tau)+T/\sqrt{k})\)	The distribution can depend on fixed \(k\); the static branch additionally assumes at most \(C\sqrt{k}\) expected switches per block; Proposition 20, Lemma 19

The additional \(\lambda S_T\) in Corollary 13 covers learner switches at comparator-segment boundaries; it does not charge the comparator. For fixed problem constants it can be absorbed into the square-root leading order, but if \(\lambda\) grows with \(T\), its dependence cannot be ignored. The main text's unified expression is \(\tilde{\mathcal{O}}(\min\{\sqrt{(S_T+1)T},T^{2/3}(P_T+1)^{1/3}\})\), while retaining Theorem 14's maximum form makes the \(P_T=0\) boundary clearer.

Ablation Study¶

The following analyzes theoretical conditions and mechanisms, not empirical module-removal ablations.

Condition or mechanism	Source requirement/role	What it does not establish
Decision domain	Convex and bounded, with radius \(R\) and diameter \(D\); density implementation additionally uses a strictly feasible origin and a barrier representation through finitely many concave constraints	Guarantees on unbounded domains or efficient implementation on arbitrary non-evaluable domains
Loss functions	Twice differentiable, convex, \(G\)-Lipschitz, \(\beta\)-smooth, and \(0\le f_t\le M_f\)	That new losses must be strongly convex, or that smoothness has been removed
Switching coefficients	\(0<\lambda_t\le\lambda\), with known \(\lambda>0\)	Adaptation to unknown, arbitrarily unbounded switching fees
Maximal coupling	Preserves correct marginals and realizes switch probabilities through TV	The same switching guarantee under independent sampling
Practical surrogate	Its conditional mean upper-bounds the exact surrogate; Appendix F	An unbiased estimate of exact \(g_t^{(H)}\)
Adversarial scope	Lemma 26 and E.3 explicitly use oblivious losses; Appendix F requires conditional independence of auxiliary samples	Automatic extension to an adaptive adversary choosing losses after observing the learner's current action

Key Findings¶

The piecewise-constant branch achieves the minimax order up to logarithmic factors with the same algorithm; it is not an oracle result using known change points.
The path branch comes from the restart tradeoff \(AT/\sqrt{k}+(B+G)P_Tk\). The interior optimal period scales as \((T/P_T)^{2/3}\) and must be clipped to \([1,T]\), explaining \(T^{2/3}P_T^{1/3}\) rather than the square-root path rate for norm-based costs.
Zero path length still leaves the static-regret baseline \(\sqrt{T}\); the pure product rate must not be read as zero regret. The clipped boundary analysis in proof C.1 and Theorem 14 are more complete than Theorem 7's abbreviated statement.

Highlights & Insights¶

Density-level lazy sampling turns “small parameter changes” into “repeating exactly the same action.” Fixed startup overhead requires this discrete stability; distance control alone is insufficient.
The surrogate is not merely a convenient optimization target but a decomposition of actual switching costs. Pricing expert-internal TV and master-weight movement separately prevents meta-learning from erasing the laziness of base experts.
Geometric covering allows one expert per period to serve arbitrary intervals. The key is matched restart blocks together with local meta-level competitiveness, rather than creating a new expert for every possible starting time.

Limitations & Future Work¶

The authors explicitly leave open whether \(\tilde{\mathcal{O}}(\sqrt{T(1+P_T)})\) is achievable under indicator costs; the paper does not establish optimality of its path rate over all algorithms. Fixed-period algorithm-family lower bounds are not general minimax lower bounds.
There are no empirical experiments, implementation-throughput measurements, or evaluations of high-dimensional sampling. Evaluable densities do not imply cheap integration, perturbed optimization, or rejection sampling, and polylogarithmic meta overhead is not end-to-end runtime.
The main conclusions do not extend unconditionally to adaptive adversaries. The imported experts theorem explicitly assumes oblivious losses, and the discussion of auxiliary randomized feedback does not resolve action-dependent losses.
Exact constants need checking: the proof of Lemma 22 controls the distance between two points by radius \(R\), whereas the direct general guarantee is at most \(2R\). Corollary 6 writes an expression containing constant terms as equal to \(C_{\mathrm{base}}\sqrt{k}\), which should be understood as an upper bound under the stated definition. These issues do not change the orders described here, but the source constants should not be treated as independently verified.
For period \(H=1\), the tuning gives \(\gamma=1\), whereas the base definition requires \(\gamma\in(0,1)\). The text read does not separately specify endpoint handling for the one-round expert. An implementation should supply a convention rather than silently assuming that the barrier construction is valid at this endpoint.

vs Sherman–Koren's Lazy OCO: Existing FPRLL primarily controls static regret and switching budgets. This paper retains its density and coupling tools but obtains local and dynamic guarantees through multiscale restarts and a meta layer.
vs Revisiting Smoothed Online Learning: Norm-based costs already admit the path guarantee \(\mathcal{O}(\sqrt{T(1+P_T)})\). This paper imposes the stronger stability requirement of paying for every change and uses TV aggregation, but its path rate remains weaker.
vs Daniely–Mansour: The discounted-normal predictor supplies a movement-aware strongly adaptive experts tool. The new connection is reducing general convex-action density problems to this finite-experts problem, rather than reinventing the entire meta-learner.
Research direction: Couplable base distributions without smooth-Hessian requirements or tighter path-variation analyses are possible directions. Assessing improvements to the path rate requires distinguishing algorithm-family obstacles from general indicator-cost obstacles. These are prospective directions, not conclusions proved in the paper.

Rating¶

Novelty: 4/5 — Connects indicator switching control with dynamic and strongly adaptive regret through a clear reduction.
Experimental Thoroughness: Not applicable — A purely theoretical paper without empirical experiments; the main text and appendices provide upper- and lower-bound proofs.
Writing Quality: 4/5 — The main argument and proof layers are clear, but some constants, endpoints, and adversarial scope require careful interpretation.
Value: 4/5 — Provides theoretical tools for fixed reconfiguration overhead; path optimality and efficient implementation remain unresolved.