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

This paper studies the complexity of finding approximate stationary pointsfor nonconvex-strongly-concave (NC-SC) smooth saddle point problem:$\min_x\max_yf(x,y)$. Under first-order smoothness conditions, and denote$\kappa_y$ the condition number for the inner strongly-concave problem,existing literature shows that the optimal complexity for first-order methodsto obtain an $\epsilon$-stationary point is$\tilde{\Theta}(\sqrt{\kappa_y}\epsilon^{-2})$. However, when the objectivefunction further satisfies certain high-order smoothness conditions, both theiteration complexity upper and lower bounds can be improved for first-ordermethods. In detail, given the additional assumption that the function$\Phi(x):=\max_y f(x,y)$ has Lipschitz continuous Hessian, we derive afirst-order method with an improved $\tilde{O}(\sqrt{\kappa_y}\epsilon^{-7/4})$complexity, by designing an inexact proximal point variant of the "Convex UntilProven Guilty" method that is compatible with the APPA acceleration techniquefor saddle point problems. In addition to an upper bound, we also construct an$\Omega(\sqrt{\kappa_y}\epsilon^{-12/7})$ lower bound for NC-SC problems withsecond-order smoothness. As a result, the complexity of our proposed algorithmis near-optimal and it almost matches the lower bound barring a negligiblefactor of $\tilde{O}(\epsilon^{-1/28})$.

Near-Optimal First Order Method for Saddle Point Problems with Higher Order Smoothness