深圳河套学院有幸邀请到国际计算机理论领域泰斗、两届哥德尔奖得主、南加州大学计算机科学与数学系讲席教授滕尚华（Professor Shang-Hua Teng）于12月23日，亲临SLAI开设讲座，引领师生系统深入学习理论前沿，欢迎学院师生及对该领域感兴趣的产学研界同仁参与。

Lecture Topic

Understanding and Characterizing Regularization

About the Speaker

滕尚华 教授

国际计算机理论领域泰斗、两届哥德尔奖得主、南加州大学计算机科学与数学教授

Professor Shang-Hua Teng (USC)

Two-time Gödel Prize laureate, Professor of Computer Science and Mathematics at the University of Southern California

滕尚华教授在计算机理论领域建树卓越。他是南加州大学计算机科学与数学系讲席教授，同时身兼美国计算机协会（ACM）会士、美国工业与应用数学学会（SIAM）会士、斯隆基金会会士等重要身份。

在2008年与2015年，凭借在算法平滑分析理论的开发，以及为网络系统设计突破性的近线性时间拉普拉斯求解器这两项杰出成果，两次斩获理论计算机科学领域的世界权威奖项——哥德尔奖。西蒙斯基金会誉其为“世界上最具原创性的理论计算机科学家之一”，并在2014年授予他西蒙斯研究员（Simons Investigator）称号，以支持其长期基于好奇心的基础研究。

他还荣获2009年福克森奖（Fulkerson Prize）、2023年中国计算机学会海外华人科学技术奖、2021及2025年ACM STOC“时间检验奖”（分别表彰其在平滑分析与最大流计算方面的贡献）、2022年ACM SIGecom“时间检验奖”（Test of Time Award，因解决纳什均衡计算复杂性问题）、2020年Phi Kappa Phi教师表彰奖（因其著作《可扩展的数据与网络分析算法》）、2011年ACM STOC最佳论文奖（因改进最大流-最小割算法）。

此外，他合作开发了首个针对任意三维域的最优形状Delaunay网格生成算法，解决了鲁棒统计学中的Rousseeuw-Hubert回归深度猜想，并解决了组合博弈论中关于Sprague-Grundy定理的两个长期悬而未决的复杂性理论问题。在产业界，他曾与Xerox、NASA、英特尔、IBM、Akamai和微软合作，并在编译器优化、互联网技术和社交网络等领域获得了多项专利。

Shang-Hua Teng is a USC University Professor of Computer Science and Mathematics. He is a fellow of SIAM, ACM, and Alfred P. Sloan Foundation, and has twice won the Gödel Prize, first in 2008, for developing smoothed analysis, and then in 2015, for designing the breakthrough scalable Laplacian solver.

Citing him as, “one of the most original theoretical computer scientists in the world”, the Simons Foundation named him a 2014 Investigator to pursue long-term curiosity-driven fundamental research.

He also received the 2009 Fulkerson Prize,2023 Science & Technology Award for Overseas Chinese from the China Computer Federation, 2021 and 2025 ACM STOC Test of Time Awards (for smoothed analysis and max-flow computation), and 2022 ACM SIGecom Test of Time Award (for settling the complexity of computing a Nash equilibrium.

In addition, he co-developed the first optimal well-shaped Delaunay mesh generation algorithms for arbitrary three-dimensional domains, settled the Rousseeuw-Hubert regression-depth conjecture in robust statistics, and resolved two long-standing complexity-theoretical questions regarding the Sprague-Grundy theorem in combinatorial game theory.

For his industry work with Xerox, NASA, Intel, IBM, Akamai, and Microsoft, he received fifteen patents in areas including compiler optimization, Internet technology, and social networks.

Abstract

The quintessential learning algorithm of empirical risk minimization (ERM) is known to fail in various settings for which uniform convergence does not characterize learning. Relatedly, the practice of machine learning is rife with considerably richer algorithmic techniques, perhaps the most notable of which is regularization. Nevertheless, no such technique or principle has broken away from the pack to characterize optimal learning in these more general settings. The purpose of this work is to precisely characterize the role of regularization in perhaps the simplest setting for which ERM fails: multiclass learning with arbitrary label sets. Using one-inclusion graphs (OIGs), we exhibit optimal learning algorithms that dovetail with tried-and-true algorithmic principles: Occam’s Razor as embodied by structural risk minimization (SRM), the principle of maximum entropy, and Bayesian inference. We also extract from OIGs a combinatorial sequence we term the Hall complexity, which is the first to characterize a problem’s transductive error rate exactly. Lastly, we introduce a generalization of OIGs and the transductive learning setting to the agnostic case, where we show that optimal orientations of Hamming graphs–judged using nodes’ outdegrees minus a system of node-dependent credits–characterize optimal learners exactly. We demonstrate that an agnostic version of the Hall complexity again characterizes error rates exactly, and exhibit an optimal learner using maximum entropy programs.

Joint work (COLT 2024) with Julian Asilis, Siddartha Devic, Shaddin Dughmi, and Vatsal Sharan

Host

欧阳万里教授，深圳河套学院副院长

Professor Wanli Ouyang , Deputy Dean, SLAI

Date & Time

2025年12月23日（周二）

14:00–15:30

Tuesday, 23 December 2025

14:00–15:30

Venue

深圳河套学院B411阶梯教室

（深圳市福田区福保街道红棉路6号，地图导航“深圳河套学院-南门”）

Room B411, Shenzhen Loop Area Institute

(6 Hongmian Rd, Fubao Sub-Street, Futian District, Shenzhen, navigate to "Shenzhen Loop Area Institute (South Gate)" on the map.)