Near-Optimal Private Linear Regression via Iterative Hessian Mixing

问题陈述
本工作致力于解决差分隐私普通最小二乘（DP-OLS）问题。给定数据集 $(X, Y)$，其中 $X \in \mathbb{R}^{n \times d}$ 且 $Y \in \mathbb{R}^n$，目标是估计一个线性预测器 $\theta$，使其在满足 $(\varepsilon, \delta)$-差分隐私的同时，最小化经验风险 $L(\theta) = \|Y - X\theta\|_2^2$。作者假设数据是有界的（$\|x_i\| \leq C_X, |y_i| \leq C_Y$），且系统为超定系统（$n \geq d$）。

本文立足于隐私与效用之间的张力。尽管自适应充分统计量扰动（AdaSSP）方法（Wang, 2018）一直是领先的基线——提供强大的经验性能和近乎最优的理论界限——但其误差界限包含依赖于失败概率 $\varrho$ 和数据维度 $d$ 的乘性因子。具体而言，这些界限可能引入 $\sqrt{d}$ 或 $\log(1/\varrho)$ 的因子，这可能变得不可接受。相反，高斯草图方法（Sheffet, 2017; Lev et al., 2025）提供了替代机制，但历史上被视为竞争力较弱，或者缺乏关于其何时优于 AdaSSP 的明确理论保证。

方法论：迭代海森混合（IHM）
作者提出了迭代海森混合（IHM），这是一种新的 DP-OLS 算法，它将高斯草图与受 Pilanci & Wainwright (2016) 的迭代海森草图（IHS）启发的迭代细化策略相结合。

与将随机高斯矩阵 $S$ 应用于连接数据 $(X, Y)$ 的标准草图方法不同，IHM 主要在赫森（Gram 矩阵）结构内应用草图机制。该算法迭代进行：

1. 初始化：从 $\hat{\theta}_0 = \vec{0}_d$ 开始。
2. 草图化：在每次迭代 $t$，采样高斯矩阵 $S_t$ 和噪声向量 $\xi_t, \zeta_t$。
3. 草图化赫森：计算设计矩阵的含噪草图版本：$\tilde{X}_t = S_t X + \eta \xi_t$。
4. 梯度估计：计算含噪且截断的梯度估计：$\tilde{G}_t = X^\top \text{clip}_C(Y - X\hat{\theta}_t) - \eta^2 \hat{\theta}_t + \sigma \zeta_t$。
5. 更新：使用草图化赫森的逆更新估计值：$\hat{\theta}_{t+1} = \hat{\theta}_t + (\frac{1}{k} \tilde{X}_t^\top \tilde{X}_t)^{-1} \tilde{G}_t$。

一个关键的设计选择是草图应用于 $X$（赫森内部），而不是完整的 $(X, Y)$ 对。这使得算法能够利用 $X$ 的条件数（具体为 $\lambda_{\min}(X^\top X)$）来降低所需的噪声水平，而对 $(X, Y)$ 进行草图化则迫使依赖 $\lambda_{\min}((X, Y)^\top (X, Y))$，后者通常更小并导致更高的噪声。

主要贡献

1. 算法提出：引入 IHM，将 IHS 框架适应于差分隐私设置。
2. 理论保证：
   • 隐私：证明 IHM 满足 $(\varepsilon, \delta)$-DP。
   • 效用：推导超额经验风险界限。作者表明，IHM 通过移除可能高达 $\sqrt{d}$ 的乘性因子，改进了 AdaSSP 的界限。该界限依赖于 $\gamma_h = \sqrt{\max\{d, \log(1/\varrho), g_X\}} \frac{\log(1/\delta)}{\varepsilon}$，其中 $g_X$ 与 $X$ 的条件数相关。
3. 高斯草图的重分析：本文对先前的高斯草图方法（特别是 Lev et al., 2025 的线性混合方法）提供了新的精度分析。该分析阐明了这些方法的局限性，特别是它们对残差损失 $L(\theta^*)$ 和增广矩阵 $(X, Y)$ 的最小特征值的依赖。
4. 参数选择：作者提供了选择超参数（草图大小 $k$、迭代次数 $T$ 和截断水平 $C$）的实用指南，在许多情形下无需复杂的数据依赖调整。

结果
本文在来自 UCI 存储库的 33 个真实世界数据集和合成数据集上进行了严格的实证评估。

• 性能：IHM 在广泛的 dataset 和隐私水平（$\varepsilon \in [0.1, 10]$）下，始终优于或匹配 AdaSSP 和线性混合（LinMix）基线的性能。
• 情形：实验证明了 IHM 在各种情形下的优越性：
  • 具有大残差的数据集（草图方法通常在此类数据上表现挣扎）。
  • 具有条件良好的 $X$ 但条件不良的 $(X, Y)$ 的数据集（IHM 对 $X$ 的聚焦提供了优势）。
  • $\|\theta^*\|$ 较小的数据集。
• 鲁棒性：即使在旨在触发频繁截断（违反理论假设）的合成设置中，IHM 仍保持具有竞争力的性能。

意义与主张
本文主张，IHM 通过将基于草图的效率优势与充分统计量扰动的强理论保证相结合，代表了差分隐私线性回归的重大进步。

• 理论改进：通过移除 AdaSSP 界限中存在的 $\sqrt{d}$ 因子，IHM 实现了接近信息论下界的近乎最优效用保证。
• 实用效用：该方法提供了一种鲁棒的替代方案，不需要先前草图方法为了优于 AdaSSP 而所需的特定“有利”条件（例如低残差、特定的特征值关系）。
• 未来方向：作者指出，虽然 IHM 是应用于二次损失的牛顿草图的隐私版本，但未来的工作可以探索针对一般模型的牛顿草图的隐私版本，以及使用结构化随机投影来提高计算效率。

总之，该工作论证了通过仔细将草图操作限制在赫森矩阵内并利用迭代混合框架，可以实现一种差分隐私线性回归算法，该算法在误差缩放方面理论上优于 AdaSSP，并在多样化的真实世界数据分布上具有经验鲁棒性。