Finite-Sample Analysis of Nonlinear Independent Component Analysis:Sample Complexity and Identifiability Bounds

Yuwen Jiang

cs.LGApr 10, 2026

Finite-Sample Analysis of Nonlinear Independent Component Analysis:Sample Complexity and Identifiability Bounds

Authors: Yuwen Jiang

Organizations: School of Artificial Intelligence, Guangzhou Institute of Science and Technology, Guangzhou, China

Abstract

Independent Component Analysis (ICA) is a fundamental unsupervised learning technique foruncovering latent structure in data by separating mixed signals into their independent sources. While substantial progress has been made in establishing asymptotic identifiability guarantees for nonlinear ICA, the finite-sample statistical properties of learning algorithms remain poorly understood. This gap poses significant challenges for practitioners who must determine appropriate sample sizes for reliable source recovery. This paper presents a comprehensive finite-sample analysis of nonlinear ICA with neural network encoders, providing the first complete characterization with matching upper and lower bounds. Our theoretical development introduces three key technical contributions. First, we establish a direct relationship between excess risk and identification error that bypasses parameter-space arguments, thereby avoiding the rate degradation that would otherwise yield suboptimal scaling. Second, we prove matching information-theoretic lower bounds that confirm the optimality of our sample complexity results. Third, we extend our analysis to practical SGD optimization, showing that the same sample efficiency can be achieved with finite-iteration gradient descent under standard landscape assumptions. We validate our theoretical predictions through carefully designed simulation experiments. This gap points toward valuable future research on finite-sample behavior of neural network training and highlights the importance of our validated scaling laws for dimension and diversity.

Figures & tables

Aspect	Lyu & Fu (2022)	This Work
Sample complexity	$\tilde{\mathcal{O}}(d/\sqrt{n})$	$\Theta(d/(\epsilon^{2}\Delta))$
Convergence rate	$\mathcal{O}(1/\sqrt{n})$ (slow)	$\mathcal{O}(1/n)$ (fast)
Concentration inequality	Hoeffding	Bernstein
Variance exploitation	None	Self-bounding property
Lower bounds	Not provided	Matching bounds
SGD optimization	ERM only	ERM + SGD analysis

Table 1: Comparison with Lyu and Fu (2022) : Key technical distinctions

Aspect	Lyu & Fu (2022)	This Work
Concentration inequality	Hoeffding	Bernstein
Variance exploitation	None	Self-bounding property
Generalization bound	$\mathcal{O}(1/\sqrt{n})$	$\mathcal{O}(1/n)$
Analysis approach	Uniform convergence	Localized variance analysis
Lower bounds	Not provided	Matching bounds
Optimization analysis	ERM only	ERM + SGD

Table 2: Technical comparison with Lyu & Fu (2022)

Reference	Setting	Result Type	Rate	Lower Bound
Hyvärinen et al. (2019)	Nonlinear ICA	Asymptotic	N/A	N/A
Khemakhem et al. (2020)	Nonlinear ICA (VAE)	Asymptotic	N/A	N/A
Lyu and Fu (2022)	Nonlinear ICA	Finite-sample	$O(1/\sqrt{n})$	No
Alon and Yehudayoff (2024)	Linear ICA	Finite-sample	$\tilde{\Theta}(1/n)$	Yes
Lei et al. (2023)	Standard CL	Finite-sample	$\tilde{\mathcal{O}}(1/n)$	No
This work	Nonlinear ICA	Finite-sample	$\mathbf{\mathcal{O}(1/n)}$	Yes

Table 3: Comparison with prior work on ICA and representation learning theory

Assumption	Description	Role
A1	Smooth, invertible mixing; bounded moments	Data regularity
A2	Bounded Rademacher complexity	Statistical complexity
A3	Lipschitz and smooth loss	Optimization stability
A4	Non-zero KL divergence between conditionals	Identifiability
A5	Variance controlled by excess risk	Fast convergence

Table 4: Summary of key assumptions

Work	Setting	Sample Complexity	Rate	Optimal?
Hyvärinen et al. (2019)	Nonlinear ICA	Asymptotic only	N/A	N/A
Khemakhem et al. (2020)	VAE-based ICA	Asymptotic only	N/A	N/A
Alon and Yehudayoff (2024)	Linear ICA	$\tilde{\Theta}(nd)$	$\tilde{\Theta}(1/n)$	Yes
Lei et al. (2023)	Standard CL	$\tilde{\mathcal{O}}(d/n)$	$\tilde{\mathcal{O}}(1/n)$	Unknown
This work	Nonlinear ICA	$\mathbf{\Theta(d/(\epsilon^{2}\Delta))}$	$\mathbf{\mathcal{O}(1/n)}$	Yes

Table 5: Detailed comparison with prior work on sample complexity

Figure 1: Experiment 1: Precision Scaling Results. Scaling exponents

\alpha

for 9 training configurations (V7–V15), compared with theoretical prediction

\alpha=-0.5

(dashed blue line). V8-LargeModel achieved the first negative exponent (

\alpha=-0.0014

, green), confirming directional correctness of the theory. The gap between achieved (

\alpha\approx 0

) and theoretical (

\alpha=-0.5

) exponents illustrates the ERM-SGD gap challenge in neural network training.

Figure 2: Experiment 2: Required sample size

n

to achieve target error

\epsilon=0.10

versus dimension

d

. Linear fit shows

n=500d

with

R^{2}=1.000

, confirming theoretical prediction.

Figure 3: Experiment 3: Required sample size

n

versus inverse diversity

1/\Delta

. Linear fit shows

n\propto 1/\Delta

with

R^{2}=0.999

, confirming theoretical prediction.

