Improved Leverage Score Sampling for Constrained Active Linear Regression

In this paper we study active learning for constrained linear regression. Given a design matrix $A \in \mathbb{R}^{n \times d}$, a constraint set $\mathcal C \subseteq \mathbb{R}^d$, and query access to a response vector $b \in \mathbb{R}^n$, we seek to output an approximate solution to the problem $\min_{x\in \mathcal{C}} \lVert Ax - b\rVert_2^2$ using as few queries to $b$ as possible. This problem arises in many scientific and engineering applications, and _randomized leverage score sampling_ provides a powerful method to solve it. However, existing leverage score methods either ignore the constraint or encode it only through ridge regularization, thereby suffering poor query complexity for anisotropic constraint sets. We propose _ellipsoid-regularized leverage scores_, where we first approximate the constraint set by an outer ellipsoid and then use its shape matrix to bias sampling toward directions that matter under the constraint geometry. We prove that the resulting query complexity is governed by a natural ``anisotropic effective dimension`` of the problem, $d_{\text{eff}}(\mathcal{C}) \leq d$. In particular, we show that $\tilde O(d_{\text{eff}}(\mathcal{C})/\varepsilon^2)$ label queries suffice to return a feasible point whose objective value is at most $(1+\varepsilon)$ times the optimum. This bound is typically much smaller than what would be obtained using standard leverage scores. Furthermore, for convex constraints, we show how to improve the dependence on $\varepsilon$ from $1/\varepsilon^2$ to $1/\varepsilon$. We complement these upper bounds with two lower bounds: first, a lower bound showing that the $1/\varepsilon^2$ dependence is unavoidable without convexity assumptions on $\mathcal C$, and second, a lower bound showing that the effective-dimension dependence is unavoidable for ellipsoidal constraints. We also provide experiments supporting our theoretical results.