论文探讨了理论机器学习中的优化、博弈论及泛化界的关键问题与新方法。
原文标题：【阿姆斯特丹博士论文】优化、博弈与泛化界
原文作者：数据派THU
冷月清谈：
本文探讨了理论机器学习中的多个重要议题，聚焦于优化问题、博弈论及泛化界。文章分为三个部分，第一部分主要分析了机器学习中的在线凸优化问题，提供了针对随机学习与对抗学习间的新遗憾界和一阶算法在时变变分不等式上的新见解。这些研究与强凸优化问题和时变博弈相关，形成相互关联的理论基础。第二部分则致力于算法与数据的泛化保证，通过新的Rademacher复杂性定义，探讨了算法输出集合的几何解释及其分形维度。最后，第三部分提出了零和博弈中纳什均衡计算的查询复杂性的下界，并引入了一种新的在线可行点方法，确保在广义博弈中收敛至均衡点并保持可行性。这项研究为深入理解理论机器学习提供了新的视角与方法论。
怜星夜思：
1、在机器学习中，优化与博弈论的结合有什么实际应用吗？
2、泛化界对于机器学习的模型选择有多大影响？
3、关于纳什均衡的理论探索，有哪些未来的研究方向？
2、泛化界对于机器学习的模型选择有多大影响？
3、关于纳什均衡的理论探索，有哪些未来的研究方向？
原文内容
来源：专知本文约1000字，建议阅读5分钟
本论文探讨了理论机器学习的多个方面，特别是关于优化、博弈论和泛化界的研究。
本论文探讨了理论机器学习的多个方面，特别是关于优化、博弈论和泛化界的研究。因此，论文分为三个部分：
第一部分 关注机器学习中的优化问题。具体而言，我们为介于随机学习和对抗学习问题之间的在线凸优化问题提供了新的遗憾界。此外，我们对多种一阶算法在时变变分不等式上的行为提供了新的见解。这些结果与强凸优化问题的动态遗憾界以及时变博弈的平衡追踪保证相关，因此也与第三部分（关于机器学习中的博弈论方面）的研究有关。在第三部分中，我们首次提出了零和博弈中计算纳什均衡的查询复杂性的非平凡下界。此外，我们为广义纳什均衡问题引入了一种在线可行点方法。对于广义博弈的一个子类，我们证明了该方法可以保证收敛到广义纳什均衡，同时在所有迭代中保持可行性。
第二部分 研究了算法和数据相关的泛化保证。通过引入一种新的算法依赖的Rademacher复杂性定义，我们推导出了与算法输出集合的分形维度相关的几何解释性界限。
