Publications

Citation

BibTex format

@article{Huang:2017,
author = {Huang, R and Lattimore, T and Gyorgy, A and Szepesvari, C},
journal = {Journal of Machine Learning Research},
pages = {1--31},
title = {Following the Leader and Fast Rates in Online Linear Prediction: Curved Constraint Sets and Other Regularities},
url = {http://jmlr.org/papers/v18/17-079.html},
volume = {18(145)},
year = {2017}
}
Download

RIS format (EndNote, RefMan)

TY  - JOUR
AB  - Follow the leader (FTL) is a simple online learning algorithm that is known to perform well whenthe loss functions are convex and positively curved. In this paper we ask whether there are othersettings when FTL achieves low regret. In particular, we study the fundamental problem of linearprediction over a convex, compact domain with non-empty interior. Amongst other results, weprove that the curvature of the boundary of the domain can act as if the losses were curved: In thiscase, we prove that as long as the mean of the loss vectors have positive lengths bounded away fromzero, FTL enjoys logarithmic regret, while for polytope domains and stochastic data it enjoys finiteexpected regret. The former result is also extended to strongly convex domains by establishing anequivalence between the strong convexity of sets and the minimum curvature of their boundary,which may be of independent interest. Building on a previously known meta-algorithm, we alsoget an algorithm that simultaneously enjoys the worst-case guarantees and the smaller regret ofFTL when the data is ‘easy’. Finally, we show that such guarantees are achievable directly (e.g.,by the follow the regularized leader algorithm or by a shrinkage-based variant of FTL) when theconstraint set is an ellipsoid.
AU  - Huang,R
AU  - Lattimore,T
AU  - Gyorgy,A
AU  - Szepesvari,C
EP  - 31
PY  - 2017///
SN  - 1532-4435
SP  - 1
TI  - Following the Leader and Fast Rates in Online Linear Prediction: Curved Constraint Sets and Other Regularities
T2  - Journal of Machine Learning Research
UR  - http://jmlr.org/papers/v18/17-079.html
UR  - http://hdl.handle.net/10044/1/55686
VL  - 18(145)
ER  -
Download