Research map / Federated learning and privacy / Differential privacy
Differentially Private Bilevel Optimization: Efficient Algorithms with Near-Optimal Rates
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives near-tight upper and lower bounds for differentially private convex bilevel ERM via efficient exponential and regularized exponential mechanisms (using log-concave sampling with inexact evaluations), plus a second-order DP algorithm for nonconvex bilevel with d_y-independent stationarity rates.
Problem
Differentially private bilevel optimization: minimax-optimal excess risk for convex bilevel ERM/SO and better stationarity rates for nonconvex bilevel problems, without dependence on inner dimension.
Approach
Uses exponential and regularized exponential mechanisms for convex bilevel ERM, implemented efficiently via a new log-concave grid-walk sampler robust to bounded function-evaluation error; for nonconvex, privatizes a second-order hypergradient approximation computed with a non-private inner solver, so the noise scales with the outer gradient sensitivity rather than d_y.
Key results
- Pure ε-DP bilevel ERM achieves excess empirical risk O(d_x/(εn)·[L_{f,x}D_x + L_{f,y}D_y + L_{f,y}L_{g,y}/μ_g]), with a matching lower bound Ω((L_{f,x}D_x+L_{f,y}D_y)·min{1,d_x/(nε)}).
- (ε,δ)-DP convex bilevel ERM achieves O(G D_x √(d_x log(1/δ))/(εn)), matching single-level DP-ERM up to bilevel-complexity terms.
- Nonconvex second-order DP algorithm gives E||∇Φ|| ≲ Õ((√d_x/(εn))^{1/2}), independent of d_y, improving over the prior bound with d_y dependence.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the second-order DP method that computes the lower-level approximate minimizer non-privately, then noises the upper-level gradient | Non-convex bilevel ERM · Non-convex bilevel ERM, (ε, δ)-DP | stationarity (expected gradient norm): \tilde{O}\left(\left(\frac{\sqrt{d_x}}{\varepsilon n}\right)^{1/2}\right) | Helped |
| Warm-start the second-order DP method with the exponential mechanism | Second-order DP bilevel optimization · Non-convex bilevel ERM, (ε, δ)-DP; d_x < n ε | stationarity (expected gradient norm): \tilde{O}\left(\frac{\sqrt{d_x}}{(\varepsilon n)^{3/4}}\right) | Helped |
| Privatize the lower-level solution at each iteration | Naive privatized bilevel optimization · Non-convex bilevel ERM | stationarity (expected gradient norm): O(\sqrt{d_x + d_y}/\varepsilon n)^{1/2} | Hurt |
Surprising findings
- DP bilevel ERM is provably harder than single-level DP-ERM when L_{f,y}D_y > L_{f,x}D_x, showing a separation from single-level optimization.
Limitations
- Convex SO population bound is suboptimal relative to the conjectured lower bound.
- Nonconvex warm-start algorithm is not polynomial-time (uses exponential mechanism).
- No experimental evaluation; purely theoretical.
Experimental setup
Metrics: excess empirical risk excess population risk expected gradient norm
Baselines: DP bilevel penalty-based method (local DP prior work) single-level DP-ERM rates
Builds on: exponential mechanism regularized exponential mechanism grid-walk sampling
Closest papers by meaning
- Locally Differentially Private Decentralized Stochastic Bilevel Optimization with Guaranteed Convergence Accuracy (ICML 2024 · similarity 0.93)
- Faster Algorithms for User-Level Private Stochastic Convex Optimization (NeurIPS 2024 · similarity 0.89)
- Differentially Private Optimization with Sparse Gradients (NeurIPS 2024 · similarity 0.88)
- Distributed Bilevel Optimization with Communication Compression (ICML 2024 · similarity 0.88)
- TSP: A Two-Sided Smoothed Primal-Dual Method for Nonconvex Bilevel Optimization (ICML 2025 · similarity 0.88)
- Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling (NeurIPS 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.