首页 > AI前沿 > Improved Leverage Score Sampling for Constrained Active Linear Regression

Improved Leverage Score Sampling for Constrained Active Linear Regression

arXiv机器学习 2026-11-18 12:06 12 阅读 查看原文
用户现在需要把给定的新闻正文(其实是学术内容的正文)排版成语义化的HTML片段,按照要求,每个自然段落用p包裹,长文用h2/h3划分?不对,先看内容,首先开头是研究内容,然后问题,然后方法,然后理论结果,然后下界,然后实验?不对,先理清楚内容,不能增删改,保留所有信息。首先,先看每个部分: 首先,第一段是介绍研究主题和问题设定对吧?不对,原文的内容:首先开头“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.” 不对,要不要划分小节?哦,规则说长文用h2/h3划分小节,那可以分几个小节?比如

研究背景与问题设定

?不对不对,不对,不能增删内容!哦对,不能增删改内容,所以h2/h3的标题不能自己加?哦不对不对,等下规则3是保留原文所有信息,不得增删改内容,哦,对哦,我不能自己加标题内容?不对不对,再看规则2:长文用

/

划分小节,但是不能增删改内容,那怎么划分?哦不对,原文的内容是连贯的?不对,等下再看原文的结构: 1. 研究主题与问题: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. 2. 现有方法与不足: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. 3. 提出的方法: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. 4. 理论结果: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$. 5. 下界结果: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. 6. 实验结果:Experiments on synthetic regression problems and a parametric heat conduction problem show lower regression error than standard baselines for similar query budget. 哦,但是不能加自己的话,那h2/h3怎么用?不对,哦不对,是不是我误解了?规则说长文用h2/h3划分小节,但是不能增删内容,那是不是原文里没有标题,那是不是可以不用?不对,不对,再看规则,哦,不对,有没有可能这些内容可以分成几个p,然后如果有适合的划分?不对,等下,规则1是只输出HTML片段,不要其他,保留所有内容,不能增删。那首先,代码(这里的公式)用pre code?不对,原文里的公式是行内的,哦,规则3说代码用pre code,那行内的公式算不算代码?不对,看规则3的描述:列表用ul li,引用用blockquote,代码用pre code,重要句子用strong。那这里的数学公式是内容的一部分,怎么处理?哦,不对,用户给的原文里的公式是行内的,是不是应该保留在p里面?不对,pre code是用于代码块,那行内的公式是不是不需要?哦,对,pre是块级的,所以行内的数学符号就正常放在p里就可以?不对,等下再看要求:不得增删改内容,所以公式要原封不动保留。 然后,重要句子可以用strong,比如研究的核心贡献?比如“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.” 这句是提出的方法,可以加strong?还有关键的下界和结论?不对,不要随便加,不对,规则说“重要句子可用strong”,是可以用,不是必须。 然后,现在组织HTML: 首先,有没有需要h2的地方?比如,如果把内容分成几个部分,但是不能加标题文字,那是不是不用h2?不对,等下,原文的内容是不是都是正文段落?不对,再看,哦,不对,会不会我理解错了,h2/h3是用于划分小节,如果原文本身没有小节标题,那是不是可以不用?不对,规则说“长文用

/

划分小节”,那这个是长文吗?其实这个内容不算特别长,但是可以划分吗?不对,不能加自己的话,所以标题不能用自己编的,那是不是就不用h2/h3?不对,等下再仔细看用户的要求:“2.每个自然段落用

包裹,长文用

/

划分小节”,哦,哦,可能是如果内容有不同部分,可以用h2来划分,但是标题要用原文的?不对,原文里没有标题啊。哦,不对,会不会我搞错了,原文的内容就是连贯的,那直接用p包裹每个自然段?不对,原文的原文是一整段?不,用户给的正文是: 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. 哦,原来用户给的正文是一整段?不对,那自然段落怎么分?哦,自然段落是指语义上的段落,对吧?可以分成几个p: