Gradient based methods for nonconvex optimization: a dynamical systems viewpoint
Creators: name: Dixit, Rishabh
Publisher: name: No Publisher Supplied
Year: 2024

description: Many data-driven problems in the modern world involve solving optimization problems. The large-scale nature of many of these problems also necessitates the use of first-order optimization methods, i.e., methods that rely only on the gradient information, for computational purposes. Due to their relatively lower computational complexity, gradient-related first-order methods have become the workhorse of large-scale numerical optimization problems. Many of these problems involve nonconvex objective functions with multiple saddle points, which necessitates an understanding of the behavior of discrete trajectories of first-order methods within the geometrical landscape of these functions. While plethora of literature exists for convex optimization problems, understanding the nonconvex optimization landscape is still in its nascent stages. The main challenge associated with nonconvex optimization is the landscape of the function which poses considerable complexity. This complication stems from the possibility of convergence to strict saddle points which are the first order stationary points with negative curvature. Since saddle points are first order stationary any first-order optimization methods, which include the prototypical gradient descent algorithm, face a major hurdle for nonconvex optimization: since the gradient of a function vanishes at a saddle point, first-order methods can potentially get stuck at the saddle points of the objective function. And while recent works have established that the gradient descent algorithm almost surely escapes the saddle points under some mild conditions, there remains a concern that first-order methods can spend an inordinate amount of time in the saddle neighborhoods. It is in this regard that the first part of this thesis revisits the behavior of the gradient descent trajectories within the saddle neighborhoods and answers the question of whether it is possible to provide necessary and sufficient conditions under which these trajectories escape the saddle neighborhoods in linear time. The ensuing analysis relies on precise approximations of the discrete gradient descent trajectories in terms of the spectrum of the Hessian at the saddle point, and it leads to a simple boundary condition that can be readily checked to ensure the gradient descent method escapes the saddle neighborhoods of a class of nonconvex functions in linear time. The theory behind fast saddle escape is corroborated by numerical tests on the nonconvex phase retrieval problem. The boundary condition check also leads to the development of a simple variant of the vanilla gradient descent method, termed Curvature Conditioned Regularized Gradient Descent (CCRGD). This algorithm is designed for saddle escape exponentially fast, where the algorithm runs vanilla gradient descent (GD) iterations at its core and by sensing the local curvature of the nonconvex function, makes a decision to do a course correction of its trajectory for faster escape, in case it is near a strict saddle point. The CCRGD algorithm outperforms GD on the Rastrigin function which is a test function for optimization and also converges to a local minimum of the low rank matrix factorization problem. Finally a convergence analysis of the CCRGD algorithm is provided, which includes its rate of convergence to a local minimum of a class of nonconvex optimization problems. The second part of this thesis develops a rigorous analysis for a class of Nesterov accelerated gradient (NAG) type methods for smooth nonconvex functions so as to better understand the interplay between the momentum and saddle escape-local convergence tradeoffs arising in such accelerated methods. To succinctly elucidate, a robust proof technique involving Banach space theory is first developed establishing the almost sure non-convergence guarantee of these accelerated methods to strict saddle points. Next, two novel metrics are proposed that evaluate the asymptotic speeds of these methods in proximity to critical points of nonconvex functions. Thereafter, a theoretical framework is constructed that delves into the behavior of these methods’ trajectories around strict saddle points, examining them through a dynamical systems perspective. This leads us to discern vital properties, like the duration required to exit strict saddle neighborhoods and the trajectory’s entry angle into such neighborhoods – both pivotal for ensuring a fast escape. Furthermore, a subset of accelerated methods are studied that not only converge at near-optimal rates within the convex neighborhoods of nonconvex functions to a local minimum but also outperform the NAG in terms of saddle-point evasion. Finally, the theoretical insights are corroborated by numerical tests conducted on the phase retrieval problem.