Thesis Title:

Accelerated Inexact First-Order Methods for Solving Nonconvex Composite Optimization Problems

Advisor:

Dr. Renato D.C. Monteiro, School of Industrial and Systems Engineering, Georgia Tech

Committee Members:

Dr. Arkadi Nemirovski, School of Industrial and Systems Engineering, Georgia Tech

Dr. Guanghui Lan, School of Industrial and Systems Engineering, Georgia Tech

Dr. Santanu S. Dey, School of Industrial and Systems Engineering, Georgia Tech

Dr. Edmond Chow, School of Computational Science and Engineering, Georgia Tech

Date and Time:

Friday, April 2, 2021 @ 1:30pm (EST)

Meeting URL (BlueJeans):

https://bluejeans.com/713499256

Meeting ID (BlueJeans):

713 499 256

Abstract:

This thesis focuses on developing and analyzing accelerated and inexact first-order methods for solving or finding stationary points of various nonconvex composite optimization (NCO) problems. Our main tools mainly come from variational and convex analysis, and our key results are in the form of iteration complexity bounds and how these bounds compare to other ones in the literature.

Our first study problem is the classic unconstrained NCO problem studied by Mine and Fukushima (1981), and we develop an accelerated inexact proximal point method for finding approximate stationary points of it. By analyzing the method's variational properties, we establish an iteration complexity bound that is optimal in the number of first-order oracle evaluations. As an additional result, we show that our accelerated method and the classic composite/proximal gradient method are instances of a general inexact proximal point framework under different stepsizes and levels of inexactness.

Following our developments for the unconstrained setting, we move to study two instances of a function-constrained NCO problem. The first instance comprises a set of linear set constraints, and we develop a quadratic penalty method for finding approximate stationary points of it. We then establish an iteration complexity bound that is several orders of magnitude better than the previous state-of-the-art bound. As part of the analysis, we show that one can start the method from any point where the objective function is finite (and not necessarily from a near feasible point) and that no regularity conditions are needed to obtain convergence. The second instance consists of a set of nonlinear cone constraints, and we develop a proximal inexact augmented Lagrangian method for finding approximate stationary points of it. We then establish a competitive iteration complexity bound under an easily verifiable Slater-like condition. As part of the analysis, we show that the Lagrange multipliers generated by the method are bounded, without needing to dampen the (dual) multiplier update, and, like in the penalty method, the initial point can be any point where the objective function is finite.

Before moving on to other problems, we discuss some efficient implementation strategies of the above methods. In particular, we present some efficient line search subroutines, an adaptive stepsize selection scheme, an efficient warm-start strategy, and a discussion about how to relax some algorithms' convexity assumptions. We also present a large number of real-world applications and numerical experiments that highlight our methods' performance against other modern solvers.

Our second-to-last study problem is a class of nonconvex-concave min-max NCO problems, and we develop an accelerated smoothing method for finding two kinds of approximate stationary points of it. Using prior results from our study of the unconstrained NCO problem, we establish iteration bounds that substantially improve on similar ones in the literature. Additionally, we give a brief discussion about how to generalize our smoothing method to solve linearly constrained min-max NCO problems. We then end with some numerical experiments in the unconstrained setting to validate the efficacy of our approach.

Our final study problems are a popular class of spectral NCO problems in which the inputs are general m-by-n real-valued matrices. As part of the study, we develop two inexact composite gradient methods — one based on the classic composite/proximal gradient method and another based on an accelerated variant of it — to find approximate stationary points. Extending some techniques for analyzing accelerated methods, we show that the accelerated variant obtains a competitive convergence rate in the nonconvex setting and an accelerated convergence rate in the convex setting. A vital conclusion of the study is that we show the methods perform nearly all of their iterations over the space of min{m,n}-by-1 vectors rather than the space of m-by-n matrices. We then end with some numerical experiments to show the effectiveness of the previous conclusion.