論文の概要: Convergence of a Normal Map-based Prox-SGD Method under the KL
Inequality
- arxiv url: http://arxiv.org/abs/2305.05828v1
- Date: Wed, 10 May 2023 01:12:11 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-11 14:58:03.803075
- Title: Convergence of a Normal Map-based Prox-SGD Method under the KL
Inequality
- Title（参考訳）: KL不等式下における正規写像に基づく Prox-SGD 法の収束性
- Authors: Andre Milzarek and Junwen Qiu
- Abstract要約: 我々は、$symbol$k$収束問題に対して、新しいマップベースのアルゴリズム(mathsfnorMtext-mathsfSGD$)を提案する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we present a novel stochastic normal map-based algorithm
($\mathsf{norM}\text{-}\mathsf{SGD}$) for nonconvex composite-type optimization
problems and discuss its convergence properties. Using a time window-based
strategy, we first analyze the global convergence behavior of
$\mathsf{norM}\text{-}\mathsf{SGD}$ and it is shown that every accumulation
point of the generated sequence of iterates $\{\boldsymbol{x}^k\}_k$
corresponds to a stationary point almost surely and in an expectation sense.
The obtained results hold under standard assumptions and extend the more
limited convergence guarantees of the basic proximal stochastic gradient
method. In addition, based on the well-known Kurdyka-{\L}ojasiewicz (KL)
analysis framework, we provide novel point-wise convergence results for the
iterates $\{\boldsymbol{x}^k\}_k$ and derive convergence rates that depend on
the underlying KL exponent $\boldsymbol{\theta}$ and the step size dynamics
$\{\alpha_k\}_k$. Specifically, for the popular step size scheme
$\alpha_k=\mathcal{O}(1/k^\gamma)$, $\gamma \in (\frac23,1]$, (almost sure)
rates of the form $\|\boldsymbol{x}^k-\boldsymbol{x}^*\| = \mathcal{O}(1/k^p)$,
$p \in (0,\frac12)$, can be established. The obtained rates are faster than
related and existing convergence rates for $\mathsf{SGD}$ and improve on the
non-asymptotic complexity bounds for $\mathsf{norM}\text{-}\mathsf{SGD}$.
- Abstract（参考訳）: 本稿では,非凸複合型最適化問題に対する確率正規写像に基づく新しいアルゴリズム(\mathsf{norM}\text{-}\mathsf{SGD}$)を提案し,その収束性について議論する。
時間窓に基づく戦略を用いて、まず$\mathsf{norm}\text{-}\mathsf{sgd}$のグローバル収束挙動を解析し、生成されたイテレート列の蓄積点が$\{\boldsymbol{x}^k\}_k$ はほぼ確実に期待された意味で定常点に対応することを示す。
得られた結果は標準仮定のもとで保たれ、基本近位確率勾配法のより限定的な収束保証を拡張する。
さらに、よく知られたKurtyka-{\L}ojasiewicz (KL) 分析フレームワークに基づいて、イテレート $\{\boldsymbol{x}^k\}_k$ に対する新しい点収束結果と、基礎となる KL 指数 $\boldsymbol{\theta}$ とステップサイズ力学 $\{\alpha_k\}_k$ に依存する導出収束率を提供する。
具体的には、一般的なステップサイズスキーム $\alpha_k=\mathcal{O}(1/k^\gamma)$, $\gamma \in (\frac23,1]$, (ほぼ確実に) $\|\boldsymbol{x}^k-\boldsymbol{x}^*\| = \mathcal{O}(1/k^p)$, $p \in (0,\frac12)$ が成立する。
得られたレートは、$\mathsf{SGD}$の関連および既存の収束速度よりも速く、$\mathsf{norM}\text{-}\mathsf{SGD}$の非漸近複雑性境界を改善する。
関連論文リスト
- Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳（メタデータ） (2024-02-06T15:39:09Z) - On the $O(\frac{\sqrt{d}}{T^{1/4}})$ Convergence Rate of RMSProp and Its Momentum Extension Measured by $\ell_1$ Norm [59.65871549878937]
本稿では、RMSPropとその運動量拡張を考察し、$frac1Tsum_k=1Tの収束速度を確立する。
我々の収束率は、次元$d$を除くすべての係数に関して下界と一致する。
収束率は$frac1Tsum_k=1Tと類似していると考えられる。
論文 参考訳（メタデータ） (2024-02-01T07:21:32Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - Convergence of Alternating Gradient Descent for Matrix Factorization [5.439020425819001]
非対称行列分解対象に一定のステップサイズを施した交互勾配降下(AGD)について検討した。
階数-r$行列 $mathbfA in mathbbRm times n$, smoothness $C$ in the complexity $T$ to be a absolute constant。
論文 参考訳（メタデータ） (2023-05-11T16:07:47Z) - High Probability Convergence of Stochastic Gradient Methods [15.829413808059124]
最適解への初期距離に依存する有界収束を示す。
AdaGrad-Normのハイバウンドが得られることを示す。
論文 参考訳（メタデータ） (2023-02-28T18:42:11Z) - Randomized Block-Coordinate Optimistic Gradient Algorithms for
Root-Finding Problems [8.0153031008486]
大規模設定における非線形方程式の解を近似する2つの新しいアルゴリズムを開発した。
我々は,機械学習における顕著な応用を網羅する大規模有限サム包含のクラスに,本手法を適用した。
論文 参考訳（メタデータ） (2023-01-08T21:46:27Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。
実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文 参考訳（メタデータ） (2021-10-21T18:43:00Z) - From Smooth Wasserstein Distance to Dual Sobolev Norm: Empirical
Approximation and Statistical Applications [18.618590805279187]
我々は$mathsfW_p(sigma)$が$pth次スムーズな双対ソボレフ$mathsfd_p(sigma)$で制御されていることを示す。
我々は、すべての次元において$sqrtnmathsfd_p(sigma)(hatmu_n,mu)$の極限分布を導出する。
論文 参考訳（メタデータ） (2021-01-11T17:23:24Z) - Accelerating Optimization and Reinforcement Learning with
Quasi-Stochastic Approximation [2.294014185517203]
本稿では、収束理論を準確率近似に拡張することを目的とする。
強化学習のためのグラデーションフリー最適化とポリシー勾配アルゴリズムへの応用について説明する。
論文 参考訳（メタデータ） (2020-09-30T04:44:45Z) - Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
論文 参考訳（メタデータ） (2020-05-29T07:20:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。