稳健的算法设计是 Google 系统的基础，尤其是我们的 ML 和 AI 模型。因此，开发效率、性能和速度更高的算法仍然是重中之重，因为它为从搜索和广告到地图和 YouTube 等服务提供支持。Google Research 一直处于这项工作的前沿，开发了许多创新，从隐私安全的推荐系统到可扩展的大规模 ML 解决方案。2022 年，我们继续这一征程，并在几个相关领域取得了最新进展。在这里，我们重点介绍了我们在其中一些领域的进展，包括可扩展性、隐私、市场算法和算法基础。
· 可扩展算法：图形、聚类和优化
· 隐私和联合学习
· 市场算法与因果推理
· 算法基础与理论
可扩展算法：图形、聚类和优化
随着处理大规模数据集的需求不断增长，复杂算法的可扩展性和可靠性仍然是重中之重，这些算法还表现出更好的可解释性、稳健性和速度。我们继续努力开发用于处理各个领域的大型数据集的新算法，包括无监督和半监督学习、基于图的学习、聚类和大规模优化。
此类系统的一个重要组成部分是构建相似性图- 表示对象之间相似性的最近邻图。为了实现可扩展性和速度，这个图应该是稀疏的，而不会影响质量。我们提出了一种2 跳 spanner 技术（称为 STAR），作为一种高效的分布式图构建策略，并展示了它如何在理论和实践中显著减少相似性计算的数量，构建更稀疏的图，同时产生高质量的图学习或聚类输出。例如，对于具有 10T 边的图，我们展示了成对相似性比较的效果提高了约 100 倍，并且运行时间显著加快，而质量损失几乎可以忽略不计。我们之前曾应用这个想法开发了用于度量和最小尺寸聚类的大规模并行算法。更广泛地讲，在聚类领域，我们开发了第一个线性时间层次凝聚聚类(HAC) 算法以及第一个具有对数深度的 HAC 并行算法DBSCAN ，该算法在 100B 边图上实现了 50 倍的加速。我们还针对不同类型的聚类问题设计了改进的亚线性算法，例如几何链接聚类、常数轮相关聚类和完全动态 k 聚类。
受到多核处理（例如 GBBS）成功的启发，我们着手开发图挖掘算法，该算法可以在单个多核机器上处理具有 100B 条边的图。这里最大的挑战是实现快速（例如亚线性）并行运行时间（即深度）。 继我们之前在 社区检测和相关性聚类方面的工作之后，我们开发了一种用于 HAC 的算法，称为ParHAC，该算法具有可证明的多对数深度和近线性工作，并实现了 50 倍的加速。例如，ParHAC 仅需约 10 分钟即可在超过 100B 条边的图上找到近似的亲和力层次结构，而仅需约 3 小时即可在单台机器上找到完整的 HAC。继我们之前在分布式 HAC 方面的工作之后，我们将这些多核算法用作分布式算法中的子程序，以处理万亿级图。
2022 年，我们还在图神经网络(GNN) 方面取得了许多有趣的成果。我们提供了一个基于模型的分类法，统一了许多图学习方法。此外，我们从 GNN 模型在数千个结构各异的图中的表现中发现了它们的见解（如下所示）。我们还提出了一种新的混合架构，以克服现有 GNN 在解决基本图问题（例如最短路径和最小生成树）方面的深度要求。
GraphWorld中 50,000 个不同节点分类数据集中三种 GNN 变体（ GCN、APPNP、FiLM ）的相对性能结果。我们发现学术 GNN 基准数据集存在于模型排名不变的区域。GraphWorld 可以发现以前未探索过的图表，从而揭示有关 GNN 架构的新见解。
此外，为了将这些进步带给更广泛的社区，我们发布了三个旗舰建模库，用于在 TensorFlow 中构建图神经网络(TF-GNN)。亮点包括模型库和模型编排 API，可轻松编写 GNN 解决方案。继NeurIPS'20大规模图形挖掘和学习研讨会之后，我们在ICML'22上举办了基于图形的学习研讨会，并在NeurIPS'22上举办了 TensorFlow 中的 GNN 教程。
在“使用电流进行稳健路由”中，我们介绍了一篇最新论文，该论文提出了一种 Google 地图解决方案，可以高效计算道路网络中的替代路径，以抵御故障（例如封闭、事故）。我们展示了它在现实世界道路网络上的 表现如何显著优于最先进的平台和惩罚方法。
我们如何构建与道路网络相对应的电路的示例。电流可以分解为三个流，i 1、i 2和 i 3，每个流对应于从加利福尼亚州弗里蒙特到加利福尼亚州圣拉斐尔的一条可行替代路径。
在优化方面，我们开源了 Vizier，这是我们在 Google 的旗舰黑盒优化和超参数调整库。我们还为线性规划(LP) 求解器开发了新技术，以解决由于依赖矩阵分解而导致的可扩展性限制，这限制了并行性和分布式方法的机会。为此，我们开源了一种用于 LP 的原始对偶混合梯度(PDHG) 解决方案，称为原始对偶线性规划(PDLP)，这是一种用于解决大规模 LP 问题的新型一阶求解器。PDLP 已用于解决多达 12B 个非零值的实际问题（以及扩展到 92B 个非零值的内部分布式版本）。PDLP 的有效性归功于理论发展和算法工程的结合。
使用 OSS Vizier，多个客户端各自向服务 API 发送“建议”请求，服务 API 使用Pythia 策略为客户端生成建议。客户端评估这些建议并返回测量值。所有交易都存储起来以实现容错。
顶部
隐私和联合学习
在提供高质量服务的同时尊重用户隐私仍然是所有 Google 系统的首要任务。该领域的研究涵盖许多产品，并使用差分隐私(DP) 和联邦学习的原理。
首先，我们在多种算法上取得了进展，以解决使用 DP 训练大型神经网络的问题。在我们之前的工作的基础上，我们开发了矩阵分解 DP-FTRL 方法，这使我们能够启动基于DP -FTRL 算法的 DP 神经网络。这项工作表明，人们可以设计一个数学程序来优化大量可能的 DP 机制，以找到最适合特定学习问题的机制。我们还为神经网络和基于核的方法的 DP 学习建立了与输入特征维度无关的边际保证。我们进一步将这一概念扩展到更广泛的 ML 任务，以减少 300 倍的计算量达到基线性能。对于大型模型的微调，我们认为，一旦经过预训练，这些模型（即使使用 DP）基本上也在低维子空间上运行，从而避免了DP 带来的维数灾难。
在算法方面，为了估计高维分布的熵，我们获得了局部 DP 机制（即使每个样本只有 1 位可用，也能工作）和高效的shuffle DP 机制。我们提出了一种更精确的方法，以私密的方式同时估计数据库中最受欢迎的前k 个项目，并在Plume库中采用了这种方法。此外，我们展示了一种在大规模并行计算(MPC) 模型中用于 DP 聚类的近乎最优的近似算法，这进一步改进了我们之前针对可扩展和分布式设置的工作。
另一个令人兴奋的研究方向是隐私和流媒体 的交集。我们获得了隐私频率矩的近似空间权衡，并提出了一种在滑动窗口流媒体模型中隐私地计数不同元素的新算法。我们还提出了一种用于研究对抗性流媒体的 通用混合框架。
针对安全性和隐私性交叉领域的应用，我们开发了安全、私密且通信效率高的新算法，用于测量跨发布商的覆盖面和频率。世界广告联盟已将这些算法作为其测量系统的一部分。在后续工作中，我们开发了安全且私密的新协议，用于计算 DP 双服务器模型中的稀疏直方图。这些协议从计算和通信的角度来看都很高效，比标准方法的效果好得多，并且结合了草图、加密和多方计算以及 DP 的工具和技术。
虽然我们已经使用 DP 训练了BERT和transformers，但了解大型语言模型 (LLM) 中的训练示例记忆是一种评估其隐私性的启发式方法。具体来说，我们调查了LLM 在训练过程中何时以及为何会忘记（可能记忆的）训练示例。我们的研究结果表明，较早看到的示例可能会以牺牲较晚看到的示例为代价来获得隐私优势。我们还量化了LLM 发出记忆训练数据的程度。
顶部
市场算法和因果推理
我们还在 2022 年继续开展改进在线市场的研究。例如，广告拍卖研究最近的一个重要领域是研究自动竞价在线广告，其中大多数竞价都是通过代理竞价者进行的，这些竞价者代表广告商优化更高级别的目标。用户、广告商、竞价者和广告平台之间的复杂动态导致了这一领域的重大问题。继我们之前分析和改进自动竞价拍卖机制的工作之后，我们继续研究在自动化背景下改进在线市场，同时考虑到用户体验和广告商预算等不同方面。我们的研究结果表明，即使在非真实拍卖中，适当地结合ML 建议和随机化技术也可以显著改善自动竞价算法之间的均衡总体福利。
自动竞价在线广告系统的结构。
除了自动竞价系统之外，我们还研究了复杂环境中的拍卖改进，例如买家由中介 代表的环境，以及富媒体广告，其中每个广告可以以多种可能的变体之一显示。我们在最近的一项调查中总结了我们在这方面的工作。除了拍卖之外，我们还研究了在多代理 和对抗环境中使用合同的情况。
在线随机优化仍然是在线广告系统的重要组成部分，可用于优化竞价和预算节奏。基于我们在在线分配方面的长期研究，我们最近在博客中介绍了双镜像下降，这是一种用于解决在线分配问题的新算法，它简单、强大且灵活。这种最先进的算法可以抵抗各种对抗性和随机输入分布，并可以优化除经济效率之外的重要目标，例如公平性。我们还表明，通过根据越来越流行的支出回报约束的特殊结构定制双镜像下降，我们可以优化广告商价值。双镜像下降具有广泛的应用，并且随着时间的推移一直被用来帮助广告商通过更好的算法决策获得更多价值。
双镜像下降算法概述。
此外，根据我们最近在机器学习、机制设计和市场相互作用方面的研究成果，我们研究了用于非对称拍卖设计的变换器，为无悔学习的买家设计了效用最大化策略，并开发了新的学习算法来在拍卖中竞标或定价。
二分实验设计概述，用于减少实体之间的因果相互作用。
任何复杂的在线服务的一个关键组成部分是能够通过实验测量用户和其他参与者对新干预措施的反应。准确估计这些因果效应的主要挑战是处理这些实验的控制单元和治疗单元之间的复杂相互作用（或干扰）。我们结合了图形聚类和因果推理专业知识，扩展了我们之前在该领域的工作成果，在灵活的响应模型和新的实验设计下获得了更好的结果，当治疗分配和度量测量发生在二分平台的同一侧时，这种设计可以更有效地减少这些相互作用。我们还展示了如何结合合成控制和优化技术来设计更强大的实验，尤其是在小数据范围内。
顶部
算法基础与理论
最后，我们继续进行基础算法研究，解决长期存在的未决问题。一篇出人意料的简洁论文肯定地解决了一个四十年前的未决问题，即是否存在一种机制，可以保证当买方价值略高于卖方成本时，可以获得恒定比例的交易收益。另一篇最近的论文获得了经典且研究深入的k 均值问题的最新近似值。我们还改进了相关性聚类的最佳近似值，突破了 2 的障碍近似因子。最后，我们在动态数据结构上的工作解决了最小成本和其他网络流问题，为采用连续优化技术解决经典离散优化问题做出了突破性贡献。
顶部
总结
设计有效的算法和机制是许多 Google 系统的关键组成部分，这些系统需要在隐私和安全方面考虑周全的情况下稳健地处理万亿级数据。我们的方法是开发具有坚实理论基础的算法，这些算法可以有效地部署在我们的产品系统中。此外，我们通过开源一些最新的开发成果并发布其背后的高级算法，将这些进步带给更广泛的社区。在这篇文章中，我们介绍了隐私、市场算法、可扩展算法、基于图的学习和优化方面的算法进步。随着我们向 AI 优先的 Google 迈进并进一步实现自动化，开发稳健、可扩展且隐私安全的 ML 算法仍然是重中之重。我们很高兴能够开发新算法并更广泛地部署它们。
致谢
这篇文章总结了大量团队的研究成果，并受益于多位研究人员的贡献，包括 Gagan Aggarwal、Amr Ahmed、David Applegate、Santiago Balseiro、 Jennifer Brennan、 Vincent Cohen-addad、Yuan Deng、Alessandro Epasto、Matthew Fahrbach、Badih Ghazi、Sreenivas Gollapudi、Rajesh Jayaram、Ravi Kumar、Sanjiv Kumar、Silvio Lattanzi、Kuba Lacki、Brendan McMahan、Aranyak Mehta、Bryan Perozzi、 Jean Pougetabadie、 Daniel Ramage、Ananda Theertha Suresh、Andreas Terzis、Sergei Vassilvitskii、 Erik Vee、 Di Wang 和 Song Zuo。特别感谢 Ravi Kumar 对本文的贡献。
评论