Benign Loss Landscapes Can Coexist with Worst-Case Hardness

1 Introduction

• Existing surrogate models do not satisfy both requirements: deep linear networks lack hard-to-learn targets, while infinite-width limits and kernel methods fail efficient evaluation or learnability conditions.The motivating question is what structure of practical targets lets deep learning succeed where worst-case targets resist polynomial-time gradient descent.Source: §1 · p. 1
• TTNs generalize deep linear networks to trees, represent read-once Boolean formulas including parity, and can be evaluated in time polynomial in tree size and bond dimension.They therefore meet the stated requirements of representing hard-to-learn targets while remaining efficiently evaluable.Source: §1 · p. 2
• Under a minimum-norm condition, every local minimum for a realizable TTN target is global, and every non-optimal parameter has a non-increasing path to lower loss.The paper also reports that all non-optimal critical points are Tucker-rank-deficient.Source: §1 · pp. 2–3
• The paper suggests high-order degenerate saddle points can account for optimization difficulty despite benign minima, and identifies rank-deficient points as the only possible non-global critical points.Parity illustrates this mechanism: the escape-path order grows linearly with the number of inputs, making the loss exponentially flat in that number.Source: §1 · pp. 2–3
• TTNs are proposed as an analytically tractable model for studying how target computational structure shapes optimization geometry.The main theorems are verified using the Lean proof assistant.Source: §1 · p. 3

Tensor networks

• Tensor networks have been used in supervised and unsupervised learning, and bilinear neural networks can be equivalent to TTNs with a copying operation [81] [33].Prior work also applies tensor networks to represent high-dimensional feature tensors and multi-feature interactions [77].Source: §2 · p. 3

Benign loss landscapes

• Prior benign-landscape results cover deep linear networks [64] and Tucker decomposition, while this work proves conditional results for arbitrary TTN topologies.The Tucker result requires assumptions including regularization and realizability.Source: §2 · p. 3
• Some nonlinear neural networks have spurious local minima [99], while no-bad-valley guarantees for many networks require extreme overparameterization [75] [101].The paper says its conditional TTN results do not contradict those findings.Source: §2 · p. 3

Learning computationally hard targets

• Prior work studies gradient learning of parities and other hard Boolean targets [65], but typically analyzes particular target families.The authors contrast this with results applying to every realizable target, including worst-case ones.Source: §2 · p. 4

Degenerate saddle points

• For parity with n inputs, the paper links target hardness to saddles of order at least n/2, whereas deep-linear saddle order depends primarily on model depth [49].The authors conjecture that a similar mechanism may occur for hard targets more generally.Source: §2 · p. 4

3 Tree Tensor Networks

• TTNs generalize deep linear networks by replacing matrices with higher-order tensors and chains with trees, enabling branching and compositional structure while retaining tractable algebraic features.A tensor node can receive inputs from multiple sources, unlike a matrix in a chain.Source: §3 · pp. 4–5
• The learning setup samples tensor entries uniformly and evaluates population square loss against the target tensor.The population loss is one-half the mean squared Frobenius error between the represented and target tensors.Source: §3 · pp. 5–6
• A read-once Boolean formula with s gates is represented by a TTN with s nodes and bond dimension 2, using one-hot Boolean values and gate-indicator maps.The composed network outputs the one-hot encoding of the formula’s value.Source: §3 · p. 6
• Any TTN can be evaluated in time polynomial in its tree size and bond dimension, while polynomial-size TTNs with bond dimensions ≥2 are not learnable by gradient descent in polynomially many steps.The hardness follows because TTNs realize every parity function, and parity is not efficiently learnable from statistical queries.Source: §3 · pp. 6–7
• The hardness applies to concept classes and follows from representing Boolean formulas, so it does not depend on the choice of gradient method.The paper’s definition includes full-batch gradient descent; it excludes stochastic methods, although related hardness results apply to moderate-batch SGD.Source: §3 · pp. 6–7

4 The Loss Landscape is Benign

• A minimum-norm point has the smallest parameter norm among parameters representing the same output tensor.The paper describes this as the most parameter-efficient representation of that tensor.Source: §4 · pp. 7–8
• Gradient flow preserves the minimum-norm condition when initialized at a minimum-norm point.The condition also holds for every limit point of the trajectory.Source: §4 · p. 8
• Every local minimum that is a minimum-norm point is a global minimum with zero loss.The result applies to all realizable targets, including worst-case targets.Source: §4 · p. 8
• Without the minimum-norm condition, every non-optimal parameter point has a continuous path along which loss never increases and ends at strictly lower loss.Thus the result rules out bad valleys even without the condition.Source: §4 · p. 8
• The local-minimum result assumes minimum-norm parameters, realizability, square loss, and an acyclic network topology.The paper notes that arbitrary relaxations of these conditions permit spurious local minima.Source: §4 · p. 8

