We provide an improved analysis of standard differentially private gradient
descent for linear regression under the squared error loss. Under modest
assumptions on the input, we characterize the distribution of the iterate at
each time step.
Our analysis leads to new results on the algorithm's accuracy: for a proper
fixed choice of hyperparameters, the sample complexity depends only linearly on
the dimension of the data. This matches the dimension-dependence of the
(non-private) ordinary least squares estimator as well as that of recent
private algorithms that rely on sophisticated adaptive gradient-clipping
schemes (Varshney et al., 2022; Liu et al., 2023).
Our analysis of the iterates' distribution also allows us to construct
confidence intervals for the empirical optimizer which adapt automatically to
the variance of the algorithm on a particular data set. We validate our
theorems through experiments on synthetic data.

我们对标准差分隐私梯度下降方法在线性回归中的分析进行了改进，得出基于输入的合理假设，在每个时间步骤上迭代的分布特征。我们的分析结果揭示了算法的准确性新的发现：对于适当选择的超参数，样本复杂度仅与数据维度呈线性关系。这与（非私有）普通最小二乘估计器以及依赖于复杂的自适应梯度裁剪方案的最新私有算法（Varshney 等，2022 年；Liu 等，2023 年）的维度相关性一致。我们对迭代分布的分析还允许我们构建适应特定数据集算法的方差的置信区间。我们通过对合成数据进行实验证实了我们的定理。

线性回归的私有梯度下降：更紧凑的误差界限和特定实例的不确定性估计

Private Gradient Descent for Linear Regression: Tighter Error Bounds and  Instance-Specific Uncertainty Estimation

Recently, due to the popularity of deep neural networks and other methods
whose training typically relies on the optimization of an objective function,
and due to concerns for data privacy, there is a lot of interest in
differentially private gradient descent methods. To achieve differential
privacy guarantees with a minimum amount of noise, it is important to be able
to bound precisely the sensitivity of the information which the participants
will observe. In this study, we present a novel approach that mitigates the
bias arising from traditional gradient clipping. By leveraging public
information concerning the current global model and its location within the
search domain, we can achieve improved gradient bounds, leading to enhanced
sensitivity determinations and refined noise level adjustments. We extend the
state of the art algorithms, present improved differential privacy guarantees
requiring less noise and present an empirical evaluation.

通过利用当前全局模型及其在搜索域中的位置的公共信息，我们提出了一种新方法来缓解传统梯度剪裁带来的偏差，从而实现了改进的梯度界限，进一步确定了灵敏度并调整了噪声水平，提供更好的差异性隐私保证，并进行了实证评估。