6 papers · 1 filter
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…