Papers for

online advertising optimizers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Dynamic portfolio method matches changing benchmarks with fewer errors

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.

Mon 28 SeptMachine Learning
The gist
This paper studies how to create investment strategies that can adapt and do well compared to the best changing benchmarks over time. The authors show that common methods struggle because they only measure how much these benchmarks change in a simple way. To fix this, they introduce new ways to measure changes that capture more detailed patterns, allowing for better performance. They also build a new algorithm, called Universal Dynamic Portfolio, that works well without tuning and balances different measures of change. Finally, they show that under some conditions, even faster adaptation is possible for a wider set of problems.
Open → 2609.34643v1