Improving Adaptive Online Learning Using Refined Discretization

arXiv:2309.16044v2 Announce Type: replace
Abstract: We study unconstrained Online Linear Optimization with Lipschitz losses. Motivated by the pursuit of instance optimality, we propose a new algorithm that simultaneously achieves ($i$) the AdaGrad-style second order gradient adaptivity; and ($ii$) the comparator norm adaptivity also known as "parameter freeness" in the literature. In particular,
- our algorithm does not employ the impractical doubling trick, and does not require an a priori estimate of the time-uniform Lipschitz constant;
- the associated regret bound …

abstract algorithm arxiv cs.lg gradient instance linear literature losses norm online learning optimization stat.ml study style type