Metraipolis › archive › dc_29ea92be7fa1
Benign Loss Landscapes Can Coexist with Worst-Case Hardness — arXiv:2609.13057
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.13057
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T03:15:57.268Z
- SHA-256 of the archived text
3eb2c38a059079bc9fc06e0797035808b85b300518fe694eb3f4fed5ed01b440- Stable URL of this page
https://metraipolis.com/documento/dc_29ea92be7fa1
How to cite
Benign Loss Landscapes Can Coexist with Worst-Case Hardness — arXiv:2609.13057 — arXiv (en), https://arxiv.org/abs/2609.13057 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_29ea92be7fa1 (Metraipolis archive dc_29ea92be7fa1, sha256 3eb2c38a059079bc9fc06e0797035808b85b300518fe694eb3f4fed5ed01b440)
BibTeX
@misc{dc29ea92be7fa1,
title = {Benign Loss Landscapes Can Coexist with Worst-Case Hardness — arXiv:2609.13057},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.13057},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_29ea92be7fa1; sha256 3eb2c38a059079bc9fc06e0797035808b85b300518fe694eb3f4fed5ed01b440},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.13057. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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. Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-14 in cs.LG). Categorie arXiv: Machine Learning (cs.LG) ; Machine Learning (stat.ML). Pagina del lavoro: https://arxiv.org/abs/2609.13057 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-16T03:05:44.086Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-09-14?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).