Breaking the O(1/\epsilon) Optimal Rate for a Class of Minimax Problems

MaRDI QIDQ6337439zbMATH OpenFDO

Authors Yong Jiang, Yi Ma

Publication date 26 March 2020

Abstract: It is known that for convex optimization $mi{n}_{mathbfwinmathcalW}f(mathbfw)$, the best possible rate of first order accelerated methods is $O(1/sqrtepsilon)$. However, for the bilinear minimax problem: $mi{n}_{mathbfwinmathcalW}ma{x}_{mathbfvinmathcalV}$ $f(mathbfw)$ $$ $-h(mathbfv)$ where both $f(mathbfw)$ and $h(mathbfv)$ are convex, the best known rate of first order methods slows down to $O(1/epsilon)$. It is not known whether one can achieve the accelerated rate $O(1/sqrtepsilon)$ for the bilinear minimax problem without assuming $f(mathbfw)$ and $h(mathbfv)$ being strongly convex. In this paper, we fill this theoretical gap by proposing a bilinear accelerated extragradient (BAXG) method. We show that when $mathcalW=mathbb{R}^d$, $f(mathbfw)$ and $h(mathbfv)$ are convex and smooth, and $$ has full column rank, then the BAXG method achieves an accelerated rate $O(1/sqrtepsilonlogfrac1epsilon)$, within a logarithmic factor to the likely optimal rate $O(1/sqrtepsilon)$. As result, a large class of bilinear convex concave minimax problems, including a few problems of practical importance, can be solved much faster than previously known methods.

This page was built for publication: Breaking the $O(1/\epsilon)$ Optimal Rate for a Class of Minimax Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6337439)