Optimal Comparator Adaptive Online Learning with Switching Cost

Zhiyu Zhang, Ashok Cutkosky, Yannis Paschalidis

Introduction: The Cost of Changing Your Mind

In standard online learning, an algorithm makes a sequence of predictions and incurs a loss based on the environment's response. Classical algorithms, such as Online Gradient Descent, are typically tuned for worst-case scenarios on bounded domains, yielding conservative $\mathcal{O}(\sqrt{T})$ regret bounds.

"Comparator adaptive" (or parameter-free) algorithms offer a powerful alternative. They adapt to the unknown distance to the best fixed decision in hindsight ($u^*$), learning significantly faster when the optimal decision is close to the initial guess. However, this adaptivity comes at a price: the algorithms hedge aggressively, causing predictions to swing wildly from step to step.

In real-world applications, this erratic behavior is often a dealbreaker due to switching costs—such as transaction fees in stock trading or mechanical wear-and-tear in robotic control. Previous attempts to combine comparator adaptivity with switching costs forced a hard trade-off, resulting in suboptimal regret bounds. This paper bridges that gap, presenting the first optimal, comparator-adaptive algorithms for both Online Linear Optimization (OLO) and Learning with Expert Advice (LEA) that explicitly account for switching costs.

Methodological Breakthrough: Dual Space Scaling via PDEs

To achieve optimality, the authors step away from the traditional "coin-betting" framework, which relies on hard-thresholding that breaks down when switching costs are introduced. Instead, they utilize a potential function framework—the dual approach to Follow the Regularized Leader.

The core methodological breakthrough is Dual Space Scaling, discovered through a novel continuous-time analysis:

  1. Continuous-Time PDE Modeling: By modeling the discrete step-by-step online learning game as a continuous-time process, the authors reveal that adding a switching cost $\lambda$ effectively increases the "thermal diffusivity" parameter in a backward heat equation.
  2. The Dual Space Trick: Solving this Partial Differential Equation (PDE) demonstrates that optimally handling switching costs requires more than just scaling down predictions (the primal space). Instead, the algorithm must scale the sufficient statistic—the accumulated gradients, or the dual space—fed into the potential function. While primal and dual scaling are mathematically equivalent in standard gradient descent, scaling the dual space is the secret to maintaining optimal adaptivity while suppressing switching costs in complex, adaptive potential functions.

Extending to Learning with Expert Advice (LEA)

Extending these benefits to LEA required addressing a critical geometric flaw in standard OLO-to-LEA conversions. Typically, algorithms project weights onto a probability simplex by dividing by the $L_1$ norm. However, if the weights are near zero, this normalization causes massive, erratic jumps, severely penalizing the algorithm under switching costs.

The authors resolve this by recognizing the non-uniqueness of $L_1$ norm projections. They introduce a geometric fix: using an orthogonal projection when the $L_1$ norm is less than 1. This keeps switching costs strictly controlled and enables the first comparator-adaptive algorithm for LEA with switching costs.

Key Results and Theoretical Guarantees

The proposed algorithms achieve state-of-the-art theoretical guarantees, which are also validated in practice through a sequential investment (portfolio management) task using financial data.

  • Optimal 1D OLO: The algorithm achieves an augmented regret bound of $\mathcal{O}(\sqrt{\lambda T} + |u|\sqrt{\lambda T \log(|u|)})$. This hits the Pareto-optimal frontier for the loss-regret trade-off, perfectly matching theoretical lower bounds.
  • A Tighter Divergence Bound: As a significant bonus, even without switching costs, the new LEA algorithm improves the classical $\sqrt{\text{KL}}$ divergence bound to $\sqrt{\text{TV} \cdot \text{KL}}$ (Total Variation times Kullback-Leibler). Because Total Variation is always $\le 1$, this bound is strictly tighter and can save a $(\log d)^{1/4}$ factor in environments with a large number of experts.

Limitations and Future Directions

While the continuous-time PDE provides elegant intuition, translating it back to a rigorous discrete-time algorithm introduces a slight "discretization gap." The authors must use a slightly conservative parameter choice (setting $\alpha = 4\lambda + 2$ instead of the exact PDE suggestion) to ensure the mathematical guarantees hold against any adversary. Additionally, while higher-dimensional and bounded domain extensions are provided, the primary text focuses heavily on 1D unconstrained settings.

Looking forward, achieving comparator adaptivity with switching costs serves as a crucial stepping stone. The authors suggest these techniques could significantly improve algorithms in downstream tasks with long-term effects, such as non-stochastic control and dynamical systems.

Summary updated

Abstract

Practical online learning tasks are often naturally defined on unconstrained domains, where optimal algorithms for general convex losses are characterized by the notion of comparator adaptivity. In this paper, we design such algorithms in the presence of switching cost - the latter penalizes the typical optimism in adaptive algorithms, leading to a delicate design trade-off. Based on a novel dual space scaling strategy discovered by a continuous-time analysis, we propose a simple algorithm that improves the existing comparator adaptive regret bound [ZCP22a] to the optimal rate. The obtained benefits are further extended to the expert setting, and the practicality of the proposed algorithm is demonstrated through a sequential investment task.
BibTeX
@inproceedings{zhang2022optimal,
  author = {Zhiyu Zhang and Ashok Cutkosky and Yannis Paschalidis},
  title = {{Optimal Comparator Adaptive Online Learning with Switching Cost}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=zP8-6ByNqvL},
}
Figure