AI & ML
Improved Leverage Score Sampling for Constrained Active Linear Regression
arXiv stat.ML0 views
arXiv:2611.23801v1 Announce Type: new Abstract: 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 $C\subseteq\mathbb{R}^d$, and query access to $b\in\mathbb{R}^n$, we seek an approximate solution to $\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 $d_{\text{eff}}(C)\le d$. With appropriate parameters, $O(d_{\text{eff}}(C)\log d/\varepsilon^2)$ queries suffice to return a point in $C$ with objective value at most $(1+\varepsilon)$ times the optimum. This bound can substantially improve on the standard leverage-score bound, since anisotropic constraints can make $d_{\text{eff}}(C)$ much smaller than $d$. For convex constraints, we improve the dependence on $\varepsilon$ from $1/\varepsilon^2$ to $1/\varepsilon$. We also prove two lower bounds: first, the $d/\varepsilon^2$ dependence is unavoidable without convexity assumptions on $C$, and second, in some regimes, the effective dimension dependence $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.
Source:https://arxiv.org/abs/2611.23801PreviousA Free Lunch: Gradient Averaging Achieves Optimal Statistical Efficiency in Newton SketchNextOptimal Deep Nonparametric Regression with Uniformly Bounded Lipschitz Constants
Related posts
![Quadruped Robot Software — Ch.12: Quadruped Case Studies [KR]](https://media2.dev.to/dynamic/image/width=800%2Cheight=%2Cfit=scale-down%2Cgravity=auto%2Cformat=auto/https%3A%2F%2Fdev-to-uploads.s3.us-east-2.amazonaws.com%2Fuploads%2Farticles%2Fawosw4u7jitr9h27f7c5.png)
Quadruped Robot Software — Ch.12: Quadruped Case Studies [KR]
0dev.to
How Python Is Used in Artificial Intelligence in 2026: Applications, Benefits and Career Opportunities
0dev.to

What Happens in Those Few Seconds Between Pressing the Power Button and Seeing the Windows Login Screen?
0dev.to
Getting cited by ChatGPT and Claude: what the research supports, and a free audit tool
0dev.to
Why Photoshot keeps the original color when you edit in black and white
0dev.to
ISTQB CTFL in 2027: is it still worth it? What changes, what does not
0dev.to