Even for a basic inferential task like linear regression with a single independent variable and Gaussian errors, we still don't have a complete understanding of what is the optimal differentially private estimator and what is its convergence rate. In particular, when the dataset size is small or the independent variable has small variance, differentially private analogues of the median-based Theil-Sen estimator perform better than ""asymptotically optimal"" methods like sufficient statistics perturbation, the exponential mechanism, or private gradient descent. I will survey what is known and what remains open about this problem.

Joint works Alabi, McMillan, Sarathy, and Smith (PoPETS 2022), Alabi (in preparation), and Sarathy (in preparation).