English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

It is known that for convex optimization$\min_{\mathbf{w}\in\mathcal{W}}f(\mathbf{w})$, the best possible rate of firstorder accelerated methods is $O(1/\sqrt{\epsilon})$. However, for the bilinearminimax problem:$\min_{\mathbf{w}\in\mathcal{W}}\max_{\mathbf{v}\in\mathcal{V}}$$f(\mathbf{w})$ $+\langle\mathbf{w}, \boldsymbol{A}\mathbf{v}\rangle$$-h(\mathbf{v})$ where both $f(\mathbf{w})$ and $h(\mathbf{v})$ are convex, thebest known rate of first order methods slows down to $O(1/{\epsilon})$. It isnot known whether one can achieve the accelerated rate $O(1/\sqrt{\epsilon})$for the bilinear minimax problem without assuming $f(\mathbf{w})$ and$h(\mathbf{v})$ being strongly convex. In this paper, we fill this theoreticalgap by proposing a bilinear accelerated extragradient (BAXG) method. We showthat when $\mathcal{W}=\mathbb{R}^d$, $f(\mathbf{w})$ and $h(\mathbf{v})$ areconvex and smooth, and $\boldsymbol{A}$ has full column rank, then the BAXGmethod achieves an accelerated rate $O(1/\sqrt{\epsilon}\log\frac{1}{\epsilon})$, within a logarithmic factor to the likely optimal rate$O(1/\sqrt{\epsilon})$. As result, a large class of bilinear convex concaveminimax problems, including a few problems of practical importance, can besolved much faster than previously known methods.

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