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

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

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.