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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Two classes of methods have been proposed for escaping from saddle pointswith one using the second-order information carried by the Hessian and theother adding the noise into the first-order information. The existing analysisfor algorithms using noise in the first-order information is quite involved andhides the essence of added noise, which hinder further improvements of thesealgorithms. In this paper, we present a novel perspective of noise-addingtechnique, i.e., adding the noise into the first-order information can helpextract the negative curvature from the Hessian matrix, and provide a formalreasoning of this perspective by analyzing a simple first-order procedure. Moreimportantly, the proposed procedure enables one to design purely first-orderstochastic algorithms for escaping from non-degenerate saddle points with amuch better time complexity (almost linear time in terms of the problem'sdimensionality). In particular, we develop a {\bf first-order stochasticalgorithm} based on our new technique and an existing algorithm that onlyconverges to a first-order stationary point to enjoy a time complexity of{$\widetilde O(d/\epsilon^{3.5})$ for finding a nearly second-order stationarypoint $\bf{x}$ such that $\|\nabla F(bf{x})\|\leq \epsilon$ and $\nabla^2F(bf{x})\geq -\sqrt{\epsilon}I$ (in high probability), where $F(\cdot)$ denotesthe objective function and $d$ is the dimensionality of the problem. To thebest of our knowledge, this is the best theoretical result of first-orderalgorithms for stochastic non-convex optimization, which is even competitivewith if not better than existing stochastic algorithms hinging on thesecond-order information.

First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Time