Speaker: Justin Whitehouse

Abstract: Graceful composition is one of the most important properties of differential privacy. Well-known advanced composition theorems allow one to query a private database approximately quadratically more times than naive, basic privacy composition would permit. However, there is a major caveat — although the algorithms being composed can be selected adaptively, existing results require the privacy parameters of all algorithms to be fixed before interacting with the private database. A recent line of work started by Rogers et al. has studied fully-adaptive composition, wherein both algorithms and their privacy parameters can be selected adaptively. The authors introduce two probabilistic objects to measure privacy in adaptive composition: privacy filters, objects providing differential privacy guarantees for composed interactions, and privacy odometers, time-uniform bounds on privacy loss. However, there are substantial gaps between the composition results proved about these objects and the aforementioned advanced composition theorems. First, existing filters place stronger assumptions on the algorithms being composed. Second, the odometers and filters often suffer from large constants, making them impractical. This work greatly improves the state-of-the-art for fully-adaptive composition. In particular, we construct privacy filters that exactly match the tightness of advanced composition, including constants, despite allowing for adaptively chosen privacy parameters. In addition, we construct several general families of privacy odometers that have improved empirical tightness. These odometers can be optimized to match the tightness of advanced composition exactly at an arbitrary, preselected point in time, or at all points in time simultaneously, up to a small, doubly-logarithmic factor. We obtain our results by leveraging recent advances by Howard et al. on time-uniform martingale inequalities. In sum, our results show that fully-adaptive privacy is obtainable at no loss, giving practitioners added flexibility when working with sensitive data. https://arxiv.org/abs/2203.05481