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

Epoch gradient descent method (a.k.a. Epoch-GD) proposed by Hazan and Kale(2011) was deemed a breakthrough for stochastic strongly convex minimization,which achieves the optimal convergence rate of $O(1/T)$ with $T$ iterativeupdates for the {\it objective gap}. However, its extension to solvingstochastic min-max problems with strong convexity and strong concavity stillremains open, and it is still unclear whether a fast rate of $O(1/T)$ for the{\it duality gap} is achievable for stochastic min-max optimization understrong convexity and strong concavity. Although some recent studies haveproposed stochastic algorithms with fast convergence rates for min-maxproblems, they require additional assumptions about the problem, e.g.,smoothness, bi-linear structure, etc. In this paper, we bridge this gap byproviding a sharp analysis of epoch-wise stochastic gradient descent ascentmethod (referred to as Epoch-GDA) for solving strongly convex strongly concave(SCSC) min-max problems, without imposing any additional assumption aboutsmoothness or the function's structure. To the best of our knowledge, ourresult is the first one that shows Epoch-GDA can achieve the optimal rate of$O(1/T)$ for the duality gap of general SCSC min-max problems. We emphasizethat such generalization of Epoch-GD for strongly convex minimization problemsto Epoch-GDA for SCSC min-max problems is non-trivial and requires noveltechnical analysis. Moreover, we notice that the key lemma can also be used forproving the convergence of Epoch-GDA for weakly-convex strongly-concave min-maxproblems, leading to a nearly optimal complexity without resorting tosmoothness or other structural conditions.

Optimal Epoch Stochastic Gradient Descent Ascent Methods for Min-Max Optimization