論文の概要: Efficient List-Decodable Regression using Batches

• arxiv url: http://arxiv.org/abs/2211.12743v1
• Date: Wed, 23 Nov 2022 07:08:00 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-24 14:47:46.447982
• Title: Efficient List-Decodable Regression using Batches
• Title（参考訳）: バッチを用いた効率的なリストデコジュアブル回帰
• Authors: Abhimanyu Das, Ayush Jain, Weihao Kong and Rajat Sen
• Abstract要約: バッチを用いたリスト復号化線形回帰の研究を始める。 この設定では、バッチの$alpha in (0,1]$分しか真ではない。 それぞれの真のバッチは、共通の未知の分布から$ge n$ i.i.dのサンプルを含み、残りのバッチは、任意の、あるいは、敵対的なサンプルを含むことができる。
• 参考スコア（独自算出の注目度）: 33.300073775123835
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We begin the study of list-decodable linear regression using batches. In this setting only an $\alpha \in (0,1]$ fraction of the batches are genuine. Each genuine batch contains $\ge n$ i.i.d. samples from a common unknown distribution and the remaining batches may contain arbitrary or even adversarial samples. We derive a polynomial time algorithm that for any $n\ge \tilde \Omega(1/\alpha)$ returns a list of size $\mathcal O(1/\alpha^2)$ such that one of the items in the list is close to the true regression parameter. The algorithm requires only $\tilde{\mathcal{O}}(d/\alpha^2)$ genuine batches and works under fairly general assumptions on the distribution. The results demonstrate the utility of batch structure, which allows for the first polynomial time algorithm for list-decodable regression, which may be impossible for the non-batch setting, as suggested by a recent SQ lower bound \cite{diakonikolas2021statistical} for the non-batch setting.
• Abstract（参考訳）: バッチを用いたリスト復号化線形回帰の研究を始める。 この設定では、バッチの$\alpha \in (0,1]$ fractionのみが真である。 それぞれの真のバッチは、共通の未知の分布からの$\ge n$ i.d.サンプルを含み、残りのバッチは、任意の、あるいは、敵対的なサンプルを含む。 多項式時間アルゴリズムは任意の$n\ge \tilde \Omega(1/\alpha)$に対して$\mathcal O(1/\alpha^2)$を返し、リスト内の項目の1つが真の回帰パラメータに近くなる。 このアルゴリズムは$\tilde{\mathcal{O}}(d/\alpha^2)$真のバッチのみを必要とし、分布に関するかなり一般的な仮定の下で機能する。 この結果から,非バッチ設定に対するSQ下界 \cite{diakonikolas2021statistical} が提案したように,非バッチ設定では不可能な,リスト復号化可能な回帰に対する最初の多項式時間アルゴリズムを実現するバッチ構造の有用性が示された。

関連論文リスト

• Turnstile $\ell_p$ leverage score sampling with applications [56.403488578703865]
  我々は,行列$AinmathbbRntimes d$の行をサンプリングする新しいアルゴリズムを開発した。 我々のアルゴリズムはサンプル行インデックスのセットを返すだけでなく、わずかに乱れた行を $tildea_i approx a_i$ で返却し、サンプリング確率を $varepsilon$ の相対誤差に近似する。 ロジスティック回帰のために、我々のフレームワークは$を達成した最初のアルゴリズムを得る。
  論文  参考訳（メタデータ） (2024-06-01T07:33:41Z)
• Provably Efficient High-Dimensional Bandit Learning with Batched Feedbacks [93.00280593719513]
  本稿では,オンラインインタラクションのT$ステップをバッチに分割したバッチフィードバックによる高次元マルチアームコンテキストバンドレットについて検討する。 具体的には、各バッチは以前のバッチに依存するポリシーに従ってデータを収集し、その報酬はバッチの最後にのみ明らかにする。 我々のアルゴリズムは,$mathcalO( log T)$ バッチで完全に逐次的に設定されたものに匹敵する後悔の限界を達成している。
  論文  参考訳（メタデータ） (2023-11-22T06:06:54Z)
• 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)
• 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 Mean Estimation in Nearly-PCA Time [50.79691056481693]
  高次元におけるリストデコタブル平均推定の基本的な課題について検討する。 我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。 我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
  論文  参考訳（メタデータ） (2020-11-19T17:21:37Z)
• Conditional Uncorrelation and Efficient Non-approximate Subset Selection in Sparse Regression [72.84177488527398]
  相関性の観点からスパース回帰を考察し,条件付き非相関式を提案する。 提案手法により、計算複雑性は、スパース回帰における各候補部分集合に対して$O(frac16k3+mk2+mkd)$から$O(frac16k3+frac12mk2)$に削減される。
  論文  参考訳（メタデータ） (2020-09-08T20:32:26Z)

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

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