@inproceedings{Huang:2016,
author = {Huang, R and Lattimore, T and Gyorgy, A and Szepesvari, C},
publisher = {Neutral Information Processing Systems Foundation, Inc.},
title = {Following the Leader and Fast Rates in Linear Prediction: Curved Constraint Sets and Other Regularities},
url = {http://hdl.handle.net/10044/1/42313},
year = {2016}
}

Download

TY  - CPAPER
AB  - The follow the leader (FTL) algorithm, perhaps the simplest of all online learningalgorithms, is known to perform well when the loss functions it is used on are positivelycurved. In this paper we ask whether there are other “lucky” settings whenFTL achieves sublinear, “small” regret. In particular, we study the fundamentalproblem of linear prediction over a non-empty convex, compact domain. Amongstother results, we prove that the curvature of the boundary of the domain can act asif the losses were curved: In this case, we prove that as long as the mean of the lossvectors have positive lengths bounded away from zero, FTL enjoys a logarithmicgrowth rate of regret, while, e.g., for polyhedral domains and stochastic data itenjoys finite expected regret. Building on a previously known meta-algorithm, wealso get an algorithm that simultaneously enjoys the worst-case guarantees and thebound available for FTL.
AU  - Huang,R
AU  - Lattimore,T
AU  - Gyorgy,A
AU  - Szepesvari,C
PB  - Neutral Information Processing Systems Foundation, Inc.
PY  - 2016///
TI  - Following the Leader and Fast Rates in Linear Prediction: Curved Constraint Sets and Other Regularities
UR  - http://hdl.handle.net/10044/1/42313
ER  - 

Download