Stochastic Adaptive Line Search for Differentially Private Optimization
Stochastic Adaptive Line Search for Differentially Private Optimization
复制标题
DOI：
10.1109/bigdata50022.2020.9378011
复制
发表时间：
2020-08
期刊：
影响因子：
--
通讯作者：
Chen Chen-Chen;Jaewoo Lee
中科院分区：
文献类型：
--
作者：
Chen Chen-Chen;Jaewoo Lee
私有的基于梯度的优化算法的性能高度依赖于步长（或学习率）的选择，这通常需要非平凡的调整量。在本文中，我们介绍了一个经典的回溯线搜索算法，满足Rényi微分隐私的随机变体。具体而言，该算法自适应地选择步长满足Armijo条件（具有高概率）使用噪声梯度和函数估计。此外，为了提高所选择的步长满足条件的概率，该算法在运行时根据噪声梯度的可靠性来调整每次迭代的隐私预算。回溯搜索算法的幼稚实现可能最终使用不可接受的大隐私预算，因为自适应步长选择的能力是以额外的函数评估为代价的。该算法利用稀疏向量技术结合最近的隐私放大引理避免了这个问题。我们还引入了一个隐私预算自适应策略，该算法自适应地增加预算时，它检测到，连续梯度指向的方向是截然不同的。在凸和非凸问题上的大量实验表明，自适应选择的步长使该算法能够有效地利用隐私预算，并与现有的私有优化器相比表现出竞争力。
The performance of private gradient-based optimization algorithms is highly dependent on the choice of step size (or learning rate) which often requires non-trivial amount of tuning. In this paper, we introduce a stochastic variant of classic backtracking line search algorithm that satisfies Rényi differential privacy. Specifically, the proposed algorithm adaptively chooses the step size satisfying the the Armijo condition (with high probability) using noisy gradients and function estimates. Furthermore, to improve the probability with which the chosen step size satisfies the condition, it adjusts per-iteration privacy budget during runtime according to the reliability of noisy gradient. A naive implementation of the backtracking search algorithm may end up using unacceptably large privacy budget as the ability of adaptive step size selection comes at the cost of extra function evaluations. The proposed algorithm avoids this problem by using the sparse vector technique combined with the recent privacy amplification lemma. We also introduce a privacy budget adaptation strategy in which the algorithm adaptively increases the budget when it detects that directions pointed by consecutive gradients are drastically different. Extensive experiments on both convex and non-convex problems show that the adaptively chosen step sizes allow the proposed algorithm to efficiently use the privacy budget and show competitive performance against existing private optimizers.