Hard-Margin Active Linear Regression

Elad Hazan, Zohar Karnin
Proceedings of the 31st International Conference on Machine Learning, PMLR 32(2):883-891, 2014.

Abstract

We consider the fundamental problem of linear regression in which the designer can actively choose observations. This model naturally captures various experiment design settings in medical experiments, ad placement problems and more. Whereas previous literature addresses the soft-margin or mean-square-error variants of the problem, we consider a natural machine learning hard-margin criterion. In this setting, we show that active learning admits significantly better sample complexity bounds than the passive learning counterpart, and give efficient algorithms that attain near-optimal bounds.

Cite this Paper

BibTeX
@InProceedings{pmlr-v32-hazan14, title = {Hard-Margin Active Linear Regression}, author = {Hazan, Elad and Karnin, Zohar}, booktitle = {Proceedings of the 31st International Conference on Machine Learning}, pages = {883--891}, year = {2014}, editor = {Xing, Eric P. and Jebara, Tony}, volume = {32}, number = {2}, series = {Proceedings of Machine Learning Research}, address = {Bejing, China}, month = {22--24 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v32/hazan14.pdf}, url = {https://proceedings.mlr.press/v32/hazan14.html}, abstract = {We consider the fundamental problem of linear regression in which the designer can actively choose observations. This model naturally captures various experiment design settings in medical experiments, ad placement problems and more. Whereas previous literature addresses the soft-margin or mean-square-error variants of the problem, we consider a natural machine learning hard-margin criterion. In this setting, we show that active learning admits significantly better sample complexity bounds than the passive learning counterpart, and give efficient algorithms that attain near-optimal bounds.} }
Endnote
%0 Conference Paper %T Hard-Margin Active Linear Regression %A Elad Hazan %A Zohar Karnin %B Proceedings of the 31st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2014 %E Eric P. Xing %E Tony Jebara %F pmlr-v32-hazan14 %I PMLR %P 883--891 %U https://proceedings.mlr.press/v32/hazan14.html %V 32 %N 2 %X We consider the fundamental problem of linear regression in which the designer can actively choose observations. This model naturally captures various experiment design settings in medical experiments, ad placement problems and more. Whereas previous literature addresses the soft-margin or mean-square-error variants of the problem, we consider a natural machine learning hard-margin criterion. In this setting, we show that active learning admits significantly better sample complexity bounds than the passive learning counterpart, and give efficient algorithms that attain near-optimal bounds.
RIS
TY - CPAPER TI - Hard-Margin Active Linear Regression AU - Elad Hazan AU - Zohar Karnin BT - Proceedings of the 31st International Conference on Machine Learning DA - 2014/06/18 ED - Eric P. Xing ED - Tony Jebara ID - pmlr-v32-hazan14 PB - PMLR DP - Proceedings of Machine Learning Research VL - 32 IS - 2 SP - 883 EP - 891 L1 - http://proceedings.mlr.press/v32/hazan14.pdf UR - https://proceedings.mlr.press/v32/hazan14.html AB - We consider the fundamental problem of linear regression in which the designer can actively choose observations. This model naturally captures various experiment design settings in medical experiments, ad placement problems and more. Whereas previous literature addresses the soft-margin or mean-square-error variants of the problem, we consider a natural machine learning hard-margin criterion. In this setting, we show that active learning admits significantly better sample complexity bounds than the passive learning counterpart, and give efficient algorithms that attain near-optimal bounds. ER -
APA
Hazan, E. & Karnin, Z.. (2014). Hard-Margin Active Linear Regression. Proceedings of the 31st International Conference on Machine Learning, in Proceedings of Machine Learning Research 32(2):883-891 Available from https://proceedings.mlr.press/v32/hazan14.html.

Related Material