Differentially Private Bilevel Optimization: Efficient Algorithms with Near-Optimal Rates

Thank you for your thoughtful and detailed review. We respond to your comments below:

How practical it is to sampling from an exponential distribution like the one in Eq.(5), given the bilevel structure. Are there any readily available numerical packages/tools for this?

While we show how to sample from this distribution efficiently, we also acknowledge that our method might not be practical. Since our work is purely theoretical, we leave practical implementation issues for future work, as discussed in Conclusion and Limitations.

What is $D_y$? It first appears in line 150 without definition and is later used in many places. I assume that $D_y$ is intended to be the same as $Diam(\mathcal{Y})$ (or its upper bound) defined in line 113?

Indeed, $D_y = Diam(\cal{Y})$. Thank you for catching this omission--we will add the definition to line 113.

...consider moving the hard instance around line 692 constructed for proving the lower bound to some place immediate after Assumptions 2.1 & 2.2 as a motivating example to illustrate these assumptions.

Good suggestion. We will do this in the revision.

minor typos

We will fix these. Thank you again for your careful reading of our manuscript.

Thank you for your thoughtful and detailed review. We respond to your comments below:

The paper would be strengthened by concrete bilevel optimization examples that illustrate why extending from convex to non-convex outer functions is practically important.

There are many important nonconvex BLO problems that arise in practice: e.g., model selection and hyperparameter tuning, and some Stackelberg game models (see lines 128-129). Additionally, if the loss function $f$ is non-convex (e.g., as in deep learning), then the corresponding BLO problem is non-convex. We will elaborate on this in the revision.

it's unclear whether constants like $\mu_g$ are inherent to the problem instance or chosen by the practitioner.

$\mu_g$ parameter is inherent to the problem instance: it describes the strong convexity of function $g$. It is not chosen by the practitioner.

How does the lower bound extend to arbitrary values of $\mu_g$?

Our lower bound construction satisfies $\mu_g \approx L_{g,y}/D_y$, or equivalently $D_y \approx L_{g,y}/\mu_g$. Thus, our lower bounds can equivalently be written in terms of $\mu_g$ by substituting the above relation for $D_y$. Our lower bound does not apply in the parameter regime $\mu_g \ll L_{g,y}/D_y$. Note that providing a lower bound in this regime is an open problem even for simple single-level DP ERM, as the lower bound construction of BST14 also requires $\mu \approx L/D$.

Section 4 begins by assuming $\mathcal{X}$ is unconstrained, but Theorem 4.3 reverts to $\mathcal{X}$ being a convex subset. What is the scope of the unconstrained assumption?

All of our results in Section 4 hold for both constrained and unconstrained settings (see footnote 1). For Theorem 4.3, we additionally require the existence of a compact set $\mathcal{X}$ containing a global unconstrained minimizer. We will further clarify this in the revision.

Are there corresponding [tight] lower bounds establishing optimality for this [nonconvex] problem class?

There are no tight lower bounds for DP nonconvex optimization, even in the simpler single-level optimization setting. We highlight this as an important problem for future work in the Conclusion.

Thank you for your thoughtful and detailed review. We respond to your comments below:

The work is entirely theoretical. No experimental validation is provided...

We do not consider the lack of experiments in our paper to be a weakness: Like many accepted NeurIPS papers, our work is about understanding the fundamental complexity of an important problem, and we hope our paper will be judged on those terms. As discussed in the Conclusion and Limitations sections, empirical investigation is an important direction for future work on DP BLO.

The efficiency claims for the exponential and regularized exponential mechanisms rely on complex sampling schemes (e.g., grid-walk) that may be impractical at scale.

We agree that our sampling algorithm may be complex to implement in large-scale practical applications, but do not consider this to be a weakness: The focus of our work is entirely theoretical–understanding the complexity bounds and developing polynomial-time algorithms that achieve these bounds. We leave it as future work to provide practical implementations of these algorithms.

Thank you for your reply, which helps clarify some of my concerns. Nevertheless, I still believe that, the complex sampling scheme would be a drawback of the algorithm for practical implementation, despite the theoretical side contribution of the work. Given that, I will maintain my original score.

Thank you for your thoughtful and detailed review. We respond to your comments below:

Discussion or justification for when and why the outer objective $\Phi$ would be convex.

Convex BLO (i.e. convex $\Phi$) is important, as evidenced by the large body of work studying this problem non-privately: see e.g., Ghadimi & Wang (2018), Ji & Liang (2023) and the references within. There are many applications of convex BLO problems, including: few-shot meta-learning with shared embedding model (Bertinetto et al., 2018), biased regularization in hyperparameter optimization (Grazzi et al., 2020), and fair resource allocation problem over communication networks (Srikant and Ying, 2013). With the additional space allowed for camera-ready, we will add a paragraph on these applications.

The proof of SCO result (second part of Theorem 3.3) appears to be either incorrect or at least unsound

