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

Finding approximate stationary points, i.e., points where the gradient isapproximately zero, of non-convex but smooth objective functions $f$ overunrestricted $d$-dimensional domains is one of the most fundamental problems inclassical non-convex optimization. Nevertheless, the computational and querycomplexity of this problem are still not well understood when the dimension $d$of the problem is independent of the approximation error. In this paper, weshow the following computational and query complexity results:  1. The problem of finding approximate stationary points over unrestricteddomains is PLS-complete.  2. For $d = 2$, we provide a zero-order algorithm for finding$\varepsilon$-approximate stationary points that requires at most$O(1/\varepsilon)$ value queries to the objective function.  3. We show that any algorithm needs at least $\Omega(1/\varepsilon)$ queriesto the objective function and/or its gradient to find $\varepsilon$-approximatestationary points when $d=2$. Combined with the above, this characterizes thequery complexity of this problem to be $\Theta(1/\varepsilon)$.  4. For $d = 2$, we provide a zero-order algorithm for finding$\varepsilon$-KKT points in constrained optimization problems that requires atmost $O(1/\sqrt{\varepsilon})$ value queries to the objective function. Thiscloses the gap between the works of Bubeck and Mikulincer [2020] and Vavasis[1993] and characterizes the query complexity of this problem to be$\Theta(1/\sqrt{\varepsilon})$.  5. Combining our results with the recent result of Fearnley et al. [2022], weshow that finding approximate KKT points in constrained optimization isreducible to finding approximate stationary points in unconstrainedoptimization but the converse is impossible.

The Computational Complexity of Finding Stationary Points in Non-Convex Optimization