Differential Privacy for Sequential Algorithms
  We study the differential privacy of sequential statistical inference and
learning algorithms that are characterized by random termination time. Using
the two examples: sequential probability ratio test and sequential empirical
risk minimization, we show that the number of steps such algorithms execute
before termination can jeopardize the differential privacy of the input data in
a similar fashion as their outputs, and it is impossible to use the usual
Laplace mechanism to achieve standard differentially private in these examples.
To remedy this, we propose a notion of weak differential privacy and
demonstrate its equivalence to the standard case for large i.i.d. samples. We
show that using the Laplace mechanism, weak differential privacy can be
achieved for both the sequential probability ratio test and the sequential
empirical risk minimization with proper performance guarantees. Finally, we
provide preliminary experimental results on the Breast Cancer Wisconsin
(Diagnostic) and Landsat Satellite Data Sets from the UCI repository.
