論文の概要: Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector
Problems
- arxiv url: http://arxiv.org/abs/2112.14738v1
- Date: Wed, 29 Dec 2021 18:46:52 GMT
- ステータス: 処理完了
- システム内更新日: 2021-12-30 15:36:34.355624
- Title: Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector
Problems
- Title(参考訳): 非凸確率スケール勾配Descentと一般化固有ベクトル問題
- Authors: Chris Junchi Li, Michael I. Jordan
- Abstract要約: オンライン相関解析の問題から,emphStochastic Scaled-Gradient Descent (SSD)アルゴリズムを提案する。
我々はこれらのアイデアをオンライン相関解析に適用し、局所収束率を正規性に比例した最適な1時間スケールのアルゴリズムを初めて導いた。
- 参考スコア(独自算出の注目度): 98.34292831923335
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Motivated by the problem of online canonical correlation analysis, we propose
the \emph{Stochastic Scaled-Gradient Descent} (SSGD) algorithm for minimizing
the expectation of a stochastic function over a generic Riemannian manifold.
SSGD generalizes the idea of projected stochastic gradient descent and allows
the use of scaled stochastic gradients instead of stochastic gradients. In the
special case of a spherical constraint, which arises in generalized eigenvector
problems, we establish a nonasymptotic finite-sample bound of $\sqrt{1/T}$, and
show that this rate is minimax optimal, up to a polylogarithmic factor of
relevant parameters. On the asymptotic side, a novel trajectory-averaging
argument allows us to achieve local asymptotic normality with a rate that
matches that of Ruppert-Polyak-Juditsky averaging. We bring these ideas
together in an application to online canonical correlation analysis, deriving,
for the first time in the literature, an optimal one-time-scale algorithm with
an explicit rate of local asymptotic convergence to normality. Numerical
studies of canonical correlation analysis are also provided for synthetic data.
- Abstract(参考訳): オンライン正準相関解析の問題により、一般リーマン多様体上の確率関数の期待を最小化するための \emph{Stochastic Scaled-Gradient Descent} (SSGD) アルゴリズムを提案する。
SSGDは射影確率勾配降下の概念を一般化し、確率勾配の代わりにスケールされた確率勾配を利用することができる。
一般化固有ベクトル問題において生じる球面制約の特別な場合において、非漸近的有限サンプル境界を $\sqrt{1/t}$ と定め、この速度がミニマックス最適であり、関連するパラメータの多対数係数までであることを示す。
漸近的側では、新しい軌道平均論により、ラッパート-ポリアク-ジュディツキー平均法と一致する率で局所漸近正規性を達成することができる。
我々はこれらのアイデアをオンライン正準相関解析に適用し、文献の中で初めて、局所漸近収束率を正規性に比例した最適な1時間スケールのアルゴリズムを導出した。
合成データには正準相関解析の数値的研究も提供される。
関連論文リスト
- Non-asymptotic convergence analysis of the stochastic gradient
Hamiltonian Monte Carlo algorithm with discontinuous stochastic gradient with
applications to training of ReLU neural networks [8.058385158111207]
我々は、勾配ハミルトニアンモンテカルロのWasserstein-1 と Wasserstein-2 距離の目標測度への収束の非漸近解析を提供する。
本研究の主な成果を説明するために、定量推定に関する数値実験と、金融と人工知能に関連するReLUニューラルネットワークに関わるいくつかの問題について考察する。
論文 参考訳(メタデータ) (2024-09-25T17:21:09Z) - A Mean-Field Analysis of Neural Stochastic Gradient Descent-Ascent for Functional Minimax Optimization [90.87444114491116]
本稿では,超パラメトリック化された2層ニューラルネットワークの無限次元関数クラス上で定義される最小最適化問題について検討する。
i) 勾配降下指数アルゴリズムの収束と, (ii) ニューラルネットワークの表現学習に対処する。
その結果、ニューラルネットワークによって誘導される特徴表現は、ワッサーシュタイン距離で測定された$O(alpha-1)$で初期表現から逸脱することが許された。
論文 参考訳(メタデータ) (2024-04-18T16:46:08Z) - Accelerated stochastic approximation with state-dependent noise [7.4648480208501455]
勾配観測における2次雑音に対する一般仮定の下での滑らかな凸最適化問題を考察する。
このような問題は、統計学におけるよく知られた一般化された線形回帰問題において、様々な応用において自然に発生する。
SAGDとSGEは、適切な条件下で、最適収束率を達成することを示す。
論文 参考訳(メタデータ) (2023-07-04T06:06:10Z) - Curvature-Independent Last-Iterate Convergence for Games on Riemannian
Manifolds [77.4346324549323]
本研究では, 多様体の曲率に依存しないステップサイズが, 曲率非依存かつ直線的最終点収束率を達成することを示す。
我々の知る限りでは、曲率非依存率や/または最終点収束の可能性はこれまでに検討されていない。
論文 参考訳(メタデータ) (2023-06-29T01:20:44Z) - Stochastic Mirror Descent for Large-Scale Sparse Recovery [13.500750042707407]
本稿では,2次近似の高次元スパースパラメータの統計的推定への応用について論じる。
提案アルゴリズムは, 回帰器分布の弱い仮定の下で, 推定誤差の最適収束を実現する。
論文 参考訳(メタデータ) (2022-10-23T23:23:23Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳(メタデータ) (2022-06-17T06:10:20Z) - Spectral clustering under degree heterogeneity: a case for the random
walk Laplacian [83.79286663107845]
本稿では,ランダムウォークラプラシアンを用いたグラフスペクトル埋め込みが,ノード次数に対して完全に補正されたベクトル表現を生成することを示す。
次数補正ブロックモデルの特別な場合、埋め込みはK個の異なる点に集中し、コミュニティを表す。
論文 参考訳(メタデータ) (2021-05-03T16:36:27Z) - Convergence Analysis of Homotopy-SGD for non-convex optimization [43.71213126039448]
ホモトピー法とSGDを組み合わせた一階述語アルゴリズム、Gradienty-Stoch Descent (H-SGD)を提案する。
いくつかの仮定の下で、提案した問題の理論的解析を行う。
実験の結果,H-SGDはSGDより優れていた。
論文 参考訳(メタデータ) (2020-11-20T09:50:40Z) - ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。
我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。
有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
論文 参考訳(メタデータ) (2020-08-28T14:46:56Z) - Non-asymptotic bounds for stochastic optimization with biased noisy
gradient oracles [8.655294504286635]
関数の測定値が推定誤差を持つ設定を捉えるために,バイアス付き勾配オラクルを導入する。
提案するオラクルは,例えば,独立分散シミュレーションと同一分散シミュレーションのバッチによるリスク計測推定の実践的な状況にある。
論文 参考訳(メタデータ) (2020-02-26T12:53:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。