論文の概要: Beyond the Golden Ratio for Variational Inequality Algorithms

• arxiv url: http://arxiv.org/abs/2212.13955v1
• Date: Wed, 28 Dec 2022 16:58:48 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-29 15:00:28.717618
• Title: Beyond the Golden Ratio for Variational Inequality Algorithms
• Title（参考訳）: 変分不等式アルゴリズムの黄金比を超えて
• Authors: Ahmet Alacaoglu, Axel B\"ohm, Yura Malitsky
• Abstract要約: 我々は,モノトーン変分不等式 (VI) と凸凹 min-max 問題の解法である $textitgolden ratio algorithm$ の理解を改善した。 我々は,黄金比アルゴリズムと文献における既存のアルゴリズムとの橋渡しを完了するために,より大きなステップサイズを使用することのできる新しい分析手法を提案する。
• 参考スコア（独自算出の注目度）: 12.470097382737933
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We improve the understanding of the $\textit{golden ratio algorithm}$, which solves monotone variational inequalities (VI) and convex-concave min-max problems via the distinctive feature of adapting the step sizes to the local Lipschitz constants. Adaptive step sizes not only eliminate the need to pick hyperparameters, but they also remove the necessity of global Lipschitz continuity and can increase from one iteration to the next. We first establish the equivalence of this algorithm with popular VI methods such as reflected gradient, Popov or optimistic gradient descent-ascent in the unconstrained case with constant step sizes. We then move on to the constrained setting and introduce a new analysis that allows to use larger step sizes, to complete the bridge between the golden ratio algorithm and the existing algorithms in the literature. Doing so, we actually eliminate the link between the golden ratio $\frac{1+\sqrt{5}}{2}$ and the algorithm. Moreover, we improve the adaptive version of the algorithm, first by removing the maximum step size hyperparameter (an artifact from the analysis) to improve the complexity bound, and second by adjusting it to nonmonotone problems with weak Minty solutions, with superior empirical performance.
• Abstract（参考訳）: ステップサイズを局所リプシッツ定数に適応させることにより,単調変分不等式 (VI) と凸凹 min-max 問題の解法である $\textit{golden ratio algorithm}$ の理解を改善した。 適応的なステップサイズはハイパーパラメータを選択する必要をなくすだけでなく、グローバルリプシッツ連続性の必要性を取り除き、イテレーションを1回から次のイテレーションに増やすことができる。 我々はまず, 一定のステップサイズを持つ非制約の場合において, 反射勾配, ポポフ, あるいは楽観勾配勾配上昇などのVI法を用いて, このアルゴリズムの等価性を確立する。 次に、制約された設定に移行し、より大きなステップサイズを使用できる新しい分析を導入し、黄金比アルゴリズムと文献における既存のアルゴリズムの間の橋渡しを完了します。 すると、黄金比 $\frac{1+\sqrt{5}}{2}$ とアルゴリズムの間のリンクを実際に排除します。 さらに,まず最大ステップサイズハイパーパラメータ(解析結果からのアーティファクト)を除去して複雑性境界を改善するとともに,弱いミンティ解の非単調問題に調整し,実験性能を向上することでアルゴリズムの適応性を向上させる。

関連論文リスト

• Improved Parallel Algorithm for Non-Monotone Submodular Maximization under Knapsack Constraint [0.0]
  本研究は,knapsack制約下での非モジュラーサイズに対する効率的な並列アルゴリズムを提案する。 我々のアルゴリズムは, 既存の並列処理を 8+epsilon$ から 7+epsilon$ に改良し, 適応複雑性を$O(log n)$ にする。
  論文  参考訳（メタデータ） (2024-09-06T17:17:52Z)
• Adaptive and Optimal Second-order Optimistic Methods for Minimax Optimization [32.939120407900035]
  私たちのアルゴリズムは、イテレーション毎に1つの線形システムだけを解決する必要のある、単純な更新ルールを備えています。 また,提案アルゴリズムの実用性能を,既存の2次アルゴリズムと比較して評価した。
  論文  参考訳（メタデータ） (2024-06-04T06:56:41Z)
• Accelerated SGD for Non-Strongly-Convex Least Squares [14.010916616909743]
  非強凸設定における最小二乗回帰問題の近似を考察する。 本稿では,問題のノイズに依存して最適な予測誤差率を実現するための,最初の実用的なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-03-03T14:39:33Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• Train simultaneously, generalize better: Stability of gradient-based minimax learners [12.691047660244331]
  コンベックス・コンベブと非コンベックス・ミニマックス・セッティングの両方において,訓練されたミニマックスモデルの性能において重要な役割を担っている。 学習したミニマックスモデルの一般化における最適化アルゴリズムの役割を示す数値的な結果について議論する。
  論文  参考訳（メタデータ） (2020-10-23T17:44:43Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Balancing Rates and Variance via Adaptive Batch-Size for Stochastic Optimization Problems [120.21685755278509]
  本研究は,ステップサイズの減衰が正確な収束に必要であるという事実と,一定のステップサイズがエラーまでの時間でより速く学習するという事実のバランスをとることを目的とする。 ステップサイズのミニバッチを最初から修正するのではなく,パラメータを適応的に進化させることを提案する。
  論文  参考訳（メタデータ） (2020-07-02T16:02:02Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)
• Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets [71.05306664267832]
  適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。 本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。 実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
  論文  参考訳（メタデータ） (2019-12-26T22:10:10Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。