The Large Margin Mechanism for Differentially Private Maximization

Preprint English OPEN
Chaudhuri, Kamalika; Hsu, Daniel; Song, Shuang;
  • Subject: Mathematics - Statistics Theory | Computer Science - Data Structures and Algorithms | Computer Science - Information Theory | Computer Science - Learning

A basic problem in the design of privacy-preserving algorithms is the private maximization problem: the goal is to pick an item from a universe that (approximately) maximizes a data-dependent function, all under the constraint of differential privacy. This problem has b... View more
  • References (33)
    33 references, page 1 of 4

    [1] Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization, revisited. arXiv:1405.7085, 2014.

    [3] Amos Beimel, Kobbi Nissim, and Uri Stemmer. Private learning and sanitization: Pure vs. approximate differential privacy. In RANDOM, 2013.

    [4] Amos Beimel, Kobbi Nissim, and Uri Stemmer. Characterizing the sample complexity of private learners. In ITCS, pages 97-110, 2013.

    [5] Raghav Bhaskar, Srivatsan Laxman, Adam Smith, and Abhradeep Thakurta. Discovering frequent patterns in sensitive data. In KDD, 2010.

    [6] A. Blum, C. Dwork, F. McSherry, and K. Nissim. Practical privacy: the SuLQ framework. In PODS, 2005.

    [7] Avrim Blum, Katrina Ligett, and Aaron Roth. A learning theory approach to noninteractive database privacy. Journal of the ACM, 60(2):12, 2013.

    [8] Luca Bonomi and Li Xiong. Mining frequent patterns with differential privacy. Proceedings of the VLDB Endowment, 6(12):1422-1427, 2013.

    [9] Mark Bun, Jonathan Ullman, and Salil Vadhan. Fingerprinting codes and the price of approximate differential privacy. In STOC, 2014.

    [10] Kamalika Chaudhuri and Daniel Hsu. Sample complexity bounds for differentially private learning. In COLT, 2011.

    [11] Kamalika Chaudhuri and Daniel Hsu. Convergence rates for differentially private statistical estimation. In ICML, 2012.

  • Related Organizations (8)
  • Metrics
Share - Bookmark