Universal Dynamic Portfolios

Abstract

Cover's Universal Portfolio (Cover, 1991) matches the performance of the best constant rebalanced portfolio in hindsight. We generalize this framework to compete with an arbitrary comparator sequence $\mathbf{u}_1,\ldots,\mathbf{u}_T$, leading to a dynamic regret minimization problem for the log loss where existing methods break down due to potentially unbounded gradients. The log loss is exp-concave, a curvature property that classically yields fast rates for static regret, yet we show that this advantage generally disappears in the dynamic setting. In particular, a linear-loss-type $\sqrt{TP_T}$ dependence is unavoidable, where $P_T=\sum_{t=2}^T\lVert\mathbf{u}_t-\mathbf{u}_{t-1}\rVert_1$ is the standard path length. This limitation stems from the coarse nature of $P_T$, which obscures finer spatial and temporal structure of the comparator sequence. We therefore introduce two structure-aware measures---the Jensen-Shannon distance for spatial structure and the JS$^q$-path length for temporal structure---under which faster rates are attainable when the comparator sequence has favorable structure. To achieve sharp bounds for both measures simultaneously, we develop Universal Dynamic Portfolio, a parameter-free method that combines a new Dirichlet Hedge algorithm with a fixed-share update, while retaining a near-optimal $P_T$ guarantee in the worst case. Finally, under an additional bounded-gradient assumption, we show that OPS admits the faster $T^{1/3}P_T^{2/3}$ dynamic regret rate over all comparator sequences. We attain this rate with a tractable proper algorithm that applies more broadly to general online exp-concave optimization over arbitrary compact convex domains.

Keywords

Subject