Open Problem: How much overparametrization is needed for ALS in tensor decomposition?

Dionysis Arvanitakis, Vaidehi Srinivas, Aravindan Vijayaraghavan
Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:7105-7110, 2026.

Abstract

We ask how much overparameterization is needed for simple iterative methods such as alternating least squares (ALS) and gradient descent to decompose a third-order tensor. This question can be viewed as a basic setting to study feature learning: when a rank-$r$ tensor in ambient dimension $n$ has $r\ll n$, the latent rank-one components are the features, and $k$ is the amount of overparameterization used by the algorithm. For rank $r$ tensors, recent work shows that overparametrized rank $k=O(r^2)$ suffices for the popular ALS heuristic (with random initialization) to converge to a global optima. Is the quadratic dependence on $r$ an inherent barrier for ALS-like methods? We pose the open problem of proving convergence to the global optimum for $k=o(r^2)$, or proving that a lower bound on the overparametrized rank of $k=\Omega(r^{1+c})$ for some absolute constant $c>0$ is necessary.

Cite this Paper

BibTeX
@InProceedings{pmlr-v336-arvanitakis26a, title = {Open Problem: How much overparametrization is needed for ALS in tensor decomposition?}, author = {Arvanitakis, Dionysis and Srinivas, Vaidehi and Vijayaraghavan, Aravindan}, booktitle = {Proceedings of Thirty Ninth Conference on Learning Theory}, pages = {7105--7110}, year = {2026}, editor = {Hanneke, Steve and Lattimore, Tor}, volume = {336}, series = {Proceedings of Machine Learning Research}, month = {29 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v336/main/assets/arvanitakis26a/arvanitakis26a.pdf}, url = {https://proceedings.mlr.press/v336/arvanitakis26a.html}, abstract = {We ask how much overparameterization is needed for simple iterative methods such as alternating least squares (ALS) and gradient descent to decompose a third-order tensor. This question can be viewed as a basic setting to study feature learning: when a rank-$r$ tensor in ambient dimension $n$ has $r\ll n$, the latent rank-one components are the features, and $k$ is the amount of overparameterization used by the algorithm. For rank $r$ tensors, recent work shows that overparametrized rank $k=O(r^2)$ suffices for the popular ALS heuristic (with random initialization) to converge to a global optima. Is the quadratic dependence on $r$ an inherent barrier for ALS-like methods? We pose the open problem of proving convergence to the global optimum for $k=o(r^2)$, or proving that a lower bound on the overparametrized rank of $k=\Omega(r^{1+c})$ for some absolute constant $c>0$ is necessary.} }
Endnote
%0 Conference Paper %T Open Problem: How much overparametrization is needed for ALS in tensor decomposition? %A Dionysis Arvanitakis %A Vaidehi Srinivas %A Aravindan Vijayaraghavan %B Proceedings of Thirty Ninth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Steve Hanneke %E Tor Lattimore %F pmlr-v336-arvanitakis26a %I PMLR %P 7105--7110 %U https://proceedings.mlr.press/v336/arvanitakis26a.html %V 336 %X We ask how much overparameterization is needed for simple iterative methods such as alternating least squares (ALS) and gradient descent to decompose a third-order tensor. This question can be viewed as a basic setting to study feature learning: when a rank-$r$ tensor in ambient dimension $n$ has $r\ll n$, the latent rank-one components are the features, and $k$ is the amount of overparameterization used by the algorithm. For rank $r$ tensors, recent work shows that overparametrized rank $k=O(r^2)$ suffices for the popular ALS heuristic (with random initialization) to converge to a global optima. Is the quadratic dependence on $r$ an inherent barrier for ALS-like methods? We pose the open problem of proving convergence to the global optimum for $k=o(r^2)$, or proving that a lower bound on the overparametrized rank of $k=\Omega(r^{1+c})$ for some absolute constant $c>0$ is necessary.
APA
Arvanitakis, D., Srinivas, V. & Vijayaraghavan, A.. (2026). Open Problem: How much overparametrization is needed for ALS in tensor decomposition?. Proceedings of Thirty Ninth Conference on Learning Theory, in Proceedings of Machine Learning Research 336:7105-7110 Available from https://proceedings.mlr.press/v336/arvanitakis26a.html.

Related Material