Timezone: »

Affine-Invariant Online Optimization and the Low-rank Experts Problem
Tomer Koren · Roi Livni

Wed Dec 06 06:30 PM -- 10:30 PM (PST) @ Pacific Ballroom #54
We present a new affine-invariant optimization algorithm called Online Lazy Newton. The regret of Online Lazy Newton is independent of conditioning: the algorithm's performance depends on the best possible preconditioning of the problem in retrospect and on its \emph{intrinsic} dimensionality. As an application, we show how Online Lazy Newton can be used to achieve an optimal regret of order $\sqrt{rT}$ for the low-rank experts problem, improving by a $\sqrt{r}$ factor over the previously best known bound and resolving an open problem posed by Hazan et al (2016).

Author Information

Tomer Koren (Google)
Roi Livni (Princeton)

More from the Same Authors