Algorithmic Improvements for Differentially Private Learning

Abstract:

Neural networks power a wide range of applications in healthcare, social media, and beyond. However, training them on sensitive data without adequate privacy safeguards can lead to the exposure of private information. Differential privacy (DP) offers a rigorous framework that enables learning algorithms to produce models that preserve individual privacy while maintaining high utility. Despite these advantages, integrating DP into neural network training remains challenging due to diverse data structures (e.g., Euclidean and graph data) and complex architectures (e.g., convolutional and graph neural networks). These differences necessitate specialized algorithmic improvements to balance privacy and utility effectively. In this thesis, we develop three novel differentially private learning algorithms to address these challenges.

First, we propose DPIS, a novel algorithm for differentially private learning on Euclidean data based on importance sampling (IS). By integrating IS into the differentially private stochastic gradient descent (DP-SGD) framework, DPIS reduces sampling variance and the noise required for privacy, thereby improving model accuracy. While IS has been extensively studied in non-private settings, incorporating it into private SGD is non-trivial. DPIS addresses this challenge through novel mechanism design, fine-grained privacy analysis, efficiency improvements, and adaptive gradient clipping optimization.

Second, we introduce GCON, a new algorithm for graph learning with edge-level differential privacy. Unlike existing methods that modify adjacency matrices or intermediate features, GCON preserves the integrity of graph convolution operations by applying objective perturbation. Our analysis derives tight, closed-form sensitivity bounds that quantify how edge modifications affect model parameters while ensuring rigorous privacy guarantees.

Third, we propose SaGD, a rigorous node-level DP framework for graph learning. It comprises two stages: (i) weighted message propagation over the original graph to control sensitivity, yielding a tight closed-form bound; and (ii) neural network training on perturbed gradients with analytical sensitivity analysis. This design preserves the full graph structure, ensures rigorous privacy with minimal noise, and maintains high efficiency.