Timezone: »

 
Poster
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
in Posters Wed »
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).
Keywords: Online Learning · Optimization
[ Paper] 

Author Information

Tomer Koren (Google)
Roi Livni (Princeton)

More from the Same Authors