Benign Loss Landscapes Can Coexist with Worst-Case Hardness

Zach Furman, Stephan Wäldchen, Yangda Bei +1

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…