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.
Related
- Benign population landscapes do not transfer to empirical risk minimization in nonsmooth optimization
- RLVR landscapes for iterated multiplications can be benign: Insights from spin-glass theory
- Stable Recovery and Benign Overparameterized Landscapes for Phase Retrieval from Coded Diffraction Patterns
- Optimal Initialization Scale for Neural Networks with Locally Quadratic Loss Landscapes: An SGD Dynamics Perspective
- Worst-Case Bayesian CVaR Regret Bounds for Episodic Markov Decision Processes
BibTeX
@misc{furman2026benign,
title = {{Benign Loss Landscapes Can Coexist with Worst-Case Hardness}},
author = {Zach Furman and Stephan Wäldchen and Yangda Bei and Liam Hodgkinson},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.13057},
eprint = {2609.13057},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.13057},
}
RIS
TY - UNPB
TI - Benign Loss Landscapes Can Coexist with Worst-Case Hardness
AU - Zach Furman
AU - Stephan Wäldchen
AU - Yangda Bei
AU - Liam Hodgkinson
PY - 2026
DA - 2026/09/11
PB - arXiv
DO - 10.48550/arxiv.2609.13057
UR - https://arxiv.org/abs/2609.13057
AB - 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.
ER -