Mathematics Colloquium

Time and Location:

Speaker:

Link:

Provably extracting useful information out of complex high-dimensional data remains a central theoretical challenge in Machine Learning, despite spectacular empirical progress over the past decade. Structural assumptions are needed to beat the curse of dimensionality, and a particularly relevant instance consists of functions that admit a compositional structure in terms of low-dimensional 'features'.  

In this talk, we will review recent progress on this problem, focusing on the Gaussian setting. We will describe (i) optimal algorithms for this problem, by presenting tight upper and lower bounds, (ii) how gradient-based methods that leverage this compositional structure provably learn, with quantitative control on all the problem parameters.

Joint work with Loucas Pillaud-Vivien, Alberto Bietti, Alex Damian and Jason Lee.