We thank the reviewer for this excellent and insightful comment. We agree that a rigorous generalization analysis is crucial, and we apologize for its omission in the initial draft.

The reviewer is correct that applying a classic stability argument (e.g., via a "ghost sample") to the bilevel setting is non-trivial. The main difficulty arises from the need to bound the error propagation from the lower-level optimization. During the rebuttal period, we used new sound analyses to obtain a generalization error bound of order O(\min[1/n^{1/4}, \sqrt{(d_x+d_y)/n}\]).

Proof sketch: As the first step, the $\mu_g$-strong convexity of the lower-level problem allows us to relate the solution error to the gradient of the true objective at the empirical minimizer: $|\hat{y}_Z^{\text{star}}(x) - y^{\text{star}}(x)\| \le \|\nabla_y G(x, \hat{y}_Z^{\text{star}}(x))\| / \mu_g$.

From here, there are two ways to bound the term on the right:

1. Uniform Convergence: A standard approach is to bound the gradient term using uniform concentration arguments. This is a sound method, but as the reviewer might expect, it results in a dimension-dependent generalization error of $O(\sqrt((d_x+d_y)/n))$.
2. Variance Analysis: To seek a dimension-independent bound, we analyzed the variance of $||\nabla_y G(x,\hat{y}_Z^{\text{star}}(x))||$. Our analysis utilizes the Efron-Stein Inequality. However this path currently yields a worse generalization rate of $O(1/n^{1/4})$. In the revised manuscript, we will include the complete derivation. We will also add a discussion framing the gap between our generalization error bound and the optimal $O(n^{-½})$ bound as an important open problem in DP bilevel SCO.

Can the result in Theorem 3.8 be directly applied to Theorems 3.1 or 3.3?

Yes, and we have updated the manuscript to make the direct application of Theorem 3.8 to our proposed mechanisms in Theorems 3.1 and 3.3 more explicit. The function $f(\theta)$ in Theorem 3.8 is instantiated as follows for our two algorithms:

1. For the Exponential Mechanism (Algorithm in (4)), we set $f(\theta) = (\epsilon/2s)\hat{\Phi}_Z(\theta)$ where $s$ is the sensitivity of the empirical objective.
2. For the Regularized Exponential Mechanism (Algorithm in (5)), we set $f(\theta)= k(\hat{\Phi}_Z(\theta)+ \mu \|\theta\|^2)$ where $k,\mu$ are two hyperparameters set correspondingly in Theorem B.8.

How large can the estimation error $\zeta(\theta)$ in Theorem 3.8 be while still achieving the stated bounds in Theorem 3.1? Furthermore, can this level of error be achieved under differential privacy constraints?

It suffices to set the estimation error $\zeta(\theta) = O(\varepsilon)$ in order to efficiently achieve DP and the desired excess risk bound. This follows from the distance bound in Theorem 3.8 and the following fact: if two non-negative random variables $X$ and $X′$ satisfy $\varepsilon$-differential privacy, then $E[X] \le e^{\varepsilon} E[X']$. Now take $X$ as the empirical risk under the conceptual perfect sampler and X' as the empirical risk the approximate sampler (i.e. actual implementation).

We appreciate your engagement with our work, and we hope the clarifications below help convey why (convex) DP BLO represents a significant problem and one where this paper makes foundational progress.

Why convex $\Phi$ matters.
The examples we cited in our rebuttal—few-shot meta-learning with a shared embedding model (Bertinetto et al., 2018), biased regularization in hyperparameter optimization (Grazzi et al., 2020), and fair resource allocation in communication networks (Srikant and Ying, 2013)—are indeed cases where $\Phi$ is convex, as discussed in [1, p.7]. These problems arise in real-world applications and our algorithms are near-optimal.

As another concrete problem class with convex $\Phi$, consider quadratic lower-level objectives of the form $g(x,y) = y^\top H y + x^\top J y + b^\top y + h(x)$ where $H$ and $J$ are bounded Hessian and Jacobian matrices, and $f$ satisfies the assumptions in our paper. This also yields convex $\Phi$. We believe these examples illustrate that convex BLO is not only mathematically tractable but also relevant to practical scenarios, making it a natural and important starting point for a rigorous DP theory.

SCO rates and our overall contributions.
We acknowledge that the corrected SCO bound is weaker than the original statement, and we thank you for pointing out the earlier issue. While this bound is not yet optimal, it is the first established bound for DP bilevel SCO. Combined with our near-optimal ERM bounds (including the first lower bounds for DP BLO) and improved state-of-the-art rates for non-convex BLO, we believe the overall theoretical contributions remain strong and impactful.

We hope these clarifications help convey both the significance of convex DP BLO and the breadth of our contributions, and we would be grateful if they inform your overall assessment of the paper.

[1] Ji and Liang. Lower Bounds and Accelerated Algorithms for Bilevel Optimization, 2023.