Differentially Private Bilevel Optimization
This work provides a foundational solution for researchers and practitioners needing to apply bilevel optimization in privacy-sensitive machine learning applications, addressing the critical need for DP algorithms without prohibitive computational costs.
This paper introduces the first differentially private algorithms for bilevel optimization that avoid Hessian computations. The proposed gradient-based algorithm achieves a hypergradient norm of at most $\widetilde{\mathcal{O}}\left((\sqrt{d_\mathrm{up}}/\varepsilon n)^{1/2}+(\sqrt{d_\mathrm{low}}/\varepsilon n)^{1/3}\right)$ under standard DP constraints for non-convex upper-level and strongly-convex lower-level problems.
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.