論文の概要: Adaptive and Optimal Second-order Optimistic Methods for Minimax Optimization

• arxiv url: http://arxiv.org/abs/2406.02016v1
• Date: Tue, 4 Jun 2024 06:56:41 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-05 17:40:41.957116
• Title: Adaptive and Optimal Second-order Optimistic Methods for Minimax Optimization
• Title（参考訳）: 最小値最適化のための適応的および最適二階最適化法
• Authors: Ruichen Jiang, Ali Kavis, Qiujiang Jin, Sujay Sanghavi, Aryan Mokhtari,
• Abstract要約: 私たちのアルゴリズムは、イテレーション毎に1つの線形システムだけを解決する必要のある、単純な更新ルールを備えています。 また,提案アルゴリズムの実用性能を,既存の2次アルゴリズムと比較して評価した。
• 参考スコア（独自算出の注目度）: 32.939120407900035
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose adaptive, line search-free second-order methods with optimal rate of convergence for solving convex-concave min-max problems. By means of an adaptive step size, our algorithms feature a simple update rule that requires solving only one linear system per iteration, eliminating the need for line search or backtracking mechanisms. Specifically, we base our algorithms on the optimistic method and appropriately combine it with second-order information. Moreover, distinct from common adaptive schemes, we define the step size recursively as a function of the gradient norm and the prediction error in the optimistic update. We first analyze a variant where the step size requires knowledge of the Lipschitz constant of the Hessian. Under the additional assumption of Lipschitz continuous gradients, we further design a parameter-free version by tracking the Hessian Lipschitz constant locally and ensuring the iterates remain bounded. We also evaluate the practical performance of our algorithm by comparing it to existing second-order algorithms for minimax optimization.
• Abstract（参考訳）: コンベックス・コンケーブ min-max 問題の解法として最適収束率を持つ適応線形探索自由二階法を提案する。 適応的なステップサイズにより、我々のアルゴリズムは、1イテレーションごとに1つの線形システムだけを解決し、行探索やバックトラッキング機構の不要な単純な更新ルールを特徴としている。 具体的には,アルゴリズムを楽観的手法に基づいて2次情報と適切に組み合わせる。 さらに、一般的な適応スキームと異なり、楽観的な更新において、ステップサイズを勾配ノルムと予測誤差の関数として再帰的に定義する。 まず、ステップサイズがヘッセンのリプシッツ定数の知識を必要とする変種を解析する。 リプシッツ連続勾配のさらなる仮定の下で、ヘッセン・リプシッツ定数を局所的に追跡し、イテレートが有界であることを保証することにより、パラメータフリー版をさらに設計する。 また,提案アルゴリズムの実用性能を,既存の2次アルゴリズムと比較して評価した。

関連論文リスト

• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。 本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
  論文  参考訳（メタデータ） (2024-06-28T02:56:22Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Beyond the Golden Ratio for Variational Inequality Algorithms [12.470097382737933]
  我々は,モノトーン変分不等式 (VI) と凸凹 min-max 問題の解法である $textitgolden ratio algorithm$ の理解を改善した。 我々は,黄金比アルゴリズムと文献における既存のアルゴリズムとの橋渡しを完了するために,より大きなステップサイズを使用することのできる新しい分析手法を提案する。
  論文  参考訳（メタデータ） (2022-12-28T16:58:48Z)
• Adaptive extra-gradient methods for min-max optimization and games [35.02879452114223]
  本稿では,初期の反復で観測された勾配データの幾何を自動的に活用する,minmax最適化アルゴリズムの新たなファミリーを提案する。 この適応機構により,提案手法は問題がスムーズかどうかを自動的に検出する。 滑らかな問題における$mathcalO (1/varepsilon)$反復と、非滑らかな問題における$mathcalO (1/varepsilon)$反復に収束する。
  論文  参考訳（メタデータ） (2020-10-22T22:54:54Z)
• Sequential Quadratic Optimization for Nonlinear Equality Constrained Stochastic Optimization [10.017195276758454]
  この設定では、客観的関数と微分値を明示的に計算することは難しそうだと仮定する。 最先端のライン探索SQPアルゴリズムをモデルとした決定論的設定のためのアルゴリズムを提案する。 数値実験の結果は,提案手法の実用性を示すものである。
  論文  参考訳（メタデータ） (2020-07-20T23:04:26Z)
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits [99.70167985955352]
  強凸関数のゼロ次最適化問題について検討する。 予測勾配降下アルゴリズムのランダム化近似を考察する。 その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-14T10:42:23Z)
• 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)
• Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization [56.05635751529922]
  スケッチに基づくL2正規化最小二乗問題の解法を提案する。 我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
  論文  参考訳（メタデータ） (2020-06-10T15:00:09Z)
• Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
  本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。 Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。 本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
  論文  参考訳（メタデータ） (2020-05-10T19:52:03Z)

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

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