Seminars

View all Seminars  |  Download ICal for this event

Private Convex Optimization via Exponential Mechanism

Series: Bangalore Theory Seminars

Speaker: Sivakanth Gopi MSR, Redmond

Date/Time: Mar 16 10:00:00

Location: CSA Seminar Hall (Room No. 254, First Floor)

Abstract:
We study differentially private optimization of (non-smooth) convex functions F(x)=E_i[f_i(x)]. The classic exponential mechanism minimizes F(x) by sampling from pi(x) ~ exp(-kF(x)), but achieves a suboptimal privacy vs utility tradeoff. We show that modifying the exponential mechanism by adding an ell_2^2 regularizer to F(x) and sampling from pi(x) ~ exp(-k(F(x)+mu ||x||_2^2/2)) recovers both optimal empirical risk and population loss under (eps,delta)-DP. We also give an algorithm to efficiently sample from the exponential mechanism using optimal number of oracle queries to f_i(x).
<br>
We prove that the regularized exponential mechanism satisfies Gaussian Differential Privacy; our privacy bound is optimal (with tight constants), as it includes the analysis of Gaussian mechanism as a special case. The privacy proof uses isoperimetric inequality for strongly log-concave measures.
<br>
Joint work with Yin Tat Lee and Daogao Liu. The link to the paper is at Link
<br>
<br>
Speaker Website: Link
<br>
<br>
Microsoft teams link:
<br>
Link
<br>
<br>
We are grateful to the Kirani family for generously supporting the theory seminar series
<br>
<br>
Hosts: Rahul Madhavan, Rameesh Paul, Aditya Subramanian and Aditya Abhay Lonkar