Strict Saddle Property and Noisy Stochastic Gradient Saddle Escaping for Orthogonal Tensor Decomposition

The geometric characterization of $(\theta,\gamma,\zeta)$-strict saddle functions (both unconstrained in $\mathbb{R}^d$ and manifold-constrained via generalized Lagrange multipliers on $\{c(x)=0\}$) and the polynomial-time saddle-escaping convergence guarantee of *Noisy Stochastic Gradient Descent* $w_{t+1} = w_t - \eta(\nabla f(w_t) + \xi_t + n_t)$ (with injected isotropic spherical noise $n_t \sim \mathrm{Unif}(\mathbb{S}^{d-1})$) and *Projected Noisy SGD* $w_{t+1} = \Pi_{\mathcal{X}}(w_t - \eta(\nabla f(w_t) + \xi_t + n_t))$, introduced by Rong Ge, Furong Huang, Chi Jin, and Yang Yuan (2015). A twice-differentiable function $f$ satisfies the $(\theta,\gamma,\zeta)$-strict saddle property (Definition 1 / Definition 5) if every point $x$ obeys at least one of: (1) $\|\nabla f(x)\| \ge \theta$ (or Riemannian tangent gradient $\|\chi(x)\| \ge \theta$), (2) $\lambda_{\min}(\nabla^2 f(x)) \le -\gamma$ (or minimum tangent-space Hessian eigenvalue $\lambda_{\min}(M(x)) \le -\gamma$), or (3) $x$ lies within distance $\zeta$ of a local minimum $x^*$ around which $f$ is locally $\alpha$-strongly convex. Theorems 6 and 16 prove that Noisy SGD escapes every saddle region in $O(\gamma^{-2}\log d)$ iterations via second-order Taylor quadratic growth of the negative-eigenvector projection and outputs an $\epsilon$-close local minimum in $O(\mathrm{poly}(1/\theta, 1/\gamma, d)/\epsilon^2)$ iterations; furthermore, Theorem 13 proves that the fourth-order cross-correlation objective $\min_{\|u^{(i)}\|_2=1} \sum_{i\ne j}\langle T, u^{(i)}\otimes u^{(i)}\otimes u^{(j)}\otimes u^{(j)}\rangle$ for orthogonal tensor decomposition satisfies the manifold strict-saddle property with all local minima equal to signed permutations of the true components $\{\pm a_1,\dots,\pm a_d\}$ without sequential deflation.