算法险峰的攀登者——记香港大学计算机科学系副教授黄志毅

王 芳 户 万

哪怕是没有攀登的日子，香港大学（简称“港大”）计算机科学系副教授黄志毅的思绪也会围绕着“岩点”——思考如何完美地调动指尖、脚掌、身体核心，想象动作的姿态与前后的衔接。热爱攀岩，很大程度上因为这项运动与他从事的事业——理论计算机科学领域里不确定信息下的优化问题研究有异曲同工之妙。

一面面陡峭的岩壁，就像一道道充满挑战的开放问题，都需要大脑和身体的密切配合，恰到好处地应用工具、审慎地规划总结、针对性地攻克多个困难点。然后，在一次次的坠落悬停中，忍受挫败、自我怀疑，提升情绪弹性、身体意志力和抵达终点的信念感；在种种不确定信息下，条分缕析、不断试炼，以实现微妙的平衡与优化，回应来自广阔世界的真实需求。

2014年加入港大以来，凭借不懈努力，黄志毅已陆续解决了图灵奖得主理查德·卡普（Richard Karp）提出的三十年开放问题（涵盖智能出行、器官捐赠等应用），以及线上广告中显示广告、广告关键字两个十几年开放问题。迄今为止，他已发表40余篇顶会论文。2015年，他获得算法和架构并行性年会（SPAA）最佳论文奖，是亚洲院校的首位获奖者；2020年，他获得计算机科学基础年会（FOCS）最佳论文奖，是近14年来首次、亚洲院校第二位获奖者。

黄志毅

无限风光在险峰，无限风光在前方。算法世界的攀登之旅从来没有真正的终点。对黄志毅来说，攀登的妙处在于遍寻而得的完美路线、登临之后的短暂喜悦，更在于历经艰辛触摸最高“岩点”后继续走向下一面未知峭壁的无畏勇气，以及因此而锤炼出来的不断开阔视野、不断向上进取的蓬勃生命力。

向不确定的未知进发

对理论计算机科学家而言，每个平静时刻都可能蕴藏着“头脑风暴”。有时，周末坐在地上陪伴孩子玩游戏，黄志毅不知不觉就神游别处，回想起某个算法问题。对理论计算机科学的这种痴迷，还要从他十几年前在清华大学（简称“清华”）“姚班”读书的经历说起。

2004年，图灵奖得主姚期智院士全职回到清华，讲授计算机与科学技术系课程。其间，他萌生了创立“清华学堂计算机科学实验班”的想法，并于次年通过选拔考试，正式组建了一个包括30名数学和计算机尖子生的班级，这便是第一届“姚班”。黄志毅进入第一届“姚班”时正读大三。早前因在高中数学竞赛中表现优异，他被保送清华计算机系；之后又出于对数学和物理的兴趣，上过学院“数理实验班”的课程。这些无意中为他考入“姚班”打下了一定基础。

“姚班”致力于培养与美国麻省理工学院、普林斯顿大学等世界一流高校本科生具有同等，甚至更高竞争力的领跑国际的拔尖创新计算机科学人才。姚期智院士为班内学生专门制订培养方案，尤其是他开设的理论算法课程，令人耳目一新。同时，他还邀请微软亚洲研究院的研究员为学生教授分布式计算、操作系统等课程，教材、习题在当时都十分先进。集结优秀的老师、聪明的同学，“姚班”内部形成了热烈向学的氛围，黄志毅深受熏陶，并逐渐对姚期智院士研究的理论计算机科学产生了兴趣。理论计算机科学，即计算机科学的数学基础，包括各种计算问题的算法设计及其时间复杂度、空间复杂度等方面的数学分析，十分契合黄志毅的兴趣和专长。

2008年毕业后，黄志毅前往美国宾夕法尼亚大学读博深造。导师萨姆帕斯·坎南（Sampath Kannan）是美国计算机学会会士；另一位导师亚伦·罗斯（Aaron R o t h）是斯隆奖得主，两位导师都在各自的研究领域造诣非凡。其间，黄志毅展开了积极的学术交流，接触了理论计算机科学领域的多个方向，并对其中的在线算法和算法博弈论进行了较多研究，与谷歌研究院和微软研究院进行了合作。不仅如此，博士期间，他还提出了“把算法转化为激励相容机制的一般性方法”的代表性成果，接连获得了2012年西蒙斯理论计算机科学奖学金（全美一共有5名获奖者）、2013年拉比诺夫博士论文奖等重要奖项。

取得博士学位后，黄志毅又在斯坦福大学跟随哥德尔奖得主蒂姆·拉夫加登（Tim Roughgarden）做了一年博士后研究，在这期间他认真思考了接下来的科研规划。彼时的中国，理论计算机科学研究刚刚兴起。作为第一届“姚班”学子，学成以后像姚期智院士当初一样回国效力，一直是黄志毅的期望所在。于是，2014年他选择回国，并加入紧邻家乡广东、历史悠久的香港大学（以下简称“港大”）任教。刚入职，他就从359名杰出青年学者计划申请者中脱颖而出，成为2014—2015年度香港研究资助局所颁发的22个杰出青年学者奖（Early Career Award）获奖者之一。在港大学术氛围浓厚的校园中，黄志毅由此开启了不确定信息下的优化问题研究。

2017年黄志毅（前排左三）参加以“不确定信息下的算法与优化”为主题的日本湘南会议

不确定信息下的优化问题，是一个有别于传统算法研究的方向。传统算法研究考虑的是如何在时间、存储空间等计算资源的限制条件下解决不同的计算问题；而不确定信息下的优化问题则是在把信息本身视作一种计算资源的同时，在信息不充足的限制条件下设计算法解决问题。以搜索引擎上匹配搜索请求和广告商的问题为例：一方面，算法在匹配某个搜索请求时无法准确预知将来还有什么样的请求，因此这类问题需要处理将来的不确定性；另一方面，为找到好的匹配，算法想要知道广告商对于不同关键字的价值衡量，而这个信息只有广告商自己知道，于算法而言是不确定的。

根据信息不确定性的种类及实际考量，黄志毅主要对在线算法与算法博弈论两个方向进行了深研。在这两大算法领域，又矗立着数不清的科研险峰，每座险峰天然形成多面峭壁。几十年来，其间荆棘丛生、云雾缭绕、神秘莫测，引得钟情理论计算机科学的“探险家”“攀登者”不远万里前来拜谒，苦思冥想、身体力行，寻找登顶的希望。黄志毅兴致勃勃投身其中，向不确定的未知正式进发。

破解问题与推进应用

在线算法领域，黄志毅先后聚焦非线性目标函数在线优化问题、传统在线匹配问题、完全在线匹配问题开展研究。算法博弈论方面，他对近年来的一个研究热点——如何在买家价值的概率分布信息不足的场景中进行机制设计——进行了一系列创新研究，论文发表于理论计算机科学的旗舰会议计算理论年会（STOC）和计算机科学基础年会（FOCS）。

调度和资源分配是非线性目标函数的在线优化的两类经典问题。2014年，黄志毅针对如何实时调整处理器速度，以达到能源消耗与工作处理效能间的最优平衡的问题展开研究。这当中有个关键点在于，能耗往往是处理器速度的二次或三次函数而并非线性，对此黄志毅提出了一套基于Fenchel对偶性的算法设计和分析框架，并以此为基础设计了此问题的理论最优算法。2015年，他进一步把结果扩展到无法准确预测处理每个工作所需计算资源之数量的短视模型，并在此模型下提出了一个新算法去模仿非短视模型下的算法决策。相关论文获得了高性能计算理论方面的顶会算法和架构并行性年会（SPAA）颁发的最佳论文奖。2016年，黄志毅从Fenchel对偶性框架中提炼出一般性的理论方法，从而一次性地解决了一大类非线性目标函数的覆盖及装箱问题。《美国计算机学会算法与计算理论通讯》（A C M SIGACT News）在线算法专栏的2016年总结中认为这篇论文“统一、简化，并改进了许多现有结果”，并称这一论文为“此年度最引人瞩目的结果”。

