acceptodds
Under review as a conference paper at ICLR 2027

Benign Loss Landscapes Can Coexist with Worst-Case Hardness

Abstract

Deep neural networks are expressive enough to contain worst-case targets that can be evaluated in polynomial time but cannot be learned in polynomial time by gradient descent. For practical tasks they nonetheless learn well, raising the question of what non-generic structure of real-world targets enables this. Existing surrogate models cannot pose this question because they either lack hard-to-learn targets entirely (deep linear networks) or cannot evaluate such targets efficiently (kernel methods, infinite-width limits). We study tree tensor networks (TTNs), a model class that generalizes deep linear networks and Tucker decompositions. We show they embed arbitrary read-once Boolean formulas, and thus contain polynomial-size targets that cannot be learned by gradient descent in polynomial time under the same mechanism as neural networks. Despite this, we prove that their loss landscapes are conditionally benign for every realizable target: every local minimum that is minimum-norm is global. Thus, surprisingly, bad local minima are not what distinguishes between typical and worst-case problems in TTNs. Instead, learning difficulty in TTNs can arise from high-order degenerate saddle points, which we show are caused by rank-deficiency. This is explored through a case study of the parity function, illustrating the potential for TTNs to relate landscape geometry to computational hardness.

Primary area:
optimization
Keywords:
loss landscape, tree tensor networks, local minima, saddle points, hardness of learning, parity functions

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_VqmdOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper presents a theoretical model they call tree tensor networks (TTNs), generalizing deep linear networks and Tucker decompositions. They show that TTNs satisfy both properties:

  • its hypothesis class must contain some worst-case targets which cannot be learned in polynomial time by gradient descent, like the parity function.
  • hypotheses in the class must themselves be evaluable in polynomial time; otherwise the learning difficulty is trivial and unsurprising. Hence, they claim that this is a new better deep learning surrogate, as classic ones do not satisfy both attributes.

Their main conceptual contributions are:

  • They show that TTN do not have local minima, under a minimum norm assumption

  • They show that learning difficulty in TTNs can arise from high-order degenerate saddle points, caused by rank-deficiency.

  • They give a case study with the parity function.

Critical strengths
  • The problem the paper studies seems highly important, even though I am not a direct expert on the issue.

  • The model is, according to the paper, the first surrogate to answer both to contain problems that are easy to evaulate but hard for GD to be learned.

  • I found it overall interesting

Critical weaknesses

The main weakness I see is whether this is relevant for practical settings. While the results are nice, I am not sure it can be convincing without empirical evidence. I also think the theorem showing the benign behavior relies on strong assumptions that are not really practical, and without them the setting is no more really benign as was shown in the paper.

Questions for authors
  • Could you please elaborate on why this is relevant to practice?
1 comment

We thank the reviewer for their time, and for finding the problem important and the paper interesting.

We agree that there is a gap between this paper and practice, and this is a very valid concern to have. But this gap is not specific to our paper. Nobody currently knows how to prove results like ours for practical networks. The field’s main route toward closing the gap has been to study simpler models that can be analyzed exactly, most prominently deep linear networks (Saxe et al., 2013; Kawaguchi, 2016, etc). Nobody trains deep linear networks for real tasks, but studying them has shaped how the field understands depth, initialization, and implicit regularization (see e.g. Section 3 of our paper). Simon et al. 2026 lists nonlinear generalizations of such models as their first suggested open research direction.

We believe tree tensor networks are a substantial step closer to practice, for three reasons.

First, they strictly generalize deep linear networks. Every deep linear network is a TTN, so nothing is lost by moving to TTNs.

Second, unlike deep linear networks, which can only compute linear functions, TTNs can perform genuinely nonlinear computation, such as evaluating Boolean logic (Section 3). They can also model real data reasonably well, though they are still far from state of the art. Tensor trains, a special case of TTNs, achieve under 1% test error on MNIST (Stoudenmire & Schwab, 2016). Tree-shaped TTNs perform well on MNIST and Fashion-MNIST (Stoudenmire, 2018). Tensor-train language models outperform small RNNs on language modeling (Su et al., 2024).

Third, and most importantly, TTNs let us answer questions which we could not even ask before. They can represent functions that gradient descent provably cannot learn efficiently, unlike deep linear networks. This is what lets us ask why training succeeds on some tasks and fails on others. This is a real phenomenon that can exist in virtually all realistic learning setups, and previous toy models could not capture it.

