When Do Fewer Coordinates Suffice in DP-SGD?
For practitioners of differentially private deep learning, this work provides a method to reduce the cost of DP-SGD when the model has a sparse gradient structure, though gains are conditional on informative warm-up scores.
DP-SGD noise scales with parameter dimension d. TP-TopK reduces this to active dimension k via a private warm-up phase that identifies a sparse coordinate support, with experiments showing retained gradient energy and improved utility when active dimension is small.
Differentially private stochastic gradient descent (DP-SGD) injects noise into every updated coordinate, making the injected noise energy scale with the ambient parameter dimension \(d\). We ask when private training can update fewer coordinates without losing the signal needed for optimization. We propose \textsc{TP-TopK} (Two-Phase TopK DP-SGD), a two-phase method for coordinate-sparse private training without public data, in which a private warm-up phase identifies a coordinate support used to guide the main training phase. We give a criterion characterizing when coordinate restriction can be beneficial, show via a nonconvex stationarity bound that under this condition the relevant noise term scales with the active dimension \(k\) rather than the full parameter dimension \(d\), and provide a lower bound on the reliability of warm-up-based coordinate ranking. Experiments on MNIST, FMNIST, and CIFAR-10 show that learned coordinate supports can retain more gradient energy than size-matched random supports, with the largest gains when the active dimension is small and warm-up scores are informative.