Fields Mathematical AI Seminar

Neural networks can express functions (like parities) that gradient descent cannot learn in polynomial time, yet on practical tasks they learn well. Understanding what separates typical from worst-case targets requires an analytically tractable toy model that contains such hard targets.

In this talk I will discuss tree tensor networks (TTNs), a nonlinear generalization of deep linear networks and Tucker decompositions. TTNs can represent Boolean formulas, and so contain targets that gradient descent cannot learn in polynomial time. Nevertheless, we show that their loss landscapes are benign: every minimum-norm local minimum is global. Bad local minima are therefore not necessarily what makes hard targets hard. Instead, difficulty appears to arise from high-order degenerate saddle points, which we trace to rank-deficiency. I will illustrate this with the parity function, and close with some thoughts on TTNs as a setting for relating training dynamics and data to the computations that networks learn. Depending on audience interest, I may discuss connections to geometric invariant theory or AI safety.