隐私和联邦学习

在提供高质量服务的同时尊重用户隐私仍然是所有 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的障碍逼近因子。

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

总结

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

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

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

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

参考资料：https://ai.googleblog.com/2023/02/google-research-2022-beyond-algorithmic.html