# Scale Up Nonlinear Component Analysis with Doubly Stochastic Gradients

arXiv: https://arxiv.org/abs/1504.03655 · HTML: https://mlsanity.com/paper/1504.03655/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Apr 2015.

## Built on by (most cited first, 6 of 6)

- [Learning with Density Matrices and Random Features](https://mlsanity.com/paper/2102.04394/) (2021)
- [Neural Stochastic Dual Dynamic Programming](https://mlsanity.com/paper/2112.00874/) (2021)
- [Representation Learning via Non-Contrastive Mutual Information](https://mlsanity.com/paper/2504.16667/) (2025)
- [Spectral Bellman Method: Unifying Representation and Exploration in RL](https://mlsanity.com/paper/2507.13181/) (2025)
- [Demystifying SGD with Doubly Stochastic Gradients](https://mlsanity.com/paper/2406.00920/) (2024)
- [Spectral Ghost in Representation Learning: from Component Analysis to Self-Supervised Learning](https://mlsanity.com/paper/2601.20154/) (2026)

## Abstract (arXiv)

Nonlinear component analysis such as kernel Principle Component Analysis (KPCA) and kernel Canonical Correlation Analysis (KCCA) are widely used in machine learning, statistics and data analysis, but they can not scale up to big datasets. Recent attempts have employed random feature approximations to convert the problem to the primal form for linear computational complexity. However, to obtain high quality solutions, the number of random features should be the same order of magnitude as the number of data points, making such approach not directly applicable to the regime with millions of data points. We propose a simple, computationally efficient, and memory friendly algorithm based on the "doubly stochastic gradients" to scale up a range of kernel nonlinear component analysis, such as kernel PCA, CCA and SVD. Despite the non-convex nature of these problems, our method enjoys theoretical guarantees that it converges at the rate tildeO(1/t) to the global optimum, even for the top k eigen subspace. Unlike many alternatives, our algorithm does not require explicit orthogonalization, which is infeasible on big datasets. We demonstrate the effectiveness and scalability of our algorithm on large scale synthetic and real world datasets.