![[Conference on Learning Theory Logo]](/image.pl?url=http%3a%2f%2fproceedings.mlr.press%2fv35%2fassets%2fimages%2flogo-pmlr.svg&f=jpg&w=240)
[edit]
Volumetric Spanners: an Efficient Exploration Basis for Learning
Elad Hazan, Zohar Karnin, Raghu MekaProceedings 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 - CPAPERTI - Volumetric Spanners: an Efficient Exploration Basis for Learning AU - Elad HazanAU - Zohar KarninAU - Raghu MekaBT - Proceedings of The 27th Conference on Learning TheoryDA - 2014/05/29ED - Maria Florina BalcanED - Vitaly FeldmanED - Csaba SzepesváriID - pmlr-v35-hazan14bPB - PMLRDP - Proceedings of Machine Learning ResearchVL - 35SP - 408EP - 422L1 - http://proceedings.mlr.press/v35/hazan14b.pdfUR - https://proceedings.mlr.press/v35/hazan14b.htmlAB - 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, inProceedings of Machine Learning Research 35:408-422 Available from https://proceedings.mlr.press/v35/hazan14b.html.