Differentially Private Continual Release with Relative Error

This work investigates several fundamental tasks, including $\mathsf{MaxSum}$, $\mathsf{MinSum}$, $\mathsf{MaxSelect}$, and $\mathsf{MinSelect}$, in the continual release model under differential privacy. Previous research has demonstrated that any algorithm for these tasks must admit a large purely additive error. We show that the error can be substantially reduced if a relative error term is allowed, provided that the input stream is generated non-adaptively. However, when input data records can be selected adaptively, we prove that a large error is inevitable for the task of selecting an attribute with a small cumulative sum, whereas small error bounds remain achievable for other tasks. This reveals a significant separation between non-adaptive and adaptive streams. We also complement our algorithms with nearly matching lower bounds.

Many organizations, like hospitals or statistics agencies, want to regularly share updates based on sensitive data—such as disease rates or income trends—without exposing any individual’s private information. A major challenge is that protecting privacy while releasing a continuous stream of data inevitably leads to large errors in the published results. Our work overcomes this fundamental limitation by shifting focus from absolute error to relative error, which is often more meaningful for small values. We developed new algorithms that achieve much smaller error than previous methods. Moreover, we prove that no algorithm can do better in a broad range of settings, by establishing a matching theoretical lower bound. This shows our approach is optimal, making private data sharing far more practical and reliable for real-world use.