12/18/2015

Post date: Jan 20, 2016 4:02:28 AM

Title: Nonconvex Statistical Optimization: Algorithm and Model-based Optimization Theory

Speaker: Tuo Zhao, PhD candidate, Department of Computer Science, Johns Hopkins University

[Abstract] Nonconvex regularized M-estimators have been widely applied to high dimensional data analysis. Existing statistical theory has established their statistical properties in high dimensions only when the global optimum or certain local optimum can be obtained. Though practitioners have proposed numerous heuristic computational algorithms for solving these nonconvex optimization problems, existing optimization theory does not necessarily guarantee these algorithms to obtain the global or local optima with desired statistical properties in polynomial time. Therefore, there exists a significant gap between theory and practice: What is actually computed is not the same as what has been proved.

To bridge this gap, we propose a new generation of nonconvex statistical optimization algorithms and model-based theory, which incorporate the statistical thinking into modern optimization. When developing computational algorithms, we take underlying sparse statistical models into consideration. Particularly, for nonconvex regularized M-estimation problems, our proposed algorithms devise three different optimization schemes, under which the solutions achieved by the optimization algorithm always falls within a restricted sparse set. Thus the nonconvex objective function mimics the behavior of a strongly convex function, which eventually allows our proposed algorithms to obtain an estimator with the desired optimal statistical properties in polynomial time with high probability.