Lipschitz and Comparator-Norm Adaptivity in Online Learning

Zakaria Mhammedi, Wouter M. Koolen
Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:2858-2887, 2020.

Abstract

We study Online Convex Optimization in the unbounded setting where neither predictions nor gradient are constrained. The goal is to simultaneously adapt to both the sequence of gradients and the comparator. We first develop parameter-free and scale-free algorithms for a simplified setting with hints. We present two versions: the first adapts to the squared norms of both comparator and gradients separately using $O(d)$ time per round, the second adapts to their squared inner products (which measure variance only in the comparator direction) in time $O(d^3)$ per round. We then generalize two prior reductions to the unbounded setting; one to not need hints, and a second to deal with the range ratio problem (which already arises in prior work). We discuss their optimality in light of prior and new lower bounds. We apply our methods to obtain sharper regret bounds for scale-invariant online prediction with linear models.

Cite this Paper

BibTeX
@InProceedings{pmlr-v125-mhammedi20a, title = {Lipschitz and Comparator-Norm Adaptivity in Online Learning}, author = {Mhammedi, Zakaria and Koolen, Wouter M.}, booktitle = {Proceedings of Thirty Third Conference on Learning Theory}, pages = {2858--2887}, year = {2020}, editor = {Abernethy, Jacob and Agarwal, Shivani}, volume = {125}, series = {Proceedings of Machine Learning Research}, month = {09--12 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v125/mhammedi20a/mhammedi20a.pdf}, url = {https://proceedings.mlr.press/v125/mhammedi20a.html}, abstract = { We study Online Convex Optimization in the unbounded setting where neither predictions nor gradient are constrained. The goal is to simultaneously adapt to both the sequence of gradients and the comparator. We first develop parameter-free and scale-free algorithms for a simplified setting with hints. We present two versions: the first adapts to the squared norms of both comparator and gradients separately using $O(d)$ time per round, the second adapts to their squared inner products (which measure variance only in the comparator direction) in time $O(d^3)$ per round. We then generalize two prior reductions to the unbounded setting; one to not need hints, and a second to deal with the range ratio problem (which already arises in prior work). We discuss their optimality in light of prior and new lower bounds. We apply our methods to obtain sharper regret bounds for scale-invariant online prediction with linear models. } }
Endnote
%0 Conference Paper %T Lipschitz and Comparator-Norm Adaptivity in Online Learning %A Zakaria Mhammedi %A Wouter M. Koolen %B Proceedings of Thirty Third Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2020 %E Jacob Abernethy %E Shivani Agarwal %F pmlr-v125-mhammedi20a %I PMLR %P 2858--2887 %U https://proceedings.mlr.press/v125/mhammedi20a.html %V 125 %X We study Online Convex Optimization in the unbounded setting where neither predictions nor gradient are constrained. The goal is to simultaneously adapt to both the sequence of gradients and the comparator. We first develop parameter-free and scale-free algorithms for a simplified setting with hints. We present two versions: the first adapts to the squared norms of both comparator and gradients separately using $O(d)$ time per round, the second adapts to their squared inner products (which measure variance only in the comparator direction) in time $O(d^3)$ per round. We then generalize two prior reductions to the unbounded setting; one to not need hints, and a second to deal with the range ratio problem (which already arises in prior work). We discuss their optimality in light of prior and new lower bounds. We apply our methods to obtain sharper regret bounds for scale-invariant online prediction with linear models.
APA
Mhammedi, Z. & Koolen, W.M.. (2020). Lipschitz and Comparator-Norm Adaptivity in Online Learning. Proceedings of Thirty Third Conference on Learning Theory, in Proceedings of Machine Learning Research 125:2858-2887 Available from https://proceedings.mlr.press/v125/mhammedi20a.html.

Related Material