Stochastic Approximation for Online Tensorial Independent Component Analysis

Abstract

Independent component analysis (ICA) has been a popular dimension reduction tool in statistical machine learning and signal processing. In this paper, we present a convergence analysis for an online tensorial ICA algorithm, by viewing the problem as a nonconvex stochastic approximation problem. For estimating one component, we provide a dynamics-based analysis to prove that our online tensorial ICA algorithm with a specific choice of stepsize achieves a sharp finite-sample error bound. In particular, under a mild assumption on the data-generating distribution and a scaling condition such that $d^4/T$ is sufficiently small up to a polylogarithmic factor of data dimension $d$ and sample size $T$, a sharp finite-sample error bound of $\tilde{O}(\sqrt{d/T})$ can be obtained.

arXiv commentTo appear in Conference on Learning Theory (COLT), 2021

References in corpus (20)

• Identifying and attacking the saddle point problem in high-dimensional non-convex optimization
• SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
• Non-convex Finite-Sum Optimization Via SCSG Methods
• When Are Nonconvex Problems Not Scary?
• Efficient approaches for escaping higher order saddle points in non-convex optimization
• Riemannian SVRG: Fast Stochastic Optimization on Riemannian Manifolds
• Escaping Saddles with Stochastic Gradients
• Stochastic Recursive Gradient Algorithm for Nonconvex Optimization
• Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent
• Near-Optimal Stochastic Approximation for Online Principal Component Estimation
• Subgradient Descent Learns Orthogonal Dictionaries
• A Nonconvex Approach for Exact and Efficient Multichannel Sparse Blind Deconvolution
• Sharp Analysis for Nonconvex SGD Escaping from Saddle Points
• Online Stochastic Gradient Descent with Arbitrary Initialization Solves Non-smooth, Non-convex Phase Retrieval
• Online ICA: Understanding Global Dynamics of Nonconvex Optimization via Diffusion Processes
• High-dimensional Varying Index Coefficient Models via Stein's Identity
• The Scaling Limit of High-Dimensional Online Independent Component Analysis