論文の概要: Generalized Optimistic Methods for Convex-Concave Saddle Point Problems

• arxiv url: http://arxiv.org/abs/2202.09674v1
• Date: Sat, 19 Feb 2022 20:31:05 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-23 08:14:20.728424
• Title: Generalized Optimistic Methods for Convex-Concave Saddle Point Problems
• Title（参考訳）: 凸凸鞍点問題の一般化的楽観的解法
• Authors: Ruichen Jiang, Aryan Mokhtari
• Abstract要約: 楽観的勾配法は凸凹サドル点問題を解くための効率的な一階法であることを示す。 また、スムーズ性係数を知らずにステップサイズを選択するための適応的な線探索手法も開発している。
• 参考スコア（独自算出の注目度）: 26.328847475942894
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The optimistic gradient method has seen increasing popularity as an efficient first-order method for solving convex-concave saddle point problems. To analyze its iteration complexity, a recent work [arXiv:1901.08511] proposed an interesting perspective that interprets the optimistic gradient method as an approximation to the proximal point method. In this paper, we follow this approach and distill the underlying idea of optimism to propose a generalized optimistic method, which encompasses the optimistic gradient method as a special case. Our general framework can handle constrained saddle point problems with composite objective functions and can work with arbitrary norms with compatible Bregman distances. Moreover, we also develop an adaptive line search scheme to select the stepsizes without knowledge of the smoothness coefficients. We instantiate our method with first-order, second-order and higher-order oracles and give sharp global iteration complexity bounds. When the objective function is convex-concave, we show that the averaged iterates of our $p$-th-order method ($p\geq 1$) converge at a rate of $\mathcal{O}(1/N^\frac{p+1}{2})$. When the objective function is further strongly-convex-strongly-concave, we prove a complexity bound of $\mathcal{O}(\frac{L_1}{\mu}\log\frac{1}{\epsilon})$ for our first-order method and a bound of $\mathcal{O}((L_p D^\frac{p-1}{2}/\mu)^{\frac{2}{p+1}}+\log\log\frac{1}{\epsilon})$ for our $p$-th-order method ($p\geq 2$) respectively, where $L_p$ ($p\geq 1$) is the Lipschitz constant of the $p$-th-order derivative, $\mu$ is the strongly-convex parameter, and $D$ is the initial Bregman distance to the saddle point. Moreover, our line search scheme provably only requires an almost constant number of calls to a subproblem solver per iteration on average, making our first-order and second-order methods particularly amenable to implementation.
• Abstract（参考訳）: 楽観的勾配法は凸凹サドル問題を解くための効率的な一階法として人気が高まっている。 反復の複雑さを分析するために、最近の研究(arxiv:1901.08511]は、楽観的勾配法を近位点法の近似として解釈する興味深い視点を提案した。 本稿では,このアプローチに従い,楽観主義の基本概念を蒸留し,楽観的勾配法を特殊ケースとして包含する一般化楽観的手法を提案する。 汎用フレームワークは,複合目的関数を用いた制約付き鞍点問題を扱うことができ,ブレグマン距離を持つ任意のノルムを扱うことができる。 さらに,平滑度係数を知らずにステップズを選択する適応ライン探索手法を開発した。 我々は,本手法を一階,二階,高階のオラクルでインスタンス化し,大域的な反復複雑性境界を与える。 目的関数が凸凸であれば、我々の$p$-th-order method(p\geq 1$)の平均イテレートが$\mathcal{o}(1/n^\frac{p+1}{2})$で収束することを示す。 When the objective function is further strongly-convex-strongly-concave, we prove a complexity bound of $\mathcal{O}(\frac{L_1}{\mu}\log\frac{1}{\epsilon})$ for our first-order method and a bound of $\mathcal{O}((L_p D^\frac{p-1}{2}/\mu)^{\frac{2}{p+1}}+\log\log\frac{1}{\epsilon})$ for our $p$-th-order method ($p\geq 2$) respectively, where $L_p$ ($p\geq 1$) is the Lipschitz constant of the $p$-th-order derivative, $\mu$ is the strongly-convex parameter, and $D$ is the initial Bregman distance to the saddle point. さらに, 線形探索方式は, 平均的に1イテレーションあたりのサブプロブレム解数に対して, ほぼ一定回数の呼び出ししか必要とせず, 実装に特に適する一階法と二階法が成立する。

関連論文リスト

• Revisiting Subgradient Method: Complexity and Convergence Beyond Lipschitz Continuity [24.45688490844496]
  次進法は非滑らかな最適化のための最も基本的なアルゴリズムスキームの1つである。 本研究では、まず、非Lipschitz凸と弱凸最小化をカバーするために、下次法の典型的な反復複雑性結果を拡張する。
  論文  参考訳（メタデータ） (2023-05-23T15:26:36Z)
• A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
  本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。 特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
  論文  参考訳（メタデータ） (2023-01-10T20:43:29Z)
• Min-Max Optimization Made Simple: Approximating the Proximal Point Method via Contraction Maps [77.8999425439444]
  本稿では,凸/凹凸 min-max 問題に対して,ほぼ最適収束率を許容する一階法を提案する。 我々の研究は、近点法の更新規則を精度良く近似できるという事実に基づいている。
  論文  参考訳（メタデータ） (2023-01-10T12:18:47Z)
• Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
  我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。 提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
  論文  参考訳（メタデータ） (2022-10-23T21:24:37Z)
• Accelerated first-order methods for convex optimization with locally Lipschitz continuous gradient [0.0]
  まず,Lipschitz連続勾配 (LLCG) を用いた非拘束凸最適化について検討し,それを解決するための加速近位勾配 (APG) 法を提案する。 提案手法は検証可能な終端基準を備えており、演算複雑性は$cal O(varepsilon-1/2log varepsilon-1)$である。 提案手法の性能を実証するために,予備的な数値計算結果を示す。
  論文  参考訳（メタデータ） (2022-06-02T10:34:26Z)
• A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
  凸凹対象 $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, ここで、$f$ は局所リプシッツ勾配を持つ凸関数であり、$g$ は凸かつ非滑らかである。 主勾配ステップと2段ステップを交互に交互に行うCondat-Vuアルゴリズムの適応バージョンを提案する。
  論文  参考訳（メタデータ） (2021-10-28T14:19:30Z)
• Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations [54.42518331209581]
  私たちは発見するアルゴリズムを見つけます。 epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using $(epsilon,gamma)$surimateランダムランダムポイント。 ここでの私たちの下限は、ノイズのないケースでも新規です。
  論文  参考訳（メタデータ） (2020-06-24T04:41:43Z)
• Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
  非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。 特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
  論文  参考訳（メタデータ） (2020-02-10T23:23:04Z)
• Randomized Bregman Coordinate Descent Methods for Non-Lipschitz Optimization [31.474280642125734]
  そこで本研究では,新しいテクステンラン化ブレグマン座標降下法(CD)を提案する。 提案手法は$O(epsilon-2n)$であり,$n$は座標のブロック数であることを示す。
  論文  参考訳（メタデータ） (2020-01-15T09:57:38Z)

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

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