論文の概要: Convergence and Complexity of Stochastic Subgradient Methods with
Dependent Data for Nonconvex Optimization
- arxiv url: http://arxiv.org/abs/2203.15797v1
- Date: Tue, 29 Mar 2022 17:59:10 GMT
- ステータス: 処理完了
- システム内更新日: 2022-03-30 13:32:43.129392
- Title: Convergence and Complexity of Stochastic Subgradient Methods with
Dependent Data for Nonconvex Optimization
- Title（参考訳）: 非凸最適化のための依存データを用いた確率的下次手法の収束と複雑度
- Authors: Ahmet Alacaoglu, Hanbaek Lyu
- Abstract要約: 一般データサンプリング方式では,弱凸関数に対する古典的および近位下降法が最悪のケース収束率を有することを示す。
最適収束保証率と適応的なステップサイズを持つ投影勾配法に基づく従属データに対する最初のオンライン非行列分解アルゴリズムを得る。
- 参考スコア（独自算出の注目度）: 7.513100214864646
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We show that under a general dependent data sampling scheme, the classical
stochastic projected and proximal subgradient methods for weakly convex
functions have worst-case rate of convergence $\tilde{O}(n^{-1/4})$ and
complexity $\tilde{O}(\varepsilon^{-4})$ for achieving an $\varepsilon$-near
stationary point in terms of the norm of the gradient of Moreau envelope. While
classical convergence guarantee requires i.i.d. data sampling from the target
distribution, we only require a mild mixing condition of the conditional
distribution, which holds for a wide class of Markov chain sampling algorithms.
This improves the existing complexity for the specific case of constrained
smooth nonconvex optimization with dependent data from
$\tilde{O}(\varepsilon^{-8})$ to $\tilde{O}(\varepsilon^{-4})$ with a
significantly simpler analysis. We illustrate the generality of our approach by
deriving convergence results with dependent data for adaptive stochastic
subgradient algorithm AdaGrad and stochastic subgradient algorithm with heavy
ball momentum. As an application, we obtain first online nonnegative matrix
factorization algorithms for dependent data based on stochastic projected
gradient methods with adaptive step sizes with optimal rate of convergence
guarantee.
- Abstract（参考訳）: 一般的な従属データサンプリングスキームの下では、弱凸関数に対する古典確率的および近位劣次法は、モローエンベロープの勾配のノルムで$\varepsilon$-near定常点を達成するために$\tilde{O}(n^{-1/4})$と複雑さ$\tilde{O}(\varepsilon^{-4})$の最悪の収束率を持つことを示す。
古典的な収束保証は、ターゲット分布からのデータサンプリングを必要とするが、条件分布の緩やかな混合条件しか必要とせず、これは幅広い種類のマルコフ連鎖サンプリングアルゴリズムに当てはまる。
これにより、制約付き滑らかな非凸最適化の特定の場合の既存の複雑さが改善され、より単純な解析で$\tilde{o}(\varepsilon^{-8})$から$\tilde{o}(\varepsilon^{-4})$への依存データが得られる。
適応確率下進アルゴリズム AdaGrad と,重球運動量を持つ確率下進アルゴリズム AdaGrad に対する依存データを用いた収束結果の導出によるアプローチの一般化について述べる。
応用として、最適収束保証率を持つ適応ステップサイズを持つ確率的射影勾配法に基づく従属データに対する最初のオンライン非負行列分解アルゴリズムを得る。
関連論文リスト
- Gradient Methods with Online Scaling [19.218484733179356]
オンライン学習による勾配に基づく手法の収束を加速する枠組みを提案する。
広範に使用される過勾配降下は勾配降下の収束により改善されることを示す。
論文 参考訳（メタデータ） (2024-11-04T05:04:18Z) - An Adaptive Stochastic Gradient Method with Non-negative Gauss-Newton Stepsizes [17.804065824245402]
機械学習の応用では、各損失関数は非負であり、平方根とその実数値平方根の構成として表すことができる。
本稿では, ガウス・ニュートン法やレフスカルト法を適用して, 滑らかだが非負な関数の平均を最小化する方法を示す。
論文 参考訳（メタデータ） (2024-07-05T08:53:06Z) - On the Stochastic (Variance-Reduced) Proximal Gradient Method for Regularized Expected Reward Optimization [10.36447258513813]
我々は、強化学習(RL)における既存の問題の多くを網羅する非文献設定における正規化期待報酬最適化問題を考える。
特に、標準条件下では、$O(epsilon-4)$サンプルを$epsilon$-stationaryポイントに含めることが示されている。
分析の結果,サンプルの複雑さは,追加条件下では$O(epsilon-4)$から$O(epsilon-3)$に改善できることがわかった。
論文 参考訳（メタデータ） (2024-01-23T06:01:29Z) - Convex and Non-convex Optimization Under Generalized Smoothness [69.69521650503431]
凸法と非最適化法の分析は、しばしばリプシッツ勾配を必要とし、この軌道による解析を制限する。
最近の研究は、非一様滑らか性条件を通した勾配設定を一般化している。
論文 参考訳（メタデータ） (2023-06-02T04:21:59Z) - Min-Max Optimization Made Simple: Approximating the Proximal Point
Method via Contraction Maps [77.8999425439444]
本稿では,凸/凹凸 min-max 問題に対して,ほぼ最適収束率を許容する一階法を提案する。
我々の研究は、近点法の更新規則を精度良く近似できるという事実に基づいている。
論文 参考訳（メタデータ） (2023-01-10T12:18:47Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳（メタデータ） (2022-06-17T06:10:20Z) - Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box
Optimization Framework [100.36569795440889]
この作業は、一階情報を必要としない零次最適化(ZO)の反復である。
座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
論文 参考訳（メタデータ） (2020-12-21T17:29:58Z) - Improved Complexities for Stochastic Conditional Gradient Methods under
Interpolation-like Conditions [12.096252285460814]
条件付き勾配法では, 勾配オラクルへの$mathcalO(epsilon-1.5)$呼び出しが必要であり, 最適解を求める。
勾配のスライディングステップを含めると、呼び出しの数は$mathcalO(epsilon-1.5)$に減少する。
論文 参考訳（メタデータ） (2020-06-15T06:51:39Z) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳（メタデータ） (2019-12-26T22:10:10Z) - On the Convergence of Adaptive Gradient Methods for Nonconvex Optimization [80.03647903934723]
我々は、勾配収束法を期待する適応勾配法を証明した。
解析では、非理解勾配境界の最適化において、より適応的な勾配法に光を当てた。
論文 参考訳（メタデータ） (2018-08-16T20:25:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。