論文の概要: Stationary Behavior of Constant Stepsize SGD Type Algorithms: An Asymptotic Characterization

• arxiv url: http://arxiv.org/abs/2111.06328v1
• Date: Thu, 11 Nov 2021 17:39:50 GMT
• ステータス: 処理完了
• システム内更新日: 2021-11-12 16:58:36.054732
• Title: Stationary Behavior of Constant Stepsize SGD Type Algorithms: An Asymptotic Characterization
• Title（参考訳）: 定常ステップによるsgd型アルゴリズムの定常挙動:漸近的特徴付け
• Authors: Zaiwei Chen, Shancong Mou, and Siva Theja Maguluri
• Abstract要約: 一定段差がゼロとなる極限において, 適切にスケールされた定常分布の挙動について検討する。 極限スケールの定常分布は積分方程式の解であることを示す。
• 参考スコア（独自算出の注目度）: 4.932130498861987
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Stochastic approximation (SA) and stochastic gradient descent (SGD) algorithms are work-horses for modern machine learning algorithms. Their constant stepsize variants are preferred in practice due to fast convergence behavior. However, constant step stochastic iterative algorithms do not converge asymptotically to the optimal solution, but instead have a stationary distribution, which in general cannot be analytically characterized. In this work, we study the asymptotic behavior of the appropriately scaled stationary distribution, in the limit when the constant stepsize goes to zero. Specifically, we consider the following three settings: (1) SGD algorithms with smooth and strongly convex objective, (2) linear SA algorithms involving a Hurwitz matrix, and (3) nonlinear SA algorithms involving a contractive operator. When the iterate is scaled by $1/\sqrt{\alpha}$, where $\alpha$ is the constant stepsize, we show that the limiting scaled stationary distribution is a solution of an integral equation. Under a uniqueness assumption (which can be removed in certain settings) on this equation, we further characterize the limiting distribution as a Gaussian distribution whose covariance matrix is the unique solution of a suitable Lyapunov equation. For SA algorithms beyond these cases, our numerical experiments suggest that unlike central limit theorem type results: (1) the scaling factor need not be $1/\sqrt{\alpha}$, and (2) the limiting distribution need not be Gaussian. Based on the numerical study, we come up with a formula to determine the right scaling factor, and make insightful connection to the Euler-Maruyama discretization scheme for approximating stochastic differential equations.
• Abstract（参考訳）: 確率近似 (SA) と確率勾配降下 (SGD) アルゴリズムは、現代の機械学習アルゴリズムのワークホースである。 それらの定常段階的変種は、高速収束挙動のために実際に好まれる。 しかし、定数ステップ確率反復アルゴリズムは漸近的に最適解に収束するのではなく、解析的に特徴づけられない定常分布を持つ。 本研究では, 定段化が0になる極限において, 適度にスケールされた定常分布の漸近的挙動について検討する。 具体的には,(1)滑らかで凸度の高いSGDアルゴリズム,(2)Hurwitz行列を含む線形SAアルゴリズム,(3)契約演算子を含む非線形SAアルゴリズムの3つの設定を考える。 反復が 1/\sqrt{\alpha}$ でスケールすると、$\alpha$ は定数ステップサイズであり、制限されたスケールされた定常分布は積分方程式の解であることを示す。 この方程式上の一意性仮定(特定の設定で除去できる)の下で、この極限分布を、共分散行列が適切なリャプノフ方程式の唯一の解であるガウス分布として特徴づける。 これらの場合を超えるsaアルゴリズムについて、我々の数値実験は中央極限定理の型と異なり、(1)スケーリング係数は 1/\sqrt{\alpha}$ でなければならず、(2) 制限分布はガウス分布である必要はないことを示唆している。 数値的な研究に基づいて、正しいスケーリング係数を決定する公式を考案し、確率微分方程式を近似するオイラー・丸山離散化スキームに洞察力のある接続を行う。

関連論文リスト

• Fully Zeroth-Order Bilevel Programming via Gaussian Smoothing [7.143879014059895]
  ビルベル問題の解法としてゼロ階近似アルゴリズムを研究・解析する。 我々の知る限りでは、完全ゼロ階二階最適化アルゴリズムのためにサンプル境界が確立されたのはこれが初めてである。
  論文  参考訳（メタデータ） (2024-03-29T21:12:25Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  制約付き非線形最適化問題のオンライン統計的推測を考察する。 これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
  論文  参考訳（メタデータ） (2022-05-27T00:34:03Z)
• Mean-Square Analysis with An Application to Optimal Dimension Dependence of Langevin Monte Carlo [60.785586069299356]
  この研究は、2-ワッサーシュタイン距離におけるサンプリング誤差の非同相解析のための一般的な枠組みを提供する。 我々の理論解析は数値実験によってさらに検証される。
  論文  参考訳（メタデータ） (2021-09-08T18:00:05Z)
• A stochastic linearized proximal method of multipliers for convex stochastic optimization with expectation constraints [8.133190610747974]
  計算可能近似型アルゴリズム,すなわち乗算器の線形化近近凸法を提案する。 予備的な数値計算の結果は,提案アルゴリズムの性能を示すものである。
  論文  参考訳（メタデータ） (2021-06-22T07:24:17Z)
• Sample Complexity Bounds for Two Timescale Value-based Reinforcement Learning Algorithms [65.09383385484007]
  2つの時間スケール近似(SA)は、値に基づく強化学習アルゴリズムで広く使われている。 本稿では,2つの時間スケール線形および非線形TDCとGreedy-GQアルゴリズムの漸近収束率について検討する。
  論文  参考訳（メタデータ） (2020-11-10T11:36:30Z)
• ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
  第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。 我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。 有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
  論文  参考訳（メタデータ） (2020-08-28T14:46:56Z)
• Inexact and Stochastic Generalized Conditional Gradient with Augmented Lagrangian and Proximal Step [2.0196229393131726]
  我々は著者の以前の論文で開発されたCGALPアルゴリズムの不正確さとバージョンを分析した。 これにより、いくつかの勾配、項、および/または線形最小化オラクルを不正確な方法で計算することができる。 ラグランジアンのアフィン制約の最適性と実現可能性への収束を示す。
  論文  参考訳（メタデータ） (2020-05-11T14:52:16Z)
• On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration [115.1954841020189]
  The inequality and non-asymptotic properties of approximation procedure with Polyak-Ruppert averaging。 一定のステップサイズと無限大となる反復数を持つ平均的反復数に対する中心極限定理(CLT)を証明する。
  論文  参考訳（メタデータ） (2020-04-09T17:54:18Z)

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

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