Master’s Thesis Presentation • Algorithms and Complexity • Efficient Mean Estimation via a Sum-of-Squares Exponential MechanismExport this event to calendar

Friday, December 9, 2022 — 11:00 AM to 12:00 PM EST

Please note: This master’s thesis presentation will take place online.

Mahbod Majid, Master’s candidate
David R. Cheriton School of Computer Science

Supervisor: Professor Gautam Kamath

We are increasingly seeing machine learning algorithms being applied to privacy sensitive data, making it increasingly more important to devise algorithms that preserve privacy. Yet, even the most fundamental high dimensional statistical estimation tasks were not well understood under differential privacy. Namely, no efficient algorithms were known for mean estimation with optimal number of samples under pure differential privacy.

We introduce a novel approach to design efficient private algorithm for statistical estimation tasks based on the Sum of Squares hierarchy and the exponential mechanism. The Sum of Squares hierarchy is a convex programming method that has been successfully used to design efficient algorithms in robust statistics. The exponential mechanism has been widely used in differential privacy to design information theoretically optimal algorithms, which are often inefficient. We use these two approaches combined together to obtain efficient and information theoretically optimal algorithms. We apply this approach to mean estimation and learning Gaussian distributions and demonstrate that they are optimal. We demonstrate that this approach can be applied to many other problems captured by the Sum of Squares method, through a meta-theorem. Moreover, our algorithms draw strong connections between robustness and privacy.

We also provide information theoretical lower bounds to demonstrate that our approaches are statistically optimal. Technically we use packing lower bounds, however the novelty of our lower bounds is in capturing the high probability setting.


To join this master’s thesis presentation on Zoom, please go to https://uwaterloo.zoom.us/j/93407334364.

Location 
Online master’s thesis presentation
200 University Avenue West

Waterloo, ON N2L 3G1
Canada
Event tags 

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