5.1 Rank Deficiencies in Spurious Critical Points

• Non-global critical points must be Tucker-rank-deficient, where the network uses only part of its capacity and can be represented with lower bond dimensions.This confines saddle points to rank-deficient parameters.Source: §5.1 · p. 9

5.2 The Parity Example

• For parity, the rank-1 best-approximation point is a critical saddle of order at least n/2, even though parity is realizable with bond dimension 2.The point represents a state of partial learning progress.Source: §5.2 · p. 9
• Although a descent path exists from the parity saddle, every such path has order at least n/2, so its flatness grows with input size.Theorem 4.3 also rules out minimum-norm spurious local minima for parity.Source: §5.2 · p. 9

6 Conclusion

• TTNs are proposed as analytically tractable toy models that represent nonlinear read-once Boolean computation, unlike deep linear networks.The authors connect this capacity to studying computational structures in deep learning.Source: §6 · pp. 9–10
• TTNs can contain targets that gradient descent cannot learn in polynomial time while conditionally lacking suboptimal local minima.The paper suggests that highly degenerate saddles may be where worst-case difficulty arises.Source: §6 · p. 10
• The parity analysis is a proof-of-concept for how computational structure can influence TTN loss-landscape geometry; systematic study is left for future work.The authors point to analogous closed-form learning-dynamics results in deep linear networks as a possible direction.Source: §6 · p. 10

Appendix

• The appendices provide multilinear-algebra setup, prove the main landscape results, examine the minimum-norm condition and parity saddle, and describe Lean formalization.Appendix B covers edge matricizations, cut factorizations, gauge freedom, and a rank-based realizability characterization.Source: Appendix · p. 17, The minimum-norm condition · p. 17

The minimum-norm condition.

• The minimum-norm condition is equivalent to Kempf–Ness and balancedness conditions, is preserved by gradient flow, and is necessary for the local-minimum result.An explicit three-leaf star TTN has a spurious local minimum without the assumption.Source: The minimum-norm condition · p. 17

A Background: Multilinear Algebra and Tensor Networks

• The background appendix bridges the main text’s directed composition view of TTNs and the proofs’ undirected tensor-contraction view.It reviews multilinear algebra and tensor, array, and multilinear-map representations.Source: A Background: Multilinear Algebra and… · p. 17, §A.1 · p. 18

A.2 Composition Is Tensor Contraction

• Tensor contraction computes composition of multilinear maps, and for vectors or matrices reduces to inner product or matrix multiplication, respectively.Source: §A.2 · p. 19

A.3 Equivalence of TTN Definitions

• Choosing a root orients the undirected TTN and yields the same represented tensor; the contraction-based definition is easier to manipulate algebraically.Source: §A.3 · p. 19

• The appendix sets up edge matricizations, cut factorizations, gauge freedom, realizability, and the residual for the squared loss used in the proofs.The positive normalization factor in the loss does not change its landscape properties.Source: B Additional Setup · pp. 19–20
• Cutting a TTN at an edge gives a factorization across the resulting partition, and changing basis on the bond while inversely transforming the other factor leaves the represented tensor unchanged.These transformations are the parameterization’s gauge freedom.Source: B Additional Setup · p. 20
• A target tensor is realizable with bond dimensions r_e exactly when each edge matricization has rank at most r_e.A realization can use only the target’s edge ranks as bond directions and can be supported on prescribed subspaces of those dimensions.Source: B Additional Setup · p. 20

C No Spurious Critical Points at Full Tucker Rank

• Every full-Tucker-rank critical point is a global minimum; equivalently, any non-global critical point is rank-deficient.The proof inductively removes leaves: full rank and realizability align the model and target at each leaf, transferring criticality and the other conditions to a smaller tree.Source: C No Spurious Critical Points at Full… · p. 21

D No Spurious Local Minima at Minimum-Norm Points

