Fugu-MT 論文翻訳(概要): Generalized Optimistic Methods for Convex-Concave Saddle Point Problems

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

arxiv url: http://arxiv.org/abs/2202.09674v2
Date: Wed, 10 Jan 2024 05:05:20 GMT
ステータス: 処理完了
システム内更新日: 2024-01-11 18:13:57.111165
Title: Generalized Optimistic Methods for Convex-Concave Saddle Point Problems
Title（参考訳）: 凸凸鞍点問題の一般化的楽観的解法
Authors: Ruichen Jiang, Aryan Mokhtari
Abstract要約: この楽観的な手法は凸凹点問題の解法として人気が高まっている。我々は,係数を知らずにステップサイズを選択するバックトラックライン探索手法を開発した。
参考スコア（独自算出の注目度）: 24.5327016306566
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: The optimistic gradient method has seen increasing popularity for solving convex-concave saddle point problems. To analyze its iteration complexity, a recent work [arXiv:1906.01115] proposed an interesting perspective that interprets this 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 includes 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 using Bregman distances. Moreover, we develop a backtracking line search scheme to select the step sizes without knowledge of the smoothness coefficients. We instantiate our method with first-, second- and higher-order oracles and give best-known global iteration complexity bounds. For our first-order method, we show that the averaged iterates converge at a rate of $O(1/N)$ when the objective function is convex-concave, and it achieves linear convergence when the objective is strongly-convex-strongly-concave. For our second- and higher-order methods, under the additional assumption that the distance-generating function has Lipschitz gradient, we prove a complexity bound of $O(1/\epsilon^\frac{2}{p+1})$ in the convex-concave setting and a complexity bound of $O((L_pD^\frac{p-1}{2}/\mu)^\frac{2}{p+1}+\log\log\frac{1}{\epsilon})$ in the strongly-convex-strongly-concave setting, where $L_p$ ($p\geq 2$) is the Lipschitz constant of the $p$-th-order derivative, $\mu$ is the strong convexity parameter, and $D$ is the initial Bregman distance to the saddle point. Moreover, our line search scheme provably only requires a constant number of calls to a subproblem solver per iteration on average, making our first- and second-order methods particularly amenable to implementation.
Abstract（参考訳）: 楽観的な勾配法は凸凹点問題の解法として人気が高まっている。反復の複雑さを分析するために、最近の研究(arxiv: 1906.01115]は、この手法を近位点法の近似として解釈する興味深い視点を提案した。本稿では,このアプローチに従い,楽観主義の基本概念を蒸留し,楽観的勾配法を特別に含む一般化楽観的手法を提案する。汎用フレームワークは,複合目的関数を用いた制約付き鞍点問題を扱うことができ,ブレグマン距離を用いて任意のノルムを扱うことができる。さらに,スムーズ性係数を知らずにステップサイズを選択するバックトラックライン探索手法を開発した。一階,二階,高階のオラクルでメソッドをインスタンス化し,最もよく知られたグローバルなイテレーション複雑性境界を与える。一階法では、目的関数が凸凸であるときに平均的反復関数が$O(1/N)$で収束し、目的関数が凸凸凸であるときに線形収束することを示す。 For our second- and higher-order methods, under the additional assumption that the distance-generating function has Lipschitz gradient, we prove a complexity bound of $O(1/\epsilon^\frac{2}{p+1})$ in the convex-concave setting and a complexity bound of $O((L_pD^\frac{p-1}{2}/\mu)^\frac{2}{p+1}+\log\log\frac{1}{\epsilon})$ in the strongly-convex-strongly-concave setting, where $L_p$ ($p\geq 2$) is the Lipschitz constant of the $p$-th-order derivative, $\mu$ is the strong convexity parameter, and $D$ is the initial Bregman distance to the saddle point. さらに,1次および2次探索方式では,1次および2次探索方式を実装しやすいものにするため,反復毎に一定数の呼び出ししか必要としない。

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

関連論文リスト