Active Regression by Stratification
We propose a new active learning algorithm for parametric linear regression with random design. We provide finite sample convergence guarantees for general distributions in the misspecified model. This is the first active learner for this setting that provably can improve over passive learning. Unlike other learning settings (such as classification), in regression the passive learning rate of O(1/ ) cannot in general be improved upon. Nonetheless, the so-called 'constant' in the rate of convergence, which is characterized by a distribution-dependent risk, can be improved in many cases. For a given distribution, achieving the optimal risk requires prior knowledge of the distribution. Following the stratification technique advocated in Monte-Carlo function integration, our active learner approaches the optimal risk using piecewise constant approximations.
This work studies the problem of active learning in linear regression.Unlike classification, the objective in active regression is merely to improve the constant factors in the distribution-dependent rates of convergence compared to passive learning, since it is known that the asymptotic dependence on the number of labels typically cannot be improved compared to passive learning, and nor can the worst-casevalues of the constant factor.  The paper argues that there is a distribution-dependent constant factor in the rate of convergence of passive learning, which can sometimes be improved for active learning.Specifically, they propose a rejection sampling scheme, which altersthe sampling distribution to a more-favorable one, without changingthe optimal solution.  However, the rejection sampler requires a sort of scaling function \phi as a parameter, and obtaining good performance guarantees requires one to set this function carefully, and with some dependence on the joint distribution of (X,Y).  Since this latter distribution is unknown, the algorithm attempts to optimize the choice of \phi amongpiecewise constant functions, using an estimated linear function from an initial sample.  They prove a risk bound for this method, which can be made to approach the ``oracle'' rate (where the optimal \phi is given),and which is provably sometimes superior to the capabilities of passive learning methods.Overall, this seems to be a solid contribution, which I suspect will have a wide audience.My one main reservation is that I would have liked to see more discussionof the dependence on K vs \rho*_A in Theorem 5.1.  There are some termsthat are increasing in K, while we would like \rho*_A to decrease toward\rho*, which presumably requires K to grow.  Thus, the trade-off betweenthese two quantities can affect the rates.  Some examples to illustrate how we should expect this trade-off to behave, for some reasonable distributions and sensible partition, would be helpful.minor comments: One citation that is missing here is Efromovich (2005): Sequential Designand Estimation in Heteroscedastic Nonparametric Regression.That work studies active regression as well (though for a nonparametric class),and also finds improvements in constant factors based on the degree of heteroscedasticity.I also want to echo a remark of one of the other reviewers, that the notation for P_\phi seems a little strange to me.  I believe the intention is that, denoting by Q_\phi the measure having density \phi with respect to D, we define P_\phi as the distribution of (X/\sqrt{\phi(X)},Y/\sqrt{\phi(X)}), for (X,Y) \sim Q_\phi. This P_\phi should then be well-defined, and L(w,D)=L(w,P_\phi) would then follow via the law of the unconscious statistician.Was this the intended meaning of P_\phi?