FAST RATE ANALYSIS OF STOCHASTIC OPTIMIZATION IN STATISTICAL ESTIMATION

Abstract

The interplay of optimization and machine learning becomes an important part of modern artificial intelligence. On one hand, a lot of machine learning problem can be formulated into the optimization problem, and then in the training phase, parameters in these models are tuned using optimization algorithm. Optimization approaches have enjoyed prominence in machine learning because of their wide applicability and attractive theoretical properties. On the other hand, the increasing complexity of machine learning model and big data era push modern optimization algorithms to a higher level. Our study focuses on the stochastic first order method for the high dimensional statistics model. In particular, we investigate the convex stochastic optimization problem and propose the modified regret to relax the strong convexity assumption in some well-known algorithms. We then extend this to solve the large scale robust optimization problem. At last, we study the finite-sum problem, which covers several important formulations such as Lasso, group Lasso, logistic regression, and some non-convex models such as linear regression with SCAD regularization. We show that three variance reduced randomized first order methods enjoy the fast linear convergence even in the non-convex setting under the assumption of restricted strong convexity.