Statistical Inference Via Convex Optimization PDF Download

High dimensional statistical problems with matrix or tensor type data are ubiquitous in modern data analysis. In many applications, the dimension of the matrix or tensor is high and much bigger than the sample size and some structural assumptions are often imposed to ensure the problem is well-posed. One of the most popular structures in matrix and tensor data analysis is the low-rankness. In this thesis, we make contributions to the statistical inference and optimization in low-rank matrix and tensor data analysis from the following three aspects. First, first-order algorithms have been the workhorse in modern data analysis, including matrix and tensor problems, for their simplicity and efficiency. Second-order algorithms suffer from high computational costs and instability. The first part of the thesis explores the following question: can we develop provable efficient second-order algorithms for high-dimensional matrix and tensor problems with low-rank structures? We provide a positive answer to this question, where the key idea is to explore smooth Riemannian structures of the sets of low-rank matrices and tensors and the connection to the second-order Riemannian optimization methods. In particular, we demonstrate that for a large class of tensor-on-tensor regression problems, the Riemannian Gauss-Newton algorithm is computationally fast and achieves provable second-order convergence. We also discuss the case when the intrinsic rank of the parameter matrix/tensor is unknown and a natural rank overspecification is implemented. In the second part of the thesis, we explore an interesting question: is there any connection between different non-convex optimization approaches for solving the general low-rank matrix optimization? We find from a geometric point of view, the common non-convex factorization formulation has a close connection with the Riemannian formulation and there exists an equivalence between them. Moreover, we discover that two notable Riemannian formulations, i.e., formulations under Riemannian embedded and quotient geometries, are also closely related from a geometric point of view. In the final part of the thesis, we are dedicated to studying one intriguing phenomenon in high dimensional statistical problems, statistical and computational trade-offs, which refers to the commonly appearing gaps between the different signal-to-noise ratio thresholds that make the problem information-theoretically solvable or polynomial-time solvable. Here we focus on the statistical-computational trade-offs induced by tensor structures. We would provide rigorous evidence for the computational barriers to two important classes of problems: tensor clustering and tensor regression. We show these computational limits by the average-case reduction and restricted class of low-degree polynomials arguments.