【阿姆斯特丹博士论文】优化、博弈与泛化界，208页pdf

本论文探讨了理论机器学习的多个方面，特别是关于优化、博弈论和泛化界的研究。因此，论文分为三个部分： 第一部分 关注机器学习中的优化问题。具体而言，我们为介于随机学习和对抗学习问题之间的在线凸优化问题提供了新的遗憾界。此外，我们对多种一阶算法在时变变分不等式上的行为提供了新的见解。这些结果与强凸优化问题的动态遗憾界以及时变博弈的平衡追踪保证相关，因此也与第三部分（关于机器学习中的博弈论方面）的研究有关。在第三部分中，我们首次提出了零和博弈中计算纳什均衡的查询复杂性的非平凡下界。此外，我们为广义纳什均衡问题引入了一种在线可行点方法。对于广义博弈的一个子类，我们证明了该方法可以保证收敛到广义纳什均衡，同时在所有迭代中保持可行性。

第二部分 研究了算法和数据相关的泛化保证。通过引入一种新的算法依赖的Rademacher复杂性定义，我们推导出了与算法输出集合的分形维度相关的几何解释性界限。