arXiv:2611.23801v1 stat.ML

제약 능동 선형 회귀를 위한 개선된 레버리지 점수 샘플링

Improved Leverage Score Sampling for Constrained Active Linear Regression

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

제출 2026-11-19

한국어 초록

본 논문에서는 제약 선형 회귀를 위한 능동 학습을 연구한다. 설계 행렬 $A\in\mathbb{R}^{n\times d}$, 제약 집합 $C\subseteq\mathbb{R}^d$, 그리고 $b\in\mathbb{R}^n$에 대한 질의 접근이 주어졌을 때, 가능한 한 적은 질의로 $\min_{x\in C}\|Ax-b\|_2^2$의 근사해를 구하고자 한다. 이 문제는 많은 과학 및 공학 응용에서 나타나며, 무작위 레버리지 점수 샘플링은 이를 푸는 강력한 방법을 제공한다. 그러나 기존 레버리지 점수 방법은 제약을 무시하거나 릿지 정규화를 통해 인코딩하므로, 비등방성 제약 집합에서 불리한 질의 복잡도를 겪는다. 우리는 제약 집합을 외부 타원체로 근사하고 그 형상 행렬을 사용하여 제약 기하 아래에서 중요한 방향으로 샘플링을 편향시키는 타원체 정규화 레버리지 점수를 제안한다. 질의 복잡도가 비등방성 유효 차원 $d_{\text{eff}}(C)\le d$에 의해 결정됨을 증명한다. 적절한 파라미터에서는 $O(d_{\text{eff}}(C)\log d/\varepsilon^2)$번의 질의로 목적 함수 값이 최적값의 $(1+\varepsilon)$배 이하인 $C$ 내의 점을 반환하기에 충분하다. 비등방성 제약은 $d_{\text{eff}}(C)$를 $d$보다 훨씬 작게 만들 수 있으므로, 이 한계는 표준 레버리지 점수 한계를 크게 개선할 수 있다. 볼록 제약의 경우 $\varepsilon$에 대한 의존성을 $1/\varepsilon^2$에서 $1/\varepsilon$로 개선한다. 또한 두 가지 하한을 증명한다. 첫째, $C$에 대한 볼록성 가정이 없으면 $d/\varepsilon^2$ 의존성은 피할 수 없다. 둘째, 일부 영역에서 타원체 제약에 대해서는 유효 차원 의존성 $d_{\mathrm{eff}}(C)/\varepsilon$이 필요하다. 합성 회귀 문제와 매개변수 열전도 문제에 대한 실험에서 유사한 질의 예산에서 표준 기준선보다 낮은 회귀 오차를 보였다.

원문 초록

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.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2611.23801v1제출 시각 미확인

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

공통 태그로 연결된 공개 논문이 아직 없습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.