Near-Optimal Tensor PCA via Normalized Stochastic Gradient Ascent with Overparameterization

We study the Order-k (k ≥ 4) spiked tensor model for the tensor principal component analysis (PCA) problem: given N i.i.d. observations of a k-th order tensor generated from the model T = λ · v_*otimes k + E, where λ > 0 is the signal-to-noise ratio (SNR), v_* is a unit vector, and E is a random noise tensor, the goal is to recover the planted vector v_*. We propose a normalized stochastic gradient ascent (NSGA) method with overparameterization for solving the tensor PCA problem. Without any global (or spectral) initialization step, the proposed algorithm successfully recovers the signal v_* when Nλ2 ≥ widetildeOmega(dlceil k/2 rceil), thereby breaking the previous conjecture that (stochastic) gradient methods require at least Omega(dk-1) samples for recovery. For even k, the widetildeOmega(dk/2) threshold coincides with the optimal threshold under computational constraints, attained by sum-of-squares relaxations and related algorithms. Theoretical analysis demonstrates that the overparameterized stochastic gradient method not only establishes a significant initial optimization advantage during the early learning phase but also achieves strong generalization guarantees. This work provides the first evidence that overparameterization improves statistical performance relative to exact parameterization that is solved via standard continuous optimization.