PDE-Based Optimal Strategy for Unconstrained Online Learning

Zhiyu Zhang, Ashok Cutkosky, Ioannis Paschalidis
Proceedings of the 39th International Conference on Machine Learning, PMLR 162:26085-26115, 2022.

Abstract

Unconstrained Online Linear Optimization (OLO) is a practical problem setting to study the training of machine learning models. Existing works proposed a number of potential-based algorithms, but in general the design of these potential functions relies heavily on guessing. To streamline this workflow, we present a framework that generates new potential functions by solving a Partial Differential Equation (PDE). Specifically, when losses are 1-Lipschitz, our framework produces a novel algorithm with anytime regret bound CT+||u||2T[log(1+||u||/C)+2], where C is a user-specified constant and u is any comparator unknown and unbounded a priori. Such a bound attains an optimal loss-regret trade-off without the impractical doubling trick. Moreover, a matching lower bound shows that the leading order term, including the constant multiplier 2, is tight. To our knowledge, the proposed algorithm is the first to achieve such optimalities.

Cite this Paper


BibTeX
@InProceedings{pmlr-v162-zhang22d, title = {{PDE}-Based Optimal Strategy for Unconstrained Online Learning}, author = {Zhang, Zhiyu and Cutkosky, Ashok and Paschalidis, Ioannis}, booktitle = {Proceedings of the 39th International Conference on Machine Learning}, pages = {26085--26115}, year = {2022}, editor = {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan}, volume = {162}, series = {Proceedings of Machine Learning Research}, month = {17--23 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v162/zhang22d/zhang22d.pdf}, url = {https://proceedings.mlr.press/v162/zhang22d.html}, abstract = {Unconstrained Online Linear Optimization (OLO) is a practical problem setting to study the training of machine learning models. Existing works proposed a number of potential-based algorithms, but in general the design of these potential functions relies heavily on guessing. To streamline this workflow, we present a framework that generates new potential functions by solving a Partial Differential Equation (PDE). Specifically, when losses are 1-Lipschitz, our framework produces a novel algorithm with anytime regret bound $C\sqrt{T}+||u||\sqrt{2T}[\sqrt{\log(1+||u||/C)}+2]$, where $C$ is a user-specified constant and $u$ is any comparator unknown and unbounded a priori. Such a bound attains an optimal loss-regret trade-off without the impractical doubling trick. Moreover, a matching lower bound shows that the leading order term, including the constant multiplier $\sqrt{2}$, is tight. To our knowledge, the proposed algorithm is the first to achieve such optimalities.} }
Endnote
%0 Conference Paper %T PDE-Based Optimal Strategy for Unconstrained Online Learning %A Zhiyu Zhang %A Ashok Cutkosky %A Ioannis Paschalidis %B Proceedings of the 39th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2022 %E Kamalika Chaudhuri %E Stefanie Jegelka %E Le Song %E Csaba Szepesvari %E Gang Niu %E Sivan Sabato %F pmlr-v162-zhang22d %I PMLR %P 26085--26115 %U https://proceedings.mlr.press/v162/zhang22d.html %V 162 %X Unconstrained Online Linear Optimization (OLO) is a practical problem setting to study the training of machine learning models. Existing works proposed a number of potential-based algorithms, but in general the design of these potential functions relies heavily on guessing. To streamline this workflow, we present a framework that generates new potential functions by solving a Partial Differential Equation (PDE). Specifically, when losses are 1-Lipschitz, our framework produces a novel algorithm with anytime regret bound $C\sqrt{T}+||u||\sqrt{2T}[\sqrt{\log(1+||u||/C)}+2]$, where $C$ is a user-specified constant and $u$ is any comparator unknown and unbounded a priori. Such a bound attains an optimal loss-regret trade-off without the impractical doubling trick. Moreover, a matching lower bound shows that the leading order term, including the constant multiplier $\sqrt{2}$, is tight. To our knowledge, the proposed algorithm is the first to achieve such optimalities.
APA
Zhang, Z., Cutkosky, A. & Paschalidis, I.. (2022). PDE-Based Optimal Strategy for Unconstrained Online Learning. Proceedings of the 39th International Conference on Machine Learning, in Proceedings of Machine Learning Research 162:26085-26115 Available from https://proceedings.mlr.press/v162/zhang22d.html.

Related Material