Hard-Margin Active Linear Regression
Elad Hazan, Zohar S. Karnin · 2014
We consider the fundamental problem of lin-ear regression in which the designer can actively choose observations. This model naturally cap-tures various experiment design settings in med-ical 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 learn-ing hard-margin criterion. In this setting, we show that active learning admits significantly better sample complexity bounds than the pas-sive learning counterpart, and give efficient algo-rithms that attain near-optimal bounds. 1.