由Jeff Dean领衔的Google Research年终总结系列「Google Research, 2022 & beyond」第五期，本期的主题是算法上的进步（algorithmic advances），撰写作者是谷歌研究院的副总裁Vahab Mirrokni.

往期链接：

1. 超详超硬Jeff Dean万字总结火热出炉！图解谷歌2022年AIGC、LLM、CV三大领域成就
   

2. 谷歌2022年度回顾：让AI更负责任，主要做了4点微小的工作
   

3. Jeff Dean发推：谷歌超硬年终总结「第三弹」来了！大力发展Jax
   

4. 让大模型的训练和推理，比更快还更快！谷歌2022年终总结第四弹
   

稳健的算法设计是整个谷歌系统的基础，特别是对于机器学习和人工智能模型来说，稳健性显得更加重要。

因此，开发具有更高效率、更强性能以及更快速的算法仍然具有相当高的优先级，可以提升从搜索和广告到地图和 YouTube 等各种服务的能力。

Google Reserach一直走在该领域前沿，开发了许多创新性的算法，涉及的领域包括隐私安全的推荐系统、大规模机器学习的可扩展解决方案等。

下面介绍一些Google在2022年提出的最先进的技术包括可伸缩性、隐私、市场算法和算法基础等。

可伸缩算法: 图、聚类和优化

随着处理大规模数据集的需求增加，复杂算法的可伸缩性（scalability）和可靠性（reliability）在改进算法的可解释性、健壮性和速度上仍然具有较高优先级。

谷歌开发的新算法可用于处理各个领域的大型数据集，包括无监督和半监督学习、基于图的学习、聚类和大规模优化。

系统中的一个重要组成部分是建立一个相似图（similarity graph），节点为对象，边表示对象之间的相似度。为了提高可伸缩性和速度，邻接图应该是稀疏的。

谷歌提出了一种叫做 STAR 的两跳扩展技术（2-hop spanner technique），是一种高效的分布式图形生成策略，并展示了它如何在理论和实践上显著减少相似度计算的数量，在生成高质量的图形学习或聚类输出的同时生成更稀疏的图形。

论文链接：https://neurips.cc/Conferences/2022/ScheduleMultitrack?event=53141

比如说对于具有10T条边的图，在成对相似性比较和运行时间加速方面实现了约100倍的改进，而质量损失可以忽略不计，谷歌已经应用这个想法来开发用于度量和最小规模聚类的大规模并行处理算法。

论文链接：https://proceedings.mlr.press/v139/dhulipala21a.html

在广义的聚类背景下，谷歌开发了第一个具有线性时间层次聚集聚类(HAC)算法和第一个对数深度 HAC 并行算法 DBSCAN，该算法在100B 边图上实现了50倍的加速。

并且还针对不同类型的聚类问题设计了改进的次线性算法，如几何连接聚类、常数轮相关聚类和完全动态 k 聚类。

受到多核处理(例如 GBBS)成功的启发，研究人员开始着手开发能够在单个多核机器上处理具有100B 边的图的图挖掘算法，其中最大的难题是实现快速(例如，次线性)并行运行时间(例如，深度)。

在之前社区检测和相关聚类工作的基础上，谷歌开发了一个 HAC 算法叫做 ParHAC，具有可证明的多对数深度和近线性工作，并实现了50倍的加速。

论文链接：https://openreview.net/pdf?id=LpgG0C6Y75

例如，ParHAC 只需要约10分钟就可以在一个超过100B 边的图上找到一个近似的亲和层次结构，而在一台机器上找到完整的 HAC 则需要约3小时。

继之前在分布式 HAC 上的工作之后，使用这些多核算法作为分布式算法中的一个子例程来ter-scale的图。

2022年，谷歌在图形神经网络(GNN)方面也得到了一些进展。

论文链接：https://www.jmlr.org/papers/volume23/20-852/20-852.pdf

研究人员开发了一个基于模型的分类方法，统一了图学习方法，实验中还从数千个不同结构的图表中发现了对 GNN 模型的新思路，提出了一种新的混合体系结构，以克服现有 GNN 解决基本图问题(如最短路径和最小生成树)的深度要求。

此外，为了将这些成果带到更广泛的社区中，谷歌发布了用于在 TensorFlow (TF-GNN)中构建图形神经网络的旗舰建模库的三个版本，其中的亮点包括一个模型库和模型编排 API，这使得编写 GNN 解决方案变得更加容易。

