Differentially Private Bilevel Optimization: Efficient Algorithms with Near-Optimal Rates
Authors: Andrew Lowy
Daogao Liu
Venue: NeurIPS 2025 poster ()
Keywords: differential privacy
bilevel optimization
private optimization
Primary area: social_and_economic_aspects_of_machine_learning
TL;DR: We develop efficient, differentially private algorithms for bilevel optimization with near-optimal excess risk bounds that nearly match the best rates for standard private optimization.

Abstract: Bilevel optimization, in which one optimization problem is nested inside another, underlies many machine learning applications with a hierarchical structure---such as meta-learning and hyperparameter optimization. Such applications often involve sensitive training data, raising pressing concerns about individual privacy. Motivated by this, we study differentially private bilevel optimization. We first focus on settings where the outer-level objective is convex, and provide novel upper and lower bounds on the excess empirical risk for both pure and approximate differential privacy. These bounds are nearly tight and essentially match the optimal rates for standard single-level differentially private ERM, up to additional terms that capture the intrinsic complexity of the nested bilevel structure. We also provide population loss bounds for bilevel stochastic optimization. The bounds are achieved in polynomial time via efficient implementations of the exponential and regularized exponential mechanisms. A key technical contribution is a new method and analysis of log-concave sampling under inexact function evaluations, which may be of independent interest. In the non-convex setting, we develop novel algorithms with state-of-the-art rates for privately finding approximate stationary points. Notably, our bounds do not depend on the dimension of the inner problem.

