論文の概要: Identification of Mixtures of Discrete Product Distributions in
Near-Optimal Sample and Time Complexity
- arxiv url: http://arxiv.org/abs/2309.13993v1
- Date: Mon, 25 Sep 2023 09:50:15 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-26 16:10:03.613759
- Title: Identification of Mixtures of Discrete Product Distributions in
Near-Optimal Sample and Time Complexity
- Title（参考訳）: 準最適サンプルおよび時間複雑度における離散積分布の混合の同定
- Authors: Spencer L. Gordon, Erik Jahn, Bijan Mazaheri, Yuval Rabani, Leonard J.
Schulman
- Abstract要約: 任意の$ngeq 2k-1$に対して、サンプルの複雑さとランタイムの複雑さをどうやって達成するかを示す(1/zeta)O(k)$。
また、既知の$eOmega(k)$の下位境界を拡張して、より広い範囲の$zeta$と一致させる。
- 参考スコア（独自算出の注目度）: 6.812247730094931
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the problem of identifying, from statistics, a distribution of
discrete random variables $X_1,\ldots,X_n$ that is a mixture of $k$ product
distributions. The best previous sample complexity for $n \in O(k)$ was
$(1/\zeta)^{O(k^2 \log k)}$ (under a mild separation assumption parameterized
by $\zeta$). The best known lower bound was $\exp(\Omega(k))$. It is known that
$n\geq 2k-1$ is necessary and sufficient for identification. We show, for any
$n\geq 2k-1$, how to achieve sample complexity and run-time complexity
$(1/\zeta)^{O(k)}$. We also extend the known lower bound of $e^{\Omega(k)}$ to
match our upper bound across a broad range of $\zeta$. Our results are obtained
by combining (a) a classic method for robust tensor decomposition, (b) a novel
way of bounding the condition number of key matrices called Hadamard
extensions, by studying their action only on flattened rank-1 tensors.
- Abstract（参考訳）: 統計から、k$ の積分布の混合である離散確率変数 $x_1,\ldots,x_n$ の分布を識別する問題を考える。
n \in o(k)$ の以前の最良のサンプル複雑性は$(1/\zeta)^{o(k^2 \log k)}$であった。
最もよく知られた下界は$\exp(\Omega(k))$である。
n\geq 2k-1$ は識別に必要で十分であることが知られている。
任意の$n\geq 2k-1$に対して、サンプルの複雑さと実行時の複雑さを$(1/\zeta)^{O(k)}$にする方法を示す。
また、既知の下限である$e^{\Omega(k)}$を拡張して、より広い範囲の$\zeta$と一致させる。
私たちの結果は組み合わせることで得られます
(a)強靭なテンソル分解の古典的方法
(b)ハダマール拡大と呼ばれるキー行列の条件数を制限する新しい方法は、それらの作用を平坦化ランク1テンソルにのみ研究することである。
関連論文リスト
- Overcomplete Tensor Decomposition via Koszul-Young Flattenings [63.01248796170617]
最小ランク1項の和として$n_times n times n_3$ tensorを分解する新しいアルゴリズムを与える。
次数-d$s のさらに一般的なクラスは、定数 $C = C(d)$ に対して階数 $Cn$ を超えることができないことを示す。
論文 参考訳（メタデータ） (2024-11-21T17:41:09Z) - Sum-of-squares lower bounds for Non-Gaussian Component Analysis [33.80749804695003]
非ガウス成分分析(Non-Gaussian Component Analysis、NGCA)は、高次元データセットにおいて非ガウス方向を求める統計的タスクである。
本稿では Sum-of-Squares フレームワークにおける NGCA の複雑さについて考察する。
論文 参考訳（メタデータ） (2024-10-28T18:19:13Z) - 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) - Average-Case Complexity of Tensor Decomposition for Low-Degree
Polynomials [93.59919600451487]
多くの統計的推論タスクにおいて「統計計算ギャップ」が発生する。
1つの成分が他の成分よりもわずかに大きいランダムオーダー3分解モデルを考える。
テンソルエントリは$ll n3/2$のとき最大成分を正確に推定できるが、$rgg n3/2$のとき失敗する。
論文 参考訳（メタデータ） (2022-11-10T00:40:37Z) - Classical shadows of fermions with particle number symmetry [0.0]
我々は、$mathcalO(k2eta)$classic complexityを持つ任意の$k$-RDMに対する推定器を提供する。
ハーフフィリングの最悪の場合、我々の手法はサンプルの複雑さに4k$の利点をもたらす。
論文 参考訳（メタデータ） (2022-08-18T17:11:12Z) - Tight Bounds on the Hardness of Learning Simple Nonparametric Mixtures [9.053430799456587]
有限混合系における非パラメトリック分布の学習問題について検討する。
このようなモデルにおける成分分布を学習するために、サンプルの複雑さに厳密な境界を定めている。
論文 参考訳（メタデータ） (2022-03-28T23:53:48Z) - The Sparse Hausdorff Moment Problem, with Application to Topic Models [5.151973524974052]
我々は$m=2k$iid二進確率変数のサンプルを用いて$k$-mixtureを同定するアルゴリズムを提案する。
加法精度$w_mincdotzetaO(k)$のモーメントを知るだけで十分である。
論文 参考訳（メタデータ） (2020-07-16T04:23:57Z) - Second-Order Information in Non-Convex Stochastic Optimization: Power
and Limitations [54.42518331209581]
私たちは発見するアルゴリズムを見つけます。
epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using
$(epsilon,gamma)$surimateランダムランダムポイント。
ここでの私たちの下限は、ノイズのないケースでも新規です。
論文 参考訳（メタデータ） (2020-06-24T04:41:43Z) - 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) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。