On Equivalence of Martingale Tail Bounds and Deterministic Regret Inequalities

Alexander Rakhlin, Karthik Sridharan
Proceedings of the 2017 Conference on Learning Theory, PMLR 65:1704-1722, 2017.

Abstract

We study an equivalence of (i) deterministic pathwise statements appearing in the online learning literature (termed \emphregret bounds), (ii) high-probability tail bounds for the supremum of a collection of martingales (of a specific form arising from uniform laws of large numbers), and (iii) in-expectation bounds for the supremum. By virtue of the equivalence, we prove exponential tail bounds for norms of Banach space valued martingales via deterministic regret bounds for the online mirror descent algorithm with an adaptive step size. We show that the phenomenon extends beyond the setting of online linear optimization and present the equivalence for the supervised online learning setting.

Cite this Paper

BibTeX
@InProceedings{pmlr-v65-rakhlin17a, title = {On Equivalence of Martingale Tail Bounds and Deterministic Regret Inequalities}, author = {Rakhlin, Alexander and Sridharan, Karthik}, booktitle = {Proceedings of the 2017 Conference on Learning Theory}, pages = {1704--1722}, year = {2017}, editor = {Kale, Satyen and Shamir, Ohad}, volume = {65}, series = {Proceedings of Machine Learning Research}, month = {07--10 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v65/rakhlin17a/rakhlin17a.pdf}, url = {https://proceedings.mlr.press/v65/rakhlin17a.html}, abstract = {We study an equivalence of (i) deterministic pathwise statements appearing in the online learning literature (termed \emphregret bounds), (ii) high-probability tail bounds for the supremum of a collection of martingales (of a specific form arising from uniform laws of large numbers), and (iii) in-expectation bounds for the supremum. By virtue of the equivalence, we prove exponential tail bounds for norms of Banach space valued martingales via deterministic regret bounds for the online mirror descent algorithm with an adaptive step size. We show that the phenomenon extends beyond the setting of online linear optimization and present the equivalence for the supervised online learning setting. } }
Endnote
%0 Conference Paper %T On Equivalence of Martingale Tail Bounds and Deterministic Regret Inequalities %A Alexander Rakhlin %A Karthik Sridharan %B Proceedings of the 2017 Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2017 %E Satyen Kale %E Ohad Shamir %F pmlr-v65-rakhlin17a %I PMLR %P 1704--1722 %U https://proceedings.mlr.press/v65/rakhlin17a.html %V 65 %X We study an equivalence of (i) deterministic pathwise statements appearing in the online learning literature (termed \emphregret bounds), (ii) high-probability tail bounds for the supremum of a collection of martingales (of a specific form arising from uniform laws of large numbers), and (iii) in-expectation bounds for the supremum. By virtue of the equivalence, we prove exponential tail bounds for norms of Banach space valued martingales via deterministic regret bounds for the online mirror descent algorithm with an adaptive step size. We show that the phenomenon extends beyond the setting of online linear optimization and present the equivalence for the supervised online learning setting.
APA
Rakhlin, A. & Sridharan, K.. (2017). On Equivalence of Martingale Tail Bounds and Deterministic Regret Inequalities. Proceedings of the 2017 Conference on Learning Theory, in Proceedings of Machine Learning Research 65:1704-1722 Available from https://proceedings.mlr.press/v65/rakhlin17a.html.

Related Material