betaFeedback

WorksComputer Science

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

Abstract

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 O(UTlog⁡(UTlog⁡2T+1))\mathcal{O}\Big(U \sqrt{T \log(U \sqrt{T} \log^2 T +1)}\Big), where UU is the L2L_2 norm of an arbitrary comparator and both TT and UU are unknown to the player. This bound is optimal up to log⁡log⁡T\sqrt{\log \log T} terms. When TT is known, we derive an algorithm with an optimal regret bound (up to constant factors). For both the known and unknown TT case, a Normal approximation to the conditional value of the game proves to be the key analysis tool.

Paper details

vlnc:W_xbx4f9am
Version
v1 · latest
Published
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…