Mild Over-Parameterization Benefits Asymmetric Tensor PCA

Asymmetric Tensor PCA (ATPCA) is a prototypical model for studying the trade-offs between sample complexity, computation, and memory. Existing algorithms for this problem typically require at least d^leftlceiloverlinek/2rightrceil state memory cost to recover the signal, where d is the vector dimension and overlinek is the tensor order. We focus on the setting where overlinek ≥ 4 is even and consider (stochastic) gradient descent-based algorithms under a limited memory budget, which permits only mild over-parameterization of the model. We propose a matrix-parameterized method (in d2 state memory cost) using a novel three-phase alternating-update algorithm to address the problem and demonstrate how mild over-parameterization facilitates learning in two key aspects: (i) it improves sample efficiency, allowing our method to achieve near-optimal d^overlinek-2 sample complexity in our limited memory setting; and (ii) it enhances adaptivity to problem structure, a previously unrecognized phenomenon, where the required sample size naturally decreases as consecutive vectors become more aligned, and in the symmetric limit attains d^overlinek/2, matching the best known polynomial-time complexity. To our knowledge, this is the first tractable algorithm for ATPCA with d^overlinek-independent memory costs.