論文の概要: Variance reduction techniques for stochastic proximal point algorithms
- arxiv url: http://arxiv.org/abs/2308.09310v3
- Date: Tue, 6 Aug 2024 10:38:22 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-07 19:51:34.494472
- Title: Variance reduction techniques for stochastic proximal point algorithms
- Title（参考訳）: 確率的近位点アルゴリズムのばらつき低減手法
- Authors: Cheik Traoré, Vassilis Apidopoulos, Saverio Salzo, Silvia Villa,
- Abstract要約: そこで本研究では,近点アルゴリズムにおける分散低減手法の統一化研究を提案する。
我々は,SVRG,SAGA,およびそれらの変種の近位バージョンを提供するために特定可能な,汎用的近位アルゴリズムを提案する。
本実験は, 勾配法よりも近似分散還元法の利点を実証する。
- 参考スコア（独自算出の注目度）: 5.374800961359305
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In the context of finite sums minimization, variance reduction techniques are widely used to improve the performance of state-of-the-art stochastic gradient methods. Their practical impact is clear, as well as their theoretical properties. Stochastic proximal point algorithms have been studied as an alternative to stochastic gradient algorithms since they are more stable with respect to the choice of the step size. However, their variance-reduced versions are not as well studied as the gradient ones. In this work, we propose the first unified study of variance reduction techniques for stochastic proximal point algorithms. We introduce a generic stochastic proximal-based algorithm that can be specified to give the proximal version of SVRG, SAGA, and some of their variants. For this algorithm, in the smooth setting, we provide several convergence rates for the iterates and the objective function values, which are faster than those of the vanilla stochastic proximal point algorithm. More specifically, for convex functions, we prove a sublinear convergence rate of $O(1/k)$. In addition, under the Polyak-{\L}ojasiewicz (PL) condition, we obtain linear convergence rates. Finally, our numerical experiments demonstrate the advantages of the proximal variance reduction methods over their gradient counterparts in terms of the stability with respect to the choice of the step size in most cases, especially for difficult problems.
- Abstract（参考訳）: 有限和最小化の文脈では、分散還元法は最先端確率勾配法の性能向上に広く用いられている。
彼らの実践的な影響は明らかであり、理論上も明らかである。
確率的近点アルゴリズムは、ステップサイズの選択に関してより安定であるため、確率的勾配アルゴリズムの代替として研究されている。
しかし、それらの分散還元版は勾配版ほどよく研究されていない。
本研究では,確率的近点アルゴリズムにおける分散低減手法の統一化研究を提案する。
我々は,SVRG,SAGA,およびそれらの変種の近位バージョンを提供するために特定可能な,確率的近位アルゴリズムを提案する。
このアルゴリズムでは、スムーズな設定で、ベニラ確率的近点アルゴリズムよりも高速な反復率と目的関数値に対して、いくつかの収束率を提供する。
具体的には、凸函数に対して、サブ線型収束率を$O(1/k)$とする。
さらに、Polyak-{\L}ojasiewicz (PL)条件下では、線形収束率を得る。
最後に, 数値実験により, 特に難解な問題において, ステップサイズの選択に対する安定性の観点から, 勾配よりも近似分散低減法の利点を実証した。
関連論文リスト
- Fast Unconstrained Optimization via Hessian Averaging and Adaptive Gradient Sampling Methods [0.3222802562733786]
ヘシアン・アブラッシングに基づくサブサンプルニュートン法による有限サム予測対象関数の最小化について検討する。
これらの方法は不有効であり、ヘッセン近似の固定コストがかかる。
本稿では,新しい解析手法を提案し,その実用化に向けた課題を提案する。
論文 参考訳（メタデータ） (2024-08-14T03:27:48Z) - Stochastic Optimization for Non-convex Problem with Inexact Hessian
Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。
TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文 参考訳（メタデータ） (2023-10-18T10:29:58Z) - High-Probability Bounds for Stochastic Optimization and Variational
Inequalities: the Case of Unbounded Variance [59.211456992422136]
制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。
これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
論文 参考訳（メタデータ） (2023-02-02T10:37:23Z) - Reinforcement Learning with Unbiased Policy Evaluation and Linear
Function Approximation [11.345796608258434]
マルコフ決定プロセスを制御するためのシミュレーションベースのポリシーイテレーションの変種に対して,性能保証を提供する。
第一のアルゴリズムは最小二乗アプローチを伴い、各反復において、特徴ベクトルに関連する新しい重みの集合が少なくとも二乗によって得られる。
第2のアルゴリズムは、最小二乗解への勾配降下を数ステップ行う2段階の近似アルゴリズムを含む。
論文 参考訳（メタデータ） (2022-10-13T20:16:19Z) - Exponential Concentration in Stochastic Approximation [0.8192907805418583]
我々は,各ステップで目標に向かって反復的に進行する近似アルゴリズムの挙動を解析する。
我々はマルコフ近似アルゴリズム、具体的には射影勾配 Descent, Kiefer-Wolfowitz および Frank-Wolfe アルゴリズムに適用する。
論文 参考訳（メタデータ） (2022-08-15T14:57:26Z) - Differentiable Annealed Importance Sampling and the Perils of Gradient
Noise [68.44523807580438]
Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。
差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。
我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
論文 参考訳（メタデータ） (2021-07-21T17:10:14Z) - Multi-kernel Passive Stochastic Gradient Algorithms and Transfer
Learning [21.796874356469644]
勾配アルゴリズムはコスト関数のノイズ勾配が評価される位置を制御できない。
このアルゴリズムは高次元問題において著しく優れており、分散還元を取り入れている。
論文 参考訳（メタデータ） (2020-08-23T11:55:19Z) - Exploiting Higher Order Smoothness in Derivative-free Optimization and
Continuous Bandits [99.70167985955352]
強凸関数のゼロ次最適化問題について検討する。
予測勾配降下アルゴリズムのランダム化近似を考察する。
その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
論文 参考訳（メタデータ） (2020-06-14T10:42:23Z) - Proximal Gradient Temporal Difference Learning: Stable Reinforcement
Learning with Polynomial Sample Complexity [40.73281056650241]
本稿では,真の勾配時間差学習アルゴリズムを設計・解析する原理的な方法として,近位勾配時間差学習を導入する。
本研究では, 従来の目的関数からではなく, 主目的関数から始めることによって, 勾配性TD強化学習法を公式に導出する方法を示す。
論文 参考訳（メタデータ） (2020-06-06T21:04:21Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。
我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。
得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文 参考訳（メタデータ） (2020-02-21T17:45:32Z) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳（メタデータ） (2019-12-26T22:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。