【伯克利博士论文】优化与机器学习中的结构驱动算法设计，420页pdf

优化算法的一个教科书式特性是在通用的正则条件下解决问题的能力。两个例子分别是单纯形方法和梯度下降（GD）方法。然而，这些基本且通用的优化算法的性能往往不尽如人意；它们经常运行缓慢，在通用设置下可能返回次优解。在我看来，这是它们通用性的代价；实际上，通用算法是一项成就，但对于许多问题来说，利用特殊结构所带来的收益可能非常巨大。一个基本问题随之产生：我们如何在算法中利用问题特定结构，以获得具有强性能保证的快速、实用的算法？随着更多结构化的数据驱动决策模型的出现，这个问题对实践者来说变得越来越紧迫和相关。

例如，在非凸优化中，GD方法众所周知容易陷入次优的鞍点。然而，一系列近期的研究表明，随机初始化或扰动改变了GD的动态特性，并使其可证明地收敛于全局最优解。此外，马尔可夫决策过程（MDP）和离散最优传输（OT）问题都可以通过大规模线性规划来解决。与使用通用LP算法不同，策略迭代和Sinkhorn迭代利用了MDP和OT中的特殊结构，因此在实践中表现更好。将算法调整为问题特定结构通常被称为结构驱动的算法设计。

尽管这一研究方向已经被广泛研究了70多年并取得了广泛的成功，但机器学习的成功案例引入了新的表述，它们适合进行深入的理论分析和产生显著的实际影响。我的研究通过识别可靠机器学习（极小极大优化）和多智能体机器学习（高阶优化及以上）的特殊结构，以及设计计算适当定义的最优解的最优算法；还有其他结构化问题，如高效熵正则化最优传输、无梯度非光滑非凸优化以及在博弈中的自适应和双重最优学习，推动了这一领域的发展。