讲座主题：
Understanding and Characterizing Regularization
时间：
2025年4月10日14:30
地点：
人工智能与计算机学院B310会议室
摘要：
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.
个人简介：
滕尚华现任南加州大学特级教授，计算机科学系和数学系教授。从2009年到2012年，他是南加州大学计算机科学系系主任。之前，他曾任教于波士顿大学，伊利诺伊大学香槟分校（UIUC），明尼苏达大学，和麻省理工学院。他也曾任Akamai科技公司高级科学家，Xerox PARC博士后研究员，并兼任微软研究院，IBM 公司，Intel 公司，美国航空航天局研究院（NASA Ames）暑假访问科学家。滕尚华获得上海交通大学计算机科学和电子工程双学位 （1985），南加州大学计算机硕士（1988），卡内基梅隆大学计算机科学博士 （1991）。
他曾两度荣获理论计算机领域哥德尔奖（Gödel Prize，2008年和2015年），并荣获2009年美国数学学会和美国数学规划学会颁发的福克森奖（Fulkerson Prize），2023 中固计算机学会海外科技人物奖，2014年西蒙斯研究员奖，和两次计算机理论科学时间检验奖。他是美国计算机学会会士和斯隆基金会会士。
当前位置:
