哪怕是没有攀ȝ日子Q香港大学（U“港大”）计算机科学系副教授黄志毅的思A也会(x)围绕着“岩点”——思考如何完地调动指尖、脚掌、n体核心，惌动作的姿态与前后的衔接。热爱攀岩，很大E度上因运动与他从事的事业——理机U学领域里不定信息下的优化问题研究有异曲同工之妙?/span>
一面面陡峭的岩壁，像一道道充满挑战的开N题，都需要大脑和w体的密切配合，恰到好处地应用工兗审慎地规划ȝ、针Ҏ(gu)地d多个困难炏V然后，在一ơ次的坠落?zhn)停中Q忍受挫败、自我怀疑，提升情AҎ(gu)、n体意志力和抵辄点的信念感；在种U不定信息下，条分~析、不断试|以实现微妙的q与优化，回应来自qK世界的真实需求?/span>
黄志?span style="font-size:16px;font-family:楷体;color:blue">Q清华大学计机p?span lang="EN-US">2004U校友）
2014q加入港大以来，凭借不懈努力，黄志毅已陆箋解决了图灵奖得主理查?span lang="EN-US">·卡普Q?span lang="EN-US">Richard KarpQ提出的三十q开N题（늛、器官捐赠等应用Q，以及U上q告中显C广告、广告关键字两个十几q开N题。迄今ؓ(f)止，他已发表40余篇会(x)论文?span lang="EN-US">2015q_他获得算法和架构q行性年?x)?span lang="EN-US">SPAAQ最佌文奖Q是亚洲院校的首位获奖者；2020q_他获得计机U学基础q会(x)Q?span lang="EN-US">FOCSQ最佌文奖Q是q?span lang="EN-US">14q来首次、亚z院校第二位获奖者?/span>
无限风光在险峎ͼ无限风光在前斏V算法世界的攀M旅从来没有真正的l点。对黄志毅来_攀ȝ妙处在于遍寻而得的完\Uѝ登临之后的短暂喜?zhn)Q更在于历经艰辛触摸最高“岩点”后l箋走向下一面未知峭壁的无畏勇气Q以及因此而锤炼出来的不断开阔视野、不断向上进取的蓬勃生命力?/span>
向不定的未知进?/span>
对理机U学家而言Q每个^静时刻都可能蕴藏着“头脑风暴”。有Ӟ周末坐在C陪伴孩子玩游戏，黄志毅不知不觉就游别处Q回惌v某个法问题。对理论计算机科学的q种痴迷Q还要从他十几年前在清华大学Q简U“清华”）“姚班”读书的l历说v?/span>
2004q_囄奖得d期智院士全职回到清华Q讲授计机与科学技术系评。其_他萌生了创立?/span>清华学堂计算机科学实验班?/span>的想法，q于ơ年通过选拔考试Q正式组Z一个包?span lang="EN-US">30名数学和计算机尖子生的班U，q便是第一?span lang="EN-US">?/span>姚班?/span>。黄志毅q入W一?span lang="EN-US">?/span>姚班?/span>时正d三。早前因在高中数学竞赛中表现优异Q他被保送清华计机p；之后又出于对数学和物理的兴趣Q上q学?span lang="EN-US">?/span>数理实验?span lang="EN-US">?/span>的课E。这些无意中Z考入?/span>姚班?/span>打下了一定基?/span>
“姚班”致力于培养与美国麻省理工学院、普林斯大学等世界一高校本U生h同等Q甚x高竞争力的领跑国际的拔尖创新计算机科学h才。姚期智院士为班内学生专门制订培L案，其是他开讄理论法评Qo目一新。同Ӟ他还邀请微软亚z研I的研I员为学生教授分布式计算、操作系l等评Q教材、习(fn)题在当时都十分先q。集l优U的老师、聪明的同学Q“姚班”内部Ş成了热烈向学的氛_黄志毅深受熏Ӟq渐对姚期智院士研究的理机U学产生了兴。理机U学Q即计算机科学的数学基础Q包括各U计问题的法设计及其旉复杂度、空间复杂度{方面的数学分析Q十分契合黄志毅的兴和专长?/span>
2008q毕业后Q黄志毅前往国宑֤法尼亚大学读博深造。导师萨姆帕?span lang="EN-US">·坎南Q?span lang="EN-US">Sampath KannanQ是国计算机学?x)?x)士；另一位导师亚?span lang="EN-US">·|斯Q?span lang="EN-US">Aaron RothQ是斯隆奖得主，两位导师都在各自的研I域造诣非凡。其_黄志毅展开了积极的学术交流Q接触了理论计算机科学领域的多个方向Qƈ对其中的在线法和算法博弈论q行了较多研IӞ与谷歌研I和微软研Iq行了合作。不仅如此，博士期间Q他q提Z?/span>把算法{化ؓ(f)ȀqҎ(gu)制的一般性方?span lang="EN-US">?/span>的代表性成果，接连获得?span lang="EN-US">2012q西蒙斯理论计算机科学奖学金Q全一共有5名获奖者）?span lang="EN-US">2013q拉比诺夫博士论文奖{重要奖V?/span>
取得博士学位后，黄志毅又在斯坦福大学跟随哥d?dng)奖得主蒂姆·拉夫加登Q?span lang="EN-US">Tim RoughgardenQ做了一q博士后研究Q在q期间他认真思考了接下来的U研规划。彼时的中国Q理机U学研究刚刚兴v。作为第一?span lang="EN-US">?/span>姚班?/span>学子Q学成以后像姚期智院士当初一样回国效力，一直是黄志毅的期望所在。于是，2014q他选择回国Qƈ加入紧邻家乡q东、历史?zhn)久的香港大学Q以下简U?span lang="EN-US">?/span>港大?/span>QQ教。刚入职Q他׃359名杰出青q学者计划申误中脱颖而出Q成?span lang="EN-US">2014?015q度香港研究资助局所颁发?span lang="EN-US">22个杰出青q学者奖Q?span lang="EN-US">Early Career AwardQ获奖者之一。在港大学术氛围厚的校园中Q黄志毅由此开启了不确定信息下的优化问题研I?/span>
不确定信息下的优化问题，是一个有别于传统法研究的方向。传l算法研I考虑的是如何在时间、存储空间等计算资源的限制条件下解决不同的计问题；而不定信息下的优化问题则是在把信息本n视作一U计资源的同时Q在信息不充的限制条g下设计算法解决问题。以搜烦引擎上匹配搜索请求和q告商的问题ZQ一斚wQ算法在匚w某个搜烦h时无法准预知将来还有什么样的请求，因此q类问题需要处理将来的不确定性；另一斚wQؓ(f)扑ֈ好的匚wQ算法想要知道广告商对于不同关键字的价D量，而这个信息只有广告商自己知道Q于法而言是不定的?/span>
2017q黄志毅Q前排左三）参加?span lang="EN-US">?/span>不确定信息下的算法与优化?/span>Z题的日本湘南?x)?/span>
Ҏ(gu)信息不确定性的U类及实际考量Q黄志毅主要对在U算法与法博弈Z个方向进行了q。在q两大算法领域，又矗立着C清的U研险峰Q每座险峰天然Ş成多面峭壁。几十年来，光荆棘丛生、云雄l、神U莫，引得钟情理论计算机科学的“探险家”“攀登者”不q万里前来拜谒，苦思冥惟뀁n体力行，L登顶的希望。黄志毅兴致勃勃投n其中Q向不确定的未知正式q发?/span>
破解问题与推q应?/span>
在线法领域Q黄志毅先后聚焦非线性目标函数在U优化问题、传l在U匹配问题、完全在U匹配问题开展研I。算法博弈论斚wQ他对近q来的一个研I热点——如何在买家价值的概率分布信息不的场景中q行机制设计——进行了一pd创新研究Q论文发表于理论计算机科学的旗舰?x)议计算理论q会(x)Q?span lang="EN-US">STOCQ和计算机科学基q会(x)Q?span lang="EN-US">FOCSQ?/span>
调度和资源分配是非线性目标函数的在线优化的两cȝ兔R题?span lang="EN-US">2014q_黄志毅针对如何实时调整处理器速度Q以辑ֈ能源消耗与工作处理效能间的最优^衡的问题展开研究。这当中有个关键点在于，能耗往往是处理器速度的二ơ或三次函数而ƈ非线性，Ҏ(gu)黄志毅提Z一套基?span lang="EN-US">Fenchel对偶性的法设计和分析框Ӟq以此ؓ(f)基础设计了此问题的理论最优算法?span lang="EN-US">2015q_他进一步把l果扩展到无法准预处理每个工作所需计算资源之数量的短视模型Qƈ在此模型下提Z一个新法L仉K短视模型下的法决策。相兌文获得了高性能计算理论斚w的顶?x)算法和架构q行性年?x)?span lang="EN-US">SPAAQ颁发的最佌文奖?span lang="EN-US">2016q_黄志毅从Fenchel对偶性框架中提炼Z般性的理论Ҏ(gu)Q从而一ơ性地解决了一大类非线性目标函数的覆盖及装问题。《美国计机学会(x)法与计理论通讯》（ACM SIGACT NewsQ在U算法专栏的2016qȝ中认论?span lang="EN-US">?/span>l一、简化，q改q了许多现有l果?/span>QƈU这一论文?span lang="EN-US">?/span>此年度最引h瞩目的结?span lang="EN-US">?/span>?/span>
匚w是最基础的优化问题之一Q而它的在U版本也是在U算法中最受关注的方向之一。传l在U匹配模型在器官UL、在U广告匹配等应用场景的徏模中十分常见。由于理机U学中常用的最坏情形分析框架在q些场景下往往不能很好地刻d际问题的特点Q所以近q在U匹配的热点和难点之一是在模型中引入一定的随机性ƈ在此前提下设计算法。此外，传统在线匚w中有一些经q?span lang="EN-US">10q以上研I仍未有H破的开放性问题?span lang="EN-US">2020q_l过多年U篏和思考，黄志毅针?span lang="EN-US">2005q提出的q告关键字问题和2009q提出的昄q告问题提出了名为在U相关选择的新法技巧，一丄破了q两个开放性问题的瓉。尤其值得一提的是，他关于解xC广告问题的工作获得?span lang="EN-US">2020q度计算机科学基q会(x)Q?span lang="EN-US">FOCSQ的?x)议最佌文奖Q是历史上第二次有亚z院校的学者获奖，也是q?span lang="EN-US">14q来的首ơ?/span>
传统的在U匹配理论只处理二分囑配，比如搜烦h和广告商的匹配。而在包括叫R、拼车服务在内的一些新应用场景中，法所需要处理的往往是一般图的在U匹配。从实际场景出发Q?span lang="EN-US">2018q黄志毅提出了完全在U匹配模型及相应的算法分析框Ӟ从而一般图的在U匹配理论研I成为可能，q被认ؓ(f)?span lang="EN-US">?/span>首次把图灵奖得主理查?span lang="EN-US">·卡帕{提出的法推广C般图q取得好?span lang="EN-US">0.5的近似比?/span>。由于研I具h(hun)|后箋叫Rq_Lyft、麻省理工学院、斯坦福大学{研I组都参考用了q个模型?/span>
此外Q在法博弈论方面，关于“如何在贝叶斯模型下从数据中学习(fn)叶斯先验概率分布的近似Ş式，从而用较少的数据得出利润最大化的近似最优机制”的问题Q针对算法的采样复杂度，?span lang="EN-US">2015qvQ黄志毅接连产出了一pd研究成果?/span>
—?span lang="EN-US">2015q_黄志毅发Cq一问题与统计机器学?fn)理论及信息Z间的联系Q其中前者能用于分析采样复杂度的上界Q而后者能用于分析采样复杂度的下界。基于这些工P他解决了单个买家单个物品情Ş下的采样复杂度问题，在业内引起广泛关注?/span>
—?span lang="EN-US">2016q_黄志毅把Zl计机器学习(fn)理论的算法思\及分析的Ҏ(gu)推广C多个买家的情形，从而改q了光样复杂度上界?/span>
—?span lang="EN-US">2017q_黄志毅注意到实际场景中的法需要不断利用新的数据更新所学到的机制和定h(hun)Q这可以视作一U在U学?fn)。通过提出一套新的多度在线学习(fn)理论Q他设计了新的算法ƈ获得了最优的理论l果。这套新理论后来在传l机器学?fn)理论的模型选择问题中也得到了应用?/span>
—?span lang="EN-US">2018q_黄志毅注意到此前的相关研I中一般假设买家ƈ不会(x)针对卖家的算法对自n行ؓ(f)q行{略性的调整Q而一些后l研I指个假设过度简化了问题Qƈ证明了买家的{略性行为可能大q降低卖家算法所获得的利润。据此，他提Z一套基于差分隐U的法工具Q这套工具在所需要学?fn)的机制l构相对单时可以有效地降低买家的{略性行为?/span>
—?span lang="EN-US">2019q_黄志毅基于此前研IӞ重新提出了一套与之前框架截然不同的基于信息学的新Ҏ(gu)Q从而彻底解决了多个买家情Ş下采样复杂度问题Q被学界视ؓ(f)采样复杂度方向的一?span lang="EN-US">?/span>H破性结?span lang="EN-US">?/span>?/span>
—?span lang="EN-US">2020q_黄志毅进一步将q一pd采样复杂度理论应用到更困隄市场划分问题上，q获得了q个问题的首个多式采样复杂度上界?/span>
以上相关成果获得了包括算法博弈论的奠及理论计算机科学领域高规格奖哥德尔奖得主诺姆·尼桑（Noam NisanQ、蒂?span lang="EN-US">·拉夫加登Q以及奈望林U_得主h坦丁诺斯·达斯卡拉基斯Q?span lang="EN-US">Constantinos DaskalakisQ、图灵奖得主姚期智等在内的著名学者的引用研究?/span>
黄志毅在中国计算机协?x)?span lang="EN-US">CCFQ启Z(x)上以?/span>数据驱动的拍卖机制设?span lang="EN-US">?/span>Z题开展讲?/span>
从讲C聆听基础评應|学子Q到成ؓ(f)与诸位恩师、学界前辈娓娓而谈的学术同行，黄志毅的成长肉眼可见。“我的进步除了离不开姚院士的指引Q也深深受益于我的博士生导师萨姆帕斯·坎南和亚伦L(fng)斯，以及博士后导师蒂姆h夫加癅R微软研I实习(fn)时的导师基?dng)·d瓦马塔尔Q?span lang="EN-US">Nikhil DevanurQ。邓铁、滕华、孙晓明{学界前辈，亦多ơ提携指教，l予我宝늚?span lang="EN-US">?/span>一q又一q_现实世界的诸多问题凝于脑P伴随一ơ次复杂的推演、解题，黄志毅的法险峰攀M旅渐入佳境?/span>
明d格物 探烦不止
港大的校徽上镌刻着“明h物?span lang="EN-US">4个字?span lang="EN-US">?/span>明d?/span>是彰显徯Q?span lang="EN-US">?/span>格物?/span>是探究事物原理。在快节奏的香港Q港大给师生营造了一个安静舒适的学术天堂Q去除了躁Qƈ不一呌求论文出。在q?span lang="EN-US">10q的港大生中，黄志毅体?x)最大的是q种让h富有严的学术自由度?/span>
“理机U学研究的成果出周期相对较长，但是学院q没有一刀切地下达性Q务指标，而是重了大家的学科特点。学院领D很注重培dL师的独立U研能力Q鼓励我们先发展自己的团队和感兴的U研方向Q而不是与资深的教授合作尽快出成果。”正是在q种氛围下，黄志毅没有跟风选择热门方向Q而是坚持自己的研I兴，逐渐带领团队步入正轨Q顺理成章地形成了一pd有媄响力的学术成果?/span>
目前Q黄志毅团队q_每年招收1名博士研I生Q课题组的博士研I生一般ؓ(f)4?span lang="EN-US">5名。此外，每年夏天Q他q会(x)指导2?span lang="EN-US">6名来自国内外的本U生做研I。短期的师生~分l束后，如果互相考察满意Q将?x)l进行ؓ(f)期一q的合作研究。而这些本U生中的一部分便是来自清华?span lang="EN-US">?/span>姚班?/span>?span lang="EN-US">?/span>姚班?span lang="EN-US">?/span>一边传承着姚期智院士的学术钵Q一边协作创斎ͼ人才辈出?/span>
黄志毅看来，理论计算机科学的研究模式Q某U意义上是一U学徒制。“我跟学生是合作关系。我们的区别可能主要在于我经验更丰富、资历更深。在日常研究中，他们?x)通过N研究Q学?fn)我的选题思\、解题思\、提问思\{。这U研I模式，没有一套完整的教材Q导师更需要对学生q行a传n教。?/span>
为此Q黄志毅对学生提Z他认为最重要的几点要求。一是要培养寚w价值选题、高品位选题的认知。“十多年前，我去宑֤法尼亚大学读博，pMd介会(x)上讲了许多话Q我至今唯一记得的一句就是‘读博这几年Q最重要的一件事是形成研究的品位，知道选题的好与坏’。”二是做理论计算机科学研IӞ需要在数学思维的运行、数学工L(fng)使用上有_的成熟度Q能够随机应变，x设法推进研究。三是养成好?fn)惯。“我l常跟学生强调，要保持良好的阅读论文的习(fn)惯，除了自己方向的论文外，q要可能了解一些其他相关领域的前沿学术成果Q拓展知识储备、学术视野。”至于，很多人关心的论文发表Q黄志毅反而对此抱着L的态度Q“论文发表有一定的q气成分在，看学生个人造化好Q急不来”?/span>
即便当了多年老师Q黄志毅也始l}记自q学生w䆾。在姚期智院士众多的提点之语中，那句“做研究的hQ不需要在同一个问题上反复证明自己”曾如一颗石子投入湖_在黄志毅的心里激起圈圈涟漪，后来成ؓ(f)他时时勉pqDQ激q他不断尝试、不断挑战，每隔一D|间便停下来回ȝ。而决定攀L功与否的Q往往是微末的细节、一늚犹U。如今，相比获得“最佌文”，做出新颖的科研探索、践行美好的U研品位Q更让黄志毅心向往之?/span>
在线法研究的问题根源于未来发生的不确定性，法博弈论关注的是与自私MUh信息的不定性相关的问题。未来，在不定性下优化的广泛背景下Q黄志毅希望对相x向上未解决的挑战l箋展开探烦。在战略环境中的学习(fn)、在U优化的U性程序层ơ结构、融合来自不同领域的在线决策{略……一座险峰、一面面峭壁Q也正向q位勇敢的攀登者发出盛情邀U?/span>
清华校友M(x)服务?/span>
清华校友M(x)订阅?/span>