Benign Landscapes and Worst-Case Hardness Can Coexist

Paper: 2609.13057 Authors: Zach Furman, Stephan Wäldchen, Yangda Bei, Liam Hodgkinson Categories: cs.LG, stat.ML

The Gap

There is a gap between expressivity and learnability that the paper states cleanly: 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. So in the worst case, gradient descent fails on a problem that is easy to check.

And yet for practical tasks they nonetheless learn well. That combination is the puzzle: if hard targets exist inside the model class, what non-generic structure of real-world targets enables this? Something about the targets actually encountered must be doing work that the worst case does not capture.

The obstacle is that the obvious surrogate models cannot pose the question at all. They fail in two opposite ways: they either lack hard-to-learn targets entirely (deep linear networks) or cannot evaluate such targets efficiently (kernel methods, infinite-width limits). A surrogate that has no hard problems cannot explain what makes some problems hard; a surrogate that cannot evaluate its own worst cases cannot be used for a complexity argument. You need both properties at once.

   A GAP BETWEEN EXPRESSIVITY AND LEARNABILITY

   deep NNs 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
        -> in the WORST CASE, gradient descent FAILS on a problem that
           is EASY TO **CHECK**
        |
        v
   AND YET for PRACTICAL TASKS they NONETHELESS LEARN WELL
        |
        v
   [THE PUZZLE] if HARD TARGETS EXIST INSIDE THE MODEL CLASS,
     WHAT NON-GENERIC STRUCTURE OF REAL-WORLD TARGETS ENABLES THIS?
        <- something about the targets ACTUALLY ENCOUNTERED must be
           doing work the WORST CASE DOES NOT CAPTURE

   [THE OBSTACLE: THE OBVIOUS SURROGATE MODELS CANNOT POSE THE QUESTION]
     they fail in TWO OPPOSITE WAYS:
       either LACK hard-to-learn targets ENTIRELY
         (deep linear networks)
       or CANNOT EVALUATE such targets EFFICIENTLY
         (kernel methods, infinite-width limits)
     <- a surrogate with NO HARD PROBLEMS cannot explain what makes some
        problems hard
     <- a surrogate that CANNOT EVALUATE ITS OWN WORST CASES cannot be
        used for a COMPLEXITY ARGUMENT
     -> you need BOTH PROPERTIES AT ONCE

The Increment

One sentence: Before this paper, no surrogate model could pose the question of what structure makes real targets learnable; after it, tree tensor networks contain worst-case hardness while remaining conditionally benign everywhere, locating the difficulty in degenerate saddle points rather than bad minima.

Core Mechanism

Tree tensor networks (TTNs) are the surrogate chosen, and the paper states what they generalise: deep linear networks and Tucker decompositions. The design requirement from the gap was two properties at once, and TTNs supply both.

They contain hardness. The paper shows TTNs 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. Two phrases matter: read-once Boolean formulas is a broad enough class that the embedding is not a contrived construction, and the same mechanism as neural networks is what makes the hardness relevant — a hardness proof arising from a different cause would not speak to the phenomenon the paper is investigating.

And they are benign anyway. The paper proves that their loss landscapes are conditionally benign for every realizable target: every local minimum that is minimum-norm is global. The qualifier is the substance: conditionally benign, and among minimum-norm local minima. So this is not the strong claim that all local minima are global; it is the claim that within a well-defined class of critical points, there is nothing to get stuck in.

The consequence is a negative result about the usual explanation: bad local minima are not what distinguishes typical from worst-case problems in TTNs. That rules out one of the standard intuitions about why training works in practice, and ruling it out in a setting where the hardness is otherwise present is what makes it informative.

So the paper locates the difficulty elsewhere: high-order degenerate saddle points, which it shows are caused by rank-deficiency. Two things about this. High-order degenerate saddle points are a different obstacle class from local minima — flat and degenerate rather than trapping — and they are the kind that have been observed in practice. And attributing them to rank-deficiency gives the difficulty a concrete parameter rather than a generic description.