匹配是最基础的优化问题之一，而它的在线版本也是在线算法中最受关注的方向之一。传统在线匹配模型在器官移植、在线广告匹配等应用场景的建模中十分常见。由于理论计算机科学中常用的最坏情形分析框架在这些场景下往往不能很好地刻画实际问题的特点，所以近年在线匹配的热点和难点之一是在模型中引入一定的随机性并在此前提下设计算法。此外，传统在线匹配中有一些经过10年以上研究仍未有突破的开放性问题。2020年，经过多年积累和思考，黄志毅针对2005年提出的广告关键字问题和2009年提出的显示广告问题提出了名为在线相关选择的新算法技巧，一举突破了这两个开放性问题的瓶颈。尤其值得一提的是，他关于解决显示广告问题的工作获得了2020年度计算机科学基础年会（FOCS）的会议最佳论文奖，是历史上第二次有亚洲院校的学者获奖，也是近14年来的首次。

传统的在线匹配理论只处理二分图匹配，比如搜索请求和广告商的匹配。而在包括叫车、拼车服务在内的一些新应用场景中，算法所需要处理的往往是一般图的在线匹配。从实际场景出发，2018年黄志毅提出了完全在线匹配模型及相应的算法分析框架，从而使一般图的在线匹配理论研究成为可能，这被认为是“首次把图灵奖得主理查德·卡帕等提出的算法推广到一般图并取得好于0.5的近似比”。由于研究颇具价值，后续叫车平台Lyft、麻省理工学院、斯坦福大学等研究组都参考使用了这个模型。

此外，在算法博弈论方面，关于“如何在贝叶斯模型下从数据中学习出贝叶斯先验概率分布的近似形式，从而用较少的数据得出利润最大化的近似最优机制”的问题，针对算法的采样复杂度，自2015年起，黄志毅接连产出了一系列研究成果。

——2015年，黄志毅发现了这一问题与统计机器学习理论及信息论之间的联系，其中前者能用于分析采样复杂度的上界，而后者能用于分析采样复杂度的下界。基于这些工具，他解决了单个买家单个物品情形下的采样复杂度问题，在业内引起广泛关注。

——2016年，黄志毅把基于统计机器学习理论的算法思路及分析的方法推广到了多个买家的情形，从而改进了其采样复杂度上界。

——2017年，黄志毅注意到实际场景中的算法需要不断利用新的数据更新所学到的机制和定价，这可以视作一种在线学习。通过提出一套新的多尺度在线学习理论，他设计了新的算法并获得了最优的理论结果。这套新理论后来在传统机器学习理论的模型选择问题中也得到了应用。

黄志毅在中国计算机协会（CCF）启智会上以“数据驱动的拍卖机制设计”为主题开展讲座

——2018年，黄志毅注意到此前的相关研究中一般假设买家并不会针对卖家的算法对自身行为进行策略性的调整，而一些后续研究指出这个假设过度简化了问题，并证明了买家的策略性行为可能大幅降低卖家算法所获得的利润。据此，他提出了一套基于差分隐私的算法工具，这套工具在所需要学习的机制结构相对简单时可以有效地降低买家的策略性行为。

——2019年，黄志毅基于此前研究，重新提出了一套与之前框架截然不同的基于信息学的新方法，从而彻底解决了多个买家情形下采样复杂度问题，被学界视为采样复杂度方向的一个“突破性结果”。

——2020年，黄志毅进一步将这一系列采样复杂度理论应用到更困难的市场划分问题上，并获得了这个问题的首个多项式采样复杂度上界。

以上相关成果获得了包括算法博弈论的奠基者及理论计算机科学领域高规格奖哥德尔奖得主诺姆·尼桑（N o a m Nisan）、蒂姆·拉夫加登，以及奈望林纳奖得主康斯坦丁诺斯·达斯卡拉基斯（Constantinos Daskalakis）、图灵奖得主姚期智等在内的著名学者的引用研究。

