Collaborative Research: Robust Acceleration and Preconditioning Methods for Data-Related Applications: Theory and Practice

在许多科学和工程学科中，人们经常遇到数字、向量或其他数学对象的序列。在这些情况下，一个共同的目标是以较低的成本获得序列的极限。作为一个简单的例子，有几种方法可以生成收敛到数字pi的数字序列，并且某些序列将相当快地达到极限pi。在某些情况下，可以修改生成序列的原始方法，以获得更快的收敛速度。然而，这并不总是可能的或成本效益高的，因为产生序列的过程不明确，或者对这种方法来说可能过于繁琐而不实用。另一种常见的解决方案是通过“加速”来改变序列。这通常需要组合序列的术语，以更快地产生达到限制的新条目。到目前为止，加速方法是由数学家和(量子)物理学家开发出来的，用于处理物理科学中的一系列问题。这个项目的主要目标是研究这种加速方法，并通过专注于与机器学习以及更广泛的数据科学相关的主题来使它们适应现代。这个由埃默里大学和明尼苏达大学的研究人员合作的研究项目，将从理论上开发和研究一些稳健的加速算法，重点是源于数据相关应用的问题，以及培训这一研究领域的研究生。加速各种类型的数字序列的需要经常被广泛的学科所感受到，这一点已经被许多研究人员解决了很长一段时间。在过去，这种加速或外推方案主要针对从物理模拟产生的矢量序列，例如，由量子物理中的自洽场(SCF)迭代生成的势序列。近年来，机器学习方法在各种学科中的快速扩展产生了对加速各种类型序列的算法的新需求。然而，在这些应用中遇到的新类型的序列在根本上不同于它们在物理模拟中的类似物。与例如量子物理中所需的常见设置相比，机器学习中的计算通常以单精度或半精度而不是双精度来执行。此外，在神经网络中，这些序列往往是非常不规则的，因为它们来自随机梯度方法。来自埃默里大学和明尼苏达大学的合作团队将从理论上开发和研究一些稳健的加速算法，重点是它们在不规则序列中的应用，例如在数据相关应用中遇到的那些。调查小组将研究一些改进标准加速方案的健壮性的策略，如安德森混合或epsilon算法。最近提出的一些基于(所谓的)动量思想的二阶方法已被证明对加速深度学习中的标准随机梯度下降方法有很大的帮助。调查人员将在这些方案中增加另一种基于切比雪夫加速的同类方法。切比雪夫格式的一个优点是，它在理论上很容易研究，部分原因是它很容易被理解为线性问题。在第二个研究方向，调查团队将在机器学习任务的特定背景下研究加速方法。例如，受参数平均和方差减少方案的最新进展的启发，他们将探索将经典外推方法应用于随机梯度序列作为自适应外推过程。实验表明，参数平均是加速过程成功的关键。同样重要的是选择要加速的载体。同样，将为被低精度算法阻碍的序列设计和研究稳健的加速方案。这一奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

In many disciplines of science and engineering one often encounters sequences of numbers or vectors or other mathematical objects. A common goal in these situations is to obtain the limit of the sequence inexpensively. As a simple example, there are several ways to generate a sequence of numbers that converge to the number pi and some sequences will reach the limit pi rather quickly. In some cases, it may be possible to modify the original method that produced the sequence to obtain a faster converging one. However, this is not always possible or cost-effective because the process by which the sequence is produced is not explicit or it may be too cumbersome for this approach to be practical. Another common solution is to transform the sequence, by 'accelerating it'. This usually entails combining the terms of the sequence to produce new entries that reach the limit faster. So far, acceleration methods were developed by mathematicians and (quantum) physicists to deal with a wide range of problems from the physical sciences. The primary goal of this project is to study such acceleration methods and to adapt them to the modern era by focusing on topics related to machine learning and, more generally, data sciences. This collaborative research project between researchers at Emory University and the University of Minnesota, will develop and study theoretically a number of robust acceleration algorithms with an emphasis on problems that stem from data-related applications, as well as train graduate students in this field of study. The need to accelerate numerical sequences of various types has frequently been felt across a wide range of disciplines and it has been addressed by many researchers for quite some time. In the past, such acceleration or extrapolation schemes were targeted mainly toward sequences of vectors that arise from physical simulations, e.g., the sequence of potentials generated by the Self Consistent Field (SCF) iterations in quantum physics. In recent years, the rapid expansion of machine learning methodologies across a great variety of disciplines has generated new demand for algorithms to accelerate sequences of various types. However, the new type of sequences encountered in these applications differ in fundamental ways from their analogues in physical simulations. In contrast with the common setting required in, e.g., quantum physics, calculations in machine learning are often performed in single or half precision instead of double precision. Furthermore, in neural networks these sequences tend to be very irregular because they originate from stochastic gradient approaches. The collaborative team from Emory University and the University of Minnesota, will develop and study theoretically a number of robust acceleration algorithms with an emphasis on their application to irregular sequences such as those encountered in data-related applications. The investigating team will study a number of strategies for improving the robustness of standard acceleration schemes, such as Anderson mixing, or the epsilon algorithm. A number of recently advocated second-order methods, based on (so-called) momentum ideas, have been shown to be of great help in accelerating standard stochastic gradient descent methods in Deep Learning. The investigators will add to these schemes another method of the same class that is grounded in Chebyshev acceleration. One advantage of the Chebyshev-based scheme is that it is fairly easy to study theoretically in part because it is well understood for linear problems. In a second research direction, the investigating team will study acceleration methods in the specific context of machine learning tasks. For example, inspired by recent advances in parameter averaging and variance reduction schemes they will explore the application of classical extrapolation methods to stochastic gradient sequences as an adaptive extrapolation procedure. Experiments show that parameter averaging is key to the success of acceleration procedures. Just as important is the selection of the vectors to accelerate. Along the same lines, robust acceleration schemes will be designed and studied for sequences hampered by low precision arithmetic.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.