• Every minimum-norm local minimum is globally optimal because any positive-loss minimum-norm critical point has a local loss-decreasing perturbation within a rank-deficient core.The core is formed by collapsing surrounding full-rank regions; coordinated perturbations activate directions invisible to first order.Source: D No Spurious Local Minima at… · p. 22

D.1 Dormant Subspaces

• At minimum-norm points, dormant directions coincide with parameter-kernel directions, and an internal edge is rank-deficient exactly when its model unfolding rank is below its bond dimension.Minimum norm rules out unused tensor slices, and the model unfolding rank equals the ranks of the adjacent tensor matricizations.Source: §D.1 · pp. 23–24

D.2 Active Bond Directions are Target-Aligned

• At a minimum-norm critical point, each active bond direction aligns nontrivially with the target, and the model unfolding rank is at most the target bond rank.When the model unfolding has full bond rank, the cross-Gram matrix is invertible.Source: §D.2 · pp. 24–25

D.3 Reduction to Full Target Rank

• The problem can be reduced to one whose target has full rank on every internal edge, while preserving the represented model tensor and loss under zero-padding.The reduced target has bond rank r*_e on each edge, and the restriction and inclusion maps relate the original and reduced problems.Source: §D.3 · pp. 25–26
• Restricting to the chosen subspaces preserves the external target and its edge-matricization ranks, so the reduced problem can assume full target rank without loss of generality.The target realization lies in those subspaces by construction.Source: §D.3 · p. 26
• Zero-padding commutes with TTN contraction and is a linear isometry, preserving loss and transferring minimum-norm critical points and local minima to the reduced problem.The reduced parameter’s minimum-norm property follows from the original one, and criticality and local minimality also transfer.Source: §D.3 · p. 26
• Any local descent path found after reduction zero-pads to a local descent path for the original problem.Source: §D.3 · p. 26

D.4 The Rank-Deficient Core

• A connected component of rank-deficient edges yields a reduced TTN with the same internal core edges, rank-deficient model edges, and full-rank target edges.The reduction freezes tensors outside the component into boundary factors and preserves the loss up to an additive constant.Source: §D.4 · pp. 26–27
• Any strict local descent path in the reduced core lifts to a strict local descent path in the original network.The reduction also preserves local minimality from the original parameters to the reduced parameters.Source: §D.4 · pp. 27–28

D.5 Descent on the Rank-Deficient Core

• Because the residual is nonzero, a rank-one tensor U can be chosen with negative residual inner product, making the loss decrease for sufficiently small positive t.The continuous perturbation path starts at the original core parameter, so the decrease can be arbitrarily local and then lifted to the full network.Source: §D.5 · pp. 28–29
• Perturbing every core tensor together creates a descent term of order t^N, where N is the number of core vertices.Rank-deficient directions make terms from proper nonempty subsets of perturbed vertices vanish, leaving the full-core term.Source: §D.5 · p. 28

D.6 Main Theorem

• Every minimum-norm local minimum has zero loss and is therefore globally optimal.The proof rules out a non-optimal minimum by reducing it to a rank-deficient core with a strict descent path.Source: §D.6 · p. 29
• The descent direction has order N, the number of vertices in the rank-deficient core, and higher order means a more suppressed escape.The authors relate the order to how much the network must learn “in one step” and note a similar phenomenon in neural networks.Source: §D.6 · p. 29

D.7 Tightness of Assumptions

• The minimum-norm condition is essential: a realizable 3-leaf Tucker decomposition has a spurious local minimum at a non-minimum-norm parameter..Source: §D.7 · p. 29
• Realizability is necessary; without it, even a star TTN with unit bond dimensions can have spurious local minima when fitting generic non-rank-1 targets.The cited contrast is the matrix case, where Baldi and Hornik rule out such minima.Source: §D.7 · p. 29
• The guarantees also rely on square loss and tree topology: other losses can admit spurious critical points, and ring tensor networks can have spurious local minima.The ring example persists under substantial over-parameterization.Source: §D.7 · pp. 29–30
• The authors conjecture that, under the minimum-norm assumption, TTN parameterization alone does not create spurious critical points when none exist in function space, leaving this for future work..Source: §D.7 · p. 29

E Escape Paths

• From any non-target parameter, a continuous path has non-increasing loss and ends at strictly lower loss, but may leave its neighborhood.Thus the corollary does not rule out spurious local minima in unrestricted parameter space.Source: E Escape Paths · p. 30

F The Minimum-Norm Condition

