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