Research map / Optimization / Implicit bias and generalization
Feature learning from non-Gaussian inputs: the case of Independent Component Analysis in high dimensions
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Analyses sample complexity of FastICA and online SGD (plus smoothed SGD) for recovering a single non-Gaussian direction in the noisy ICA spiked-cumulant model, and checks the search phase of FastICA on ImageNet patches.
Problem
Understanding how many samples FastICA and SGD need to escape the search phase and recover a non-Gaussian feature in high-dimensional ICA, motivated by the similarity between ICA filters and first-layer CNN filters.
Approach
Rewrites non-Gaussian expectations as Gaussian ones via the likelihood ratio and uses information exponents (of the population loss and the contrast function) to derive sharp sample-complexity thresholds for one-step FastICA, vanilla SGD, and smoothed SGD, showing smoothing closes the statistical-computational gap only when the exponents match.
Key results
- FastICA fails to recover the spike at n=d^2 and needs n~d^4 samples (overlap stuck near 1/sqrt(d)), with theory giving O(1/d) overlap for n=d^{k*-delta}, delta in (1,2].
- Vanilla online SGD recovers the spike with n=Omega(d^3 log^2 d), outperforming FastICA; smoothed SGD with matched information exponent (kurtosis contrast) reaches the quadratic n~d^2 threshold.
- On ImageNet patches, FastICA is stuck in a search phase at n=2d but recovers a non-Gaussian direction at n=2d^2.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use FastICA instead of an algorithm reaching quadratic sample complexity | ICA on the noisy ICA model · Noisy ICA model | samples for spike recovery: n \gtrsim d^4; optimal efficient threshold n=\omega(d^2) | Hurt |
| use vanilla online SGD instead of FastICA | ICA on the noisy ICA model · Noisy ICA model | samples for strong spike recovery: n = \Omega(d^3 \log^2 d); FastICA requires n \gtrsim d^4 | Helped |
| smooth the loss and use a contrast with k^*_2=4 matched to the loss exponent | online spherical SGD · Noisy ICA model | samples for spike recovery: d^3 -> d^2 | Helped |
| smooth the loss while retaining a standard contrast with k^*_2=2 (ablation) | online spherical SGD · Noisy ICA model | samples for spike recovery: d^3 | No clear effect |
| remove the regularisation term from the FastICA update (ablation) | FastICA · Noisy ICA model, infinite batch | squared overlap with spike: 1 - o(1) -> O(1/d) | Hurt |
| increase the FastICA batch from quadratic to quartic sample complexity | FastICA · Noisy ICA model | spike recovery: n=d^2: does not recover; n=d^4: recovers the spike | Helped |
| increase the FastICA batch to n=d^{3+\varepsilon} | FastICA · Noisy ICA model | spike recovery: n=d^{3+\varepsilon}, \varepsilon=0.2 | Mixed |
| increase the number of ImageNet patches from n=2d to n=2d^2 | FastICA · ImageNet patches | test loss change from initialization: n=2d; n=2d^2 | Helped |
| use an even FastICA contrast on a latent prior with a non-trivial third cumulant but zero fourth cumulant | FastICA · Noisy ICA model with 3not4 prior | spike recovery | No clear effect |
Surprising findings
- FastICA is blind to odd cumulants, so the third-order cumulant of images does not help it despite a predicted k*=3 threshold.
- The regularisation term in FastICA, introduced for speed, is the essential contribution that escapes mediocrity at initialisation.
Limitations
- Analysis restricted to a single non-Gaussian direction in a simple spiked-cumulant model with whitened inputs.
- Smoothing requires data-dependent tuning of the contrast function, which is not practical.
- Finite-size effects make the empirical non-Gaussianity of ImageNet hard to measure; Laplace prior case verified only experimentally.
Experimental setup
Datasets: ImageNet synthetic noisy ICA (spiked cumulant) data
Benchmarks: ImageNet patches (ICA recovery) synthetic noisy ICA model
Metrics: overlap between estimated and planted direction excess kurtosis test loss change from initialisation fourth-moment ratio
Baselines: online SGD FastICA with gradient-only update smoothed online SGD PCA
Builds on: FastICA information exponent single-index models giant step analysis of one-step gradient methods smoothing for single-neuron learning
Closest papers by meaning
- On the Identifiability of Nonlinear ICA: Sparsity and Beyond (NeurIPS 2022 · similarity 0.86)
- Additive Component Analysis (CVPR 2017 · similarity 0.86)
- Asymptotics of Learning with Deep Structured (Random) Features (ICML 2024 · similarity 0.84)
- A Theory of Non-Linear Feature Learning with One Gradient Step in Two-Layer Neural Networks (ICML 2024 · similarity 0.84)
- How Deep Networks Learn Sparse and Hierarchical Data: the Sparse Random Hierarchy Model (ICML 2024 · similarity 0.84)
- Learning from higher-order correlations, efficiently: hypothesis tests, random features, and neural networks (NeurIPS 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.