We therefore believe that TTNs are a meaningful and needed step to theoretical results which apply to real architectures.

Finally, a small note on the strength of assumptions: our main claim is that a benign loss landscape can coexist with hard-to-learn targets, and our assumptions are sufficient to show this. The point is that it is surprising that these two phenomena can coexist, and this fact constrains our possible explanations for these phenomena.

Reviewer_BHYxOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper investigates the loss landscape of tree tensor networks (TTN). It finds that TTN does not have bad minimal-norm local minima, and the bad critical points are rank-deficient.

Critical strengths
  1. The paper is easy to follow.

  2. The investigated problem is well-defined and important and the paper provides some insights on it to help people understand it.

Critical weaknesses

The tree tensor network investigated in the paper is a toy network and remains structurally quite different from commonly used architectures such as MLPs, CNNs, and GNNs. This makes it difficult to transfer the insights of this paper to practice.

Questions for authors
  1. The mathematical formulation of TTNs is not sufficiently intuitive. Although Definition 3.1 provides a formal definition, it is difficult to understand what each node actually takes as input and produces as output, how the weight tensors operate, and how the node-wise multilinear maps compose into the overall function. A small explicit worked example would improve the accessibility of the subsequent Boolean-function and landscape analyses.

  2. The scope of the learning-hardness claim should be stated more carefully. Corollary 3.4 derives hardness through statistical-query lower bounds, with gradient-based learning modeled through expected gradient or loss queries. This is a meaningful notion of hardness, but it is not obviously equivalent to saying that general finite-step GD or SGD cannot efficiently learn the target.

  3. The minimum-norm assumption substantially limits the practical interpretation of Theorem 4.3. The strongest benign-landscape result only guarantees that minimum-norm local minima are global. Although the authors connect minimum norm to balancedness and show that it is preserved under gradient flow, it remains unclear whether standard random initialization and practical finite-step optimization actually satisfy, or close to, this regime.

  4. Corollary 4.4 only provides an existence result. The existence of a continuous non-increasing path from a non-optimal point to a point of lower loss does not imply that gradient descent can efficiently identify or follow such a path. Therefore, the absence of “bad valleys” should not be interpreted directly as evidence of easy optimization.

  5. The connection between degenerate saddles and worst-case learning hardness is not fully established. Proposition 5.3 shows that one particular parity construction contains a high-order degenerate saddle, which is an interesting observation. However, the existence of such a saddle does not imply inefficient learning: the paper does not show that gradient-based optimization reaches this saddle from typical initialization, remains near it for super-polynomial time.

  6. The paper should better clarify the novel or surprising insights provided by the TTN analysis. Several qualitative phenomena emphasized in the paper, such as the role of rank deficiency, saddle points, and benign landscapes, have already been observed in simpler models such as deep linear networks and in the broader nonconvex optimization literature. The TTN-specific results may be technically nontrivial generalizations, but it remains unclear what fundamentally new conceptual message is learned from them beyond extending known phenomena to a richer model class.

  7. The practical relevance of the TTN results should be better justified. The main theoretical conclusions rely on the TTN structure. It is therefore unclear which of these mechanisms are expected to carry over to commonly used architectures such as MLPs, CNNs, GNNs, or Transformers. Since the paper motivates TTNs as a surrogate model for understanding deep learning, a clearer discussion of this connection would strengthen the practical significance of the work.

2 comments

We thank the reviewer for their time, and for their recognition that the paper is easy to follow and investigates an important problem. We address concerns and questions below.

Weakness: TTNs are a toy model. Indeed, TTNs are intended as a toy model, in the same sense as deep linear networks, which have been widely studied for exactly this reason. A recent position paper (Simon et al. 2026) lists “simple, solvable models of genuinely deep, nonlinear learning” as its first proposed direction for future research (Open Direction 1).

Q1: Requests a small worked example of a TTN. The paper does include such an example, in Figure 3. It shows specific inputs, the entries of a node tensor, and the value carried along every edge. We are confused what is missing from this example? We are happy to modify it or add another example.

