Unified Algorithms for Online Learning and Competitive Analysis

Niv Buchbinder, Shahar Chen, Joshep (Seffi) Naor, Ohad Shamir
Proceedings of the 25th Annual Conference on Learning Theory, PMLR 23:5.1-5.18, 2012.

Abstract

Online learning and competitive analysis are two widely studied frameworks for online decisionmaking settings. Despite the frequent similarity of the problems they study, there are significant differences in their assumptions, goals and techniques, hindering a unified analysis and richer interplay between the two. In this paper, we provide several contributions in this direction. We provide a single unified algorithm which by parameter tuning, interpolates between optimal regret for learning from experts (in online learning) and optimal competitive ratio for the metrical task systems problem (MTS) (in competitive analysis), improving on the results of Blum and Burch (1997). The algorithm also allows us to obtain new regret bounds against “drifting” experts, which might be of independent interest. Moreover, our approach allows us to go beyond experts/MTS, obtaining similar unifying results for structured action sets and “combinatorial experts", whenever the setting has a certain matroid structure.

Cite this Paper

BibTeX
@InProceedings{pmlr-v23-buchbinder12, title = {Unified Algorithms for Online Learning and Competitive Analysis}, author = {Buchbinder, Niv and Chen, Shahar and Naor, Joshep (Seffi) and Shamir, Ohad}, booktitle = {Proceedings of the 25th Annual Conference on Learning Theory}, pages = {5.1--5.18}, year = {2012}, editor = {Mannor, Shie and Srebro, Nathan and Williamson, Robert C.}, volume = {23}, series = {Proceedings of Machine Learning Research}, address = {Edinburgh, Scotland}, month = {25--27 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v23/buchbinder12/buchbinder12.pdf}, url = {https://proceedings.mlr.press/v23/buchbinder12.html}, abstract = {Online learning and competitive analysis are two widely studied frameworks for online decisionmaking settings. Despite the frequent similarity of the problems they study, there are significant differences in their assumptions, goals and techniques, hindering a unified analysis and richer interplay between the two. In this paper, we provide several contributions in this direction. We provide a single unified algorithm which by parameter tuning, interpolates between optimal regret for learning from experts (in online learning) and optimal competitive ratio for the metrical task systems problem (MTS) (in competitive analysis), improving on the results of Blum and Burch (1997). The algorithm also allows us to obtain new regret bounds against “drifting” experts, which might be of independent interest. Moreover, our approach allows us to go beyond experts/MTS, obtaining similar unifying results for structured action sets and “combinatorial experts", whenever the setting has a certain matroid structure.} }
Endnote
%0 Conference Paper %T Unified Algorithms for Online Learning and Competitive Analysis %A Niv Buchbinder %A Shahar Chen %A Joshep (Seffi) Naor %A Ohad Shamir %B Proceedings of the 25th Annual Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2012 %E Shie Mannor %E Nathan Srebro %E Robert C. Williamson %F pmlr-v23-buchbinder12 %I PMLR %P 5.1--5.18 %U https://proceedings.mlr.press/v23/buchbinder12.html %V 23 %X Online learning and competitive analysis are two widely studied frameworks for online decisionmaking settings. Despite the frequent similarity of the problems they study, there are significant differences in their assumptions, goals and techniques, hindering a unified analysis and richer interplay between the two. In this paper, we provide several contributions in this direction. We provide a single unified algorithm which by parameter tuning, interpolates between optimal regret for learning from experts (in online learning) and optimal competitive ratio for the metrical task systems problem (MTS) (in competitive analysis), improving on the results of Blum and Burch (1997). The algorithm also allows us to obtain new regret bounds against “drifting” experts, which might be of independent interest. Moreover, our approach allows us to go beyond experts/MTS, obtaining similar unifying results for structured action sets and “combinatorial experts", whenever the setting has a certain matroid structure.
RIS
TY - CPAPER TI - Unified Algorithms for Online Learning and Competitive Analysis AU - Niv Buchbinder AU - Shahar Chen AU - Joshep (Seffi) Naor AU - Ohad Shamir BT - Proceedings of the 25th Annual Conference on Learning Theory DA - 2012/06/16 ED - Shie Mannor ED - Nathan Srebro ED - Robert C. Williamson ID - pmlr-v23-buchbinder12 PB - PMLR DP - Proceedings of Machine Learning Research VL - 23 SP - 5.1 EP - 5.18 L1 - http://proceedings.mlr.press/v23/buchbinder12/buchbinder12.pdf UR - https://proceedings.mlr.press/v23/buchbinder12.html AB - Online learning and competitive analysis are two widely studied frameworks for online decisionmaking settings. Despite the frequent similarity of the problems they study, there are significant differences in their assumptions, goals and techniques, hindering a unified analysis and richer interplay between the two. In this paper, we provide several contributions in this direction. We provide a single unified algorithm which by parameter tuning, interpolates between optimal regret for learning from experts (in online learning) and optimal competitive ratio for the metrical task systems problem (MTS) (in competitive analysis), improving on the results of Blum and Burch (1997). The algorithm also allows us to obtain new regret bounds against “drifting” experts, which might be of independent interest. Moreover, our approach allows us to go beyond experts/MTS, obtaining similar unifying results for structured action sets and “combinatorial experts", whenever the setting has a certain matroid structure. ER -
APA
Buchbinder, N., Chen, S., Naor, J.(. & Shamir, O.. (2012). Unified Algorithms for Online Learning and Competitive Analysis. Proceedings of the 25th Annual Conference on Learning Theory, in Proceedings of Machine Learning Research 23:5.1-5.18 Available from https://proceedings.mlr.press/v23/buchbinder12.html.

Related Material