Leveraging as a Paradigm for Statistically Informed Large-Scale Computation

• Activity Number: 5
• Type: Invited
• Date/Time: Sunday, August 4, 2013 : 2:00 PM to 3:50 PM
• Sponsor: Biometrics Section
• Author(s): Michael W. Mahoney*+
• Companies: Stanford University
• Keywords: Leverage ; Least-squares ; Algorithms ; Lapack

Abstract

Statistical leverage has historically been used in regression diagnostics to flag outliers, but recently it has emerged as a design principle to obtain faster (both in theory and in practice) algorithms for large-scale matrix and regression problems. Interestingly, these algorithms work for arbitrary, i.e., worst-case, input, but implicitly they use traditional statistical ideas. As an example, by approximating or preconditioning to be uniform the leverage scores of an arbitrary tall matrix, we can obtain algorithms for very overconstrained least-squares approximation that beat Lapack subroutines in terms of clock time for arbitrary matrices of size as small as thousands by hundreds. This approach of using the empirical statistical structure of the input to obtain better algorithms for arbitrary large-scale problems, as well as statistical questions raised by this paradigm, will be discussed.