在NeurIPS’20上的关于大规模图形挖掘和学习研讨会之后，谷歌在 ICML’22举办了一个关于基于图形的学习的研讨会，以及在 NeurIPS’22举办了一个关于 TensorFlow 中 GNN 的教程。

论文链接：https://dl.acm.org/doi/abs/10.1145/3474717.3483961

谷歌还提出了一个谷歌地图解决方案，可以有效地计算道路网络中的可选路线、持续故障(例如，道路关闭和突发事件等)。

文中还展示了该模型如何显著优于现实世界中的道路网络的最先进的plateau and penalty方法。

在优化方面，谷歌开源了 Vizier，一个强大的黑盒优化和超参数调优库。

研究人员还为线性规划(LP)解决方案开发了新的技术，解决了由于依赖矩阵分解而导致的可伸缩性限制，限制了并行性和分布式方法的发展。

代码链接：https://github.com/google/or-tools

为此，研究人员开源了一个称为原始-对偶线性规划(PDLP)的原始-对偶混合梯度(PDHG)解决方案，一个新的一阶求解器，可用于解决大规模 LP 问题。

PDLP 已经被用来解决现实世界中多达12B non-zeros的问题(内部分布式版本扩展到92B non-zeros)，PDLP 的有效性是理论发展和算法工程相结合的结果。

隐私和联邦学习

在提供高质量服务的同时尊重用户隐私仍然是所有 Google 系统的首要任务，该领域的研究涉及许多产品，并使用了来自差分隐私(differential privacy，DP)和联邦学习的原则。

首先，为了解决用 DP 训练大型神经网络的问题，研究人员在算法上取得了一些进展。

在早期工作的基础上，继续开发了一个基于 DP-FTRL 算法的 DP 神经网络，用于矩阵分解的算法DP-FTRL。

论文链接：https://arxiv.org/pdf/2103.00039.pdf

这项工作表明，人们可以设计一个数学程序，以优化超过一个可能的 DP 机制的大集，以找到那些最适合特定的学习问题。

在神经网络和核方法的 DP 学习中，研究人员还建立了与输入特征维数无关的边界保证，并且进一步将这个概念扩展到更广泛的机器学习任务，以不到原来1/300的计算量就可以匹敌基线的性能。

对于大型模型的微调，研究人员认为，一旦预训练后，这些模型(甚至与 DP)基本上操作在一个低维子空间，从而绕过了 DP 强加的维数灾难。

在算法方面，为了估计一个高维分布的熵，可以得到局部 DP 机制（即使每个样本只有一个比特可用也能工作）和有效的shuffle DP 机制。

论文链接：https://arxiv.org/abs/2210.15178

研究人员提出了一种更加精确的方法来同时以私密的方式估计数据库中最受欢迎的项目，并在 Plume 库中应用了这种方法。

此外，在近似演算法计算(MPC)模型中展示了接近最佳的 DP 集群大规模并行处理机，进一步改进了以前在可伸缩和分布式设置方面的工作。

论文链接：https://arxiv.org/abs/2107.14527

另一个有前景的研究方向是隐私和流媒体的交叉，研究人员提出了一个近似最优的近似空间权衡私有频率矩和一个新的算法私有计数不同的元素在滑动窗口流模型，还提出了一个研究对抗流（adversarial streaming）的通用混合框架。

针对安全性和隐私性交叉的应用程序，谷歌开发了安全、私有和通信效率高的新算法，用于测量交叉出版商的覆盖范围和频率。

世界广告商联合会（World Federation of Advertisers）已经采用这些算法作为他们测量系统的一部分，在后续的工作中，研究人员还开发了新的协议，是保证安全的且私有的，用于在 DP 的两服务器模型中计算稀疏直方图。

论文链接：https://dl.acm.org/doi/10.1145/3548606.3559383

从计算和通信的角度来看，这些协议都是高效的，比标准方法要好得多，并且结合了草图、密码学和多方计算以及 DP 等工具和技术。

虽然目前已经用 DP 训练了 BERT 和变压器，但理解大语言模型(LLM)中的训练样例记忆是评估其隐私性的一种启发式方法。

论文链接：https://arxiv.org/abs/2207.00099

特别是研究了 LLM 在训练中忘记(潜在记忆)训练例子的时间和原因，研究结果表明，以前看到的例子可能会以后看到的例子为代价来观察隐私的好处。

论文链接：https://arxiv.org/abs/2202.07646

研究人员还量化了 LLM 发出记忆训练数据的程度。

