AF: RI: Small: Computationally Efficient Approximation of Stationary Points in Convex and Min-Max Optimization

University Of Wisconsin-Madison, Madison WI

Investigators

Abstract

Optimization permeates almost every aspect of life, from natural selection and evolution to technological and economic development. Within modern data science, optimization algorithms are the core engine for finding patterns in the data, creating models that explain and mimic them, and making predictions. The primary goal of this project is to advance the theoretical foundations of optimization and leverage the obtained insights to develop new algorithms that are broadly applicable, adaptive to different data models, and scalable, so that they can be applied to the ever-more ambitious data-science applications. One of the guiding principles for the development of theoretical frameworks in this project are parallels between optimization algorithms and laws, such as the principle of least action, governing the behavior of physical systems. More concretely, the goal of this project is to further the understanding of how fast it is possible for optimization algorithms to converge to stationary points, defined as the points with small gradient norms. In convex optimization, one of the most fundamental facts is that every stationary point is also a global function minimum. However, the problem of efficiently computing near-stationary points is quite different from the problem of efficiently approximating the function minima, and methods that exhibit optimal convergence rates under one of the criteria do not in general exhibit optimal convergence rates under both. In particular, Nesterov’s accelerated gradient method is iteration-complexity-optimal in terms of minimizing smooth (gradient-Lipschitz) convex functions, but suboptimal in terms of finding their near-stationary points. While the complexity of minimizing convex functions is well-understood, much less is known about the complexity of finding near-stationary points. This troubling gap in understanding causes severe algorithmic limitations not only for general-purpose optimization algorithms, but also in a number of application areas. The primary focus of this project is to close this gap by developing a general framework for the analysis of convergence to stationary points in convex optimization and its generalizations, leveraging technical tools from dynamical systems, monotone-operator theory, and fixed-point theory. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.