Online ICA: Understanding Global Dynamics of Nonconvex Optimization via Diffusion Processes
Solving statistical learning problems often involves nonconvex optimization. Despite the empirical success of nonconvex statistical optimization methods, their global dynamics, especially convergence to the desirable local minima, remain less well understood in theory. In this paper, we propose a new analytic paradigm based on diffusion processes to characterize the global dynamics of nonconvex statistical optimization. As a concrete example, we study stochastic gradient descent (SGD) for the tensor decomposition formulation of independent component analysis. In particular, we cast different phases of SGD into diffusion processes, i.e., solutions to stochastic differential equations. Initialized from an unstable equilibrium, the global dynamics of SGD transit over three consecutive phases: (i) an unstable Ornstein-Uhlenbeck process slowly departing from the initialization, (ii) the solution to an ordinary differential equation, which quickly evolves towards the desirable local minimum, and (iii) a stable Ornstein-Uhlenbeck process oscillating around the desirable local minimum. Our proof techniques are based upon Stroock and Varadhan's weak convergence of Markov chains to diffusion processes, which are of independent interest.
This paper aims to study the global dynamics of nonconvex statistical optimization based on diffusion processes. As an example of non-convex problems, this paper discusses in details the SGD applied on the tensor decomposition formulation of independent component analysis (ICA). An interesting finding in this paper is a three-phases phenomenon of the global dynamics of SGD to capture the transition of SGD solution from unstable initialization to finally stable local minimum. Overall, this paper is well written and it addresses a very challenge problem. This paper serves as a first step in the theoretical understanding of global dynamics of SGD, and is believed to stimulate many work on the global dynamic of non-convex optimizations.   
This paper aims to study the global dynamics of nonconvex statistical optimization based on diffusion processes. As an example of non-convex problems, this paper discusses in details the SGD applied on the tensor decomposition formulation of independent component analysis (ICA). An interesting finding in this paper is a three-phases phenomenon of the global dynamics of SGD to capture the transition of SGD solution from unstable initialization to finally stable local minimum. Overall, this paper is well written and it addresses a very challenge problem. This paper serves as a first step in the theoretical understanding of global dynamics of SGD, and is believed to stimulate many work on the global dynamic of non-convex optimizations.    Q1: Discuss how to generalize it other non-convex models? As a concrete example, this paper only discussed SGD for ICA. Can the authors briefly discuss how to apply their framework to other non-convex optimization problems?  Q2: discuss the relationship to a series of literature which also provides global rate of convergence of non-convex optimzation problems. e.g.   (1) Zhang et al. (2014), Spectral Methods meet EM: A Provably Optimal Algorithm for Crowdsourcing (2) Anandkumar, A., Ge, R. and Janzamin, M. (2014), Guaranteed non-orthogonal tensor decomposition via alternating rank-1 updates. (3) Sun et. al. (2016), Provable sparse tensor decomposition.  Q3: Assumptions: In (iii) of Assumption 1, Y_i is assumed to have up to 8-th moment, i.e., k = 1,2,...,8. However, in Proposition 2, it requires the assumption for k = 1, 2,...,d, where d is the dimension of X. Can the authors discuss in details why such condition is required? When d diverges, is this condition strong?  Q4: Please further polish the paper. Below are some examples of typos:  (1)line 118. ``Y_1,\ldots,Y_n" should be X_1,\ldots,X_n. (2)line 123: ``...whose the number linearly grows... (3)line 139: ``...the well-known coupon collector problem [18] it takes..." (4)line 146: ``To work on the approximation we first conclude the following". This is not a complete setence.