`

Timezone: »

 
Poster
Accuracy First: Selecting a Differential Privacy Level for Accuracy Constrained ERM
Katrina Ligett · Seth Neel · Aaron Roth · Bo Waggoner · Steven Wu

Wed Dec 06 06:30 PM -- 10:30 PM (PST) @ Pacific Ballroom #67 #None

Traditional approaches to differential privacy assume a fixed privacy requirement ε for a computation, and attempt to maximize the accuracy of the computation subject to the privacy constraint. As differential privacy is increasingly deployed in practical settings, it may often be that there is instead a fixed accuracy requirement for a given computation and the data analyst would like to maximize the privacy of the computation subject to the accuracy constraint. This raises the question of how to find and run a maximally private empirical risk minimizer subject to a given accuracy requirement. We propose a general “noise reduction” framework that can apply to a variety of private empirical risk minimization (ERM) algorithms, using them to “search” the space of privacy levels to find the empirically strongest one that meets the accuracy constraint, and incurring only logarithmic overhead in the number of privacy levels searched. The privacy analysis of our algorithm leads naturally to a version of differential privacy where the privacy parameters are dependent on the data, which we term ex-post privacy, and which is related to the recently introduced notion of privacy odometers. We also give an ex-post privacy analysis of the classical AboveThreshold privacy tool, modifying it to allow for queries chosen depending on the database. Finally, we apply our approach to two common objective functions, regularized linear and logistic regression, and empirically compare our noise reduction methods to (i) inverting the theoretical utility guarantees of standard private ERM algorithms and (ii) a stronger empirical baseline based on binary search.

Author Information

Katrina Ligett (Hebrew University)
Seth Neel (University of Pennsylvania)

PhD student in statistics studying fairness and privacy in learning. Advised by Aaron Roth and Michael Kearns.

Aaron Roth (University of Pennsylvania)
Bo Waggoner
Steven Wu (Microsoft)

More from the Same Authors

  • 2021 : Efficient Competitions and Online Learning with Strategic Forecasters »
    Anish Thilagar · Rafael Frongillo · Bo Waggoner · Robert Gomez
  • 2021 : Efficient Competitions and Online Learning with Strategic Forecasters »
    Anish Thilagar · Rafael Frongillo · Bo Waggoner · Robert Gomez
  • 2021 : Panel »
    Oluwaseyi Feyisetan · Helen Nissenbaum · Aaron Roth · Christine Task
  • 2021 : Invited talk: Aaron Roth (UPenn / Amazon): Machine Unlearning. »
    Aaron Roth
  • 2021 Poster: Adaptive Machine Unlearning »
    Varun Gupta · Christopher Jung · Seth Neel · Aaron Roth · Saeed Sharifi-Malvajerdi · Chris Waites
  • 2021 Poster: Surrogate Regret Bounds for Polyhedral Losses »
    Rafael Frongillo · Bo Waggoner
  • 2021 Poster: Unifying lower bounds on prediction dimension of convex surrogates »
    Jessica Finocchiaro · Rafael Frongillo · Bo Waggoner
  • 2019 : Aaron Roth, "Average Individual Fairness" »
    Aaron Roth
  • 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 Session »
    Nathalie Baracaldo Angel · Seth Neel · Tuyen Le · Dan Philps · Suheng Tao · Sotirios Chatzis · Toyo Suzumura · Wei Wang · WENHANG BAO · Solon Barocas · Manish Raghavan · Samuel Maina · Reginald Bryant · Kush Varshney · Skyler D. Speakman · Navdeep Gill · Nicholas Schmidt · Kevin Compher · Naveen Sundar Govindarajulu · Vivek Sharma · Praneeth Vepakomma · Tristan Swedish · Jayashree Kalpathy-Cramer · Ramesh Raskar · Shihao Zheng · Mykola Pechenizkiy · Marco Schreyer · Li Ling · Chirag Nagpal · Robert Tillman · Manuela Veloso · Hanjie Chen · Xintong Wang · Michael Wellman · Matthew van Adelsberg · Ben Wood · Hans Buehler · Mahmoud Mahfouz · Antonios Alexos · Megan Shearer · Antigoni Polychroniadou · Lucia Larise Stavarache · Dmitry Efimov · Johnston P Hall · Yukun Zhang · Emily Diana · Sumitra Ganesh · Vineeth Ravi · · Swetasudha Panda · Xavier Renard · Matthew Jagielski · Yonadav Shavit · Joshua Williams · Haoran Wei · Shuang (Sophie) Zhai · Xinyi Li · Hongda Shen · Daiki Matsunaga · Jaesik Choi · Alexis Laignelet · Batuhan Guler · Jacobo Roa Vicens · Ajit Desai · Jonathan Aigrain · Robert Samoilescu
  • 2019 : Invited talk #3 »
    Aaron Roth
  • 2016 Workshop: Adaptive Data Analysis »
    Vitaly Feldman · Aaditya Ramdas · Aaron Roth · Adam Smith
  • 2015 Poster: Generalization in Adaptive Data Analysis and Holdout Reuse »
    Cynthia Dwork · Vitaly Feldman · Moritz Hardt · Toni Pitassi · Omer Reingold · Aaron Roth
  • 2014 Tutorial: Differential Privacy and Learning: The Tools, The Results, and The Frontier »
    Katrina Ligett
  • 2012 Poster: A Simple and Practical Algorithm for Differentially Private Data Release »
    Moritz Hardt · Katrina Ligett · Frank McSherry