从讲台下聆听基础课的懵懂学子，到成为与诸位恩师、学界前辈娓娓而谈的学术同行，黄志毅的成长肉眼可见。“我的进步除了离不开姚院士的指引，也深深受益于我的博士生导师萨姆帕斯·坎南和亚伦·罗斯，以及博士后导师蒂姆·拉夫加登、微软研究院实习时的导师尼基尔·德瓦马塔尔（Nikhil Devanur）。邓小铁、滕尚华、孙晓明等学界前辈，亦多次提携指教，给予我宝贵的建议。”一年又一年，现实世界的诸多问题凝于脑海，伴随一次次复杂的推演、解题，黄志毅的算法险峰攀登之旅渐入佳境。

明德格物 探索不止

港大的校徽上镌刻着“明德格物”4个字。“明德”就是彰显德行，“格物”就是探究事物原理。在快节奏的香港，港大给师生营造了一个安静舒适的学术天堂，去除了浮躁，并不一味追求论文产出。在近10年的港大生涯中，黄志毅体会最大的就是这种让人富有尊严的学术自由度。

“理论计算机科学研究的成果产出周期相对较长，但是学院并没有一刀切地下达硬性任务指标，而是尊重了大家的学科特点。学院领导还很注重培养年轻教师的独立科研能力，鼓励我们先发展自己的团队和感兴趣的科研方向，而不是与资深的教授合作尽快产出成果。”正是在这种氛围下，黄志毅没有跟风选择热门方向，而是坚持自己的研究兴趣，逐渐带领团队步入正轨，顺理成章地形成了一系列有影响力的学术成果。

目前，黄志毅团队平均每年招收1名博士研究生，课题组的博士研究生一般为4到5名。此外，每年夏天，他还会指导2到6名来自国内外的本科生做研究。短期的师生缘分结束后，如果互相考察满意，将会继续进行为期一年的合作研究。而这些本科生中的一部分便是来自清华的“姚班”。“姚班人”一边传承着姚期智院士的学术衣钵，一边协作创新，人才辈出。

在黄志毅看来，理论计算机科学的研究模式，某种意义上是一种学徒制。“我跟学生是合作关系。我们的区别可能主要在于我经验更丰富、资历更深。在日常研究中，他们会通过课题研究，学习我的选题思路、解题思路、提问思路等。这种研究模式，没有一套完整的教材，导师更需要对学生进行言传身教。”

为此，黄志毅对学生提出了他认为最重要的几点要求。一是要培养对高价值选题、高品位选题的认知。“十多年前，我去宾夕法尼亚大学读博，系主任在简介会上讲了许多话，我至今唯一记得的一句就是‘读博这几年，最重要的一件事就是形成研究的品位，知道选题的好与坏’。”二是做理论计算机科学研究，需要在数学思维的运行、数学工具的使用上有足够的成熟度，能够随机应变，想方设法推进研究。三是养成好习惯。“我经常跟学生强调，要保持良好的阅读论文的习惯，除了自己小方向的论文外，还要尽可能了解一些其他相关领域的前沿学术成果，拓展知识储备、学术视野。”至于，很多人关心的论文发表，黄志毅反而对此抱着轻松的态度，“论文发表有一定的运气成分在，看学生个人造化就好，急不来”。

即便当了多年老师，黄志毅也始终谨记自己的学生身份。在姚期智院士众多的提点之语中，那句“做研究的人，不需要在同一个问题上反复证明自己”曾如一颗石子投入湖水，在黄志毅的心里激起圈圈涟漪，后来成为他时时勉励自己的格言，激励着他不断尝试、不断挑战，每隔一段时间便停下来回顾总结。而决定攀登成功与否的，往往就是微末的细节、一念的犹豫。如今，相比获得“最佳论文”，做出新颖的科研探索、践行美好的科研品位，更让黄志毅心向往之。

在线算法研究的问题根源于未来将发生的不确定性，算法博弈论关注的是与自私主体私人信息的不确定性相关的问题。未来，在不确定性下优化的广泛背景下，黄志毅希望对相关方向上未解决的挑战继续展开探索。在战略环境中的学习、在线优化的线性程序层次结构、融合来自不同领域的在线决策策略……一座座险峰、一面面峭壁，也正向这位勇敢的攀登者发出盛情邀约。