Although gradient descent (GD) almost always escapes saddle points
asymptotically [Lee et al., 2016], this paper shows that even with fairly
natural random initialization schemes and non-pathological functions, GD can be
significantly slowed down by saddle points, taking exponential time to escape.
On the other hand, gradient descent with perturbations [Ge et al., 2015, Jin et
al., 2017] is not slowed down by saddle points - it can find an approximate
local minimizer in polynomial time. This result implies that GD is inherently
slower than perturbed GD, and justifies the importance of adding perturbations
for efficient non-convex optimization. While our focus is theoretical, we also
present experiments that illustrate our theoretical findings.

本文研究了梯度下降法遇到鞍点问题，提出加入微扰可以提高非凸优化的效率，其在理论上和实验上均得到了支持。

梯度下降法在逃离鞍点时可能需要指数级的时间

Gradient Descent Can Take Exponential Time to Escape Saddle Points

We study the parsing complexity of Combinatory Categorial Grammar (CCG) in
the formalism of Vijay-Shanker and Weir (1994). As our main result, we prove
that any parsing algorithm for this formalism will take in the worst case
exponential time when the size of the grammar, and not only the length of the
input sentence, is included in the analysis. This sets the formalism of
Vijay-Shanker and Weir (1994) apart from weakly equivalent formalisms such as
Tree-Adjoining Grammar (TAG), for which parsing can be performed in time
polynomial in the combined size of grammar and input sentence. Our results
contribute to a refined understanding of the class of mildly context-sensitive
grammars, and inform the search for new, mildly context-sensitive versions of
CCG.

本研究研究了 Vijay-Shanker 和 Weir（1994）形式主义下组合范畴语法（CCG）的解析复杂性。我们的主要结果是，在分析中，将语法的大小（而不仅仅是输入句子的长度）考虑进去时，该形式主义的任何解析算法最坏情况下需要指数时间。这与弱等价形式主义（如 Tree-Adjoining Grammar (TAG)）有所不同，对于这种形式主义，可以在与语法和输入句子的大小成多项式时间完成分析。我们的研究结果有助于更加深入地理解轻度上下文敏感语法的分类，并为寻找新的轻度上下文敏感版本的 CCG 提供信息。