• Minimum norm is equivalent to an easily checked balancedness identity, conserved by tensor-dependent gradient flow and driven toward zero defect exponentially by ℓ2 regularization.The condition generalizes balancedness used in deep linear network analyses [10] and conserved by gradient flow.Source: F The Minimum-Norm Condition · p. 30

F.1.1 The Two-Node Case: Minimal Factorizations

• For two-node matrix factorizations, minimal factorizations form one GL(r)-orbit, and any two factorizations of the same matrix have intersecting orbit closures.The orbit closure contains a minimal factorization whose factors each have squared Frobenius norm equal to the nuclear norm of the product.Source: §F.1.1 · pp. 31–32

F.1.2 The General Case

• For general tree TTNs, contracting edges preserves the relevant orbit-closure structure, enabling induction to show that parameters representing the same tensor have intersecting orbit closures.The resulting uniqueness of the closed gauge orbit in each fiber follows from the shared orbit-closure point.Source: §F.1 · p. 31, §F.1.2 · pp. 33–34

F.1 The Fiber has a Unique Closed Gauge Orbit

• Every TTN contraction fiber contains a norm minimizer whose gauge orbit is its unique closed orbit; uniqueness requires tree topology and can fail for cyclic networks.The minimum-norm parameters satisfy the Kempf–Ness condition, and the balancedness conservation law is a Noether law for gauge symmetry.Source: F The Minimum-Norm Condition · pp. 30–31, §F.1.2 · p. 34

F.1.2 The General Case

• Over the complex numbers, Acuaviva et al. use norm minimization and Kempf–Ness [55] to obtain a minimal canonical form for tensor networks of arbitrary geometry.For tree tensor networks, this form is closely related to the Vidal gauge; the authors state that the real case required proving the result themselves because they could not directly apply complex GIT machinery (see Acosta [6]).Source: §F.1.2 · p. 34

F.2 Equivalent Conditions to Minimum-Norm

• For tree tensor networks, minimum norm on a fiber, minimum norm on the gauge orbit, and balancedness are equivalent; minimum-norm points in a fiber form one orthogonal-gauge orbit.Balancedness is an edge-by-edge condition: the two endpoint tensors use the bond space identically.Source: §F.2 · p. 35
• Tree topology is needed for the implication from gauge-orbit minimum to fiber minimum; a self-loop example shows that the converse can fail.For networks whose internal edges join distinct nodes, the other implications and the equivalence between gauge-orbit minimum and balancedness hold without the tree assumption.Source: §F.2 · p. 36

F.3 Minimum-Norm is Preserved by Gradient Flow

• A minimum-norm initialization remains minimum norm under gradient flow on the square loss, and more generally on losses depending only on the represented tensor.The proof uses the equivalence between minimum norm and balancedness, which is conserved for these losses.Source: §F.3 · pp. 36–37
• With ℓ2 regularization, each balancedness defect decays as e^(-2λt), driving limit points toward minimum norm regardless of initialization.This follows from the defect dynamics ˙∆e = −2λ∆e and the equivalence between balancedness and minimum norm for TTNs.Source: §F.3 · p. 37
• The conservation law for balancedness holds on networks of arbitrary topology, but balancedness need not imply minimum norm outside the tree setting.The tree structure is needed for the equivalence used to conclude that gradient-flow trajectories remain minimum norm.Source: §F.3 · p. 38

G A Spurious Local Minimum Without the Minimum-Norm Assumption

• Without the minimum-norm assumption, a realizable 3-leaf star TTN can have a spurious local minimum at tight bond-dimension capacity.The constructed example requires a multilinear interaction of order at least three.Source: G A Spurious Local Minimum Without the… · p. 38

G.1 Setup

• The target has rank 3 in every matricization, so it is realizable at tight bond dimension 3 on every edge.The construction uses a 3 × 3 × 3 core and three 3 × 3 leaf matrices.Source: §G.1 · p. 38
• At the specified point, the represented tensor is e000 + e111 rather than the target, because the leaf matrices’ third columns vanish.The target-zero coefficients are therefore absent from the contraction at this point.Source: §G.1 · p. 38
• Near the point, any loss decrease would require a positive T222 term, whose increase in the norm term dominates the possible alignment decrease.The loss expansion identifies the alignment term as the only potentially negative term.Source: §G.1 · p. 39
• The specified point is a spurious local minimum of the squared loss, despite representing a tensor different from the target.The same output tensor has a lower-norm representation: 8 < 14.Source: §G.1 · pp. 38–40

