Seminar • Algorithms and Complexity • Cactus Mechanisms: Optimal Differential Privacy Mechanisms in the Large-composition RegimeExport this event to calendar

Wednesday, April 20, 2022 — 1:00 PM EDT

Please note: This seminar will be given online.

Shahab Asoodeh, Assistant Professor
Department of Computing and Software, McMaster University

Most differential privacy mechanisms are applied (i.e., composed) numerous times on sensitive data. In this talk, I will discuss the design of “optimal” mechanisms in the limit of a large number of compositions. In this regime, the best mechanism in terms of the privacy-utility trade-off is shown to be the one that minimizes the Kullback-Leibler divergence between the conditional output distributions of the mechanism given two different inputs, subject to some utility constraints. Unfortunately, this optimization problem is infinite-dimensional and cannot be solved analytically. Nevertheless, I discuss a quantization technique to approximate the optimizer and derive a near-optimal mechanism that we call “cactus mechanism” due to its shape. Surprisingly, the Gaussian mechanism is strictly sub-optimal compared to this new mechanism.

In the second part of the talk, I focus on the regime where the sensitivities of all queries are small. In this regime, I show that the optimal mechanism is additive whose noise pdf is fully characterized by the ground-state eigenfunction of the Schrödinger operator. This leads to a family of optimal mechanisms for queries with small sensitivities, dubbed as the Schrödinger mechanisms, depending on the utility measures. Measuring utility in terms of l1-cost function, this result leads to a new optimal mechanism that is based on the Airy function, thus we call it “Airy mechanism”. And measuring utility in terms of quadratic function, this result shows the optimality of Gaussian mechanisms (only for small sensitivity regime).

This is a work in progress with Flavio Calmon and Wael Alghamdi (Harvard), and Oliver Kosut and Lalitha Sankar (ASU).


To join this seminar on Zoom, please go to https://uwaterloo.zoom.us/j/95394821239?pwd=THZUM0dWTE1CcVVGcUE3Si9uSU9MQT09.

Location 
Online seminar
200 University Avenue West

Waterloo, ON N2L 3G1
Canada
Event tags 

S M T W T F S
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
  1. 2022 (123)
    1. July (5)
    2. June (17)
    3. May (20)
    4. April (24)
    5. March (22)
    6. February (16)
    7. January (19)
  2. 2021 (210)
    1. December (21)
    2. November (13)
    3. October (12)
    4. September (21)
    5. August (20)
    6. July (17)
    7. June (11)
    8. May (16)
    9. April (27)
    10. March (20)
    11. February (13)
    12. January (19)
  3. 2020 (217)
  4. 2019 (255)
  5. 2018 (217)
  6. 2017 (36)
  7. 2016 (21)
  8. 2015 (36)
  9. 2014 (33)
  10. 2013 (23)
  11. 2012 (4)
  12. 2011 (1)
  13. 2010 (1)
  14. 2009 (1)
  15. 2008 (1)