12月29日，软件学院举办“智能・软件・未来”论坛第19期、第20期，邀请中国人民大学何昆副教授和中国科学院数学与系统科学研究院王长军副研究员分别作题为“Sinkhorn-Knopp算法的相变”和“Interdicting Max-Vertex-Cover Randomly under Matroid Constraints”的学术报告。

在对神经网络和大模型等进行预训练时，数据对齐是一项十分重要的操作。按照代数的观点，对数据对齐效果的衡量可以转化为计算两个矩阵之间的距离这一问题，而这又可以进一步转化为如何对一个矩阵的元素进行放缩使其变成一个行和和列和均为数1的矩阵，即矩阵放缩问题。矩阵放缩同时也是经典的最优传输问题的核心步骤。Sinkhorn-Knopp算法是矩阵缩放的标准算法，何昆在报告中对Sinkhorn-Knopp算法给出了新的分析。该分析表明，对于几乎所有的非负矩阵，Sinkhorn-Knopp算法在对数次迭代内即可收敛，这解释了为什么该算法是高效的。对于矩阵密度大于1/2的一个正矩阵的族，Sinkhorn-Knopp算法至少需要sqrt{n}/varepsilon次迭代才能达到近似收敛，并且这一迭代轮次数是紧的。该结果完整刻画了Sinkhorn-Knopp算法关于矩阵密度的相变现象。

阻断问题来源于网络上leader和follower之间的博弈。leader在网络上随机地选择一些顶点进行保护，而follower随机选择一些顶点进行攻击。Leader的目标是确定一个随机化的选择顶点的策略，使得follower的期望收益最小。这是一个双层优化问题。王长军对这一类双层阻断问题给出了一个通用的近似求解框架以及相应的分析技术。在该双层优化问题中，follower要求解的问题可表达为一个整数线性规划。在报告中证明了该线性规划的整数间隙至少为4/3，并且该间隙是紧的。当内层的follower的优化问题被相应的线性规划松弛替代后，报告证明了leader的外层优化问题有一个多项式时间的2-近似算法。在这个求解框架中把这两部分合起来，就得到了原双层优化问题的一个近似比为8/3的近似算法。

何昆，中国人民大学副教授。博士毕业于中科院计算所，曾任中科院计算所助理研究员、副研究员，获中国科学院院长特别奖、CCF优秀博士论文奖、计算所百星等荣誉。主要从事理论计算机领域尤其是概率方法的研究，解决多个由哥德尔奖得主、莱布尼茨奖得主提出的开放问题，在理论计算机顶会STOC、FOCS、SODA上发表论文多篇。

王长军，中国科学院数学与系统科学研究院副研究员。主要从事算法博弈与机制设计、组合优化等方向的理论研究。目前已在包括OR、MOR、POM、EC、WINE等相关领域重要国际期刊及会议发表多篇论文。主持国家自然科学基金面上项目等多个科研项目，入选中国科协青年人才托举工程，获中国运筹学会青年科技奖。

（文/图：张鹏 责任编辑：戴鸿君）