编者按：作为人工智能核心领域之一，机器学习研究近年受到高度关注，相关应用的增长也如井喷。而在这热闹场景的背后，机器学习的应用边界仍然受制于理论基础的发展。今年备受关注的学习理论会议(COLT)和理论计算机会议(STOC)，机器学习的研究动态如何？CCCF特别邀请了南京大学张利军和高尉博士撰文向读者介绍。

COLT 2017

由计算学习学会(ACL)举办的学习理论会议(Conference On Learning Theory, COLT) 于2017年7月7~10日在荷兰阿姆斯特丹大学召开，约170人参会。

该会关注机器学习的理论基础，强调运用概率、统计、优化、信息论、几何等基础理论对机器学习进行严格的数学分析。

COLT始于1988年。由于强调理论分析，COLT一直是一个小众会议。会议论文的录用率比其他一些顶级会议高，原因是COLT不是匿名评审，投稿人都会比较慎重，论文本身的质量比较高。被录用论文的一个共同点是页数很多，这是由于强调理论分析，需要有大量的证明推导过程。从图1可以看出，近一半论文超过30页，最长的达81页之多。

由于会议规模较小，COLT一直采用单轨的会议形式，即所有的学术报告都在一个会场内进行。2017年录用的73篇论文，有18篇被选为20分钟的长报告，其余55篇为10分钟的短报告。除口头报告外，会议还安排了约2小时的墙报展示报告环节。另外，会议还为著名学者曼弗雷德·瓦尔穆特(Manfred Warmuth)教授举办了60岁生日庆祝活动，邀请了许多学者介绍他在学习理论尤其是在线学习方面的杰出工作。

今年COLT录用论文的主题覆盖面非常广泛。既包括传统方向，如在线学习、随机优化、统计学习理论、PAC学习、矩阵分解，又涵盖了新兴方向，如非凸优化、神经网络、众包。随着深度学习的流行，研究非凸优化以及神经网络表达能力的理论文章越来越多。今年COLT的最佳论文奖授予了斯坦福大学Yuchen Zhang等人的“A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics”，反映出非凸优化越来越受到重视。今年的最佳学生论文奖由斯坦福大学Cutkosky和Boahen的“Online Learning Without Prior Information”获得，体现出在线学习依然是COLT的传统强势方向。

美国的研究者在COLT上仍然占据压倒性优势，今年有大约2/3的论文第一作者单位来自美国，其次是法国、以色列、中国。今年第一作者来自中国的论文有4篇，3篇来自清华大学交叉信息研究院，1篇来自南京大学LAMDA组。

编者按：作为人工智能核心领域之一，机器学习研究近年受到高度关注，相关应用的增长也如井喷。而在这热闹场景的背后，机器学习的应用边界仍然受制于理论基础的发展。今年备受关注的学习理论会议(COLT)和理论计算机会议(STOC)，机器学习的研究动态如何？CCCF特别邀请了南京大学张利军和高尉博士撰文向读者介绍。

COLT 2017

由计算学习学会(ACL)举办的学习理论会议(Conference On Learning Theory, COLT) 于2017年7月7~10日在荷兰阿姆斯特丹大学召开，约170人参会。

该会关注机器学习的理论基础，强调运用概率、统计、优化、信息论、几何等基础理论对机器学习进行严格的数学分析。

COLT始于1988年。由于强调理论分析，COLT一直是一个小众会议。会议论文的录用率比其他一些顶级会议高，原因是COLT不是匿名评审，投稿人都会比较慎重，论文本身的质量比较高。被录用论文的一个共同点是页数很多，这是由于强调理论分析，需要有大量的证明推导过程。从图1可以看出，近一半论文超过30页，最长的达81页之多。

由于会议规模较小，COLT一直采用单轨的会议形式，即所有的学术报告都在一个会场内进行。2017年录用的73篇论文，有18篇被选为20分钟的长报告，其余55篇为10分钟的短报告。除口头报告外，会议还安排了约2小时的墙报展示报告环节。另外，会议还为著名学者曼弗雷德·瓦尔穆特(Manfred Warmuth)教授举办了60岁生日庆祝活动，邀请了许多学者介绍他在学习理论尤其是在线学习方面的杰出工作。

今年COLT录用论文的主题覆盖面非常广泛。既包括传统方向，如在线学习、随机优化、统计学习理论、PAC学习、矩阵分解，又涵盖了新兴方向，如非凸优化、神经网络、众包。随着深度学习的流行，研究非凸优化以及神经网络表达能力的理论文章越来越多。今年COLT的最佳论文奖授予了斯坦福大学Yuchen Zhang等人的“A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics”，反映出非凸优化越来越受到重视。今年的最佳学生论文奖由斯坦福大学Cutkosky和Boahen的“Online Learning Without Prior Information”获得，体现出在线学习依然是COLT的传统强势方向。

