We consider 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 online queries as they arrive. Our primary contribution is a new differentially private multiplicative weights mechanism for answering a large number of counting queries that arrive online and may be adaptively chosen. This mechanism yields two main results.

First, it is the first {em efficient} mechanism for answering large numbers of online queries with worst-case accuracy guarantees (accuracy on every input database). The error is emph{optimal} in its dependence on the number of participants and depends only logarithmically on the number of queries being answered. The running time is nearly {em linear} in the size of the data universe. Previous mechanisms for answering many counting queries all run in super cubic time, even for the (easier) offline setting where all queries are known in advance.

Second, while continuing to guarantee worst-case privacy for {em any} input database, we obtain exponential improvements in running time for a broad class of databases. When the input database is drawn from a {em smooth} distribution that does not place too much weight on any single data item, accuracy remains as above and the running time becomes {em poly-logarithmic} in the data universe size. To the best of our knowledge, this is the first example of a poly-logarithmic time mechanism for answering large numbers of general queries (indeed, for worst-case accuracy guarantees, there are known hardness results). Our main technical contributions are a new application of multiplicative weights techniques to the differential privacy setting, a new privacy analysis for multiplicative weights algorithms, and a general technique for reducing data dimensionality for databases drawn from smooth distributions.