stat.MLNov 18, 2026

Improved Leverage Score Sampling for Constrained Active Linear Regression

Authors: Aarshvi Gajjar, Syamantak Kumar, Aditya Makkar, Christopher Musco, Joey Zhou

Organizations: New York University · University of Texas at Austin

Abstract

In this paper we study active learning for constrained linear regression. Given a design matrix A∈Rn×dA\in\mathbb{R}^{n\times d}, a constraint set C⊆RdC\subseteq\mathbb{R}^d, and query access to b∈Rnb\in\mathbb{R}^n, we seek an approximate solution to min⁡x∈C∥Ax−b∥22\min_{x\in C}\|Ax-b\|_2^2 using as few queries 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 ignore the constraint or encode it through ridge regularization, suffering unfavorable query complexity for anisotropic constraint sets. We propose ellipsoid-regularized leverage scores, where we approximate the constraint set by an outer ellipsoid and use its shape matrix to bias sampling toward directions that matter under the constraint geometry. We prove that the query complexity is governed by an anisotropic effective dimension deff(C)≤dd_{\text{eff}}(C)\le d. With appropriate parameters, O(deff(C)log⁡d/ε2)O(d_{\text{eff}}(C)\log d/\varepsilon^2) queries suffice to return a point in CC with objective value at most (1+ε)(1+\varepsilon) times the optimum. This bound can substantially improve on the standard leverage-score bound, since anisotropic constraints can make deff(C)d_{\text{eff}}(C) much smaller than dd. For convex constraints, we improve the dependence on ε\varepsilon from 1/ε21/\varepsilon^2 to 1/ε1/\varepsilon. We also prove two lower bounds: first, the d/ε2d/\varepsilon^2 dependence is unavoidable without convexity assumptions on CC, and second, in some regimes, the effective dimension dependence deff(C)/εd_{\mathrm{eff}}(C)/\varepsilon is necessary for ellipsoidal constraints. Experiments on synthetic regression problems and a parametric heat conduction problem show lower regression error than standard baselines for similar query budget.

Explore similar work

Jul 7, 2026

The Approximation Ratio for the Risk of Myopic Bayesian Active Learning for Linear Regression

Active learning studies the fundamental question: what data should we choose to observe? The greedy algorithm in optimal experiment design is a common heuristic and also equivalent to myopic Bayesian active learning for linear regression, the common framework where long-term planning is replaced with the one-step optimal choice. In this work, we prove a first-of-its-kind approximation ratio for the greedy algorithm's risk that is tight up to an absolute constant. The approximation ratio is linear in the maximum initial leverage score (MILS), a newly identified quantity fundamental to the greedy algorithm's performance. Finally, we illustrate the results with simple numerical simulations.
Aug 2, 2026

Active Regression for Single-Index Models with Unknown Link Functions

This paper studies active regression for single-index models under general ℓp\ell_p-loss with an unknown 11-Lipschitz link function ff, formulated as min⁡f,x∥f(Ax)−b∥pp\min_{f,x} \|f(Ax)-b\|_p^p with full access to AA but coordinate-query access to bb. Prior work established upper bounds for known link functions for all p≥1p\geq 1 and for unknown link functions only in the p=2p=2 case, together with lower bounds for p≤2p\leq 2. This work addresses the more challenging setting of unknown link functions and general p≥1p \geq 1. A non-adaptive sampling algorithm is presented that achieves a (1+ε)(1+ε)-approximation using O(dp/2∨1/εp∨2poly⁡log⁡(n/ε))O(d^{p/2\vee 1}/ε^{p\vee 2}\operatorname{poly}\log(n/ε)) queries. Nearly tight lower bounds are also established for p>2p>2. These results close much of the remaining gap in active ℓp\ell_p-regression for single-index models.
Jun 9, 2026

Robust Regression of General ReLUs with Queries

We study the task of agnostically learning general (as opposed to homogeneous) ReLUs under the Gaussian distribution with respect to the squared loss. In the passive learning setting, recent work gave a computationally efficient algorithm that uses poly(d,1/ε)poly(d,1/ε) labeled examples and outputs a hypothesis with error O(opt)+εO(opt)+ε, where optopt is the squared loss of the best fit ReLU. Here we focus on the interactive setting, where the learner has some form of query access to the labels of unlabeled examples. Our main result is the first computationally efficient learner that uses dpolylog(1/ε)+O~(min⁡{1/p,1/ε})d polylog(1/ε)+\tilde{O}(\min\{1/p, 1/ε\}) black-box label queries, where pp is the bias of the target function, and achieves error O(opt)+εO(opt)+ε. We complement our algorithmic result by showing that its query complexity bound is qualitatively near-optimal, even ignoring computational constraints. Finally, we establish that query access is essentially necessary to improve on the label complexity of passive learning. Specifically, for pool-based active learning, any active learner requires Ω~(d/ε)\tildeΩ(d/ε) labels, unless it draws a super-polynomial number of unlabeled examples.