# Mild Over-Parameterization Benefits Asymmetric Tensor PCA

arXiv: https://arxiv.org/abs/2604.10208 · HTML: https://mlsanity.com/paper/2604.10208/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 49 references that are in the map.
- First posted on arXiv 11 Apr 2026.

## Builds on (most cited first, 5 of 5)

- [Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks](https://mlsanity.com/paper/1811.08888/) (2018)
- [Statistical limits of spiked tensor models](https://mlsanity.com/paper/1612.07728/) (2016)
- [Scaling Law for Stochastic Gradient Descent in Quadratically Parameterized Linear Regression](https://mlsanity.com/paper/2502.09106/) (2025)
- [Revisit CP Tensor Decomposition: Statistical Optimality and Fast Convergence](https://mlsanity.com/paper/2505.23046/) (2025)
- [Near-Optimal Tensor PCA via Normalized Stochastic Gradient Ascent with Overparameterization](https://mlsanity.com/paper/2510.14329/) (2025)

## Abstract (arXiv)

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.