Q2: Statistical-query hardness is not the same as hardness for SGD. We agree, and the paper does make this distinction. Footnote 5 states that our definition "includes full-batch gradient descent, but not stochastic gradient methods," and it cites Abbe et al. (2021b) for the SGD case.

Q3: Limitations of the minimum-norm assumption. We strongly believe the minimum-norm condition is a strength of the paper rather than a limitation. It is preserved by gradient flow (Proposition 4.2). Weight decay drives training toward it exponentially fast from any initialization (Corollary F.13). It generalizes the standard balancedness assumption from deep linear networks (Proposition F.10). It is a natural property connected to geometric invariant theory (Appendix F). And it cannot simply be dropped, since without it spurious local minima exist (Appendix G). We discuss this in both the main text and Appendix F, but can expand this discussion further.

Q4: Corollary 4.4 does not imply that gradient descent follows the descent path. We agree, and we do not expect gradient descent to follow these paths in general. Corollary 4.4 is a secondary result; our main landscape result is Theorem 4.3. The role of Corollary 4.4 is narrower: it rules out loss barriers, which are a mechanism by which bad local minima trap SGD (Appendix I.2). We can make this point more explicitly in the paper.

Q5: The parity saddle does not establish learning hardness. We note that the paper does not claim that this saddle establishes worst-case hardness. We propose it as a possible explanation, and Appendix I.3 discusses why a degenerate saddle may not be sufficient on its own. We believe this to be an interesting direction for future work.

Q6: What is new beyond extending known phenomena? We explain the desiderata missing from prior results in the abstract, the introduction, and Figure 1. We also discuss the relation to prior work in Section 2. We are confused: could the reviewer clarify what they find missing from this discussion?

Q7: Relevance to MLPs, CNNs, and Transformers. This is a good question, thank you. We refer to our response to reviewer Vqmd for a more in-depth answer.

Thank you for your response. However, after reading the rebuttal, I still have the following concerns.

  1. For the mathematical formulation of TTNs, I think Figure 3 helps. It would be better to show the operations more explicitly there, for example, how the inputs are processed (concatenated or operated separately?) and how they are operated with WANDW_{AND} and WORW_{OR}. This would help the audience understand the TTN more deeply.

  2. For the minimal norm assumption, it is still unclear whether standard random initialization and practical finite-step optimization actually satisfy, or close to, this regime. Because if random initialization does not come close to this regime, then the minimum-norm assumption will not hold. This is my major concern and so far the explanation is not convincing to me.

  3. In the paper, such as the abstract, the authors do mention some differences from existing works, such as "For practical tasks they nonetheless learn well, raising the question of what non-generic structure of real-world targets enables this. Existing surrogate models cannot pose this question because they either lack hard-to-learn targets entirely (deep linear networks) or cannot evaluate such targets efficiently (kernel methods, infinite-width limits). But this is more like the difference between the TTN and the other architectures, not the methodological contribution or insights of the paper. Thus, I suggest the authors to explain the new conceptual message or the methodological contribution of the paper.

Reviewer_pEUwOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper is motivated by the mystery observed in deep learning on why gradient optimizers seem to be able to find high quality minima, even under non convex landscapes, and studies benign landscapes vs worst-case hardness.

Here, benign landscapes means that local minima are global as well. Prior works have established results of that flavor for deep linear networks, or very wide networks, but cannot yet explain why training succeeds for other cases. The parity function is one such example, that the authors call target, and that cannot be efficiently leared via gradient descent. The authors conclude that practical settings (called targets by the authors) must possess a property not shared by worst-case targets.

To capture these observations, the authors propose Tree Tensor Networks (TTNs) which are defined by a tree whose nodes have multilinear maps, and as such they generalize deep linear networks. As the authors note, the TTNs can express any read-once Boolean formula, including parity, and can also be evaluated in time polynomial in the tree size and Bond Dimension (not sure they define it when first stated).

The paper proves that for worst case targets the TTNs landscapes are conditionally benign, so all min-norm local minima are global minima. This is presented as Theorem 4.3. On the other hand, they prove that they can contain worst-case targets. The authors propose that such two properties can arise from high-order degenerate saddle points by showing that any critical points (which are not global minima) must occur at Tucker-rank-deficient points (I used their phrasing here, as it was hard to understand and the authors do not provide context).

Critical strengths

