論文の概要: Computing High-dimensional Confidence Sets for Arbitrary Distributions

• arxiv url: http://arxiv.org/abs/2504.02723v1
• Date: Thu, 03 Apr 2025 16:05:10 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-04 12:57:27.147312
• Title: Computing High-dimensional Confidence Sets for Arbitrary Distributions
• Title（参考訳）: 任意分布に対する高次元信頼集合の計算
• Authors: Chao Gao, Liren Shan, Vaidehi Srinivas, Aravindan Vijayaraghavan,
• Abstract要約: 最良球の体積と競合する体積が$exp(tildeO(d2/3)$因子)の信頼集合を求めるアルゴリズムが見つかる。 我々の結果は、信頼セットの適切な(不適切な)学習と適切な(不適切な)学習を、興味深い分離を提供する。
• 参考スコア（独自算出の注目度）: 22.923139209762788
• License:
• Abstract: We study the problem of learning a high-density region of an arbitrary distribution over $\mathbb{R}^d$. Given a target coverage parameter $\delta$, and sample access to an arbitrary distribution $D$, we want to output a confidence set $S \subset \mathbb{R}^d$ such that $S$ achieves $\delta$ coverage of $D$, i.e., $\mathbb{P}_{y \sim D} \left[ y \in S \right] \ge \delta$, and the volume of $S$ is as small as possible. This is a central problem in high-dimensional statistics with applications in finding confidence sets, uncertainty quantification, and support estimation. In the most general setting, this problem is statistically intractable, so we restrict our attention to competing with sets from a concept class $C$ with bounded VC-dimension. An algorithm is competitive with class $C$ if, given samples from an arbitrary distribution $D$, it outputs in polynomial time a set that achieves $\delta$ coverage of $D$, and whose volume is competitive with the smallest set in $C$ with the required coverage $\delta$. This problem is computationally challenging even in the basic setting when $C$ is the set of all Euclidean balls. Existing algorithms based on coresets find in polynomial time a ball whose volume is $\exp(\tilde{O}( d/ \log d))$-factor competitive with the volume of the best ball. Our main result is an algorithm that finds a confidence set whose volume is $\exp(\tilde{O}(d^{2/3}))$ factor competitive with the optimal ball having the desired coverage. The algorithm is improper (it outputs an ellipsoid). Combined with our computational intractability result for proper learning balls within an $\exp(\tilde{O}(d^{1-o(1)}))$ approximation factor in volume, our results provide an interesting separation between proper and (improper) learning of confidence sets.
• Abstract（参考訳）: 任意の分布の高密度領域を$\mathbb{R}^d$で学習する問題について検討する。 対象のカバレッジパラメータ $\delta$ と任意の分布 $D$ へのサンプルアクセスが与えられたら、$S$ が $D$ の$\delta$ のカバレッジを達成させるような信頼セット $S \subset \mathbb{R}^d$ を出力し、$S$ が$D$ のカバレッジを達成し、すなわち $\mathbb{P}_{y \sim D} \left[ y \in S \right] \ge \delta$ を出力し、$S$ の体積は可能な限り小さい。 これは高次元統計学における中心的な問題であり、信頼セットの発見、不確実性定量化、サポート推定などへの応用がある。 最も一般的な設定では、この問題は統計的に難易度が高いので、我々はVC次元の有界な概念クラス$C$の集合との競合に注意を向ける。 アルゴリズムがクラス$C$と競合するのは、任意の分布のサンプルが$D$であれば、$\delta$のカバレッジが$D$に達する集合を多項式時間で出力し、そのボリュームが$C$の最小のセットと$\delta$のカバレッジが$\delta$である場合である。 この問題は、$C$がすべてのユークリッド球の集合であるときでも計算的に困難である。 既存のコアセットに基づくアルゴリズムは、体積が$\exp(\tilde{O}(d/ \log d))$-factor である球が最良の球の体積と競合する多項式時間に現れる。 我々の主な結果は、体積が$\exp(\tilde{O}(d^{2/3}))$係数が所望のカバレッジを持つ最適球と競合する信頼集合を求めるアルゴリズムである。 アルゴリズムは不適切な(楕円体を出力する)。 この結果と,$\exp(\tilde{O}(d^{1-o(1)}))$近似係数内の固有学習球に対する計算的難易度を組み合わせることで,信頼集合の適切な学習と(不適切な)学習を分離する。

関連論文リスト

• A New Rejection Sampling Approach to $k$-$\mathtt{means}$++ With Improved Trade-Offs [0.12289361708127876]
  単純かつ効果的なリジェクションサンプリングに基づくアプローチで,$k$-$mathttmeans$++ を高速化する。 最初のメソッドは $tildeO(mathttnnz (mathcalX) + beta k2d)$ で実行されます。 第2の手法は,計算コストと解品質の新たなトレードオフを示す。
  論文  参考訳（メタデータ） (2025-02-04T08:05:34Z)
• Statistical Query Lower Bounds for Learning Truncated Gaussians [43.452452030671694]
  この問題のSQアルゴリズムの複雑さは、$dmathrmpoly (1/epsilon)$であり、クラス$mathcalC$が単純である場合でも、$mathrmpoly(d/epsilon)が情報理論的に十分であることを示す。
  論文  参考訳（メタデータ） (2024-03-04T18:30:33Z)
• 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)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。 この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
  論文  参考訳（メタデータ） (2021-08-19T16:16:48Z)
• Efficient inference of interventional distributions [13.31079561447385]
  有限個の観測値から因果ベイズネットワーク内の干渉分布を効率的に推定する問題を考察する。 我々は、$mathbfY$ が任意の集合であるとき、グラフ同型問題を含む統計的ゼロ知識を持つ全ての問題が効率的なランダム化アルゴリズムを持っていなければ、$varepsilon$-close である分布の評価器を$P_bf x(mathbfY)$ に出力する効率的なアルゴリズムは存在しないことを示した。
  論文  参考訳（メタデータ） (2021-07-25T02:40:01Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。 構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
  論文  参考訳（メタデータ） (2020-12-14T18:14:08Z)
• 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)
• Maximizing Determinants under Matroid Constraints [69.25768526213689]
  我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。 この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
  論文  参考訳（メタデータ） (2020-04-16T19:16:38Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)
• 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)

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

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