Timezone: »
Poster
On Differentially Private Stochastic Convex Optimization with Heavytailed Data
Di Wang · Hanshen Xiao · Srinivas Devadas · Jinhui Xu
Thu Jul 16 07:00 AM  07:45 AM & Thu Jul 16 07:00 PM  07:45 PM (PDT) @
In this paper, we consider the problem of designing
Differentially Private (DP) algorithms for Stochastic Convex Optimization (SCO) on heavytailed data. The irregularity of such data violates some key
assumptions used in almost all existing DPSCO and DPERM methods, resulting in failure to provide the DP guarantees. To better understand this type of challenges, we provide in this paper a comprehensive study of DPSCO under various settings. First, we consider the case where the loss function is strongly convex and smooth. For this case, we propose a method based on the sampleandaggregate framework, which has an excess population risk of
$\tilde{O}(\frac{d^3}{n\epsilon^4})$ (after omitting other factors), where $n$ is the sample size and $d$ is the dimensionality of the data. Then, we show that with some additional assumptions on the loss functions, it is possible to reduce the
\textit{expected} excess population risk to $\tilde{O}(\frac{ d^2}{ n\epsilon^2 })$. To lift these additional conditions, we also
provide a gradient smoothing and trimming based scheme to achieve excess population risks of
$\tilde{O}(\frac{ d^2}{n\epsilon^2})$ and $\tilde{O}(\frac{d^\frac{2}{3}}{(n\epsilon^2)^\frac{1}{3}})$ for strongly convex and general convex loss functions, respectively, \textit{with high probability}.
Experiments on both synthetic and realworld datasets suggest that our algorithms can effectively deal with the challenges caused by data irregularity.
Author Information
Di Wang (State University of New York at Buffalo)
Hanshen Xiao (MIT CSAIL)
Srinivas Devadas (MIT)
Jinhui Xu (SUNY Buffalo)
More from the Same Authors

2019 Poster: Differentially Private Empirical Risk Minimization with Nonconvex Loss Functions »
Di Wang · Changyou Chen · Jinhui Xu 
2019 Poster: On Sparse Linear Regression in the Local Differential Privacy Model »
Di Wang · Jinhui Xu 
2019 Oral: Differentially Private Empirical Risk Minimization with Nonconvex Loss Functions »
Di Wang · Changyou Chen · Jinhui Xu 
2019 Oral: On Sparse Linear Regression in the Local Differential Privacy Model »
Di Wang · Jinhui Xu