論文の概要: An Optimal Multistage Stochastic Gradient Method for Minimax Problems
- arxiv url: http://arxiv.org/abs/2002.05683v1
- Date: Thu, 13 Feb 2020 18:01:18 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-01 13:04:39.038095
- Title: An Optimal Multistage Stochastic Gradient Method for Minimax Problems
- Title（参考訳）: 最小値問題に対する最適多段確率勾配法
- Authors: Alireza Fallah, Asuman Ozdaglar, Sarath Pattathil
- Abstract要約: 滑らかかつ強凸な凹凸配置におけるミニマックス最適化問題について検討する。
まず, 定常ステップサイズでグラディエントDescent Ascent (GDA) 法を解析した。
本稿では,学習速度の減衰スケジュールを多段階に設定した多段階型GDAを提案する。
- 参考スコア（独自算出の注目度）: 8.615625517708324
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we study the minimax optimization problem in the smooth and
strongly convex-strongly concave setting when we have access to noisy estimates
of gradients. In particular, we first analyze the stochastic Gradient Descent
Ascent (GDA) method with constant stepsize, and show that it converges to a
neighborhood of the solution of the minimax problem. We further provide tight
bounds on the convergence rate and the size of this neighborhood. Next, we
propose a multistage variant of stochastic GDA (M-GDA) that runs in multiple
stages with a particular learning rate decay schedule and converges to the
exact solution of the minimax problem. We show M-GDA achieves the lower bounds
in terms of noise dependence without any assumptions on the knowledge of noise
characteristics. We also show that M-GDA obtains a linear decay rate with
respect to the error's dependence on the initial error, although the dependence
on condition number is suboptimal. In order to improve this dependence, we
apply the multistage machinery to the stochastic Optimistic Gradient Descent
Ascent (OGDA) algorithm and propose the M-OGDA algorithm which also achieves
the optimal linear decay rate with respect to the initial error. To the best of
our knowledge, this method is the first to simultaneously achieve the best
dependence on noise characteristic as well as the initial error and condition
number.
- Abstract（参考訳）: 本稿では, 勾配のノイズ推定を行う場合, 滑らかかつ強凸強凹設定におけるミニマックス最適化問題について検討する。
特に,確率的勾配沈み込み法(GDA)を定常的なステップサイズで解析し,ミニマックス問題の解の近傍に収束することを示す。
我々はさらに、この地区の収束率と規模に厳密な境界を与えている。
次に,確率的GDA(M-GDA)の多段階的変種について提案する。
我々は,M-GDAが雑音特性の知識を前提とせずに,雑音依存性の観点から下限を達成することを示す。
また, m-gda は初期誤差に対する誤差の依存性に関して線形減衰率を得るが, 条件数依存性は最適でないことを示した。
この依存性を改善するため,多段機械を確率的漸進勾配降下法(ogda)法に適用し,初期誤差に対して最適線形減衰率を達成するm-ogdaアルゴリズムを提案する。
我々の知る限り、この手法は、初期誤差と条件数だけでなく、ノイズ特性への最高の依存を同時に達成する最初の方法である。
関連論文リスト
- Gradient Normalization with(out) Clipping Ensures Convergence of Nonconvex SGD under Heavy-Tailed Noise with Improved Results [60.92029979853314]
本稿では,NSGDCを含まない勾配正規化(NSGDC-VR)について検討する。
両アルゴリズムの理論的結果の大幅な改善について述べる。
論文 参考訳（メタデータ） (2024-10-21T22:40:42Z) - From Gradient Clipping to Normalization for Heavy Tailed SGD [19.369399536643773]
最近の実証的な証拠は、機械学習の応用が重尾ノイズを伴い、実際に有界分散の標準的な仮定に挑戦していることを示している。
本稿では, 勾配依存型雑音収束問題において, テール雑音下での厳密性を実現することができることを示す。
論文 参考訳（メタデータ） (2024-10-17T17:59:01Z) - Accelerated stochastic approximation with state-dependent noise [7.4648480208501455]
勾配観測における2次雑音に対する一般仮定の下での滑らかな凸最適化問題を考察する。
このような問題は、統計学におけるよく知られた一般化された線形回帰問題において、様々な応用において自然に発生する。
SAGDとSGEは、適切な条件下で、最適収束率を達成することを示す。
論文 参考訳（メタデータ） (2023-07-04T06:06:10Z) - First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities [91.46841922915418]
本稿では,一階変分法の理論解析のための統一的アプローチを提案する。
提案手法は非線形勾配問題とモンテカルロの強い問題の両方をカバーする。
凸法最適化問題の場合、オラクルに強く一致するような境界を与える。
論文 参考訳（メタデータ） (2023-05-25T11:11:31Z) - Utilising the CLT Structure in Stochastic Gradient based Sampling :
Improved Analysis and Faster Algorithms [14.174806471635403]
粒子ダイナミック(IPD)に対するグラディエント・ランゲヴィン・ダイナミクス(SGLD)やランダムバッチ法(RBM)などのサンプリングアルゴリズムの近似を考察する。
近似によって生じる雑音は中央極限定理(CLT)によりほぼガウス的であるが、ブラウン運動はまさにガウス的である。
この構造を利用して拡散過程内の近似誤差を吸収し、これらのアルゴリズムの収束保証を改善する。
論文 参考訳（メタデータ） (2022-06-08T10:17:40Z) - Differentiable Annealed Importance Sampling and the Perils of Gradient
Noise [68.44523807580438]
Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。
差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。
我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
論文 参考訳（メタデータ） (2021-07-21T17:10:14Z) - ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。
我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。
有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
論文 参考訳（メタデータ） (2020-08-28T14:46:56Z) - Least Squares Regression with Markovian Data: Fundamental Limits and
Algorithms [69.45237691598774]
マルコフ連鎖からデータポイントが依存しサンプリングされる最小二乗線形回帰問題について検討する。
この問題を$tau_mathsfmix$という観点から、鋭い情報理論のミニマックス下限を確立する。
本稿では,経験的リプレイに基づくアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-16T04:26:50Z) - Exploiting Higher Order Smoothness in Derivative-free Optimization and
Continuous Bandits [99.70167985955352]
強凸関数のゼロ次最適化問題について検討する。
予測勾配降下アルゴリズムのランダム化近似を考察する。
その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
論文 参考訳（メタデータ） (2020-06-14T10:42:23Z) - Stochastic gradient algorithms from ODE splitting perspective [0.0]
我々は、ODEの近似解の分割スキームに遡る最適化に関する異なる見解を示す。
そこで本研究では, ODE の勾配一階分割方式と降下アプローチの関連性について述べる。
我々は、機械学習アプリケーションにインスパイアされた分割の特殊なケースを考察し、それに対するグローバルスプリッティングエラーに新たな上限を導出する。
論文 参考訳（メタデータ） (2020-04-19T22:45:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。