Breaking the $O(1\mathrm{/}ϵ)$ Optimal Rate for a Class of Minimax Problems

It is known that for convex optimization ${\min }_{\mathbf{w}\in \mathcal{W}}f(\mathbf{w})$, the best possible rate of first order accelerated methods is $O(1\mathrm{/}\sqrt{ϵ})$. However, for the bilinear minimax problem: ${\min }_{\mathbf{w}\in \mathcal{W}}{\max }_{\mathbf{v}\in \mathcal{V}}$ $f(\mathbf{w})$ $+⟨\mathbf{w},\mathit{A}\mathbf{v}⟩$ $-h(\mathbf{v})$ where both $f(\mathbf{w})$ and $h(\mathbf{v})$ are convex, the best known rate of first order methods slows down to $O(1\mathrm{/}ϵ)$. It is not known whether one can achieve the accelerated rate $O(1\mathrm{/}\sqrt{ϵ})$ for the bilinear minimax problem without assuming $f(\mathbf{w})$ and $h(\mathbf{v})$ being strongly convex. In this paper, we fill this theoretical gap by proposing a bilinear accelerated extragradient (BAXG) method. We show that when $\mathcal{W}={\mathbb{R}}^d$, $f(\mathbf{w})$ and $h(\mathbf{v})$ are convex and smooth, and $\mathit{A}$ has full column rank, then the BAXG method achieves an accelerated rate $O(1/\sqrt{\epsilon}\log \frac{1}{\epsilon})$,withinalogarithmicfactortothelikelyoptimalrate$O(1/\sqrt{\epsilon})$. 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.