Beyond Covariance Matrix: The Statistical Complexity of Private Linear Regression
This work addresses the problem of private linear regression and bandits for researchers in differential privacy and machine learning, providing foundational insights and optimal algorithms.
The paper tackles the statistical complexity of private linear regression under unknown, ill-conditioned covariate distributions, showing that the intrinsic complexity is captured by L1 analogues of the covariance matrix rather than the usual covariance matrix, and establishes minimax convergence rates with an Information-Weighted Regression method achieving optimal rates. As an application, it proposes an efficient algorithm for private linear contextual bandits that achieves rate-optimal regret bounds of order sqrt(T) + 1/α and sqrt(T)/α under joint and local α-privacy models, demonstrating that joint privacy incurs almost no additional cost.
We study the statistical complexity of private linear regression under an unknown, potentially ill-conditioned covariate distribution. Somewhat surprisingly, under privacy constraints the intrinsic complexity is \emph{not} captured by the usual covariance matrix but rather its $L_1$ analogues. Building on this insight, we establish minimax convergence rates for both the central and local privacy models and introduce an Information-Weighted Regression method that attains the optimal rates. As application, in private linear contextual bandits, we propose an efficient algorithm that achieves rate-optimal regret bounds of order $\sqrt{T}+\frac{1}α$ and $\sqrt{T}/α$ under joint and local $α$-privacy models, respectively. Notably, our results demonstrate that joint privacy comes at almost no additional cost, addressing the open problems posed by Azize and Basu (2024).