Which data are learnable?

Learning generic tasks in high dimension is impossible, as it would require an unreachable number of training data. Yet algorithms or humans can play the game of go, decide what is on an image or learn languages. 
The only resolution of this paradox is that learnable data are highly structured. I will review ideas in the field of what this structure may be. I will then discuss two recent results of our group. (i) if the data  is hierarchical,
supervised learning can occur with a training set size which is polynomial, and not exponential, in the data dimension (1). (ii) I will discuss how novel data, such as the pictures of the fake celebrities below, can be generated by composing
known features into a new whole. This theory of composition predicts a phase transition in generative models. I will discuss empirical evidence for its validity (2). 

(1) Cagnetta, Petrini, Tomasini, Favero, Wyart,  23’
(2) Sclocchi, Favero, Wyart, 24'