报告地点：陕西师范大学长安校区文津楼3425报告厅

主办单位：计算机科学学院

报告一题目：Proper Learnability and the Role of Unlabeled Data and Regularization

报告时间：2025年4月1日（周二）上午9:30

报告人：滕尚华 教授

报告摘要: Proper learning refers to the setting in which learners must emit predictors in the underlying hypothesis class H, and often leads to learners with simple algorithmic forms (e.g., empirical risk minimization (ERM), regularization based structural risk minimization (SRM)). The limitation of proper learning, however, is that there exist problems which can only be learned improperly, e.g. in multiclass classification. Thus, we ask: Under what assumptions on the hypothesis class or the information provided to the learner is a problem properly learnable? We demonstrate that when the unlabeled data distribution is given, there always exists an optimal proper learner governed by distributional regularization, a randomized generalization of regularization. We refer to this setting as the distribution-fixed PAC model, and continue to evaluate the learner on its worst case performance over all distributions. Furthermore, we precisely characterize the role of regularization in perhaps the simplest setting for which ERM and SRM 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 extract from OIGs a combinatorial sequence we term the Hall complexity, which is the first to characterize a problem’s transductive error rate exactly; we also introduce a generalization of OIGs and the transductive learning setting to the agnostic case. We demonstrate that an agnostic version of the Hall complexity again characterizes error rates exactly, and exhibit an optimal learner using maximum entropy programs. This work provides new insights into the role of unlabeled data, and how it can empower local regularization in machine learning.

报告人介绍：滕尚华是南加州大学（USC）的大学教授及Seely G. Mudd计算机科学与数学讲席教授。他是SIAM, ACM和Alfred P. Sloan 基金会的会士，并且两次荣获理论计算机领域最高奖--哥德尔奖(Gödel Prize)。首次获奖是在 2008 年，因开发了平滑分析理论；第二次获奖是在 2015 年，因设计出具有突破性的可扩展拉普拉斯求解器。Simons基金会称他为 “世界上最具原创性的理论计算机科学家之一”，并将他评为 2014 年度Simons研究员，以支持他开展由好奇心驱动的长期基础研究。他还曾获得 2009 年的富尔克森奖、2023 年中国计算机学会颁发的海外华人科技奖、2022 年美国计算机协会经济与计算特别兴趣小组（ACM SIGecom）的时间检验奖（因解决了计算纳什均衡的复杂度问题）、2021 年美国计算机协会计算理论研讨会（ACM STOC）的时间检验奖（因平滑分析理论）、2020 年因所著《数据与网络分析的可扩展算法》一书获得的斐陶斐荣誉学会教师表彰奖（2020 年），以及 2011 年美国计算机协会计算理论研讨会（ACM STOC）的最佳论文奖（因改进了最大流最小割算法）。此外，他与合作者们开发出了针对任意三维区域的首个最优良形德劳内网格生成算法，解决了稳健统计学领域中鲁塞厄-休伯特回归深度猜想，并解答了组合博弈论中与斯普拉格 - 格伦迪定理相关的两个长期存在的复杂性理论问题。鉴于他与Xerox, NASA, Intel, IBM, Akamai, 以及 Microsoft等行业合作伙伴的合作成果，他在编译器优化、互联网技术和社交网络等领域获得了15项专利。

报告二题目：量子线路优化中的一类数学问题

报告时间：2025年4月1日（周二）上午10:30

报告人： 孙晓明 中国科学院计算技术研究所研究员

报告摘要：量子线路作为描述量子算法的一种通用数学模型，已成为量子计算领域的研究重点之一。当前，量子计算的研究已步入含噪声中等尺度量子系统（NISQ）的新阶段，在这一阶段对量子线路的综合优化显得尤为重要。与经典电路复杂性相类似，量子线路的复杂度亦关注于线路规模和深度的优化，同时量子电路的度量标准更为复杂，还涉及辅助比特数量、使用的能级等多个角度。在本次报告中，我们将汇报从量子线路优化中抽象出来的一类与魔方相关的数学问题，以及其与shuffle-exchange问题、Babai猜想的内在联系，并汇报我们的一些进展结果。

报告人介绍：孙晓明，中国科学院计算技术研究所研究员，量子计算与算法理论实验室主任，中国计算机学会会士。主要研究领域为算法与计算复杂性、量子计算等，曾获王选杰出青年学者奖等。目前担任中国计算机学会量子计算专委会主任，《中国科学:信息科学》《软件学报》《Information and Computation》《FCS》等期刊编委。