$T$	$T/n$	MCC	$\epsilon$	Std
1000	0.20	0.4658	0.5342	$\pm$ 0.0172
2000	0.40	0.4367	0.5633	$\pm$ 0.0221
5000	1.00	0.3904	0.6096	$\pm$ 0.0276
10000	2.00	0.3470	0.6530	$\pm$ 0.0131
20000	4.00	0.3484	0.6516	$\pm$ 0.0265

Table 6: SGD Iteration Scaling Results (

n=5000

d=10

)

Figure 4: Experiment 4: Identification error

\epsilon

versus SGD iterations

T

(normalized by

n=5000

). Error stabilizes when

T\geq n

(CV = 3.16%), validating Theorem 4.7 . The counter-intuitive increase with more iterations suggests optimal

T\approx n/2

Configuration	$n=500$	$n=10000$	Trend	Analysis
Diag-LinearMixing	$\epsilon=0.701$	$\epsilon=0.782$	$\nearrow$ +11.6%	Linear mixing harder
Diag-OracleInit	$\epsilon=0.576$	$\epsilon=0.513$	$\searrow$ -10.9%	✓Theory trend!
Diag-LossDirect	$\epsilon=0.609$	$\epsilon=0.522$	$\searrow$ -14.3%	✓Theory trend!

Table 7: Diagnostic Experiment Results

Experiment	Prediction	Measured	Fit	Status
Precision (Exp 1)	$\epsilon\propto n^{-0.5}$	$\epsilon\propto n^{-0.0014}$	$R^{2}=0.005$	Partial
Dimension (Exp 2)	$n\propto d$	$n=500d$	$R^{2}=1.000$	✓Validated
Diversity (Exp 3)	$n\propto 1/\Delta$	$n=12537/\Delta$	$R^{2}=0.999$	✓Validated
SGD Scaling (Exp 4)	$\epsilon$ stabilizes when $T\geq n$	Stable (CV=3.2%)	$T/n\geq 1$	✓Validated

Table 8: Summary of experimental results

Explore similar work

Aug 13, 2026

Foundations of Independent Component Analysis

We present the mathematical foundations of linear independent component analysis (ICA) models based on standard literature in a self-contained note. It is aimed at readers with a background in measure-theoretic probability theory. We first develop the theory of the characteristic functions of probability measures on

\mathbb{R}^d

, including their analyticity and the way in which they determine and characterise the distributions. We then focus on several identifiability results of ICA models with successively strengthened assumptions on the sources: from merely non-constant, to non-Gaussian, to Gaussian-free independent sources. Under the strictest assumptions, we show that the independent sources are identifiable up to translation, permutation, scales and signs, and this even in the presence of additive Gaussian noise. Furthermore, we present the online equivariant gradient descent ICA algorithm for recovering the independent sources from data, in the standard complete noiseless non-Gaussian ICA setting.

Patrick Forré

AI4Science Lab Korteweg-de Vries Institute for Mathematics University of Amsterdam

Parameter Identifiability Independent Component Analysis

Ask PDF

May 8, 2026

Learnability and Competition in High-Dimensional Multi-Component ICA

Independent Component Analysis (ICA) is a foundational tool for unsupervised representation learning, yet its high-dimensional theory remains largely limited to single-component recovery. We develop an asymptotically exact mean-field theory for multi-component online ICA, capturing the coupling induced by simultaneous learning and orthogonalization. In the high-dimensional limit, the joint empirical distribution of learned estimates and ground-truth components converges to a deterministic process, yielding a closed ODE system for the overlap matrix between learned directions and true components. This characterization reveals a genuinely multi-component, initialization-driven phase structure: a decoupled regime, where estimates align with distinct components and evolve nearly independently, and a competition regime, where overlapping initializations induce orthogonality-driven conflicts, slow reorientation, and delayed convergence. Our steady-state analysis gives explicit learnability boundaries and competition conditions linking step size, data moments, and initialization. These conditions show that larger higher-order moments and competition shrink the stable learning-rate window, increase convergence times, and predict a staircase phenomenon in which the number of recoverable components changes discretely with the learning rate. Experiments on synthetic data and hyperspectral remote sensing data validate the predicted trajectories and phase behavior.

Eser Ilke Genc, Samet Demir, Zafer Dogan

MLIP Research Group, KUIS AI Center, Koç University · Department of EEE, Koç University

Independent Component Analysis Unsupervised Representation Learning Mean-Field Theory Statistical Learning Theory Online Learning

Ask PDF

Sep 18, 2026

Kinks vs. Smoothness: Identifiability of Real Analytic nICA for Laplace-like Sources

Many machine learning systems try to explain complex data - like images or financial time series - in terms of hidden, independent factors that generated them. Recovering the true underlying factors, rather than some scrambled version of them, is the central challenge of nonlinear Independent Component Analysis (nICA). We prove identifiability (exact recovery) up to trivial ambiguities for real analytic generating functions when source probability density functions have a finite number of discontinuities in the first derivative. The Laplace distribution is the most prominent example satisfying this assumption. Our proof relies on the contrast between kinks in the source distribution and the smoothness of real analytic functions. Real analytic functions comprise a broad class of generating mechanisms, and can be approximated with Normalizing Flows or Variational Autoencoders with standard activation functions (e.g., tanh, softplus, GELU), so our result applies with minimal changes to existing training pipelines. We perform experiments on real and synthetic data with both Normalizing Flows and Variational Auto-Encoders demonstrating their identifiability properties. In experiments on CelebA data we recover several interpretable latent factors controlling unique attributes across the dataset.

Isaac Manring, Kejun Huang

Department of Computer Science University of Florida Gainesville, FL 32611, USA

Independent Component Analysis Representation Identifiability

Ask PDF