Dynamic Regret in Online Convex Optimization with Indicator Switching Costs

arXiv:2609.30556v1 Announce Type: new 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, R^{mathbf{1}}_T le ilde{O}(min{sqrt{T(S_T{+}1)},T^{2/3}(P_T+1)^{1/3}}), where R^{mathbf{1}}_T is the dynamic regret plus the cumulative indicator switching cost, S_T counts comparator switches, and P_T is the comparator path length. The bound holds simultaneously for all sequences and requires no prior knowledge of S_T or P_T: it is minimax-optimal (up to logarithmic factors) for tracking piecewise-constant comparators, and also captures frequently moving comparators with small total path length.

Related

• Minimax Alternating Regret for the Experts Problem and Online Convex Optimization
• Dynamic Regret for Online Regression in RKHS via Discounted VAW and Subspace Approximation
• From Switching to Dynamic Regret: A Simple Reduction via Unbiased Random Sequences

Source: arXiv cs.LG | 2026-09-28