用于差分隐私的快速混合机制

# 差分隐私的快速混合机制 来源：https://arxiv.org/html/2605.30600 ###### 摘要 随机草图化是压缩大规模优化问题同时保持精度的核心工具。特别是，基于结构化矩阵（例如哈达玛矩阵）的草图可以高效应用，并且通常能以更低的计算成本得到近似于原问题解的结果。在差分隐私（DP）中，高斯草图已被用于求解 DP 线性回归，始于 Sheffet（2017，2019），并由 Lev 等人（2025，2026）进一步改进。然而，尽管这些方法具有强大的效用保证，但它们通常不会比经典 DP 方法在运行时间上有所改善。在这项工作中，我们引入了一种基于快速变换的新型 DP 草图机制，该机制在某些情况下能与经典快速草图方法的运行时间相匹配。我们证明了该机制具有最先进的隐私保证，并表明在有利条件下，其隐私保证与高斯草图相差一个常数因子。作为应用，我们将该机制与最新的基于草图的 DP 线性回归方法相结合，得到了一种具有强大效用和改进运行时间的新算法。我们为该算法建立了隐私和精度保证，据我们所知，这实现了第一个用于 DP 普通最小二乘法的快速方法。Omri Lev† Moshe Shenfeld⋆,‡ Vishwak Srinivasan†,‡ Katrina Ligett⋆ Ashia C. Wilson††麻省理工学院 ⋆希伯来大学 ††footnotetext:通讯作者：[email protected]。代码见 https://github.com/omrilev1/FastMix。‡‡footnotetext:同等贡献。## 1 引言

现代数据收集和处理技术催生了大规模数据集，需要使用计算高效的方法进行分析。近年来，*随机草图化*已被证明是设计计算高效数据分析工具的一种有吸引力的方法；参见 Woodruff（2014）的概述。大致来说，这些草图方法通过随机投影变换数据，数据分析则在变换后的数据上进行。这些随机投影的开发主要基于两个关键目标：(a) 减小数据规模，从而降低数据分析的计算成本；(b) 保留原始数据的基本结构，从而确保数据分析的结论与原始数据分析的结果相差不大。这促使人们开发能够同时满足这两个期望的随机投影，并且近年来在这方面取得了显著进展（Drineas 等，2006；Sarlos，2006；Ailon and Liberty，2009，2013；Drineas 等，2011；Pilanci and Wainwright，2015，2016，2017；Cohen 等，2016；Avron 等，2017；Derezinski 等，2021）。

与此同时，随着这些大规模数据集（尤其是基于个人数据构建的数据集）的出现，保护参与个人隐私的问题日益受到关注。差分隐私（DP）（Dwork 等，2006）为开发能够可证明地保护隐私的机制提供了严格的理论框架，并且 DP 机制最近已在实践中得到部署（Research，2017；Bureau，2019；Research，2020；Security，2022）。这里需要权衡的是隐私保护与数据分析质量（相对于非隐私数据分析）之间的关系；例如，完全混乱的输出实现了完全的隐私，但根本上忽视了数据分析问题。

一个相对未被充分探索的方向是将随机草图化的随机性视为提供 DP 的一种手段。一个显著的例子是 Blocki 等人（2012）的工作，它证明了随机投影可以提供差分隐私；以及 Sheffet（2017，2019）的工作，该工作在此基础上展示了如何将高斯草图应用于私有线性回归。最近的论文（Li 等，2025；Lev 等，2025，2026）改进了高斯草图的隐私分析，开发了改进的私有线性回归算法，并在理论和实证上展示了相对于标准基线的优势。然而，这些方法并未提供通常与草图化相关的主要计算优势。具体来说，如果 S∈ℝ^(k×n) 是一个稠密的高斯矩阵，X∈ℝ^(n×d)，那么计算 SX 需要 O(knd) 次操作，通常与求解原问题的成本相当。相比之下，现代非私有草图方法通常使用稀疏或结构化的变换构建，这些变换计算快速且能保留数据结构，例如子采样随机哈达玛变换（SRHT）。

基于以上讨论，我们的工作受到一个自然假设的驱动：**我们能否设计一种快速 DP 机制，同时保留对数据分析至关重要的属性？** 这个问题最早由 Upadhyay（2014）研究过，他提出了一种 DP 草图机制，其应用速度明显快于高斯草图。然而，他们的方法性能通常不理想；虽然他们的机制原则上可行，但我们证明了它在典型的隐私体制下是不实用的，相对于高斯草图的隐私保证存在显著的差距。因此，从实用的角度来看，这个问题仍然有待解决。

### 1.1 我们的贡献

我们引入了一个新的快速 DP 草图家族，它弥合了非私有快速草图方法与最近研究的私有草图方法之间的差距。我们的快速 DP 草图机制（在第 3 节中介绍）应用两个草图：首先是一个用于压缩数据集的大型快速草图，其次是一个用于提供 DP 的小型高斯草图。这种方法类似于先前用于近似矩阵乘法的非私有快速草图工作（例如，参见 Cohen 等人（2016）的附录 A.3）。对于输入矩阵 X∈ℝ^(n×d) 和目标草图大小 k，该方案比稠密高斯草图快一个因子 Õ(min{n/k, k})。为了证明这确实是私有的，我们为提出的方案提供了 Rényi-DP（一种更强的 DP 概念）保证。

