Low-rank gradient flow - a first order algorithm for non-convex optimization

University Of Maryland Baltimore County, Baltimore MD

Investigators

Abstract

Non-convex optimization problems are ubiquitous in science and engineering. They often present significant challenges for many existing classes of algorithms due to the presence of multiple suboptimal, undesirable solutions. The methods emerging from this project will circumvent some of these challenges due to their ability of bypassing more efficiently suboptimal solutions using a novel set of techniques. They will contribute to the numerical solution of non-convex optimization problems that can be found in a very wide range of applications, such as computer-aided design (shape and topology optimization), radiation therapy, optimization of manufacturing processes, inverse problems, optimal control of partial differential equations, statistics, and artificial intelligence. Open software will be shared with the community in order to facilitate the reproducibility of the results. One summer undergraduate student and one graduate student will benefit from training in areas that are relevant to topics of current interest to both academia and industry. Special attention will be given to the recruitment of students from underrepresented groups. The project is centered around developing and analyzing a novel class of first order methods for solving optimization problems, called low-rank-gradient-flow (LRGF). The idea behind the method consists of developing, at each step, quadratic surrogates with low-rank Hessian, and computing analytically the gradient flow on that surrogate. The step will conclude with a line search along the curvilinear gradient flow, with the purpose of finding a point satisfying the Wolfe conditions. Convergence will be accelerated using a multilevel approach based on reduced order models. The convergence properties of the method will be studied, addressing both questions related to global convergence, efficient construction of low-rank models, as well as convergence rates. The method will be applied to maximum likelihood estimation, optimization of hyperbolic partial differential equations, and training of deep neural networks. 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.