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 = {Elad Hazan and Zohar Karnin and Raghu Meka}, booktitle = {Proceedings of The 27th Conference on Learning Theory}, pages = {408--422}, year = {2014}, editor = {Maria Florina Balcan and Vitaly Feldman and Csaba Szepesvári}, 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 = {http://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 %J Proceedings of Machine Learning Research %P 408--422 %U http://proceedings.mlr.press %V 35 %W PMLR %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 PY - 2014/05/29 DA - 2014/05/29 ED - Maria Florina Balcan ED - Vitaly Feldman ED - Csaba Szepesvári ID - pmlr-v35-hazan14b PB - PMLR SP - 408 DP - PMLR EP - 422 L1 - http://proceedings.mlr.press/v35/hazan14b.pdf UR - http://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 PMLR 35:408-422

Related Material