WINE 2020 | Constantinos Daskalakis教授均衡计算
编者按
第十六届国际互联网经济学术会议（The 16th Conference on Web and Internet Economics, WINE 2020）于2020年12月7日—11日在线上举行，由北京大学主办，北京大学前沿计算研究中心承办。
本期带来大会特邀报告精彩内容回顾。
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 下的均衡点计算。
WINE 2020 参会指南
本次大会为期5天，共设6个分论坛，给大家带来：
42个学术报告
6个女性论坛报告
4个 keynote 特邀报告
11个 poster
11个 workshop
EC best presentation
会议将全程采用线上模式，每天8小时不间断直播，所有公开报告均可以免费注册观看。
请长按↓小程序码↓转免费注册：
公众号内回复“WINE”转大会信息合辑。
为你最喜欢的海报和报告投票
免费注册者也可以参与投票哦（权重是普通注册者的一半）
投票网站：https://elicitation.info/accounts/signup
请使用你在注册 WINE 2020时使用的邮箱注册。
注册后，点击主页中的 Vote for WINE 开始投票。你可以为一个海报和一个报告投票，投票在提交后不可修改。
投票页面将在会议开始后可见。
投票实时热榜
每天北京时间晚11点将会揭晓当天投票热榜。
你可以在Happy Hour Session（https://gather.town/app/Xpxd8okJW4u1TKHp/WINE20TeaBreak）中观看实时揭榜。
你也可以在网站中看到截至前一天晚11点的榜单。
联系我们
投票相关问题，请联系：
Zhihuan Huang nbdhhzh@pku.edu.cn
Shengwei Xu shengwei.xu@pku.edu.cn
往期回顾
大会新闻
分论坛介绍及议程
特色论坛介绍及议程
大会官网
http://econcs.pku.edu.cn/wine2020
直播平台
哔哩哔哩
寇享学术
关于WINE
国际互联网经济学术会议 （The Conference on Web and Internet Economics, 简称WINE）是由姚期智、叶荫宇和邓小铁教授自2005年从中国香港发起，在亚、欧、美三大洲循环举办的互联网经济学术会议，旨在推动理论计算机、运筹学和机器学习方法论和互联网经济学的交互发展，历经15届，已经成为三大洲互联网经济学者开展科研成果交流的国际顶级会议。
时隔六年，WINE 再次来到中国。本次大会将聚焦于互联网经济及相关学科的前沿问题和最新进展，涵盖机制设计、博弈、拍卖、定价、社会选择等互联网中的重要议题，旨在为各国从事互联网相关经济问题的研究人员提供一个相互交流和展示成果的平台，以此来推动互联网经济及相关学科的发展。
因疫情原因，WINE 将首次在线上召开，届时，论文作者将在线上进行报告和答疑。同时大会还邀请到国内外计算经济学领域的诸多专家学者带来精彩的主题演讲。线上形式给 WINE 2020带来了更多的可能性，组委会正在解锁全新的互动环节，敬请关注！
组委会介绍
大会主席
邓小铁
北京大学前沿计算研究中心讲席教授
欧洲科学院外籍院士
ACM Fellow，IEEE Fellow
程序委员会主席
陈旭瑾
中国科学院数学与系统科学研究院研究员
Nick Gravin
上海财经大学教授
Martin Hoefer
法兰克福大学教授
Ruta Mehta
伊利诺伊大学厄巴纳-香槟分校助理教授
大会特邀报告人
Eric Budish
芝加哥大学商学院教授
Yiling Chen
哈佛大学教授
Jose Correa
智利大学教授
Constantinos Daskalakis
麻省理工学院教授
承办单位简介
作为大会的承办单位，北京大学前沿计算研究中心（PKU CFCS）成立于2017年12月，为北京大学新体制科研机构，立足国际计算机学科前沿，与世界顶尖高校及科研机构深度合作，在计算理论、人工智能等多个领域的交叉方向展开前沿探索，创立具有国际一流影响力的计算理论科学研究中心；创建宽松自由的国际化学术环境，助力青年科学家成长为计算机学科世界一流的学者；并以“图灵人才培养计划”为代表，建立国际先进的计算科学及相关交叉学科人才培养机制，为国家新时代科技和教育发展培养引领未来的卓越人才。
赞助商
文字 | 李佳蔚、段志健
— 版权声明 —
本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。
点“阅读原文”转B站直播