And the mechanism is explored through a case study of the parity function, which is a well-chosen instrument: parity is a canonical example where gradient descent struggles, so a surrogate that explains its difficulty has something to say. The paper frames the larger aim as the potential for TTNs to relate landscape geometry to computational hardness — that is, using the surrogate not just to explain training but to connect the geometry of the loss to the complexity of the problem.

   TREE TENSOR NETWORKS (TTNs) ARE THE SURROGATE CHOSEN
     they GENERALISE deep linear networks AND Tucker decompositions
     <- the design requirement from the gap was TWO PROPERTIES AT ONCE,
        and TTNs supply BOTH

   [PROPERTY ONE: THEY CONTAIN HARDNESS]
     the paper shows TTNs EMBED ARBITRARY READ-ONCE BOOLEAN FORMULAS
     -> they CONTAIN POLYNOMIAL-SIZE TARGETS THAT CANNOT BE LEARNED BY
        GRADIENT DESCENT IN POLYNOMIAL TIME UNDER THE SAME MECHANISM AS
        NEURAL NETWORKS
       <- "READ-ONCE BOOLEAN FORMULAS" is a BROAD ENOUGH CLASS that the
          embedding is NOT A CONTRIVED CONSTRUCTION
       <- "THE SAME MECHANISM AS NEURAL NETWORKS" is what makes the
          hardness RELEVANT: a hardness proof arising from A DIFFERENT
          CAUSE would not speak to the phenomenon under investigation

   [PROPERTY TWO: THEY ARE BENIGN ANYWAY]
     the paper proves their loss landscapes are CONDITIONALLY BENIGN FOR
     EVERY REALIZABLE TARGET:
       EVERY LOCAL MINIMUM THAT IS MINIMUM-NORM IS GLOBAL
       <- the QUALIFIER is the substance:
          "CONDITIONALLY" benign, among "MINIMUM-NORM" local minima
       -> NOT the strong claim that ALL local minima are global
       -> it IS the claim that WITHIN A WELL-DEFINED CLASS OF CRITICAL
          POINTS, THERE IS NOTHING TO GET STUCK IN

   [THE CONSEQUENCE IS A NEGATIVE RESULT ABOUT THE USUAL EXPLANATION]
     BAD LOCAL MINIMA ARE NOT WHAT DISTINGUISHES TYPICAL FROM WORST-CASE
     PROBLEMS IN TTNs
       <- rules out ONE OF THE STANDARD INTUITIONS about why training
          works in practice
       <- and ruling it out IN A SETTING WHERE THE HARDNESS IS OTHERWISE
          PRESENT is what makes it INFORMATIVE

   [SO THE DIFFICULTY IS LOCATED ELSEWHERE]
     HIGH-ORDER DEGENERATE SADDLE POINTS, shown to be caused by
     RANK-DEFICIENCY
       <- a DIFFERENT OBSTACLE CLASS from local minima: FLAT AND
          DEGENERATE rather than TRAPPING -- the kind OBSERVED IN PRACTICE
       <- attributing them to RANK-DEFICIENCY gives the difficulty a
          CONCRETE PARAMETER rather than a GENERIC DESCRIPTION

   [AND THE MECHANISM IS EXPLORED THROUGH A CASE STUDY OF THE PARITY
   FUNCTION]
     <- a WELL-CHOSEN INSTRUMENT: parity is a CANONICAL EXAMPLE where
        gradient descent struggles
     -> a surrogate that EXPLAINS ITS DIFFICULTY has something to say
     <- the larger aim: THE POTENTIAL FOR TTNs TO RELATE LANDSCAPE
        GEOMETRY TO COMPUTATIONAL HARDNESS
        -> using the surrogate NOT JUST to explain training, but to
           CONNECT THE GEOMETRY OF THE LOSS TO THE COMPLEXITY OF THE
           PROBLEM

Think of it as a maze where the dead ends have been eliminated and the difficulty lives in the wide open rooms. The classic worry about training is that you get stuck in a dead end — a local minimum that looks fine and leads nowhere. The paper’s result in this setting is that the dead ends are not where the problem is: within the well-defined class of stopping points, a stopping point that qualifies is a solution. Yet the maze is still hard to traverse, because some of the large rooms are degenerate — the gradient gives no useful direction, so you can wander without progress. Two details from the paper make this concrete. The hardness is genuine and arises the same way it does in neural networks, so the maze really does contain an impossible corner. And the degeneracy traces back to rank-deficiency, so the shape of the room has a name rather than being described as merely “flat”.

