Constrained Active Regression via Ellipsoid Regularized Leverage Scores

Randomized leverage-score sampling has emerged as a powerful tool for active learning, providing an alternative to classical optimal-design and Bayesian methods. For linear regression, kernel regression, shallow-neural networks, and more, it offers strong worst-case guarantees, even under adversarial label noise. In this report, we introduce a simple approach for extending it to \emph{constrained regression problems.}. We suggest sampling training data using generalized \emph{ellipsoid-regularized leverage scores} with respect to the smallest ellipsoid containing the constraint set. We prove strong theoretical guarantees, with sample complexity adapting naturally to the restriction imposed by the constraint. These results are supported by preliminary experiments on synthetic data, and we also provide a matching lower bound on the sample complexity in the case of non-convex constraints.