零阶优化固有随机性无法保证隐私，迭代越多泄露越严重
On the Inherent Privacy of Zeroth Order Projected Gradient Descent
- 利用零阶梯度估计的优化算法本身存在隐私漏洞
- 固定初始点下，强凸函数上不满足差分隐私
- 即使随机初始化，隐私损失随迭代次数超线性增长
近期，因内存需求低，差分隐私零阶优化方法在机器学习模型私有微调中受到关注。现有方法通过向零阶梯度估计添加高斯噪声来实现隐私保护。然而，由于零阶方法的搜索方向本身具有随机性，Tang等（2024）与Zhang等（2024a）提出关键问题：零阶估计的内在噪声是否足以保证算法整体的差分隐私？本文针对基于查询的优化算法（查询返回零阶梯度估计）解决了该问题。我们证明，在固定初始化下，存在强凸目标函数使得运行（投影）零阶梯度下降（ZO-GD）不满足差分隐私。此外，即使采用随机初始化且不披露初始及中间迭代值，当最小化凸目标函数时，ZO-GD的隐私损失仍会随迭代次数超线性增长。
原文摘要 · Abstract (English)
Differentially private zeroth-order optimization methods have recently gained popularity in private fine tuning of machine learning models due to their reduced memory requirements. Current approaches for privatizing zeroth-order methods rely on adding Gaussian noise to the estimated zeroth-order gradients. However, since the search direction in the zeroth-order methods is inherently random, researchers including Tang et al. (2024) and Zhang et al. (2024a) have raised an important question: is the inherent noise in zeroth-order estimators sufficient to ensure the overall differential privacy of the algorithm? This work settles this question for a class of oracle-based optimization algorithms where the oracle returns zeroth-order gradient estimates. In particular, we show that for a fixed initialization, there exist strongly convex objective functions such that running (Projected) Zeroth-Order Gradient Descent (ZO-GD) is not differentially private. Furthermore, we show that even with random initialization and without revealing (initial and) intermediate iterates, the privacy loss in ZO-GD can grow superlinearly with the number of iterations when minimizing convex objective functions.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。