Efficient Algorithms for Statistical Estimation

Abstract

Statistical estimation aims to find parameters or structures relating to an underlying distribution given empirical samples. Many statistical estimation problems are information theoretically solvable, but are not fully understood computationally if time or space resources are limited. In many cases, these estimation problems require solving complex optimization problem with constraints which are algorithmically hard. In other cases, even if these estimation methods offer an explicit formula to compute, under some big data settings we still can not afford to compute it directly. In addition there are other computational considerations such as the robustness of the estimator. In all these cases, we need to rethink the problem and redesign our estimation algorithms. Sometimes the efficient estimation algorithm ends up very different from the standard statistical method.

In this thesis we present three different examples of statistical estimation problems: noisy graph matching, l2 norm tracking and mean/covariance estimation for heavy tail distributions. All of them originate from standard and well-studied statistical problems. In addition, for each of them, there are various applications in different fields. However, these statistical estimation problems are not fully understood. We will consider each of the problems from both the perspectives of statistics and computation, and demonstrate progress on efficiently solving these problems in certain scenarios.