Benign Loss Landscapes Can Coexist with Worst-Case Hardness
arXiv:2609.13057v1 Announce Type: new 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 ti