Timezone: »

 
Spotlight
Private optimization in the interpolation regime: faster rates and hardness results
Hilal Asi · Karan Chadha · Gary Cheng · John Duchi

Wed Jul 20 02:45 PM -- 02:50 PM (PDT) @ Room 307
in SA: Privacy-preserving Statistics and Machine Learning »
In non-private stochastic convex optimization, stochastic gradient methods converge much faster on interpolation problems---namely, problems where there exists a solution that simultaneously minimizes all of the sample losses---than on non-interpolating ones;similar improvements are not known in the private setting. In this paper, we investigate differentially private stochastic optimization in the interpolation regime. First, we show that without additional assumptions, interpolation problems do not exhibit an improved convergence rates with differential privacy. However, when the functions exhibit quadratic growth around the optimum, we show (near) exponential improvements in the private sample complexity. In particular, we propose an adaptive algorithm that improves the sample complexity to achieve expected error $\alpha$ from $\frac{d}{\diffp \sqrt{\alpha}}$ to $\frac{1}{\alpha^\rho} + \frac{d}{\diffp} \log\paren{\frac{1}{\alpha}}$ for any fixed $\rho >0$, while retaining the standard minimax-optimal sample complexity for non-interpolation problems. We prove a lower bound that shows the dimension-dependent term in the expression above is tight. Furthermore, we provide a superefficiency result which demonstrates the necessity of the polynomial term for adaptive algorithms: any algorithm that has a polylogarithmic sample complexity for interpolation problems cannot achieve the minimax-optimal rates for the family of non-interpolation problems.
Keywords: OPT: Convex · OPT: Stochastic · T: Optimization · SA: Privacy-preserving Statistics and Machine Learning

Author Information

Hilal Asi (Stanford University)
Karan Chadha (Stanford University)
Gary Cheng (Stanford University)
John Duchi (Stanford University)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors