跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.23801 · v1

Improved Leverage Score Sampling for Constrained Active Linear Regression

首次提交 2026-11-18 12:06
版本更新 2026-11-18 12:06
雷达观测 2026-11-19 19:08
arXiv ↗PDF ↗

摘要

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.

作者备注:To appear in NeurIPS 2026 (Spotlight)

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v1 · 2026-11-18 12:06 · 最新观测版本

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∈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.

查看此版本解读 →查看此版本原文 ↗