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

由于可用于商业、科学和安全应用的数据量不断增加，使用每个输入数据一次(单次通过)或少量扫描输入(多次通过)的流传输算法正变得越来越重要。执行大规模数据分析和机器学习通常需要处理数值线性代数基元，如最小二乘回归、奇异值分解、最小绝对偏差回归和典型相关分析。在这项建议中，PI旨在显著改进这些基本线性代数内核的流算法的理论和实践。新算法将为无处不在的大数据应用程序提供更快、更准确的内核，减少机器学习应用程序的资源消耗(硬件和能源)，并将使关键依赖准确性的安全应用程序可以被证明是可信的。此外，它们将改进物理、化学和生物医学应用中的数据开发。将考虑的计算要么使用不精确的增量单遍算法，要么使用昂贵的多遍算法。尽管现有的不精确算法在实践中往往工作得足够好，但依赖于这些构建块的应用程序的最坏情况还没有得到表征。这在安全和异常检测领域尤其令人担忧，在这些领域，可以想象恶意方可以利用这种不准确。PI将为数值线性代数开发一套可证明准确的单次通过算法。他们还将探索替代算法路线，主要是多通道随机算法，既用于核心问题(最小二乘回归和奇异值分解)，也用于更具挑战性的问题(最小绝对偏差回归和典型相关性)。它们将描述与这些计算相关的精度/性能权衡，其中性能主要指通过次数，但也指总计算工作量(包括通信)。PI将使用来自重要应用的基准以及单次通过算法的理论下限来进行这项调查。

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.