CRII: AF: Optimization and sampling algorithms with provable generalization and runtime guarantees, with applications to deep learning

在训练深度学习和其他机器学习模型时，人们希望以这样一种方式进行训练，即训练模型的泛化误差，即训练模型被用来对未用于训练模型的“测试”数据集进行预测时的误差尽可能低。具有良好泛化特性的训练算法可以导致机器学习模型对数据集的变化更健壮，允许稳健的预测，并且当训练数据集可能不能完全代表种群数据集的多样性时，有助于减轻算法偏差。这样的算法还可以在分布式训练和在线学习等设置中产生更稳定的训练。在实际应用中，用来训练模型的优化算法的选择对模型的训练误差和泛化误差都有很大影响。遗憾的是，缺乏对泛化误差有可证明保证的优化算法。这使得设计能够同时实现快速运行时间和低泛化误差的算法变得困难。本项目的目的是设计新的算法来训练深度学习和其他机器学习模型，并证明这些算法在运行时间、泛化误差和相关的鲁棒性方面的保证。为了设计和分析这样的算法，这个项目汇集了数学和计算机科学的不同领域的想法。这个项目设计了新的优化和马尔可夫链采样算法，用于训练深度学习模型和其他机器学习模型。它的目的是证明这些算法的泛化误差保证和相关的健壮性，并提供快速运行时间保证。在深度学习中，保证较低的泛化误差尤其具有挑战性，因为可训练参数的数量往往比数据集的大小大得多，并且用于训练模型的损失函数是非凸的。为了证明更强的泛化和相关的健壮性保证，项目团队使用流形学习和微分几何的思想来对许多机器学习应用中出现的数据集的低维结构进行建模。该项目有三个组成部分。一个组成部分是设计和分析用于训练深度学习模型的新的优化算法。另一个组成部分是设计和分析多智能体优化问题的算法，例如训练生成性对手网(GANS)时出现的最小-最大优化问题，以及训练元学习模型时出现的多智能体优化问题。最后，除了优化算法，它还设计和分析了用于训练贝叶斯机器学习模型的马尔可夫链抽样算法和相关算法。这一奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

When training deep-learning and other machine-learning models, one would like to train in such a way that the generalization error of the trained model, that is, the error of the trained model when it is used to make predictions on a “test” dataset which was not used to train the model, is as low as possible. Training algorithms with good generalization properties can lead to machine-learning models that are more robust to changes in the dataset, allow for robust predictions, and help mitigate algorithmic bias when the training dataset may not be fully representative of the diversity of the population dataset. Such algorithms can also lead to more stable training in settings such as distributed training and online learning. In practice, the choice of optimization algorithm that one uses to train the model can greatly affect both its training error and generalization error. Unfortunately, there is a lack of optimization algorithms with provable guarantees on the generalization error. This makes it difficult to design algorithms which provably achieve both a fast running time and low generalization error. The aim of this project is to design novel algorithms for training deep-learning and other machine-learning models, and to prove guarantees on the running time, generalization error and related robustness properties of these algorithms. To design and analyze such algorithms, this project brings together ideas from different areas of mathematics and computer science.This project is designing novel optimization and Markov-chain sampling algorithms, for training deep-learning models as well as other machine-learning models. It aims to prove guarantees on the generalization error and related robustness properties of these algorithms, and also to provide fast running-time guarantees. Guaranteeing a low generalization error is especially challenging in deep learning, since the number of trainable parameters is oftentimes much larger than the size of the dataset, and the loss function used to train the model is nonconvex. To prove stronger generalization and related robustness guarantees, the project team uses ideas from manifold learning and differential geometry to model the low-dimensional structure of datasets which arise in many machine learning applications. The project has three components. One component is to design and analyze novel optimization algorithms for training deep learning models. Another component is to design and analyze algorithms for multi-agent optimization problems, such as the min-max optimization problems which arise when training generative adversarial nets (GANs) as well as multi-agent optimization problems which arise when training meta-learning models. Finally, in addition to optimization algorithms, it is also designing and analyzing Markov-chain sampling algorithms and related algorithms which are used to train Bayesian machine learning models.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.