Reduce and Conquer: Independent Component Analysis at linear sample complexity

Feature learning at the scale of deep neural networks remains poorly understood due to the complexity of deep network dynamics. Independent component analysis (ICA) provides a simple unsupervised model for feature learning, as it learns filters that are similar to deep networks. ICAextracts these features from the higher-order correlations of the inputs, which is a computationallyhard task in high dimensions with a sample complexity of at least $n ≳ D^2$for $D$-dimensionalinputs. In practice, this difficulty is overcome by running ICA in the d-dimensional subspacespanned by the leading principal components of the inputs, which is often taken to be $d = D/4$.However, there exist no theoretical guarantees for this procedure. Here, we first conduct systematicexperiments on ImageNet to demonstrate that running FastICA in a finite subspace of $d ∼ O_D(1)$dimensions yields non-Gaussian directions in the D-dimensional image space. We then introducea “subspace model” for synthetic data, and prove that FastICA does indeed recover the most nonGaussian direction in a sample complexity that is linear in the input dimension. We finally showexperimentally that deep convolutional networks trained on ImageNet exhibit behaviour consistentwith FastICA: during training, they converge to the principal subspace of image patches beforeor when they find non-Gaussian directions. By providing quantitative, rigorous insights into theworking of FastICA, our study thus unveils a plausible feature-learning mechanism in deep convolutional neural networks.