Private Learning with Public Feature Conditioning

We study differentially private (DP) regression in settings where each data sample includes public, non-sensitive features—common in applications like recommendation or advertising systems. While such label DP or DP with semi-sensitive features settings have been primarily explored in the context of classification, effective approaches for regression remain underexplored. We introduce $\textsf{Cond-DP}$, a conditioned variant of $\textsf{DPSGD}$ that leverages the structure of public feature matrices to improve optimization under privacy constraints. Motivated by the observation that these public features often exhibit rapidly decaying spectra, $\textsf{Cond-DP}$ incorporates a data-driven conditioning matrix to reshape the optimization landscape and accelerate convergence. We provide convergence guarantees for convex, strongly convex and non-convex settings, and recover standard $\textsf{DPSGD}$ as a special case when the conditioning matrix is the identity. We show how to construct an effective conditioning matrix for $\textsf{Cond-DP}$ directly from public features, enabling faster convergence than $\textsf{DPSGD}$ in private linear regression, without incurring additional privacy cost. Empirically, $\textsf{Cond-DP}$ with this conditioning matrix consistently outperforms state-of-the-art baselines across a wide range of datasets and model architectures under label DP, demonstrating strong and robust performance in practice.