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.