Recovering low-rank structures via eigenvector perturbation analysis is a common problem in statistical machine learning, such as in factor analysis, community detection, ranking, matrix completion, among others. While a large variety of results provide tight bounds on the average errors between empirical and population statistics of eigenvectors, fewer results are tight for entrywise analyses, which are critical for a number of problems such as community detection and ranking.

Nonconvex reformulations via low-rank factorization for stochastic convex semidefinite optimization problem have attracted arising attention due to their empirical efficiency and scalability. Compared with the original convex formulations, the nonconvex ones typically involve much fewer variables, allowing them to scale to scenarios with millions of variables. However, it opens a new challenge that under what conditions the nonconvex stochastic algorithms may find the population minimizer within the optimal statistical precision despite their empirical success in applications. In this paper, we provide an answer that the stochastic gradient descent (SGD) method can be adapted to solve the nonconvex reformulation of the original convex problem, with a global linear convergence when using a fixed step size, i.e., converging exponentially fast to the population minimizer within an optimal statistical precision in the restricted strongly convex case. If a diminishing step size is adopted, the bad effect caused by the variance of gradients on the optimization error can be eliminated but the rate is dropped to be sublinear. The core of our treatment relies on a novel second-order descent lemma, which is more general than the existing best result in the literature and improves the analysis on both online and batch algorithms. The developed theoretical results and effectiveness of the suggested SGD are also verified by a series of experiments.

In this paper, we develop an alternating direction method of multipliers (ADMM) for deep neural networks training with sigmoid-type activation functions (called sigmoid-ADMM pair ), mainly motivated by the gradient-free nature of ADMM in avoiding the saturation of sigmoid-type activations and the advantages of deep neural networks with sigmoid-type activations (called deep sigmoid nets) over their rectified linear unit (ReLU) counterparts (called deep ReLU nets) in terms of approximation. In particular, we prove that the approximation capability of deep sigmoid nets is not worse than that of deep ReLU nets by showing that ReLU activation function can be well approximated by deep sigmoid nets with two hidden layers and finitely many free parameters but not vice-verse. We also establish the global convergence of the proposed ADMM for the nonlinearly constrained formulation of the deep sigmoid nets training from arbitrary initial points to a Karush-Kuhn-Tucker (KKT) point at a rate of order O(1/k). Besides sigmoid activation, such a convergence theorem holds for a general class of smooth activations. Compared with the widely used stochastic gradient descent (SGD) algorithm for the deep ReLU nets training (called ReLU-SGD pair), the proposed sigmoid-ADMM pair is practically stable with respect to the algorithmic hyperparameters including the learning rate, initial schemes and the pro-processing of the input data. Moreover, we find that to approximate and learn simple but important functions the proposed sigmoid-ADMM pair numerically outperforms the ReLU-SGD pair.

No abstract uploaded!

We formulate the Riemannian calculus of the probability set embedded with L^2-Wasserstein metric. This is an initial work of transport information geometry. Our investigation starts with the probability simplex (probability manifold) supported on vertices of a finite graph. The main idea is to embed the probability manifold as a submanifold of the positive measure space with a nonlinear metric tensor. Here the nonlinearity comes from the linear weighted Laplacian operator. By this viewpoint, we establish torsion-free Christoffel symbols, Levi-Civita connections, curvature tensors, and volume forms in the probability manifold by Euclidean coordinates. As a consequence, the Jacobi equation, Laplace-Beltrami and Hessian operators on the probability manifold are derived. These geometric computations are also provided in the infinite-dimensional density space (density manifold) supported on a finite-dimensional manifold. In particular, an identity is given connecting the Baker-{É}mery Γ2 operator (carr{é} du champ it{é}r{é}) by connecting Fisher-Rao information metric and optimal transport metric. Several examples are demonstrated.