Differentially Private Bilevel Optimization

Guy Kornowski

Abstract

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 $(\epsilon,\delta)$-DP algorithm returns a point with hypergradient norm at most $\widetilde{\mathcal{O}}\left((\sqrt{d_\mathrm{up}}/\epsilon n)^{1/2}+(\sqrt{d_\mathrm{low}}/\epsilon 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.

Introduction

Bilevel optimization (BO) has emerged as a critical framework in modern machine learning, underpinning tasks such as hyperparameter optimization, meta-learning, and neural architecture search. These problems are characterized by a nested structure: an outer (upper-level) objective depends on the optimal solution of an inner (lower-level) objective.

Despite its utility, BO presents significant challenges when the underlying data is sensitive. While differentially private (DP) methods are well-established for single-level optimization, applying them to the nested structure of BO is non-trivial. This paper introduces the first gradient-based, $(\epsilon, \delta)$-DP algorithms for bilevel optimization, providing a computationally efficient path toward private hyperparameter tuning and beyond.

The Privacy and Computational Bottleneck

In a typical bilevel problem, the "hypergradient" (the gradient of the outer objective) is computed with respect to the inner problem's optimal solution. This creates two primary hurdles:

  1. Privacy Leakage: Even if the outer objective does not directly use sensitive data, the hypergradient is a function of the inner solution. If the inner problem is trained on private data, the hypergradient can inadvertently leak this information. For example, if the inner problem is a simple mean estimation, the hypergradient can directly reveal the dataset's mean—a clear violation of privacy.
  2. Computational Complexity: Standard hypergradient estimation requires calculating and inverting Hessians (second-order derivatives). In high-dimensional settings, such as those involving Large Language Models (LLMs), these operations are computationally prohibitive.

A First-Order DP Framework

To address these challenges, the proposed algorithm avoids second-order derivatives entirely, relying instead on a first-order penalty-based approach. The methodology centers on several technical innovations:

Penalty-Based Approximation

Rather than solving the inner problem to exact optimality—which is difficult to achieve under DP constraints—the algorithm utilizes a penalty function. This formulation allows the hypergradient to be approximated using only first-order information, significantly reducing the computational burden.

Localized DP-GD

For the inner solver, the authors employ a "localized" version of DP Gradient Descent. By performing optimization over shrinking balls, the algorithm achieves the high-probability convergence rates necessary to keep the bias of the hypergradient low without exhausting the privacy budget.

Refined Lipschitz Analysis

A major obstacle in DP optimization is that noise must be proportional to the sensitivity (Lipschitz constant) of the function. Typically, penalty-based methods suffer from sensitivity that grows with the penalty parameter. This work provides a refined analysis showing that the sensitivity is actually independent of the penalty parameter, allowing for higher accuracy with less added noise.

Theoretical Guarantees

The paper provides the first finite-time convergence guarantees for DP Bilevel Optimization across several contexts:

  • Empirical Risk Minimization (ERM): For a dataset of size $n$, the algorithm identifies a point where the hypergradient norm is bounded by $\tilde{O}\left((\frac{\sqrt{d_x}}{\epsilon n})^{1/2} + (\frac{\sqrt{d_y}}{\epsilon n})^{1/3}\right)$, where $d_x$ and $d_y$ represent the dimensions of the upper and lower levels, respectively.
  • Mini-batching: The analysis extends to mini-batch settings, showing that the error depends on the outer batch size, aligning with established results for single-level non-convex DP optimization.
  • Generalization: The authors derive a population loss guarantee of $O(n^{-1/4})$, ensuring that the private solution found on the training set generalizes effectively to unseen data.

Conclusion and Future Directions

By removing the need for Hessian inversions and providing rigorous $(\epsilon, \delta)$-DP guarantees, this work makes private bilevel optimization feasible for large-scale machine learning. While the current bounds provide a strong theoretical foundation, future research may focus on closing the gap between these upper bounds and known lower bounds for single-level DP. Additionally, incorporating variance reduction techniques could further accelerate convergence to private stationarity in complex, high-dimensional landscapes.

Summary updated

Abstract

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 $(\epsilon,\delta)$-DP algorithm returns a point with hypergradient norm at most $\widetilde{\mathcal{O}}\left((\sqrt{d_\mathrm{up}}/\epsilon n)^{1/2}+(\sqrt{d_\mathrm{low}}/\epsilon 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.
BibTeX
@inproceedings{kornowski2026differentially,
  author = {Guy Kornowski},
  title = {{Differentially Private Bilevel Optimization}},
  booktitle = {ALT},
  year = {2026},
  url = {https://openreview.net/forum?id=9pPj3J6PBp},
}
Figure