Volumetric Spanners: an Efficient Exploration Basis for Learning

Elad Hazan, Zohar Karnin, Raghu Meka
Proceedings of The 27th Conference on Learning Theory, PMLR 35:408-422, 2014.

Abstract

Numerous machine learning problems require an \it exploration basis - a mechanism to explore the action space. We define a novel geometric notion of exploration basis with low variance called volumetric spanners, and give efficient algorithms to construct such bases. We show how efficient volumetric spanners give rise to an efficient and near-optimal regret algorithm for bandit linear optimization over general convex sets. Previously such results were known only for specific convex sets, or under special conditions such as the existence of an efficient self-concordant barrier for the underlying set.

Cite this Paper

BibTeX
@InProceedings{pmlr-v35-hazan14b, title = {Volumetric Spanners: an Efficient Exploration Basis for Learning }, author = {Hazan, Elad and Karnin, Zohar and Meka, Raghu}, booktitle = {Proceedings of The 27th Conference on Learning Theory}, pages = {408--422}, year = {2014}, editor = {Balcan, Maria Florina and Feldman, Vitaly and Szepesvári, Csaba}, volume = {35}, series = {Proceedings of Machine Learning Research}, address = {Barcelona, Spain}, month = {13--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v35/hazan14b.pdf}, url = {https://proceedings.mlr.press/v35/hazan14b.html}, abstract = {Numerous machine learning problems require an \it exploration basis - a mechanism to explore the action space. We define a novel geometric notion of exploration basis with low variance called volumetric spanners, and give efficient algorithms to construct such bases. We show how efficient volumetric spanners give rise to an efficient and near-optimal regret algorithm for bandit linear optimization over general convex sets. Previously such results were known only for specific convex sets, or under special conditions such as the existence of an efficient self-concordant barrier for the underlying set. } }
Endnote
%0 Conference Paper %T Volumetric Spanners: an Efficient Exploration Basis for Learning %A Elad Hazan %A Zohar Karnin %A Raghu Meka %B Proceedings of The 27th Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2014 %E Maria Florina Balcan %E Vitaly Feldman %E Csaba Szepesvári %F pmlr-v35-hazan14b %I PMLR %P 408--422 %U https://proceedings.mlr.press/v35/hazan14b.html %V 35 %X Numerous machine learning problems require an \it exploration basis - a mechanism to explore the action space. We define a novel geometric notion of exploration basis with low variance called volumetric spanners, and give efficient algorithms to construct such bases. We show how efficient volumetric spanners give rise to an efficient and near-optimal regret algorithm for bandit linear optimization over general convex sets. Previously such results were known only for specific convex sets, or under special conditions such as the existence of an efficient self-concordant barrier for the underlying set.
RIS
TY - CPAPER TI - Volumetric Spanners: an Efficient Exploration Basis for Learning AU - Elad Hazan AU - Zohar Karnin AU - Raghu Meka BT - Proceedings of The 27th Conference on Learning Theory DA - 2014/05/29 ED - Maria Florina Balcan ED - Vitaly Feldman ED - Csaba Szepesvári ID - pmlr-v35-hazan14b PB - PMLR DP - Proceedings of Machine Learning Research VL - 35 SP - 408 EP - 422 L1 - http://proceedings.mlr.press/v35/hazan14b.pdf UR - https://proceedings.mlr.press/v35/hazan14b.html AB - Numerous machine learning problems require an \it exploration basis - a mechanism to explore the action space. We define a novel geometric notion of exploration basis with low variance called volumetric spanners, and give efficient algorithms to construct such bases. We show how efficient volumetric spanners give rise to an efficient and near-optimal regret algorithm for bandit linear optimization over general convex sets. Previously such results were known only for specific convex sets, or under special conditions such as the existence of an efficient self-concordant barrier for the underlying set. ER -
APA
Hazan, E., Karnin, Z. & Meka, R.. (2014). Volumetric Spanners: an Efficient Exploration Basis for Learning . Proceedings of The 27th Conference on Learning Theory, in Proceedings of Machine Learning Research 35:408-422 Available from https://proceedings.mlr.press/v35/hazan14b.html.

Related Material