論文の概要: Algorithms for adaptive and heteroskedastic linear regression at the computational threshold
- arxiv url: http://arxiv.org/abs/2608.18402v1
- Date: Wed, 19 Aug 2026 00:17:22 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-20 20:13:55.237531
- Title: Algorithms for adaptive and heteroskedastic linear regression at the computational threshold
- Title（参考訳）: 計算しきい値におけるアダプティブおよびヘテロスケダスティック線形回帰のアルゴリズム
- Abstract要約: 本研究では, 有限サンプル線形回帰法について検討した。
適応線形回帰では、誤差は未知の分布から引き出される。
計算非効率な)適応推定器を導入し、$p$が$k対称対数対数対数の混合である限り達成する。
- 参考スコア（独自算出の注目度）: 2.2359088001899736
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study finite-sample linear regression in the presence of varied and unknown label noise, focusing on the heteroskedastic and adaptive linear regression models. Heteroskedastic linear regression models settings where the labels are of varying quality. We receive $n$ pairs $(X_i,Y_i)$ with labels $Y_i=X_i^\topβ+\varepsilon_i$, where $\varepsilon_i\sim N(0,σ_i^2)$ and the variances are unknown to the estimator. One natural measurement of the difficulty of this problem is the number of samples $m$ for which $σ_i^2\le1$ (larger $m$ is easier). We obtain a polynomial-time estimator with rate $\tilde{O}((nd^3/m^4)^{1/6})$ when $m\gg d^{3/4}n^{1/4}$, as well as nearly-matching lower bounds. For $d=O(1)$, our estimator achieves error $o(1)$ when $m\gg n^{1/4}$, whereas $L_1$ regression and other traditional approaches require $m\gg n^{1/2}$. In adaptive linear regression, the errors are drawn i.i.d. from an unknown distribution $p$, and our goal is to design a generic estimator that performs nearly as well as the best custom estimator that knows $p$. We introduce a (computationally inefficient) adaptive estimator that, so long as $p$ is a mixture of $k$ symmetric log-concave densities, achieves error comparable with the optimal estimator that knows $p$ and has $\tildeΘ(n/k)$ samples. For $k=1$, we show that $L_q$ regression (with data-dependent $q$) gives a polynomial-time estimator. Finally, to study the computational limits of both problems, we introduce the planted linear regression problem, where $X_i\sim N(0,I_d)$, $m$ unknown samples are noiseless, and the rest have error $\varepsilon_i\sim N(0,1)$. We conjecture that recovering $β$ up to error $\ll\sqrt{d/n}$ (or exactly) may have an information-computation gap between $m=d+1$ and $m\sim d^{3/4}n^{1/4}$, as is suggested by our near-matching polynomial-time estimator and statistical query (SQ) lower bound.
- Abstract（参考訳）: 本研究では, 有限サンプル線形回帰モデルを用いて, 異種・未知のラベル雑音の存在下での有限サンプル線形回帰について検討した。
Heteroskedastic linear regression model setting where the labels are various quality。
我々は$n$ペア$(X_i,Y_i)$とラベル$Y_i=X_i^\topβ+\varepsilon_i$を受け取ります。
この問題の難しさの自然な測定の一つは、$σ_i^2\le1$(より大きい$m$は簡単)のサンプル数$m$である。
次数$\tilde{O}((nd^3/m^4)^{1/6})$, $m\gg d^{3/4}n^{1/4}$の多項式時間推定器と、ほぼ一致する下界を求める。
for $d=O(1)$, our estimator achieves error $o(1)$ when $m\gg n^{1/4}$, and $L_1$ regression and other traditional approach requires $m\gg n^{1/2}$.
適応線形回帰では、誤差は未知の分布から$p$から引き出され、我々のゴールは、p$を知っている最も優れたカスタム推定器とほぼ同等に機能するジェネリック推定器を設計することである。
計算的に非効率な)適応推定器を導入し、$p$が$k$対称な対数凹凸密度の混合である限り、$p$を知り、$\tilde\(n/k)$サンプルを持つ最適推定器に匹敵する誤差を達成する。
k=1$の場合、$L_q$回帰(データ依存$q$)は多項式時間推定器を与える。
最後に、両問題の計算限界を研究するために、X_i\sim N(0,I_d)$, $m$未知のサンプルがノイズなく、残りはエラー$\varepsilon_i\sim N(0,1)$を導入する。
誤差$\ll\sqrt{d/n}$(または正確には)のリカバリは$m=d+1$と$m\sim d^{3/4}n^{1/4}$の間の情報計算のギャップを持つかもしれないと推測する。
関連論文リスト
- Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
このタスクに対する効率的な統計的クエリアルゴリズムは、VSTATの複雑さを少なくとも$tildeOmega(d1/2/alpha2)$で要求する。
論文 参考訳（メタデータ） (2025-10-12T15:42:44Z) - Distribution-Independent Regression for Generalized Linear Models with
Oblivious Corruptions [49.69852011882769]
一般化線形モデル (GLMs) の重畳雑音の存在下での回帰問題に対する最初のアルゴリズムを示す。
本稿では,この問題に最も一般的な分布非依存設定で対処するアルゴリズムを提案する。
これは、サンプルの半分以上を任意に破損させる難聴ノイズを持つGLMレグレッションに対する最初の新しいアルゴリズムによる結果である。
論文 参考訳（メタデータ） (2023-09-20T21:41:59Z) - Convergence analysis of online algorithms for vector-valued kernel regression [0.0]
回帰関数 $f_mu:, Omega to Y$ from noisy $mu$-distributed vector-valued data。
標準正規化オンライン近似アルゴリズムにより得られた近似値$f(m) in H$のRKHSノルムの2乗誤差を推定する。
論文 参考訳（メタデータ） (2023-09-14T15:10:47Z) - Almost Linear Constant-Factor Sketching for $\ell_1$ and Logistic
Regression [74.28017932704704]
我々は,従来の難解なスケッチとターンタイルストリーミングの結果を$ell_1$とロジスティック回帰で改善する。
また、入力空間の間隔で1+varepsilon$近似を出力するトレードオフも行います。
我々のスケッチは、データ依存正規化器が個々のロジスティック損失の分散に対応するような、正規化されたロジスティック回帰を近似するために拡張することができる。
論文 参考訳（メタデータ） (2023-03-31T18:12:33Z) - A spectral least-squares-type method for heavy-tailed corrupted
regression with unknown covariance \& heterogeneous noise [2.019622939313173]
重み付き最小二乗線形回帰は、少なくとも$epsilon n$ arbitrary outliersの$n$のラベル特徴サンプルを破損させたと仮定して再検討する。
本稿では,$(Sigma,Xi) や $Xi$ の演算ノルムに関する知識を前提に,電力法に基づくほぼ最適に計算可能な推定器を提案する。
論文 参考訳（メタデータ） (2022-09-06T23:37:31Z) - (Nearly) Optimal Private Linear Regression via Adaptive Clipping [22.639650869444395]
固定されたガウス型分布から各データ点をサンプリングする微分プライベート線形回帰問題について検討する。
本稿では,各イテレーションの点を置換せずにサンプリングする1パスのミニバッチ勾配勾配法(DP-AMBSSGD)を提案し,解析する。
論文 参考訳（メタデータ） (2022-07-11T08:04:46Z) - Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。
我々はこの$d$への依存が対数的要因まで最適であることを示す。
また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
論文 参考訳（メタデータ） (2021-11-09T00:20:01Z) - Statistical Query Lower Bounds for List-Decodable Linear Regression [55.06171096484622]
本稿では,リスト復号化可能な線形回帰問題について考察する。
我々の主な成果は、この問題に対して$dmathrmpoly (1/alpha)$の統計的クエリ(SQ)の低いバウンダリである。
論文 参考訳（メタデータ） (2021-06-17T17:45:21Z) - Outlier-robust sparse/low-rank least-squares regression and robust
matrix completion [1.0878040851637998]
ヘテロジニアス雑音を伴う統計的学習フレームワークにおける高次元最小二乗回帰について検討する。
また, 製品プロセスの新たな応用に基づいて, 行列分解を伴う新しいトレーサリグレス理論を提案する。
論文 参考訳（メタデータ） (2020-12-12T07:42:47Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳（メタデータ） (2020-07-16T06:44:44Z) - Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
論文 参考訳（メタデータ） (2020-05-29T07:20:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。