Differentially Private Accelerated Optimization Algorithms
Differentially Private Accelerated Optimization Algorithms
复制标题
DOI：
10.1137/20m1355847
复制
发表时间：
2020-08
期刊：
影响因子：
--
通讯作者：
Nurdan Kuru;cS. .Ilker Birbil;Mert Gurbuzbalaban;S. Yıldırım
中科院分区：
文献类型：
--
作者：
Nurdan Kuru;cS. .Ilker Birbil;Mert Gurbuzbalaban;S. Yıldırım
我们提出了两类由著名的加速一阶方法导出的差分私有优化算法。第一种算法的灵感来自Polyak的重球方法，并采用平滑方法来减少差分隐私所需的梯度步骤上累积的噪声。第二类算法是基于Nesterov的加速梯度法及其最近的多阶段变体。为了改善Nesterov方法的误差行为，我们提出了一种用于Nesterov方法迭代的噪声分割机制。利用动力系统分析技术对重球和Nesterov加速梯度法进行了收敛速度分析。最后，我们的数值实验表明，本文提出的算法比已知的差分私有算法有优势。
We present two classes of differentially private optimization algorithms derived from the well-known accelerated first-order methods. The first algorithm is inspired by Polyak's heavy ball method and employs a smoothing approach to decrease the accumulated noise on the gradient steps required for differential privacy. The second class of algorithms are based on Nesterov's accelerated gradient method and its recent multi-stage variant. We propose a noise dividing mechanism for the iterations of Nesterov's method in order to improve the error behavior of the algorithm. The convergence rate analyses are provided for both the heavy ball and the Nesterov's accelerated gradient method with the help of the dynamical system analysis techniques. Finally, we conclude with our numerical experiments showing that the presented algorithms have advantages over the well-known differentially private algorithms.