On the Geometric Structure of Problems in Statistics and Optimization

Abstract

This thesis explores problems in optimization and statistics exhibiting a particular geometric structure.In particular, we propose to leverage such underlying structure to provide computationally efficient and statistically optimal approaches.

The first part of this manuscript is dedicated to optimization problems. In particular, semidefinite programs (SDPs) have been proposed for machine learning, control theory and theoretical computer science applications. Unfortunately, interior point methods typically used to solve SDPs suffer from scalability issue. Building on tools from optimization on Riemannian manifolds, we provide non deterministic convergence guarantees for a popular heuristic to solve SDPs.

Next, we propose a new type of quasi-Newton method. Traditional quasi-Newton methods propose an approximation of the Hessian that is either symmetric or satisfies several secant equations. Our approach satisfies approximately, more specifically in the least square sense, several secant equations while remaining symmetric. To the best of our knowledge, this is the first approach to satisfy, at least approximately, those two conditions.

The second part of this thesis adresses a statistical problem motivated by applications such as cryo-EM, computer vision and natural language processing. In particular, we consider the problem of estimating a cloud of points from numerous noisy

observations of that cloud after unknown rotations, and possibly reflections. We focus on a regime where the noise level is larger than the magnitude of the signal. We investigate this setting by addressing the following fundamental question: given an arbitrarily high level of noise on the measurements, how accurately can one hope to estimate the parameter? Within those limits, can we derive an estimator that is both computationally efficient and statistically optimal? As a mean to this end, we propose new bounds on the sensitivity of the Cholesky factorization.