Fugu-MT 論文翻訳(概要): Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methods

論文の概要: Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methods

arxiv url: http://arxiv.org/abs/2202.04640v1
Date: Wed, 9 Feb 2022 18:57:47 GMT
ステータス: 処理完了
システム内更新日: 2022-02-10 16:32:23.406594
Title: Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methods
Title（参考訳）: 分離可能なミニマックスのシャーパレートとプリマル2次元外部勾配法による有限サム最適化
Authors: Yujia Jin, Aaron Sidford, Kevin Tian
Abstract要約: 分離可能なミニマックス最適化問題 $min_x max_y f(x) - g(y) + h(x, y)$, where $f$ and $g$ have smoothness and strong convexity parameters $(Lx, mux)$, $(Ly, muy)$, and $h$ is convex-concave with a $(Lambdaxx, Lambdaxy, Lambdayymuyright)$。
参考スコア（独自算出の注目度）: 39.87865197769047
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We design accelerated algorithms with improved rates for several fundamental classes of optimization problems. Our algorithms all build upon techniques related to the analysis of primal-dual extragradient methods via relative Lipschitzness proposed recently by [CST21]. (1) Separable minimax optimization. We study separable minimax optimization problems $\min_x \max_y f(x) - g(y) + h(x, y)$, where $f$ and $g$ have smoothness and strong convexity parameters $(L^x, \mu^x)$, $(L^y, \mu^y)$, and $h$ is convex-concave with a $(\Lambda^{xx}, \Lambda^{xy}, \Lambda^{yy})$-blockwise operator norm bounded Hessian. We provide an algorithm with gradient query complexity $\tilde{O}\left(\sqrt{\frac{L^{x}}{\mu^{x}}} + \sqrt{\frac{L^{y}}{\mu^{y}}} + \frac{\Lambda^{xx}}{\mu^{x}} + \frac{\Lambda^{xy}}{\sqrt{\mu^{x}\mu^{y}}} + \frac{\Lambda^{yy}}{\mu^{y}}\right)$. Notably, for convex-concave minimax problems with bilinear coupling (e.g.\ quadratics), where $\Lambda^{xx} = \Lambda^{yy} = 0$, our rate matches a lower bound of [ZHZ19]. (2) Finite sum optimization. We study finite sum optimization problems $\min_x \frac{1}{n}\sum_{i\in[n]} f_i(x)$, where each $f_i$ is $L_i$-smooth and the overall problem is $\mu$-strongly convex. We provide an algorithm with gradient query complexity $\tilde{O}\left(n + \sum_{i\in[n]} \sqrt{\frac{L_i}{n\mu}} \right)$. Notably, when the smoothness bounds $\{L_i\}_{i\in[n]}$ are non-uniform, our rate improves upon accelerated SVRG [LMH15, FGKS15] and Katyusha [All17] by up to a $\sqrt{n}$ factor. (3) Minimax finite sums. We generalize our algorithms for minimax and finite sum optimization to solve a natural family of minimax finite sum optimization problems at an accelerated rate, encapsulating both above results up to a logarithmic factor.
Abstract（参考訳）: 最適化問題の基本クラスを改良した高速化アルゴリズムを設計する。我々のアルゴリズムは, [cst21] によって最近提唱された相対リプシッツネスによる素数-双次超勾配法の解析手法に基づいている。 1)分離可能なミニマックス最適化。分離可能な minimax 最適化問題 $\min_x \max_y f について検討する。 (x)-g (y) + h(x, ここで、$f$ と $g$ は滑らかで強い凸パラメータ $(l^x, \mu^x)$, $(l^y, \mu^y)$ を持ち、$h$ は $(\lambda^{xx}, \lambda^{xy}, \lambda^{yy})$-blockwise 作用素ノルム有界ヘッセンである。勾配クエリ複雑性 $\tilde{O}\left(\sqrt {\frac{L^{x}}{\mu^{x}}} + \sqrt {\frac{L^{y}}{\mu^{y}}} + \frac{\Lambda^{xx}}{\mu^{x}} + \frac{\Lambda^{xy}}{\sqrt{\mu^{x}\mu^{y}}} + \frac{\Lambda^{yy}}{\mu^{y}}\right)$ のアルゴリズムを提供する。特に、二重線型カップリングを伴う凸凸凹ミニマックス問題(例えば、二次数)に対して、$\Lambda^{xx} = \Lambda^{yy} = 0$ は[ZHZ19] の下界と一致する。 2)有限和最適化。有限和最適化問題 $\min_x \frac{1}{n}\sum_{i\in[n]} f_i について検討する。 (x)$、各$f_i$は$l_i$-smoothであり、全体の問題は$\mu$-strongly convexである。勾配クエリ複雑性 $\tilde{O}\left(n + \sum_{i\in[n]} \sqrt {\frac{L_i}{n\mu}} \right)$ のアルゴリズムを提供する。特に、滑らか性境界が$\{L_i\}_{i\in[n]}$が一様でないとき、加速されたSVRG[LMH15, FGKS15]とKatyusha[All17]を最大$\sqrt{n}$因子で改善する。 (3)ミニマックス有限和。我々は,極小和最適化と有限和最適化のアルゴリズムを一般化し,極小和最適化問題の自然系を高速化速度で解き,両結果を対数係数にカプセル化する。

論文の概要: Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methods

関連論文リスト