論文の概要: High-Accuracy List-Decodable Mean Estimation

• arxiv url: http://arxiv.org/abs/2511.17822v1
• Date: Fri, 21 Nov 2025 22:35:19 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-25 18:34:24.446993
• Title: High-Accuracy List-Decodable Mean Estimation
• Title（参考訳）: 高精度リストデコダブル平均推定
• Authors: Ziyun Chen, Spencer Compton, Daniel Kane, Jerry Li,
• Abstract要約: リスト記述可能な学習では、これらの点の$$-fractionが、$D$のよい分布から得られるようなデータポイントのセットが与えられます。 目標は、このリストの少なくとも1つの要素が$D$に関する非自明な情報を回復するように、候補ソリューションの短いリストを出力することである。 最大で$L = exp left Oleft( fractlog2 1 / 2 right) の候補手段のリストが存在することを示す。
• 参考スコア（独自算出の注目度）: 18.3185438532753
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In list-decodable learning, we are given a set of data points such that an $α$-fraction of these points come from a nice distribution $D$, for some small $α\ll 1$, and the goal is to output a short list of candidate solutions, such that at least one element of this list recovers some non-trivial information about $D$. By now, there is a large body of work on this topic; however, while many algorithms can achieve optimal list size in terms of $α$, all known algorithms must incur error which decays, in some cases quite poorly, with $1 / α$. In this paper, we ask if this is inherent: is it possible to trade off list size with accuracy in list-decodable learning? More formally, given $ε> 0$, can we can output a slightly larger list in terms of $α$ and $ε$, but so that one element of this list has error at most $ε$ with the ground truth? We call this problem high-accuracy list-decodable learning. Our main result is that non-trivial high-accuracy guarantees, both information-theoretically and algorithmically, are possible for the canonical setting of list-decodable mean estimation of identity-covariance Gaussians. Specifically, we demonstrate that there exists a list of candidate means of size at most $L = \exp \left( O\left( \tfrac{\log^2 1 / α}{ε^2} \right)\right)$ so that one of the elements of this list has $\ell_2$ distance at most $ε$ to the true mean. We also design an algorithm that outputs such a list with runtime and sample complexity $n = d^{O(\log L)} + \exp \exp (\widetilde{O}(\log L))$. We do so by demonstrating a completely novel proof of identifiability, as well as a new algorithmic way of leveraging this proof without the sum-of-squares hierarchy, which may be of independent technical interest.
• Abstract（参考訳）: リスト分割可能な学習では、これらの点の$α$-fractionが、ある小さな$α\ll 1$に対して$D$から得られるようなデータポイントのセットが与えられ、このリストの少なくとも1つの要素が$D$に関する非自明な情報を回復するように、候補解の短いリストを出力することが目的である。 しかし、多くのアルゴリズムは、$α$という観点で最適なリストサイズを達成できるが、既知の全てのアルゴリズムは、崩壊するエラーを発生させなければならない。 本稿では,リスト記述可能な学習において,リストサイズと精度を両立させることは可能か,と問う。 より正式には、$ε> 0$ とすると、$α$ と $ε$ で少し大きなリストを出力できるが、このリストの1つの要素が少なくとも$ε$ の誤差を基底真理で出力できる。 我々はこの問題を高精度リスト復号学習と呼んでいる。 我々の主な成果は、情報理論とアルゴリズムの両面において非自明な高精度保証が、同一性共分散ガウス平均推定の標準設定において可能であることである。 具体的には、最大$L = \exp \left(O\left( \tfrac{\log^2} / α}{ε^2} \right)\right)$ の候補平均のリストが存在して、このリストの要素の1つが少なくとも$ε$の真の平均まで$\ell_2$距離を持つことを示す。 また、実行時およびサンプル複雑性$n = d^{O(\log L)} + \exp \exp (\widetilde{O}(\log L))$でそのようなリストを出力するアルゴリズムを設計する。 我々は、全く新しい識別可能性の証明を証明し、またこの証明を、独立した技術的関心を持つであろう2乗の階層を使わずに活用する新しいアルゴリズム的方法を示す。

関連論文リスト

• Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
  このタスクに対する効率的な統計的クエリアルゴリズムは、VSTATの複雑さを少なくとも$tildeOmega(d1/2/alpha2)$で要求する。
  論文  参考訳（メタデータ） (2025-10-12T15:42:44Z)
• Batch List-Decodable Linear Regression via Higher Moments [39.32851434877865]
  バッチを用いたリスト復号化線形回帰の課題について検討する。 バッチは、未知の線形回帰分布からのi.d.サンプルからなる場合、クリーンと呼ばれる。
  論文  参考訳（メタデータ） (2025-03-12T20:11:07Z)
• 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)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)
• 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)
• List-Decodable Mean Estimation via Iterative Multi-Filtering [44.805549762166926]
  未知の$alpha$-fraction of points in $T$は未知の平均と有界な共分散分布$D$から引き出される。 仮説ベクトルの小さなリストを出力し、その中の少なくとも一方が$D$に近いようにする。 より詳しくは、本アルゴリズムはサンプリングと計算効率が良く、情報理論上の準最適誤差を実現する。
  論文  参考訳（メタデータ） (2020-06-18T17:47:37Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。 もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
  論文  参考訳（メタデータ） (2020-02-17T18:41:49Z)

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

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