Efficiently Convolving DistributionsSpeaker: Daniel
Title: Efficiently Convolving Distributions
Date: 03 Dec 2021 11:30-13:00 EST
Location: SEC Level 3 NW Terrace
Abstract: Abstracting privacy losses as random variables provides a clean and mathematically convenient approach to quantifying provable guarantees of information loss. Optimally composing privacy loss (random variables) is a hard problem. In particular, computing the exact privacy loss incurred by a k-fold composition is #P-complete. However, one can still approximate privacy loss contracts to any desired accuracy (in time that is roughly inversely proportional to your accuracy parameter). In this talk, I will discuss several approaches to approximately composing privacy curves/losses and focus on one particular view that is gaining traction: using the Fast Fourier Transform (FFT) to convolve distributions efficiently. If time permits, I might discuss the notion of a coupling approximation.