Yang-Da Bei

Benign Loss Landscapes Can Coexist with Worst-Case Hardness

This work studies tree tensor networks (TTNs), a model class that generalizes deep linear networks and Tucker decompositions and shows 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 neura...