Differentially Private Regression with Unbounded Covariates

Ever since the introduction of Differential Privacy (DP) by Dwork et al. (2006), differentially private variants of statistical estimation procedures have been a research topic of intense interest. The work on learning linear models alone is vast (see Cai et al. (2020); Wang (2018) for two recent reviews). Empirical Risk Minimization is also the impetus for the development of a broad array of new methods for DP-mechanism design, including output perturbation (Iyengar et al., 2019; Zhang et al., 2017; Jain and Thakurta, 2014), objective perturbation (Chaudhuri et al., 2011; Kifer et al., 2012), and gradient perturbation (Bassily et al., 2014; Abadi et al., 2016), to name a few. Nevertheless, despite the intense interest on this topic, all of the existing work on regression provides differential-privacy guarantees assuming bounded covariates. Intuitively, this can be explained by inspecting even the simple least squares estimator used in linear regression. It is easy to see that estimator's sensitivity, i.e., its variability under changes on a single sample, is determined by the design matrix (i.e., the matrix of samples). As sensitivity has a direct effect on differential privacy guarantees, bounding the design matrix's eigenvalues is the prevalent approach for bounding the sensitivity. For this reason, assuming bounded covariates is a ubiquitous assumption in DP literature on both linear regression and learning generalized linear models.