NSF-BSF: AF: Collaborative Research: Small: Randomized preconditioning of iterative processes: Theory and practice

North Carolina State University, Raleigh NC

Investigators

Abstract

A simple way to predict the long-term movement of your stock portfolio is to graph the daily prices tracked over the past several months, and then fit a line through the graph. The slope of the line can help to predict whether the trend is for prices to increase or to decrease. This is the most basic version of a so-called `regression problem'. Regression problems, in more sophisticated forms, are mainstays in a multitude of areas, including finance, statistics, science, genetics, and engineering; and their fast solution is a must when it comes to timely diagnoses and prediction of events. The project aims to speed up the solution of regression problems through accelerators (called 'preconditioners'). The accelerators are set up very fast, by picking and choosing a few pieces at 'random' from the original problem: Think of throwing dice to determine what to pick next. Although this may sound haphazard, it is efficient because regression problems tend to have a lot of redundancy and repetition, making it difficult to miss an important piece. In addition, this is a safe way of accelerating regression problems: On the off-chance that the randomization should produce somewhat inefficient accelerators, we are still ok: The accelerator is slower, but we are still solving the original problem --just not quite as fast as expected. The project involves the design and analysis of accelerators for speeding up regression problems in a variety of practical settings, with particular attention to human genetics. Linear least squares/regression problems are of primary importance in many computational sciences, either standalone on their own or as part of a sequence in the outer iterations of an optimization method. The project involves accelerating the solution of regression problems via `dynamic' randomized preconditioners that can either change across inner iterations of a solver or else change across least squares problems in outer iterations of an optimization method. Specific optimization methods to be investigated include: (i) iteratively reweighted least squares for solving generalized linear models; (ii) interior point methods for linear programs; (iii) nonlinear least squares for training overparameterized neural networks; and (iv) high-order order orthogonal iteration for computing low-rank tensor decompositions. The project will impact many domains and pay particular attention to human genetics. The effectiveness of the methods will be validated on standard test suites, as well as large-scale matrices from the UK Biobank dataset. 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.