 Main
Structured Estimation In HighDimensions
 Negahban, Sahand N.
 Advisor(s): Wainwright, Martin J
Abstract
Highdimensional statistical inference deals with models in which the number of parameters $p$ is comparable to or larger than the sample size $n$. Since it is usually impossible to obtain consistent procedures unless $p/n \to 0$, a line of recent work has studied models with various types of lowdimensional structure, including sparse vectors, sparse and structured matrices, lowrank matrices, and combinations thereof. Such structure arises in problems found in compressed sensing, sparse graphical model estimation, and matrix completion. In such settings, a general approach to estimation is to
solve a regularized optimization problem, which combines a loss function measuring how well the model fits the data with some regularization function that encourages the assumed structure. We will present a unified framework for establishing consistency and convergence rates for such regularized $M$estimators under highdimensional scaling. We will then show how this framework can be utilized to rederive a few existing results and also to obtain a number of new results on consistency and convergence rates, in both $\ell_2$error and related norms.
An equally important consideration is the computational efficiency in performing inference in the highdimensional setting. This highdimensional structure precludes the usual global assumptionsnamely, strong convexity and smoothness conditionsthat underlie much of classical optimization analysis. We will discuss ties between the statistical inference problem itself and efficient computational methods for performing the estimation. In particular, we will show that the same underlying statistical structure can be exploited to prove global geometric convergence of the gradient descent procedure up to \emph{statistical accuracy}. This analysis reveals interesting connections between statistical precision and computational efficiency in highdimensional estimation.
Main Content
Enter the password to open this PDF file:













