Optimal Parameter-free Online Learning with Switching Cost

Zhiyu Zhang, Ashok Cutkosky, Ioannis Ch. Paschalidis

Abstract

Parameter-freeness in online learning refers to the ability of an algorithm to adapt to the optimal decision in hindsight without prior knowledge of its scale. However, achieving this adaptivity often results in high volatility, which is penalized in settings with switching costs. This paper introduces a novel dual space scaling strategy, derived from continuous-time PDE analysis, to design the first optimal parameter-free algorithms for Online Linear Optimization (OLO) and the expert setting under switching costs. We demonstrate that our approach achieves the theoretical lower bounds for regret and outperforms existing methods in sequential investment tasks.

Introduction

In the framework of online learning, an agent iteratively makes predictions to minimize regret—the difference between its cumulative loss and that of the best fixed decision $u^*$ in hindsight. Traditional algorithms often require a learning rate tuned to the norm of $u^*$, which is typically unknown. "Parameter-free" or "comparator-adaptive" algorithms solve this by automatically adapting to the scale of $u^*$.

While powerful, these adaptive algorithms are inherently "aggressive," frequently making large updates to quickly identify the optimal decision. In many practical applications, such as portfolio management with transaction fees or robotic control, these rapid changes incur a "switching cost." The fundamental challenge lies in balancing the need for fast adaptivity with the requirement for smooth transitions. Previous attempts to reconcile these goals resulted in suboptimal regret bounds. This paper bridges that gap, achieving the theoretical "gold standard" for regret in both linear optimization and expert advice settings.

Methodology: Dual Space Scaling

The authors move beyond the standard "coin-betting" paradigms often used in parameter-free literature, instead employing a Potential Function framework informed by continuous-time analysis.

Continuous-Time PDE Analysis

By analyzing the problem in a continuous-time limit, the discrete updates of online learning are modeled as a Partial Differential Equation (PDE)—specifically a variation of the backward heat equation. This analysis revealed that switching costs effectively alter the "thermal diffusivity" ($\alpha$) of the learning process. This perspective allows for the discovery of algorithmic structures that would be difficult to derive through discrete-time analysis alone.

Dual Space Scaling

The core innovation is Dual Space Scaling. In standard gradient descent, scaling the learning rate is mathematically equivalent to scaling the output (primal space). However, in the context of adaptive learning, these operations diverge. The authors discovered that scaling the "dual space"—the space of accumulated gradients—allows the algorithm to maintain optimal adaptivity while suppressing the excessive movement that triggers high switching costs.

Extension to Expert Advice

Transitioning from Online Linear Optimization (OLO) to Learning with Expert Advice (LEA) usually introduces discontinuities near zero, which can cause switching costs to explode. To mitigate this, the authors developed a conversion method based on an $L_1$ orthogonal projection. This ensures smooth transitions between expert weights even when certain weights are near zero, maintaining the efficiency of the adaptive strategy.

Experimental Evaluation

The proposed algorithm was tested against existing benchmarks, including the previously suboptimal state-of-the-art (ZCP22a), across two main environments:

  1. Synthetic Markets: A five-asset simulation incorporating i.i.d. noise, periodic sine wave fluctuations, and constant trends to test the algorithm's ability to capture diverse signals.
  2. Historical US Stock Data: A five-year dataset (2013–2018) comprising eight major stocks: Apple (AAPL), Berkshire Hathaway (BRK.B), Meta (FB), Johnson & Johnson (JNJ), JPMorgan Chase (JPM), Microsoft (MSFT), Pfizer (PFE), and Exxon Mobil (XOM).

Key Results

  • Theoretical Optimality: The algorithm achieves a regret bound of $O(\sqrt{T \log(|u|T)})$, matching the known lower bounds for adaptive learning without switching costs. This proves that switching costs do not necessarily degrade the asymptotic performance of parameter-free learners.
  • Empirical Performance: In portfolio simulations, the algorithm consistently outperformed baselines. It demonstrated a superior ability to identify market trends quickly without being over-penalized by transaction costs. It was notably less "conservative" than prior adaptive methods.
  • Robustness to Penalty: As the switching cost penalty ($\lambda$) increased, the performance gap between the proposed algorithm and its predecessors widened, highlighting the effectiveness of the dual space scaling approach in high-cost environments.
  • Improved Expert Bounds: For the experts setting, the research improved the standard $\sqrt{KL}$ regret bound to a $\sqrt{TV \cdot KL}$ bound (where TV is Total Variation), indicating better performance when the prior distribution is close to the optimal one.

Conclusion and Future Work

This work provides a principled way to achieve optimal regret in adaptive online learning under practical switching cost constraints. By utilizing PDE-based design and dual space scaling, the authors offer a robust framework for sequential decision-making.

Future research directions include extending these bounds to constrained settings (e.g., budget-constrained portfolio management where shorting is not allowed), exploring self-financing rebalancing strategies, and addressing non-convex losses or more complex, history-dependent adversaries common in non-stochastic control.

Summary updated

Abstract

Parameter-freeness in online learning refers to the adaptivity of an algorithm with respect to the optimal decision in hindsight. In this paper, we design such algorithms in the presence of switching cost - the latter penalizes the optimistic updates required by parameter-freeness, leading to a delicate design trade-off. Based on a novel dual space scaling strategy, we propose a simple yet powerful algorithm for Online Linear Optimization (OLO) with switching cost, which improves the existing suboptimal regret bound [ZCP22a] to the optimal rate. The obtained benefit is extended to the expert setting, and the practicality of our algorithm is demonstrated through a sequential investment task.
BibTeX
@inproceedings{zhang2022optimal,
  author = {Zhiyu Zhang and Ashok Cutkosky and Ioannis Ch. Paschalidis},
  title = {{Optimal Parameter-free Online Learning with Switching Cost}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=zP8-6ByNqvL},
}
Figure