2025 Theses Doctoral

Differentially Private Algorithmic Design: Private Bandits, Counting and Histograms

Ou, Tingting

As concerns around data privacy continue to grow, designing differentially private (DP) algorithms has become a central topic of interest, particularly for statistical and machine learning methods used in practice. This thesis contributes to this line of work by presenting new results in private algorithm design and analysis for multi-armed bandits, counting, and histogram estimation.

The thesis begins by showing that the classical Thompson Sampling algorithm with a Gaussian prior for multi-armed bandits is inherently differentially private without any modification. We further propose simple modifications that yield improved privacy guarantees, and analyze how these adjustments affect regret. Next, we study distinct count estimation under differential privacy in the turnstile streaming model. We present the first differentially private algorithms using sublinear space in the stream length T. Our method achieves an error and space complexity of O(T¹/³), significantly improving over prior linear-space approaches.

Lastly, we address locally private succinct histogram estimation in the federated setting. Building on the sample-and-threshold paradigm which is only centrally private, we develop a locally private algorithm that incorporates an additional local randomization step. This new method achieves stronger privacy guarantees without significantly compromising the accuracy.