Scalable Nonconvex Optimization Algorithms

Modern statistical problems often involve minimizing objective functions that are not necessarily convex or smooth. In this study, we devote to developing scalable algorithms for nonconvex optimization with statistical guarantees. We first investigate a broad surrogate framework defined by generalized Bregman divergence functions for developing scalable algorithms. Local linear approximation, mirror descent, iterative thresholding, and DC programming can all be viewed as particular instances. The Bregman re-characterization enables us to choose suitable measures of computational error to establish global convergence rate results even for nonconvex problems in high-dimensional settings. Moreover, under some regularity conditions, the sequence of iterates in Bregman surrogate optimization can be shown to approach the statistical truth within the desired accuracy geometrically fast. The algorithms can be accelerated with a careful control of relaxation and stepsize parameters. Simulation studies are performed to support the theoretical results. An important applications of nonconvex optimization is robust estimation. Outliers widely occur in big-data and high-dimensional applications and may severely affect statistical estimation and inference. A framework of outlier-resistant estimation is introduced to robustify an arbitrarily given loss function. It has a close connection to the method of trimming but explicitly includes outlyingness parameters for all samples, which greatly facilitates computation, theory, and parameter tuning. To address the issues of nonconvexity and nonsmoothness, we develop scalable algorithms with implementation ease and guaranteed fast convergence. In particular, we introduce a new means to alleviate the requirement on the initial value such that on regular datasets the number of data resamplings can be substantially reduced. Moreover, based on combined statistical and computational treatments, we are able to develop new tools for nonasymptotic robust analysis regarding a general loss. The obtained estimators, though not necessarily globally or even locally optimal, enjoy minimax rate optimality in both low dimensions and high dimensions. Experiments in regression, classification, and neural networks show excellent performance of the proposed methodology in robust parameter estimation and variable selection.