論文の概要: The Price of List Replicability: Tight Bounds for Bias Estimation

• arxiv url: http://arxiv.org/abs/2611.04532v1
• Date: Tue, 03 Nov 2026 08:59:54 GMT
• ステータス: 情報取得中
• システム内更新日: 2026-11-04 17:47:47.918388
• Title: The Price of List Replicability: Tight Bounds for Bias Estimation
• Title（参考訳）: リストリプリケータの価格:バイアス推定のためのタイト境界
• Abstract要約: 我々は、$d$コインのバイアスを推定するためのリストレプリカブルアルゴリズムのサンプル複雑さについて検討した。 この問題に対する最初の非自明なサンプルの複雑さを低く抑え、多対数因子に匹敵するアルゴリズムを改良する。
• 参考スコア（独自算出の注目度）: 7.4097965693079155
• License:
• Abstract: We study the sample complexity of list replicable algorithms for estimating the biases of $d$ coins. An algorithm is $(k,\varepsilon,δ)$-list replicable if for every bias vector $\mathbf{p}\in[0,1]^d$, there is a set of outputs $L_{\mathbf{p}}\subseteq \mathbb{R}^d$ of at most $k$ elements such that every $\mathbf{y}\in L_{\mathbf{p}}$ satisfies $\lVert\mathbf{y}-\mathbf{p}\rVert_\infty\leq\varepsilon$, and the algorithm output is in $L_{\mathbf{p}}$ with probability at least $1-δ$. Prior work gave a $(d+1,\varepsilon,δ)$-list replicable algorithm with sample complexity $\widetilde{O}\left(\frac{d^3}{\varepsilon^2}\right)$, but no nontrivial sample complexity lower bound was known. We establish the first non-trivial sample complexity lower bound for this problem and give an improved algorithm that matches it up to polylogarithmic factors. Together, these results determine the optimal sample complexity for list size $d+1$ to be $\widetildeΘ\left(\frac{d^2}{\varepsilon^2}\right)$, showing that the quadratic dependence on dimension is inherent up to polylogarithmic factors. More generally, for every $k\in[d+1,2^d]$, we establish matching upper and lower bounds of $\widetildeΘ\left(\frac{d^2}{\varepsilon^2\log k}\right)$ on the total sample complexity.
• Abstract（参考訳）: 我々は、$d$コインのバイアスを推定するためのリストレプリカブルアルゴリズムのサンプル複雑さについて検討した。 a algorithm is $(k,\varepsilon,δ)$-list replicable if for every bias vector $\mathbf{p}\in[0,1]^d$, a set of outputs $L_{\mathbf{p}}\subseteq \mathbb{R}^d$ of at most $k$ elements such that every $\mathbf{y}\in L_{\mathbf{p}}$ satisfies $\lVert\mathbf{y}-\mathbf{p}\rVert_\infty\leq\varepsilon$, and the algorithm output is in $L_{\mathbf{p}}$ at least $1-δ$。 以前の研究では、サンプル複雑性を持つ$(d+1,\varepsilon,δ)$-listのレプリカブルアルゴリズムが与えられた。 この問題に対する最初の非自明なサンプルの複雑さを低く抑え、多対数因子に匹敵するアルゴリズムを改良する。 これらの結果は、リストサイズ$d+1$ を $\widetilde\left(\frac{d^2}{\varepsilon^2}\right)$ に最適なサンプル複雑性を決定し、次元に対する二次的依存が多元対数因子に固有のものであることを示す。 より一般に、すべての$k\in[d+1,2^d]$に対して、合計のサンプル複雑性に基づいて、$\widetilde\left(\frac{d^2}{\varepsilon^2\log k}\right)$の上限と下限を一致させる。

関連論文リスト

• High-accuracy sampling for diffusion models and log-concave distributions [70.90863485771405]
  本稿では,$mathrmpolylog (1/)$のステップで$$-errorを求める拡散モデルサンプリングアルゴリズムを提案する。 我々の手法は、一般的なログ凹凸分布に対する最初の$mathrmpolylog (1/)$ complexity samplerをもたらす。
  論文  参考訳（メタデータ） (2026-02-01T17:05:31Z)
• Improved sampling algorithms and Poincaré inequalities for non-log-concave distributions [2.959331374750817]
  これは$d$と$frac1epsilon$である。 $L=mathcalO(1)$と$M=mathrmpoly(d)$である。
  論文  参考訳（メタデータ） (2025-07-15T12:06:11Z)
• Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan [49.1574468325115]
  ランク1テンソルを$otimes_i=1N mathbbRd$で完了する際のサンプルと計算複雑性を再考する。 本稿では,一対のランダム線形系上で,ガウス・ヨルダンに相当するアルゴリズムを許容する問題のキャラクタリゼーションを提案する。
  論文  参考訳（メタデータ） (2024-08-10T04:26:19Z)
• 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)
• 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)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
  論文  参考訳（メタデータ） (2022-03-17T23:52:08Z)
• 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)

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

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