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

Introduction

The problem of interest in this paper is given by

where $\xi$ is a random variable and $f(\mathbf{x};\xi)$ is a random smooth non-convex function of $\mathbf{x}$. It is notable that our developments are also applicable to a finite-sum problem with a very large number of components: