Mild Over-Parameterization Benefits Asymmetric Tensor PCA

arXiv:2604.10208v1 Announce Type: new Abstract: 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^{leftlceiloverline{k}/2rightrceil} state memory cost to recover the signal, where d is the vector dimension and overline{k} is the tensor order. We focus on the setting where overline{k} geq 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 d^{2} 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^{overline{k}-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^{overline{k}/2}, matching the best known polynomial-time complexity. To our knowledge, this is the first tractable algorithm for ATPCA with d^{overline{k}}-independent memory costs.

Related

• How Does Machine Learning Manage Complexity?
• Stochastic Gradient Descent in the Saddle-to-Saddle Regime of Deep Linear Networks

Source: arXiv cs.LG | 2026-04-14