Active Regression by Stratification

Abstract

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/\epsilon )$ 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.

References in corpus (2)

• Random design analysis of ridge regression
• UPAL: Unbiased Pool Based Active Learning

Cited by in corpus (9)

• Exploring Connections Between Active Learning and Model Extraction
• Active Regression via Linear-Sample Sparsification
• Interactive algorithms: from pool to stream
• Online A-Optimal Design and Active Linear Regression
• Differentiable Learning Under Triage
• Active Online Learning with Hidden Shifting Domains
• Classification Under Human Assistance
• Regression Under Human Assistance
• Chernoff Sampling for Active Testing and Extension to Active Regression