H The Parity Example

• The parity parameter point is a critical point and a saddle of order at least n/2.The local loss bound is L(θ) − L(θ0) ≥ −C∥θ − θ0∥^(n/2+1) within radius ρ.Source: H The Parity Example · p. 41
• The appendix conjectures that the parity saddle order may be n − 2, but reports only numerical checks at n ∈ {4, 8}.The authors state that the exact order is not important to their paper and leave it for future work.Source: H The Parity Example · p. 41

I Implications for Learning With Stochastic Gradient Methods

• Population-loss analysis is idealized because practitioners have finite samples and use per-sample losses rather than direct access to the target.The discussion motivates relating the population loss to stochastic methods through noisy estimates of the loss and its gradient.Source: I Implications for Learning With… · p. 42, §I.1 · p. 42
• The paper models minibatch SGD, under standard approximations, as noisy gradient descent on the population loss.The continuous-time approximation assumes Brownian noise and isotropic, homogeneous covariance; the latter is described as unrealistic.Source: I Implications for Learning With… · p. 42, §I.1 · p. 42

I.2 Benign Loss Landscapes Help SGD

• When a suboptimal local minimum has a positive loss barrier, small-noise SGD may remain in its basin for extremely long times.Increasing batch size or decreasing step size reduces the noise scale, making such barriers harder to cross.Source: §I.2 · p. 43
• A population landscape with no suboptimal local minima or non-increasing paths to lower loss avoids this particular failure mode for SGD.The authors connect their benign-loss results to SGD because they remove energetic barriers, not because they establish rapid progress.Source: §I.2 · p. 43

I.3 Degenerate Saddle Points Can Still Slow SGD

• At a degenerate saddle, descent may lack a useful quadratic negative-curvature direction and require higher-order coordinated perturbations.Small perturbations near such a saddle are amplified more slowly, and the parity example exhibits this kind of point.Source: §I.3 · pp. 43–44
• High-order degeneracy may be necessary but not sufficient for difficulty with stochastic noise; the escape path may also need to be unlikely to find by chance.Unlike escape from a local minimum, escape from a saddle has no loss-barrier exponential obstruction, although local geometry can affect the prefactor.Source: §I.3 · p. 44

J Autoformalization in Lean

• The authors formalized Theorems 4.3 and 5.2 in Lean, selecting results whose dependencies could be developed with existing Mathlib infrastructure.The formalization was generated and reviewed with language models; the authors did not retain complete records of token usage, elapsed time, and cost.Source: J Autoformalization in Lean · p. 44, §J.1 · p. 44

J.1 Development and Verification

• Lean and Comparator checks replayed the proofs through the kernel and checked permitted axioms and agreement with production theorem statements.The authors reviewed theorem statements and relevant definitions, but did not line-by-line audit intermediate results or generated proof scripts.Source: §J.1 · pp. 44–45, Figure 5 · p. 45

J.2 Paper-to-Lean Correspondence and Proof Organization

• The Lean representation aggregates external modes and defines contraction as a sum over internal bond indices; the correspondence to the directed definition is explained mathematically but not formalized.Criticality is encoded as a zero Fréchet derivative, with a theorem relating it to vanishing nodewise first-order loss variations.Source: §J.2 · p. 45
• The proof of Theorem 5.2 uses the full-column-rank result for the factor obtained by contracting the rest of the tree at a leaf edge.The manuscript establishes full column rank for both contraction factors at every internal edge; the Lean proof uses the leaf-edge case for induction.Source: §J.2 · p. 45
• Formalization exposed and fixed an edge case in the reduction argument when the target tensor is zero and compressed bond dimensions would be zero.Corollary 4.4 was not formalized because its proof relies on real algebraic geometry and geometric invariant theory outside the stated scope.Source: §J.2 · p. 45

J.3 Formalization as a Verification Check for Toy Models

• The shared library definitions for TTN architecture, contraction, loss, and rank conditions remain available for further model analysis.The authors argue that shared formal definitions can let results on expressiveness, optimization, and learning dynamics compare assumptions and reuse checked lemmas.Source: §J.3 · p. 46
• Formal verification establishes mathematical consequences of a toy model’s assumptions, but whether those assumptions capture phenomena of interest remains an empirical question.The authors propose supplementary machine-checked proofs when dependencies are available in existing libraries, while retaining responsibility for checking that formal statements express intended claims.Source: §J.3 · p. 46