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, and they serve as invaluable preprocessing tools for various purposes such as data exploration, dimension reduction and feature extraction. However, existing algorithms for nonlinear component analysis cannot scale up to millions of data points due to prohibitive computation and memory requirements. There are some recent attempts to scale up kernel version of component analysis using random feature approximations. However, to obtain high quality solutions, the number of required random features can 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, SVD and latent variable model estimation. Despite the non-convex nature of these problems, we are able to provide theoretical guarantees that the algorithm converges at the rateÕ(1/t) to the global optimum, even for the top k eigen subspace. We demonstrate the effectiveness and scalability of our algorithm on large scale synthetic and real world datasets. Component analysis, especially Principal Component Analysis (PCA) and Correlation Component Analysis (CCA), are basic and popular techniques in statistics, machine learning, and data analysis. They can discover important features and patterns in unlabeled datasets, and thus have many applications, such as exploration, visualization, approximation and denoising of the data. The importance of component analysis become even more significant in the era of big data, since the extraction of components allows downstream applications such as classification and regression to exploit useful information in large datasets in a computationally efficient way. Most, if not all, large scale datasets have inherent nonlinear structures, which leads to increasing interests in kernel component analysis, such as kernel PCA [28], kernel SVD [8], kernel CCA [1], and kernel ICA [5]. These methods extend component analysis to data mapped to the kernel feature space. Since the vectors in the kernel feature space correspond to nonlinear functions in the original space, they enable the exploitation of the nonlinear structure, allowing one to do nonlinear dimension reduction or discover nonlinear latent components. This is crucial for complex data such as text and images, which are abundant nowadays. However, the applicability of kernel component analysis on large-scale datasets has been limited due to prohibitive computation and memory requirement. Recently, methods such as Randomized Component Analysis [19] are able to scale to larger datasets by leveraging random feature approximation. Such methods approximate the kernel function by using explicit random feature mappings. Subsequent component analysis
REF proposed a stochastic algorithm based on the Lagrangian formulation of the CCA objective.
Scale Up Nonlinear Component Analysis with Doubly Stochastic Gradients
ArXiv
ArXiv
Mathematics Computer Science