Feb, 2024
线性回归的私有梯度下降：更紧凑的误差界限和特定实例的不确定性估计
Private Gradient Descent for Linear Regression: Tighter Error Bounds and Instance-Specific Uncertainty Estimation
Gavin Brown, Krishnamurthy Dvijotham, Georgina Evans, Daogao Liu, Adam Smith...
TL;DR我们对标准差分隐私梯度下降方法在线性回归中的分析进行了改进，得出基于输入的合理假设，在每个时间步骤上迭代的分布特征。我们的分析结果揭示了算法的准确性新的发现：对于适当选择的超参数，样本复杂度仅与数据维度呈线性关系。这与（非私有）普通最小二乘估计器以及依赖于复杂的自适应梯度裁剪方案的最新私有算法（Varshney 等，2022 年；Liu 等，2023 年）的维度相关性一致。我们对迭代分布的分析还允许我们构建适应特定数据集算法的方差的置信区间。我们通过对合成数据进行实验证实了我们的定理。