The Price of Locality in Label Privacy: Optimal Rates for Classification and Regression

We study classification and regression tasks under label differential privacy (label-DP), a setting where only the labels are considered sensitive information. We quantify the "price of locality" by revealing fundamental statistical gaps between local and central privacy models. For classification, we establish a strict separation in accuracy. Specifically, we prove that the minimax excess risk in the local model is lower bounded by $\Omega(\frac{1}{\epsilon}\sqrt{\text{VC}(\mathcal{H})/n})$ for classification on size-$n$ dataset, a fundamental limitation that holds even under relaxed approximate $(\epsilon, \delta)$-local DP. Overcoming this barrier, we propose the first *efficient* central-model algorithm that operates under the stricter pure $\epsilon$-DP, yet achieves a significantly improved upper bound of $\tilde{O}(\sqrt{\text{VC}(\mathcal{H})/(\epsilon n)})$. For linear regression, we show that local randomizers or naive central-DP approach algorithms are statistically inefficient. Instead, we turn to the Matrix Mechanism and use an encoder-decoder framework built on ridge regression, which projects the data into a spherical latent space before injecting noise. This structural design effectively isolates and exponentially suppresses the severe noise inflation typically caused by ill-conditioned feature covariance matrices in full-DP (Cai et al., The Annals of Statistics, 49(5)), achieving an optimal privacy penalty of $\tilde{O}({d^2}/({n^2\epsilon^2}))$ where $d$ is the feature dimension.