論文の概要: Selective Multiple Power Iteration: from Tensor PCA to gradient-based
exploration of landscapes
- arxiv url: http://arxiv.org/abs/2112.12306v1
- Date: Thu, 23 Dec 2021 01:46:41 GMT
- ステータス: 処理完了
- システム内更新日: 2021-12-25 02:17:58.404878
- Title: Selective Multiple Power Iteration: from Tensor PCA to gradient-based
exploration of landscapes
- Title（参考訳）: 選択的多重電力反復:テンソルpcaから勾配に基づく景観探査へ
- Authors: Mohamed Ouerfelli, Mohamed Tamaazousti, Vincent Rivasseau
- Abstract要約: Selective Multiple Power Iterations (SMPI) はスパイクを回復する重要な問題に対処する新しいアルゴリズムである。
これらの予期せぬ性能は、ノイズが信号の回復に重要な役割を果たす強力なメカニズムに起因していることを示す。
これらの結果は、実用的および理論的応用の両方に強い影響を与える可能性がある。
- 参考スコア（独自算出の注目度）: 7.648784748888189
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We propose Selective Multiple Power Iterations (SMPI), a new algorithm to
address the important Tensor PCA problem that consists in recovering a spike
$\bf{v_0}^{\otimes k}$ corrupted by a Gaussian noise tensor $\bf{Z} \in
(\mathbb{R}^n)^{\otimes k}$ such that $\bf{T}=\sqrt{n} \beta \bf{v_0}^{\otimes
k} + \bf{Z}$ where $\beta$ is the signal-to-noise ratio (SNR). SMPI consists in
generating a polynomial number of random initializations, performing a
polynomial number of symmetrized tensor power iterations on each
initialization, then selecting the one that maximizes $\langle \bf{T},
\bf{v}^{\otimes k} \rangle$. Various numerical simulations for $k=3$ in the
conventionally considered range $n \leq 1000$ show that the experimental
performances of SMPI improve drastically upon existent algorithms and becomes
comparable to the theoretical optimal recovery. We show that these unexpected
performances are due to a powerful mechanism in which the noise plays a key
role for the signal recovery and that takes place at low $\beta$. Furthermore,
this mechanism results from five essential features of SMPI that distinguish it
from previous algorithms based on power iteration. These remarkable results may
have strong impact on both practical and theoretical applications of Tensor
PCA. (i) We provide a variant of this algorithm to tackle low-rank CP tensor
decomposition. These proposed algorithms also outperforms existent methods even
on real data which shows a huge potential impact for practical applications.
(ii) We present new theoretical insights on the behavior of SMPI and gradient
descent methods for the optimization in high-dimensional non-convex landscapes
that are present in various machine learning problems. (iii) We expect that
these results may help the discussion concerning the existence of the
conjectured statistical-algorithmic gap.
- Abstract（参考訳）: ガウスノイズテンソルである$\bf{z} \in (\mathbb{r}^n)^{\otimes k}$ によって破られたスパイク $\bf{v_0}^{\otimes k}$ から得られる重要なテンソルpca問題に対処するための新しいアルゴリズムであるsmpiを提案し、$\bf{t}=\sqrt{n} \beta \bf{v_0}^{\otimes k} + \bf{z}$ が信号対雑音比 (snr) である。
SMPIは、ランダムな初期化の多項式数を生成し、各初期化に対して対称化されたテンソルパワーイテレーションの多項式数を実行し、次に$\langle \bf{T}, \bf{v}^{\otimes k} \rangle$を選択する。
従来考えられていた範囲$n \leq 1000$の様々な数値シミュレーションは、smpiの実験性能が既存のアルゴリズムによって大幅に向上し、理論的最適回復に匹敵することを示した。
これらの予期せぬ性能は、ノイズが信号の回復に重要な役割を担い、低$\beta$で発生する強力なメカニズムによるものである。
さらに、このメカニズムは、パワーイテレーションに基づく以前のアルゴリズムと区別するSMPIの5つの重要な特徴から生じる。
これらの顕著な結果は、Tensor PCAの実用的および理論的応用に強い影響を与える可能性がある。
i) 低ランクCPテンソル分解に対処するため,本アルゴリズムの変種を提案する。
提案アルゴリズムは,実データにおいても既存の手法よりも優れており,実用的応用に大きな影響を与える可能性がある。
(ii)様々な機械学習問題に存在する高次元非凸景観における最適化のためのsmpiの挙動と勾配降下法に関する新しい理論的知見を提示する。
(iii)これらの結果は,推定された統計的利他的ギャップの存在に関する議論に有用であると考えられる。
関連論文リスト
- Improved quantum algorithm for calculating eigenvalues of differential operators and its application to estimating the decay rate of the perturbation distribution tail in stochastic inflation [0.0]
微分作用素 $mathcalL$ の最初の固有値を $mathbbRd$ 上で推定する量子アルゴリズムを提案する。
次に、量子インフレーション(quantum inflation)として知られる宇宙のインフレーションの理論的枠組みにおける問題への我々の方法の適用について考察する。
論文 参考訳（メタデータ） (2024-10-03T07:56:20Z) - Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximation [53.17668583030862]
一般関数近似の文脈において,無限水平平均逆マルコフ決定過程(AMDP)について検討する。
最適化最適化(LOOP)と呼ばれる新しいアルゴリズムフレームワークを提案する。
我々は LOOP がサブ線形 $tildemathcalO(mathrmpoly(d, mathrmsp(V*)) sqrtTbeta )$ regret を達成することを示す。
論文 参考訳（メタデータ） (2024-04-19T06:24:22Z) - Efficiently Escaping Saddle Points for Non-Convex Policy Optimization [40.0986936439803]
政策勾配(PG)は、拡張性と優れた性能のために強化学習に広く用いられている。
本稿では,ヘッセンベクトル積 (HVP) の形で二階情報を用いた分散還元二階法を提案し,サンプルの複雑さを$tildeO(epsilon-3)$とする近似二階定常点 (SOSP) に収束する。
論文 参考訳（メタデータ） (2023-11-15T12:36:45Z) - Sub-linear Regret in Adaptive Model Predictive Control [56.705978425244496]
本稿では,STT-MPC (Self-Tuning tube-based Model Predictive Control) について述べる。
システム力学を最初に認識したアルゴリズムと比較して,アルゴリズムの後悔を解析する。
論文 参考訳（メタデータ） (2023-10-07T15:07:10Z) - Permutation Compressors for Provably Faster Distributed Nonconvex
Optimization [68.8204255655161]
本稿では,Gorbunov et al (2021) の MARINA 法が,理論的な通信複雑性の観点から最先端の手法とみなすことができることを示す。
MARINAの理論は、古典的な独立圧縮機設定を超えて、潜在的にエミュレートされた圧縮機の理論を支持するものである。
論文 参考訳（メタデータ） (2021-10-07T09:38:15Z) - Reducing the Variance of Gaussian Process Hyperparameter Optimization
with Preconditioning [54.01682318834995]
プレコンディショニングは、行列ベクトル乗算を含む反復的な方法にとって非常に効果的なステップである。
プレコンディショニングには、これまで検討されていなかった付加的なメリットがあることを実証する。
基本的に無視可能なコストで、同時に分散を低減することができる。
論文 参考訳（メタデータ） (2021-07-01T06:43:11Z) - Lattice partition recovery with dyadic CART [79.96359947166592]
我々は、$d$次元格子上の加法ガウス雑音によって破損したピースワイド定値信号について検討する。
この形式のデータは、多くのアプリケーションで自然に発生し、統計処理や信号処理の文献において、信号の検出やテスト、ノイズの除去、推定といったタスクが広く研究されている。
本稿では,未知の信号の一貫性領域によって誘導される格子の分割を推定する,分割回復の問題について考察する。
我々は、DCARTベースの手順が、下位分割を$sigma2 k*の順序で一貫して推定することを証明した。
論文 参考訳（メタデータ） (2021-05-27T23:41:01Z) - Low-rank State-action Value-function Approximation [11.026561518386025]
いくつかの高次元状態問題は、本質的な低ランク構造によってよく近似できる。
本稿では,$Q(s, a)$行列の低ランク分解を推定するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-04-18T10:31:39Z) - New Riemannian preconditioned algorithms for tensor completion via
polyadic decomposition [10.620193291237262]
これらのアルゴリズムは、ポリアジック分解形態におけるローランクテンソルの因子行列の積空間上の非ユークリッド計量を利用する。
提案された勾配降下アルゴリズムがテンソル完備問題の定常点にグローバルに収束することを証明する。
合成データと実世界のデータの数値計算結果から,提案アルゴリズムは最先端アルゴリズムよりもメモリと時間において効率的であることが示唆された。
論文 参考訳（メタデータ） (2021-01-26T22:11:06Z) - On Function Approximation in Reinforcement Learning: Optimism in the
Face of Large State Spaces [208.67848059021915]
強化学習のコアにおける探索・探索トレードオフについて検討する。
特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。
私たちの後悔の限界はエピソードの数とは無関係です。
論文 参考訳（メタデータ） (2020-11-09T18:32:22Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。