美国的研究者在COLT上仍然占据压倒性优势，今年有大约2/3的论文第一作者单位来自美国，其次是法国、以色列、中国。今年第一作者来自中国的论文有4篇，3篇来自清华大学交叉信息研究院，1篇来自南京大学LAMDA组。

STOC 2017

STOC是ACM计算理论年会(ACM Annual Symposium on the Theory Of Computing, STOC)，是理论计算机科学领域的顶级学术盛宴之一。STOC始自1969年。第49届STOC于2017年6月19~23日在加拿大蒙特利尔召开。

STOC 2017共吸引422篇投稿，录用103篇，录用率为24.4%。从图2可见近五年来STOC会议投稿量、录用量情况。与COLT相似，STOC会议秉承“小而精”的理念，会议规模相对较小，但论文质量要求很高。入选论文需要在某一领域取得突破性、开创性进展，有深刻的理论认识和严格的推理论证。论文的篇幅也比较长，页数超过30页的占50%以上，最长的124页。高质量的学术工作吸引了不少学术大师，例如图灵奖得主、清华大学姚期智教授出席了会议。

会议组织举办了两场特邀报告、三场教学报告和六场专题研讨会。大会涵盖计算机科学诸多领域，如理论计算机科学、机器学习、博弈论、信息论、信息安全等。为便于研究工作的充分展示和交流，每篇论文不仅有15分钟的口头报告和5分钟的问答互动环节，还有一个晚上的论文墙报展示报告。

今年的会议颁发了2017年度理论计算机科学界两大极富盛誉的奖项：哥德尔奖(Gödel Prize)和高德纳奖(Knuth Award)。哥德尔奖由欧洲计算机学会(EATCS)与美国计算机学会基础理论专业组织(ACM SIGACT)于1993年共同设立，用于奖励在理论计算机领域取得突出贡献的学术论文，侧重于在某一领域取得开创性、突破性进展。今年哥德尔奖颁给了C. Dwork, F. McSherry, K. Nissim和A. Smith四人，以表彰差分隐私的开创性工作“Calibrating Noise to Sensitivity in Private Data Analysis”。高德纳奖侧重于终身成就奖。今年的高德纳奖颁给了以色列魏茨曼科学研究所(Israel Weizmann Institute of Science)的Oded Goldreich教授，以表彰他在理论计算机科学中的密码学、概率可验证明、复杂性理论等领域的杰出贡献。会议最佳论文奖分别颁发给编码、并查集以及拟阵的奇偶问题三个工作。

STOC 2017大会开幕后，2009年哥德尔奖得主、美国科学院院士Avi Wigderson教授作了题为“On the Nature and Future of the Theory of Computation”的特邀报告，报告回顾了理论计算机科学所取得的进展，以及理论计算机科学与数学、物理等学科之间的联系。第二个特邀报告来自以色列希伯来大学Orna Kupferman教授，题为“Examining Classical Graph-Theory Problems from the Viewpoint of Formal-Verification Methods”。此报告详细介绍了如何利用形式化验证(formal verification)方法研究经典图论问题，以获取图的丰富结构与语义，进而进行推理。此外，STOC还组织了多场全体会议(plenary)报告，用于分享其他顶级国际会议论文（如ICML、NIPS、PODS等）或期刊论文，今年的plenary报告共11篇，其中3篇机器学习方向的报告来自ICML’16和NIPS’15。

作为人工智能核心之一的机器学习，一直受到理论计算机科学领域的高度关注。图3统计了过去四年机器学习相关论文在STOC所有录用论文中所占的比例，可以发现，每年机器学习方向都有10余篇论文在STOC上发表。此外，今年会议最后一天组织了6场专题研讨会，其中一场题为“New Challenges in Machine Learning: Robustness and Nonconvexity”的研讨会，由美国南加州大学I. Diakonikolas, 微软研究院R. Ge和麻省理工学院A. Moitra三位学者发起，对机器学习中非凸性和鲁棒性研究进展进行了深入探讨，这一话题与今年COLT凸显的非凸优化十分切合。而今年会议的三个教学报告之一“Foundations of Deep Learning”也关注深度学习的理论基础。可见，机器学习受到理论计算机科学领域的持续关注，同时理论计算机科学的融入，也将从根本上推动机器学习方法与应用的发展。   ■