← All AI/ML open problems

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?

OpenEditorially scopedSpecified modelCompiled 2026-11-19

Seed catalog · Showing the bundled record.

Problem statement

For a smoothed rank-rr third-order tensor T=∑i=1rai⊗bi⊗ciT=\sum_{i=1}^r a_i\otimes b_i\otimes c_i, can randomly initialized alternating least squares reconstruct TT using k=o(r2)k=o(r^2) components in polynomial time? Alternatively, prove that a superlinear algorithmic rank k=Ω(r1+c)k=\Omega(r^{1+c}) 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

  1. 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.

  2. 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.