BSF: 2014324: Streaming Algorithms for Fundamental Computations in Numerical Linear Algebra

International Computer Science Institute, Berkeley CA

Investigators

Abstract

Streaming algorithms that use every input datum once (single-pass) or scan the input a small number of times (multiple passes) are gaining importance due to the increasing volumes of data that are available for business, scientific, and security applications. Performing large-scale data analysis and machine learning often requires addressing numerical linear algebra primitives, such as least squares regression, singular value decompositions, least absolute deviations regression, and canonical correlation analysis. In this proposal, the PIs aim to improve significantly the theory and practice of streaming algorithms for these fundamental linear algebra kernels. The new algorithms will provide faster and more accurate kernels for the ubiquitous big data applications, reducing resource use (hardware and energy) of machine learning applications, and will make security applications that rely critically on accuracy provably trustworthy. In addition, they will enable improved exploitation of data in physical, chemical, and biomedical applications. The computations that will be considered are performed either using inexact incremental single-pass algorithms, or by expensive multi-pass algorithms. Although existing inexact algorithms often work well enough in practice, the worst-case behavior of applications relying on these building blocks has not been characterized. This is especially troubling in the security and anomaly-detection areas, where a malicious party could conceivably exploit such inexactness. The PIs will develop a set of provably-accurate single-pass algorithms for numerical linear algebra. They will also explore alternative algorithmic routes, mainly multi-pass randomized algorithms, both for the core problems (least squares regression regression and singular value decomposition) and for the more challenging ones (least absolute deviations regression and canonical correlations). They will characterize the accuracy/performance tradeoffs associated with these computations, where performance refers mostly to the number of passes but also to the total computational effort (including communication). The PIs will carry out this investigation using benchmarks from significant applications, as well as theoretical lower bounds on single-pass algorithms.