新闻动态
新闻动态

【WINE 2020】Constantinos Daskalakis教授均衡计算

  2020年12月8日,麻省理工学院教授 Constantinos Daskalakis 带来了题为《均衡计算,对抗神经网络以及深度学习的理论基础》的主旨报告。报告由伊利诺伊大学厄巴纳-香槟分校的 Ruta Mehta 教授主持。

  

 

Constantinos Daskalakis教授报告中

  

  Daskalakis 教授首先指出了当先深度学习实践中的一个有趣现象:单 agent 时,许多优化算法例如梯度下降,都能快速收敛到局部最优解,且具有很好的泛化能力;而有多 agent 时,假如还是都使用梯度下降法训练,很可能长时间都不收敛。无论是 GAN 的训练还是其他 multi-agent 训练过程中都经常遇到这一问题。

 

 

  为了对这一现象寻求一个理论上的解释,Daskalakis 教授考虑一种最简单的 multi-agent 模型,min-max 优化问题,希望对比普通的局部最优解问题和 min-max 问题的区别。当要优化的函数具有凸性时,优化领域早已证明无论是局部(同时也是全局)最小值还是 min-max 点,一阶方法均可以在多项式时间内收敛。

 

  

  而更一般的情况,当函数不再有凸性,仅有光滑性假设时,局部最小值问题仍然有多项式时间的一阶方法,而求 min-max 点的复杂性问题尚不清楚。

 

  

  对于第一种情况,即当优化的函数具有凸性时,主要问题在于优化方法的选择上。假如优化方法选择不得当,仍然可能不收敛。无约束优化的情况已有大量研究,将这一问题研究地非常清楚。而有约束的情况的研究还不足,仍有大量未解决的问题。

 

  

  对于第二种情况,即优化函数不具有凸性时,Daskalakis 教授及其合作者证明了求 min-max 点的计算复杂性是 PPAD-Complete 的。因此任何算法,无论一阶,二阶等,都需要超多项式时间才能收敛,除非 P=PPAD。而局部最小值问题仍然存在多项式算法,这一定程度上解释了为什么局部最小值问题往往优化容易,而 min-max 以及其他 multi-agent 问题优化困难。

 

 

  Daskalakis 教授还对这一结果发表了自己的观点,他认为,multi-agent 机器学习不能再简单粗暴地用标准优化方法+大数据+超级计算机的来解决问题,而必须做好以下四点:1)对问题设定的建模;2)定义何为有意义的解;3)选择合适的机器学习模型;4)专门设计学习和优化算法。

 

  

  最后,Daskalakis 教授总结了一些下一步值得尝试的研究方向,包括:1)一般条件下具有渐进收敛性的算法;2)寻找是否有一些特殊结构下,有可能高效地求得 min-max 点;3)Multi-agent 下的均衡点计算。