論文の概要: Batch List-Decodable Linear Regression via Higher Moments

• arxiv url: http://arxiv.org/abs/2503.09802v1
• Date: Wed, 12 Mar 2025 20:11:07 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-14 15:54:01.905230
• Title: Batch List-Decodable Linear Regression via Higher Moments
• Title（参考訳）: 高次モーメントによるバッチリストデコダブル線形回帰
• Authors: Ilias Diakonikolas, Daniel M. Kane, Sushrut Karmalkar, Sihan Liu, Thanasis Pittas,
• Abstract要約: バッチを用いたリスト復号化線形回帰の課題について検討する。 バッチは、未知の線形回帰分布からのi.d.サンプルからなる場合、クリーンと呼ばれる。
• 参考スコア（独自算出の注目度）: 39.32851434877865
• License:
• Abstract: We study the task of list-decodable linear regression using batches. A batch is called clean if it consists of i.i.d. samples from an unknown linear regression distribution. For a parameter $\alpha \in (0, 1/2)$, an unknown $\alpha$-fraction of the batches are clean and no assumptions are made on the remaining ones. The goal is to output a small list of vectors at least one of which is close to the true regressor vector in $\ell_2$-norm. [DJKS23] gave an efficient algorithm, under natural distributional assumptions, with the following guarantee. Assuming that the batch size $n$ satisfies $n \geq \tilde{\Omega}(\alpha^{-1})$ and the number of batches is $m = \mathrm{poly}(d, n, 1/\alpha)$, their algorithm runs in polynomial time and outputs a list of $O(1/\alpha^2)$ vectors at least one of which is $\tilde{O}(\alpha^{-1/2}/\sqrt{n})$ close to the target regressor. Here we design a new polynomial time algorithm with significantly stronger guarantees under the assumption that the low-degree moments of the covariates distribution are Sum-of-Squares (SoS) certifiably bounded. Specifically, for any constant $\delta>0$, as long as the batch size is $n \geq \Omega_{\delta}(\alpha^{-\delta})$ and the degree-$\Theta(1/\delta)$ moments of the covariates are SoS certifiably bounded, our algorithm uses $m = \mathrm{poly}((dn)^{1/\delta}, 1/\alpha)$ batches, runs in polynomial-time, and outputs an $O(1/\alpha)$-sized list of vectors one of which is $O(\alpha^{-\delta/2}/\sqrt{n})$ close to the target. That is, our algorithm achieves substantially smaller minimum batch size and final error, while achieving the optimal list size. Our approach uses higher-order moment information by carefully combining the SoS paradigm interleaved with an iterative method and a novel list pruning procedure. In the process, we give an SoS proof of the Marcinkiewicz-Zygmund inequality that may be of broader applicability.
• Abstract（参考訳）: バッチを用いたリスト復号化線形回帰の課題について検討する。 バッチは、未知の線形回帰分布からのi.d.サンプルからなる場合、クリーンと呼ばれる。 パラメータ $\alpha \in (0, 1/2)$ の場合、バッチの未知の $\alpha$-fraction はクリーンであり、残りは仮定されない。 目標は、$\ell_2$-normの真の回帰ベクトルに近い少なくとも一方のベクトルの小さなリストを出力することである。 [DJKS23] は, 自然分布仮定に基づく効率的なアルゴリズムを, 以下の保証付きで提供した。 バッチサイズ $n$ が $n \geq \tilde{\Omega}(\alpha^{-1})$ を満たすとすると、バッチの数は $m = \mathrm{poly}(d, n, 1/\alpha)$ となる。 ここでは,共変量分布の低次モーメントが Sum-of-Squares (SoS) であるという仮定の下で,より強い保証を持つ新しい多項式時間アルゴリズムを設計する。 具体的には、任意の定数$\delta>0$に対して、バッチサイズが$n \geq \Omega_{\delta}(\alpha^{-\delta})$と次数-\Theta(1/\delta)$の共変数のモーメントはSoS certifiably boundedであり、我々のアルゴリズムは$m = \mathrm{poly}((dn)^{1/\delta}, 1/\alpha)$のバッチを使用し、多項式時間で動作し、$O(1/\alpha)$サイズのベクトルリストを出力する。 すなわち、最適なリストサイズを達成しつつ、最小バッチサイズと最終エラーをかなり小さくする。 提案手法では,SOSパラダイムを反復的手法と新規なリストプルーニング手法とを慎重に組み合わせて高次モーメント情報を利用する。 この過程において、より広い適用性を持つかもしれないMarcinkiewicz-Zygmundの不等式の SoS 証明を与える。

関連論文リスト

• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。 これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。 また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
  論文  参考訳（メタデータ） (2024-08-16T02:33:07Z)
• Efficient List-Decodable Regression using Batches [33.300073775123835]
  バッチを用いたリスト復号化線形回帰の研究を始める。 この設定では、バッチの$alpha in (0,1]$分しか真ではない。 それぞれの真のバッチは、共通の未知の分布から$ge n$ i.i.dのサンプルを含み、残りのバッチは、任意の、あるいは、敵対的なサンプルを含むことができる。
  論文  参考訳（メタデータ） (2022-11-23T07:08:00Z)
• 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)
• List-Decodable Covariance Estimation [1.9290392443571387]
  共分散推定アルゴリズムを初めて提案する。 この結果から,リスト復号化可能な線形回帰と部分空間復元のための初となるエンフェクサクタクティックアルゴリズムが提案された。
  論文  参考訳（メタデータ） (2022-06-22T09:38:06Z)
• 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)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。 また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
  論文  参考訳（メタデータ） (2022-04-13T22:18:47Z)
• 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)
• Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
  本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。 我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-06-16T03:34:14Z)
• List-Decodable Subspace Recovery: Dimension Independent Error in Polynomial Time [5.812499828391904]
  リスト化可能部分空間のリカバリにおいて、入力は$n$ポイント$alpha n$(ある$alpha ll 1/2$)の集合であり、それらは分布$mathcalD$から引き出される。 本研究は, より高速な固定ポリノミカルランニング時間を用いて, アンフェクタブルな集中防止誤差の3つの側面について, 結果を改善するものである。
  論文  参考訳（メタデータ） (2020-02-12T18:30:09Z)

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

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