Key Concepts

• The expressivity–learnability gap: hard targets exist inside the model class while real targets learn well. It motivates asking what structure of real targets does the work.
• Two properties a surrogate needs: hard-to-learn targets that can still be evaluated efficiently. Missing either makes the question unaskable, which is why previous surrogates could not pose it.
• Conditionally benign landscapes: every minimum-norm local minimum is global. A qualified claim, and the qualification is what makes it precise.
• Bad minima ruled out as the explanation: in a setting where hardness is present. It removes a standard intuition about why training succeeds.
• High-order degenerate saddle points from rank-deficiency: the difficulty located in a specific obstacle class with a concrete cause, and one observed in practice.
• Relating geometry to hardness: the larger aim, using the surrogate to connect loss geometry with computational complexity rather than only explaining training.

Framework Shift

Before (hardness known, explanation unclear):
  networks contain targets that are evaluable but not learnable
  -> real targets nonetheless learn well
  -> surrogate models cannot pose the question: no hard targets, or
     no efficient evaluation
  -> bad local minima assumed to be the obstacle

After (a surrogate with both properties):
  tree tensor networks embed read-once Boolean formulas, so hardness is
    present under the same mechanism as neural networks
  yet landscapes are conditionally benign: minimum-norm local minima
    are global
  -> bad minima are NOT the distinguishing factor
  -> difficulty comes from high-order degenerate saddle points caused
     by rank-deficiency, studied on parity

From assuming that local minima explain why training is hard, to a surrogate in which that explanation is unavailable and the difficulty is located in degenerate saddles, the core shift is that benignity and hardness can coexist, so the obstacle has to be somewhere else.

Expert Assessment

Problem choice: Excellent, and the criterion for a useful surrogate is stated sharply: you need a model class that both contains hard targets and lets you evaluate them. That requirement is what makes the paper’s object well chosen rather than merely convenient, and it explains why the question had gone unposed rather than unanswered.

Method maturity: TTNs are a good choice precisely because they generalise two familiar families, which makes the class recognisable rather than exotic. Embedding read-once Boolean formulas gives the hardness a broad base, and specifying that the hardness arises by the same mechanism as neural networks keeps it relevant. The benignity result is carefully qualified — conditionally, for minimum-norm critical points — which is the honest scope for a claim that does not assert all local minima are global.

Experimental integrity: The most valuable element is the negative result: demonstrating that bad local minima are not the obstacle in a setting where hardness is otherwise present is considerably stronger than arguing they are unimportant in general. Locating the difficulty in high-order degenerate saddle points and attributing them to rank-deficiency gives a testable mechanism, and the parity case study anchors it in a function known to be hard for gradient methods. The limitation is that TTNs are a surrogate, so the transfer to actual deep networks is a hypothesis the paper supports structurally rather than demonstrates empirically.

Writing quality: The three-part structure — hardness present, benignity proved, difficulty located elsewhere — is clearly ordered, and each part is stated with its qualifiers intact. Because the payoff is a failure mode rather than a theorem about training, a short passage on what a practitioner would do with the saddle-point diagnosis — whether rank-deficiency is measurable during training — would make the result actionable.

Verdict: strong accept — it constructs a surrogate with the two properties the question requires, proves hardness and benignity together, and uses that combination to displace a standard explanation with a more specific one.

Takeaways

• Check whether your testbed can pose the question. A surrogate with no hard cases, or one that cannot evaluate them, cannot distinguish typical from worst-case behaviour.
• Separate the two obstacles. Local minima and degenerate saddle points call for different remedies, and a benign landscape rules out the first.
• Keep the qualifiers on a benignity claim. “Minimum-norm local minima are global” is precise where “the landscape is benign” is not.
• Look for the concrete cause of a flat region. Attributing degeneracy to rank-deficiency gives a measurable parameter rather than a description.