10 papers
Differentially Private Bilevel Optimization: Efficient Algorithms with Near-Optimal Rates
Andrew Lowy, Daogao Liu
Bilevel optimization, in which one optimization problem is nested inside another, underlies many machine learning applications with a hierarchical structure -- such as meta-learnin…
Private Geometric Median in Nearly-Linear Time
Syamantak Kumar, Daogao Liu, Kevin Tian +1
Estimating the geometric median of a dataset is a robust counterpart to mean estimation, and is a fundamental problem in computational geometry. Recently, [HSU24] gave an $(\vareps…
Faster Algorithms for User-Level Private Stochastic Convex Optimization
Andrew Lowy, Daogao Liu, Hilal Asi
We study private stochastic convex optimization (SCO) under user-level differential privacy (DP) constraints. In this setting, there are users (e.g., cell phones), each possess…
Adaptive Batch Size for Privately Finding Second-Order Stationary Points
Daogao Liu, Kunal Talwar
There is a gap between finding a first-order stationary point (FOSP) and a second-order stationary point (SOSP) under differential privacy constraints, and it remains unclear wheth…
Improved Sample Complexity for Private Nonsmooth Nonconvex Optimization
Guy Kornowski, Daogao Liu, Kunal Talwar
We study differentially private (DP) optimization algorithms for stochastic and empirical objectives which are neither smooth nor convex, and propose methods that return a Goldstei…
Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions
Hilal Asi, Daogao Liu, Kevin Tian
We study the problem of differentially private stochastic convex optimization (DP-SCO) with heavy-tailed gradients, where we assume a -moment bound on the Lipschitz…
Private Online Learning via Lazy Algorithms
Hilal Asi, Tomer Koren, Daogao Liu +1
We study the problem of private online learning, specifically, online prediction from experts (OPE) and online convex optimization (OCO). We propose a new transformation that trans…
Private Gradient Descent for Linear Regression: Tighter Error Bounds and Instance-Specific Uncertainty Estimation
Gavin Brown, Krishnamurthy Dvijotham, Georgina Evans +3
We provide an improved analysis of standard differentially private gradient descent for linear regression under the squared error loss. Under modest assumptions on the input, we ch…
Fast Rerandomization via the BRAIN
Jiuyao Lu, Daogao Liu, Zhanran Lin +1
Randomized experiments are a crucial tool for causal inference in many different fields. Rerandomization addresses any covariate imbalance in such experiments by resampling treatme…
User-level Differentially Private Stochastic Convex Optimization: Efficient Algorithms with Optimal Rates
Hilal Asi, Daogao Liu
We study differentially private stochastic convex optimization (DP-SCO) under user-level privacy, where each user may hold multiple data items. Existing work for user-level DP-SCO…