論文の概要: Replica Exchange for Non-Convex Optimization
- arxiv url: http://arxiv.org/abs/2001.08356v4
- Date: Wed, 16 Jun 2021 06:23:31 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-07 13:21:51.040096
- Title: Replica Exchange for Non-Convex Optimization
- Title（参考訳）: 非凸最適化のためのレプリカ交換
- Authors: Jing Dong and Xin T. Tong
- Abstract要約: 勾配降下(GD)は凸目的関数に対して急速に収束することが知られているが、局所的なミニマに閉じ込められることがある。
ランゲヴィン力学(LD)は状態空間を探索し、大域的な最小値を見つけることができるが、正確な推定を得るためには、LDは小さな離散化ステップサイズで実行し、弱い力を検証する必要がある。
本稿では,これら2つのアルゴリズムとその非スワッピング変種が,単純な交換機構によって協調可能であることを示す。
- 参考スコア（独自算出の注目度）: 4.421561004829125
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Gradient descent (GD) is known to converge quickly for convex objective
functions, but it can be trapped at local minima. On the other hand, Langevin
dynamics (LD) can explore the state space and find global minima, but in order
to give accurate estimates, LD needs to run with a small discretization step
size and weak stochastic force, which in general slow down its convergence.
This paper shows that these two algorithms and their non-swapping variants. can
``collaborate" through a simple exchange mechanism, in which they swap their
current positions if LD yields a lower objective function. This idea can be
seen as the singular limit of the replica-exchange technique from the sampling
literature. We show that this new algorithm converges to the global minimum
linearly with high probability, assuming the objective function is strongly
convex in a neighborhood of the unique global minimum. By replacing gradients
with stochastic gradients, and adding a proper threshold to the exchange
mechanism, our algorithm can also be used in online settings. We also study
non-swapping variants of the algorithm, which achieve similar performance. We
further verify our theoretical results through some numerical experiments and
observe superior performance of the proposed algorithm over running GD or LD
alone.
- Abstract（参考訳）: 勾配降下 (gd) は凸対象関数に対して素早く収束することが知られているが、局所極小に閉じ込めることができる。
一方、ランゲヴィン力学(LD)は状態空間を探索し、大域的最小値を求めることができるが、正確な推定を得るためには、LDは小さな離散化ステップサイズと弱い確率力で実行する必要がある。
本稿では,これら2つのアルゴリズムと非スワッピング型について述べる。
は、LDが低い目的関数を出力した場合、現在の位置を交換する単純な交換メカニズムを通じて"協調"することができる。
この考え方はサンプリング文献からの複製交換技法の特異な極限と見なすことができる。
対象関数が一意な大域的最小値の近傍で強凸であることを仮定して,この新しいアルゴリズムは大域的最小値に高確率で収束することを示す。
勾配を確率勾配に置き換え、交換機構に適切なしきい値を加えることで、我々のアルゴリズムはオンライン設定でも使用できる。
また、同様の性能を実現するアルゴリズムの非スワッピング変種についても検討する。
さらに,いくつかの数値実験により理論結果を検証し,GDやLDを単独で動作させるよりも提案アルゴリズムの優れた性能を観察する。
関連論文リスト
- Langevin Dynamics: A Unified Perspective on Optimization via Lyapunov Potentials [15.718093624695552]
我々は、リアプノフポテンシャルと最適化に基づいて、グラディエント・ランゲヴィン・ダイナミクス(SGLD)のグローバル・ミニマへの収束を分析する。
2) SGLD に対する最初の有限勾配複雑性、3) 連続時間ランゲヴィンダイナミクスが最適化に成功するなら、次に離散時間 SGLD が穏やかな正則性仮定の下で成功することを証明する。
論文 参考訳（メタデータ） (2024-07-05T05:34:10Z) - On the Convergence of Multi-objective Optimization under Generalized Smoothness [27.87166415148172]
我々はより一般的で現実的な$ell$-smooth損失関数のクラスを研究し、$ell$は一般の非減少関数ノルムである。
我々は、$ell$-smooth Generalized Multi-MOO GradientGradと、その変種である Generalized Smooth Multi-MOO descentの2つの新しいアルゴリズムを開発した。
私たちのアルゴリズムは、より厳密な$mathcalO(epsilon-2)$を各イテレーションで、より多くのサンプルを使って保証します。
論文 参考訳（メタデータ） (2024-05-29T18:36:59Z) - Decentralized Riemannian Algorithm for Nonconvex Minimax Problems [82.50374560598493]
ニューラルネットワークのためのミニマックスアルゴリズムは、多くの問題を解決するために開発された。
本稿では,2種類のミニマックスアルゴリズムを提案する。
そこで我々は, DRSGDAを提案し, 本手法が勾配を達成することを証明した。
論文 参考訳（メタデータ） (2023-02-08T01:42:45Z) - Adaptive Federated Minimax Optimization with Lower Complexities [82.51223883622552]
本稿では,これらのミニマックス問題の解法として,適応最小最適化アルゴリズム(AdaFGDA)を提案する。
運動量に基づく還元および局所SGD技術を構築し、様々な適応学習率を柔軟に組み込む。
論文 参考訳（メタデータ） (2022-11-14T12:32:18Z) - A Communication-efficient Algorithm with Linear Convergence for
Federated Minimax Learning [1.713291434132985]
GAN(Geneimation Adversarial Networks)をモデル化した大規模マルチエージェントミニマックス最適化問題について検討する。
全体的な目的は、エージェントのプライベートなローカルな目的関数の総和である。
我々は,FedGDA-GTが,大域的な$epsilon GDA解に一定のステップサイズで線形収束することを示した。
論文 参考訳（メタデータ） (2022-06-02T16:31:16Z) - Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and
Beyond [63.59034509960994]
シャッフルに基づく変種(ミニバッチと局所ランダムリシャッフル)について検討する。
ポリアック・ロジャシエヴィチ条件を満たす滑らかな函数に対して、これらのシャッフル型不変量(英語版)(shuffling-based variants)がそれらの置換式よりも早く収束することを示す収束境界を得る。
我々は, 同期シャッフル法と呼ばれるアルゴリズムの修正を提案し, ほぼ均一な条件下では, 下界よりも収束速度が速くなった。
論文 参考訳（メタデータ） (2021-10-20T02:25:25Z) - The Minimax Complexity of Distributed Optimization [0.0]
分散最適化に適用可能な古典的なオラクルフレームワークの拡張である「グラフオラクルモデル」を紹介します。
私は「間欠的コミュニケーション設定」の具体例に焦点をあてる
コンベックス設定におけるSGD(Local Descent)アルゴリズムの理論的特性を解析する。
論文 参考訳（メタデータ） (2021-09-01T15:18:33Z) - Faster Convergence of Stochastic Gradient Langevin Dynamics for
Non-Log-Concave Sampling [110.88857917726276]
我々は,非log-concaveとなる分布のクラスからサンプリングするために,勾配ランゲヴィンダイナミクス(SGLD)の新たな収束解析を行う。
我々のアプローチの核心は、補助的時間反転型マルコフ連鎖を用いたSGLDのコンダクタンス解析である。
論文 参考訳（メタデータ） (2020-10-19T15:23:18Z) - Aligning Partially Overlapping Point Sets: an Inner Approximation
Algorithm [80.15123031136564]
変換の値に関する事前情報がない点集合を整列するロバストな手法を提案する。
我々のアルゴリズムは変換の正規化を必要とせず、変換の値に関する事前情報がない状況に対処できる。
実験により,提案手法が最先端のアルゴリズムよりも高いロバスト性を示した。
論文 参考訳（メタデータ） (2020-07-05T15:23:33Z) - Unified Analysis of Stochastic Gradient Methods for Composite Convex and
Smooth Optimization [15.82816385434718]
本稿では、滑らかで凸な損失と凸正則化器を最小化するための勾配アルゴリズムの収束解析のための統一定理を提案する。
我々は、Gorbunov, Hanzely & Richt'arik (2020) の統一解析を拡張し、損失関数が強く凸であるという要求を下げる。
我々の統一解析は、近位SGD、分散還元法、量子化、およびいくつかの座標降下型法などの既存のアルゴリズムのホストに適用できる。
論文 参考訳（メタデータ） (2020-06-20T13:40:27Z) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳（メタデータ） (2019-12-26T22:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。