首个隐私保护双层优化算法，无需计算海森矩阵。
Differentially Private Bilevel Optimization
- 基于梯度的隐私算法，避免高成本海森矩阵计算。
- 在非凸上层与强凸下层条件下，超梯度范数误差为约 $\widetilde{\mathcal{O}}((\sqrt{d_\mathrm{up}}/εn)^{1/2} + (\sqrt{d_\mathrm{low}}/εn)^{1/3})$。
- 适用于正则化超参数调优等场景，适合关注数据隐私的机器学习研究者。
我们提出了用于双层优化问题的差分隐私（DP）算法，该类问题近年来在多个机器学习应用中受到广泛关注。这是首个在标准差分隐私约束下解决此类问题的算法，也是首个避免海森矩阵计算的方法，后者在大规模场景中计算代价极高。在上层目标不一定是凸的、下层问题是强凸的经典设定下，我们提出的基于梯度的 $(ε,δ)$-差分隐私算法，返回的点其超梯度范数不超过 $\widetilde{\mathcal{O}}\left((\sqrt{d_\mathrm{up}}/εn)^{1/2}+(\sqrt{d_\mathrm{low}}/εn)^{1/3}\right)$，其中 $n$ 为数据集大小，$d_\mathrm{up}/d_\mathrm{low}$ 分别为上层/下层维度。分析覆盖了有约束与无约束问题，考虑了小批量梯度，并适用于经验损失与总体损失。作为应用，我们将分析特化，推导出一个简单的私有正则化超参数调优规则。
原文摘要 · Abstract (English)
We present differentially private (DP) algorithms for bilevel optimization, a problem class that received significant attention lately in various machine learning applications. These are the first algorithms for such problems under standard DP constraints, and are also the first to avoid Hessian computations which are prohibitive in large-scale settings. Under the well-studied setting in which the upper-level is not necessarily convex and the lower-level problem is strongly-convex, our proposed gradient-based $(ε,δ)$-DP algorithm returns a point with hypergradient norm at most $\widetilde{\mathcal{O}}\left((\sqrt{d_\mathrm{up}}/εn)^{1/2}+(\sqrt{d_\mathrm{low}}/εn)^{1/3}\right)$ where $n$ is the dataset size, and $d_\mathrm{up}/d_\mathrm{low}$ are the upper/lower level dimensions. Our analysis covers constrained and unconstrained problems alike, accounts for mini-batch gradients, and applies to both empirical and population losses. As an application, we specialize our analysis to derive a simple private rule for tuning a regularization hyperparameter.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。