然后，我们将我们的机制应用于 DP 普通最小二乘法（DP-OLS）。将其与 SRHT 草图实例化，我们推导出了隐私和精度保证，明确量化了快速私有草图相对于非快速构造的代价。对于条件良好的设计矩阵，这些保证与最先进的慢速 DP-OLS 方法相匹配。在大规模线性回归数据集上的实验表明，我们的方法在保持接近非快速基线的精度的同时，实现了最先进的运行时间。相比之下，Upadhyay（2014）并未将他们的快速草图机制应用于 DP-OLS，也没有提供与最先进 DP-OLS 方法相媲美的精度保证。因此，据我们所知，我们的工作提供了第一个用于 DP-OLS 的快速算法。

## 2 问题设置与背景

##### 符号。
随机变量使用无衬线字体（例如 X,y），其实例使用有衬线字体（例如 X,y）。集合 {1,…,n} 记作 [n]。v∈ℝ^d 的 ℓ₂ 范数为 ‖v‖。设 X∈ℝ^(n×d)。我们使用 λ_min^X, λ_max^X, ‖X‖_op 分别表示 λ_min(X⊤X), λ_max(X⊤X) 和 √(λ_max^X)。ℝ^d 中的全零列向量是 0⃗_d，k×k 单位矩阵是 I_k。均值为 μ、协方差为 Σ 的高斯分布记为 N(μ,Σ)，而 N(0,I_(k1×k2)) 表示一个 k1×k2 的随机矩阵，其元素为独立同分布的标准正态分布。全文使用 Õ(·) 隐藏仅在与显示界中具有多项式依赖关系的量中的多对数因子。ℝ^d 的标准基记为 {e_i}_i=1^d，其中 e_i∈ℝ^d 是 I_d 的列。其他符号见附录 A。

##### 问题设置。
我们感兴趣的是设计作用于表格数据集的差分隐私机制。这些数据由矩阵 X∈ℝ^(n×d) 表示。我们做了一个有界域假设，即存在一个已知常数 C_X，使得对所有 i∈[n] 有 ‖x_i‖ ≤ C_X，这与之前在私有和非私有设置中的若干分析一致（例如，Shamir，2015；Wang，2018）。具体来说，从隐私角度来看，这个条件可以通过“裁剪”数据来强制执行。全文我们假设 C_X=1 而不失一般性。由于 X′=X/C_X 且 θ′=C_X θ 给出 Xθ=X′θ′，因此 C_X=1 的任何界限可以通过重新缩放扩展到一般的 C_X。

### 2.1 差分隐私

差分隐私（Dwork 等，2006）是随机化机制 M 的一个性质，它量化了 M 在“相邻”数据集上的输出分布有多大差异。这里，如果 X′ 是通过从 X 中移除一个元素（或反之）而形成的，则数据集 X,X′ 是*邻居*。¹ 我们将这种关系记为 X≃X′。全文我们使用以下标准定义。

###### 定义 1 ((ε,δ)-DP)。
称随机化机制 M 满足 *(ε,δ)-差分隐私*，若对所有满足 X′≃X 的 X,X′ 以及可测子集 S⊆Range(M)，有
Pr(M(X)∈S) ≤ e^ε·Pr(M(X′)∈S) + δ. (1)

我们的工作利用了 Rényi-DP（Mironov, 2017）这种差分隐私的变体。

###### 定义 2 ((α,r(α))-RDP)。
称随机化机制 M 满足 *(α,r(α))-RDP*（对某 α>1），若对所有满足 X≃X′ 的 X,X′，有
D_α(M(X)‖M(X′)) ≤ r(α), (2)
其中 D_α(P‖Q) ≔ (1/(α-1)) log(E_{x∼Q}[P^α(x)Q^{-α}(x)]) 表示 α-Rényi 散度（Rényi, 1960）²。

如下所示，可以将 (α,r(α))-RDP 转换为经典的 (ε,δ)-DP。

###### 命题 1（Canonne 等人 (2020)，命题 12）。
若 M 满足 (α,r(α))-RDP，则它也满足对任意 0<δ<1 的 (ε,δ)-DP，其中 ε=r(α) + log(1-1/α) - (log(αδ))/(α-1)。

(α,r(α))-RDP 和 (ε,δ)-DP 在后处理下都保持不变，并且在组合下优雅地退化。特别地，后处理保证如果机制 f 满足任一定义，那么对任何（可能随机化的）g，g∘f 也满足（Dwork 等，2014；Mironov，2017）。

### 2.2 子采样随机哈达玛变换

我们的快速 DP 草图基于子采样随机哈达玛变换（SRHT），本小节将讨论这一点。这是通过矩阵乘法实现大矩阵快速降维的标准工具（Tropp，2011；Ailon and Liberty，2013）。

###### 定义 3 (SRHT)。
设 n 是 2 的幂。一个 SRHT 矩阵 S_SRHT∈ℝ^(k×n)（k≤n）定义为
S_SRHT := √(n/k) P_{k×n} H_n B_n, (3)
其中 B_n = diag(b_1,…,b_n)，b_i 独立地从 Rademacher 分布（均匀 ±1）中抽取；H_n∈ℝ^(n×n) 是归一化的哈达玛矩阵（Walsh，1923），满足 H_n⊤H_n=I_n；P_{k×n} 是从 n 列中均匀随机选取 k 列（无放回）并乘以一个缩放因子 I_{n→k} 所得到的矩阵，使得其元素是（在每一列）