論文の概要: On efficient robust regression with subquadratic samples

• arxiv url: http://arxiv.org/abs/2605.18042v1
• Date: Mon, 18 May 2026 08:34:07 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-19 17:57:49.127933
• Title: On efficient robust regression with subquadratic samples
• Title（参考訳）: 準4次サンプルを用いた効率的なロバスト回帰について
• Authors: Deeksha Adil, Jarosław Błasiok, Hongjie Chen, Deepak Narayanan Sridharan,
• Abstract要約: ここでは,$widetildeO(d/4)$サンプルを用いたニア線形時間アルゴリズムが,$lesssim 1$条件下で予測誤差$O(sqrt)$を達成することを示す。 また、$lesssim 1$のような仮定がなければ、効率的なアルゴリズムには$tildeleft(mind22, 2d2right)$サンプルが必要であるという詳細な証拠を与える低次下界も証明する。
• 参考スコア（独自算出の注目度）: 2.017649213266693
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We revisit the problem of robust linear regression under Gaussian covariates with an unknown covariance matrix of condition number $κ$. For this fundamental problem, significant gaps remain in our understanding of the trade-offs among sample complexity, condition number, runtime, and prediction error for efficient algorithms. Our first result is a near-linear-time algorithm that uses $\widetilde{O}(d/ε^4)$ samples, where $d$ is the dimension and $ε$ is the corruption rate, and achieves prediction error $O(\sqrt{εκ})$ under the condition $εκ\lesssim 1$, improving over all prior works. We complement this result with a Statistical Query (SQ) lower bound showing that efficient SQ algorithms achieving error $o(\sqrt{εκ})$ when $εκ\lesssim 1$ require queries that take $Ω(d^2)$ samples to simulate. Finally, we prove a low-degree polynomial lower bound that gives fine-grained evidence that, without assumptions such as $εκ\lesssim 1$, efficient algorithms may require $\tildeΩ\left(\min\{dε^{2}κ^{2},\ ε^{2}d^{2}\}\right)$ samples to significantly outperform the trivial estimator that always guesses $0$.
• Abstract（参考訳）: ガウス共変量の下では、条件数$κ$の未知の共分散行列で頑健な線形回帰の問題を再考する。 この根本的な問題に対して、効率的なアルゴリズムに対するサンプルの複雑さ、条件数、実行時間、予測誤差の間のトレードオフに対する理解には、大きなギャップが残っています。 最初の結果は、$\widetilde{O}(d/ε^4)$サンプルを使用するニア線形時間アルゴリズムであり、$d$は次元であり、$ε$は汚職率であり、$O(\sqrt{εκ})$の予測誤差を$εκ\lesssim 1$の条件で達成し、すべての先行作業を改善する。 この結果を統計的クエリ (SQ) の下界で補うと、効率的なSQアルゴリズムがエラーを$o(\sqrt{εκ})$にしたとき、$εκ\lesssim 1$は$Ω(d^2)$のサンプルを必要とする。 最後に、$εκ\lesssim 1$のような仮定がなければ、効率的なアルゴリズムは$\tildeΩ\left(\min\{dε^{2}κ^{2},\ ε^{2}d^{2}\right)$サンプルを必要として、常に0$と推測する自明な推定器を著しく上回るような、低次多項式の下界を証明する。

関連論文リスト

• Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
  このタスクに対する効率的な統計的クエリアルゴリズムは、VSTATの複雑さを少なくとも$tildeOmega(d1/2/alpha2)$で要求する。
  論文  参考訳（メタデータ） (2025-10-12T15:42:44Z)
• Nearly Optimal Robust Covariance and Scatter Matrix Estimation Beyond Gaussians [2.311583680973075]
  楕円分布の共分散/散乱行列の計算効率の良いロバスト推定問題について検討する。 ガウスのケースを超えて拡張される、計算可能で、ほぼ最適な、ほぼ最適な共分散推定器を初めて得る。
  論文  参考訳（メタデータ） (2025-02-10T15:31:57Z)
• Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean Estimation and Linear Regression [44.13655983242414]
  最適誤差保証付きニア・ニア・ニア・リニア時間アルゴリズムの最初のサンプルを設計する。 堅牢な線形回帰のために、サンプル複雑性$n = tildeO(d/epsilon2)$と、ターゲット回帰器を$ell$-$O(epsilon)$で近似するほぼ線形ランタイムを持つ最初のアルゴリズムを与える。 これは、文献のオープンな疑問に答え、最適なエラー保証を達成するための最初のサンプルとタイムアルゴリズムである。
  論文  参考訳（メタデータ） (2023-12-04T00:31:16Z)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。 我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
  論文  参考訳（メタデータ） (2023-07-13T18:59:28Z)
• Near-Optimal Non-Convex Stochastic Optimization under Generalized Smoothness [21.865728815935665]
  2つの最近の研究は、$O(epsilon-3)$サンプル複雑性を確立し、$O(epsilon)$-定常点を得る。 しかし、どちらも$mathrmploy(epsilon-1)$という大きなバッチサイズを必要とする。 本研究では,STORMアルゴリズムの単純な変種を再検討することにより,従来の2つの問題を同時に解決する。
  論文  参考訳（メタデータ） (2023-02-13T00:22:28Z)
• Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
  我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。 我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。 我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
  論文  参考訳（メタデータ） (2022-09-30T04:15:44Z)
• Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
  対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。 我々はこの$d$への依存が対数的要因まで最適であることを示す。 また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
  論文  参考訳（メタデータ） (2021-11-09T00:20:01Z)
• 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)
• The Sparse Hausdorff Moment Problem, with Application to Topic Models [5.151973524974052]
  我々は$m=2k$iid二進確率変数のサンプルを用いて$k$-mixtureを同定するアルゴリズムを提案する。 加法精度$w_mincdotzetaO(k)$のモーメントを知るだけで十分である。
  論文  参考訳（メタデータ） (2020-07-16T04:23:57Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。