TL;DR
This paper introduces the first differentially private (DP) first-order algorithms for bilevel optimization, avoiding expensive Hessian inversions while providing rigorous privacy and utility guarantees. By combining a penalty formulation with localized DP gradient descent and a noise-calibrated hypergradient estimator, the method achieves near-stationary points for smooth nonconvex-strongly-convex bilevel problems in both empirical risk minimization (ERM) and population settings.
What Problem Does This Paper Address?
Bilevel optimization (BO) models hierarchical machine learning tasks where an outer problem depends on the optimal solution of an inner problem—such as hyperparameter tuning, meta-learning, and dataset reweighting: $$\min_{x \in \mathcal{X}} F(x) := f(x, y^*(x)) \quad \text{subject to} \quad y^*(x) \in \arg\min_y g(x, y)$$
Extending BO to the differentially private setting presents two severe roadblocks:
- Privacy Leakage via the Hypergradient: Even if the outer loss $f$ contains no private data at all, the hypergradient $\nabla F(x)$ inherently depends on the inner minimizer $y^*(x)$. For instance, in simple quadratic objectives, evaluating $\nabla F(0)$ directly outputs the exact non-private sample mean of the dataset.
- Computational Bottleneck: Standard bilevel optimization requires computing and inverting the inner Hessian $\nabla^2_{yy} g(x, y^*(x))$. In high-dimensional deep learning, this is computationally prohibitive.
Prior work on private BO was restricted to local DP and relied on explicit Hessian evaluations and inversions. This paper provides the first framework for central $(\epsilon, \delta)$-DP bilevel optimization using only first-order (gradient) queries.
Methods
The paper builds on a first-order penalty approximation framework:
- Surrogate Objective: The hyperobjective is approximated using an auxiliary penalized objective $\mathcal{L}_\lambda(x, y) = f(x, y) + \lambda [g(x, y) - g(x, y^*(x))]$. For sufficiently large penalty $\lambda$, the surrogate $\mathcal{L}^*_\lambda(x) = \min_y \mathcal{L}_\lambda(x, y)$ closely mimics $F(x)$, and its gradient can be written purely via first-order terms: $$\nabla \mathcal{L}^*_\lambda(x) = \nabla_x f(x, y^\lambda(x)) + \lambda \big(\nabla_x g(x, y^\lambda(x)) - \nabla_x g(x, y^*(x))\big)$$
- Private Inner Subroutines via Localization: Instead of computing $y^*(x)$ and $y^\lambda(x)$ exactly, the algorithm estimates them privately using Localized DP-GD (or Localized DP-SGD in the mini-batch variant). Running projected gradient steps over geometrically shrinking balls guarantees high-probability convergence with distance error $\widetilde{\mathcal{O}}(\frac{\sqrt{d_y}}{\epsilon n})$.
- $\lambda$-Independent Sensitivity Analysis: Multiplying by $\lambda$ usually blows up sensitivity. The authors prove that $\|y^\lambda(x) - y^*(x)\| \le \mathcal{O}(1/\lambda)$, which precisely cancels the $\lambda$ multiplier, making the sensitivity of each component function $\mathcal{O}(1)$ with respect to $\lambda$.
- Inexact Outer Step: The outer iterates $x_t$ are updated via projected gradient steps with Gaussian perturbation on the inexact hypergradient estimate. The output point is selected by finding $\arg\min_t \|x_{t+1} - x_t\|$, avoiding the privacy penalty of selecting the minimum gradient norm via standard selection mechanisms.
Datasets
Not discussed in the paper (this work is purely theoretical and does not present empirical benchmarks or datasets).
Key Insights and Ideas
- Information Leaks Across Levels: Deciding where to evaluate the gradient oracle based on an empirical minimizer can destroy differential privacy before any noise is even added. Privatization must happen inside the inner solver itself.
- Penalty Sensitivity Invariance: Even though the penalty formulation scales terms by $\lambda \to \infty$, the displacement between the true inner minimizer $y^*$ and the penalized inner minimizer $y^\lambda$ shrinks at rate $\mathcal{O}(1/\lambda)$. This establishes that individual sample gradients of $\mathcal{L}^*_\lambda$ have bounded sensitivity independent of $\lambda$.
- Hessian-Free Private Hypergradients: By computing difference quotients of first-order partial gradients between the two private points $\tilde{y}$ and $\tilde{y}^\lambda$, the algorithm completely sidesteps second-order derivatives.
- Closed-Form Private Hyperparameter Updates: When applied to regularized empirical risk minimization, the update reduces to sampling a 1D Gaussian centered around the difference in regularizer evaluations between models trained with and without validation loss feedback.
Key Results
For upper dimension $d_x$, lower dimension $d_y$, dataset size $n$, and privacy parameters $(\epsilon, \delta)$:
- Full-Batch DP Bilevel ERM: Algorithm 1 outputs an iterate satisfying: $$\|G_{F_S, \eta}(x_{\text{out}})\| = \widetilde{\mathcal{O}}\left(\left(\frac{\sqrt{d_x}}{\epsilon n}\right)^{1/2} + \left(\frac{\sqrt{d_y}}{\epsilon n}\right)^{1/3}\right)$$ (where $G_{F_S, \eta}$ is the projected hypergradient mapping, which equals $\nabla F_S$ in unconstrained settings).
- Mini-Batch ERM: Algorithm 3 yields an identical privacy and rate bound with an additive $\mathcal{O}(1/b_{\text{out}})$ error, where $b_{\text{out}}$ is the outer batch size. The rate is independent of the inner batch size $b_{\text{in}}$.
- Population Risk: Under samples $S \sim \mathcal{P}^n$, uniform convergence bounds show that the population hypergradient norm is bounded by the empirical error plus an additive generalization gap of $\widetilde{\mathcal{O}}\left(\frac{\sqrt{d_x}}{\sqrt{n}} + \frac{1}{n^{1/4}}\right)$.
Limitations and Future Work
- Rate Suboptimality: The best known lower bound for single-level smooth nonconvex DP-ERM is $\Omega(\frac{\sqrt{d}}{\epsilon n})$. The obtained exponents ($1/2$ and $1/3$) suggest a potential theoretical gap.
- Dependence on Lower-Level Dimension ($d_y$): While first-order, the rate depends on $d_y^{1/6}$. Concurrent/subsequent second-order methods (e.g., Lowy & Liu, 2025) removed the $d_y$ dependence at the expense of inverting Hessians; closing this gap with a first-order method remains open.
- Outer Batch Dependence: In the constrained mini-batch case, the bound retains an additive $\mathcal{O}(1/b_{\text{out}})$ penalty unless $b_{\text{out}}$ scales with $n$.
- Assumption Scope: The theory requires the lower-level objective to be smooth and strongly convex; relaxing this to general convex or nonconvex inner objectives remains an active challenge.
Summary updated