Differentially Private Bilevel Optimization

## Abstract

Abstract We present differentially private (DP) algorithms for bilevel optimization, a problem class that received significant attention lately in various machine learning applications.
These are the first DP algorithms for this task that are able to provide any desired privacy, while also avoiding Hessian computations which are prohibitive in large-scale settings.
Under the well-studied setting in which the upper-level is not necessarily convex and the lower-level problem is strongly-convex, our proposed gradient-based ( ϵ , δ ) italic-ϵ 𝛿 (\epsilon,\delta) -DP algorithm returns a point with hypergradient norm at most 𝒪 ~ ​ ( ( d up / ϵ ​ n ) 1 / 2 + ( d low / ϵ ​ n ) 1 / 3 ) ~ 𝒪 superscript subscript 𝑑 up italic-ϵ 𝑛 1 2 superscript subscript 𝑑 low italic-ϵ 𝑛 1 3 \widetilde{\mathcal{O}}\left((\sqrt{d_{\mathrm{up}}}/\epsilon n)^{1/2}+(\sqrt{d_{\mathrm{low}}}/\epsilon n)^{1/3}\right) where n 𝑛 n is the dataset size, and d up / d low subscript 𝑑 up subscript 𝑑 low d_{\mathrm{up}}/d_{\mathrm{low}} are the upper/lower level dimensions.
Our analysis covers constrained and unconstrained problems alike, accounts for mini-batch gradients, and applies to both empirical and population losses.

## 1 Introduction

Bilevel optimization
is
a fundamental framework
for
solving optimization objectives of hierarchical structure,
in which
constraints are defined themselves by an auxiliary optimization problem. Formally, it is defined as

$$ $\displaystyle\mathrm{minimize}_{\mathbf{x}\in\mathcal{X}}~{}~{}$ $\displaystyle F(\mathbf{x}):=f(\mathbf{x},\mathbf{y}^{*}(\mathbf{x}))~{}~{}~{}~{}~{}$ (BO) $\displaystyle\mathrm{subject~{}to}~{}~{}~{}$ $\displaystyle\mathbf{y}^{*}(\mathbf{x})\in\arg\min_{\mathbf{y}}g(\mathbf{x},\mathbf{y})~{},$ $$