-the model itself for TTNs seems interesting as an intermediate model by which we can study the loss landscape and understand the aforementioned properties in temrs of learning and optimization.

Critical weaknesses

-the paper is extremely hard to read, with often missing definitions and context, and heavy use of jargon that is undefined.

-the main paper does not contain any proofs for the main theorems and statements, which renders the paper not so informative as is expected for the level of ICLR.

-the technical description of the paper lacks rigor, in part due to the missing proofs. The authors should try to improve the presentation and main ideas behind the proofs rather than just stating the main theorems and then put all proofs in the appendix.

-without describing the proofs to some level of detail, one cannot judge the importatn novel aspects and do a comparison with known prior results and techniques.

Questions for authors

-Can the authors provide a proof sketch and proof idea for their main theorems?

-What is novel in the proofs? What was known and should be attributed to prior works for those main proofs?

2 comments

We thank the reviewer for their time, and for their recognition that tree tensor networks seem like an interesting intermediate model for studying the loss landscape and optimization.

We want to take the concerns raised here seriously, but we are unsure what changes would be possible to address them. We would be grateful for clarification on the points below.

Rigor. Every term in the theorem statements is defined in the main text. Every result is proved in full in the appendices. The two central theorems are also machine-checked in Lean 4 (Appendix J). Could the reviewer point to a statement or step they believe is not rigorous?

Proofs in the main text. Given the nine page limit on main body content, the standard practice is to put proofs in the appendix, which is what we do. Each major proof there opens with an overview of its main idea (Appendices C, D, and F.1). Is there a specific result in the main text that the reviewer could not follow without its proof? We are happy to move specific details from the proofs or their overviews to the main text of the paper if they can fit within the page limit.

Undefined terms. The review claims that the paper makes “heavy use of jargon that is undefined.” Can the reviewer clarify what these are? The review mentions “bond dimension” and “Tucker-rank-deficient,” but these are defined in Definition 3.1 and Definition 5.1 respectively. Is the concern instead that terms are not defined sufficiently early in the paper? We will attempt to improve this.

Novelty. The review says “one cannot judge the important novel aspects” of the paper without the proofs. We emphasize that the paper makes a case for novelty based on its results, rather than proofs: that no other loss landscape result satisfies the two desiderata (A) and (B) we lay out on the first page and in Figure 1. Does the reviewer believe this claim is false, and that prior work already establishes this? Or, is the concern that this result would be obvious from existing techniques? We are happy to discuss specific concerns here.

To the reviewer’s questions:

1. Each major proof opens with an overview of its main idea (Appendices C, D, and F.1). In a revision, we are happy to move condensed versions of these into the main text.
2. To our knowledge, the main proof techniques are new; where we build on existing tools, we discuss this (e.g. Appendix F, Remark F.8). But as noted above (while we believe the proofs are useful and meaningful as well), the paper’s case for novelty rests on its results, not its proof techniques. Our results generalize known results for deep linear networks and Tucker decomposition, as discussed in the related works section (Section 2).

Reviewer_pEUwOpenReview ↗

main concerns still remain

As i mentioned in my review, the main paper does not contain proofs. It builds up until the main theorems and tries to give a description of it, but still no proofs or intuition behind the proofs is are presented. Pushing the main proofs to the appendix with no clear exposition is a serious drawback of this paper. Due to that, reading the paper is not so informative unless we go into the very dense and technical appendix. The authors should make an effort to present the main ideas and intution behind the proofs in the main body.

For example, in Sec 4 leading towards your theorem you write phrases such as (taken from your paper): "A minimum-norm point is the most parameter-efficient representation of a given output tensor. Intuitively, it ensures that invisible “useless” structure cannot exist, so there is always sufficient internal capacity in the network to continue learning. We believe this condition to be a natural one. For example, Appendix F studies it in detail, showing that it coincides with the Kempf–Ness condition of geometric invariant theory (Kempf & Ness, 1979) for the gauge group of the network. It is also equivalent to a balancedness condition which generalizes the well-known balancedness condition in deep linear networks (Arora et al., 2018b), and reproduces known canonical forms of tree tensor networks (Acuaviva et al., 2023). We believe this condition to be a significant technical contribution of our work. "

I don't think this is clear at all and in fact it makes the paper hard to follow. I suggest you seriously reconsider the presentation and position of this paper.

I will maintain my score.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.