Nonconvex Optimization Methods: Iteration Complexity And Applications

Abstract

Nowadays, optimization algorithms have become an essential tool for a large variety of applications in many fields. Despite the hardness of nonconvexity, a large number of these applications are dealing with nonconvex optimization problems. In this thesis, we shall focus on several different aspects of nonconvex optimization algorithms and their complexity results, including the Riemannian optimization methods for solving manifold constrained problems, and variance reduced cubic regularized Newton's method for computing second-order solution for empirical risk minimization problems. In the end, we include an application of such methods for the problem of community detection.