Differentially Private Bilevel Optimization: Efficient Algorithms with Near-Optimal Rates
Andrew Lowy"
Daogao Liu Google Research Liudaogao@gmail.com
CISPA Helmholtz Center for Information Security lowy www.ew1wgeaaaal......mmmmmmm com
Abstract
Bilevel optimization, in which one optimization problem nested inside another, underlies many machine learning applications with a hierarchical structure-sut as meta-learning and hyperparameter optimization. Such applications often in- volve sensitive training data, raising pressing concerns about individual privacy. Motivated by this, we study differentially private bilevel optimization. We first focus settings where the outer-level objective is convex, and provide novel upper and lower bounds on the excess empirical risk for both pure and approximate differential privacy. These bounds are nearly tight and essentially match the op- timal rates for standard single-level differentially private ERM, up to additional terms that capture the intrinsic complexity of the nested bilevel structure. We also provide population loss bounds for bilevel stochastic optimization. The bounds are achieved in polynomial time via efficient implementations of the exponential and regularized exponential mechanisms. A key technical contribution is a new method and analysis of log-concave sampling under inexact function evaluations, which may be of independent interest. In the non-comver setting, we develop novel algorithms with sate-of-the-are rates for privately finding approximate stationary points. Notably, our bounds do not depend on the dimension of the inner problem.
Introduction
Bilevel optimization has emerged as a key tool for solving hierarchical learning and decision-making problems across machine learning and beyond. In bilevel optimization problem, one task (the upper-level problem) is constrained by the solution to another optimization problem (the lower-level problem). This nested structure arises naturally in variety of settings, including meta-learning [33, hyperparameter optimization and model selection 21 22], reinforcement learning (27]) adversarial training [49]. and game theory 47 where the solution to problem depends implicitly the outcome of another. Formally, a bilevel problem can be written as:
min ((x) = F(x ( =EX
s.t. y (x) E argmin G(x,, v),
where and y the upper- and lower-level variables respectively. F is the upper-level objective, G the lower-level objective, X' C Rdd a domain. Solving (1) is challenging due to the dependency of y" (x:) The study of algorithms and complexities for solving T has received lot of attention
from the optimization and MI. communities in recent years 23 30 10 16 20 39 31 33 34 14].
Authors listed in reverse alphabetical order. Part of this work was completed while the first author was at
University of Wisconsin-Madison
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

In many applications where bilevel optimization can be useful, data privacy is of critical importance.
Machine learning models can leak sensitive training data [3 42 Differential privacy (DP) [8]
mitigates this by ensuring negligible dependence any single data point.
While differentially private optimization has been extensively studied in variety of settings
6
8,22 35
the community's 's understanding of DP BLO is limited. Indeed, we are only aware of two
prior works on DP BLO T 28). The work of [15] considers local DP (26) and does provide
guarantees in the important privacy regime & = O(1). On the other hand, [28] provides guarantees
for central DP nonconvex BLO with any ε > O, which we improve over in this work.
In this work, we provide DP algorithms and error bounds for two fundamental BLO problems. The first BLO problem study is bilevel empirical risk minimization (ERM) w.r.t data set Z (21, -n) E E
$x(x) = (z(,, = 1 Σ [x, 12,,72(1) (2), (1))
min DER
(Bilevel ERM)
(2(1,,)= Σ g(x, 02 (x),
s.t. (2))) = argmin yER"
where f: ; x Rdd x Z + RR and g X Rdy x x + are smooth upper- and lower-level loss functions. Second, we consider bilevel stochastic optimization (SO):
min TEX
((x) = F Fxx (x)) = E. (f(xx
(Bilevel SO)
s.t. (x)) = argmin yERd, {G(z, y) = Es~plg(2, y, 2]]]
We assume, as is standard, that g(x,"; =) is strongly convex, so Vo there are unique T2 (a) and y" (x))
A fundamental open problem in DP BLO is to determine the minimax optimal error rates for solving problems Bilevel ERM and Bilevel SO A natural first step is to consider the convex case:
Question 1.
What are the optimal error rates for solving
problem Bilevel ERM with DP when 2 is convex?
Convex 22, T arise in variety of applications 33 including few-shot meta-learning with shared embedding model [IT] biased regularization hyperparameter optimization [25], fair resource allocation in communication networks [46), and bilevel optimization with smooth convex [(, v) and quadratic g(x,,) 33
Contribution 1. We give a (nearly) complete answer to Question for both pure s-DP and approximate (e, dD-D, by providing nearly tight upper and lower bounds: see Section 3 Our results show that if the smoothness, Lipschitz, and strong convexity parameters are constants, then it is possible achieve the same rates as standard single-level convex DP-ERM (9) despite the more challenging bilevel setting (e.g., (dz//nn) for E-DP bilevel ERM). On the other hand, our lower bound establishes a novel separation between standard single-level DP optimization and DP BLO, showing that the eтror of any algorithm for DP BLO must necessarily depend on the complexity parameters of the lower-level problem (e.g. the Lipschitz parameter of ((xr,,,)) Our algorithms are built on the exponential mechanism [4) for cDD and the regularized exponential mechanism [24] for (c, -D... We provide efficient (i.e. polynomial-ting
implementations these mechanisms for DP BLO and novel analysis of how function evaluation errors affect log-concave sampling algorithms. Additionally, we provide upper and lower bounds on the excess population risk for DP Bilevel SO
DP Nonconvex BLO.
The recent work of 28 provided an (e, 0)-P algorithm A capable of finding approximate stationary points of nonconvex Z such that
Vd
1/2
dy
1/3
Ex (A(2)) ó
+
En
If dy is large, bound 2 suffers: e.g., if dy 2 dz, then the bound is 2 (V (d)///)//3 1/3 This leads us to:

---

Question 2. Can we improve over the state-of-the-art bound for DP stationary points in nonconvex Bilevel ERMP
We give positive answer to Question in Section developing novel DP algorithms that improve over the bound in ( Our first algorithm A simple and efficient second-order DP BLO method that achieves an improved dy dn-innependent bound of
Contribution 2:
E (()(I S ((
1/2
dx
Second, we provide an (inefficient) algorithm A2 that uses the exponential mechanism to "warm start" Ai using the framework of 37 to obtain a further improved bound in the parameter regime d, ne:
dd
s
(en)3/4
As detailed in Appendix bilevel finite-sum optimization:
C our results imply a new state-of-the-ee upper bound for DP non-convex
(vdz
Vdz
1/2
vdz
de A11)
E| V (2)))) 5ō
A
(En)3/4
A
(3)
1.1 Technical overview
We develop and utilize several novel algorithmic and analytic techniques to obtain results.
Our algorithms are built on the exponential and regularized A key challenge is to implement these algorithms efficiently in BLO. where one lacks access to 72 (r) and hence cannot directly query 4 Z (xx). To overcome this challenge, we provide a novel analysis of log-concave sampling with inexact function evaluations, building on the grid-walk algorithm of and the approach of [9] To do so, we prove bound on the conductance of the perturbed Markov chain arising from the grid-walk with perturbed/inexac function evaluation, well bound on the relative distance between the original and perturbed stationary distributions. We believe these techniques and analyses may be of independent interest, since there are many problems beyond BLO where access exact function evaluations is unavailable.
Techniques for convex DP BLO:
exponential mechanisms
40
24
To prove our lower bounds, we construct novel bilevel hard instance with linear upper-level / and quadratic lower-level g. This allows chain together the and y variables, control 72 (ar), and reduce BLO to mean estimation. By carefully scaling our hard instance, we obtain our lower bound.
Techniques for nonconvex DP BLO: In the nonconvex setting, algorithm order approximation Fz 1t+1) ss (z,) in order to approximate gradient descent run on $2- A key insight is that we can obtain a better bound by getting a high-accuracy non-priin con-private approximate solution V4+1 R V2 (Iz) and then noising V F2 (2t rather than privatizing Ut+1- To prove such an approach can be made DP, require careful sensitivity analysis that leverages perturbation inequalities from numerical analysis. Further, we build a two-step algorithm on our novel second-order algorithm by leveraging the warm-start framework of (38
second-
2 Preliminaries
Notation and assumptions. Let : Rd x 2 R and g X x Rdd x Z - R be loss functions, with X Rdd being a closed convex set of di-deeet D, [0, oo). The data universe denote the & norm when applied vectors. When applied to matrix A, ||| : $max (A) V / (AAT) denotes the le operator norm, which is the largest singular value of A. Function : + R. is L-Lipschitz if [h(x) h(x')l L|[ z'll for all x, E X. Function h. X R is p-strongly convex if Max + (1)))=") S ah(x) + aa)((()))= a(1 a(l=a)m
Z can be any set. P denotes any data distribution on X. Let
2 ||x - x'Il2 for all a E [o, 1] and all Jr, x' X. If 0, say h is convex. The excess (population) risk of randomized algorithm A with

---

output E = A(Z) on loss function h(,, 2) is ( H" where H(x) = Bz 2)] and 11 :- inf, H().. If [z)(z) ト h(x, zi) an empirical loss function w.r.t. data set Z, then the excess empirical risk of A E (z) - H Denote a = min(a, b). For functions o and & of imput parameters 0, write yp & if there an absolute constant C' such that (0)) I (+) for all permissible values of B. We use Ö to hide logarithmic factors. Denote by (z, 2( + Vy(x)" yJ, y(z), 2) the gradient of function J w.r.t.
()(,,,(z),
We assume, as is standard in DP optimization, that the loss functions are Lipschitz continuous, and that ( 2) is strongly convex- standard assumption in the BLO literature:
Assumption 2.1.
1. (() is a Lipschitz in for all y,
2. (x);;;)) is I.f.y--isschin in y for all x. 2.
3. g(z,,, Mg Hg-strongly convex y.
4. There exists compact set Y C Rd with (ū% for ERM or (x))x)) C for SO such that g(z,', 2) is Lg. -iipschit on y
Note that D, = diam())) S Luve by Assumption 2.1 Some of our algorithms additionally require:
Py
Assumption 2.2. For all x, x' y, 3/, 2 we have:
1. [,,(E, Vul(or ,)]l < B5.vllly y s'll-
2. [,,(x, Vas(de, y; =)| s f || x/
3. [vf(2, v,
V=f(2, 2) s Byayllyy y'll and Vyf(a, - V vz((z',),))
35,zyl [ 2-11
4.
y, =)1 < Br and ( v,,)| S 8g
5. Veu9(z, y, 2)1l - 2g.vv
6. (2 v; V2 (z', y, =]] _ M Mo.yll x'11, || V2 (x; y, v, Vemelaa' .,,,)] S
Mg.zyl [x 2'11. and V 1 (z, =) V pyg(2', y, 2) < M, Mg.vo || z'|l.
7. [ 22,9 y, Cg.zvlly y'l, ||, and V y.2) ( v/ 2)11 < C. Co.vulyy y'll-
V (x v' 2) < Cg lly 1/11. 12
1 (x: y, 2) 9x, v/ 2)]l s
Assumption 2.2 is standard for second-order optimization methods and is essentially the same as the (28] Assumptions 2.5 and 2.6]. but we define the different smoothness parameters a more granular level to get more precise bounds. As discussed in [23], these assumptions are satisfied in important applications of BLO, such model selection and hyperparameter tuning with logistic loss (or another loss with bounded gradient and Hessian) and some Stackelberg game models.
Differential Privacy. Differential privacy prevents any adversary from inferring much more about any individual's data than if that data had not been used for training.
Definition 2.3 (Differential Privacy). Let 0, d E [0, 1). Randomized algorithm AA Z W is (s, 8) -iffferrentill private (DP) if for any two datasets Z = (Z1,..., Zn) Zn) and Z' = (2( z that differ one data point (i.e. 2, * 2/. 2j 2/ for j # i) and any measurable set C X, we have
P(A(Z) S) (P(A(Z) ES 5)+ +
Algorithmic preliminaries on DP are given in Appendix A
3 Private convex bilevel optimization
In this section, we characterize the optimal excess risk bounds for DP convex bilevel ERM:

---

Theorem 3.1 (Convex DP BLO Informal). Let & and & be convex (AZ E 2*) and grant Assumption 2.7 Then, there an efficient E-DP algorithm with output such that
E4 z
2
ET
If Assumption 2.2 parts 3-4 hold, then there is an efficient (e, DD algorithm with output Tor s.t.
V de (og()
( 32 0o
Moreover, the above upper bounds are fight (optimal) up logarithmic factors.
The following subsections contain formal statements capturing the precise dependence on the problem parameters given in Assumptions 2.1 and 2.2 and runtime bounds. We also provide bounds for DP convex bilevel SO.
3.1 Conceptual algorithms and excess risk upper bounds
This section contains our conceptual algorithms (ignoring efficiency considerations) and precise excess risk upper bounds.
Pure c-DP. Consider the following sampler for DP bilevel ERM, which is an instantiation of the exponential mechanism 40 Given Z E 2", sample F = Z(Z) X with probability
x exp
$ (3)
where
28
2 $ = n
fL
L L Dr + L.
Hg
Theorem 3.2. Grant Assumption
2.1 and suppose Ø is convex. The Algorithm in 4 is 8-DP and
dn EN L1.zD2 + LyN + L
E
Pg
We defer the proof to Appendix B and describe the efficient implementation in Section 3.2 If 4 is not convex, then privacy still holds and the same excess risk holds up to logarithmic factors. The key step in the privacy proof is to upper bound the sensitivity of the score function (x) by 8, by leveraging Assumption 2.1 and the fact that | (x) TZ (x))l 2 Pg for adjacent Z Z
Approximate (c, -DP Consider the following instantiation the regularized exponential mecha- nism 24]: Given Z, sample v = ((Z) from probability density function
exp(-k(@0) (+) + p=)
where
(5)
um2e2
h: = 0
and
G2 log(1/5)
L 1
G G= L, + Pg
Mg
where j is an algorithmic parameter that we will assign (not to be confused with pg).
Theorem 3.3 (Informal). Grant Assumption 2.1 and parts 3 and 4 of Assumption 2.2 Assume $ %
and & are convex for all Z e z". There exists a choice of p and l such that Algorithm (5) is (e, -DD and achieves excess empirical risk
Lin8n.u B - $2 so 10((1)
de log(1/8)
D2
En
Further, if ~ are independent samples, the excess population risk with a different choice of k, S. is
/ dd log(1/)
EΦ(T) Φ" 00
+
EN
n
5

---

Refer to Theorem B.8 in Appendix for the precise population loss bound with proper units. The main
idea of the privacy proof (in Appendix B is to show that क - क2. is 2( L/ + 1.i. + 1. }- My
nyt,
Lipschitz and then compare the privacy curve [5] between the distributions Q and Q' (corresponding
to with data Z and Z' respectively) to the privacy curve between two Gaussians, by leveraging
24 Theorem 4.1].
generalization error bound involves fairly long "ghost sample" argument that leverages the Wasserstein distance bound for log-concave distributions, Kantorovich- Rubinstein duality, and the Efron-Stein Stein inequality. One can also obtain an ( /d/n) generalization error bound by uniform convergence argument; omit those details here.
Obtaining our coimension-independeee
Remark 3.4 (Near-optimality for ERM). The bounds in Theorem 3.2 and 3.3 nearly match the optimal bounds for standard single-level DP ERM [9], e.g. (L Dar d, (1/))/ssn) for (s, 6)- DP ERM 99 48 J. except for the addition of two terms capturing the complexity of the bilevel problem: For s DD ERM, the additional terms are O D, Dydz/en and (((L),y (dgd:////)))))))) Our lower bound in Theorem 3.10 shows that the first additional term is necessary. We conjecture that the second additional term is also necessary and that our upper bound is tight up to absolute constant. This conjecture is clearly true in the parameter regime L. Pgg R Dy. For (c, 5)DD,, the additional terms scale with f( 9y (yy + g f,zy/ (4y (2) Our lower bound in Theorem 3.10 shows that dependence on y is necessary and that the L gg.ay/ Mg term is tight in the parameter regime Dy 2 D Mg. If also Dr.agay/ S Lg then the bounds in Theorem 3.3 are tight up to an absolute constant factor.
Remark 3.5 (Suboptimality for SO). There is a gap between our population risk upper bound in Thcorem 3.3 and the lower bounds in [6] and Remark 3.11 for single-level SCO and bilevel SO respectively. We conjecture that our lower bound in Remark 3.1 is nearly tight and that our upper bound is suboptimal. We leave it as future work to investigate this conjecture.
3.2 Efficient implementation of conceptual algorithms
In many practical applications of optimization and sampling algorithms, we face unavoidable approx- imation errors when evaluating functions. Given any z. we may not get the exact 172 (1) in solving the low-level optimization, which means we may introduce a small error cach time we compute the function value of fzz i7 (z), z). This section analyzes how such small function evaluation errors affect log-concave sampling algorithms. We establish bounds on the impact of errors bounded by Ç on the conductance, mixing time, and distributional accuracy of Markov chains used for sampling. We then develop an efficient implementation based on the [9] approach that maintains polynomial time complexity while providing formal guarantees on sampling accuracy in the presence of function evaluation errors. As a corollary of our developments, we obtain Theorem
3.1
Our approach builds on the classic Grid-War algorithm of R for sampling from log-concave distributions. Let F(.) be real positive-value function defined on a cube A = [a, b)d in Rdd. Let f(0)= - log (0) and suppose there exist real numbers a, 3 such that:
[f()) - f(v) S a max 1 144-10 wi).
[E[L_4]
f(Ar + (1-A))) 2 Af(x) (1-1)(11 x)f(8) - -3,
for all x, E A and e 1]. 1]. The algorithm of [3], detailed in Appendix B.3.1 for completeness, samples from a distribution on the continuous domain A such that for all 0 É A. (v) < C. where e is a normalization constant and > 0. The algorithm defines a random walk (which is Markov Chain) on the centers of small subcubes that partition A and form the state space Ω A. The final output of the algorithm is a point x E A, returned with probability close to F(z).
Next, we briefly outline our analysis how the Grid-Walk algorithm behaves when the function F can only be evaluated with some bounded error, resulting in a "perturbed" Markov chain.
Conductance bound with function evaluation errors. For Markov chain with state space Ω, transition matrix P and stationary distribution g, its conductance yp measures how well the chain mixes, i.e. how quickly it converges to its stationary distribution:
Σ Ee s Pay)
Φ =
min (CQ:<c($))112
((S)

---

We analyze how function evaluation enrors affect Grid-Wale conductance:
Lemma 3,6 (Conductance with Function Evaluation Errors). Let P be the transition matrix of the original Markov chain in the grid-walk algorithm of Section [33.1 based on function with state space and conductance y. Let P' be the transition matrix of the perturbed chain based on f where ('( (() ((0) with [ç(0)] S Ç for all 0 E Ω2 where ((-) is bounded error function. Then the conductance x' of the perturbed chain satisfies:
2 e 05 p.
Relative distance bound between F and F. We now analyze how function evaluation errors affect the distributional distance between the original and perturbed stationary distributions.
Lemma 3.7 (Distance Between and F),, Let F(0) = = ((0) and F'(0) = (0) where (0
f(0) (()) with K(O) S for all 0 E A. Then,
(() F(0) S 6, 4O E A.
Furthermore, if we define the distributions (0) x F(0) and (0) x FO),, then:
x x0)
Dist (I', x) == sup BEA
log
$ 2Ç.
x()
Mixing time analysis. For Markov chain with state space Ω transition matrix P, and stationary distribution æ, the mixing time mix(() with respect to the -distance defined as:
tiix (c) == (t 2 0 max Dist (P. (x. (T)) <c),
(6)
zEQ
for any e 2 0. We determine the number of steps required for Los convergence with perturbed F: Lemma 3.8 (Impact on Mixing Time). The mixing time (emax() () of the perturbed chain to achieve
Los diistinne to its stationary distribution satisfies:
d2 e max dlog atvd .a7 ..a7)
(E) S 125 .
Efficient implementation. Leveraging our analysis of how function evaluation errors affect conduc- tance, mixing time, and distributional distance, we develop an efficient algorithm for sampling from log-concave distributions in the presence of such errors. Our approach builds upon the framework developed by [ extending it to handle approximation errors.
Theorem 3.9 LLngCCo Sampling with Function Evaluation Error). Let C Rd be a convex set and f C + IR be a convex, L-Lipschitz, function, Suppose we have access to an approximate function evaluator that returns f(()) f ((0) where [ç(0) S for all C, and Ç = O()) is constant independent of dimension. There exists an efficient algorithm that outputs sample E C from a distribution yt such that: Dista (p/: T) S +
where 7 (0) x (1(0) the target log-concave distribution and 8 0 arbitrarily small constant. This algorithm runs in time 22 d poly(L, I[C1|,,
The efficiency claims in Theorem 3.1 follow as corollaries of Theorem 3.9 see Appendix
B.3
3.3 Excess risk lower bounds
If the problem parameters (e.g., Lipschitz, smoothness) are constants, then the upper bounds in Theorems 3.2 and 3.3 are tight and match known lower bounds for standard single-level DP ERM and SCO 9 6 In this section, we go a step further and provide novel lower bounds illustrating that the dependence of our bounds on T.f.,, y (or a quantity larger than this) necessary, thereby establishing novel separation between single-level DP optimization and DP BLO:
7

---

Theorem 3.10 (Excess risk lower bounds for DP ERM). 1. Let A be E-DP. Then, there exists data set Z E z" and a convex bilevel ERM problem instance satisfying Assumptions 2.1 and 2.2 with Mg @ Dyy such that
(Oz(A(Z)) - $ =2 (L + Lyy min
dn ne
2. Let A be (e, DP with 2 2-Q(m) S 1/n++0(1), Then, there exists data set 7. E t and convex bilevel ERM problem instance satisfying Assumptions) 2.7 and 2.2 with P4 (Lg D2) such that
E (A(2)) - 3z = ( + Lyy min { v log(1/0)
1,
ne
By comparing the lower bounds in Theorem 3.10 with the bounds in [9, one sees that the DP bilevel ERM is harder (in terms of minimax error) than standard single-level DP ERM if L,yD, > L Dz.
See Appendix [B4 for the proof. A key challenge is in constructing the right f and g chain together the x and y variables and obtain the desired Lf.y Dy scaling term.
Remark 3.11 (Bilevel SO lower bounds). One can obtain lower bounds on the excess population risk that are larger than the excess empirical risk bounds in Theorem 3.10 by an additive via the reduction in 7
4 Private non-convex bilevel optimization
In this section, we provide novel algorithms with state-of-the-art guarantees for privately finding approximate stationary points of non-convex & (see 33
4.1 An iterative second-order method
Assume for simplicity that X' d so that the optimization problem is unconstrained P
natural
approach to solving Bilevel ERM is to use gradient descent scheme, where we iterate
F141 2, V/ (x)))
(8)
By the implicit function theorem, we have (c.f. 23
(x) V (z v 3,
Define the following approximation váz(z) at (z,y):
Vf2(2,)) = - Gz
(9)
Note that FF2(1,)) v42 if (x).
Then to approximate
(non-privately). iterate (c.f.
23
Vt+1 T2 (xxe
F++ = F. (Z(
(10)
A naive approach privatizing the iterations (10) is to solve gt++1 R (2;) argmin, (z., (Z v)
privately at each step (c.g.. by rumning DP-SGD), and then add noise to V (az, y(+1) before taking step of noisy GD. (This is similar to how 28 privatized the penalty-based bilevel optimization
algorithm of (30) However, this approach results a bound x s O(vd, + dyy 1///
that depends dy due the bias F2 (Zt, V++1) v ) that results from using private Vt+1- To mitigate this issue and obtain state-of- of-the-arttttt utility independent of dy, we propose an alternative approach in Algorithm we find approximate minimizer of Gz(Ze.) non-privately in line 3.

---

Algorithm 1: A Second-Order DP Bilevel Optimization Algorithm
Input: Dataset DD (Z1,.... ...). noise scale a, initial points zo, yo X parameter o;; for i o,...,? ,T,TT- do
Find V141 2 7/ (xz) such that 11++1 - -0 - a (e.g, via SGD or Katyusha 22); J++1 = 24 V (Te M641) + u1). where in ~ ~~(00,0aa.)
end
Output: FT ~ Unif( (2))=1))
Since (2( )) is smooth, strongly convex ERM function, implement line efficiently using a non-pen non-private algorithm such as SGD or Katyusha (2]
Denote L == I + Pa.yLyi which is an upper bound on IV T2 (z),
2)
and
C: 0fay + Bramsgg.u + Lig
Co.oy + Cg.nvi8a.ay
(11)
My
Fgg
19
which satisfies (V) VFz(z, vlll S Cl) all for any x. y by 123
Lemma 2.2]. Let
B Bray L 2T
B BgayBrron Leg
Cnayynn
1 Lg Caau
L L 9ny
K =
Vg
1
19
19
12
(12)
Lemma 4.1 (Sensitivity Bound for Algorithm
For any fixed ue, define the query qi : 2 - Rdd
(Z) = Fz 1t+1);
On where and K are defined in Equations and 12 then the se-siiiitvvtty of qu is upper bounded by 4K
where Yi+1 yt+1 (Z) is given in Algorithm 1 If a S K
The proof of this lemma in Appendix g is long. It uses the operator norm perturbation inequality ||M~ N 'I M 'I| ||| N|| bound the sensitivity of [ Gz (2+) in
Now we can state the main result of this subsection:
Theorem 4.2 (Guarantees of Algorithm T for Non-Convex Bilevel ERM Informal). Grant Assump- tions] 2.1 and 2.2 Set a = 32K / TT log(1 1/8)/nE. Denote the smoothness parameter of & by Bq, There are choices of oz, s.t. Algorithm 7 is (e, 8DP and has output satisfying
given Lemma C.2
1/2
B|| V & Kv (Øz(z0) 332) Br v de log
The privacy proof leverages Lemma 4.1 Utility is analyzed through the lens of gradient descent with biased, noisy gradient oracle. We choose small a so the bias is negligible and use smoothness of $ z.
4.2 "Warm starting" Algorithm I with the exponential mechanism
This subsection provides an algorithm that enables an improvement over the utility bound given in Theorem 4.2 in the parameter regime d, ne. Our algorithm is built the "warm start" framework of [37]: first, we run the exponential mechanism (4) with privacy parameter e/2 2 to obtain Zi! then,
run (e/2 8)-DP Algorithm [ with "warm" initial point zp- See Algorithm
2 Zi Appendix C.2
Theorem 4.3 (Guarantees of Algorithm for Non-Convex Bilevel ERM). Grant Assumptions 2.
and 2.2 Assume that there is compact set X dd of diameter D containing approximate global minimizer such that ( 42 S en with output satisfying
d. where == Ls L. Lixkan Then,
there exists an (e,0) DDDD instantiation of Algorithm 2
1/2
VZ S
[
21/2 11/2
1/2 [n ddr//og(1//)
(ne)3/2
*Our approach and results readily extend to constrained X by incorporating proximal steps and measuring utility in terms of the norm of the proximal gradient mapping.

---

In Appendix C.S
we explain how to deduce the upper bound in (3) by combining Theorems 4.2 and 4.3 with the exponential mechanism using cost function | (z)]l-
5
Conclusion and discussion
We provided novel algorithms and lower bounds for differentially private bilevel optimization, with near-optimal rates for the convex setting and state-of-the-art rates for the nonconvex setting. There some interesting open problems for future work to explore: (1) What are the optimal rates for DP bilevel convex SO? As discussed Remark 3.5 we believe that should be possible, though challenging, obtain improved ((1/vT)) generalization error bound nearly matching the lower bound in Remark 3. T.IT (2a) What are the optimal rates for DP nonconvex bilevel ERM and SO? Since the optimal rates for standard single-level DP nonconvex ERM and SO are still unknown, a first. step would be to answer: (2b) Can we match the SOTA rate for single-level non-convex ERM (88 in BLO? Incorporating
in DP BLO seems challenging. (3) This work was focused on fundamental theoretical questions about DP BLO, but another important direction is to provide practical implementations and experimental evaluations.
References
[1] A. Ajalloeian and S. U. Stich. On the convergence of sgd with biased gradients. arXiv preprint arXiv:2008.00051, 2020.
[2] Z. Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods. The Journal of Machine Leurning Research, ((():88144822) 2017.
[3] D. Applegate and R. Kannan. Sampling and integration of near log- cog-concave functions. In Proceedings of the twenty-third annual ACM symposium on Theory of computing, pages 156- 163, 1991.
[4] H. Asi, V. Feldman, T. Koren, and K. Talwar. Private stochastic convex optimization: Optimal rates E, geometry. ICML, 2021.
[5] B. Balle and Y.-X. Wang. Improving the gaussian mechanism for differential privacy: Analytical calibration and optimal denoising. In International Conference on Machine Learning, pages 394-403. PMLR, 2018.
[6] R. Bassily, V. Feldman, K. Talwar, and A. Thakurta. Private stochastic convex optimization with optimal rates. In Advances in Neural Information Processing Systems, volume 32, 2019.
[7] R. Bassily, V. Feldman, K. Talwar, and A. Thakurta. Private stochastic convex optimization with optimal rates. In Advances in Neural Information Processing Systems, volume 32, pages 11282-1 1291, 2019.
[8] R. Bassily, C. Guzmán, and M. Menart. Differentially private algorithms for the stochastic saddle point problem with optimal rates for the strong gap. In The Thirty Sixth Annual Conference on Learning Theory, pages 2482-2508. PMLR, 2023.
[9] R. Bassily, A. Smith, and Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 464-473 IEEE, 2014.
[10] K. P. Bennett, J. Hu, Ji, G. Kunapuli, and J.S.. Pang. Model selection via bilevel optimization. In The 2006 IEEE International Joint Conference on Neural Network Proceedings, pages 1922-1929, IEEE, 2006.
[11] I.. Bertinetto, J. F. Henriques, P. Torr, and Vedaldi. Meta-learning with differentiable closed-form solvers. arXiv preprint arXiv:1805.087. 2018.
[12] O. Bousquet and Elisseeff. Stability and generalization. The Journal of Machine Learning Research, 2:499-526, 2002.
10

---

[13] N. Carlini, F. Tramer. E. Wallace, M. Jagielski, A. Herbert- Voss, K. Lee, A. Roberts. T. B. Brown, D. Song. U. Erlingsson, al. Extracting training data from large language models. In USENIX Security Symposium, volume 6, pages 2633-26500 2021.
[14] L. Chen, J. Xu, and J. Zhang.
On finding small hyper-gradient in bilevel optimization: Hardness results and improved analysis. In The Thirty Seventh Annual Conference on Learning Theory, pages 947-980. PMLR, 2024.
[15] Z. Chen and Y. Wang. Locally differentially private decentralized stochastic bilevel optimization with guaranteed convergence accuracy. In Forty-first International Conference on Machine Learning, 2024.
[16] B. Colson, P. Marcotte, and G. Savard. An overview of bilevel optimization. Annals of operations research, 153:235-256. 2007.
[17] E. De Klerk and M. Laurent. Comparison of lasserre's measure-based bounds for polynomial optimization to bounds obtained by simulated annealing. Mathematics of Operations Research, 43(44,1317-1325, 2018.
[18) C. Dwork, F, McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryplography conference, pages 265-284. Springer, 2006.
[19] C. Dwork and A. Roth. The Algorithmic Foundations of Differential Privacy, volume 9. Now Publishers, Inc., 2014.
[20] E. Falk and J. Liu. On bilevel programming, part i: general nonlinear cases. Mathematical Programming, 70:47-72, 1995.
[21] L. Franceschi, P. Frasconi, S. Salzo, R. Grazzi, and M. Pontil. Bilevel programming for hyperparameter optimization and meta-learning. In International conference on machine learning, pages 1568-1577. PMLR, 2018.
[22] C. Gao, A. Lowy, X. Zhou, and S. Wright. Private heterogeneous federated learning without a trusted server revisited: Error-optimal and communication-effin -efficccn algorithms for convex losses. In Forty-first International Conference on Machine Learning, 2024.
[23] S. Ghadimi and M. Wang. Approximation methods for bilevel programming, arXiv preprint arXiv:1802.0222: 02.46.....22...... 2018.
[24] S. Gopi, Y. T. Lee, and D. Liu. Private convex optimization via exponential mechanism. In Conference Learning Theory, pages 1948-1989. PMLR, 2022.
[25] R. Grazzi, L. Franceschi, M. Pontil, and S. Salzo. On the iteration complexity of hypergradient computation. International Conference on Machine Learning, pages 3748-3758. PMLR, 2020.
[26] S. P. Kasiviswanathan, H. K. Lee, K. Nissim, S. Raskhodnikova, and A. Smith. What can we learn privately? SIAM Journal on Computing, 40(3):793-826, 2011.
[27] V. Konda and Tsitsiklis. Actor-critic algorithms. Advances neural information processing systems, 12, 1999.
[28] G. Kornowski. Differentially private bilevel optimization. arXiv preprini arXiv:2409.19800, 2024.
[29] G. Kunapuli, K. Bennett, J. Hu, and J.-S. Pang. Bilevel model selection for support vector machines. Data mining and mathematical programming, 45:129, 2008
[30] J. Kwon, D. Kwon, S. Wright, and R. D. Nowak. A fully first-order method for stochastic bilevel optimization. International Conference on Machine Learning, pages 18083-18113. 13. PMLR, 2023.
[31] J. Kwon, D. Kwon, S. Wright, and R. D. Nowak. On penalty methods for nonconvex bilevel optimization and first-order stochastic approximation. The Twelfth International Conference on Learning Representations, 2024.

---

[32] Y. T. Lee, A. Sidford, and S. C.-w. Wong. A faster cutting plane method and its implications for combinatorial and convex optimization. In 2015 IEEE 56th Annual Symposiun on Foundations of Computer Science, pages 1049-1065. IEFE, 2015.
[33] Y. Liang et al. Lower bounds and accelerated algorithms for bilevel optimization. Journal of machine learning research, 24(22): 2023.
[34] B. Liu, M. Ye, S. Wright, P. Stone, and Q. Liu. Bome! bilevel optimization made easy: A simple first-order approach. Advances in neural information processing systems, 35:17248- 2022.
[35] A. Lowy, D. Liu, and H. Asi. Faster algorithms for user-level private stochastic convex optimization. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
[36] A. Lowy and M. Razaviyayn. Output perturbation for differentially private convex optimization: Faster and more general. arXiv preprint arXiv:2102.04700 2021.
[37] A. Lowy, J. Ullman, and S. Wright. How to make the gradients small privately: Improved rates for differentially private non-convex optimization. In Forty-first International Conference Machine Learning 2024.
[38] A. Lowy, J. Ullman, and S. J. Wright. How to make the gradients small privately: Improved rates for differentially private non-convex optimization. arXiv preprint arXiv:2402.11173, 2024.
[39] Z. Lu and S. Mei. First-order penalty methods for bilevel optimization. SIAM Journal on Optimization, 34(2):1937-199) 2024.
[40] F. McSherry and K. Talwar. Mechanism design via differential privacy. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07), pages 94-103. IEEE, 2007.
[41] B. Morris and Y. Peres. Evolving sets, mixing and heat kernel bounds. Probability Theory and Related Fields, 133(2):245-26) 2005.
[42] M. Nasr, J. Rando, N. Carlini, J. Hayase, M. Jagielski. A. F. Cooper, D. Ippolito, C. A. Choquette- Choo, F. Tramèr, and K. Lee. Scalable extraction of training data from aligned, production language models. In The Thirleenth International Conference Learning Representations, 2025.
[43] A. Rajeswaran, C. Finn, S. M. Kakade, and S. Levine. Meta-learning with implicit gradients. Advances neural information processing systems, 32, 2019.
[44] S. Shalev-Shwartz, O. Shamir, N. Srebro, and K. Sridharan. Stochastic convex optimization. In COLT, volume 2, page 5, 2009.
[45] R. Shokri, M. Stronati, C. Song, and V. Shmatikov. Membership inference attacks against machine learning models. In 2017 IEEE symposium on security and privacy (SP), pages 3-18. IEEE, 2017.
[46] R. Srikant and L. Ying. Communication networks: An optimization, control and stochastic networks perspective. Cambridge University Press, 2014.
[47] H. Stackelberg. The Theory of the Market Economy. Oxford University Press, 1952.
[48] T. Steinke and J. Ullman. Between pure and approximate differential privacy. Journal of Privacy and Confudentiality 7(2), 2016
[49] Y. Zhang, G. Zhang, P. Khanduri, M. Hong. S. Chang, and S. Liu. Revisiting and advancing fast adversarial training through the lens of bi-level optimization. In International Conference on Machine Learning, pages 16693-26712 PMLR, 2022.
12

---

Appendix
A
More privacy preliminaries
Definition A.1 (Sensitivity). Given a function y 2 -y IR the lz-sensitivity of q is defined as
sup ll9 (Z")ll
2~2'
where the supremum is taken over all pairs of datasets that differ one data point.
Definition A.2 (Gaussian Mechanism). Let 0, 8 E (0, 1). Given function q: 2 R with fz-sensitivity A, the Gaussian Mechanism M defined by
M(Z) g +
where v ~ No II) and o² = 24 log(2/6)
Lemma A.3 (Privacy of Gaussian Mechanism [9]). The Gaussian Mechanism is (s, 6)-DP.
we adaptively query data set T times, then the privacy guarantees of the T-th query still DP and the privacy parameters degrade gracefully:
Lemma A.4 (Advanced Composition Theorem [9]). Let 2 0,8,8' E (0. 1). Assume Au, Ar, with Ar n x X - X, are each (8, () DP AI 1....... .T. Then, the adaptive composition
A(Z) = Ar AT 2 2 ))) is (E', T6 + DDP for
e' = v 2T 2n + Te(e" - 1).
B Proofs for Section 3.1
B.1
Conceptual algorithms and excess risk upper bounds
Pure e-D.. We restate and prove the guarantees of the s-DP exponential mechanism for BLO
below:
Theorem B.1 (Re-statement of Theorem 3.2 Grant Assumption 2.1 and suppose क is convex. The
Algorithm 4 is E-DP and achieves excess empirical risk
de
Tr Dz + Dy + LI.ghr
E (T)
$2 < 1000
Pg
Proof. Privacy: First, notice that the distribution induced by the exponential weight function in !
is
the same we use exp (- 2s (2x))) o (Λx)) for some arbitrary point 20 E To establish the
privacy guarantee, it suffices to show that the sensitivity of Zz(z)) 3z(2)) is upper bounded by for any æ. Now, let 7' any adjacent data sets differing =1 * of and let x X. Then the sensitivity of & (0z(x) (x) (200) is upper bounded by
xx(x)= कz (20) क (x) + T z (2ro)
f(z, O2 (I), 21) f(x0 02 (2o), 21) (2), + f(ao (20) (20),11) 21)
ff T2 (x), (4),
i>
(f TZ (zo); 21) f(2o. Mz. (xo). 2:)1
i>1
<
LL Dr Lyy
Σ 1f(0, D2 (x), 2:) s(x (x),
1
[f (20)
f N2 (xa) 2:)l-
71
1>1
13

---

Now, for any we have
2
112 (x)) -
Pg
by 36.. Together with 1.yy-Lipscchte continuity of f(z," + z), we can then obtain the desired sensitivity bound.
Excess risk: This immediate from Lemma B.2 (stated below) in the convex case. For nonconvex 2,, the same excess risk bound holds up to logarithmic factors by
Lemma B.2 (Utility Guarantee, 117 Corollary 1J.. Suppose k > 0 and is a convex function over the convex K. C Rd. If we sample according distribution whose density is proportional to exp(- - (x)), then we have
Eg [x & min F(x) + k'
zER
Next, we turn to the (c, 6)-DP case.
Approximate (s, d)-P.
define the privacy curve first:
Definition B.3 (Privacy Curve). Given two random variables X,Y Y supported on some set Q define the privacy curve 8(X Y Rz0 + [0, 1] as:
8 (() = sup Pr(V P e S).
SCR
We have the following theorem from 24
Theorem B.4 (Regularized Exponential Mechanism, (4)). Given convex set K. C Rd and p-strooggy convex functions F, F over K. Let P.Q be distributions over such that P(x) FF()) and Q(x) x e F(x) If F is G-Lipschitz over K., then for all E [0, 1).
8(P Q)(c)) S s = (
11)) (c).
N Vu
suffices to bound the Lipschitz constant (2(x) (z)). We have the following technical
lemma:
Lemma B.5. Let T2 (x) = (oggminney22(,,0 where Gz(z, v) = 1 En g(x v, 2.). If gg 2) is Stronyyy convex in and (V,G2(I,8) Gz .8)l I By,avlle x' for all x. 2, then
3 3g.wy | x'1l-
(0) O2 (x'))
Proof. Since (z(x) is the minimizer of Gz( y), the first-order optimality condition gives:
(z))
Similarly for w/:
v ( =0
By strong convexity of G2(2',)) and the first-order optimality condition, we have:
M V1ll2
Tz (>'))) < <V (x)) 7, T2 (x'))
(. -2) 7x V Gz v,G2(z. (0) (z()') =
14

---

2.9,0yl - x11 (102(a) V3(2'))
Therefore:
Bamay || x'1l.
(02(2) - 0x2(2')1 -
Mg
Lemma B.6. Grant Assumption 2.1 and additionally assume [ V=f =)|l S
31,aylyy sopull-gl of and [IV NV,G2( (Z. v) v, (x', y)ll S 8g.zy || x') flror all x, x', y. y.y. Then, for any datasets Z, Z z" differing in one element, z T2 is 2 L1, p
1 >-Lipschitz
Mn +
npa
Proof. Suppose without loss of generality that Z and z' differ only the first element 21 # o Then:
x2(2) 2z(x')) - क +
(sr 02 (I), 21) [(x (1
- 02 (x), ((d.))))))))
+ [f 02)) f(x f('
1 n
1ls f(e' (x'),
1=2
For = 1, we have
1f(x,02())) (x), 21) - f(a',002 (x'), (x)).
$ 1f 12 (x), 21) - -f(x', M2 (I), zı + (2'' (x), - (x'),, 21)
5110011 z'll 11. |
x' ||
Pg
where the last inequality follows from Lemma
B.5 The same argument works for 21.
For each 2 (where z; is the same in both datasets), recalling that 11 (x) T2. S
2ba. Pg
we
have
(2(), 21) (2.
[f 24) - f(0', U2 (x'), 24) Vef(tz + (1 - t)2l 02 (tr + - (1- (x x')
Val(kx + (1 1)a' Tz. (lx +
(x - x')
Using the smoothness of Va with respect to y::
1//
V Vlx + (1 1)o', Tz (lr + (1 - 1)='), 21) V2J(1x + (1 100.02200.0 (Ix + (1 ()x'), =z)
3 11 (1 t)x²) TZ (tx + (1 - +))='))(dtt
((¹ 35.a 2Lg 2 2Igg.111.2
n4gg
n2/gg
Therefore,
(1x,03(0)) 2i) - 2:) (2))), - 10'.05 (2'),
2L 31.00 1|- x'1
<
n142
15

---

A similar analysis applies to the term involving and 21, with an additional constant accounting for the difference between functions. Therefore,
L1x (L +
Liw Pyt
Fz(x) 22(x') xz + (z)) 22
1|0 x'11,
11g1
as desired.
B.2 Generalization error of the regularized exponential mechanism for bilevel SCO
Another advantage of the Regularized Exponential Mechanism is that it can have good generalization error.
Lemma B.7. If we sample the solution from density (2))) exp( exp(-k(022(1) + |=|>=11/// the excess population loss is bounded as
d2
Lan +
LLg,y + T.s.))
Li Poyku
B P.w ((x) Φ6) 2
Ro + DD2 +
3g + Kig)
Mgn
Pi
1gg
LS Lingo (1 + Kig)
Pggt
where
Ki Pa.uu/
(13)
L 2 [1,,0t + n
T.s.u8g.20 Hg
T T.g.uBgay
(14)
Hg
C. = Bq (1 *kg))
(15)
Proof. We have
Ex-zz 7w [2(x) 441 Zx क2(2) + - -611
By Lemma we have
dn k + nD2
E Z~ Zn
Next we bound the generalization error. Note that
Eg 2 (0()) [1)) = Bewaz. pm F (x, y² (z)) - Fz (x)).
Recall that 7 = {=1,... }. Suppose we replace E Z by fresh independent sample z/ from P
and get Z'. Then we have
Exn 7 [F y (x)) - Fz (2)
-E 7. (x ( (z),
f(x. T2 (z), 2)]
-B Z.x; [1 (z'), - ExNaz d (s (x), =]]
-B
2. .2.;; [1 (z)),=) - s(x', TZ (x 0) =;)
Ev'nay [f (2)), 2)]] - Ex y Z (a', T2 (z), 2|]
Eggnag Z [f(2 02 2:) Egviz Z (f, 92 (z), 2)).
where the first equality follows by the argument in Lemma 7]. Recall that in the proof of Theorem 3.2. show that for any x,
2Lga
(1) (x)) <
Mg
which leads to that
2L S.s. L 14 n
Eyg Bagw Z. (/ (x) [)) -B 21]
16

---

By Lemma B.5 we know for any Z, we have
z.) [(' (0'00'(')). 21)1 = 1f (z)) - [(x, 02 (x'): 26) + [ax 02 (x)), 21) 5(x', 02 (2 2:)
L
Li + Iig.5)
|| - x' + I.g.2 || - x'1l
1| x'1l
Hg
Hg
Moreover, by Lemma B.6 and [24
we can show that (2 S L with L = 2( bi
Ba + L.a
Hence we have
Mgl
nig
BeNny 2, Lf (2, (2), zill -
2i]
Bz,,, [Bewxz) 1z (x) Eewaz h2, (x)]
L 1.yga. + Lg,)) (T2
My
Li + L/p
Fg
Now, by Lipschitz continuity, it remains to bound the right- hand side of Re' Z,e 1/ (x)); 2i) f(d (1), 2:)] R -0) (z), 2/)
(16)
S <Lin (x))ll
(17)
For any x, by the strong convexity of g, we have (v))(,,T2())) VyG(a,y"")) y (x)) 11
By the first-order optimality, we know that V v,G(z, (x)) 0, and hence we know
(1) - (z)1l S (Z
Similarly, we have
(x)) =0
and
11 G,
Next, we bound
E Exnaz 2
v,G2(z,
Let u(2,z) = V, Glz (z)) - V GZ Using the law of total variance, we have
Ez [aa,
Varz (ar (,,, + 1B,22/v(2 (l,(Z
Term
Term
Term
Note that we have
(x)(),
Gv, (2)))
< By || x'1l + Bg. 10 (z) - 72 (+'))
Ba.wn 9.
$ (8g,zg
|o 21
(18)
Mg
where we apply Lemma B.5 for the last step. Similarly, we also have
(x')0) s (Bg.ny B Bg. gay 1|
|1 (z,) - (1)
x'1l-
Mg
17

---

For Term A, for any dataset Z, 2 is kto-lly log-coneave, and function is Lipschitz in z with Lipschitz constant (gg.ry my + 8y FuweRue ) specified in Equation 18 By Poincaré inequality, we have
(8g.0g + P Po.vo )a
Vargwnz 2 (u(2,x)) -
V (Z, = ki
kj
Mg
As for the Term B, let (()) = Egwny u (2 By the Efron-Stein Inequality, we have
(ar()(Z))= -
E [l]l(()) uZ2))
"h 2 [= - - vZ22)13
2
jELn]
where Zj is the dataset with 2ÿ replaced by fresh sample. Then have
Ellu(Z) - v( =(2')l = Ez,,! Be (Z) - Exwry of VyG(z, 02 (z)) - (E V 1, (2 BENTE V.G T2 (x))
By Sestorovvic--ubinssetee duality and Cauchy-Schward have [[<)>~((>)>>>> (h(=)) S Wi (T) S W2(TT,
for any 1-L.isschizz function h and any distributions ,, x' E Lz. By Lemma B.5 the above fact
implies
S 80. (T()
1 Ag.sy L/p. Hg
E (x) E F2(22)1
Hg
A similar argument can be used to bound
|Eenaz V,, (x)) - Ex' GyG(e',022'') S 2y W2( S 8g.z Lip,
and likewise for V,,GzEz, 77 (z)). Hence
El Ellu(Z) - x 2(Z')11 - Ez,2! EENTZ V (G(,, - EN'NTH VyG(I', (x')))))
+ Ez,, |Eg'nnT V,G(s', 02 (x') EN'-EYy V, 02 (x) |)
+ Ez,,; || |BI'NNT: V ,,G (1', (1'07 BRNNY V V, (z. iz (x))
+ Ex,e |BENT G2 F2(2)) - EENTZ V G2 (z. Tz (x))
(oaee ps (1)
(Bamm
$g.30 L + Lg
2
+
L
2
+ (
L gg
2
12
+
11
1l
n
Therefore,
(L)
2
2
gg (Mg 112
Var(v(Z)) S Cn Var()(Z))$C'
(19)
11
for C' defined in the lemma statement.
We already bounded Var(u(Z)). As Fl[n (2) = Var(o(Z)) + [IBe(Z))2 It remains to bound
Term C: [Z)(()] 2. For this, have
Be((Z) = -B 2. &
(x, T2 (1), #/) - V Vug(z, T2 (x), 2;]]
-B
719 T2 (x'), =] E = V 0 U2 (x), 21))
E ,g(l' T2 (I'), E
gz( (2)),
+ F w 2 a V gg(a' (x²),
E Exaaz o V , 17 (x), 2:)]
Hence
[E(] < 3g.wv 2Lg
+(3 (Bg,ey + By. 9g.zy W W2
Mg
1gg Bg.oy L 1
2Lg
3g.vw
+ (Bg.ry
Mg
Taking square roots and combining all the pieces above yields the lemma.
18

---

Theorem B.8 (Precise Statement of Theorem 3.3. Grant Assumption 2.1 and parts 3 and 4 of Assumption 2.2 Assume z and & convex for all Z. Sampling T from distribution proportional
to exp(- (x) + /||==1 with k: = (G (oR((1))8)
un??²
and G = (Teg,a + Liw Ly.y f.ay
(e, C)... Moreover,
setting log((// nD,5
achieve excess risk
(41s+
Dr. v d. log
E+ (
8 50
+
1g
1g
ne
setting
G LiyCC
de log(1/))
GCL,y G (11s* +
L
# Dz
+ +
+
En
E2n
PLvn
n
14g
for
C Bg.zy( (1 + kig) with Nig
/g.vv/ Mg. the population loss has the following guaran-
tee:
Φx $ Dz (T((T)
G
/ de logllo/0//
(V
+ G + I. pg) + T. (15g 1)
Li
Vn
en
Mgg
1gg
GCL
Lg.y Lgg
n
1/4
Bg
MyT
Proof.
The privacy guarantee follows from the privacy curve of Gaussian variables and Lemma 6.3
124
G (1))((
When setting 1
Lemma B.2
gives us that
nD25
d
nDa
G² log(1/6)
μD² = O GD,
de log( 1/6)
z
K
2
2
The population loss guarantee follows from plugging the prescribed and into Lemma B.7
19

---

B.3 Efficient implementation of conceptual algorithms
many practical applications of optimization and sampling algorithms, we face unavoidable approx- imation errors when evaluating functions. Given any we may not get the exact 1/2 (1) in solving the low-level optimization, which means we may introduce small error each time we compute the function value of fz, 1/2 (z), 2). This section analyzes how such small function evaluation errors affect log-concave sampling algorithms. We establish bounds on the impact of errors bounded by on the conductance, mixing time, and distributional accuracy of Markov chains used for sampling. We then develop an efficient implementation based on the [ approach that maintains polynomial time complexity while providing formal guarantees sampling accuracy in the presence of function evaluation errors.
B.3.1 Original Grid-Walk Algorithm for Log-Concant Sampling
We first state the classic Grid- Malk algorithm from Applegate and Kannan 3 on sampling from log-concave distributions.
Let F(-) be a real positive-valuee valued function defined on cube A [a, bjd in R where [a, bjst represents a hypercube with side length & := b a. Let f(0) log F(0) and suppose there exist real numbers a, such that:
[f(z) - f(y)) S max |z, - vil
[E[1.d]
f(Ar + (1 A)y) 2 Af(x) + (1 x)f(y) B,
for v, y E A and À E [0.
Let y I 1/((2)) be a discretization parameter. The following algorithm samples from a distribution on the continuous domain A such that for all 0 E A, (p(0) cf) S e, where normalization constant:
1. Divide the cube A into small cubes {Cz} } of side length with centers {x}. Let Ω be the set of all such centers.
2. K. < 1/a, then pick a point uniformly from and output with probability F(0)/(e mexzze F(x)); otherwise restart.
3. For x 2 1/a. proceed follows:
(a) Choose starting point zo Ω arbitrarily.
(b) Define random walk on the centers of the small cubes as follows:
i. At a state (cube center) x, stay at & with probability 1/2.
ii Otherwise (with probability 1/2), choose direction u E {=e1, ". tea) uni- formly random (each chosen with probability 1/2d), where e, is the standard basis vector in the i-th coordinate.
iii the adjacent cube in that direction not in A. stay at æ.
iv. Otherwise, move to the center of that adjacent cube with probability
min(1, F(w)F((() with probability 1 - min(1, F())/F(x), remain at
(c) Run this random walk for steps. Let be the final state.
(d) Pick a point uniformly from the cube Cz.
(e) Output 0 with probability F(0)/(eF(z))) otherwise, restart from step 3(a) with new recursive call.
For implementation details, we refer to the original paper 3 analyze how this algorithm behaves when the function F can only be evaluated with some bounded error, a common scenario in practical applications.
In the subsections that follow, we
B.3.2 Conductance Bound with Function Evaluation Errors
The conductance a Markov chain measures how well the chain mixes, specifically how quickly converges to its stationary distribution. For Markov chain with state space I2 transition matrix P
20

---

and stationary distribution q, the conductance yp is defined as:
Exes. (()) ((5)
min $1
Higher conductance implies faster mixing, while lower conductance suggests the presence of bottle- necks in the state space.
We now analyze how small errors function evaluation affect the conductance of the Markov chain used in log-concave sampling, described in Section B.3.T] This analysis is central to understanding the robustness of sampling algorithms in the presence of approximation errors.
Lemma B.9 (Re-statement of Lemma 3.6). Let P be the transition matrix of the original Markov chain in the grid-walk algorithm of Section B.3.7 based on function f. with state space St and conductance ş. Let P' be the transition matrix of the perturbed chain based on I' where (0) f(0) + {(0) with [((0) S for all 9 E Q2 where 5(-) is an arbitrary bounded error function and Ç > is upper bound its magnitude. Then the conductance s' of the perturbed chain satisfies:
o' 22 65 p.
Proof. Fix any subset of the state space. The conductance of in the original chain is:
Exes.ve (())
Pg min min(Exes (F)), En4s {()}}
where q is the stationary distribution and Pay the transition probabilities.
In the grid-wall walk algorithm, we know Pay 0 if x + y are not adjacent; for adjacent points æ and y::
1
F(y) 1
min((,e-((0)-1000)
Pzy
min
1.
4d
F(r)
4d
and remarkably Paw = 1 Exjy Pzg.
For the perturbed chain with adjacent xt y::
F()) 1, F'(x) 5
P
-
min
min (1, min(1,,-(f(())) ((())))(())
4d
4d
Since f'(v) f'(x) = f(v) - f(x) + (C(y) - ((x)) and K(y) ((x)) s 2Ç, we have:
e ((1))))1(()22)) < - (V' I ((w)))))((+))
This implies:
e 25 (mmm(1,e((())((tt)) < minf11 -((( < minn1,,e-(1)---
Therefore:
2C Pay S Psy S 26 Pay
e
The stationary distributions q and q' satisfy:
F(x)
and (((x) F' F'(x))
((x) = Ereo F())
Exen F()
Since F' =
= f -(() -e(0))c()
= =F(z)e ((x)), we have:
Exen F(2)
Exen F(2) Eren (2)
c q(x) q())
Even F2(2) < (x((x) S el ((x))
The normalization ratio satisfies:
ExEn (2(
<
Exerr F(2) Sec
21

---

Therefore:
26 .(())= S d'(x) S E q(z).
Using the bounds on transition probabilities and stationary distributions:
Σ xES.EAS
( 2e 4<
Σ
g(x)
#ESyES
And:
min
Σ (x),
Σ (x)
S ec min Σ
f(x),
Σg(r) ((x))
2ES
LES
248
Therefore:
ExER, d' (x))
433 min EvES (2), Ex))
46 Σ EeSS (())
2 min ( (0), Exes (2))
66 ps.
Since & ming os and s0 ming S''s, have:
6 2 e 66
B.3.3 Relative Distance Bound Between F' and Fr
We now analyze how function evaluation errors affect the distributional distance between the original and perturbed stationary distributions.
For distributions, we define the Too distance (or log-ratio distance) between distributions j and on A as:
log n4)) v(0)
Dist (H,2) sup 8EA
(20)
Lemma B.10 (Re-statement of Lemma 3.7 Let F(0) (() and F' e- where (' f(0) + C(0) with (C(0)] s for all E A. Then the relative distance between F' and F is bounded by:
F'(0) F(O) <e,
VO A.
Furthermore, if we define the distributions π (0) x F()) and n'' (0) x F'()), then the infinity-distance between them is bounded by:
T'()) (1())
Distor (T' sup θЕ
log
< 2Ç
Proof. For any E A, we have:
F'(0) = =0 ('(0) = - -((0)+((()) =e- -5(0) ((0) F(0))-((0 C(1)
Since [C(0) S S, we have:
- < -((0) < cs
22

---

Therefore:
= - F(0). .
For the normalized distributions, have:
F(O)
(0) = SA F(z)dz
(O)
F(0)e-(10)
(0) SA (z)
JA ((
This gives:
π (0) F(0)e- <(D)
F(
<(0) JA F(2)dz
((0) SA (F(2)--sia)d
F(O)
Ja (2))
Since < S (((() < e for all A, we have:
e- J d(=)dz+ < / F(z)e ((t))= S F(z)dz.
Therefore:
26 7'
(0)) S 25
Thus, the -distancce between n/ and ग is bounded by:
sup In r0) BeA T(() 2Ç..
Dist m)
B.3.4 Mixing Time Analysis and Implementation Details
For a Markov chain with state space Ω2 transition matrix P, and stationary distribution म, the mixing time (c)(() (c) with respect to the - -distance is defined as:
(c) min (1
max Dist (Pt (x. m())) c), zEQ
(21)
for any e 2 O. For efficient implementation of the grid-walk algorithm, we utilize the results of 9 Following their approach,
determine the number of steps required for Lx convergence using:
Lemma B.11 (Mixing time for relative L convergence [1]). Let P be lazy, timerrevesible Markov chain over finite state space with stationary distribution w. Then, the mixing time of P w.r.t. Loo distance is at most
A/c
4dx
L00
1
(22)
(x)
where xp(x)= inf(ys: x(S) 2), ys denotes the conductance of the set S and n.
minger ((x) is the minimum probability assigned by the stationary distribution.
We now provide a bound on how function evaluation errors affect the mixing time.
Lemma B.12 (Re-statement of Lemma 3.8 The mixing time t'mix (c) of the perturbed chain to achieve Los distance to its stationary distribution satisfies:
(
Q2²22 2
e max dlog orVa
.a7) .or))
t'm (c) S 12c
23

---

Proof. For a concave function F(z) = e- f(z) where f is o-Lipschitz, we set the grid spacing parameter 7 2 Using the conductance bound from previous analysis [.) we can derive the lower bound on conductance:
(x)) S
By Lemma 3.6 conductance v for perturbed chain F' satisfies
('(x) 2 e -
80723/2
By the Lipschitz assumption, we have that
(u) c0T--2 2 (T/r)/
<'(u) Even F'(o)
Hence, by the lower bounds of conductance and minimum probability in the state space and Lemma B.11 we complete the proof.
Building upon our analysis how function evaluation errors affect conductance, mixing time, and distributional distance, now develop efficient algorithm for sampling from log-concave distributions the presence of such errors. Our approach builds upon the framework developed by Bassily, Smith, and Thakurta [9], extending it to handle approximation errors with formal guarantees.
Theorem B.13 (BST14-Based Implementation). Let C C Rd be convex set and J C a convex, L-Lipschitz, function. There exists an efficient algorithm that, when given exact function evaluations, oulputs a sumple 0 C from distribution such that the relative distance between y and the target log-concave distribution N (0) x e f(0) can be made arbitrarily small, i.e., Do (H, T) S. for any desired & > O. This algorithu runs in time O poll(L, ||C 1/E)), which is polynomial in the dimension d, the diameter of C, the Lipschitz constant L, and the accuracy parameter 1/g.
The key techniques in this implementation include:
1. Extending the function f beyond the convex set to a surrounding cube A
2. Using a gauge penalty function to reduce the probability of sampling outside C
3. Implementing an efficient grid-walk algorithm to sample from the resulting distribution
We now formally incorporate the effect of function evaluation errors into this framework:
Theorem B.14 (Re-statement of Theorem 3.9 Let C C Rdd be convex set and f C + R. be convex, L-Lipschitz function. Suppose we have access to an approximate function evaluator that returns f'(0) f(0) + <(0) where [C(0)] S all 0 C, and Ç = O(1) a constant independent of dimension. There exists an efficient algorithm that outputs a sample E C from a distribution pi such that:
Distoo 5C
(23)
where x0) x (10) is the target log-concave distribution and 8 > 0 is arbitrarily small constant.
This algorithm runs in time Oee d poly(L, 1/E)), When Ç = O(1) is a constant, this remains Odd poly(L. ||C'|2, 1/E)) with the same asymptotic complexity the exact evaluation algorithm, differing only by constant factor 125 in the running time.
Proof. We follow the approach of with appropriate modifications account for function evalua- tion emrors:
1. Enclose the convex set C' in an isotropic cube A with edge length ||C||

---

2. Construct a convex Lipschitz extension f of the function f over A using:
vEC T(x) min (f(w)) L|| yll2)
This extension preserves the Lipschitz constant L and the convexity of f.
3. Define gauge penalty function using the Minkowski functional of C:
(, = a max(0, (00)) -
where v)(0) in 0: 0 rC} is the Minkowski norm of 9 with respect C, and is parameter set ensure correct sampling properties.
4. Define the target sampling distribution:
(0) x e 1(0)-v_()) 40 E A.
5. presence of function evaluation errors, for 0 E A, the algorithm samples from:
(0) x e (0) (.)
where 7((0)= [(0) + ((0) and [c(0) c.
6. By Lemma 3.7 on the relative distance between distributions, we have:
Distac (T', ,,) - 2Ç.
7. For the sampling algorithm's computational efficiency, we note that by Corollary 3.8| the mixing time increases by a factor of gl2C_ and the modified algorithm's running time becomes (e .3 poly([., ||||2,, 1/E)).
If is constant, then the factor e22 is also a constant. Therefore, the algorithm maintains the same asymptotic polynomial complexity in d the exact evaluation algorithm, with only the leading constant factor affected by the approximation error.
Theorem B.15 (Exponential Mechanism Implementation). Under Assumptions 2.1 for any constants E = O1), there is an efficient sampler to solve DP-bilevel ERM with the following guarantees:
The scheme is (e, D)-DP
The expected loss is bounded by Ô de Ly.xDz + L. + Bentaw))
The running time is O (don poly(T,, Da, 1/8, Io,(dI. /.y// (g)) h dnn Lox poly Dz, 1/e)).
Let Z and Z' be adjacent data sets. Consider the exponential mechanism and the probability density iz proportional to exp(- 2/ (z)). We set Ç = e//6. Let the T'Z be the probability density of the final output of the sampler. Then by Theorem B.14 we know
Proof. Privacy:
Dist oc =2) S 6
By Theorem 3.2
we have
Distos (TZ, SE'
Hence know
Dist 122,T22 2='
and setting = e/2 completes the proof of the privacy guarantee.
Excess risk:
The excess risk bound follows from Theorem 3.2 and the assumption that & = 0(1).
25

---

Time complexity: Given function value query of (2(2),, we need to return a value of error at most ç. By the Lipschitz of far 2), it suffices to find a point such that
11 (x)) S L/
By the strong convexity of g(x,,,2,, there are multiple ways to find the qualified y. In our case,
simply apply the cutting plane method [2), which can be implemented in ((@noooyyloog(( //P(o)))))) /PP))) Alternatively, we could apply the subgradient method G (2 (2.-).
which can be implemented in (dn( (ae)) (ww)): Combining the query complexity in Theorem B. gives the total running time complexity.
Pg
With Theorem B.8 and a similar argument on the implementation, we can get the following result of the Regularized Exponential Mechanism.
Theorem B.16 (Regularized Exponential Mechanism Implementation). Grant Assumptions 2.7 and additionally assume v y, V=f v', z)11 S Byayylly - v'll and vy,Gz(z,) y) V V, y))ll gg, x'Il for all x, , y, , Given & = 0() and 0 8 1/10, there is an efficient sampler to implement the Regularized Exponential Mechanism and solve DP-bilevel ERM with the following guarantees:
The scheme is (E.8)-DP:
The expected empirical loss is bounded by O (( + LeuBoon + Low Dr yd log(1/5)
Mgg
Lis The running time is O (d polyppoly Dr, 1/E, pg)) A d'n
po--poly(,, Dz, 1/E)).
With
different parameter setting, we can time and achieve the expected dd de (1g(1/8)
get the (e, sampler population
with the
same running
loss as
(I+ + Leuga Lo D2
Vn
B.4 Excess risk lower bounds
Theorem B.17 (Re-statement of Theorem 3.10 1. Let A be S-DP. Then, there exists a data sei Z E nd and convex bilevel ERM problem instance satisfying Assumptions 2.1 and 2.2 with Pg = (Lgg Dy) such that
(²z(A(Z)) - 3z =2 -11 + byy min {1, dg
nE 1)
2. Let A be D) with 2 2-1)(n) < 5 1/nl+4(()) Then, there exists data set Z E z and convex bilevel ERM problem instance satisfying Assumptions 2.1 and 2.2 with 1lg D(Lg.//D)) such that
(O2(((Z)) - -6 =Ω (LLT.DD + Dy) min { v dzz log(1/0)
})
Proof. Case 1: Suppose DI I Ly Then we will show oz(A(2)) 12 a ((LL,)D,) min (1, na da mz with probability at least 1/3 for (5,5)-DP A.
with probability at least 1/2 for pure e-DP and (A(2)) 22 =
? (L111) min
Let f(z y, 2) -y, 2). which is convex and 1-Lipschitz in and y if y E are unit balls in Rd. d dg = dyy and = (#I/Vd)d, Let g(z, y, 2) = lyy - <x|l² for ( > be chosen later.
Note Fz(z,,) = (y, Z). where Z = Σn 24. (x) (x. and 1 (x) Fz (2.
(-çx, Z) + x (2) = argmin DEx (x) = Z
Therefore, for any x E X, we have
[21
Z
$z(2) 2z (8* (Z)) - Z |
26

---

< [1|]] (1 (2, (z,))
- | -
z 2
(24)
since ||-||| | (Z)ll S Now, recall the following result, which is due to 9 Lemma 5.1] and [48
Theorem 1.1]:
Lemma B.18 (Lower bounds for 1-way marginals). Let n, d 2 1,0 0,2-R(m) S < 1/nl+0()
1. s-DP algorithms: There a number M (minn(n, d/e)) such that for every E-DP A. there a data set = (Z1...., 2n) C. {=1/vd] with |Z]| E [[M 1)/n, n, (M + 1)/ml such that, with probability at least 1/2 over the algorithm random coins, we have
[[A(Z) Z Ω min 1, d )
2. (e, (DP algorithms: There is number M (mmin((, v /loog( such that for every (e, 8D- A, there is a data set = =21, (21,..., zn) C {+1/va]á with ||]|| e [(M 1)/m, (M + 1)/n] such that, with probability at least 1/3 over the algorithm random coins, we have
/ /dlog(1/0)
IA(Z) - Z11 = Ω
min 1,
En
We claim there exists Z E z" with | E [[M - 1)/n, n/, (M + 1)/n] such that
Z
A(Z)
21
(25)
|2|
with probability at least 1/2. Suppose for the sake of contradiction that VA 2n with |Z|| [M - 1)/n, (M + 1)/n], we have
Z
A(2)
<>
7
with probability at least 1/2. Let E 11nn,, 1/n] such that |Z] = M/n + Then for the e-DP algorithm Á(Z)= := M A(Z), we have
M A(Z) 2
(ÁĀ(Z) 211
n
M
M
Z
A(Z)
+ c
n
n
17
M A(Z)
Z
Z
+
n
|
7
M M+1
7
n
which implies ÍÍ(Z) 2|| < 1
5nL contradicting Lemma
B.18
By combining the claim 25
with inequality 244. we conclude that if x = A(Z) is e-DP, then
< [| |||
22(2) 3 2
E (2)
2
M
1 12 ( min {I, d
2 < n
me
Next, scale hard instance to obtain the DDD lower bound. Define the scaled parameter
domains X D.B,Y y Dy 2 Z = (+1/Vd} d and denote f Da Dyy for any x,y X x y 2 Define f x 2 - R by
f(ä, 0. 2)
م (ū. Z)
27

---

which is convex and y,y- Lipschitt in y for any permissible ă, 2. Define g: X x Y x 2 + by
My 2 1 cāl
g(ā, ū. 2)
where
< == Duj Dz.
Then 9 is -tronngy convex in y and -Lipschiz, since Lgg 2 Pq Dy. Now,
F2(2, = Σ f(ž,0, = -L 2), 1=1
[G2(E, () Ite 1/ 1 Çā V,
( argmin gERRv
and
$(5) = (2, (z)) - L 2).
Also,
7
i == argmin x (()
D2 (2) Dr 7
|
Thus, for any E-DP A. there exists a dataset Z Z such that the following holds with probability at least 1/2, where we denote ā A(Z):
6(6) - 5(
- -15.0 [( 23 ((82 2
=-Lsaoh [Dx - (2), 2)]
-LL..uDDa (
7
1 7
DoS
|| ||
5" (Z)
d
2 LLs D2L
En
d
Ly
Lnn
The argument for the (c, 8)-D case is identical the above, except we invoke part 2 of Lemma B.18 instead of part 1.
Finally, it easy to verify that Assumptions 2.1 and 2.2 are satisfied, with Bgaay S D= Cg.ay
Cg.vv = MM = Mg.ay = 0 = 8y.az = f3, Br.v-
Case 2: Dy 5 Dr. In this case, the desired lower bounds follow from a trivial reduction
to the single-level DP ERM lower bounds of 22, Theorems 5.2 and 5.3]: take y { for some
yo E Rd with l1 < Dy. X = D,B, = (#1/Vd}² /dddd and let f(x y, 2) = =L, (x, 2) and
2(x,,,2) 2 |y/l Then f and satisfy Assumption 2.1 92 (x) = yo. Fz(x)
Φ =
- , (x, Z). Thus, the lower bounds on the excess risk Fz (x) F for DP x given 9 Theorems
5.2 and 5.3] apply verbatim to the excess risk ZZ(x)= Tz. This completes the proof.
C Proofs for Section
C.1 An iterative second-ordes method
We have the following key lemma, which will be needed for proving Theorem 4.2 Lemma C.1 (Re-statement of Lemma 4.1 For any fixed x define the query q: n RRd,
qe (Z) = FZZ(x 11+1);
If a S En where C and K are defined in Equations and 12 then the sensiiiiyy of qu is upper bounded by 1K
where Dt+1 1 is given in Algorithm
7
K.
28

---

Proof.
We will need the following bound due to (23 Lemma 2.2]: for any 2, E X 3
( - (F2 - C1103
yll
(26)
for
C = Bray + AI.uPSgo + Lsv
Cg. Hg
Cg.vvBa.ry
My
Pig
Now, denoting 1/++1 11++(( and 1/41 U++1 the sensitivity of the the query qa is bounded by
sup Z-Z
(Z)e =x((Z')
[F2( V Fz. (T
sup
2~22'
|V (. ( x - (xx((1)) + [[
Viz (14)))
sup Z:-2'
C'lue+1 - (x))] (x, ( (x))) + (2-)l
20a +| ( - (x,)(
2K + ( - (x)))
where used the bound 26 and our choice of a, for K defined in the theorem statement. Next, claim
2K
(x+)) S
(27)
This will follow from rather long calculation that uses Assumption 2.2 repeatedly, along with the perturbation incquality ||M- .N- - < |M | - |N] which holds for any invertible matrices M and N. Let us now prove the bound (27). In what follows, the notation V denote the
derivative the function w.r.t. x (accounting for the dependence of the function on T2 (2) via the chain rule) and denote
M2(2,0) = V2
Then. |
(xx))
(x=))
n
V ff (Z) -ft.,,..))
+ -/a
n
1
[Va V2 (z), (3),
M2
Vf (/.
1
Byayy - (z)
Mz
2)) (a
n
V T2
(x)
V T2 (x), +1)1l
n
where we assumed WLOG that स oं and used the smoothness assumption in the last inequality above. Now, recall that
1) -2z) (2)) $ 2Lg
1,g n
29

---

and note that
(2 21)
(z), 2 =
[1,,
M9
by the chain rule and (3g,zy/ halp///)))))))))
Lipschitz continuity 83z (see (23) for a proof this result). Thus,
2.
|| (xx) 26 (sx))
3 fay
7
1g
i=1
11
2L
+
Next, we bound
sup z.7
( +
+ sup
x.2
2T. + L,,,, -
Bg.5v 31.00 nn
(2.
Ng
remains to bound
- M2
+ 33360310116641000000333333333343
Cg.z 10 (x) (x))
Ug
G2 (x)
+ 9g,0y
(x. ( (x))
28g.ay
20 I.y.
V2 ( V2 (x))
3 8g,ay
28g.my
Un
2C Ly
P2n
3ggay Cg.vyll (2) - O2. (I)
212
2,9g.19
3g,ay p2
30

---

g9g,ay
2C g.y Leg. pn
20 g.yg B.M 1 + ggy
9.9.
3g.ay
p2
23g 23
Ug
where in the second-to-last incquality used the operator incquality
|| N ||M - N ||
which holds for any invertible matrices M and N of compatible shape. Combining the above pieces completes the proof.
We have the following refinement of 23 Lemma 2.2c]. in which we correctly describe the precise dependence on the smoothness, Lipschitz, and strong convexity parameters of f and g:
Lemma C.2 (Smoothness of Zz). Grant Assumptions 2.1 and 2.2 Then, for any I1,
( - (22(202)1 S f011=1 x2l1,
where
23, 23y.ayBg.u
82 3.00 12
Lg,yBg.vv m2
(Ma.vv + Cg.vuDg.vy
L. Cr.yygaa + Ly g.zg
Be = -y,xx
)
Mg
pg
Pg
(28)
Proof. Recall that
Vott)--V..A(173)))--:M00 (1)),
where
M(x,y) V>,,,, Cz(
Also, MZ 8a.a Lipschitz (c.f.
23 Lemma 2.2b)). Therefore,
( - (,
+ +NNN::/22ll1@f222222222e2222,,13
+ (x1, T2 (x1 (x1))
M 02 (r2)))
$1,22 + 9
|| ||11- - x22l
Ug
Mg
+ Te
V2 G2
[ G2 17 (I2)
G (21, ||
- V2
+ Ls
$ (8,.0 +
35,0y0n.00 ) ||:11 - -x2ll
Sq.zy
81,300
80.0 |m - x2 + B | - x2ll)
1gg
1gg
1gg
+ T.g.018,.0
V Gy (2()
|
Liw
(21)) V (z(
2
Pg
31

---

23, 233,0099.00
S2 3g.0
fyæ +
1| 111--20 - x2ll
Mg
L L..y
(2 (211)
G2(11
82
-
v G2 82 (12)
Law (C
(Cy.zy (022))00((111) (22))l + Mg x2
2,
ffa
|1-1 - x2ll
M9
I. 1.FaBgg.r
(C
Bgaay ||||
[M 1|= - x2ll + C (01) 822 (x2))l] +
x2ll Mg.ry x211
2gz
Fg
where we used the operator norm inequality
|M N I|M -MMM-AA -NIIIN
which holds for any invertible matrices M and N of compatible shape. Using the Lipschitz continuity of Uz one last time completes the proof.
Theorem C.3 (Precise version of Theorem 4.2 32K /T (og(1/0) and
Grant Assumptions 2.1 and 2.2
Set
KV (62(20)) - 33)) 3o dd log(1/8) 1/2
K nC'c
a min
EN
for C defined in Equation in Algorithm 1 where
+ 2L + By 31 1 Lyy + Ly +
Lo Cove +
L L 3g
K 2
Pg
Then,
Algorithu
is (P. Further, choosing
"
1/28g
and T
Ba (2) 122)
for Bo defined in Equation
28
the output of Algorithm 1
Vd, (og(1/8) satisfies
1/2
V x Ky (0z(z0)) 83) Bo
de log (1/6)
en
Proof. Privacy: By Lemma 4.1 the fz-sensitivity of VFZ(Er, 1 is upper bounded by 4K 4K/n. Thus, by the privacy guarantee of the gaussian mechanism and the advanced composition theorem, our prescribed choice of a ensures that all T iterations of Algorithm satisfy (s, O)DP. Hence Fr is (e, O)D by post-processing.
Utility: oracle:
We will need the following descent lemma for gradient descent with biased, noisy gradient
Lemma C.4. 1 Lemma 2] Let H be 3-smooth, 3e+1 = 24 1/ (xz), where ( = V (xx) b. N, is a biased, noisy gradient such that [[Ne(1r 0. [[ [x S B, and
E [||,,
[ < x² Then for any stepsize n) S 23. we have.
17 x²
([ (((x)
(HH)))) 7 B²
(29)
2
We will apply Lemma C.4 to H = tz which is f by Lemma H =
v Fx Be+1) + with bias b, = F V(+1) - 4 (z+) and noise N, = U
32 3 x2
B 32( < - 1 (x.) ! B²
2
2 - (xx) - 1z ( [zzz] + B32 + 11
E (
"1
32

---

2 (00(( $3/
r
[ =
Σ
+ B² + n1355
(30)
11T
for any - 1
29
Now, 23 Lemma 2.2a] tells us that
|V (ot Mo+1) V (1 -1t1ll+
for C' defined in Equation Therefore,
1/2
(82(20)- K /1002(00) - -82)
3x v d2 log(1/0)
B [ S Ca
En
by our choice of a. Further,
doo = 10
x = 2 x2
n²=²
Plugging these values into (30 and choosing 77 = 1/(22Bx) we obtain
2 (zo) 1b
B|
+ +B² + 11
1/l
4,3g (
+ KV
(0z( 1 33) 3g
de log(1/0)
1024d, K2T
log(1/0
T
n²g²
Plugging the prescribed T from the theorem statement and then using Jensen's inequality completes the proof.
C.2 "Warm starting" Algorithm with the exponential mechanism
Algorithm 2: Warm-Start Meta-Algorithm for Bilevel ERM
Input: Data g", loss functions f and g. privacy parameters (e, d), warm-start DP-ERM algorithm A, DP-ERM stationary point finder B;
2 Run (f/2, 6 on Zz(-) to obtain zo;
Run (e/2, 6/2) B on (.)) with initialization æo to obtain Iprivi
Return: privv
We instantiate this framework by choosing A the exponential mechanism (4 and B as Algorithm to obtain the following result:
Theorem C.5 (Re-statement of Theorem Grant Assumptions 2.1 and 2.2 Assume that there
compact set X C dRd of diameter D2 containing approximate global minimizer & such that $2 (z) 1 V d where
LinLay
Dy + V = L1zD2 +
Pg
Then, there exists an ()PD) instantiation of Algorithm
2 with output satisfying
E| V S (KWIY 2/23
1/2 do (do
1/2
(ne)3/2
Proof. Privacy: This is immediate from basic composition, since A e/2-DP and (e/2.8/2)
DP.
33

---

Utility: First, note that the output To of the exponential mechanism in satisfies
dx ET
Φ (20)
Ō
LI.DD= LyN
Mg
with probability 21-6 for any that polynomial in all problem parameters, by
19
Theorem
3. 3.111. Let say is good if the above excess risk bound holds. Now, by Theorem 4.2 of Algorithm [ satisfies
the output
1/2
Ky (1(02(00)) - 82) Br v dg log (1/8)
2 2
en
Therefore,
1/2
dx
1)
Bo V de log
E 2 (Tr)lla is good]
<
K
LI.DDa + Ly
En
Mg
(1 K
(de
dzz
de log
(og(1/))
1/2
=
En
en
Now, since (2(2)= 2 S LD2 for any X, the law of total expectation implies
( <
(fr ||1 is good
ID&S
1/2
dv
dg
(1/8)
S Ō
K
v
+ LD
En
1/2
dg
du
K
Bg
v
En
En
where the final inequality follows by choosing sufficiently small.
C.3 Deducing the upper bound in
We prove in Lemma B.6 that supz~z'. or Thus, by similar arguments used to prove the results in Section 3.1 one can show that sampling proportional to the following density is e-DP:
(x)) < 20 n where G is defined in (5)
exp (- E
2G
Moreover, the output of this sampler satisfies
G dz
E { 5
(31)
Further, outputting arbitrary Zo E X' trivially achieves V (xo))) S Lf.0 with O-DP. By combining these upper bounds with results in Theorems 4.2 and 4.3, deduce the novel state-of-the-art upper bound in for DP nonconvex bilevel ERM (with constant problem parameters).
D Limitations
While our work provides near-optimal rates and efficient algorithms for differentially private bilevel optimization (DP BLO), several limitations remain that should be considered when interpreting our theoretical and practical contributions.
34

---

Assumptions on Problem Structure. Our results rely on several assumptions that may not hold in all practical settings. For convex DP BLO, we assume that the lower-level problem strongly convex and that the loss functions are Lipschitz continuous with bounded gradients (and, for some of our algorithms, bounded and/or Lipschitz Hessians). These structural assumptions are standard in bilevel optimization theory but may not accurately capture real-world scenarios where lower-level problems are ill-conditioned, non-convex, or lack smoothness. Violations of these assumptions could degrade both utility and privacy guarantees, as our sensitivity and excess risk bounds depend critically on these properties.
Scalability and Computational Efficiency. Although most of our algorithms are polynomial- time, they may still incur significant computational costs, especially in high-dimensional settings. Our efficient implementations rely on sampling techniques (e.g., grid-walk) whose runtime scales polynomially with the dimension. This may limit practicality on large-scale or high-dimensional problems. Additionally, the warm-start algorithm for nonconvex DP BLO is inefficient. We leave it for future work to develop algorithms with improved computational complexity guarantees.
Lack of Empirical Validation. This paper focuses on theoretical analysis and does not include experimental results. While our theoretical rates are nearly optimal, empirical performance can depend on implementation details, constant factors, and practical optimization challenges not captured in our analysis. We defer empirical validation, including runtime mcasurements and real-data utility evaluation, to future work.
E Broader Impacts
This work advances algorithms for protecting the privacy of individuals whose data is used in bilevel learning applications, such meta-learning and hyperparameter tuning. Privacy protection is widely regarded as a societal good and is enshrined as a fundamental right in many legal systems. By improving our theoretical understanding of privacy prreeeeigg bilevel optimization, this work contributes to the development of machine learning methods that respect individual privacy.
However, there are trade-offs inherent in the use of differentially private (DP) methods. Privacy guar- antees typically come at the cost of reduced model utility, which may lead to less accurate predictions suboptimal decisions. For example, if differentially private bilevel model is deployed in a sensi- tive upplication-sucee as medical treatment planning or environmental risk assessment- -reduce accuracy could lead to unintended negative outcomes. While these risks are not unique to bilevel learning, they highlight the importance of transparency when communicating the limitations of DP models to stakeholders and decision-main makers.
We also note that the performance of bilevel optimization algorithms depends on problem-specific factors such as the conditioning of the lower-level problem, the smoothness of the loss functions, and the dimensionality of the parameter spaces. Practitioners should carefully evaluate these factors when applying our methods in practice.
Finally, while this work focuses on theoretical developments and does not include empirical evaluation or deployment, we believe that the dissemination of privacy- srrvacy-preeering iggorthms-aalonside clear communication of their and practitioners to build more responsible and privacy-award aware machine learning systems.
fiffimultitatlyy serves the public interest by empowering researchers
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: All claims rigorously proved.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
35

---

The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. It is fine to include aspirational goals as motivation as long it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
See Appendix
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All theorems carefully proved in the Appendices with all assumptions clearly stated.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch provide intuition.
36

---

Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: No experiments- is theoretical work.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (c.g., a large language model), then there should either be way access this model for reproducing the results way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification: Paper does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not
37

---

including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https for more details.
//nips.com ctips.cc/public//gg www.ce/ggiies/eee http:///gggiieee/eeeubbbbiiiiise
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma еrror bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
38

---

8. Experiments compute resources
Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics httttp/e/eeerrppppcc/////////eie
Answer: [Yes]
Justification: Research conforms to the Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e-g., there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
See Appendix
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (e.g., degloommet of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
39

---

If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks. mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual- usal-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswi thcode. com datasete has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
40

---

Researchers should communicate the details of the dataset/codeemmodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development this research does not involve LLMS as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
41

---

Please refer to our LLM policy httpss//Deerriigcccc//oorrrrrres for what should or should be described.
42


Reviews:
[{"review_id": "5UNbSX2rf6", "reviewer": "Reviewer_pJMr", "summary": "The paper studies the problem of DP bilevel optimizations for both convex and non-convex settings. For the case when the outer-level objective is convex, the authors provides both upper results for ERM and SCO cases. The authors also gives a matching lower bound result which show the tightness of their rates. For non-convex setting, they propose a new algorithm with improved rate over existing works.", "questions": "The questions are included in the section \"Strengths and Weaknesses\". I am willing to increase my rating if my concerns are addressed.", "limitations": "yes", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**:\n\nBilevel optimization (BLO) is an important question with many applications, while the topic DP bilevel optimization literatures are quite underexplored. This paper deepens the understanding of DP BLO by providing improved rates and matching lower bound. Notably, the idea of using exponential mechanism to obtain rate independent of inner problem dimension is both novel and interesting.\n\n**Weaknesses**:\n\n1. The paper primarily focus on the setting where the outer objective $\\Phi$ is convex. In practice, $\\Phi$ is almost always non-convex, even in cases where the loss function $f$ is convex. The paper lacks the discussion or justification for when and why the outer objective $\\Phi$ would be convex.\n2. The proof of SCO result (second part of Theorem 3.3) appears to be either incorrect or at least unsound. The proof relies heavily on the results in [22] (Lemma B.7). However, the results in [22] only work in standard finite sum setting, where the empirical objective $\\hat{\\Phi}(x) = \\frac{1}{n}\\sum_{i\\in [n]} f(x, z_i)$ for some loss function $f$. However, in BLO, the empirical objective $\\hat{\\Phi}(x) = \\frac{1}{n}\\sum_{i\\in [n]} f(x, y^* (Z), z_i)$, where each individual function $f_i(\\cdot)=f(\\cdot, y^*(Z), z_i))$ depends on the entire dataset $Z$. This introduces correlations among $f_i(\\cdot)$, $i\\in [n]$ which will fundamentally affect the generalization analysis. As such, the generalization analysis needs to be carefully revisited in the context of BLO, rather than relying on results that apply to standard learning problems.\n3. Section 3.2 is difficult to follow. My understanding is that it proposes an efficient implementation of the exponential mechanism introduced in Section 3.1. However, the discussion centers on newly defined functions $f(\\theta)$ and $F(\\theta)$, making it unclear how the results connect back to BLO notations $\\hat{\\Phi}$, $f$, and $g$. Can the result in Theorem 3.8 be directly applied to Theorems 3.1 or 3.3? If so, it would be helpful to explicitly state this, perhaps in the form of a corollary that illustrates how Theorem 3.8 leads to a concrete implementation in the context of BLO.\n4. How large can the estimation error $\\zeta(\\theta)$ in Theorem 3.8 be while still achieving the stated bounds in Theorem 3.1? Furthermore, can this level of error be achieved under differential privacy constraints?", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful and detailed review. We respond to your comments below: \n\n>Discussion or justification for when and why the outer objective $\\Phi$  would be convex.\n\nConvex BLO (i.e. convex  $\\Phi$) is important, as evidenced by the large body of work studying this problem non-privately: see e.g., Ghadimi & Wang (2018), Ji & Liang (2023) and the references within. There are **many applications of convex BLO** problems, including: few-shot meta-learning with shared embedding model (Bertinetto et al., 2018), biased regularization in hyperparameter optimization (Grazzi et al., 2020), and fair resource allocation problem over communication networks (Srikant and Ying, 2013). With the additional space allowed for camera-ready, we will add a paragraph on these applications.\n\n>The proof of SCO result (second part of Theorem 3.3) appears to be either incorrect or at least unsound\n\nWe thank the reviewer for this excellent and insightful comment. We agree that a rigorous generalization analysis is crucial, and we apologize for its omission in the initial draft.\n\nThe reviewer is correct that applying a classic stability argument (e.g., via a \"ghost sample\") to the bilevel setting is non-trivial. The main difficulty arises from the need to bound the error propagation from the lower-level optimization. **During the rebuttal period, we used new sound analyses to obtain a generalization error bound of order $O(\\min[1/n^{1/4}, \\sqrt{(d_x+d_y)/n}\\])$.**\n\n**Proof sketch:** As the first step, the $\\mu_g$-strong convexity of the lower-level problem allows us to relate the solution error to the gradient of the true objective at the empirical minimizer: $|\\hat{y}_Z^{\\text{star}}(x) - y^{\\text{star}}(x)\\| \\le \\|\\nabla_y G(x, \\hat{y}_Z^{\\text{star}}(x))\\| / \\mu_g$.\n\nFrom here, there are two ways  to bound the term on the right:\n\n1. *Uniform Convergence:* A standard approach is to bound the gradient term using uniform concentration arguments. This is a sound method, but as the reviewer might expect, it results in a dimension-dependent generalization error of **$O(\\sqrt((d_x+d_y)/n))$.**\n2. *Variance Analysis:* To seek a dimension-independent bound, we analyzed the variance of $||\\nabla_y G(x,\\hat{y}_Z^{\\text{star}}(x))||$. Our analysis utilizes the Efron-Stein Inequality. However  this path currently yields a worse generalization rate of **$O(1/n^{1/4})$.**\nIn the revised manuscript, we will include the complete derivation. We will also add a discussion framing the gap between our generalization error bound and the optimal $O(n^{-½})$ bound as an important open problem in DP bilevel SCO.\n\n>Can the result in Theorem 3.8 be directly applied to Theorems 3.1 or 3.3?\n\n**Yes**, and we have updated the manuscript to make the direct application of Theorem 3.8 to our proposed mechanisms in Theorems 3.1 and 3.3 more explicit. The function $f(\\theta)$ in Theorem 3.8 is instantiated as follows for our two algorithms:\n1. For the **Exponential Mechanism** (Algorithm in (4)), we set $f(\\theta) = (\\epsilon/2s)\\hat{\\Phi}_Z(\\theta) $ where $s$ is the sensitivity of the empirical objective.\n2. For the **Regularized Exponential Mechanism** (Algorithm in (5)), we set $f(\\theta)= k(\\hat{\\Phi}_Z(\\theta)+ \\mu \\|\\theta\\|^2)$ where $k,\\mu$ are two hyperparameters set correspondingly in Theorem B.8.\n\n>How large can the estimation error $\\zeta(\\theta)$  in Theorem 3.8 be while still achieving the stated bounds in Theorem 3.1? Furthermore, can this level of error be achieved under differential privacy constraints?\n\nIt suffices to **set the estimation error $\\zeta(\\theta) = O(\\varepsilon)$** in order to efficiently achieve DP and the desired excess risk bound. This follows from the distance bound in Theorem 3.8 and the following fact: if two non-negative random variables $X$ and $X′$ satisfy $\\varepsilon$-differential privacy, then $E[X] \\le e^{\\varepsilon} E[X']$. Now take $X$ as the empirical risk under the conceptual perfect sampler and X' as the empirical risk the approximate sampler (i.e. actual implementation)."}, {"review_id": "iT47LlB3En", "reviewer": "Reviewer_wGn3", "summary": "This paper addresses the problem of solving bilevel optimization (BLO) under differential privacy (DP), which is important for applications like hyperparameter tuning and meta-learning on sensitive data. The authors present novel upper and lower bounds for both convex and non-convex settings, covering empirical risk minimization (ERM) and stochastic optimization (SO). In the convex case, they match the rates of standard single-level DP optimization up to bilevel-specific complexity terms. In the non-convex setting, they design second-order DP algorithms with improved rates over previous works, including one that removes dependence on the inner problem’s dimension d_y. A significant contribution is the analysis of log-concave sampling under function evaluation errors, which enables efficient implementation of exponential mechanisms for BLO.", "questions": "1. In the definition of Bilevel ERM on page 2 following line 40, should the $\\hat{y}_Z^\\*$ inside function g() simply be $y$, given that the optimization is over $y$?\n2. In section 1.1, the authors claim the algorithm lacks access to $\\hat{y}_Z^\\*$ in convex DP-BLO, but since the inner problem is strongly convex in $y$, a unique solution exists. Can the authors clarify why computing or approximating is not $\\hat{y}_Z^\\*$ feasible?\n3. Could the authors explain more concretely why the warm-starting approach improves the upper bound? Also, since this approach uses the exponential mechanism followed by noisy gradient descent, how sensitive is the method’s performance to the choice of the warm-start point?\n4. When the inner solution is computed non-privately, could this leak information about sensitive data to adversaries?\n5. The grid-walk sampling approach is theoretically efficient, but how does it scale in high dimensions in practice? Are there benchmarks or estimates of runtime and sampling accuracy?", "limitations": "Yes.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n1. The paper tackles an important and underexplored problem: DP guarantees in BLO, which is crucial for privacy in hierarchical ML applications.\n2. It provides both upper and lower bounds, contributing a nearly complete theoretical picture for convex BLO.\n3. The proposed algorithms achieve state-of-the-art rates in the non-convex setting and offer dimension-independent bounds on d_y.\n4. The paper introduces novel technical contributions, including new analysis for log-concave sampling with approximate function evaluations.\n5. The theoretical results are comprehensive, covering both pure DP and approximate DP regimes, and highlighting separations between BLO and single-level DP optimization.\n\nWeaknesses:\n1. The work is entirely theoretical. No experimental validation is provided, which limits insight into practical performance and the real-world feasibility of the proposed methods. \n2. The efficiency claims for the exponential and regularized exponential mechanisms rely on complex sampling schemes (e.g., grid-walk) that may be impractical at scale.", "was_revised": true, "final_justification": "The complex sampling scheme is a drawback of the algorithm for practical implementation, which is not well solved or discussed in the paper. Given this, I think the paper is borderline, leaning toward acceptable.", "rebuttal": "Thank you for your thoughtful and detailed review. We respond to your comments below: \n\n>The work is entirely theoretical. No experimental validation is provided...\n\nWe do not consider the lack of experiments in our paper to be a weakness: Like many accepted NeurIPS papers, our work is about understanding the fundamental complexity of an important problem, and we hope our paper will be judged on those terms. As discussed in the Conclusion and Limitations sections, empirical investigation is an important direction for future work on DP BLO. \n\n>The efficiency claims for the exponential and regularized exponential mechanisms rely on complex sampling schemes (e.g., grid-walk) that may be impractical at scale.\n\nWe agree that our sampling algorithm may be complex to implement in large-scale practical applications, but do not consider this to be a weakness: The focus of our work is entirely theoretical–understanding the complexity bounds and developing polynomial-time algorithms that achieve these bounds. We leave it as future work to provide practical implementations of these algorithms."}, {"review_id": "DZgbnoggkx", "reviewer": "Reviewer_aTVu", "summary": "The authors study differentially private bilevel optimization with empirical loss and population loss. Their algorithm works even when the access to exact function evaluations is unavailable.\n\nFor convex outer objectives, the authors use exponential and regularized exponential mechanisms and establish upper and lower bounds on excess risk under both pure and approximate differential privacy, which is tight up to a $\\mu_g$ term. For instance, the upper bound (Theorem 3.3) corresponds to\n$$ \\mathcal{O} \\left( \\Big( L_{f,x} + \\frac{L_{f,y}\\beta_{g,xy}}{\\mu_g} + \\frac{L_{g,y}\\beta_{f,xy}}{\\mu_g}  \\Big) D_x \\frac{\\sqrt{d_x \\log(1/\\delta)}}{n \\epsilon} \\right) $$\nAnd the lower bound (Theorem 3.9) corresponds to\n$$ \\Omega \\left( \\Big( L_{f,x} D_x + L_{f,y} D_y  \\Big) D_x \\frac{d_x}{n \\epsilon} \\right) $$\n\nWhen the outer function is not convex, the authors develop algorithms that find approximate stationary points privately and show the following upper bound\n$$ \\mathcal{O} \\left( K^{1/2} \\Psi^{1/4} \\beta_{\\Psi}^{1/4} \\frac{d_x^{1/2} \\log^{1/4}(1/\\delta)}{ (n\\epsilon)^{3/4}}\\right).$$\nThis result shows that the complexity is independent of the inner problem's dimension $d_y$.", "questions": "1. **Parameter dependency**: Theorems 3.2 and 3.3 involve $\\mu_g$, while the lower bounds assume $\\mu_g \\approx L_{g,y}/D_y$. How does the lower bound extend to arbitrary values of $\\mu_g$?\n\n2. **Constraint assumptions**: Section 4 begins by assuming $\\mathcal{X}$ is unconstrained, but Theorem 4.3 reverts to $\\mathcal{X}$ being a convex subset. What is the scope of the unconstrained assumption?\n\n3. **Optimality of non-convex rates**: The non-convex analysis achieves $1/(n\\epsilon)^{3/4}$ accuracy, improving upon the standard $1/\\sqrt{n\\epsilon}$ rate in existing literature. Are there corresponding lower bounds establishing optimality for this problem class?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "The paper is well-structured with an accessible introduction that effectively contextualizes the challenges in differentially private bilevel optimization. The proposed algorithms and theoretical analysis are novel and technically sound. However, several aspects could benefit from greater clarity.\n\nThe paper would be strengthened by concrete bilevel optimization examples that illustrate why extending from convex to non-convex outer functions is practically important. Additionally, the treatment of problem parameters lacks precision—it's unclear whether constants like $\\mu_g$ are inherent to the problem instance or chosen by the practitioner. The relationship between diameter bounds $D_x, D_y$ and the unconstrained setting introduced in Section 4 also requires clarification.", "was_revised": true, "final_justification": "The authors answers clarify certain points, but not all of the problems are solved. I would keep the initial score.", "rebuttal": "Thank you for your thoughtful and detailed review. We respond to your comments below: \n\n>The paper would be strengthened by concrete bilevel optimization examples that illustrate why extending from convex to non-convex outer functions is practically important.\n\nThere are **many important nonconvex BLO problems** that arise in practice: e.g., model selection and hyperparameter tuning, and some Stackelberg game models (see lines 128-129). Additionally, if the loss function $f$ is non-convex (e.g., as in deep learning), then the corresponding BLO problem is non-convex. We will elaborate on this  in the revision. \n\n>it's unclear whether constants like $\\mu_g$ are inherent to the problem instance or chosen by the practitioner.\n\n$\\mu_g$ parameter is **inherent to the problem instance**: it describes the strong convexity of function $g$. It is not chosen by the practitioner. \n\n>How does the lower bound extend to arbitrary values of $\\mu_g$?\n\nOur lower bound construction satisfies $\\mu_g \\approx L_{g,y}/D_y$, or equivalently $D_y \\approx L_{g,y}/\\mu_g$. Thus, our lower bounds can equivalently be written in terms of $\\mu_g$ by substituting the above relation for $D_y$. Our lower bound does not apply in the parameter regime $\\mu_g \\ll L_{g,y}/D_y$. Note that providing a lower bound in this regime is an open problem even for simple single-level DP ERM, as the lower bound construction of BST14 also requires $\\mu \\approx L/D$.\n\n>Section 4 begins by assuming $\\mathcal{X}$ is unconstrained, but Theorem 4.3 reverts to $\\mathcal{X}$ being a convex subset. What is the scope of the unconstrained assumption?\n\nAll of **our results in Section 4 hold for both constrained and unconstrained settings** (see footnote 1). For Theorem 4.3, we additionally require the existence of a compact set $\\mathcal{X}$ containing a global unconstrained minimizer. We will further clarify this in the revision. \n\n>Are there corresponding [tight] lower bounds establishing optimality for this [nonconvex] problem class?\n\nThere are **no tight lower bounds for DP nonconvex optimization**, *even in the simpler single-level optimization setting*. We highlight this as an important problem for future work in the Conclusion."}, {"review_id": "yPviMOwJWX", "reviewer": "Reviewer_aszX", "summary": "This work studies differentially private (DP) bilevel optimization (BLO) in both convex and non-convex settings. When the upper-level function is convex, the authors show that the (regularized) exponential mechanism (EM) achieves optimal excess empirical and generalization risks under (approximate and) pure DP. As EM can be computationally intensive, the authors further discuss about efficient implementations that allow for approximation errors. Back to theoretical analysis, they also establish excess risk lower bounds by constructing a hard instance. These bounds improve over existing results by an additive term that captures the complexity of the lower-level optimization problem. When the upper-level function is non-convex, the authors propose a second-order algorithm to avoid dimensionality dependence on the lower-level problem. Although the algorithm is computationally inefficient, as the authors themselves acknowledge, the theoretical advancement remains remarkable. Given the significant theoretical contributions to DP-BLO, I recommend acceptance.", "questions": "1. I noticed that the authors have discussed implementation-related issues, but I am still curious how practical it is to sampling from an exponential distribution like the one in Eq.(5), given the bilevel structure. Are there any readily available numerical packages/tools for this?\n2. What is $D_y$? It first appears in line 150 without definition and is later used in many places. I assume that $D_y$ is intended to be the same as $Diam(\\mathcal{Y})$ (or its upper bound) defined in line 113? Because this value appears many times in theorems and is directly related to your contributions, I suggest the authors clearly define it before first use.\n3. (This point is more of a suggestion than a question.) You may consider moving the hard instance around line 692 constructed for proving the lower bound to some place immediate after Assumptions 2.1 & 2.2 as a motivating example to illustrate these assumptions. This may make it easier for readers to digest the inequalities in Assumptions 2.1, 2.2.\n\nminor typos: \n1. line 454: should be 'for all $\\varepsilon>0$'\n2. duplicate references [34] [35]", "limitations": "The authors have discussed the limitations of this work in Appendix D, including computational challenges and lack of numerical experiments, on which I agree. I have no further comments on limitations.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:  \n1. This work provides a relatively comprehensive discussion about DP-BLO, covering a wide range of settings, including (non-)convex objectives, pure and approximate DP, empirical and generalization risks, etc. For each setting, algorithms with near optimal performance are proposed.\n2. The authors establish improved lower bounds that capture the complexity of the lower-level problem.\n3. Computational challenges are discussed\n\nWeaknesses:\nsee Limitations section.", "was_revised": true, "final_justification": "The authors have resolved my questions. I keep my original score.\n\nHowever, after reading other reviews, I realize I might not fully understand some parts of the paper; in particular, the correlation issue mentioned by Reviewer pJMr. Therefore, I am lowering the confidence of my rating from 3 to 2.", "rebuttal": "Thank you for your thoughtful and detailed review. We respond to your comments below: \n\n>How practical it is to sampling from an exponential distribution like the one in Eq.(5), given the bilevel structure. Are there any readily available numerical packages/tools for this?\n\nWhile we show how to sample from this distribution *efficiently*, we also acknowledge that our method might not be practical. Since our work is purely theoretical, we leave practical implementation issues for future work, as discussed in Conclusion and Limitations. \n\n>What is $D_y$? It first appears in line 150 without definition and is later used in many places. I assume that  $D_y$ is intended to be the same as $Diam(\\mathcal{Y})$ (or its upper bound) defined in line 113?\n\nIndeed, $D_y = Diam(\\cal{Y})$. Thank you for catching this omission--we will add the definition to line 113.\n\n>...consider moving the hard instance around line 692 constructed for proving the lower bound to some place immediate after Assumptions 2.1 & 2.2 as a motivating example to illustrate these assumptions.\n\nGood suggestion. We will do this in the revision.\n\n>minor typos\n\nWe will fix these. Thank you again for your careful reading of our manuscript."}]

Author rebuttal:

Meta-review: This paper addresses the problem of solving bilevel optimization (BLO) under differential privacy (DP) and give theoretical upper- and lower-bounds for the problem, establishing a novel separation from single-level optimization and give improved rates in the non-convex setting. The paper also contains a new analysis of log-concave sampling under approximate evaluations.
The reviewers all see the importance of the problem and find the paper well-motivated and all reviewers were appreciative of the theoretical analysis in this work. However, there was some disagreement regarding the strength of the convexity assumption and the applicability of the sampling scheme in this paper, flagging concerns regarding implementations of the work (not the lack of empirical validation, but questions such as which parameters a practitioner ought to know in advance).
Ultimately, we acknowledge that the paper presents a solid theoretical contribution to a problem which is of great importance to the ML community. We believe the merits of studying bilevel optimization with DP rigorously outweigh the negative review and therefore recommend acceptance.
Decision: Accept (poster)