Subquadratic overparameterization for iterative decomposition of smoothed tensors
Let $n \ge r$, fix $q > 0$ and put $\rho = r^{-q}$. Take arbitrary base factors $\bar A, \bar B, \bar C \in \mathbb{R}^{n \times r}$, form $A, B, C$ by adding independent centred Gaussian entries of variance $\rho^2/n$, and let $$T = \sum_{j=1}^{r} a_j \otimes b_j \otimes c_j,$$ where $a_j, b_j, c_j$ are the $j$-th columns of $A, B, C$. Arvanitakis, Srinivas and Vijayaraghavan proved that with $k = O(r^2)$ summands a parallel variant of alternating least squares (ALS), randomly initialized, converges with high probability to a global minimizer of $\|T - \sum_{i=1}^{k} x_i \otimes y_i \otimes z_i\|_F^2$ when the decomposition of $T$ is mildly conditioned and $n$ is large compared with $r$. Algebraic methods such as simultaneous diagonalization recover the decomposition of $T$ in polynomial time in this setting.
Problem. Do there exist $k(r) = o(r^2)$, a polynomial lower bound $n_0(r)$ and a randomly initialized ALS or gradient-descent method, with explicitly specified update rules, initialization and restarts, such that for every $n \ge n_0(r)$ and $0 < \varepsilon < 1$ it returns $k$ summands with $$\left\| T - \sum_{i=1}^{k} x_i \otimes y_i \otimes z_i \right\|_F \le \varepsilon \|T\|_F$$ using a number of exact real arithmetic operations polynomial in $n$, $r$ and $\log(1/\varepsilon)$, with probability $1 - o_r(1)$ over the once-drawn smoothed input and, conditionally on the input, with success probability at least inverse-polynomial over the initialization? The method must minimize $\|T - \sum_{i=1}^{k} x_i \otimes y_i \otimes z_i\|_F^2$ by alternating block least-squares steps or gradient steps, and its initial factors must be drawn independently of $T$ and of $A, B, C$, apart from an explicitly specified scalar normalization and dependence on $n$, $r$, $\rho$ and $\varepsilon$.
Source: Stated by OpenProblemsInNLA, after Arvanitakis, Srinivas and Vijayaraghavan (2026), Open Problem 2.
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- NA — Numerical Analysis
- Secondary
- OC
- Keywords
- alternating least squares, OpenProblemsInNLA, smoothed analysis, tensor decompositions
- Literature checked
- Oct. 6, 2026 by clemens-admin
References
@inproceedings{arvanitakis2026,
author = {Arvanitakis, Dionysis and Srinivas, Vaidehi and Vijayaraghavan, Aravindan},
title = {Open Problem: How much overparametrization is needed for {ALS} in tensor decomposition?},
booktitle = {Proceedings of Thirty Ninth Conference on Learning Theory},
series = {Proc. Mach. Learn. Res.},
volume = {336},
publisher = {PMLR},
year = {2026},
pages = {7105--7110},
url = {https://proceedings.mlr.press/v336/arvanitakis26a.html},
}
@inproceedings{arvanitakis2025,
author = {Arvanitakis, Dionysis and Srinivas, Vaidehi and Vijayaraghavan, Aravindan},
title = {Guarantees for Alternating Least Squares in Overparameterized Tensor Decompositions},
booktitle = {Advances in Neural Information Processing Systems 38 (NeurIPS 2025)},
year = {2025},
pages = {86725--86775},
doi = {10.52202/085713-2614},
}
@misc{openproblemsinnla-tr09,
author = {Townsend, Alex},
title = {{TR-09}: Subquadratic overparameterization for iterative decomposition of smoothed tensors},
howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
year = {2026},
url = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/tensor-computations/TR-09/README.md},
note = {Read at commit e375a6f, 2026-09-30},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00126, "Subquadratic overparameterization for iterative decomposition of smoothed tensors", clopen.solutions.