Solving structured nonconvex problems in statistical learning
Nonconvex problems arise frequently in modern applied statistics and machine learning, posing outstanding challenges from a computational and statistical viewpoint. Continuous especially convex optimization, has played a key role in our computational understanding of (relaxations or approximations of) these problems. However, some other well-grounded techniques in mathematical optimization (for example, mixed integer optimization) have not been explored to their fullest potential; despite significant advances in this field over the past several years. I will demonstrate how such techniques can be used to obtain (certifiably) near-optimal solutions to machine learning tasks that can be expressed as structured nonconvex optimization problems. Our running example will be high dimensional sparse linear regression, where, such methods seem to be promising for instances with up to a million features --- much larger than what is usually considered computationally feasible. I will also outline instances in structured sparsity, robust statistics, nonparametric function estimation and low-rank factor analysis where such techniques seem to be promising.