Randomized Numerical Linear Algebra for Large-Scale Learning and Inference
Abstract
The overarching aim of this project is to transform and extend the foundations of Randomized Numerical Linear Algebra (RandNLA) theory by addressing the following tension: first, by extending the foundations of RandNLA by tailoring randomization directly towards downstream end goals provided by the underlying signal processing and machine learning problems, rather than intermediate matrix approximation goals; and second, by using the statisticaland optimization insights obtained from these applications to transform and extend the foundations of RandNLA. Throughout, we will explicitly take into account additional structure in the problem, which will also include both implicitand explicit statistical effects. Central to our proposed work is that two complementary aspects of RandNLA are its use for speeding up NLA computations and its use for improved ML and data analysis. We emphasize three key ideas in the project: Matrix Approximations via Column Sampling, Preconditioning with Random Projections, and Compressive Sensing. The expertise of our team spans applied mathematics, statistics, signal processing, machine learning, and theory of computer science. As such, we are able to bring together a broad set of tools to advance the foundations of RandNLA. We organize the project around three general research directions. In Thrust 1: Exploring Scalability-Statistical Tradeoffs in RandNLA, we will study the interactions between RandNLA and the statistical properties of the overall data analysis pipeline it is used in. More specifically, we will consider trading off resources like amount of computation, amount of compression, and amount of memory with the statistical performance of the algorithms. In Thrust 2: Exploring Real-Time RandNLA Theory and Practice, we will depart from traditional RandNLA techniques that assume static matrices observed in their entirety, because one does not have this luxury in several applications of DoD interest. More specifically, we will develop RandNLA techniques that are provably sub-linear for temporally sensitive problems such as tracking, dynamic detection, and data streaming. In Thrust 3: Exploring RandNLA for Large-Scale Optimization, we will explore new facets of the interaction between RandNLA and large-scale optimization problems, which are common in applications of DoD interest. We will investigate novel techniques for improving the convergence speed of stochastic gradient descent by leveraging RandNLA techniques for adaptive sampling. We will also investigate the ability of RandNLA algorithms to perform implicit regularization for large-scale optimization problems, yielding more stable and meaningful solutions.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Jul 26, 2018
- Source ID
- N000141812571
Entities
People
- Richard G. Baraniuk
Organizations
- Office of Naval Research
- Rice University
- United States Navy