Over the past decade there has been a dramatic shift in how large-scale optimization problems are tackled. Whether training sophisticated machine-learning models, finding patterns in massive data sets, or tuning parameters in recommendation systems, increasingly data scientists apply simple iterative methods to solve complex optimization problems. These popular methods, e.g. variants of gradient descent, often ignore problem structure in favor of requiring additional expensive resources of time, energy, and tuning. However, broad classes of structure often permeate modern optimization problems, whether it be network structure of popular machine-learning models, the sparsity of datasets, or the low-dimensional structure of learning problems. The primary goal of this project is to provide new mathematical and algorithmic tools to exploit broad classes of structure in fundamental and prevalent optimization problems. This project will develop new techniques for solving structured optimization problems, address long-standing theoretical questions in algorithm design, and provide varied research, educational, and outreach activities designed to make these techniques broadly accessible and easily applied. Ultimately, this project will lay the foundations for more efficient structured optimization and large-scale data analysis.
This project will focus on providing significant mathematical and algorithmic advances in the theory of optimization and the design of efficient algorithms for solving prominent structured optimization problems. The investigators will develop a broad set of general structure-aware algorithmic and mathematical techniques to obtain improved running times for pervasive optimization and machine-learning problems. The optimization problems considered in this project, including linear programming, stochastic optimization, linear system solving, nonconvex optimization and the optimization tools considered in this project, such as interior-point methods, nonlinear conjugate gradient, L-BFGS, etc., lie at the heart of some of the largest open problems in theoretical computer science, operations research, scientific computing, numerical analysis, and machine learning. Consequently, to achieve these results the PIs will combine techniques across this broad spectrum of algorithmically-minded communities and advance the state-of-the-art theory in convex analysis, spectral graph theory, iterative methods, and numerical analysis to ultimately attain a new robust toolkit for solving massive-scale structured optimization problems.
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.