市场算法与因果推理

谷歌在2022年继续研究如何改善在线市场（online marketplaces）。

例如，最近广告拍卖研究的一个重要领域是自动投标在线广告的研究，其中大多数投标是通过代理投标人，代表广告商优化更高层次的目标。用户、广告商、投标人和广告平台，导致这个领域存在一些问题。

继之前分析和改进自动竞价拍卖机制的工作之后，谷歌继续研究如何在自动化背景下改进在线市场，同时考虑到了不同方面，如用户体验和广告预算。

论文链接：https://arxiv.org/abs/2207.03630

研究结果表明，适当结合机器学习的建议和随机化技术，即使在非真实的拍卖，可以有力地改善整体福利在均衡的自动竞价算法。

除了自动竞价系统，谷歌还研究了复杂环境下的拍卖改进措施，例如，买家由中介代表，多种告形式，每个广告可以显示在几个可能的变体。在最近的一篇survey中，谷歌总结了相关工作。

论文链接：https://www.sigecom.org/exchanges/volume_20/2/BHAWALKAR.pdf

除了拍卖，谷歌还研究了合同在多代理人和对抗性环境中的使用，在线随机优化仍然是在线广告系统的重要组成部分，在最优投标和预算节奏方面有着广泛的应用。

在长期的在线分配研究的基础上，研究人员最近发表了关于双镜像下降（dual mirror descent）的介绍，一种简单、健壮和灵活的在线分配问题的新算法，可以抵抗广泛的对抗性和随机输入分布，并且可以优化经济效率之外的重要目标，如公平性。

结果还表明，通过裁剪双镜下降到日益流行的特殊结构回报的支出约束，可以优化广告客户的价值，其有着广泛的应用，并且随着时间的推移已经被用来帮助广告商通过更好的算法决策获得更多的价值。

论文链接：https://arxiv.org/abs/2109.03173

此外，根据在机器学习、机制设计和市场相互作用方面的工作，谷歌研究了非对称拍卖设计的Transformer，为no-regret学习的买家设计了效用最大化策略，并开发了新的学习算法来出价或在拍卖中定价。

复杂的在线服务的一个关键组成部分是能够通过实验测量用户和其他参与者对新干预措施的反应，准确估计这些因果效应的一个主要挑战是处理这些实验的控制单元和治疗单元之间的复杂相互作用(或干扰)。

论文链接：https://openreview.net/pdf?id=hqtSdpAK39W

将图形聚类和因果推理专业知识结合起来，扩展了之前在这个领域的工作成果，在灵活的响应模型和新的实验设计下改进了结果。

论文链接：https://proceedings.neurips.cc/paper/2021/file/48d23e87eb98cc2227b5a8c33fa00680-Paper.pdf

当treatment 任务和度量测量发生在二分平台的同一侧时，可以更有效地减少这些相互作用，文中还展示了如何将综合控制和优化技术相结合来设计更强大的实验，特别是在小数据情况下。

算法基础和理论

谷歌还通过解决长期存在的「开放问题」来继续基础算法研究。

论文链接：https://dl.acm.org/doi/pdf/10.1145/3519935.3520054

一篇简明扼要的论文解决了一个40年前的悬而未决的问题: 是否存在一种机制，在买方价值弱于卖方成本的情况下，保证交易收益的一部分不变。

论文链接：https://dl.acm.org/doi/pdf/10.1145/3519935.3520011

另一篇论文得到了经典的和高度研究的 k- 均值问题的最新近似，还改进了相关聚类的最佳逼近，突破了2的障碍逼近因子。

并且在动态数据结构方面的工作解决了最小成本和其他网络流量问题，在采用连续优化技术解决经典的离散优化问题方面取得了突破性进展。

总结

设计有效的算法和机制是谷歌大规模系统的关键组成部分，这些系统需要以关键的隐私和安全考虑来稳健地处理大规模数据。

指导思想是开发具有坚实理论基础的算法，这些算法可以有效地部署在产品系统中，此外，通过开放一些最新颖的开发和发布它们背后的高级算法，将许多这些进步带给了更广泛的社区。

在这篇博客中，谷歌的研究人员讨论了算法在隐私、市场算法、可扩展算法、基于图表的学习和优化方面的进步。

随着朝着人工智能优先、自动化程度更高的谷歌迈进，开发健壮、可扩展和保护隐私的机器学习算法仍然是当务之急，对开发新的算法和更广泛地部署保持热情。