Non-Strict Saddle Point vs Local Minima While going through Escaping Saddle Points Efficiently, I came across the definition of Strict Saddle Point. They define a stationary point to be a strict saddle if at least one of the eigenvalue of the Hessian Matrix is negative. This implies a non-strict saddle point will have all eigenvalues of the Hessian Matrix greater than or equal to zero. But, isn't this a sufficient and necessary condition for local minima? What is the difference between a non-strict saddle point and a local-minima?


For a function $f\colon\mathbb{R}^n\to\mathbb{R}$, the condition $\nabla^2f(x^*)\succeq 0$ is necessary for $x^*$ to be an unconstrained local minimum of $f$, but it is in general not sufficient. Consider $f\colon\mathbb{R}\to\mathbb{R}$ defined by $f(x)=x^3$. Then $\nabla f(x) = 3x^2$ and $\nabla^2 f(x) = 6x$. Therefore, at $x^*=0$, the function satisfies both the first- and second-order necessary conditions for optimality, i.e. $\nabla f(x^*) = 0$ and $\nabla^2 f(x^*) = 0 \succeq 0$. However, $x^*=0$ is clearly not a local minimum of this function. Indeed, it is a saddle point, but this information cannot be ascertained by the Hessian, since the second-order information at $x^*=0$ does not encapsulate enough information about the geometry of $f$ in that neighborhood. To determine the true optimality (more precisely, lack there of) of $x^*=0$ for this function, you could look at the third-order term in the Taylor series expansion of $f$ around $x^*=0$.
The authors' definition of strict saddle reflects the trouble we see in the above example. In particular, a strict saddle is a saddle point whose behavior can be ascertained by the second-order information given by the Hessian. Analyzing these points avoids the issues with nonstrict saddles where we would need to look beyond second-order information.
