静5前沿讲座回顾 | Santiago Balseiro谈在线分配问题中的对偶镜像下降方法

关键词：静5前沿讲座

编者按

2022年11月4日，Columbia University 的Santiago Balseiro 教授带来了题为“The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems”的报告。报告内容基于其与 Haihao Lu 和 Vahab Mirrokni 于2022年发表在 Operations Research 上的同名论文。报告由中心邓小铁教授主持，相关内容通过蔻享学术、Bilibili 同步直播，线上线下数百人观看。

Santiago Balseiro教授做线上报告

带有资源限制的在线分配问题（online allocation problems with resource constraints）是计算机科学和运筹学中的重要问题。在这一问题中，在每个时间点，我们会收到一个请求（request）。面对每个请求，我们需要选择一个动作（action），并由此确定性地获得奖励（reward）并造成一些资源的消耗（consumption）。我们的目标是在有限的资源下尽可能的最大化累积的收益。这一问题在现实中有诸多的应用，包括在线广告（online ad）中的报价、收入管理（revenue management）以及食品捐赠（food donation）等等。其的挑战之处在于，在每一时刻我们并不预先知道未来的请求如何，而怎样面对未来的不确定性而选择当下的动作也正是这一问题的难点。

为了判断一个在线决策策略的好坏，我们将其带来的总收益与已知所有未来请求时的最优总收益进行比较。

针对请求中收益函数和消耗函数的特征，文章考虑了多种输入模型，包括从未知分布中独立抽取的随机模型、敌对模型、以及介于之间的有敌对干扰的模型，如遍历性模型或周期性模型等。文章希望能够设计与输入模型无关的算法。

为了解决这一问题，文章从拉格朗日对偶性的角度出发。利用这一方法，文章对于任意对偶系数都能给出最优总收益值的一个上界。而对于任意对偶系数，对偶的方法都能够将对偶系数看作调价参数，对每一轮分别给出相应的最优控制策略。然而，这里值得注意的是，问题的结构导致了最优的对偶参数是未知的。从而，文章的主要问题转移到迭代更新对偶参数上。

为了完成这一点，文章采用了经典的在线优化方法——镜像下降方法，其能够尽可能最大化对偶函数对时间的累计和。利用这一方法，文章进一步构造了相应的在线对偶镜像下降算法。

值得注意的是，镜像下降方法在对 Bregman 散度（Bregman divergence）的不同选取下能够复原多种常见的在线凸优化方法，包括在线梯度下降（online gradient descent）、在线乘性权重更新（online multiplicative weights update）等。

从直觉上讲，整套在线对偶镜像下降算法的逻辑是，当某次请求的消耗较多时，相应的对偶系数就会提高，资源的价格也会相应提高，导致之后的选择趋于保守。反之亦然。这一“负反馈”特性使得这一算法面对多种不同的输入模型都能保持很好的鲁棒性。

讲者在介绍这一算法的理论表现之前，首先介绍了其在在线线性规划（online linear programming）和带有预算的重复拍卖的报价（bidding in repeated auctions with budgets）这两个问题上的应用。

讲者最后介绍了在线对偶镜像下降算法的理论表现。假设  为总时间。在输入模型为随机模型时，算法可以达到  的悔（regret），这一表现在理论上是最优的。在输入模型为敌对模型时，算法可以达到最优的近似竞争比（asymptotically competitive ratio）。而在介于中间的有敌对干扰的模型中，算法的悔为  和全体输入分布的总偏差（total deviation）的和，这也是最优的。

最后，报告总结了这一算法的诸多优势。报告后，讲者回答了同学们的踊跃提问。

报告视频回放：

图文 | 陈炤桦

PKU daGAME

往期讲座

—   版权声明  —

本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。