Randomized Numerical Linear Algebra for Optimization
Abstract
Approved for Public ReleaseAdvances in randomized numerical linear algebra (randNLA) in the new millenium have reduced the complexity of a variety of fundamental linear algebraic operations, including finding the top-k eigenspace or principal components of a matrix or solving a large-scale linear system of equations. These advances have implications throughout optimization that have not yet been fully realized. This proposal reviews some of the most important and useful tools in randomized numerical linear algebra, presents some preliminary work on their use in optimization, and points the way towards major breakthroughs in statistical learning, interior point methods, and deep learning that we believe will be possible with these methods. The major technique is to approximate the most computationally challenging step in an optimization algorithm as the solution to a linear system Ax = b; and to approximate thematrix A by a matrix that is low rank + diagonal in order to efficiently solve or precondition an indirect solver for the linear system.We propose three major research directions to fundamentally improve the scale, speed, and robustness of solvers for many of themost important classes of optimization problems:1.statistical learning,2.smooth optimization and interior point methods, and3.stochastic optimization and deep learning.Preliminary work from the PIs lab shows that these techniques yield 3 58 x speedups on important machine learning problems like lasso, logistic regression, SVM, and deep learning. RandNLA has the potential to accelerate the solution of a wide variety of problems in statistical learning and artificial intelligence. This proposal directly supports the Navys mission to maintain decision superiority by efficiently processing large and complex datasets to produce actionable insights and decisions.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- May 15, 2024
- Source ID
- N000142412306
Entities
People
- Madeleine Udell
Organizations
- Office of Naval Research
- Stanford University
- United States Navy