論文の概要: SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptions

• arxiv url: http://arxiv.org/abs/2403.04744v1
• Date: Thu, 7 Mar 2024 18:49:32 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-08 12:54:25.445327
• Title: SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptions
• Title（参考訳）: ウェイカー推定による非ガウス成分分析のためのSQ下界
• Authors: Ilias Diakonikolas, Daniel Kane, Lisheng Ren and Yuxin Sun
• Abstract要約: 統計的クエリモデルにおける非ガウス成分分析(NGCA)の複雑さについて検討する。 本研究は, NGCAの場合, モーメントマッチング条件のみにおいて, ほぼ最適SQ下限を証明した。
• 参考スコア（独自算出の注目度）: 50.20087216230159
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the complexity of Non-Gaussian Component Analysis (NGCA) in the Statistical Query (SQ) model. Prior work developed a general methodology to prove SQ lower bounds for this task that have been applicable to a wide range of contexts. In particular, it was known that for any univariate distribution $A$ satisfying certain conditions, distinguishing between a standard multivariate Gaussian and a distribution that behaves like $A$ in a random hidden direction and like a standard Gaussian in the orthogonal complement, is SQ-hard. The required conditions were that (1) $A$ matches many low-order moments with the standard univariate Gaussian, and (2) the chi-squared norm of $A$ with respect to the standard Gaussian is finite. While the moment-matching condition is necessary for hardness, the chi-squared condition was only required for technical reasons. In this work, we establish that the latter condition is indeed not necessary. In particular, we prove near-optimal SQ lower bounds for NGCA under the moment-matching condition only. Our result naturally generalizes to the setting of a hidden subspace. Leveraging our general SQ lower bound, we obtain near-optimal SQ lower bounds for a range of concrete estimation tasks where existing techniques provide sub-optimal or even vacuous guarantees.
• Abstract（参考訳）: 統計的クエリ(SQ)モデルにおける非ガウス成分分析(NGCA)の複雑さについて検討する。 先行研究は、幅広い文脈に適用可能な、このタスクのSQの下限を証明する一般的な方法論を開発した。 特に、ある条件を満たす任意の単変量分布$A$に対して、標準の多変量ガウス分布とランダムに隠れた方向に振る舞い、直交補空間の標準ガウス分布のように振る舞う分布とを区別することが知られている。 要求される条件は、(1) $a$ は標準の非定値ガウス型と多くの低次モーメントに一致し、(2)標準ガウス型に関して$a$ の2乗ノルムは有限である。 硬度にはモーメントマッチング条件が必要であったが, 技術的理由からカイ二乗条件が必要であった。 本研究では,後者の条件が本当に必要ではないことを確かめる。 特に, NGCAの場合, モーメントマッチング条件のみにおいて, ほぼ最適SQ下限を示す。 この結果は自然に隠れた部分空間の設定に一般化する。 一般SQの下限を活用すれば、既存の手法が準最適あるいは空虚な保証を提供するような、様々な具体的な推定タスクに対して、ほぼ最適SQ下限が得られる。

関連論文リスト

• A Stochastic Proximal Method for Nonsmooth Regularized Finite Sum Optimization [7.014966911550542]
  スパースサブ構造を検索するために,非滑らかな正規化を伴うディープニューラルネットワークをトレーニングする問題を考察する。 我々は、収束と最悪のケースの複雑さが勾配のリプシッツ定数の知識や近似なしで確立されるSR2と呼ばれる新しい解法を導出する。 CIFAR-10とCIFAR-100で訓練されたネットワークインスタンスの実験により、SR2はProxGENやProxSGDのような関連する手法よりも常に高い空間性と精度を達成することが示された。
  論文  参考訳（メタデータ） (2022-06-14T00:28:44Z)
• Optimal SQ Lower Bounds for Robustly Learning Discrete Product Distributions and Ising Models [45.14286976373306]
  我々は、離散的な高次元分布の特定の族をしっかりと学習するために、最適な統計的クエリー(SQ)の下位境界を確立する。 我々のSQローバウンドは、これらの問題に対する既知のアルゴリズムのエラー保証と一致し、これらのタスクの現在の上限が最善であることを示す。
  論文  参考訳（メタデータ） (2022-06-09T16:10:23Z)
• Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models [15.857373057387669]
  無限大極限におけるランダム最適化問題のアンサンブル上での任意の一定レベル(層数)における濃度特性を証明した。 我々の分析は、サドル点近似の和対パス積分によって理解することができる。 一定レベルにおけるQAOAの性能は、$qge 4$のときの純$q$-spinモデルの最適性から外れ、偶数であることを示す。
  論文  参考訳（メタデータ） (2022-04-21T17:40:39Z)
• Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization [61.26619639722804]
  滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。 提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
  論文  参考訳（メタデータ） (2022-02-26T19:10:48Z)
• Near-Optimal Statistical Query Lower Bounds for Agnostically Learning Intersections of Halfspaces with Gaussian Marginals [10.06689891744466]
  本稿では,ガウス分布下での中間空間の学習に関するよく研究された問題について,難易度学習モデルを用いて考察する。 下界の2つの変種を証明し、それぞれがダイアコニコラスら (2021) の成分と、Boolean の設定に対する SQ 下界に対する異なる以前のアプローチ(拡張)を組み合わせた。
  論文  参考訳（メタデータ） (2022-02-10T15:34:10Z)
• Non-Gaussian Component Analysis via Lattice Basis Reduction [56.98280399449707]
  非ガウス成分分析(NGCA)は分布学習問題である。 我々は,NGCA に対して,$A$ が離散的あるいはほぼ離散的であるような効率的なアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2021-12-16T18:38:02Z)
• Misspecified Gaussian Process Bandit Optimization [59.30399661155574]
  カーネル化されたバンディットアルゴリズムは、この問題に対して強い経験的および理論的性能を示した。 本稿では、未知関数を$epsilon$-一様近似で近似できるエンフェミス特定カーネル化帯域設定を、ある再生カーネルヒルベルト空間(RKHS)において有界ノルムを持つ関数で導入する。 提案アルゴリズムは,不特定性に関する事前知識を伴わず,$epsilon$への最適依存を実現する。
  論文  参考訳（メタデータ） (2021-11-09T09:00:02Z)
• Constrained Optimization Involving Nonconvex $\ell_p$ Norms: Optimality Conditions, Algorithm and Convergence [4.886985244621422]
  我々は $ell_p$ ノルムの次数と $ell_p$ 球の正規錐の次数を計算する。 逐次最適性条件は反復的に重み付けされたアルゴリズムに対して容易に満足できることを示す。
  論文  参考訳（メタデータ） (2021-10-27T02:17:42Z)
• A general sample complexity analysis of vanilla policy gradient [101.16957584135767]
  政策勾配(PG)は、最も一般的な強化学習(RL)問題の1つである。 PG軌道の「バニラ」理論的理解は、RL問題を解く最も一般的な方法の1つである。
  論文  参考訳（メタデータ） (2021-07-23T19:38:17Z)

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

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