Differentially Private Bilevel Optimization
Not on the map. Why?
Abstract (arXiv)
We present differentially private (DP) algorithms for bilevel optimization, a problem class that received significant attention lately in various machine learning applications. These are the first algorithms for such problems under standard DP constraints, and are also the first to avoid Hessian computations which are prohibitive in large-scale settings. Under the well-studied setting in which the upper-level is not necessarily convex and the lower-level problem is strongly-convex, our proposed gradient-based (ε,δ)-DP algorithm returns a point with hypergradient norm at most widetildeOleft((√dup/ε n)1/2+(√dlow/ε n)1/3right) where n is the dataset size, and dup/dlow are the upper/lower level dimensions. Our analysis covers constrained and unconstrained problems alike, accounts for mini-batch gradients, and applies to both empirical and population losses. As an application, we specialize our analysis to derive a simple private rule for tuning a regularization hyperparameter.
Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 59 of its 92 references that are in the map. First posted on arXiv 29 Sep 2024.
Builds on
59 of 92 references.
References · 59
- 2016Deep Learning with Differential Privacycited by 2,728
- 2019Invariant Risk Minimizationcited by 1,854
- 2018DARTS: Differentiable Architecture Searchcited by 1,798
- 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 724
- 2016Learning to learn by gradient descent by gradient descentcited by 620
- 2019Meta-Learning with Implicit Gradientscited by 525
- 2018Bilevel Programming for Hyperparameter Optimization and Meta-Learningcited by 405
- 2018Meta-learning with differentiable closed-form solverscited by 397
- 2015Gradient-based Hyperparameter Optimization through Reversible Learningcited by 360
- 2019Optimizing Millions of Hyperparameters by Implicit Differentiationcited by 304
- 2018Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergencescited by 242
- 2018Approximation Methods for Bilevel Programmingcited by 236
38 more
- 2017Forward and Reverse Gradient-Based Hyperparameter Optimizationcited by 234
- 2020Bilevel Optimization: Convergence Analysis and Enhanced Designcited by 222
- 2019Private Stochastic Convex Optimization with Optimal Ratescited by 186
- 2020Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 153
- 2020A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Criticcited by 144
- 2013Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimizationcited by 143
- 2017A Review on Bilevel Optimization: From Classical to Evolutionary Approaches and Applicationscited by 129
- 2018Differentially Private Empirical Risk Minimization Revisited: Faster and More Generalcited by 128
- 2019A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Normcited by 106
- 2021A Near-Optimal Algorithm for Stochastic Bilevel Optimization via Double-Momentumcited by 106
- 2021Provably Faster Algorithms for Bilevel Optimizationcited by 106
- 2022BOME! Bilevel Optimization Made Easy: A Simple First-Order Approachcited by 105
- 2018Privately Learning High-Dimensional Distributionscited by 104
- 2021Hyperparameter Tuning with Renyi Differential Privacycited by 104
- 2023A Fully First-Order Method for Stochastic Bilevel Optimizationcited by 100
- 2019High probability generalization bounds for uniformly stable algorithms with nearly optimal ratecited by 98
- 2023DoGE: Domain Reweighting with Generalization Estimationcited by 90
- 2023On Penalty-based Bilevel Gradient Descent Methodcited by 87
- 2016The Landscape of Empirical Risk for Non-convex Lossescited by 86
- 2018Private Selection from Private Candidatescited by 75
- 2021A Single-Timescale Method for Stochastic Bilevel Optimizationcited by 69
- 2020Convergence of Meta-Learning with Task-Specific Adaptation over Partial Parameterscited by 65
- 2023On Penalty Methods for Nonconvex Bilevel Optimization and First-Order Stochastic Approximationcited by 51
- 2022Private Convex Optimization via Exponential Mechanismcited by 49
- 2023First-order penalty methods for bilevel optimizationcited by 41
- 2023On Finding Small Hyper-Gradients in Bilevel Optimization: Hardness Results and Improved Analysiscited by 39
- 2022Invariant and Transportable Representations for Anti-Causal Domain Shiftscited by 37
- 2024ScaleBiO: Scalable Bilevel Optimization for LLM Data Reweightingcited by 37
- 2021Randomized Stochastic Variance-Reduced Methods for Multi-Task Stochastic Bilevel Optimizationcited by 33
- 2022Faster Rates of Convergence to Stationary Points in Differentially Private Optimizationcited by 32
- 2022A Conditional Gradient-based Method for Simple Bilevel Optimization with Convex Lower-level Problemcited by 17
- 2023ReSQueing Parallel and Private Stochastic Convex Optimizationcited by 17
- 2023Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully First-Order Oraclescited by 17
- 2023A Lower Bound and a Near-Optimal Algorithm for Bilevel Empirical Risk Minimizationcited by 16
- 2024Constrained Bi-Level Optimization: Proximal Lagrangian Value function Approach and Hessian-free Algorithmcited by 16
- 2023Efficient Gradient Approximation Method for Constrained Bilevel Optimizationcited by 15
- 2023Projection-Free Methods for Stochastic Simple Bilevel Optimization with Convex Lower-level Problemcited by 13
- 2023Private (Stochastic) Non-Convex Optimization Revisited: Second-Order Stationary Points and Excess Riskscited by 12
50 most cited of 59 All 59 (JSON)
Built on by
Citing papers per year: 2025: 2.
2 papers.