Skip to Main Content
HBS Home
  • About
  • Academic Programs
  • Alumni
  • Faculty & Research
  • Baker Library
  • Giving
  • Harvard Business Review
  • Initiatives
  • News
  • Recruit
  • Map / Directions
Faculty & Research
  • Faculty
  • Research
  • Featured Topics
  • Academic Units
  • …→
  • Harvard Business School→
  • Faculty & Research→
Publications
Publications
  • Article
  • Proceedings of the IEEE Annual Symposium on Foundations of Computer Science (FOCS)

How to Use Heuristics for Differential Privacy

By: Seth Neel, Aaron Leon Roth and Zhiwei Steven Wu
  • Format:Electronic
ShareBar

Abstract

We develop theory for using heuristics to solve computationally hard problems in differential privacy. Heuristic approaches have enjoyed tremendous success in machine learning, for which performance can be empirically evaluated. However, privacy guarantees cannot be evaluated empirically, and must be proven--without making heuristic assumptions. We show that learning problems over broad classes of functions can be solved privately and efficiently, assuming the existence of a non-private oracle for solving the same problem. Our first algorithm yields a privacy guarantee that is contingent on the correctness of the oracle. We then give a reduction which applies to a class of heuristics which we call certifiable, which allows us to convert oracle-dependent privacy guarantees to worst-case privacy guarantee that hold even when the heuristic standing in for the oracle might fail in adversarial ways. Finally, we consider a broad class of functions that includes most classes of simple boolean functions studied in the PAC learning literature, including conjunctions, disjunctions, parities, and discrete halfspaces. We show that there is an efficient algorithm for privately constructing synthetic data for any such class, given a non-private learning oracle. This in particular gives the first oracle-efficient algorithm for privately generating synthetic data for contingency tables. The most intriguing question left open by our work is whether or not every problem that can be solved differentially privately can be privately solved with an oracle-efficient algorithm. While we do not resolve this, we give a barrier result that suggests that any generic oracle-efficient reduction must fall outside of a natural class of algorithms (which includes the algorithms given in this paper).

Citation

Neel, Seth, Aaron Leon Roth, and Zhiwei Steven Wu. "How to Use Heuristics for Differential Privacy." Proceedings of the IEEE Annual Symposium on Foundations of Computer Science (FOCS) 60th (2019).
  • Read Now

About The Author

Seth Neel

Technology and Operations Management
→More Publications

More from the Authors

    • 2023
    • Proceedings of the Conference on Empirical Methods in Natural Language Processing

    MoPe: Model Perturbation-based Privacy Attacks on Language Models

    By: Marvin Li, Jason Wang, Jeffrey Wang and Seth Neel
    • 2023
    • Faculty Research

    Black-box Training Data Identification in GANs via Detector Networks

    By: Lukman Olagoke, Salil Vadhan and Seth Neel
    • 2023
    • Faculty Research

    In-Context Unlearning: Language Models as Few Shot Unlearners

    By: Martin Pawelczyk, Seth Neel and Himabindu Lakkaraju
More from the Authors
  • MoPe: Model Perturbation-based Privacy Attacks on Language Models By: Marvin Li, Jason Wang, Jeffrey Wang and Seth Neel
  • Black-box Training Data Identification in GANs via Detector Networks By: Lukman Olagoke, Salil Vadhan and Seth Neel
  • In-Context Unlearning: Language Models as Few Shot Unlearners By: Martin Pawelczyk, Seth Neel and Himabindu Lakkaraju
ǁ
Campus Map
Harvard Business School
Soldiers Field
Boston, MA 02163
→Map & Directions
→More Contact Information
  • Make a Gift
  • Site Map
  • Jobs
  • Harvard University
  • Trademarks
  • Policies
  • Accessibility
  • Digital Accessibility
Copyright © President & Fellows of Harvard College.