基于数据驱动的经典优化器和学习优化器的性能保证

Apr, 2024

基于数据驱动的经典优化器和学习优化器的性能保证

Data-Driven Performance Guarantees for Classical and Learned Optimizers

Rajiv Sambharya, Bartolomeo Stellato

TL;DR介绍了一种数据驱动的方法，利用统计学习理论的泛化保证来分析连续优化算法的性能。研究经典优化器和学习优化器来解决参数优化问题的族群。建立了经典优化器的泛化保证，利用样本收敛界限，以及学习优化器的泛化保证，利用 Probably Approximately Correct (PAC)-Bayes 框架。通过使用基于梯度的算法直接最小化 PAC-Bayes 上界来训练学习优化器。在信号处理、控制和元学习的数值实验中展示了我们的框架能够在固定迭代预算的情况下为经典和学习优化器提供强大的泛化保证。对于经典优化器而言，我们的界限比最坏情况保证的界限要严格得多。对于学习优化器而言，我们的上界优于观察到的非学习对应的实际结果。

Abstract

We introduce a data-driven approach to analyze the performance of continuous optimization algorithms using generalization guarantees from statistical learning theory. We study classical and →

data-driven approach continuous optimization algorithms generalization guarantees learned optimizers pac-bayes framework

发现论文，激发创造

具有 PAC-Bayesian 保证的学习优化：理论考虑和实践实现

用 PAC-Bayesian 理论为学习优化问题提供了第一个具备可证估计以及收敛保证和收敛速度权衡的框架，学习出的优化算法在比起仅从最坏情况分析得出的算法上具备可证的优越性能，基于指数族的 PAC-Bayesian 上界对一般的、可能无界的损失函数提供了可行性，我们通过将学习过程转化为一维最小化问题并研究全局最小值的可能性，提供了一个具体算法实现和学习优化的新方法，并进行了四个实际相关的实验来支持我们的理论，展示出该学习框架使得优化算法的性能有了数个数量级的改进。

Apr, 2024

数据驱动算法设计的泛化保证：学习高性能算法需要多少数据？

研究表明，数据驱动的算法设计可以显著提高性能，我们提供了一个推广的理论，用于推导性能的一般化保证，无论参数是如何调整的。该理论还暗示了计算生物学中的投票机制和动态规划算法的新界限。

Aug, 2019

通过最小化 PAC-Bayesian 广义化界限来学习高斯过程

该研究提出了一种使用 PAC-Bayesian 边界来直接优化 GPs 及其稀疏逼近的方法，相比于最大化边缘似然的常规方法，该方法具有更好的稳健性和泛化性能，并在多个回归基准数据集上获得了显着的泛化保证。

Oct, 2018

在线到 PAC 转换：通过遗憾分析获得泛化界

本文提出了从在线学习的角度推导统计学习算法的泛化界限的新框架，建立在线学习算法与统计学习算法之间的联系，通过构造一种在线学习游戏来实现该框架并得到多种泛化保证。

May, 2023

使用非线性系统理论学习带有收敛保证的优化方法

我们提出了一个利用非线性系统理论填补演进中算法收敛性和鲁棒性分析的理论框架，可以自动化地优化学习到的算法，保证其设计上的收敛性。

Mar, 2024

深度学习的泛化界限

本研究提出了关于深度学习的泛化误差的准则，介绍了一种基于边际似然的 PAC-Bayesian Bound 方法来预测泛化误差，并进行了广泛实证分析以评估该方法的效果和特性。

Dec, 2020

具有健壮泛化保证的自适应学习

研究三种不同强度的泛化理论 —— 稳健泛化、差分隐私和完美泛化的关系，并证明了每个假设类都可以在稳健泛化的情况下进行 PAC 学习，具有相近的样本复杂度。

Feb, 2016

基于梯度的元学习的可证明保证

本文介绍了基于在线凸优化的元学习问题，并提出了一种元算法，使得流行的基于梯度的元学习和传统的基于正则化的多任务转移方法之间的差距得以弥合。我们的方法是第一个在凸设置下同时满足良好的样本效率保证，并且具有随着任务相似度提高而改善的泛化界限，同时在现代深度学习体系结构和多任务环境下具有可伸缩性的方法。尽管算法很简单，但它匹配了下限，是任何此类参数传输方法在自然任务相似度假设下的性能的常数因子。我们在凸和深度学习设置下的实验验证和演示了我们理论的适用性。

Feb, 2019

随机学习的 PAC-Bayesian 分析及其在随机梯度下降中的应用

通过 PAC-Bayes 和算法稳定性的结合研究了随机梯度下降算法的泛化误差，提出了一种基于后验优化的自适应采样算法，并在基准数据集上进行评估。结果表明，相较于均匀采样，自适应采样既可以更快地降低经验风险，也可以提高样本外准确性。

Sep, 2017

基于随机集的 PAC-Bayesian 理论对数据依赖假设集的统一泛化界限

我们从 PAC-Bayesian 的角度提出了数据相关的均匀泛化界，通过将训练算法输出的数据相关假设集应用于随机集的严格方法，我们证明了数据相关的界，适用于多种情境，并将此方法应用于基于分形维度的泛化界和连续 Langevin 动力学以及随机梯度 Langevin 动力学的轨迹上，这些结果为噪声算法的泛化特性提供了新的信息。

Apr, 2024