論文の概要: Convergence of First-Order Methods for Constrained Nonconvex
Optimization with Dependent Data
- arxiv url: http://arxiv.org/abs/2203.15797v2
- Date: Fri, 23 Jun 2023 04:11:18 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-26 17:54:03.212814
- Title: Convergence of First-Order Methods for Constrained Nonconvex
Optimization with Dependent Data
- Title（参考訳）: 依存データを用いた制約付き非凸最適化のための一階法収束
- Authors: Ahmet Alacaoglu, Hanbaek Lyu
- Abstract要約: 収束$tildeO(t-1/4)$とMoreautildeO(vareps-4)$がスムーズな非最適化のために最悪の場合の複雑性を示す。
適応的なステップサイズと最適収束度を持つ投影勾配法に基づく従属データに対する最初のオンライン非負行列分解アルゴリズムを得る。
- 参考スコア（独自算出の注目度）: 7.513100214864646
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We focus on analyzing the classical stochastic projected gradient methods
under a general dependent data sampling scheme for constrained smooth nonconvex
optimization. We show the worst-case rate of convergence $\tilde{O}(t^{-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 and gradient mapping. 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 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 stochastic proximal
gradient methods, adaptive stochastic gradient algorithm AdaGrad and stochastic
gradient 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 and optimal rate
of convergence.
- Abstract（参考訳）: 制約付き滑らかな非凸最適化のための一般依存データサンプリングスキームの下での古典的確率的投影勾配法の解析に着目する。
我々は、モローエンベロープの勾配と勾配写像のノルムで$\varepsilon$-near定常点を達成するために、収束$\tilde{O}(t^{-1/4})$と複雑性$\tilde{O}(\varepsilon^{-4})$の最悪のケース率を示す。
古典的な収束保証は、ターゲット分布からのデータサンプリングを必要とするが、条件分布の緩やかな混合条件しか必要とせず、これは幅広い種類のマルコフ連鎖サンプリングアルゴリズムに当てはまる。
これにより、制約のある滑らかな非凸最適化の既存の複雑さが改善され、より単純な解析で$\tilde{o}(\varepsilon^{-8})$から$\tilde{o}(\varepsilon^{-4})$への依存データが得られる。
本稿では,確率的近位勾配法,適応確率的勾配アルゴリズム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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。