論文の概要: Linear Convergence of Generalized Mirror Descent with Time-Dependent Mirrors

• arxiv url: http://arxiv.org/abs/2009.08574v2
• Date: Wed, 6 Oct 2021 15:09:20 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-17 02:23:43.671492
• Title: Linear Convergence of Generalized Mirror Descent with Time-Dependent Mirrors
• Title（参考訳）: 時間依存鏡を用いた一般鏡の線形収束
• Authors: Adityanarayanan Radhakrishnan and Mikhail Belkin and Caroline Uhler
• Abstract要約: 時間依存ミラーを用いたミラー降下の一般化のためのPLに基づく解析法を提案する。 この結果は十分な条件を確立し、ミラー降下率の収束学習を提供する。 関数に対しては、この解に対してGMDの補間解が存在することを示唆する。
• 参考スコア（独自算出の注目度）: 23.738242876364865
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Polyak-Lojasiewicz (PL) inequality is a sufficient condition for establishing linear convergence of gradient descent, even in non-convex settings. While several recent works use a PL-based analysis to establish linear convergence of stochastic gradient descent methods, the question remains as to whether a similar analysis can be conducted for more general optimization methods. In this work, we present a PL-based analysis for linear convergence of generalized mirror descent (GMD), a generalization of mirror descent with a possibly time-dependent mirror. GMD subsumes popular first order optimization methods including gradient descent, mirror descent, and preconditioned gradient descent methods such as Adagrad. Since the standard PL analysis cannot be extended naturally from GMD to stochastic GMD, we present a Taylor-series based analysis to establish sufficient conditions for linear convergence of stochastic GMD. As a corollary, our result establishes sufficient conditions and provides learning rates for linear convergence of stochastic mirror descent and Adagrad. Lastly, for functions that are locally PL*, our analysis implies existence of an interpolating solution and convergence of GMD to this solution.
• Abstract（参考訳）: Polyak-Lojasiewicz (PL) の不等式は、非凸条件においても勾配降下の線形収束を確立するのに十分な条件である。 確率的勾配降下法の線形収束を確立するためにpl解析を用いた最近の研究はいくつかあるが、より一般的な最適化法で同様の解析が行えるかどうかという疑問が残る。 本稿では,時間依存ミラーを用いたミラー降下の一般化である一般化ミラー降下(gmd)の線形収束に関するplに基づく解析について述べる。 GMDは、勾配降下、ミラー降下、およびAdagradのような条件付き勾配降下方法を含む一般的な一階最適化手法を仮定する。 標準PL解析はGMDから確率的GMDへ自然に拡張できないので、テイラー級数に基づく解析を行い、確率的GMDの線形収束に十分な条件を確立する。 その結果,十分条件が確立され,確率的ミラー降下とアダグラードの線形収束の学習率が得られた。 最後に、局所 PL* である関数に対して、我々の解析は補間解の存在と、この解への GMD の収束を示唆する。

関連論文リスト

• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。 最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
  論文  参考訳（メタデータ） (2023-10-20T12:45:12Z)
• Distributionally Time-Varying Online Stochastic Optimization under Polyak-{\L}ojasiewicz Condition with Application in Conditional Value-at-Risk Statistical Learning [9.749745086213215]
  オンライン最適化のレンズによる時間変化分布に続き、一連の最適化問題を考察する。 本研究では,CVaR学習問題に適用可能であることを示す。
  論文  参考訳（メタデータ） (2023-09-18T00:47:08Z)
• Curvature-Independent Last-Iterate Convergence for Games on Riemannian Manifolds [77.4346324549323]
  本研究では, 多様体の曲率に依存しないステップサイズが, 曲率非依存かつ直線的最終点収束率を達成することを示す。 我々の知る限りでは、曲率非依存率や/または最終点収束の可能性はこれまでに検討されていない。
  論文  参考訳（メタデータ） (2023-06-29T01:20:44Z)
• Mirror Descent with Relative Smoothness in Measure Spaces, with application to Sinkhorn and EM [11.007661197604065]
  本稿では,無限次元環境下でのミラー降下アルゴリズムの収束性について検討する。 結果が結合分布とクルバック-リーブラー分岐に適用され、シンクホーンの最適輸送に対する原始的な反復がミラー降下に対応することを示す。
  論文  参考訳（メタデータ） (2022-06-17T16:19:47Z)
• Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems [98.34292831923335]
  オンライン相関解析の問題から,emphStochastic Scaled-Gradient Descent (SSD)アルゴリズムを提案する。 我々はこれらのアイデアをオンライン相関解析に適用し、局所収束率を正規性に比例した最適な1時間スケールのアルゴリズムを初めて導いた。
  論文  参考訳（メタデータ） (2021-12-29T18:46:52Z)
• Leveraging Non-uniformity in First-order Non-convex Optimization [93.6817946818977]
  目的関数の非一様洗練は、emphNon-uniform Smoothness(NS)とemphNon-uniform Lojasiewicz inequality(NL)につながる 新しい定義は、古典的な$Omega (1/t2)$下界よりも早く大域的最適性に収束する新しい幾何学的一階法を刺激する。
  論文  参考訳（メタデータ） (2021-05-13T04:23:07Z)
• Benign Overfitting of Constant-Stepsize SGD for Linear Regression [122.70478935214128]
  帰納バイアスは 経験的に過剰フィットを防げる中心的存在です この研究は、この問題を最も基本的な設定として考慮している: 線形回帰に対する定数ステップサイズ SGD。 我々は、(正規化されていない)SGDで得られるアルゴリズム正則化と、通常の最小二乗よりも多くの顕著な違いを反映する。
  論文  参考訳（メタデータ） (2021-03-23T17:15:53Z)
• Exact Linear Convergence Rate Analysis for Low-Rank Symmetric Matrix Completion via Gradient Descent [22.851500417035947]
  因数分解に基づく勾配降下は、因数分解行列の完備化を解くためのスケーラブルで効率的なアルゴリズムである。 勾配勾配降下は, 地球自然問題の解を推定するために, 高速収束を楽しむことを示す。
  論文  参考訳（メタデータ） (2021-02-04T03:41:54Z)
• Optimal Sample Complexity of Subgradient Descent for Amplitude Flow via Non-Lipschitz Matrix Concentration [12.989855325491163]
  我々は、実数値の$n$次元信号を、位相のない線形測定値から復元する問題を考察する。 ランダムな不連続行列値演算子の均一な濃度に基づいて, 最適なサンプル複雑性を持つ下降勾配の局所収束を確立する。
  論文  参考訳（メタデータ） (2020-10-31T15:03:30Z)
• Asymptotic Errors for Teacher-Student Convex Generalized Linear Models (or : How to Prove Kabashima's Replica Formula) [23.15629681360836]
  凸一般化線形モデルの再構成性能に関する解析式を検証した。 解析的継続を行えば、結果を凸(非強直)問題に拡張できることを示す。 主流学習法に関する数値的な例で,本主張を述べる。
  論文  参考訳（メタデータ） (2020-06-11T16:26:35Z)
• On the Convergence Rate of Projected Gradient Descent for a Back-Projection based Objective [58.33065918353532]
  我々は、最小二乗(LS)の代替として、バックプロジェクションに基づく忠実度項を考える。 LS項ではなくBP項を用いることで最適化アルゴリズムの繰り返しを少なくすることを示す。
  論文  参考訳（メタデータ） (2020-05-03T00:58:23Z)

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

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