Unconstrained Online Linear Learning in Hilbert Spaces: Minimax Algorithms and Normal Approximations

Understand

We study algorithms for online linear optimization in Hilbert spaces, focusing on the case where the player is unconstrained.

• We develop a novel characterization of a large class of minimax algorithms, recovering, and even improving, several previous results as immediate corollaries.
• Moreover, using our tools, we develop an algorithm that provides a regret bound of $\mathcal{O}\Big(U \sqrt{T \log(U \sqrt{T} \log^2 T +1)}\Big)$, where $U$ is the $L_2$ norm of an arbitrary comparator and both $T$ and $U$ are unknown to the player.
• This bound is optimal up to $\sqrt{\log \log T}$ terms.