Fabiola Ricci (SISSA) Feature learning from non-Gaussian inputs: the case of Independent Component Analysis in high dimensions

Deep neural networks learn structured features by exploiting higher-order correlations in their inputs. How neural networks achieve this computationally hard task remains an open question. Here, we study feature learning in Independent component analysis (ICA), a simple unsupervised method that learns filters resembling those of deep convolutional neural networks. We first prove that FastICA, the most popular ICA algorithm, requires quartic sample complexity to recover a non-Gaussian direction from high-dimensional inputs. In contrast, we show that online SGD outperforms FastICA and even reaches the optimal quadratic sample complexity when smoothing the loss landscape. We then demonstrate the existence of a search phase for FastICA on ImageNet and show that FastICA recovers a non-Gaussian direction if we first project down to a finite number of principal components. We rationalise these experimental results in a synthetic ``subspace model'', where we prove that ICA recovers the non-Gaussian direction embedded in the principal subspace at linear sample complexity. We conclude by discussing how this picture extends to deep convolutional networks trained on ImageNet.