論文の概要: Free Energy Wells and Overlap Gap Property in Sparse PCA

• arxiv url: http://arxiv.org/abs/2006.10689v1
• Date: Thu, 18 Jun 2020 17:18:02 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-19 14:39:15.720213
• Title: Free Energy Wells and Overlap Gap Property in Sparse PCA
• Title（参考訳）: スパースPCAにおける自由エネルギー井戸とオーバーラップギャップ特性
• Authors: G\'erard Ben Arous, Alexander S. Wein, Ilias Zadik
• Abstract要約: 我々は「ハード」体制におけるスパースPCA問題(主成分分析)の変種について検討する。 問題に自然に関連付けられた様々なギブズ測度に対する自由エネルギー井戸の深さの有界性を示す。 我々は、オーバーラップギャップ特性(OGP)がハードレジームの重要な部分を占めていることを証明した。
• 参考スコア（独自算出の注目度）: 81.64027805404483
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study a variant of the sparse PCA (principal component analysis) problem in the "hard" regime, where the inference task is possible yet no polynomial-time algorithm is known to exist. Prior work, based on the low-degree likelihood ratio, has conjectured a precise expression for the best possible (sub-exponential) runtime throughout the hard regime. Following instead a statistical physics inspired point of view, we show bounds on the depth of free energy wells for various Gibbs measures naturally associated to the problem. These free energy wells imply hitting time lower bounds that corroborate the low-degree conjecture: we show that a class of natural MCMC (Markov chain Monte Carlo) methods (with worst-case initialization) cannot solve sparse PCA with less than the conjectured runtime. These lower bounds apply to a wide range of values for two tuning parameters: temperature and sparsity misparametrization. Finally, we prove that the Overlap Gap Property (OGP), a structural property that implies failure of certain local search algorithms, holds in a significant part of the hard regime.
• Abstract（参考訳）: 本研究では,「ハード」状態におけるスパースpca (principal component analysis, 主成分分析) 問題の変種について検討した。 先行研究は、低度度度比に基づいて、ハードレジーム全体を通して最高の(準指数的な)実行時の正確な表現を予想している。 代わりに統計物理学に触発された視点に従い、問題に自然に関連する様々なギブズ測度に対する自由エネルギー井戸の深さの境界を示す。 これらの自由エネルギー井戸は、低次予想を共起する時間下界にぶつかる:我々は、(最悪の場合の初期化を伴う)自然なmcmc(マルコフ連鎖モンテカルロ)メソッドのクラスは、予想されたランタイムよりも少ないsparse pcaを解決できないことを示す。 これらの下限は、温度とスパーシティのミスパラメトリゼーションという2つのチューニングパラメータの幅広い値に適用できる。 最後に,特定の局所探索アルゴリズムの故障を示唆する構造的特性であるオーバーラップギャップ特性(OGP)が,ハードレジームの重要な部分を占めていることを証明した。

関連論文リスト

• Stochastic Approximation with Unbounded Markovian Noise: A General-Purpose Theorem [7.443139252028032]
  非有界な状態空間と報酬関数を持つ平均逆強化学習を考える。 近年の研究では、この問題をアクター批判の枠組みで研究している。 線形関数近似を用いた時間差分学習(TD)について検討した。
  論文  参考訳（メタデータ） (2024-10-29T03:40:53Z)
• Lower Bounds for Learning in Revealing POMDPs [88.23337313766355]
  本稿では, 難易度の高い環境下での強化学習(RL)の基本的限界について検討する。 Emphmulti-steping POMDPs に対して、潜伏状態空間依存はサンプル複雑性において少なくとも$Omega(S1.5)$であることを示す。
  論文  参考訳（メタデータ） (2023-02-02T18:59:30Z)
• On constant-time quantum annealing and guaranteed approximations for graph optimization problems [0.0]
  量子アニーリング(Quantum Annealing, QA)は、量子系の連続的な進化が目的関数の最小値を見つけるために用いられる計算フレームワークである。 本稿では、理論物理学、リーブ・ロビンソン境界(LR)から借用した手法を用いて、短時間の量子アニールにより定数係数の近似比が保証されることを示す新しいツールを開発する。 我々の結果は、異なるが関連するQAOA(量子最適化アルゴリズム)フレームワークで得られたよく知られたものと類似している。
  論文  参考訳（メタデータ） (2022-02-03T15:23:18Z)
• Nonparametric estimation of continuous DPPs with kernel methods [0.0]
  パラメトリックおよび非パラメトリック推論法は、有限の場合、すなわち、点パターンが有限の基底集合に存在する場合において提案されている。 我々は、この最大可能性(MLE)問題の制限バージョンが、RKHSにおける非負関数に対する最近の表現定理の範囲内にあることを示す。 この有限次元問題を解くための固定点アルゴリズムを提案し,解析し,実証する。
  論文  参考訳（メタデータ） (2021-06-27T11:57:14Z)
• A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs [117.82903457289584]
  有限水平マルコフ決定過程(MDPs)における新たな問題依存的下界を導出する。 我々の下界は一般の場合よりもかなり小さく、最小の作用ギャップでスケールしないことが示される。 この最後の結果($poly(H)$の条件で、$H$は地平線である)は、楽観的なアルゴリズムのポリシーギャップに基づいて、後悔の意を表すことによって達成可能であることを示す。
  論文  参考訳（メタデータ） (2021-06-24T13:46:09Z)
• The Variational Method of Moments [65.91730154730905]
  条件モーメント問題は、観測可能量の観点から構造因果パラメータを記述するための強力な定式化である。 OWGMMの変動最小値再構成により、条件モーメント問題に対する非常に一般的な推定器のクラスを定義する。 同じ種類の変分変換に基づく統計的推測のためのアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2020-12-17T07:21:06Z)
• Computational Barriers to Estimation from Low-Degree Polynomials [81.67886161671379]
  本研究では,隠れ構造物の存在を検知する作業において,低次構造物のパワーについて検討する。 大規模な「信号+雑音」問題に対して、任意の程度に達成可能な最良の平均二乗誤差に対して、ユーザフレンドリな下界を与える。 応用として,植込みサブマトリクスに対する低次平均2乗誤差の厳密な評価と高密度サブグラフ問題について述べる。
  論文  参考訳（メタデータ） (2020-08-05T17:52:10Z)
• POLY-HOOT: Monte-Carlo Planning in Continuous Space MDPs with Non-Asymptotic Analysis [24.373900721120286]
  連続的な状態-作用空間を持つ環境でのモンテカルロ計画を考える。 我々は,モンテカルロ計画に連続的な武装バンディット戦略を付加するアルゴリズムであるPoly-HOOTを紹介する。 非定常バンディット問題において,HOOアルゴリズムが拡張されたことを初めて後悔する。
  論文  参考訳（メタデータ） (2020-06-08T15:23:19Z)
• Targeted free energy estimation via learned mappings [66.20146549150475]
  自由エネルギー摂動 (FEP) は60年以上前にズワンツィヒによって自由エネルギー差を推定する方法として提案された。 FEPは、分布間の十分な重複の必要性という厳しい制限に悩まされている。 目標自由エネルギー摂動(Targeted Free Energy Perturbation)と呼ばれるこの問題を緩和するための1つの戦略は、オーバーラップを増やすために構成空間の高次元マッピングを使用する。
  論文  参考訳（メタデータ） (2020-02-12T11:10:00Z)

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

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