論文の概要: Statistical Query Lower Bounds for List-Decodable Linear Regression
- arxiv url: http://arxiv.org/abs/2106.09689v1
- Date: Thu, 17 Jun 2021 17:45:21 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-18 15:57:37.581537
- Title: Statistical Query Lower Bounds for List-Decodable Linear Regression
- Title（参考訳）: リスト決定可能な線形回帰に対する統計的照会下限
- Authors: Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia, Thanasis Pittas,
Alistair Stewart
- Abstract要約: 本稿では,リスト復号化可能な線形回帰問題について考察する。
我々の主な成果は、この問題に対して$dmathrmpoly (1/alpha)$の統計的クエリ(SQ)の低いバウンダリである。
- 参考スコア（独自算出の注目度）: 55.06171096484622
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of list-decodable linear regression, where an adversary
can corrupt a majority of the examples. Specifically, we are given a set $T$ of
labeled examples $(x, y) \in \mathbb{R}^d \times \mathbb{R}$ and a parameter
$0< \alpha <1/2$ such that an $\alpha$-fraction of the points in $T$ are i.i.d.
samples from a linear regression model with Gaussian covariates, and the
remaining $(1-\alpha)$-fraction of the points are drawn from an arbitrary noise
distribution. The goal is to output a small list of hypothesis vectors such
that at least one of them is close to the target regression vector. Our main
result is a Statistical Query (SQ) lower bound of $d^{\mathrm{poly}(1/\alpha)}$
for this problem. Our SQ lower bound qualitatively matches the performance of
previously developed algorithms, providing evidence that current upper bounds
for this task are nearly best possible.
- Abstract（参考訳）: リスト決定可能な線形回帰問題(英語版)(list-decodable linear regression) では、敵が多くの例を破る可能性がある。
具体的には、ラベル付き例の集合 $T$ を $(x, y) \in \mathbb{R}^d \times \mathbb{R}$ とし、パラメータ $0< \alpha <1/2$ を $T$ 内の点の $\alpha$-fraction が i.i.d となるように与えられる。
ガウス共変量を持つ線形回帰モデルからのサンプルと点の残りの(1-\alpha)$-フラクションは任意の雑音分布から引き出される。
目標は、少なくとも1つがターゲットの回帰ベクトルに近いように、仮説ベクトルの小さなリストを出力することである。
我々の主な結果は、この問題に対して$d^{\mathrm{poly}(1/\alpha)}$の統計的クエリ(SQ)の下限である。
我々のSQ下限は、以前に開発されたアルゴリズムの性能と定性的に一致し、このタスクの現在の上限がほぼ最良であることを示す。
関連論文リスト
- How to Inverting the Leverage Score Distribution? [16.744561210470632]
ツールとして広く利用されているレバレッジスコアにもかかわらず、本論文では、新しい問題、すなわち反転レバレッジスコアについて検討する。
我々は、ニュートン法における大域収束率を確保するために反復縮小と帰納仮説を用いる。
この統計レバレッジの反転に関する重要な研究は、解釈、データリカバリ、セキュリティにおける多くの新しい応用を開放する。
論文 参考訳（メタデータ） (2024-04-21T21:36:42Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Hardness and Algorithms for Robust and Sparse Optimization [17.842787715567436]
スパース線形回帰やロバスト線形回帰といったスパース最適化問題に対するアルゴリズムと制限について検討する。
具体的には、スパース線型回帰問題は$k$-スパースベクトル$xinmathbbRd$を求め、$|Ax-b|$を最小化する。
頑健な線形回帰問題は、少なくとも$k$行を無視する集合$S$と、$|(Ax-b)_S|$を最小化するベクトル$x$を求める。
論文 参考訳（メタデータ） (2022-06-29T01:40:38Z) - List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering [42.526664955704746]
そこで我々は,リストデコダブルなスパース平均推定のための,新しい,概念的にシンプルな手法を開発した。
特に、$k$-sparse方向の「確実に有界な」$t-thモーメントを持つ分布の場合、このアルゴリズムは、サンプル複雑性$m = (klog(n))O(t)/alpha(mnt)$の誤差を1/alpha(O (1/t)$で達成する。
Gaussian inliers の特別な場合、我々のアルゴリズムは $Theta (sqrtlog) の最適誤差を保証する。
論文 参考訳（メタデータ） (2022-06-10T17:38:18Z) - Robust Testing in High-Dimensional Sparse Models [0.0]
2つの異なる観測モデルの下で高次元スパース信号ベクトルのノルムを頑健にテストする問題を考察する。
回帰係数のノルムを確実に検定するアルゴリズムは、少なくとも$n=Omegaleft(min(slog d,1/gamma4)right)サンプルを必要とする。
論文 参考訳（メタデータ） (2022-05-16T07:47:22Z) - Polyak-Ruppert Averaged Q-Leaning is Statistically Efficient [90.14768299744792]
我々はPolyak-Ruppert 平均 Q-leaning (平均 Q-leaning) を用いた同期 Q-learning を$gamma$-discounted MDP で検討した。
繰り返し平均$barboldsymbolQ_T$に対して正規性を確立する。
要するに、我々の理論分析は、Q-Leaningの平均は統計的に効率的であることを示している。
論文 参考訳（メタデータ） (2021-12-29T14:47:56Z) - On the Power of Preconditioning in Sparse Linear Regression [24.140675945592704]
プレコンディショニングされたラッソは、大まかな線形回帰問題をほぼ最適に解くことができることを示す。
最適条件のラッソに対して証明が難しいランダム設計のインスタンスを初めて構築する。
論文 参考訳（メタデータ） (2021-06-17T02:12:01Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - 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) - Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and
ReLUs under Gaussian Marginals [49.60752558064027]
ガウス境界の下では、半空間とReLUを不可知的に学習する基本的な問題について検討する。
我々の下限は、これらのタスクの現在の上限が本質的に最良のものであるという強い証拠を与える。
論文 参考訳（メタデータ） (2020-06-29T17:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。