論文の概要: On the Optimality of the Oja's Algorithm for Online PCA
- arxiv url: http://arxiv.org/abs/2104.00512v1
- Date: Wed, 31 Mar 2021 15:02:54 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-02 13:21:49.760864
- Title: On the Optimality of the Oja's Algorithm for Online PCA
- Title(参考訳): オンラインPCAにおけるOjaアルゴリズムの最適性について
- Authors: Xin Liang
- Abstract要約: 高い確率で、任意の部分ガウス分布の主成分部分空間を近似するために、効率的でギャップのないグローバル収束率を実行することが証明されている。
収束率、すなわち近似の上界は、オフライン/古典的PCAによって得られる近似の下限を定数係数に正確に一致することを示すのはこれが初めてである。
- 参考スコア(独自算出の注目度): 1.3934770330948278
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper we analyze the behavior of the Oja's algorithm for
online/streaming principal component subspace estimation. It is proved that
with high probability it performs an efficient, gap-free, global convergence
rate to approximate an principal component subspace for any sub-Gaussian
distribution. Moreover, it is the first time to show that the convergence rate,
namely the upper bound of the approximation, exactly matches the lower bound of
an approximation obtained by the offline/classical PCA up to a constant factor.
- Abstract(参考訳): 本稿では,オンライン/ストリーミング主成分部分空間推定におけるojaアルゴリズムの挙動を解析する。
高い確率で、ガウス分布の主成分部分空間を近似するために、効率よく、ギャップフリーで大域収束速度を実行することが証明された。
さらに、収束率、すなわち近似の上界は、オフライン/古典的PCAによって得られる近似の下限を定数係数に正確に一致することを示すのはこれが初めてである。
関連論文リスト
- Distributed Markov Chain Monte Carlo Sampling based on the Alternating
Direction Method of Multipliers [143.6249073384419]
本論文では,乗算器の交互方向法に基づく分散サンプリング手法を提案する。
我々は,アルゴリズムの収束に関する理論的保証と,その最先端性に関する実験的証拠の両方を提供する。
シミュレーションでは,線形回帰タスクとロジスティック回帰タスクにアルゴリズムを配置し,その高速収束を既存の勾配法と比較した。
論文 参考訳(メタデータ) (2024-01-29T02:08:40Z) - Linear Convergence of Pre-Conditioned PI Consensus Algorithm under
Restricted Strong Convexity [6.327393762036103]
本稿では,ピアツーピアマルチエージェントネットワークにおける分散凸最適化問題について考察する。
比例積分 (PI) 制御戦略を用いることで, 固定段数をもつ様々なアルゴリズムが開発されている。
論文 参考訳(メタデータ) (2023-09-30T15:54:52Z) - Fast Computation of Optimal Transport via Entropy-Regularized
Extragradient Methods [98.85583323658366]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳(メタデータ) (2023-01-30T15:46:39Z) - Orthogonal Polynomials Approximation Algorithm (OPAA):a functional
analytic approach to estimating probability densities [0.0]
新しい直交多項式近似アルゴリズム(OPAA)を提案する。
OPAAは機能解析手法を用いて確率分布を推定する。
後部の正規化重量を推定するために応用できる。
論文 参考訳(メタデータ) (2022-11-16T00:51:00Z) - Stochastic Approximation with Decision-Dependent Distributions: Asymptotic Normality and Optimality [8.771678221101368]
我々は、アルゴリズムが使用するデータ分布が反復列に沿って進化する決定依存問題に対する近似を解析する。
軽微な仮定の下では、アルゴリズムの反復と解の偏差は正規であることを示す。
また,平均化アルゴリズムの性能は局所的に最小限であることを示す。
論文 参考訳(メタデータ) (2022-07-09T01:44:17Z) - Outlier-Robust Sparse Estimation via Non-Convex Optimization [73.18654719887205]
空間的制約が存在する場合の高次元統計量と非破壊的最適化の関連について検討する。
これらの問題に対する新規で簡単な最適化法を開発した。
結論として、効率よくステーションに収束する一階法は、これらのタスクに対して効率的なアルゴリズムを導出する。
論文 参考訳(メタデータ) (2021-09-23T17:38:24Z) - Gradient Descent Averaging and Primal-dual Averaging for Strongly Convex
Optimization [15.731908248435348]
強凸の場合の勾配降下平均化と主双進平均化アルゴリズムを開発する。
一次二重平均化は出力平均化の観点から最適な収束率を導出し、SC-PDAは最適な個々の収束を導出する。
SVMとディープラーニングモデルに関するいくつかの実験は、理論解析の正確性とアルゴリズムの有効性を検証する。
論文 参考訳(メタデータ) (2020-12-29T01:40:30Z) - Distributed Variational Bayesian Algorithms Over Sensor Networks [6.572330981878818]
一般ベイズ推論問題に対する2つの新しい分散VBアルゴリズムを提案する。
提案アルゴリズムは、核融合センターで利用可能な全データに依存する集中型VBアルゴリズムとほぼ同等の性能を有する。
論文 参考訳(メタデータ) (2020-11-27T08:12:18Z) - An Asymptotically Optimal Primal-Dual Incremental Algorithm for
Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。
非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文 参考訳(メタデータ) (2020-10-23T09:12:47Z) - Approximation Algorithms for Sparse Principal Component Analysis [57.5357874512594]
主成分分析(PCA)は、機械学習と統計学において広く使われている次元削減手法である。
スパース主成分分析(Sparse principal Component Analysis)と呼ばれる,スパース主成分負荷を求める様々な手法が提案されている。
本研究では,SPCA問題に対するしきい値の精度,時間,近似アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-06-23T04:25:36Z) - IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method [64.15649345392822]
本稿では,局所関数が滑らかで凸な分散最適化環境下での原始的手法設計のためのフレームワークを提案する。
提案手法は,加速ラグランジアン法により誘導されるサブプロブレム列を概ね解いたものである。
加速度勾配降下と組み合わせることで,収束速度が最適で,最近導出された下界と一致した新しい原始アルゴリズムが得られる。
論文 参考訳(メタデータ) (2020-06-11T18:49:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。