Loss functions with a large number of saddle points are one of the main obstacles to training many modern machine learning models. Gradient descent (GD) is a fundamental algorithm for machine learning and converges to a saddle point for certain initial data. We call the region formed by these initial values the "attraction region." For quadratic functions, GD converges to a saddle point if the initial data is in a subspace of up to n-1 dimensions. In this paper, we prove that a small modification of the recently proposed Laplacian smoothing gradient descent (LSGD) [Osher, et al, arXiv:1806.06317] contributes to avoiding saddle points without sacrificing the convergence rate of GD. In particular, we show that the dimension of the LSGD's attraction region is at most floor((n-1) 2) for a class of quadratic functions which is significantly smaller than GD's (n-1)-dimensional attraction region.
@cite_24 showed that GD converges to a local minimizer almost surely if the initial point is randomly chosen. The proof is based on the stable manifold theorem and hence no upper bound of the number of steps is provided. How to escape from saddle points efficiently has been a core problem in non-convex optimization. There has been much recent work on developing algorithms which provably avoid saddle points. The existing algorithms use either the perturbed noisy gradient or partially or fully the Hessian information.
@cite_24
2283214199
We show that gradient descent converges to a local minimizer, almost surely with random initialization. This is proved by applying the Stable Manifold Theorem from dynamical systems theory.