Timezone: »

 
Poster
Empirical Risk Minimization in Non-interactive Local Differential Privacy Revisited
Di Wang · Marco Gaboardi · Jinhui Xu

Wed Dec 05 02:00 PM -- 04:00 PM (PST) @ Room 210 #94
In this paper, we revisit the Empirical Risk Minimization problem in the non-interactive local model of differential privacy. In the case of constant or low dimensions ($p\ll n$), we first show that if the loss function is $(\infty, T)$-smooth, we can avoid a dependence of the sample complexity, to achieve error $\alpha$, on the exponential of the dimensionality $p$ with base $1/\alpha$ ({\em i.e.,} $\alpha^{-p}$), which answers a question in \cite{smith2017interaction}. Our approach is based on polynomial approximation. Then, we propose player-efficient algorithms with $1$-bit communication complexity and $O(1)$ computation cost for each player. The error bound is asymptotically the same as the original one. With some additional assumptions, we also give an efficient algorithm for the server. In the case of high dimensions ($n\ll p$), we show that if the loss function is a convex generalized linear function, the error can be bounded by using the Gaussian width of the constrained set, instead of $p$, which improves the one in \cite{smith2017interaction}.

Author Information

Di Wang (State University of New York at Buffalo)
Marco Gaboardi (Univeristy at Buffalo)
Jinhui Xu (SUNY at Buffalo)

More from the Same Authors

  • 2020 Poster: Learning Manifold Implicitly via Explicit Heat-Kernel Learning »
    Yufan Zhou · Changyou Chen · Jinhui Xu
  • 2019 : Poster Session »
    Clement Canonne · Kwang-Sung Jun · Seth Neel · Di Wang · Giuseppe Vietri · Liwei Song · Jonathan Lebensold · Huanyu Zhang · Lovedeep Gondara · Ang Li · FatemehSadat Mireshghallah · Jinshuo Dong · Anand D Sarwate · Antti Koskela · Joonas Jälkö · Matt Kusner · Dingfan Chen · Mi Jung Park · Ashwin Machanavajjhala · Jayashree Kalpathy-Cramer · · Vitaly Feldman · Andrew Tomkins · Hai Phan · Hossein Esfandiari · Mimansa Jaiswal · Mrinank Sharma · Jeff Druce · Casey Meehan · Zhengli Zhao · Hsiang Hsu · Davis Railsback · Abraham Flaxman · · Julius Adebayo · Aleksandra Korolova · Jiaming Xu · Naoise Holohan · Samyadeep Basu · Matthew Joseph · My Thai · Xiaoqian Yang · Ellen Vitercik · Michael Hutchinson · Chenghong Wang · Gregory Yauney · Yuchao Tao · Chao Jin · Si Kai Lee · Audra McMillan · Rauf Izmailov · Jiayi Guo · Siddharth Swaroop · Tribhuvanesh Orekondy · Hadi Esmaeilzadeh · Kevin Procopio · Alkis Polyzotis · Jafar Mohammadi · Nitin Agrawal
  • 2019 Poster: Privacy Amplification by Mixing and Diffusion Mechanisms »
    Borja Balle · Gilles Barthe · Marco Gaboardi · Joseph Geumlek
  • 2019 Poster: Facility Location Problem in Differential Privacy Model Revisited »
    Yunus Esencayi · Marco Gaboardi · Shi Li · Di Wang
  • 2018 : Poster Session »
    Phillipp Schoppmann · Patrick Yu · Valerie Chen · Travis Dick · Marc Joye · Ningshan Zhang · Frederik Harder · Olli Saarikivi · Théo Ryffel · Yunhui Long · Théo JOURDAN · Di Wang · Antonio Marcedone · Negev Shekel Nosatzki · Yatharth A Dubey · Antti Koskela · Peter Bloem · Aleksandra Korolova · Martin Bertran · Hao Chen · Galen Andrew · Natalia Martinez · Janardhan Kulkarni · Jonathan Passerat-Palmbach · Guillermo Sapiro · Amrita Roy Chowdhury
  • 2018 Poster: Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences »
    Borja Balle · Gilles Barthe · Marco Gaboardi
  • 2017 Poster: Differentially Private Empirical Risk Minimization Revisited: Faster and More General »
    Di Wang · Minwei Ye · Jinhui Xu
  • 2013 Poster: k-Prototype Learning for 3D Rigid Structures »
    Hu Ding · Ronald Berezney · Jinhui Xu