Embeddings & representations · Learning dynamics & scaling / Open question
How Much Overparameterization Is Enough?
Tensor decomposition isolates a central mystery of feature learning: how much extra model capacity is needed to discover a small set of latent features?
Seed catalog · Showing the bundled record.
Problem statement
For a smoothed rank- third-order tensor , can randomly initialized alternating least squares reconstruct using components in polynomial time? Alternatively, prove that a superlinear algorithmic rank is necessary for a stated ALS variant, as proposed by Arvanitakis, Srinivas and Vijayaraghavan at COLT 2026.
Assumptions and scope
- Use the source's smoothed setting: r is small relative to ambient dimension n, with independent Gaussian factor perturbations of covariance rho² I/n and rho inverse-polynomial in r; expose conditioning and dimension requirements.
- Fix the parallel or sequential ALS update, least-squares tie-breaking, normalization and random initialization. Guarantees for different iterative variants must be identified separately.
- Seek relative Frobenius reconstruction error at most epsilon in time polynomial in n, r and log(1/epsilon); distinguish high probability over the smoothed instance from success probability over initialization.
What would settle it?
A subquadratic-rank reconstruction guarantee for an explicitly specified iterative algorithm, or a superlinear-rank failure lower bound on random or smoothed instances. A lower bound for one proof technique or a pathological tensor is weaker progress.
Selected for a theoretical or computational target. A fitted scaling curve or improved benchmark score alone does not establish the stated learning-theoretic guarantee.
Status and evidence
The source reports O(r²) global convergence for a parallel ALS variant and an r²-dimensional span-containment bottleneck in that analysis. Generic algebraic tensor recovery is already polynomial-time in this setting. The challenge is the capacity needed by simple iterative dynamics, not tensor identifiability alone. This is an editorial reformulation of a published open problem. The preliminary review through 2026-11-19 does not certify novelty or exclude an unlocated resolution.
Preliminary source check; not an expert-verified open status or an independent audit of proposed proofs. The compilation date is not a literature-review cutoff.
Sources and further reading
- Arvanitakis, Srinivas and Vijayaraghavan — How Much Overparametrization Is Needed for ALS in Tensor Decomposition? ↗problem statement · source checked 2026-11-19
PDF Sections 1–2 checked: smoothed factors have independent Gaussian perturbations of covariance rho² I/n with rho inverse-polynomial in r. Questions 2–3 ask subquadratic algorithmic rank or a superlinear lower bound for iterative methods; generic algebraic recovery is already possible.
- Arvanitakis, Srinivas and Vijayaraghavan — Guarantees for Alternating Least Squares in Overparameterized Tensor Decompositions ↗partial theory · source checked 2026-11-19
Metadata checked; the COLT 2026 problem paper reports a global guarantee for a parallel ALS variant with O(r²) components, mildly conditioned factors and sufficiently large ambient dimension. The original proof was not read.