We consider privacy-preserving statistical data analysis with online queries. In this setting a trusted curator maintains a database of sensitive information about individual participants, and releases privacy-preserving answers to queries as they arrive online. Our primary contribution is a new differentially private multiplicative weights mechanism for answering a large number of queries that arrive online and may be adaptively chosen. Our mechanism is the first to achieve worst-case accuracy guarantees (accuracy on every input database) for a large number of online queries together with a runtime that is polynomial in the data universe. The error is optimal in its dependence on the size of the database and depends only logarithmically on the number of queries being answered.
Our main technical contributions are a new application of multiplicative weights techniques to the differential privacy setting, and a new privacy analysis for multiplicative weights algorithms.
Joint work with Guy Rothblum.