where $F:\mathbb{R}^{d_{x}}\to\mathbb{R}$ is referred to as the hyperobjective, $f:\mathbb{R}^{d_{x}}\times\mathbb{R}^{d_{y}}\to\mathbb{R}$
as the upper-level (or outer) objective,
and $g:\mathbb{R}^{d_{x}}\times\mathbb{R}^{d_{y}}\to\mathbb{R}$ as the lower-level (or inner) objective. While bilevel optimization is well studied for over half a century (Bracken and McGill, ),
it has recently received significant attention due to its diverse applications in machine learning (ML). These include hyperparameter tuning
(Bengio, ; Maclaurin et al., ; Franceschi et al., , ; Lorraine et al., ),
meta-learning (Andrychowicz et al., ; Bertinetto et al., ; Rajeswaran et al., ; Ji et al., ),
neural architecture search (Liu et al., ),
invariant learning (Arjovsky et al., ; Jiang and Veitch, ),
and data reweighting (Grangier et al., ; Fan et al., ; Pan et al., ).
In these applications,
both the upper and lower level objectives
in ([BO](#S1.Ex1)) typically represent some loss over data,
and are given by empirical risk minimization (ERM) problems
with respect to some dataset $S=\{\xi_{1},\dots,\xi_{n}\}\in\Xi^{n}:$(^1^11It is possible for the datasets with respect to $f$ and $g$ to be distinct (e.g., validation and training data), perhaps of different sizes. We will assume without loss of generality that $S$ is the entire dataset, and thus $n$ is the total number of samples. Concretely, letting $f(\cdot;\xi_{i})=0$ or $g(\cdot;\xi_{i})=0$ for certain indices in order to exclude corresponding data points from either objective, will not affect our results.)

$$ $\displaystyle f(\mathbf{x},\mathbf{y}):=f_{S}(\mathbf{x},\mathbf{y})=\frac{1}{n}\sum_{i=1}^{n}f(\mathbf{x},\mathbf{y},\xi_{i})~{},\qquad g(\mathbf{x},\mathbf{y}):=g_{S}(\mathbf{x},\mathbf{y})=\frac{1}{n}\sum_{i=1}^{n}g(\mathbf{x},\mathbf{y},\xi_{i})~{},$ (ERM) $$

often serving as empirical proxies of the stochastic (population) objectives with respect to a distribution $\mathcal{P}$ supported on $\Xi:$

$$ $\displaystyle f(\mathbf{x},\mathbf{y}):=f_{\mathcal{P}}(\mathbf{x},\mathbf{y})=\mathbb{E}_{\xi\sim\mathcal{P}}[f(\mathbf{x},\mathbf{y};\xi)]~{},\qquad g(\mathbf{x},\mathbf{y}):=g_{\mathcal{P}}(\mathbf{x},\mathbf{y})=\mathbb{E}_{\xi\sim\mathcal{P}}[g(\mathbf{x},\mathbf{y};\xi)]~{}.$ (Pop) $$

In this work, we study bilvel optimization under
differential privacy (DP) (Dwork et al., ).
As ML models are deployed in an ever-growing number of applications, protecting the privacy of the data on which they are trained is a major concern, and DP has become the gold-standard for privacy preserving ML (Abadi et al., ).
Accordingly, DP optimization is extensively studied, with a vast literature focusing both on empirical and stochastic objectives under various assumptions (Chaudhuri et al., ; Kifer et al., ; Bassily et al., ; Wang et al., ; Bassily et al., ; Wang et al., ; Feldman et al., ; Tran and Cutkosky, ; Gopi et al., ; Arora et al., ; Carmon et al., ; Ganesh et al., ; Lowy et al., ).

Nonetheless, to the best of our knowledge, no first-order algorithm (i.e., which uses only gradient queries) that solves bilevel optimization problems under DP, is known to date. This is no coincidence: until recently, no first-order methods with finite time guarantees were known even for non-private bilevel problems.
This follows the fact (Ghadimi and Wang, , Lemma 2.1) that under mild regularity assumptions, the so-called hypergradient takes the form:

$$ $\displaystyle\nabla F(\mathbf{x})=\nabla_{x}f(\mathbf{x},\mathbf{y}^{*}(\mathbf{x}))-\nabla^{2}_{xy}g(\mathbf{x},\mathbf{y}^{*}(\mathbf{x}))[\nabla^{2}_{yy}g(\mathbf{x},\mathbf{y}^{*}(\mathbf{x}))]^{-1}\nabla_{y}f(\mathbf{x},\mathbf{y}^{*}(\mathbf{x}))~{}.$ (1) $$

Consequently, directly applying a “gradient” method to $F$
requires inverting Hessians of the lower level problem at each time step, thus limiting applicability in contemporary high-dimensional applications.
Following various approaches to tackle this challenge (see Section [1.2](#S1.SS2)), recent breakthroughs were finally able to provide fully first-order methods for bilevel optimization with non-asymptotic guarantees (Liu et al., ; Kwon et al., ; Yang et al., ; Chen et al., ).
These recent algorithmic advancements show promising empirical results in large scale applications, even up to the LLM scale of ${\sim}10^{9}$ parameters (Pan et al., ).
We therefore make use of these techniques for the sake of private optimization. As we will see, our privacy analysis requires overcoming some subtle challenges due to privacy leaking between the inner and outer problems, since $\nabla F(\mathbf{x})$ itself depends on $\mathbf{y}^{*}(\mathbf{x})$ (seen in
Eq. ([1](#S1.E1))).

The only prior method we are aware of for DP bilevel optimization was recently proposed by Chen and Wang (), which falls short in two main aspects.
First, their algorithm only provides *some* privacy guarantee which cannot be controlled by the user.
Moreover, it requires inverting local Hessians at each step, which significantly limits scalability; see Section [1.2](#S1.SS2) for further discussion.

### 1.1 Our contributions

We present DP algorithms that solve bilevel optimization problems whenever the the upper level is smooth but not necessarily convex, and the lower level problem is smooth and strongly-convex.
To the best of our knowledge, these are the first algorithms to do so using only first-order (i.e. gradient) queries of the upper- and lower-level objectives,
and that can ensure any desired privacy
$\epsilon,\delta>0$.
Our contributions can be summarized as follows:

- •
Bilevel ERM Algorithm (Theorem [3.1](#S3.Thmtheorem1)):
We present a $(\epsilon,\delta)$-DP first-order algorithm for the bilevel ERM problem ([BO](#S1.Ex1)/[ERM](#S1.Ex3)) that outputs with high probability a point with hypergradient norm bounded by
$\left\|\nabla F_{S}(\mathbf{x})\right\|=\widetilde{\mathcal{O}}\left(\left(\frac{\sqrt{d_{x}}}{\epsilon n}\right)^{1/2}+\left(\frac{\sqrt{d_{y}}}{\epsilon n}\right)^{1/3}\right)~{}.$
Our algorithm also adapts to the case where $\mathcal{X}\subsetneq\mathbb{R}^{d_{x}}$ is a non-trivial constraint set, which is common in certain applications.(^2^22For instance, in data reweighting $\mathcal{X}$ is the probability simplex; in hyperparameter tuning it is the hyperparameter space, which is typically constrained.)
In the constrained setting, we obtain the same guarantee as above
in terms of the projected hypergradient (see Section [2](#S2) for
details).
- •
Mini-batch Bilevel ERM Algorithm (Theorem [4.1](#S4.Thmtheorem1)): Aiming for a more practical algorithm, we design a variant of our previous algorithm that relies on mini-batch gradients. For the bilevel ERM problem ([BO](#S1.Ex1)/[ERM](#S1.Ex3)), given any batch sizes $b_{\mathrm{in}},b_{\mathrm{out}}\in\{1,\dots,n\}$
for sampling gradients of the inner/outer problems respectively, our algorithm ensures $(\epsilon,\delta)$-DP and outputs
with high probability a point with hypergradient norm bounded by
$\left\|\nabla F_{S}(\mathbf{x})\right\|=\widetilde{\mathcal{O}}\left(\left(\frac{\sqrt{d_{x}}}{\epsilon n}\right)^{1/2}+\left(\frac{\sqrt{d_{y}}}{\epsilon n}\right)^{1/3}+\frac{1}{b_{\mathrm{out}}}\right)~{}.$
(2)
Notably, Eq. ([2](#S1.E2))
is independent of the inner-batch size, yet depends on the outer-batch size,
which coincides
with known results for “single”-level constrained nonconvex optimization (Ghadimi et al., ) (see Remark [4.2](#S4.Thmtheorem2) for further discussion).
Our mini-batch algorithm is also applicable in the constrained setting $\mathcal{X}\subsetneq\mathbb{R}^{d_{x}}$ with the same guarantee in terms of projected hypergradient.
- •
Population loss guarantees (Theorem [5.1](#S5.Thmtheorem1)):
We further provide guarantees for stochastic objectives. In particular, we show that for the population bilevel problem ([BO](#S1.Ex1)/[Pop](#S1.Ex4)), our $(\epsilon,\delta)$-DP algorithm outputs with high probability a point with hypergradient norm bounded by
$\left\|\nabla F_{\mathcal{P}}(\mathbf{x})\right\|=\widetilde{\mathcal{O}}\left(\left(\frac{\sqrt{d_{x}}}{\epsilon n}\right)^{1/2}+\left(\frac{d_{x}}{n}\right)^{1/2}+\left(\frac{\sqrt{d_{y}}}{\epsilon n}\right)^{1/3}\right)~{},$
with an additional additive $1/b_{\mathrm{out}}$ factor in the mini-batch setting.

### 1.2 Related work

Bilevel optimization was introduced by Bracken and McGill (),
and grew into a vast body of work, with classical results focusing on asymptotic guarantees for specific problem structures
(Anandalingam and White, ; Ishizuka and Aiyoshi, ; White and Anandalingam, ; Vicente et al., ; Zhu, ; Ye and Zhu, ). There exist multiple surveys and books covering various approaches for these problems
(Vicente and Calamai, ; Dempe, ; Colson et al., ; Bard, ; Sinha et al., ).

Ghadimi and Wang ()
observed Eq. ([1](#S1.E1)) under strong-convexity of the inner problem
using the implicit function theorem, asserting that
the hypergradient can be computed via inverse Hessians,
which requires solving a linear system at each point.
Many follow up works built upon this second-order approach with additional techniques such as variance reduction, momentum, Hessian sketches, projection-free updates,
or incorporating external constraints (Amini and Yousefian, ; Yang et al., ; Khanduri et al., ; Guo et al., ; Ji et al., ; Chen et al., ; Akhtar et al., ; Chen et al., ; Tsaknakis et al., ; Hong et al., ; Jiang et al., ; Abolfazli et al., ; Merchav and Sabach, ; Xu and Zhu, ; Cao et al., ; Dagréou et al., ).

Only recently, the groundbreaking result of Liu et al. () proved finite-time convergence guarantees for a fully first-order method which is based on a penalty approach. This result was soon extended to stochastic objectives (Kwon et al., ),
with the convergence rate later improved by (Yang et al., ; Chen et al., ),
and also extended to constrained bilevel problems (Yao et al., ; Kornowski et al., ).
The first-order penalty paradigm also shows promise for some bilevel problems in which the inner problem is not strongly-convex (Shen and Chen, ; Kwon et al., ; Lu and Mei, ), which is generally a highly challenging setting (Chen et al., ; Bolte et al., ).
Moreover, Pan et al. () provided an efficient implementation of this paradigm, showing its effectiveness for large scale applications.

As to DP optimization, there is an extensive literature on optimization problems, both for ERM and for stochastic losses,
which are either convex (Chaudhuri et al., ; Kifer et al., ; Bassily et al., ; Wang et al., ; Bassily et al., ; Feldman et al., ; Gopi et al., ; Carmon et al., )
or smooth and nonconvex (Wang et al., ; Tran and Cutkosky, ; Arora et al., ; Ganesh et al., ; Lowy et al., ).

To the best of our knowledge, the only existing result for DP bilevel optimization is the very recent result of Chen and Wang (), which differs than ours in several aspect. Their proposed algorithm is second-order, requiring
evaluating Hessians, and solving linear systems at each time step, which we avoid altogether.
Moreover, Chen and Wang () study the *local* DP model (Kasiviswanathan et al., ), in which each user (i.e. $\xi_{i}$) does not reveal its individual information.
Due to this more challenging setting, they can only derive guarantees for *some finite* privacy budget $\epsilon<\infty$, even as the dataset size grows. We study the common central DP model, in which a trusted curator acts on the collected data and releases a private solution, and thus are able to provide any desired privacy and accuracy guarantees with sufficiently many samples.
Our work is the first to study bilevel optimization in this common DP setting.
We also note that Fioretto et al. () studied
the related problem of DP in Stackelberg games, which are certain bilevel programs which arise in game theory, aiming at designing coordination mechanisms that maintain the individual agents’ privacy.

## 2 Preliminaries

##### Notation and terminology.

We let bold-face letters (e.g. $\mathbf{x}$) denote vectors, and denote by $\mathbf{0}$ the zero vector (whenever the dimension is clear from context) and by $I_{d}\in\mathbb{R}^{d\times d}$ the identity matrix.
$[n]:=\{1,2,\dots,n\}$,
$\left\langle\,\cdot\,,\,\cdot\,\right\rangle$ denotes the standard Euclidean dot product, and $\left\|\,\cdot\,\right\|$ denotes either its induced norm for vectors or operator norm for matrices, and $\left\|f\right\|_{\infty}=\sup_{\mathbf{x}\in\mathcal{X}}|f(\mathbf{x})|$ denotes the sup-norm.
We denote by $\mathrm{Proj}_{\mathbb{B}(\mathbf{z},R)}$ the projection onto the closed ball around $\mathbf{z}$ of radius $R$.
$\mathcal{N}(\bm{\mu},\Sigma)$ denotes a normal (i.e., Gaussian) random variable with mean $\bm{\mu}$ and covariance $\Sigma$.
We use standard big-O notation, with $\mathcal{O}(\cdot)$ hiding absolute constants (independent of problem parameters), $\widetilde{\mathcal{O}}(\cdot)$ also hiding poly-logarithmic terms. We denote $f\lesssim g$ if $f=\mathcal{O}(g)$, and $f\asymp g$ if $f\lesssim g$ and $g\lesssim f$.
A function $f:\mathcal{X}\subseteq\mathbb{R}^{d_{1}}\to\mathbb{R}^{d_{2}}$ is $L_{0}$-Lipschitz if for all $\mathbf{x},\mathbf{y}\in\mathcal{X}:\left\|f(\mathbf{x})-f(\mathbf{y})\right\|\leq L_{0}\left\|\mathbf{x}-\mathbf{y}\right\|$; $L_{1}$-smooth if $\nabla f$ exists and is $L_{1}$-Lipschitz; and $L_{2}$ Hessian-smooth if $\nabla^{2}f$ exists and is $L_{2}$-Lipschitz (with respect to the operator norm).
A twice-differentiable function $f$ is $\mu$-strongly-convex if $\nabla^{2}f\succeq\mu I$,
denoting by “$\succeq$”
the standard PSD (“Loewner”) order on matrices.

##### Differential privacy.

Two datasets $S,S^{\prime}\in\Xi^{n}$ are said to be neighboring, denoted by $S\sim S^{\prime}$, if they differ by only one data point. A randomized algorithm $\mathcal{A}:\Xi^{n}\to\mathcal{R}$ is called $(\epsilon,\delta)$ differentially private (or $(\epsilon,\delta)$-DP) for $\epsilon,\delta>0$ if for any two neighboring datasets $S\sim S^{\prime}$ and measurable $E\subseteq\mathcal{R}$ in the algorithm’s range, it holds that $\Pr[\mathcal{A}(S)\in E]\leq e^{\epsilon}\Pr[\mathcal{A}(S^{\prime})\in E]+\delta$ (Dwork et al., ).
The basic composition property of DP states that the (possibly adaptive) composition of $(\epsilon_{0},\delta_{0})$-DP- and $(\epsilon_{1},\delta_{1})$-DP mechanisms, is $(\epsilon_{0}+\epsilon_{1},\delta_{0}+\delta_{1})$-DP.
We next recall some well known DP basics: advanced composition, the Gaussian mechanism, and privacy amplification by subsampling.

###### Lemma 2.1 (Advanced composition, Dwork et al., 2010 ) .

For $\epsilon_{0}<1$, a $T$-fold (possibly adaptive) composition of $(\epsilon_{0},\delta_{0})$-DP mechanisms is $(\epsilon,\delta)$-DP for $\epsilon=\sqrt{2T\log(1/\delta_{0})}\epsilon_{0}+2T\epsilon_{0}^{2},~{}\delta=(T+1)\delta_{0}$.

###### Lemma 2.2 (Gaussian mechanism) .

Given a function $h:\Xi^{b}\to\mathbb{R}^{d}$, the Gaussian mechanism $\mathcal{M}(h):\Xi^{b}\to\mathbb{R}^{d}$ defined as $\mathcal{M}(h)(S):=h(S)+\mathcal{N}(\mathbf{0},\sigma^{2}I_{d})$ is $(\epsilon,\delta)$-DP for $\epsilon,\delta\in(0,1)$,
as long as $\sigma^{2}\geq\frac{2\log(5/4\delta)(\mathcal{S}_{h})^{2}}{\epsilon^{2}}$, where $\mathcal{S}_{h}:=\sup_{S\sim S^{\prime}}\left\|h(S)-h(S^{\prime})\right\|$ is the $L_{2}$-sensitivity of $h$.

###### Lemma 2.3 (Privacy amplification, Balle et al., 2018 ) .

Suppose $\mathcal{M}:\Xi^{b}\to\mathcal{R}$ is $(\epsilon_{0},\delta_{0})$-DP. Then given $n\geq b$, the mechanism $\mathcal{M}^{\prime}:\Xi^{n}\to\mathcal{R},~{}\mathcal{M}^{\prime}(S):=\mathcal{M}(B)$ where $B\sim\mathrm{Unif}(\Xi)^{b}$, is $(\epsilon,\delta)$-DP for
$\epsilon=\log(1+(1-(1-1/n)^{b})(e^{\epsilon_{0}}-1)),~{}\delta=\delta_{0}$.

We remark that advanced composition will be used when
$\epsilon_{0}\lesssim\sqrt{\log(1/\delta_{0})/T}$, thus the accumulated privacy scales as $\epsilon\asymp\sqrt{T}\epsilon_{0}$.
Similarly, privacy amplification will be used when
$\epsilon_{0}\leq 1$, under which the privacy after subsampling scales as $\epsilon\asymp\frac{b\epsilon_{0}}{n}$ (since $e^{\epsilon_{0}}-1\asymp\epsilon_{0},~{}(1-1/n)^{b}\asymp\frac{b}{n}$ and $\log(1+\frac{b}{n}\epsilon_{0})\asymp\frac{b}{n}\epsilon_{0}$).

###### Lemma 2.1 (Advanced composition, Dwork et al., 2010 ) .

###### Lemma 2.2 (Gaussian mechanism) .

###### Lemma 2.3 (Privacy amplification, Balle et al., 2018 ) .

##### Gradient mapping.

Given a point $\mathbf{x}\in\mathbb{R}^{d}$, and some $\mathbf{v}\in\mathbb{R}^{d},~{}\eta>0$, we denote

$$ $\mathcal{G}_{\mathbf{v},\eta}(\mathbf{x}):=\frac{1}{\eta}\left(\mathbf{x}-\mathcal{P}_{\mathbf{v},\eta}(\mathbf{x})\right)~{},~{}~{}~{}~{}~{}\mathcal{P}_{\mathbf{v},\eta}(\mathbf{x}):=\arg\min_{\mathbf{u}\in\mathcal{X}}\left[\left\langle\mathbf{v},\mathbf{u}\right\rangle+\frac{1}{2\eta}\left\|\mathbf{u}-\mathbf{x}\right\|^{2}\right]~{}.$ $$

In particular, given an $L$-smooth function $F:\mathbb{R}^{d}\to\mathbb{R}$ and $\eta\leq\frac{1}{2L}$, we denote the projected gradient (also known as reduced gradient)
and the gradient (or prox) mapping, respectively, as

$$ $\mathcal{G}_{F,\eta}(\mathbf{x}):=\frac{1}{\eta}\left(\mathbf{x}-\mathcal{P}_{\nabla F,\eta}(\mathbf{x})\right)~{},~{}~{}~{}~{}~{}\mathcal{P}_{\nabla F,\eta}(\mathbf{x}):=\arg\min_{\mathbf{u}\in\mathcal{X}}\left[\left\langle\nabla F(\mathbf{x}),\mathbf{u}\right\rangle+\frac{1}{2\eta}\left\|\mathbf{u}-\mathbf{x}\right\|^{2}\right]~{}.$ $$

The projected gradient $\mathcal{G}_{F,\eta}(\mathbf{x})$
generalizes the gradient
to the possibly constrained setting:
for points $\mathbf{x}\in\mathcal{X}$ sufficiently far from the boundary of $\mathcal{X},~{}\mathcal{G}_{F,\eta}(\mathbf{x})=\nabla F(\mathbf{x})$, namely it simply reduces to the gradient. See the textbooks (Nesterov, ; Lan, ) for additional details.
We will recall a useful fact, which asserts that the mapping $\mathcal{G}_{\mathbf{v},\eta}(\mathbf{x})$ is non-expansive with respect to $\mathbf{v}:$

###### Lemma 2.4 .

For any $\mathbf{x},\mathbf{v},\mathbf{w}\in\mathbb{R}^{d},~{}\eta>0:~{}\left\|\mathcal{G}_{\mathbf{v},\eta}(\mathbf{x})-\mathcal{G}_{\mathbf{w},\eta}(\mathbf{x})\right\|\leq\left\|\mathbf{v}-\mathbf{u}\right\|$.

Lemma [2.4](#S2.Thmtheorem4) is important in our analysis, since as we will argue later (in Section [3.1](#S3.SS1)), gradient estimates must be *inexact* in the bilevel setting
to satisfy privacy, and Lemma [2.4](#S2.Thmtheorem4) will allows us to control the error due to this inexactness.
Although this result is known (cf. Ghadimi et al. ), we reprove it in Appendix [B](#A2) for completeness.

###### Lemma 2.4 .

### 2.1 Setting

We impose the following assumptions, all of which are standard in the bilevel optimization literature.

###### Assumption 2.5 .

For ([BO](#S1.Ex1)) with either ([ERM](#S1.Ex3)) or ([Pop](#S1.Ex4)),
we assume the following hold:

- i.
$\mathcal{X}\subseteq\mathbb{R}^{d_{x}}$ is a closed convex set.
- ii.
$F(\mathbf{x}_{0})-\inf_{\mathbf{x}\in\mathcal{X}}F(\mathbf{x})\leq\Delta_{F}$ for some initial point $\mathbf{x}_{0}\in\mathcal{X}$.
- iii.
$f$ is twice differentiable, and $L_{1}^{f}$-smooth.
- iv.
For all $\xi\in\Xi:~{}f(\cdot,\cdot\,;\xi)$ is $L_{0}^{f}$-Lipschitz (hence, so is $f$).
- v.
$g$ is $L_{2}^{g}$-Hessian-smooth, and for all $\mathbf{x}\in\mathcal{X}:~{}g(\mathbf{x},\cdot)$ is $\mu_{g}$-strongly-convex.
- vi.
For all $\xi\in\Xi:~{}g(\cdot,\cdot\,;\xi)$ is $L_{1}^{g}$-smooth (hence, so is $g$).

As mentioned, these assumptions are standard in the study of bilevel optimization problems and are shared by nearly all of the previous works we discussed. In particular, the strong convexity of $g(\mathbf{x},\cdot)$ ensures that $\mathbf{y}^{*}(\mathbf{x})$ is uniquely defined, which is generally required in establishing the regularity of the hyporobjective. Indeed, it is known that dropping this assumption, can, in general, lead to pathological behaviors not amenable for algorithmic guarantees
(cf. Chen et al. ; Bolte et al. and discussions therein).
For the purpose of differential privacy though, the strong convexity of $g(\mathbf{x},\cdot)$ raises a subtle issue. As the standard assumption in the DP optimization literature is that the component functions are Lipschitz, which allows privatization of gradients using sensitivity arguments, strongly-convex objectives cannot be Lipschitz over the entire Euclidean space.(^3^33If $g(\mathbf{x},\cdot\,;\xi)$ were Lipschitz over $\mathbb{R}^{d_{y}}$ for all $\xi\in\Xi$, then so would $g(\mathbf{x},\cdot)$, contradicting strong convexity.) Therefore, strongly-convex objectives are regularly analyzed in the DP setting under the additional assumption that the domain of interest is bounded. For bilevel problems, the domain of interest for $\mathbf{y}$ is the lower level solution set, thus we impose the following assumption.

###### Assumption 2.6 .

There exists a compact set $\mathcal{Y}\subset\mathbb{R}^{d_{y}}$ with $\{\mathbf{y}^{*}(\mathbf{x}):\mathbf{x}\in\mathcal{X}\}\subseteq\mathcal{Y}$, such that for all $\mathbf{x}\in\mathcal{X},\,\xi\in\Xi:~{}g(\mathbf{x},\cdot\,;\xi)$ is $L_{0}^{g}$-Lipschitz over $\mathcal{Y}$.

###### Remark 2.7 .

Note that $\mathrm{diam}(\mathcal{Y})\leq{2L_{0}^{g}}/{\mu_{g}}$. Indeed, fixing some $\mathbf{x}\in\mathcal{X}$,
since $g(\mathbf{x},\cdot\,;\xi)$ is $L_{0}^{g}$-Lipschitz over $\mathcal{Y}$ for all $\xi\in\Xi$, then so is $g(\mathbf{x},\cdot)$. Moreover, by $\mu_{g}$-strong-convexity, we get that for all $\mathbf{y}\in\mathcal{Y}:~{}\mu_{g}\left\|\mathbf{y}-\mathbf{y}^{*}(\mathbf{x})\right\|\leq\left\|\nabla_{y}g(\mathbf{x},\mathbf{y})\right\|\leq L_{0}^{g}$. Hence $\mathcal{Y}\subseteq\mathbb{B}(\mathbf{y}^{*}(\mathbf{x}),{L_{0}^{g}}/{\mu_{g}})$, which is of diameter ${2L_{0}^{g}}/{\mu_{g}}$.

Following Assumptions [2.5](#S2.Thmtheorem5) and [2.6](#S2.Thmtheorem6), we denote $\ell:=\max\{L_{0}^{f},L_{1}^{f},L_{0}^{g},L_{1}^{g},L_{2}^{g}\},~{}\kappa:=\ell/\mu_{g}$.

###### Assumption 2.5 .

###### Assumption 2.6 .

###### Remark 2.7 .

## 3 Algorithm for bilevel ERM

Figure: Algorithm 1 DP Bilevel

Figure: Algorithm 2 DP-Loc-GD

In this section, we consider the ERM bilevel problem, namely ([BO](#S1.Ex1)) with ([ERM](#S1.Ex3)), for which we denote the hyperobjective by $F_{S}$.
Our algorithm is presented in Algorithm [1](#alg1). We prove the following result:

###### Theorem 3.1 .

Assume [2.5](#S2.Thmtheorem5) and [2.6](#S2.Thmtheorem6) hold, and that
$\alpha\leq\ell\kappa^{3}\min\{\frac{1}{2\kappa},\frac{L_{0}^{g}}{L_{0}^{f}},\frac{L_{1}^{g}}{L_{1}^{f}},\frac{\Delta_{F}}{\ell\kappa}\}$.
Then there is an assignment of parameters
$\lambda\asymp\ell\kappa^{3}\alpha^{-1},~{}\sigma^{2}\asymp\ell^{2}\kappa^{2}T\log(T/\delta)\epsilon^{-2}n^{-2},~{}\eta\asymp\ell^{-1}\kappa^{-3},~{}T\asymp\Delta_{F}\ell\kappa^{3}\alpha^{-2}$,
such that running Algorithm [1](#alg1) satisfies $(\epsilon,\delta)$-DP,
and returns $\mathbf{x}_{\mathrm{out}}$ such that with probability at least $1-\gamma:$

$$ $\left\|\mathcal{G}_{F_{S},\eta}(\mathbf{x}_{\mathrm{out}})\right\|\leq\alpha=\widetilde{\mathcal{O}}\left(K_{1}\left(\frac{\sqrt{d_{x}}}{\epsilon n}\right)^{1/2}+K_{2}\left(\frac{\sqrt{d_{y}}}{\epsilon n}\right)^{1/3}\right)~{},$ $$

where $K_{1}=\mathcal{O}(\Delta_{F}^{1/4}\ell^{3/4}\kappa^{5/4}),~{}K_{2}=\mathcal{O}(\Delta_{F}^{1/6}\ell^{1/2}\kappa^{11/6})$.

###### Remark 3.2 .

Recall that when $\mathcal{X}=\mathbb{R}^{d_{x}}$, then $\mathcal{G}_{F_{S},\eta}(\mathbf{x}_{\mathrm{out}})=\nabla F_{S}(\mathbf{x}_{\mathrm{out}})$.

###### Theorem 3.1 .

###### Remark 3.2 .

### 3.1 Analysis overview

In this section, we will go over the main ideas that appear in the proof of Theorem [3.1](#S3.Thmtheorem1), all which are provided in full detail in Section [6](#S6). We start by introducing some useful notation:
Given $\lambda>0$, we denote the penalty function

$$ $\mathcal{L}_{\lambda}(\mathbf{x},\mathbf{y}):=f(\mathbf{x},\mathbf{y})+\lambda\left[g(\mathbf{x},\mathbf{y})-g(\mathbf{x},\mathbf{y}^{*}(\mathbf{x}))\right]~{},$ $$

and further denote

$$ $\mathcal{L}^{*}_{\lambda}(\mathbf{x}):=\mathcal{L}_{\lambda}(\mathbf{x},\mathbf{y}^{\lambda}(\mathbf{x}))~{},~{}~{}~{}~{}\mathbf{y}^{\lambda}(\mathbf{x}):=\arg\min_{\mathbf{y}}\mathcal{L}_{\lambda}(\mathbf{x},\mathbf{y})~{}.$ $$

The starting point of our analysis is the following result, underlying the previously discussed recent advancements in (non-private) first-order bilevel optimization:

###### Lemma 3.3 ( Kwon et al. 2023 , 2024 ; Chen et al. 2024 ) .

For
$\lambda\geq 2L_{1}^{f}/\mu_{g}$,
the following hold:

- a.
$\left\|\mathcal{L}^{*}_{\lambda}-F\right\|_{\infty}=\mathcal{O}(\ell\kappa/\lambda)$.
- b.
$\left\|\nabla\mathcal{L}^{*}_{\lambda}-\nabla F\right\|_{\infty}=\mathcal{O}(\ell\kappa^{3}/\lambda)$.
- c.
$\mathcal{L}_{\lambda}^{*}$ is $\mathcal{O}(\ell\kappa^{3})$-smooth
(independently of $\lambda$).

In other words, the lemma shows that
for sufficiently large penalty $\lambda$,
$\mathcal{L}_{\lambda}^{*}$ is a smooth approximation of the hyperobjective $F$, and that it suffices to minimize the gradient norm of $\mathcal{L}_{\lambda}^{*}$ in order to get a hypergradient guarantee in terms of $\nabla F$. Moreover, note that $\nabla\mathcal{L}_{\lambda}^{*}$ can be computed entirely in a first-order fashion, since by construction $\mathcal{L}_{\lambda}^{*}(\mathbf{x})=\arg\min_{\mathbf{y}}\mathcal{L}_{\lambda}(\mathbf{x},\mathbf{y})$, and therefore it holds that

$$ $\displaystyle\nabla\mathcal{L}_{\lambda}^{*}(\mathbf{x})$ $\displaystyle=\nabla_{x}\mathcal{L}^{*}_{\lambda}(\mathbf{x},\mathbf{y}^{\lambda}(\mathbf{x}))+\nabla_{x}\mathbf{y}^{\lambda}(\mathbf{x})^{\top}\underset{=\mathbf{0}}{\underbrace{\nabla_{y}\mathcal{L}_{\lambda}(\mathbf{x},\mathbf{y}^{\lambda}(\mathbf{x}))}}$ $\displaystyle=\nabla_{x}f(\mathbf{x},\mathbf{y}^{\lambda}(\mathbf{x}))+\lambda\left(\nabla_{x}g(\mathbf{x},\mathbf{y}^{\lambda}(\mathbf{x}))-\nabla_{x}g(\mathbf{x},\mathbf{y}^{*}(\mathbf{x}))\right)~{}.$ (3) $$

This observation raises a subtle privacy issue: Since $\mathbf{y}^{*}(\mathbf{x}),\mathbf{y}^{\lambda}(\mathbf{x})$ are required in order to compute the gradient $\nabla\mathcal{L}_{\lambda}^{*}(\mathbf{x})$, and are defined as the minimizers of $g(\mathbf{x},\cdot),\mathcal{L}_{\lambda}(\mathbf{x},\cdot)$ which are data-dependent, we cannot simply compute them up to arbitraily small accuracy
under the DP constraint.
In other words, even deciding *where* to invoke the gradient oracles, can already
leak user information, hence
breaking privacy
before the gradients are even computed.
We therefore must resort to approximating them using an auxiliary private method, for which we use DP-Loc(alized)-GD (Algorithm [2](#alg2)).(^4^44 We can replace the inner solver by any DP method that guarantees with high probability the optimal rate for strongly-convex objectives, as we further discuss in Appendix [A](#A1).)
We then crucially rely on the fact that $g(\mathbf{x},\cdot)$ $\mathcal{L}_{\lambda}(\mathbf{x},\cdot)$ are both strongly-convex, which implies that optimizing them produces ${\widetilde{\mathbf{y}}}_{t},\widetilde{\mathbf{y}}^{\lambda}_{t}$ such that the *distances* to the minimizers, namely $\left\|{\widetilde{\mathbf{y}}}_{t}-\mathbf{y}^{*}(\mathbf{x}_{t})\right\|,\left\|\widetilde{\mathbf{y}}^{\lambda}_{t}-\mathbf{y}^{\lambda}(\mathbf{x}_{t})\right\|$, are small.
The distance bound is key, as Eq. ([3](#S3.E3)) allows using the smoothness of $f,g$ to
translate the distance bounds into
an inexact (i.e. biased) gradient oracle for $\nabla\mathcal{L}_{\lambda}^{*}(\mathbf{x}_{t})$,
computed at the private points ${\widetilde{\mathbf{y}}}_{t},\widetilde{\mathbf{y}}^{\lambda}_{t}$. Using this analysis we obtain the following guarantee:

###### Lemma 3.4 .

If $\lambda\geq\max\{\frac{2L_{1}^{g}}{\mu_{g}},\frac{L_{0}^{f}}{L_{0}^{g}},\frac{L^{f}_{1}}{L^{g}_{1}}\}$, then there is $\beta=\widetilde{\mathcal{O}}\left(\frac{\lambda\ell\kappa\sqrt{d_{y}T}}{\epsilon n}\right)$ such that with probability at least $1-\gamma$, for all $t\in\{0,\dots,T-1\}:$

$$ $\left\|\nabla\mathcal{L}^{*}_{\lambda}(\mathbf{x}_{t})-\left[\nabla_{x}f(\mathbf{x}_{t},\widetilde{\mathbf{y}}^{\lambda}_{t})+\lambda\left(\nabla_{x}g(\mathbf{x}_{t},\widetilde{\mathbf{y}}^{\lambda}_{t})-\nabla_{x}g(\mathbf{x}_{t},\widetilde{\mathbf{y}}_{t})\right)\right]\right\|\leq\beta~{}.$ $$

Having constructed an inexact gradient oracle, we can privatize its response using the standard Gaussian mechanism.
Recalling that the noise variance required to ensure privacy is tied to the component Lipschitz constants,
we note that $\mathcal{L}_{\lambda}^{*}(\mathbf{x})$ decomposes as the finite-sum $\mathcal{L}_{\lambda}^{*}(\mathbf{x})=\frac{1}{n}\sum_{i=1}^{n}\mathcal{L}^{*}_{\lambda,i}(\mathbf{x})$, where

$$ $\mathcal{L}^{*}_{\lambda,i}(\mathbf{x}):=f(\mathbf{x},\mathbf{y}^{\lambda}(\mathbf{x});\xi_{i})+\lambda\left[g(\mathbf{x},\mathbf{y}^{\lambda}(\mathbf{x});\xi_{i})-g(\mathbf{x},\mathbf{y}^{*}(\mathbf{x});\xi_{i})\right]~{}.$ $$

At first glance, a naive application of the chain rule and the triangle inequality would bound the Lipschitz constant of $\mathcal{L}_{\lambda,i}^{*}$ by approximately $\mathrm{Lip}(\mathbf{y}^{*})(L_{0}^{f}+\lambda L_{0}^{g})\lesssim\lambda\mathrm{Lip}(\mathbf{y}^{*})L_{0}^{g}$, where $\mathrm{Lip}(\mathbf{y}^{*})$ is the Lipschitz constant of $\mathbf{y}^{*}(\mathbf{x}):\mathbb{R}^{d_{x}}\to\mathbb{R}^{d_{y}}$. Unfortunately, this bound grows with the penalty parameter $\lambda$, which will eventually be set large, and in particular, will grow with the dataset size $n$. We therefore derive the following lemma, showing that applying a more nuanced analysis allows obtaining a significantly tighter Lipschitz bound, independent of $\lambda:$

###### Lemma 3.5 .

$\mathcal{L}^{*}_{\lambda,i}$ is
$\mathcal{O}(\ell\kappa)$-Lipschitz.

Finally, having constructed a private inexact stochastic oracle response for the smooth approximation $\mathcal{L}^{*}_{\lambda}$, we analyze an outer loop (Line 5 of Algorithm [1](#alg1)), showing that is provably robust to inexact and noisy gradients.
We then employ a stopping criteria which makes use of the already-privatized iterates, thus avoiding the need of additional noise in choosing the smallest gradient.
In particular, we show that the corresponding process gets to a point with small (projected-)gradient norm, as stated below:

###### Proposition 3.6 .

Suppose $h:\mathbb{R}^{d}\to\mathbb{R}$ is $L$-smooth, that $\|\widetilde{\nabla}h(\cdot)-\nabla h(\cdot)\|\leq\beta$, and consider the following update rule with $\eta=\frac{1}{2L}:$

$$ $\mathbf{x}_{t+1}=\arg\min_{\mathbf{u}\in\mathcal{X}}\left\{\left\langle\widetilde{\nabla}h(\mathbf{x}_{t})+\nu_{t},\mathbf{u}\right\rangle+\frac{1}{2\eta}\left\|\mathbf{x}_{t}-\mathbf{u}\right\|^{2}\right\}~{},~{}~{}~{}\nu_{t}\sim\mathcal{N}(0,\sigma^{2}I)~{},$ $$

with the output rule $\mathbf{x}_{\mathrm{out}}:=\mathbf{x}_{t_{\mathrm{out}}},~{}t_{\mathrm{out}}:={\arg\min}_{t\in\{0,\dots,T-1\}}\left\|\mathbf{x}_{t+1}-\mathbf{x}_{t}\right\|$.
If $\alpha>0$ is such that
$\alpha\geq C\max\{\beta,\sigma\sqrt{d\log(T/\gamma)}\}$ for a sufficiently large absolute constant $C>0$, then with probability at least $1-\gamma:~{}\left\|\mathcal{G}_{h,\eta}(\mathbf{x}_{\mathrm{out}})\right\|\leq\alpha$
for $T=\mathcal{O}\left(\frac{L(h(\mathbf{x}_{0})-\inf h)}{\alpha^{2}}\right)$.

Overall, applying Proposition [3.6](#S3.Thmtheorem6) to $h=\mathcal{L}_{\lambda}^{*}$, we see that the (projected-)gradient norm can be as small as $\max\{\beta,\sigma\sqrt{d_{x}}\}$, up to logarithmic terms. Accounting for the smallest possible
inexactness $\beta$ and noise addition $\sigma$ that ensure
the the inner and outer loops, respectively, are both sufficiently private, we conclude the proof of
Theorem [3.1](#S3.Thmtheorem1);
the full details appear in Section [6](#S6).

###### Lemma 3.3 ( Kwon et al. 2023 , 2024 ; Chen et al. 2024 ) .

###### Lemma 3.4 .

###### Lemma 3.5 .

###### Proposition 3.6 .

## 4 Mini-batch algorithm for bilevel ERM

Figure: Algorithm 3 Mini-batch DP Bilevel

Figure: Algorithm 4 DP-Loc-SGD

In this section, we consider once again the ERM bilevel problem, ([BO](#S1.Ex1)) with ([ERM](#S1.Ex3)),
and provide Algorithm [3](#alg3),
which is a mini-batch variant of the ERM algorithm discussed in the previous section.
Given a mini-batch $B\subseteq S=\{\xi_{1},\dots,\xi_{n}\}$ and a function $h:\mathbb{R}^{d}\times\Xi\to\mathbb{R}$, we let
$\nabla h(\mathbf{z};B)=\frac{1}{|B|}\sum_{\xi_{i}\in B}\nabla h(\mathbf{z};\xi_{i})$ denote the mini-batch gradient.
We prove the following result:

###### Theorem 4.1 .

Assume [2.5](#S2.Thmtheorem5) and [2.6](#S2.Thmtheorem6) hold, and that $\alpha\leq\ell\kappa^{3}\min\{\frac{1}{2\kappa},\frac{L_{0}^{g}}{L_{0}^{f}},\frac{L_{1}^{g}}{L_{1}^{f}},\frac{\Delta_{F}}{\ell\kappa}\}$.
Then running Algorithm [3](#alg3) with assigned parameters as in Theorem [3.1](#S3.Thmtheorem1)
and any batch sizes $b_{\mathrm{in}},b_{\mathrm{out}}\in[n]$,
satisfies $(\epsilon,\delta)$-DP
and returns $\mathbf{x}_{\mathrm{out}}$ such that with probability at least $1-\gamma:$

$$ $\left\|\mathcal{G}_{F_{S},\eta}(\mathbf{x}_{\mathrm{out}})\right\|\leq\alpha=\widetilde{\mathcal{O}}\left(K_{1}\left(\frac{\sqrt{d_{x}}}{\epsilon n}\right)^{1/2}+K_{2}\left(\frac{\sqrt{d_{y}}}{\epsilon n}\right)^{1/3}+K_{3}\cdot\frac{1}{b_{\mathrm{out}}}\right)~{},$ $$

where
$K_{1}=\mathcal{O}(\Delta_{F}^{1/4}\ell^{3/4}\kappa^{5/4}),~{}K_{2}=\mathcal{O}(\Delta_{F}^{1/6}\ell^{1/2}\kappa^{11/6}),~{}K_{3}=\mathcal{O}(\ell\kappa)$.

###### Remark 4.2 (Outer batch size dependence) .

Algorithm [3](#alg3) ensures privacy for any batch sizes, yet notably, the guaranteed gradient norm bound does not go to zero (as $n\to\infty$) for constant outer-batch size.
The same phenomenon also holds for for “single”-level constrained nonconvex optimization, as noted by Ghadimi et al. () (specifically, see Corollary 4 and related discussion).
Accordingly, the inner-batch size
$b_{\mathrm{in}}$ can be set whatsoever,
while
setting $b_{\mathrm{out}}=\mathcal{O}(\max\{(\epsilon n/\sqrt{d_{x}})^{1/2},(\epsilon n/\sqrt{d_{y}})^{1/3}\})\ll n$ recovers the full-batch rate. More generally, from a worst-case perspective, one should set
$b_{\mathrm{out}}=\omega_{n}(1)$ to grow with the sample (resulting in $\lim_{n\to\infty}\|\mathcal{G}(\mathbf{x}_{\mathrm{out}})\|=0$).
It is interesting to note that the additional $1/b_{\mathrm{out}}$ term shows up in the analysis only as an upper bound on the sub-Gaussian norm of the mini-batch gradient estimator.
Thus, in applications for which some (possibly constant) batch size results in reasonably accurate gradients, the result above should hold with the outer mini-batch gradient’s standard deviation replacing $1/b_{\mathrm{out}}$, which is to be expected anyhow for high probability guarantees.

The difference between Algorithm [3](#alg3) and Algorithm [1](#alg1),
is that both the inner and outer loops sample mini-batch gradients.
The inner loop guarantee is the same regardless of the inner-batch size $b_{\mathrm{in}}$, since for strongly-convex objectives it is possible to prove the same
convergence rate
guarantee for DP optimization in any case (as further discussed in Appendix [A](#A1)).
As to the outer loop (Line 5),
we apply standard concentration bounds to argue about the quality of the gradient estimates — hence the additive $1/b_{\mathrm{out}}$ factor —
and rely on our analysis of the outer loop
with inexact gradients (which are now even less exact due to sampling stochasticity).
We remark that compared to the classic analysis of Ghadimi et al. () for constrained nonconvex optimization, we derive high probability bounds without requiring several re-runs of the algorithm.
We further remark that we analyze mini-batch sampling with replacement for simplicity, though the same guarantees (up to constants) can be derived for sampling at each time step without replacement, at the cost of a more involved analysis.

###### Theorem 4.1 .

###### Remark 4.2 (Outer batch size dependence) .

## 5 Generalizing from ERM to population loss

In this section, we move to consider stochastic (population) objectives, the problem ([BO](#S1.Ex1)) with ([Pop](#S1.Ex4)).
We denote the population hyperobjective by $F_{\mathcal{P}}$, and as before $F_{S}$ denotes the empirical objective, where $S\sim\mathcal{P}^{n}$. We prove the following result:

###### Theorem 5.1 .

Under Assumptions [2.5](#S2.Thmtheorem5) and [2.6](#S2.Thmtheorem6),
if the preconditions of Theorem [3.1](#S3.Thmtheorem1) hold,
then Algorithm [1](#alg1) is $(\epsilon,\delta)$-DP,
and returns $\mathbf{x}_{\mathrm{out}}$ such that with probability at least $1-\gamma:$

$$ $\left\|\mathcal{G}_{F_{\mathcal{P}},\eta}(\mathbf{x}_{\mathrm{out}})\right\|\leq\alpha=\widetilde{\mathcal{O}}\left(K_{1}\left(\frac{\sqrt{d_{x}}}{\epsilon n}\right)^{1/2}+K_{2}\left(\frac{\sqrt{d_{y}}}{\epsilon n}\right)^{1/3}+K_{3}\left(\frac{d_{x}}{n}\right)^{1/2}\right)~{},$ $$

where
$K_{1}=\mathcal{O}(\Delta_{F}^{1/4}\ell^{1/4}\kappa^{5/4}),~{}K_{2}=\mathcal{O}(\Delta_{F}^{1/6}\ell^{1/2}\kappa^{11/6}),~{}K_{3}=\mathcal{O}(\ell\kappa)$.
Similarly, if the preconditions of Theorem [4.1](#S4.Thmtheorem1) hold, then for any batch sizes $b_{\mathrm{in}},b_{\mathrm{out}}\in[n]$,
Algorithm [3](#alg3) is $(\epsilon,\delta)$-DP, and returns $\mathbf{x}_{\mathrm{out}}$ such that with probability at least $1-\gamma:$

$$ $\left\|\mathcal{G}_{F_{\mathcal{P}},\eta}(\mathbf{x}_{\mathrm{out}})\right\|\leq\alpha=\widetilde{\mathcal{O}}\left(K_{1}\left(\frac{\sqrt{d_{x}}}{\epsilon n}\right)^{1/2}+K_{2}\left(\frac{\sqrt{d_{y}}}{\epsilon n}\right)^{1/3}+K_{3}\cdot\frac{1}{b_{\mathrm{out}}}+K_{3}\left(\frac{d_{x}}{n}\right)^{1/2}\right)~{}.$ $$

The proof of Theorem [5.1](#S5.Thmtheorem1) relies on arguing that the hyperobjective is Lipschitz, and applying a uniform convergence bound for bounded gradients, which further implies uniform convergence of projected gradients by Lemma [2.4](#S2.Thmtheorem4).

###### Theorem 5.1 .

## 6 Proofs

Throughout the proof section, we abbreviate $f_{i}(\cdot)=f(\cdot\,;\xi_{i}),~{}g_{i}(\cdot)=g(\cdot\,;\xi_{i}),~{}F=F_{S}$.

### 6.1 Proof of Lemma 3.4

Note that the two sub-problems solved by Line 3 of Algorithm [1](#alg1) are strongly-convex and admit Lipschitz components over
$\mathcal{Y};~{}g(\mathbf{x},\cdot)$ by assumption, and $f+\lambda g$ by combining this with the smoothness/Lipschitzness of $f$, as follows:

###### Lemma 6.1 .

If $\lambda\geq\max\{\frac{2L_{1}^{g}}{\mu_{g}},\frac{L_{0}^{f}}{L_{0}^{g}}\}$ then for all $\mathbf{x}\in\mathcal{X}:~{}f(\mathbf{x},\cdot)+\lambda g(\mathbf{x},\cdot)$ is $\frac{\lambda\mu_{g}}{2}$ strongly-convex, and moreover for all $i\in[n]:~{}f_{i}(\mathbf{x},\cdot)+\lambda g_{i}(\mathbf{x},\cdot)$ is $2\lambda L_{0}^{g}$-Lipschitz.

We therefore invoke the following guarantee, which provides the optimal result for strongly-convex DP ERM via DP-Loc-GD (Algorithm [2](#alg2)).

###### Theorem 6.2 .

Suppose that $h:\mathbb{R}^{d_{y}}\to\mathbb{R}$ is a $\mu$-strongly-convex function of the form $h(\mathbf{y})=\frac{1}{n}\sum_{i=1}^{n}h(\mathbf{y},\xi_{i})$ where
$h(\cdot,\xi_{i})$ is $L$-Lipschitz for all $i\in[n]$.
Suppose $\arg\min h=:\mathbf{y}^{*}\in\mathbb{B}(\mathbf{y}_{0},R_{0})$ and that $n\geq\frac{LR_{0}^{2/\log(d_{y})}}{\mu\epsilon^{\prime}}$.
Then there is an assignment of parameters
$M=\log_{2}\log(\frac{\mu\epsilon^{\prime}n}{L})\,,~{}\sigma^{2}_{\mathrm{GD}}=\widetilde{\mathcal{O}}(L^{2}/\epsilon^{\prime 2})\,,~{}\eta_{t}=\frac{1}{\mu(t+1)},~{}T_{\mathrm{GD}}=n^{2}\,,~{}R_{m}=\widetilde{\Theta}\left(\sqrt{\frac{R_{m-1}L}{\mu\epsilon^{\prime}n}}+\frac{L\sqrt{d_{y}}}{\mu\epsilon^{\prime}n}\right)$ such that
running Algorithm [2](#alg2) satisfies $(\epsilon^{\prime},\delta^{\prime})$-DP, and outputs $\mathbf{y}_{\mathrm{out}}$ such that $\left\|\mathbf{y}_{\mathrm{out}}-\mathbf{y}^{*}\right\|=\widetilde{\mathcal{O}}\left(\frac{L\sqrt{d_{y}}}{\mu n\epsilon^{\prime}}\right)$ with probability at least $1-\gamma$.

Although the rate in Theorem [6.2](#S6.Thmtheorem2) appears in prior works such as (Bassily et al., ; Feldman et al., ), it is typically manifested through a bound in expectation (and in terms of function value) as opposed to with high probability, required for our purpose. We therefore, for the sake of completeness, provide a self-contained proof of
Theorem [6.2](#S6.Thmtheorem2) in Appendix [A](#A1).

Applied to the functions $g(\mathbf{x}_{t},\cdot)$ and $f(\mathbf{x}_{t},\cdot)+\lambda g(\mathbf{x}_{t},\cdot)$, and invoking
Lemma [6.1](#S6.Thmtheorem1), yields the following.

###### Corollary 6.3 .

If $\lambda\geq\max\{\frac{2L_{1}^{g}}{\mu_{g}},\frac{L_{0}^{f}}{L_{0}^{g}}\}$, then
$\widetilde{\mathbf{y}}_{t}$ and $\widetilde{\mathbf{y}}_{t}^{\lambda}$ (as appear in Line 3 of Algorithm [1](#alg1)) satisfy with probability at least $1-\gamma:$

$$ $\max\left\{\left\|\widetilde{\mathbf{y}}_{t}-\mathbf{y}^{*}(\mathbf{x}_{t})\right\|,~{}\|\widetilde{\mathbf{y}}_{t}^{\lambda}-\mathbf{y}^{\lambda}(\mathbf{x}_{t})\|\right\}=\widetilde{\mathcal{O}}\left(\frac{L_{0}^{g}\sqrt{d_{y}T}}{\epsilon\mu_{g}n}\right)~{}.$ $$

We are now ready to prove the main proposition of this section, which we restate below:

See [3.4](#S3.Thmtheorem4)

###### Proof of Lemma 3.4 .

As in Eq. ([3](#S3.E3)), we note that by construction $\mathcal{L}_{\lambda}^{*}(\mathbf{x})=\arg\min_{\mathbf{y}}\mathcal{L}_{\lambda}(\mathbf{x},\mathbf{y})$, therefore it holds that

$$ $\displaystyle\nabla\mathcal{L}_{\lambda}^{*}(\mathbf{x})=\nabla_{x}f(\mathbf{x},\mathbf{y}^{\lambda}(\mathbf{x}))+\lambda\left(\nabla_{x}g(\mathbf{x},\mathbf{y}^{\lambda}(\mathbf{x}))-\nabla_{x}g(\mathbf{x},\mathbf{y}^{*}(\mathbf{x}))\right)~{}.$ $$

Denoting $\mathbf{g}_{t}=\nabla_{x}f(\mathbf{x}_{t},\widetilde{\mathbf{y}}^{\lambda}_{t})+\lambda\left(\nabla_{x}g(\mathbf{x}_{t},\widetilde{\mathbf{y}}^{\lambda}_{t})-\nabla_{x}g(\mathbf{x}_{t},\widetilde{\mathbf{y}}_{t})\right)$, by the smoothness of $f$ and $g$
we see that

$$ $\left\|\mathbf{g}_{t}-\nabla\mathcal{L}_{\lambda}^{*}(\mathbf{x}_{t})\right\|\leq L_{1}^{f}\left\|\widetilde{\mathbf{y}}_{t}^{\lambda}-\mathbf{y}^{\lambda}(\mathbf{x}_{t})\right\|+\lambda L_{1}^{g}\left\|\widetilde{\mathbf{y}}_{t}^{\lambda}-\mathbf{y}^{\lambda}(\mathbf{x}_{t})\right\|+\lambda L_{1}^{g}\left\|\widetilde{\mathbf{y}}_{t}-\mathbf{y}^{*}(\mathbf{x}_{t})\right\|~{}.$ $$

Applying Corollary [6.3](#S6.Thmtheorem3) and union bounding over $T$, we can further bound the above as

$$ $\displaystyle\left\|\mathbf{g}_{t}-\nabla\mathcal{L}_{\lambda}^{*}(\mathbf{x}_{t})\right\|$ $\displaystyle=\widetilde{\mathcal{O}}\left(\frac{L_{1}^{f}L_{0}^{g}\sqrt{d_{y}T}}{\epsilon\mu_{g}n}+\frac{\lambda L_{1}^{g}L_{0}^{g}\sqrt{d_{y}T}}{\epsilon\mu_{g}n}+\frac{\lambda L_{1}^{g}L_{0}^{g}\sqrt{d_{y}T}}{\epsilon\mu_{g}n}\right)$ $\displaystyle=\widetilde{\mathcal{O}}\left(\frac{\lambda L_{1}^{g}L_{0}^{g}\sqrt{d_{y}T}}{\epsilon\mu_{g}n}\right)$ $\displaystyle=\widetilde{\mathcal{O}}\left(\frac{\lambda\ell\kappa\sqrt{d_{y}T}}{\epsilon n}\right)~{},$ $$

where the second bound holds for $\lambda\geq\frac{L_{1}^{f}}{L_{1}^{g}}$ .
∎

###### Lemma 6.1 .

###### Theorem 6.2 .

###### Corollary 6.3 .

###### Proof of Lemma 3.4 .

### 6.2 Proof of Lemma 3.5

We start by providing two lemmas, both of which
borrow ideas that appeared in the smoothness analysis of Chen et al. (), and are proved here for completeness.

###### Lemma 6.4 .

$\mathbf{y}^{\lambda}(\mathbf{x}):\mathbb{R}^{d_{x}}\to\mathbb{R}^{d_{y}}$ is $\left(\frac{4L_{1}^{g}}{\mu_{g}}\right)$-Lipschitz.

###### Proof of Lemma 6.4 .

Differentiating $\nabla_{y}\mathcal{L}_{\lambda}(\mathbf{x},\mathbf{y}^{\lambda}(\mathbf{x}))=\mathbf{0}$ with respect the first argument gives

$$ $\nabla^{2}_{xy}\mathcal{L}_{\lambda}(\mathbf{x},\mathbf{y}^{\lambda}(\mathbf{x}))+\nabla\mathbf{y}^{\lambda}(\mathbf{x})\cdot\nabla_{yy}\mathcal{L}_{\lambda}(\mathbf{x},\mathbf{y}^{\lambda}(\mathbf{x}))=\mathbf{0}~{},$ $$

hence

$$ $\nabla\mathbf{y}^{\lambda}(\mathbf{x})=-\nabla^{2}_{xy}\mathcal{L}_{\lambda}(\mathbf{x},\mathbf{y}^{\lambda}(\mathbf{x}))\cdot\left[\nabla_{yy}\mathcal{L}_{\lambda}(\mathbf{x},\mathbf{y}^{\lambda}(\mathbf{x}))\right]^{-1}~{}.$ $$

Noting that $\nabla^{2}_{xy}\mathcal{L}_{\lambda}\preceq 2\lambda L_{1}^{g}$ and $\nabla^{2}_{yy}\mathcal{L}_{\lambda}\succeq\lambda\mu_{g}/2$ everywhere, hence $[\nabla^{2}_{yy}\mathcal{L}_{\lambda}]^{-1}\preceq 2/\lambda\mu_{g}$
we get that

$$ $\left\|\nabla\mathbf{y}^{\lambda}(\mathbf{x})\right\|\leq 2\lambda L_{1}^{g}\cdot\frac{2}{\lambda\mu_{g}}=\frac{4L_{1}^{g}}{\mu_{g}}~{}.$ $$

∎

###### Lemma 6.5 .

For all $\mathbf{x}\in\mathcal{X}:~{}\left\|\mathbf{y}^{\lambda}(\mathbf{x})-\mathbf{y}^{*}(\mathbf{x})\right\|\leq\frac{L_{0}^{f}}{\lambda\mu_{g}}$.

###### Proof of Lemma 6.5 .

First, note that by definition of $\mathbf{y}^{\lambda}(\mathbf{x})$ it holds that

$$ $\mathbf{0}=\nabla_{y}\mathcal{L}_{\lambda}(\mathbf{x},\mathbf{y}^{\lambda}(\mathbf{x}))=\nabla_{y}f(\mathbf{x},\mathbf{y}^{\lambda}(\mathbf{x}))+\lambda\nabla_{y}g(\mathbf{x},\mathbf{y}^{\lambda}(\mathbf{x}))~{},$ $$

hence

$$ $\nabla_{y}g(\mathbf{x},\mathbf{y}^{\lambda}(\mathbf{x}))=-\frac{1}{\lambda}\cdot\nabla_{y}f(\mathbf{x},\mathbf{y}^{\lambda}(\mathbf{x}))~{},$ $$

so in particular by the Lipschitz assumption on $f$ we see that

$$ $\left\|\nabla_{y}g(\mathbf{x},\mathbf{y}^{\lambda}(\mathbf{x}))\right\|\leq\frac{L_{0}^{f}}{\lambda}~{}.$ $$

By invoking the $\mu$-strong convexity of $g$ we further get

$$ $\displaystyle\left\|\mathbf{y}^{\lambda}(\mathbf{x})-\mathbf{y}^{*}(\mathbf{x})\right\|\leq~{}$ $\displaystyle\frac{1}{\mu}\left\|\nabla_{y}g(\mathbf{x},\mathbf{y}^{\lambda}(\mathbf{x}))-\underset{=\mathbf{0}}{\underbrace{\nabla_{y}g(\mathbf{x},\mathbf{y}^{*}(\mathbf{x}))}}\right\|\leq\frac{L_{0}^{f}}{\lambda\mu}~{}.$ $$

∎

We are now ready to prove the main result of this section, restated below.

See [3.5](#S3.Thmtheorem5)

###### Proof of Lemma 3.5 .

For all $\mathbf{x}\in\mathcal{X}$ it holds that

$$ $\displaystyle\left\|\nabla\mathcal{L}^{*}_{\lambda,i}(\mathbf{x})\right\|$ $\displaystyle=\left\|\nabla_{x}f_{i}(\mathbf{x},\mathbf{y}^{\lambda}(\mathbf{x}))+\lambda\left[\nabla_{x}g_{i}(\mathbf{x},\mathbf{y}^{\lambda}(\mathbf{x}))-\nabla_{x}g_{i}(\mathbf{x},\mathbf{y}^{*}(\mathbf{x}))\right]\right\|$ $\displaystyle\leq\left\|\nabla_{x}f_{i}(\mathbf{x},\mathbf{y}^{\lambda}(\mathbf{x}))\right\|+\lambda\left\|\nabla_{x}g_{i}(\mathbf{x},\mathbf{y}^{\lambda}(\mathbf{x}))-\nabla_{x}g_{i}(\mathbf{x},\mathbf{y}^{*}(\mathbf{x}))\right\|~{},$ (4) $$

thus we will bound each of the summands above.

For the first term, since $\mathbf{y}^{\lambda}$ is $\frac{4L_{1}^{g}}{\mu_{g}}$ Lipschitz according to Lemma [6.4](#S6.Thmtheorem4), and $f_{i}$ is $L_{0}^{f}$-Lipschitz by assumption,
the chain rule yields the bound

$$ $\left\|\nabla_{x}f_{i}(\mathbf{x},\mathbf{y}^{\lambda}(\mathbf{x}))\right\|\leq\frac{4L_{1}^{g}L_{0}^{f}}{\mu_{g}}\leq 4\ell\kappa~{}.$ (5) $$

As to the second term, since $g_{i}$ is $L_{1}^{g}$-smooth, we use Lemma [6.5](#S6.Thmtheorem5) and get that

$$ $\lambda\left\|\nabla_{x}g_{i}(\mathbf{x},\mathbf{y}^{\lambda}(\mathbf{x}))-\nabla_{x}g_{i}(\mathbf{x},\mathbf{y}^{*}(\mathbf{x}))\right\|\leq\lambda L_{1}^{g}\left\|\mathbf{y}^{\lambda}(\mathbf{x})-\mathbf{y}^{*}(\mathbf{x})\right\|\leq\frac{L_{1}^{g}L_{0}^{f}}{\mu_{g}}\leq\ell\kappa~{}.$ (6) $$

Plugging Eqs. ([5](#S6.E5)) and ([6](#S6.E6)) into Eq. ([4](#S6.E4)) completes the proof.

∎

###### Lemma 6.4 .

###### Proof of Lemma 6.4 .

###### Lemma 6.5 .

###### Proof of Lemma 6.5 .

###### Proof of Lemma 3.5 .

### 6.3 Proof of Proposition 3.6

As $\nu_{0},\dots,\nu_{T-1}\overset{iid}{\sim}\mathcal{N}(0,\sigma^{2}I)$, a standard Gaussian norm bound (cf. Vershynin , Theorem 3.1.1) ensures that with probability at least
$1-\gamma$, for all $t\in\{0,1,\dots,T-1\}:~{}\left\|\nu_{t}\right\|^{2}\lesssim d\sigma^{2}\log(T/\gamma)\lesssim\frac{\alpha^{2}}{64}$.
We therefore condition the rest of the proof on the highly probable event under which this uniform norm bound indeed holds.
We continue by introducing some notation.
We denote $\widetilde{\nabla}_{t}=\widetilde{\nabla}{h}(\mathbf{x}_{t})+\nu_{t}$, and
$\delta_{t}:=\widetilde{\nabla}_{t}-\nabla h(\mathbf{x}_{t})$. We further denote

$$ $\displaystyle\mathbf{x}_{t}^{+}$ $\displaystyle:=\arg\min_{\mathbf{u}\in\mathcal{X}}\left\{\left\langle\nabla h(\mathbf{x}_{t}),\mathbf{u}\right\rangle+\frac{1}{2\eta}\left\|\mathbf{x}_{t}-\mathbf{u}\right\|^{2}\right\}~{},$ $\displaystyle\mathcal{G}_{t}$ $\displaystyle:=\frac{1}{\eta}(\mathbf{x}_{t}-\mathbf{x}_{t}^{+})~{},$ $\displaystyle\rho_{t}$ $\displaystyle:=\frac{1}{\eta}(\mathbf{x}_{t}-\mathbf{x}_{t+1})~{}.$ $$

Note that by construction,

$$ $\mathcal{G}_{t}=\mathcal{G}_{h,\eta}(\mathbf{x}_{t}):=\frac{1}{\eta}\left(\mathbf{x}_{t}-\mathcal{P}_{\nabla h,\eta}(\mathbf{x}_{t})\right)~{},~{}~{}~{}~{}~{}\mathcal{P}_{\nabla h,\eta}(\mathbf{x}_{t}):=\arg\min_{\mathbf{u}\in\mathcal{X}}\left[\left\langle\nabla h(\mathbf{x}_{t}),\mathbf{u}\right\rangle+\frac{1}{2\eta}\left\|\mathbf{u}-\mathbf{x}_{t}\right\|^{2}\right]~{},$ $$

and that $\mathcal{G}_{t_{\mathrm{out}}}$ is precisely the quantity we aim to bound.
We start by proving some useful lemmas regarding the quantities defined above.

###### Lemma 6.6 .

Under the event that $\left\|\nu_{t}\right\|^{2}\leq\frac{\alpha^{2}}{64}$ for all $t$, it holds that $\left\|\delta_{t}\right\|\leq\frac{\alpha}{4}$.

###### Proof.

By our assumptions on $\beta,\left\|\nu_{t}\right\|$, we get that

$$ $\left\|\delta_{t}\right\|\leq\|\widetilde{\nabla}h(\mathbf{x}_{t})-\nabla h(\mathbf{x}_{t})\|+\left\|\nu_{t}\right\|\leq\beta+\frac{\alpha}{8}\leq\frac{\alpha}{4}~{}.$ $$

∎

###### Lemma 6.7 .

It holds that $\langle\widetilde{\nabla}_{t},\rho_{t}\rangle\geq\left\|\rho_{t}\right\|^{2}$.

###### Proof.

By definition, $\mathbf{x}_{t+1}=\arg\min_{\mathbf{u}\in\mathcal{X}}\left\{\langle\widetilde{\nabla}_{t},\mathbf{u}\rangle+\frac{1}{2\eta}\left\|\mathbf{x}_{t}-\mathbf{u}\right\|^{2}\right\}$. Hence, by the first-order optimality criterion, for any $\mathbf{u}\in\mathcal{X}:$

$$ $\left\langle\widetilde{\nabla}_{t}+\frac{1}{\eta}(\mathbf{x}_{t+1}-\mathbf{x}_{t}),\mathbf{u}-\mathbf{x}_{t+1}\right\rangle\geq 0~{}.$ $$

In particular, setting $\mathbf{u}=\mathbf{x}_{t}$
yields

$$ $0\leq\left\langle\widetilde{\nabla}_{t}+\frac{1}{\eta}(\mathbf{x}_{t+1}-\mathbf{x}_{t}),\mathbf{x}_{t}-\mathbf{x}_{t+1}\right\rangle=\left\langle\widetilde{\nabla}_{t}-\rho_{t},\eta\rho_{t}\right\rangle=\eta\left(\left\langle\widetilde{\nabla}_{t},\rho_{t}\right\rangle-\left\|\rho_{t}\right\|^{2}\right)~{},$ $$

which proves the claim since $\eta>0$.
∎

With the lemmas above in hand, we are now ready to prove Proposition [3.6](#S3.Thmtheorem6).
Note that by construction, the algorithm returns the index $t$ with minimal $\left\|\rho_{t}\right\|$.
Further note that $\left\|\rho_{t}-\mathcal{G}_{t}\right\|\leq\left\|\delta_{t}\right\|$ by Lemma [2.4](#S2.Thmtheorem4), thus

$$ $\left\|\mathcal{G}_{t}\right\|\leq\left\|\rho_{t}\right\|+\left\|\delta_{t}\right\|\leq\left\|\rho_{t}\right\|+\frac{\alpha}{4}~{},$ (7) $$

where the last inequality is due to Lemma [6.6](#S6.Thmtheorem6),
hence it suffices to bound $\left\|\rho_{t_{\mathrm{out}}}\right\|$ (which is the quantity measured by the stopping criterion).
To that end, by smoothness, we have for any $t\in\{0,1,\dots,T-2\}:$

$$ $\displaystyle h(\mathbf{x}_{t+1})$ $\displaystyle\leq h(\mathbf{x}_{t})+\left\langle\nabla h(\mathbf{x}_{t}),\mathbf{x}_{t+1}-\mathbf{x}_{t}\right\rangle+\frac{L}{2}\left\|\mathbf{x}_{t+1}-\mathbf{x}_{t}\right\|^{2}$ $\displaystyle=h(\mathbf{x}_{t})-\eta\left\langle\nabla h(\mathbf{x}_{t}),\rho_{t}\right\rangle+\frac{L\eta^{2}}{2}\left\|\rho_{t}\right\|^{2}$ $\displaystyle=h(\mathbf{x}_{t})-\eta\left\langle\widetilde{\nabla}_{t},\rho_{t}\right\rangle+\frac{L\eta^{2}}{2}\left\|\rho_{t}\right\|^{2}+\eta\left\langle\delta_{t},\rho_{t}\right\rangle$ $\displaystyle\leq h(\mathbf{x}_{t})-\eta\left\|\rho_{t}\right\|^{2}+\frac{L\eta^{2}}{2}\left\|\rho_{t}\right\|^{2}+\eta\left\|\delta_{t}\right\|\cdot\left\|\rho_{t}\right\|~{},$ $$

where the last inequality followed by applying Lemma [6.7](#S6.Thmtheorem7) and Cauchy-Schwarz. Rearranging, and recalling that $\eta=\frac{1}{2L}$, hence $1<2-L\eta$
and also $\frac{1}{\eta}=2L$,
we get that

$$ $\left\|\rho_{t}\right\|^{2}-2\left\|\delta_{t}\right\|\cdot\left\|\rho_{t}\right\|\leq\left(2-L\eta\right)\left\|\rho_{t}\right\|^{2}-2\left\|\delta_{t}\right\|\cdot\left\|\rho_{t}\right\|\leq\frac{2\left(h(\mathbf{x}_{t})-h(\mathbf{x}_{t+1})\right)}{\eta}=4L\left(h(\mathbf{x}_{t})-h(\mathbf{x}_{t+1})\right)~{}.$ $$

Summing over $t\in\{0,1\dots,T-1\}$, using the telescoping property of the right hand side, and dividing by $T$ gives that

$$ $\frac{1}{T}\sum_{t=0}^{T-1}\left\|\rho_{t}\right\|\left(\left\|\rho_{t}\right\|-2\left\|\delta_{t}\right\|\right)\leq\frac{4L\left(h(\mathbf{x}_{0})-\inf h\right)}{T}~{}.$ (8) $$

Note that if for some $t\in\{0,1,\dots,T-1\}:~{}\left\|\rho_{t}\right\|\leq\frac{3\alpha}{4}$ then we have proved our desired claim by Eq. ([7](#S6.E7))
and the fact that $\left\|\rho_{t_{\mathrm{out}}}\right\|=\min_{t}\left\|\rho_{t}\right\|$ by definition. On the other hand, assuming that $\left\|\rho_{t}\right\|>\frac{3\alpha}{4}$ for all $t$, invoking Lemma [6.6](#S6.Thmtheorem6), we see that $\left\|\rho_{t}\right\|-2\left\|\delta_{t}\right\|\geq\left\|\rho_{t}\right\|-\frac{\alpha}{2}\geq\frac{1}{3}\left\|\rho_{t}\right\|$, which implies $\left\|\rho_{t}\right\|\left(\left\|\rho_{t}\right\|-2\left\|\delta_{t}\right\|\right)\geq\frac{1}{3}\left\|\rho_{t}\right\|^{2}$. Combining this with Eq. ([8](#S6.E8)) yields

$$ $\left\|\rho_{t_{\mathrm{out}}}\right\|^{2}=\min_{t\in\{0,1,\dots,T-1\}}\left\|\rho_{t}\right\|^{2}\leq\frac{1}{T}\sum_{t=0}^{T-1}\left\|\rho_{t}\right\|^{2}\leq\frac{12L\left(h(\mathbf{x}_{0})-\inf h\right)}{T}~{},$ $$

and the right side is bounded by $\frac{9\alpha^{2}}{16}$ for $T=\mathcal{O}\left(\frac{L(h(\mathbf{x}_{0})-\inf h)}{\alpha^{2}}\right)$, finishing the proof by Eq. ([7](#S6.E7)).

###### Lemma 6.6 .

###### Proof.

###### Lemma 6.7 .

###### Proof.

### 6.4 Proof of Theorem 3.1

We start by proving the privacy guarantee. Since $\mathcal{L}^{*}_{\lambda,i}$ is
$\mathcal{O}(\ell\kappa)$-Lipschitz by Lemma [3.5](#S3.Thmtheorem5), the sensitivity of $\nabla_{x}f(\mathbf{x}_{t},\widetilde{\mathbf{y}}^{\lambda}_{t})+\lambda\left(\nabla_{x}g(\mathbf{x}_{t},\widetilde{\mathbf{y}}^{\lambda}_{t})-\nabla_{x}g(\mathbf{x}_{t},\widetilde{\mathbf{y}}_{t})\right)$ is at most $\mathcal{O}(\ell\kappa)$.
Hence, by setting $\sigma^{2}=C\frac{\ell^{2}\kappa^{2}\log(T/\delta)T}{\epsilon^{2}n^{2}}$ for a sufficiently large absolute constant $C>0$, $\widetilde{\mathbf{g}}_{t}$ is $(\frac{\epsilon}{\sqrt{18T}},\frac{\delta}{3(T+1)})$-DP. By basic composition, since each iteration also runs $(\frac{\epsilon}{\sqrt{18T}},\frac{\delta}{3(T+1)})$-DP-Loc-GD twice,
we see that each iteration of the algorithm is $(3\cdot\frac{\epsilon}{\sqrt{18T}},3\cdot\frac{\delta}{3(T+1)})=(\frac{\epsilon}{\sqrt{2T}},\frac{\delta}{(T+1)})$-DP.
Noting that under our parameter assignment $\frac{\epsilon}{\sqrt{T}}\ll 1$, by advanced composition we get that throughout $T$ iterations, the algorithm is overall $(\epsilon,\delta)$-DP as claimed.

We turn to analyze the utility of the algorithm. It holds that

$$ $\displaystyle\left\|\mathcal{G}_{F,\eta}(\mathbf{x}_{t_{\mathrm{out}}})\right\|$ $\displaystyle\leq\left\|\mathcal{G}_{F,\eta}(\mathbf{x}_{t_{\mathrm{out}}})-\mathcal{G}_{\mathcal{L}^{*}_{\lambda},\eta}(\mathbf{x})\right\|+\left\|\mathcal{G}_{\mathcal{L}^{*}_{\lambda},\eta}(\mathbf{x}_{t_{\mathrm{out}}})\right\|$ $\displaystyle\leq\|\nabla F(\mathbf{x}_{t_{\mathrm{out}}})-\nabla\mathcal{L}^{*}_{\lambda}(\mathbf{x})\|+\|\mathcal{G}_{\mathcal{L}^{*}_{\lambda},\eta}(\mathbf{x}_{t_{\mathrm{out}}})\|$ $\displaystyle\lesssim\frac{\ell\kappa^{3}}{\lambda}+\|\mathcal{G}_{\mathcal{L}^{*}_{\lambda},\eta}(\mathbf{x}_{t_{\mathrm{out}}})\|$ $\displaystyle\leq\frac{\alpha}{2}+\|\mathcal{G}_{\mathcal{L}^{*}_{\lambda},\eta}(\mathbf{x}_{t_{\mathrm{out}}})\|~{},$ (9) $$

where the second inequality is due to Lemma [2.4](#S2.Thmtheorem4), the third due to Lemma [3.3](#S3.Thmtheorem3).b, and the last by our assignment of $\lambda$. It therefore remains to bound $\|\mathcal{G}_{\mathcal{L}^{*}_{\lambda},\eta}(\mathbf{x}_{t_{\mathrm{out}}})\|$.

To that end, applying Proposition [3.6](#S3.Thmtheorem6) to the function $h=\mathcal{L}^{*}_{\lambda}$,
under our assignment of $T$ — which accounts for the smoothness and initial sub-optimality bounds ensured by Lemma [3.3](#S3.Thmtheorem3) —
we get that $\|\mathcal{G}_{\mathcal{L}^{*}_{\lambda},\eta}(\mathbf{x}_{t_{\mathrm{out}}})\|\leq\frac{\alpha}{2}$, for $\alpha$ as small as

$$ $\alpha=\Theta\left(\max\{\beta,\sigma\sqrt{d_{x}\log(T/\gamma)}\}\right)$ (10) $$

By Lemma [3.4](#S3.Thmtheorem4), it holds that

$$ $\beta=\widetilde{\mathcal{O}}\left(\frac{\lambda\ell\kappa\sqrt{d_{y}T}}{\epsilon n}\right)=\widetilde{\mathcal{O}}\left(\frac{\ell^{3/2}\kappa^{11/2}\Delta_{F}^{1/2}\sqrt{d_{y}}}{\alpha^{2}\epsilon n}\right)$ (11) $$

and we also have

$$ $\sigma\sqrt{d_{x}\log(T/\gamma)}=\widetilde{\mathcal{O}}\left(\frac{\ell^{3/2}\kappa^{5/2}\Delta_{F}^{1/2}\sqrt{d_{x}}}{\alpha\epsilon n}\right)~{}.$ (12) $$

Plugging ([11](#S6.E11)) and ([12](#S6.E12)) back into Eq. ([10](#S6.E10)), and solving for $\alpha$, completes the proof.

### 6.5 Proof of Theorem 4.1

Throughout this section, we abbreviate $b=b_{\mathrm{out}}$.
We will need the following lemma, which is the
mini-batch analogue of Lemma [3.4](#S3.Thmtheorem4) from the full-batch setting.

###### Lemma 6.8 .

If $\lambda\geq\max\{\frac{2L_{1}^{g}}{\mu_{g}},\frac{L_{0}^{f}}{L_{0}^{g}},\frac{L^{f}_{1}}{L^{g}_{1}}\}$, then there is $\beta_{b}=\widetilde{\mathcal{O}}\left(\frac{\lambda\ell\kappa\sqrt{d_{y}T}}{\epsilon n}+\frac{\ell\kappa}{b}\right)$ such that with probability at least $1-\gamma/2$,
$\mathbf{g}_{t}^{B}:=\nabla_{x}f(\mathbf{x}_{t},\widetilde{\mathbf{y}}^{\lambda}_{t};B_{t})+\lambda\left(\nabla_{x}g(\mathbf{x}_{t},\widetilde{\mathbf{y}}^{\lambda}_{t};B_{t})-\nabla_{x}g(\mathbf{x}_{t},\widetilde{\mathbf{y}}_{t};B_{t})\right)$
satisfies for all $t\in\{0,\dots,T-1\}:~{}\|\nabla\mathcal{L}^{*}_{\lambda}(\mathbf{x}_{t})-\mathbf{g}^{B}_{t}\|\leq\beta_{b}$.

###### Proof of Lemma 6.8 .

It holds that

$$ $\left\|\nabla\mathcal{L}^{*}_{\lambda}(\mathbf{x}_{t})-\mathbf{g}^{B}_{t}\right\|\leq\left\|\nabla\mathcal{L}^{*}_{\lambda}(\mathbf{x}_{t})-\mathbb{E}[\mathbf{g}^{B}_{t}]\right\|+\left\|\mathbf{g}^{B}_{t}-\mathbb{E}[\mathbf{g}^{B}_{t}]\right\|~{}.$ $$

To bound the first summand, note that $\mathbb{E}[\mathbf{g}^{B}_{t}]=\nabla_{x}f(\mathbf{x}_{t},\widetilde{\mathbf{y}}^{\lambda}_{t})+\lambda\left(\nabla_{x}g(\mathbf{x}_{t},\widetilde{\mathbf{y}}^{\lambda}_{t})-\nabla_{x}g(\mathbf{x}_{t},\widetilde{\mathbf{y}}_{t})\right)$,
and therefore with probability at least $1-\gamma/4:$

$$ $\left\|\nabla\mathcal{L}^{*}_{\lambda}(\mathbf{x}_{t})-\mathbb{E}[\mathbf{g}^{B}_{t}]\right\|=\mathcal{O}\left(\frac{\lambda L_{1}^{g}L_{0}^{g}\sqrt{d_{y}T}}{\epsilon\mu_{g}n}\right)=\mathcal{O}\left(\frac{\lambda\ell\kappa\sqrt{d_{y}T}}{\epsilon n}\right)~{},$ $$

following the same proof as Lemma [3.4](#S3.Thmtheorem4) in Section [6.1](#S6.SS1),
by replacing Theorem [6.2](#S6.Thmtheorem2) by the mini-batch Theorem [A.1](#A1.Thmtheorem1) (whose guarantee holds regardless of the inner batch size) .

To bound the second summand, note that $\|\nabla_{x}f(\mathbf{x}_{t},\widetilde{\mathbf{y}}^{\lambda}_{t};\xi)+\lambda(\nabla_{x}g(\mathbf{x}_{t},\widetilde{\mathbf{y}}^{\lambda}_{t};\xi)-\nabla_{x}g(\mathbf{x}_{t},\widetilde{\mathbf{y}}_{t};\xi))\|\leq M=\mathcal{O}(\ell\kappa)$ for every $\xi\in\Xi$, by Lemma [3.5](#S3.Thmtheorem5). Hence, $\mathbf{g}^{B}_{t}$ is the average of $b$
independent vectors bounded by $M$, all with the same mean, and therefore a standard concentration bound (cf. Jin et al. ) ensures that $\|\mathbf{g}_{t}^{B}-\mathbb{E}[\mathbf{g}_{t}^{B}]\|=\widetilde{\mathcal{O}}(M/b)$ with probability at least $1-\gamma/4$, which completes the proof.
∎

We can now prove the main mini-batch result:

###### Proof of Theorem 4.1 .

We start by proving the privacy guarantee. Since $\mathcal{L}^{*}_{\lambda,i}$ is
$\mathcal{O}(\ell\kappa)$-Lipschitz by Lemma [3.5](#S3.Thmtheorem5), the sensitivity of $\nabla_{x}f(\mathbf{x}_{t},\widetilde{\mathbf{y}}^{\lambda}_{t};B_{t})+\lambda\left(\nabla_{x}g(\mathbf{x}_{t},\widetilde{\mathbf{y}}^{\lambda}_{t};B_{t})-\nabla_{x}g(\mathbf{x}_{t},\widetilde{\mathbf{y}}_{t};B_{t})\right)$ is at most
$\mathcal{O}(\ell\kappa)$.
Accordingly, the “unamplified” Gaussian mechanism (Lemma [2.2](#S2.Thmtheorem2)) ensures $(\tilde{\epsilon},\tilde{\delta})$-DP for $\tilde{\epsilon}=\widetilde{\Theta}\left(\frac{\ell\kappa}{b\sigma}\right)$,
and hence is amplified (Lemma [2.3](#S2.Thmtheorem3)) to $(\epsilon_{0},\delta_{0})$-DP for $\epsilon_{0}=\widetilde{\Theta}\left(\frac{\ell\kappa}{b\sigma}\cdot\frac{b}{n}\right)=\frac{\epsilon}{\sqrt{18T}}$,
the last holding for sufficiently large $\sigma^{2}=\widetilde{\Theta}\left(\frac{\ell^{2}\kappa^{2}T}{\epsilon^{2}n^{2}}\right)$,
and for $\delta_{0}=\frac{\delta}{3(T+1)}$.
Therefore, basic composition shows that each iteration of the algorithm is $(3\cdot\frac{\epsilon}{\sqrt{18T}},3\frac{\delta}{3(T+1)})=(\frac{\epsilon}{\sqrt{2T}},\frac{\delta}{T+1})$-DP.
Since $\epsilon/\sqrt{T}\ll 1$ under our parameter assignment, advanced composition over the $T$ iterations yields the $(\epsilon,\delta)$-DP guarantee.

We turn to analyze the utility of the algorithm. It holds that

$$ $\displaystyle\left\|\mathcal{G}_{F,\eta}(\mathbf{x}_{t_{\mathrm{out}}})\right\|$ $\displaystyle\leq\left\|\mathcal{G}_{F,\eta}(\mathbf{x}_{t_{\mathrm{out}}})-\mathcal{G}_{\mathcal{L}^{*}_{\lambda},\eta}(\mathbf{x})\right\|+\left\|\mathcal{G}_{\mathcal{L}^{*}_{\lambda},\eta}(\mathbf{x}_{t_{\mathrm{out}}})\right\|$ $\displaystyle\leq\|\nabla F(\mathbf{x}_{t_{\mathrm{out}}})-\nabla\mathcal{L}^{*}_{\lambda}(\mathbf{x})\|+\|\mathcal{G}_{\mathcal{L}^{*}_{\lambda},\eta}(\mathbf{x}_{t_{\mathrm{out}}})\|$ $\displaystyle\lesssim\frac{\ell\kappa^{3}}{\lambda}+\|\mathcal{G}_{\mathcal{L}^{*}_{\lambda},\eta}(\mathbf{x}_{t_{\mathrm{out}}})\|$ $\displaystyle\leq\frac{\alpha}{2}+\|\mathcal{G}_{\mathcal{L}^{*}_{\lambda},\eta}(\mathbf{x}_{t_{\mathrm{out}}})\|~{},$ (13) $$

where the second inequality is due to Lemma [2.4](#S2.Thmtheorem4), the third due to Lemma [3.3](#S3.Thmtheorem3), and the last by our assignment of $\lambda$. It therefore remains to bound $\|\mathcal{G}_{\mathcal{L}^{*}_{\lambda},\eta}(\mathbf{x}_{t_{\mathrm{out}}})\|$.

To that end, applying Proposition [3.6](#S3.Thmtheorem6) to the function $h=\mathcal{L}^{*}_{\lambda}$,
under our assignment of $T$ — which accounts for the smoothness and initial sub-optimality bounds ensured by Lemma [3.3](#S3.Thmtheorem3) —
we get that $\|\mathcal{G}_{\mathcal{L}^{*}_{\lambda},\eta}(\mathbf{x}_{t_{\mathrm{out}}})\|\leq\frac{\alpha}{2}$, for $\alpha$ as small as

$$ $\alpha=\Theta\left(\max\{\beta_{b},\sigma\sqrt{d_{x}\log(T/\gamma)}\}\right)$ (14) $$

By Lemma [6.8](#S6.Thmtheorem8), it holds that

$$ $\beta_{b}=\widetilde{\mathcal{O}}\left(\frac{\lambda\ell\kappa\sqrt{d_{y}T}}{\epsilon n}+\frac{\ell\kappa}{b}\right)=\widetilde{\mathcal{O}}\left(\frac{\ell^{3/2}\kappa^{11/2}\Delta_{F}^{1/2}\sqrt{d_{y}}}{\alpha^{2}\epsilon n}+\frac{\ell\kappa}{b}\right)~{},$ (15) $$

and we also have

$$ $\sigma\sqrt{d_{x}\log(T/\gamma)}=\widetilde{\mathcal{O}}\left(\frac{\ell^{3/2}\kappa^{5/2}\Delta_{F}^{1/2}\sqrt{d_{x}}}{\alpha\epsilon n}\right)~{}.$ (16) $$

Plugging ([15](#S6.E15)) and ([16](#S6.E16)) back into Eq. ([14](#S6.E14)), and solving for $\alpha$, completes the proof.

∎

###### Lemma 6.8 .

###### Proof of Lemma 6.8 .

###### Proof of Theorem 4.1 .

### 6.6 Proof of Theorem 5.1

We first need a simple lemma that immediately follows from our assumptions, and Eq. ([1](#S1.E1)):

###### Lemma 6.9 .

Under Assumptions [2.5](#S2.Thmtheorem5) and [2.6](#S2.Thmtheorem6), $F(\cdot\,;\xi)$ is $G$-Lipschitz, for $G=\mathcal{O}(\ell\kappa)$.

Accordingly, the main tool that will allow us to obtain generalization guarantees, is the following uniform convergence result in terms of gradients:

###### Lemma 6.10 ( Mei et al., 2018 , Theorem 1) .

Suppose $\overline{\mathcal{X}}\subset\mathbb{R}^{d}_{x}$ is a subset of bounded diameter
$\mathrm{diam}(\overline{\mathcal{X}})\leq D$, and that $S\sim\mathcal{P}^{n}$. Then with probability at least $1-\gamma$ for all $\mathbf{x}\in\overline{\mathcal{X}}:$

$$ $\left\|\nabla F_{\mathcal{P}}(\mathbf{x})-\nabla F_{S}(\mathbf{x})\right\|=\widetilde{\mathcal{O}}\left(G\sqrt{{d_{x}\log(D/\gamma)}/{n}}\right)~{},$ $$

where $G$ is the Lipschitz constant of $F$.(^5^55 Mei et al. () originally stated this for functions whose gradients are sub-Gaussian vectors. By Lemma [6.9](#S6.Thmtheorem9), the gradients are $G$-bounded, hence $\mathcal{O}(G)$-sub-Gaussian.)

###### Proof of Theorem 5.1 .

With probability at least $1-\gamma/2$ it holds that

$$ $\displaystyle\left\|\mathcal{G}_{F_{\mathcal{P}},\eta}(\mathbf{x}_{\mathrm{out}})\right\|$ $\displaystyle\leq\left\|\mathcal{G}_{F_{S},\eta}(\mathbf{x}_{\mathrm{out}})\right\|+\left\|\mathcal{G}_{F_{\mathcal{P}},\eta}(\mathbf{x}_{\mathrm{out}})-\mathcal{G}_{F_{S},\eta}(\mathbf{x}_{\mathrm{out}})\right\|$ $\displaystyle\leq\left\|\mathcal{G}_{F_{S},\eta}(\mathbf{x}_{\mathrm{out}})\right\|+\left\|\nabla F_{\mathcal{P}}(\mathbf{x}_{\mathrm{out}})-\nabla F_{S}(\mathbf{x}_{\mathrm{out}})\right\|$ $\displaystyle=\left\|\mathcal{G}_{F_{S},\eta}(\mathbf{x}_{\mathrm{out}})\right\|+\widetilde{\mathcal{O}}\left(\ell\kappa\sqrt{\frac{d_{x}}{n}}\right)~{},$ $$

where the second inequality is due to Lemma [2.4](#S2.Thmtheorem4), and the last is by Lemma [6.10](#S6.Thmtheorem10) with the Lipschitz bound of Lemma [6.9](#S6.Thmtheorem9)
and the domain bound $\|\mathbf{x}_{\mathrm{out}}-\mathbf{x}_{0}\|\leq D$ for some sufficiently large $D$ which is polynomial in all problem parameters (therefore only affecting log terms).
The results then follow from Theorems [3.1](#S3.Thmtheorem1) and [4.1](#S4.Thmtheorem1).
∎

###### Lemma 6.9 .

###### Lemma 6.10 ( Mei et al., 2018 , Theorem 1) .

###### Proof of Theorem 5.1 .

## 7 Discussion

In this paper, we studied differentially-private bilevel optimization, and proposed the first algorithms to solve this problem that enable any desired privacy guarantee, while also requiring only gradient queries.
Our provided guarantees hold both for constrained and unconstrained settings, cover empirical and population losses alike, and account for mini-batched gradients.

Our work leaves open several directions for future research.
First, it is likely that the rate derived in this work can be improved. Specifically, for “single”-level DP nonconvex optimization, Arora et al. () showed that incorporating variance reduction leads to gradient bounds that decay faster with the sample size.
Applying this for DP bilevel optimization as the outer loop would require, according to our analysis, to evaluate the cost of inexact gradients in variance-reduced methods, which we leave for future work.

Another open direction is understanding whether mini-batch algorithms can avoid the additive $1/b_{\mathrm{out}}$ factor in the *unconstrained* case $\mathcal{X}=\mathbb{R}^{d_{x}}$.
As previously discussed, for constrained problems, even single-level nonconvex algorithms suffer from this batch dependence (Ghadimi et al., ).
Nonetheless, for unconstrained problems,
Ghadimi and Lan () showed that setting a smaller stepsize, roughly on the order of $\alpha^{2}/\sigma^{2}$, converges to a point with gradient bounded by $\alpha$ after $\mathcal{O}(\alpha^{-4})$ steps, even for $b_{\mathrm{out}}=1$. Applying this to DP bilevel unconstrained optimization, would require analyzing SGD under biased gradients, and accounting for the larger privacy loss due to the slower convergence rate (compared to $\mathcal{O}(\alpha^{-2})$ in our case), both of which seem feasible.

Lastly, an important direction is of course empirical validation of our proposed methods.
At a high level, our methods are privatized variants of the first-order penalty approach for bilevel optimization,
which has been substantially scaled up following initial theoretically-focused works,
confirming this paradigm as
highly effective in some large scale non-private applications (Pan et al., ).
While our analysis provides conservative (worst-case) estimates for the convergence rate under privatization of both the upper and lower level problems, it would be interesting to explore the actual cost of privatization seen in practice for these problems.
As this work is a theoretically focused, we leave this for future research.

#### Acknowledgments

This research is supported through an Azrieli Foundation graduate fellowship.
We would like to express our gratitude to
Vitaly Feldman, Kunal Talwar and
the Apple MLR team for the encouraging environment in which this research took place.
Specifically, we
thank Kunal Talwar for insightful discussions,
which included pointing out the utility of localizing DP-SGD for optimal high probability guarantees.

## Appendix A Optimal DP algorithm for strongly-convex objectives

The goal of this appendix is to provide a self contained analysis of a DP algorithm
for strongly-convex optimization
which achieves the optimal convergence rate with a
a high probability guarantee.
Any such algorithm can be used as the inner loop in our DP bilevel algorithm.

In particular, we analyze *localized* DP (S)GD.
Although it would have been more natural to apply DP-SGD, this seems (at least according to our analysis) to yield an inferior rate with respect to the required high probability guarantee.(^6^66 Even if we would have sought only expectation bounds with respect to the hyperobjective, the high probability bound with respect to the inner problem is key to being able to argue about the gradient inexactness thereafter.)
Indeed, for DP-(S)GD,
previous works (such as Bassily et al. )
typically provide bounds in expectation, and then convert them into high-probability bounds via a black-box reduction, which applies several runs and selects the best run via the private noisy-min (i.e. Laplace mechanism).
The additional error incurred by this selection is of order $\frac{1}{n}$,
which translates to $\frac{1}{\sqrt{n}}$ in terms of distance to the optimum,
thus spoiling the fast rate of $\frac{1}{n}$ otherwise achieved in expectation
for strongly-convex objectives.
We therefore resort to localization [Feldman et al., ]: by running projected-(S)GD over balls with shrinking radii, applying martingale concentration bounds enables us to show that the distance to optimum shrinks as $R_{m+1}\lesssim\sqrt{\frac{R_{m}}{n}}+\frac{1}{n}$, and thus with negligible overhead we eventually recover
the optimal fast rate $R_{M}\lesssim\frac{1}{n}$ with high probability.
Our analysis differs than previous localization analyses, as it does not require adapting the noise-level and step sizes throughout the rounds.

We prove the following (which easily implies also the full-batch Theorem [6.2](#S6.Thmtheorem2)):

###### Theorem A.1 .

Suppose that $h:\mathbb{R}^{d_{y}}\times\Xi\to\mathbb{R}$ is a $\mu$-strongly-convex function of the form $h(\mathbf{y})=\frac{1}{n}\sum_{i=1}^{n}h(\mathbf{y},\xi_{i})$ where
$h(\cdot,\xi_{i})$ is $L$-Lipschitz for all $i\in[n]$.
Suppose $\arg\min h=:\mathbf{y}^{*}\in\mathbb{B}(\mathbf{y}_{0},R_{0})$,
and that $n\geq\frac{LR_{0}^{\frac{2}{\log(d_{y})}}}{\mu\epsilon^{\prime}}$.
Then given any batch size $b\in\{1,\dots,n\}$,
there is an assignment of parameters
$M=\log_{2}\log(\frac{\mu\epsilon^{\prime}n}{L}),~{}\sigma^{2}_{\mathrm{SGD}}=\widetilde{\mathcal{O}}\left(\frac{L^{2}}{\epsilon^{\prime 2}}\right),~{}\eta_{t}=\frac{1}{\mu(t+1)},~{}T_{\mathrm{SGD}}=n^{2},~{}R_{m}=\widetilde{\Theta}\left(\sqrt{\frac{R_{m-1}L}{\mu\epsilon^{\prime}n}}+\frac{L\sqrt{d_{y}}}{\mu\epsilon^{\prime}n}\right)$ such that running Algorithm [4](#alg4) satisfies $(\epsilon,\delta)$-DP, and outputs $\mathbf{y}_{\mathrm{out}}$ such that $\left\|\mathbf{y}_{\mathrm{out}}-\mathbf{y}^{*}\right\|=\widetilde{\mathcal{O}}\left(\frac{L\sqrt{d_{y}}}{\mu n\epsilon}\right)$ with probability at least $1-\gamma$.

###### Proof of Theorem A.1 .

We start by proving the privacy guarantee.
By the Lipschitz assumption, the sensitivity of $\nabla h(\cdot;B_{t})$ is at most $\frac{2L}{b}$,
thus the “unamplified” Gaussian mechanism (Lemma [2.2](#S2.Thmtheorem2)) ensures $(\tilde{\epsilon},\tilde{\delta})$-DP with $\tilde{\epsilon}=\widetilde{\Theta}\left(\frac{L}{b\sigma}\right)=\widetilde{\Theta}\left(\frac{\epsilon^{\prime}}{b}\right)$, and hence is amplified (Lemma [2.3](#S2.Thmtheorem3)) to $(\epsilon_{0},\delta_{0})$-DP for $\epsilon_{0}=\widetilde{\Theta}\left(\frac{\epsilon^{\prime}}{b}\cdot\frac{b}{n}\right)=\widetilde{\Theta}\left(\frac{\epsilon^{\prime}}{n}\right)=\widetilde{\Theta}\left(\frac{\epsilon^{\prime}}{\sqrt{T}}\right)$. Advanced composition (Lemma [2.1](#S2.Thmtheorem1)) therefore ensures that the overall algorithm is $(\epsilon^{\prime},\delta^{\prime})$-DP
(note that this uses the fact that $M=\widetilde{\mathcal{O}}(1)$).

We turn to prove the utility of the algorithm.
We first show that for all $m:$

$$ $\Pr\left[\mathbf{y}^{*}\in\mathbb{B}(\mathbf{y}_{0}^{m},R_{m})\right]\geq 1-\frac{m\gamma}{M}~{}.$ (17) $$

We prove this by induction over $m$. The base case $m=0$ follows by the assumption $\mathbf{y}^{*}\in\mathbb{B}(\mathbf{y}_{0},R_{0})$.
Denoting $\mathbf{e}_{t}^{m}:=\nabla h(\mathbf{y}_{t}^{m};B_{t})-\nabla h(\mathbf{y}_{t}^{m})$,
using the inductive hypothesis that $\mathbf{y}^{*}\in\mathbb{B}(\mathbf{y}_{0}^{m},R_{m})$ with probability at least $1-\frac{m\gamma}{M}$,
under this probably event we get

$$ $\displaystyle\left\|\mathbf{y}_{t+1}^{m}-\mathbf{y}^{*}\right\|^{2}$ $\displaystyle=\left\|\mathrm{Proj}_{\mathbb{B}(\mathbf{y}_{0}^{m},R_{m})}\left[\mathbf{y}_{t}^{m}-\eta_{t}(\nabla h(\mathbf{y}_{t}^{m};B_{t}^{m})+\nu_{t}^{m})\right]-\mathbf{y}^{*}\right\|^{2}$ $\displaystyle\leq\left\|\mathbf{y}_{t}^{m}-\eta_{t}(\nabla h(\mathbf{y}_{t}^{m};B_{t}^{m})+\nu_{t}^{m})-\mathbf{y}^{*}\right\|^{2}$ $\displaystyle=\left\|\mathbf{y}_{t}^{m}-\mathbf{y}^{*}\right\|^{2}-2\eta_{t}\left\langle\mathbf{y}_{t}^{m}-\mathbf{y}^{*},\nabla h(\mathbf{y}_{t}^{m};B_{t}^{m})+\nu_{t}^{m}\right\rangle+\eta_{t}^{2}\left\|\nabla h(\mathbf{y}_{t}^{m};B_{t}^{m})+\nu_{t}^{m}\right\|^{2}$ $\displaystyle\leq\left\|\mathbf{y}_{t}^{m}-\mathbf{y}^{*}\right\|^{2}-2\eta_{t}\left\langle\mathbf{y}_{t}^{m}-\mathbf{y}^{*},\nabla h(\mathbf{y}_{t})+\mathbf{e}^{m}_{t}+\nu_{t}^{m}\right\rangle+2\eta_{t}^{2}\left(\left\|\nu^{m}_{t}\right\|^{2}+\left\|\nabla h(\mathbf{y}_{t})\right\|^{2}\right)$ $\displaystyle=\left\|\mathbf{y}_{t}^{m}-\mathbf{y}^{*}\right\|^{2}-2\eta_{t}\left\langle\mathbf{y}_{t}^{m}-\mathbf{y}^{*},\nabla h(\mathbf{y}_{t}^{m})\right\rangle$ $\displaystyle~{}~{}~{}~{}~{}-2\eta_{t}\left\langle\mathbf{y}_{t}^{m}-\mathbf{y}^{*},\mathbf{e}^{m}_{t}+\nu_{t}^{m}\right\rangle+2\eta_{t}^{2}\left(\left\|\nu^{m}_{t}\right\|^{2}+\left\|\nabla h(\mathbf{y}_{t})\right\|^{2}\right)~{}.$ $$

Rearranging, and using the strong convexity and Lipschitz assumptions,
we see that

$$ $\displaystyle h(\mathbf{y}_{t}^{m})-h(\mathbf{y}^{*})$ $\displaystyle\leq\left\langle\mathbf{y}_{t}^{m}-\mathbf{y}^{*},\nabla h(\mathbf{y}_{t}^{m})\right\rangle-\frac{\mu}{2}\left\|\mathbf{y}_{t}^{m}-\mathbf{y}^{*}\right\|^{2}$ $\displaystyle\leq\left(\frac{1}{2\eta_{t}}-\frac{\mu}{2}\right)\left\|\mathbf{y}_{t}^{m}-\mathbf{y}^{*}\right\|^{2}-\frac{1}{2\eta_{t}}\left\|\mathbf{y}_{t+1}^{m}-\mathbf{y}^{*}\right\|^{2}$ $\displaystyle~{}~{}~{}~{}~{}~{}-\left\langle\mathbf{y}_{t}^{m}-\mathbf{y}^{*},\mathbf{e}^{m}_{t}+\nu_{t}^{m}\right\rangle+\eta_{t}\left(\left\|\nu_{t}^{m}\right\|^{2}+L^{2}\right)~{}.$ $$

Averaging over $t$ and using $\eta_{t}=\frac{1}{\mu(t+1)}$, which satisfies $\left(\frac{1}{\eta_{t}}-\frac{1}{\eta_{t-1}}-\mu\right)\leq 0$ and $\frac{1}{T}\sum_{t=0}^{T}\eta_{t}\lesssim\frac{\log T}{\mu T}$,
by Jensen’s inequality, overall we get with probability at least $1-\frac{m\gamma}{M}:$

$$ $\displaystyle h(\mathbf{y}_{0}^{m+1})-h(\mathbf{y}^{*})$ $\displaystyle=h\left(\frac{1}{T}\sum_{t=0}^{T-1}\mathbf{y}_{t}^{m}\right)-h(\mathbf{y}^{*})$ $\displaystyle\lesssim\underset{(I)}{\underbrace{\left|\frac{1}{T}\sum_{t=0}^{T-1}\left\langle\mathbf{y}_{t}^{m}-\mathbf{y}^{*},\mathbf{e}^{m}_{t}+\nu_{t}^{m}\right\rangle\right|}}+\frac{L^{2}\log T}{\mu T}+\frac{\log T}{\mu T}\underset{(II)}{\underbrace{\sum_{t=0}^{T-1}\left\|\nu_{t}^{m}\right\|^{2}}}~{}.$ (18) $$

We now apply concentration inequalities to bound $(I)$ and $(II)$ with high probability, for which we will use basic properties of sub-Gaussian distributions (cf. Vershynin , §3.4).
To bound $(I)$, note that
for all $t:~{}\mathbb{E}\mathbf{e}^{m}_{t}=\mathbb{E}\nu^{m}_{t}=\mathbf{0}$ and therefore $\mathbb{E}\left\langle\mathbf{y}_{t}^{m}-\mathbf{y}^{*},\mathbf{e}^{m}_{t}+\nu_{t}^{m}\right\rangle=0$. Moreover, $\mathbf{e}^{m}_{t}=\frac{1}{b}\sum_{\xi\in B_{t}^{m}}(\nabla h(\mathbf{x}_{t}^{m};\xi)-\nabla h(\mathbf{y}_{t}^{m}))$ is the average of $b$ independent vectors with norm bounded by at most $2L$, while $\nu_{t}^{m}\sim\mathcal{N}(\mathbf{0},\sigma^{2}_{\mathrm{SGD}}I_{d_{y}})=\mathcal{N}(\mathbf{0},\widetilde{\mathcal{O}}(\frac{L^{2}}{\epsilon^{\prime 2}})\cdot I_{d_{y}})$, and also $\left\|\mathbf{y}_{t}^{m}-\mathbf{y}^{*}\right\|\leq R_{m}$ by the inductive hypothesis. By combining all of these observations, we see that $\left\langle\mathbf{y}_{t}^{m}-\mathbf{y}^{*},\mathbf{e}^{m}_{t}+\nu_{t}^{m}\right\rangle$ is a $\mathcal{O}(R_{m}\cdot(\frac{L}{b}+\frac{L}{\epsilon^{\prime}}))=\mathcal{O}(\frac{R_{m}L}{\epsilon^{\prime}})$-sub-Gaussian random variable.
By Azuma’s inequality for sub-Gaussians [Shamir, ], we get that with probability at least $1-\frac{\gamma}{2M}:$

$$ $(I)=\widetilde{\mathcal{O}}\left(\frac{\frac{R_{m}L}{\epsilon^{\prime}}\log(\gamma/M)}{\sqrt{T}}\right)=\widetilde{\mathcal{O}}\left(\frac{R_{m}L}{\epsilon^{\prime}n}\right)~{}.$ (19) $$

To bound $(II)$, by concentration of the Gaussian norm (cf. Vershynin , Theorem 3.1.1) and the union bound we can get that with probability at least $1-\frac{\gamma}{2M}:$

$$ $(II)=\widetilde{\mathcal{O}}\left(d_{y}\sigma_{\mathrm{SGD}}^{2}\right)=\widetilde{\mathcal{O}}\left(\frac{d_{y}L^{2}}{\epsilon^{\prime 2}}\right)~{}.$ (20) $$

Plugging Eqs. ([19](#A1.E19)) and ([20](#A1.E20)) into Eq. ([18](#A1.E18)), we overall get that with probability at least $1-\frac{m\gamma}{M}-2\cdot\frac{\gamma}{2M}=1-\frac{(m+1)\gamma}{M}:$

$$ $h(\mathbf{y}_{0}^{m+1})-h(\mathbf{y}^{*})=\widetilde{\mathcal{O}}\left(\frac{R_{m}L}{\epsilon^{\prime}n}+\frac{d_{y}L^{2}}{\mu\epsilon^{\prime 2}n^{2}}\right)~{}.$ $$

Applying the $\mu$-strong-convexity of $h$, and sub-additivity of the square root, we get that

$$ $\left\|\mathbf{y}_{0}^{m+1}-\mathbf{y}^{*}\right\|\leq\sqrt{\frac{2(h(\mathbf{y}_{0}^{m+1})-h(\mathbf{y}^{*}))}{\mu}}=\widetilde{\mathcal{O}}\left(\sqrt{\frac{R_{m}L}{\mu\epsilon^{\prime}n}}+\frac{L\sqrt{d_{y}}}{\mu\epsilon^{\prime}n}\right)\leq R_{m+1}~{}.$ $$

We have therefore proven Eq. ([17](#A1.E17)).
In particular for $m=M$ we get that with probability at least $1-\gamma:$

$$ $\left\|\mathbf{y}_{\mathrm{out}}-\mathbf{y}^{*}\right\|\leq R_{M}~{},$ (21) $$

hence it remains to bound $R_{M}$. We will prove, once again by induction over $m$, that

$$ $R_{m}=\widetilde{\mathcal{O}}\left(R_{0}^{\frac{1}{2^{m}}}\left(\frac{L}{\mu\epsilon^{\prime}n}\right)^{1-\frac{1}{2^{m}}}+\frac{L}{\mu\epsilon^{\prime}n}\sum_{i=1}^{m}d_{y}^{\frac{1}{2^{i}}}\right)~{}.$ (22) $$

The base $m=0$ simply follows since the left hand side in Eq. ([22](#A1.E22))
reduces to $R_{0}$.
Denoting $A:=\frac{L}{\mu\epsilon^{\prime}n}$, by our assignment of $R_{m+1}$, the induction hypothesis and sub-additivitiy of the square root we get:

$$ $\displaystyle R_{m+1}$ $\displaystyle=\widetilde{\mathcal{O}}\left(\sqrt{R_{m}A}+A\sqrt{d_{y}}\right)$ $\displaystyle=\widetilde{\mathcal{O}}\left(A^{1/2}\left(R_{0}^{\frac{1}{2^{m+1}}}A^{\frac{1}{2}-\frac{1}{2^{m+1}}}+A^{1/2}\sum_{i=1}^{m}d_{y}^{\frac{1}{2^{i+1}}}\right)+Ad_{y}^{1/2}\right)$ $\displaystyle=\widetilde{\mathcal{O}}\left(R_{0}^{\frac{1}{2^{m+1}}}A^{1-\frac{1}{2^{m+1}}}+A\sum_{i=1}^{m+1}d_{y}^{\frac{1}{2^{i}}}\right)~{},$ $$

therefore proving Eq. ([22](#A1.E22)). In particular, for $m=M=\log_{2}\log(\frac{\mu\epsilon^{\prime}n}{L})$,
which satisfies $\frac{1}{2^{M}}=\frac{1}{\log(\frac{\mu\epsilon^{\prime}n}{L})}=\frac{1}{\log(1/A)}$
we get

$$ $\displaystyle R_{M}$ $\displaystyle=\widetilde{\mathcal{O}}\left(R_{0}^{\frac{1}{\log(1/A)}}A^{1+\frac{1}{\log(A)}}+MAd_{y}^{1/2}\right)$ $\displaystyle=\widetilde{\mathcal{O}}\left(R_{0}^{\frac{1}{\log(1/A)}}A+Ad^{1/2}\right)$ $\displaystyle=\widetilde{\mathcal{O}}\left(R_{0}^{\frac{1}{\log(\mu\epsilon^{\prime}n/L)}}\frac{L}{\mu\epsilon^{\prime}n}+\frac{Ld_{y}^{1/2}}{\mu\epsilon^{\prime}n}\right)$ $\displaystyle=\widetilde{\mathcal{O}}\left(\frac{L\sqrt{d_{y}}}{\mu\epsilon^{\prime}n}\right)~{},$ $$

where the last follows from our assumption on $n$.
This completes the proof by Eq. ([21](#A1.E21)).
∎

###### Theorem A.1 .

###### Proof of Theorem A.1 .

## Appendix B Auxiliary Lemma

See [2.4](#S2.Thmtheorem4)

###### Proof of Lemma 2.4 .

The proof is due to Ghadimi et al. [].
By definition,

$$ $\displaystyle\mathcal{P}_{\mathbf{v},\eta}(\mathbf{x})$ $\displaystyle=\arg\min_{\mathbf{u}\in\mathcal{X}}\left\{\langle\mathbf{v},\mathbf{u}\rangle+\frac{1}{2\eta}\left\|\mathbf{x}-\mathbf{u}\right\|^{2}\right\}~{},$ $\displaystyle\mathcal{P}_{\mathbf{w},\eta}(\mathbf{x})$ $\displaystyle=\arg\min_{\mathbf{u}\in\mathcal{X}}\left\{\langle\mathbf{w},\mathbf{u}\rangle+\frac{1}{2\eta}\left\|\mathbf{x}-\mathbf{u}\right\|^{2}\right\}~{},$ $$

hence by first order optimality criteria, for any $\mathbf{u}\in\mathcal{X}:$

$$ $\displaystyle\left\langle\mathbf{v}+\frac{1}{\eta}(\mathcal{P}_{\mathbf{v},\eta}(\mathbf{x})-\mathbf{x}),\mathbf{u}-\mathcal{P}_{\mathbf{v},\eta}(\mathbf{x})\right\rangle$ $\displaystyle\geq 0~{},$ $\displaystyle\left\langle\mathbf{w}+\frac{1}{\eta}(\mathcal{P}_{\mathbf{w},\eta}(\mathbf{x})-\mathbf{x}),\mathbf{u}-\mathcal{P}_{\mathbf{w},\eta}(\mathbf{x})\right\rangle$ $\displaystyle\geq 0~{}.$ $$

Plugging $\mathcal{P}_{\mathbf{w},\eta}(\mathbf{x})$ into the first inequality above, and $\mathcal{P}_{\mathbf{v},\eta}(\mathbf{x})$ into the second,
shows that

$$ $\displaystyle 0$ $\displaystyle\leq\left\langle\mathbf{v}+\frac{1}{\eta}(\mathcal{P}_{\mathbf{v},\eta}(\mathbf{x})-\mathbf{x}),\mathcal{P}_{\mathbf{w},\eta}(\mathbf{x})-\mathcal{P}_{\mathbf{v},\eta}(\mathbf{x})\right\rangle~{},$ $\displaystyle 0$ $\displaystyle\leq\left\langle\mathbf{w}+\frac{1}{\eta}(\mathcal{P}_{\mathbf{w},\eta}(\mathbf{x})-\mathbf{x}),\mathcal{P}_{\mathbf{v},\eta}(\mathbf{x})-\mathcal{P}_{\mathbf{w},\eta}(\mathbf{x})\right\rangle=\left\langle-\mathbf{w}+\frac{1}{\eta}(\mathbf{x}-\mathcal{P}_{\mathbf{w},\eta}(\mathbf{x})),\mathcal{P}_{\mathbf{w},\eta}(\mathbf{x})-\mathcal{P}_{\mathbf{v},\eta}(\mathbf{x})\right\rangle~{}.$ $$

Summing the two inequalities yields

$$ $\displaystyle 0$ $\displaystyle\leq\left\langle{\mathbf{v}-\mathbf{w}}+\frac{1}{\eta}(\mathcal{P}_{\mathbf{v},\eta}(\mathbf{x})-\mathcal{P}_{\mathbf{w},\eta}(\mathbf{x})),\mathcal{P}_{\mathbf{w},\eta}(\mathbf{x})-\mathcal{P}_{\mathbf{v},\eta}(\mathbf{x})\right\rangle$ $\displaystyle=\left\langle\mathbf{v}-\mathbf{u},\mathcal{P}_{\mathbf{w},\eta}(\mathbf{x})-\mathcal{P}_{\mathbf{v},\eta}(\mathbf{x})\right\rangle-\frac{1}{\eta}\left\|\mathcal{P}_{\mathbf{w},\eta}(\mathbf{x})-\mathcal{P}_{\mathbf{v},\eta}(\mathbf{x})\right\|^{2}$ $\displaystyle\leq\left\|\mathcal{P}_{\mathbf{w},\eta}(\mathbf{x})-\mathcal{P}_{\mathbf{v},\eta}(\mathbf{x})\right\|\left(\left\|\mathbf{v}-\mathbf{u}\right\|-\frac{1}{\eta}\left\|\mathcal{P}_{\mathbf{w},\eta}(\mathbf{x})-\mathcal{P}_{\mathbf{v},\eta}(\mathbf{x})\right\|\right)~{}.$ $$

Hence,

$$ $\displaystyle\left\|\mathbf{v}-\mathbf{u}\right\|$ $\displaystyle\geq\frac{1}{\eta}\left\|\mathcal{P}_{\mathbf{v},\eta}(\mathbf{x})-\mathcal{P}_{\mathbf{w},\eta}(\mathbf{x})\right\|$ $\displaystyle=\left\|\frac{1}{\eta}\left(\mathcal{P}_{\mathbf{v},\eta}(\mathbf{x})-\mathbf{x}\right)-\frac{1}{\eta}\left(\mathcal{P}_{\mathbf{w},\eta}(\mathbf{x})-\mathbf{x}\right)\right\|$ $\displaystyle=\left\|\mathcal{G}_{\mathbf{v},\eta}(\mathbf{x})-\mathcal{G}_{\mathbf{w},\eta}(\mathbf{x})\right\|~{}.$ $$

∎

###### Proof of Lemma 2.4 .

## Peer Reviews

confidence: 2
contribution: 3
initial_rating: 6
presentation: 3
questions: Since the paper is built on recent advancements in (non-private) first-order bilevel optimization, what are the technical challenges when moving from non-private to private case?
What are the technical difficulties of the analysis of the algorithm compared to the ones for non-private bilevel optimization?

I hope to see some empircal results if possible.
soundness: 3
strengths: - The paper studies bilevel optimization under central DP, establishing first results in the area.
- It provides a mini-batch variant and addresses both ERM and population risks. 
- The paper has a well organized structure.
summary: This paper studies bilevel optimization under the central DP model. The authors leverage recent advancements in (non-private) first-order bilevel optimization and propose algorithms that cover both ERM and population loss.
The proposed algorithm avoids computing Hessian and uses only gradients, finding approximate solutions under certain conditions. Authors also show the mini-batch variant has similar convergence properties.
weaknesses: See questions below

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
questions: The closest existing result is from Chen (2024), but due to the difference in the DP frameworks (central DP vs. local DP) it is hard to draw a direct comparation. Since both DP mechanisms are achieved by adding Gaussian noise, a question remains: When the scale of noise is identical, can the performance between these methods be effectively compared?
soundness: 3
strengths: This framework can work with different inner algorithms with only dependency on its convergence rate and DP parameters.
summary: The paper presents DP algorithms for bilevel optimization problems, where upper-level objectives are smoot and the lower-level problems are smooth and strongly convex. The proposed gradient-based DP algorithms can avoid Hessian computations.
weaknesses: While the methods outlined in the paper appear innovative, they lack a clear comparative analysis with existing methods. Fully first-order methods have already been established in non-DP settings; however, it's not apparent whether the DP version introduces significant additional complexities. 

The paper lacks empirical evaluation, which is noted as future work. This omission is unconventional and limits the ability to gauge practical effectiveness. Exploring the interaction between outer and inner algorithms through experiments could yield insightful results regarding their actual performances.

The "any desired privacy" mentioned in the contributions does not have a clear meaning because:
Adjusting a parameter to achieve a specific \epsilon,\delta value is almost always possible in all DP algorithms. The algorithm can meet any pair of \epsilon,\delta pair. However, through naive application of gaussian noise. While being correct, it does not exactly produce the desired privacy. Furthermore, meeting any privacy specification doesn't necessarily imply efficiency.

---

confidence: 4
contribution: 3
initial_rating: 8
presentation: 4
questions: We get guarantees for the gradient norm but the paper calls it "ERM." Is this a standard terminology for the non-convex problem?
soundness: 4
strengths: This submission provides a clear contribution. Private bilevel optimization is certainly worthy of study. The paper is written well.
summary: This paper introduces a method for differentially private bilevel optimization. In bilevel optimization, the constraint set itself is given as another optimization problem. This submission aims to produce a value with a small gradient norm (we do not assume the "upper" objective is convex).

This problem has received a lot of attention recently because of new approaches, based on penalizing/smoothing the objective, that only require first-order information. One recent paper considered bilevel optimization in the local model and assumed access to second-order information. This submission operates in the central model and only uses gradients.

The submission provides theoretical guarantees for the minimizing the norm of the empirical gradient and for the population term. It also analyzes a minibatch variant with roughly similar guarantees.
weaknesses: The submission is not very deep: once the problem is stated and we've decided to following the non-private first-order penalty methods, the analysis strikes me as essentially a process of assembling the right tools and carefully applying them and tracking the error. (I don't mean to imply that this is trivial, just that the paper would appeal to a wider audience if it had new ideas for private optimization. Maybe it does, and I wasn't able to pick them up?)

---

confidence: 3
contribution: 3
initial_rating: 8
presentation: 4
questions: The proof technique assumes that the lower-level objective $g(x, y)$ is strongly convex in $y$. Can this assumption be weakened so that only the convexity of $g(x,y)$ is required?
soundness: 3
strengths: According to the author, the proposed method is the first fully first-order DP optimization method that solves the bilevel optimization problem. The proof seems correct to me and the paper is well-organized.
summary: The paper proposes a novel algorithm to solve differential private bilevel optimization problems, assuming that (1) the upper-level objective is smooth and Lipschitz and (2) the lower-level function is strongly convex and locally Lipschitz around optima. 
Compared to existing approaches, the proposed method is fully first-order and doesn’t need assumptions on privacy parameter $(\varepsilon, \delta)$
weaknesses: As the authors pointed out in the discussion section, the error rate for bilevel ERM, as well as the additive factor on the inverse batch size that appeared in minibatch bilevel ERM, could potentially be improved.

Meta-review: Paper studies the Differentially Private optimization of smooth nonconvex-strongly-convex Bilevel problem. Authors provide DP algorithms for solving both the ERM and population level problem in both full-batch and mini-batch settings. Only other work earlier work on DP bilevel optimization requires Hessian inversion and studies provides only stricter local DP guarantees. Theoretical results appear correct, but it is noted to be straightforward even though tedious. Unfortunately, authors do not provide any empirical evaluation to validate their results which limits the practical usefulness of the manuscript.

Decision: Reject