Improved Analysis of Sparse Linear Regression in Local Differential Privacy Model

We are grateful for the time and effort that the reviewer has dedicated to reviewing our work.

1. Answer to the question regarding Theorem 7:

The main differences between Theorem 7 and Theorem 9 are two fold. First we need finer analysis on $B_1$ term due to clipping operation. Second, due to different distributional assumption we adopt a more general lemma related to RIP condition. The main contribution of Theorem 7, as we mentioned, is rectifying the flaws in the previous result. To see greater novelty in proof techniques, please refer to Theorem 34 in the Appendix for the case without the isotropic assumption.

2. Answer to the question regarding Table 1:

Thank you for your suggestion. In our current version, Table 1 is placed in the Appendix due to space limit. We will definitely move to the paper if additional pages are allowed.

We are grateful for the time and effort that the reviewer has dedicated to reviewing our work.

1.Response for W1 and Q1:

We cannot agree with the reviewer's comment. Our results confirm that the dependence of dimension is due to the hardness of the LDP setting rather than the norm of the data being upper bounded by $O(\sqrt{d})$. In fact, in the central DP case, even under some similar assumptions on data distribution, the nearly optimal rate is $O(\sqrt{\frac{k\log d}{n}}+\frac{k\log d}{n\epsilon})$ (see assumptions (P1'), (D1') and (D2') and Theorem 4.4 in Cai et al. 2021). Note that even in the heavy-tailed response setting with $\|x\|_2\leq O(\sqrt{d})$, we can still get an upper bound which only depends on $\text{Poly}(k, \log d)$ (see Theorem 7 and Assumption 3 in [1]). Similarly, for the non-private setting, Raskutti et al. 2011 show that the optimal rate is $O(\sqrt{\frac{k\log d}{n}})$ in the case where $x$ is $\sigma^2$-subgaussian, indicating that the $\ell_2$-norm of $x$ is upper bounded by $O(\sqrt{d})$ with high probability. We refer the reviewer to Table 1 in Appendix for a detailed comparison with some related work.

[1] Hu, Lijie, et al. "High dimensional differentially private stochastic optimization with heavy-tailed data." Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. 2022.

2.Response to W2.

In fact, only our upper bound for the NLDP model relies on the $\ell_1$-norm bound assumption. Specifically, we need such an assumption in the proof of Theorem 3 to bound the $T_3$ term. Please refer to Page 24 in the Appendix to see how the assumption $\|\theta^{*}\|_1\leq 1$ is applied. We will introduce an additional factor of $\sqrt{d}$ if we use $\ell_2$-norm assumption instead. As we mentioned, this assumption has been previously studied in the literature such as Chen et al. (2023; 2022a) and Fan et al. (2021).

3. Response to W3

It is notable that Assumption 2 assumes $x$ and $y$ are sub-Gaussian, which is the most commonly used assumption in the literature of sparse linear regression even in the non-private case, such as Raskutti et al. 2011. Assumption 1 is only used for Theorem 3. The usage of $\ell_1$-norm boundedness assumption was just discussed above; $\kappa_\infty$ is vital for providing $\ell_\infty$-norm bound on the inverse of private covariance estimator (Please refer to Page 23 in the Appendix).

4. Answer to W4

Firstly, although $k\ll d$ holds in general, sparsity $k$ can heavily affect the estimation error. For instance, when $k=O(d^{\frac{1}{2}})$, ignoring the sparsity structure limits the previous result to an estimation error of $O(\frac{d^\frac{3}{2}}{\sqrt{n}\epsilon})$ in LDP model. In contrast, our work attains rate of $O(\frac{d^{\frac{5}{4} }}{\sqrt{n}\epsilon})$ and $O(\frac{d} {\sqrt{n}\epsilon})$ for NLDP and interactive LDP, respectively.

Secondly, from the theoretical perspective, the significant implication of sparse linear regression in ML, DP and many interconnected problems is the impetus to address the constraints of previous techniques as they cannot be readily generalized to the general $k$-sparse case. We believe that our methods and some technical lemmas can also be used in other related problems.

Thirdly, as the previous paper already showed that the estimation error will be trivial even when $k=1$ in the case of $n\ll d$. However, the problem remains inadequately understood in the low-dimensional regime, which is the motivation of our research. We aim to give an answer to the question: what is the optimal rate of sparse linear regression in the rich data regime ($n\gg d$)? Sparse linear regression in the low dimensional case $n\gg d$ has received enormous attention but remains under-studied in the DP community. For example, [2] studies the problem of the sparse linear bandit, highlighting the critical difference between the poor data regime ($n\ll d$) and the rich data regime ($n\gg d$). Thus, we believe our problem is merited to study.

[2] Hao, Botao, Tor Lattimore, and Mengdi Wang. "High-dimensional sparse linear bandits." Advances in Neural Information Processing Systems 33 (2020): 10753-10763.

5. Response to W5

We guess the reviewer refers to the assumption of $n\geq O(d^4)$ in Theorem 3 and 5. Note that it is only used in the non-interactive case and we do not need such an assumption in the interactive setting. As we mentioned in Remark 3, this assumption is to ensure the private covariance matrix is invertible. We can relax such an assumption when there is some public unlabeled data.

6. Response to Q2

The reason we assume the whitened covariate $x$ is subgaussian and $x$ has bounded covariance is just for convenience and to make the paper easier to read.

For the assumption on $\zeta$, since we have assumed that both $y$ and $x$ are sub-Gaussian, indicating that $\zeta$ is also sub-Gaussian with variance $\sigma^2$ due to the sub-Gaussian property and our linear model.

7. Response to Q3

It is notable that even in the case $||\theta^{*}||_2 \leq 1$, all the lower bounds still hold without any changes to the proofs. See Page 18 for the proof of Theorem 1, and Page 27 for the proof of Theorem 6. We have $\|\theta_z\|_2\leq \|\theta\|_1\leq 1$. In the revised version, we added the above comments.

8. Response to Q4

In fact, our upper bound in the interactive setting is still valid when $\|\theta^*\|_2\leq 1$. In contrast, our upper bound for the NLDP model relies on such an assumption. Specifically, if the assumption on $\theta^*$ is loosened to $\ell_2$-norm bounded, it would be hard to bound the $T_3$ term in the proof of Theorem 3 without introducing an additional factor of $\sqrt{d}$. Please refer to Page 23 in the Appendix to see how the assumption $\|\theta^*\|_1\leq 1$ is applied. However, to make the paper consistent, we assume ${\|\theta^{*}\|_1\leq 1}$.

We thank the Reviewer for the careful and detailed review as well as the constructive feedback.

1.Response to Weakness

We acknowledge the gap between the upper and lower bounds established in our work. However, as sparse linear regression is a fundamental problem in both statistics and differential privacy, we do not think such gaps undermine our contributions. Here are the reasons:

Only the work (Wang & Xu (2021)) has studied sparse linear regression in the LDP model. However, the problem is still far from well understood: (1) For lower bounds, previous results only consider the case where $k=1$ and it is technically difficult to extend to the general $k$ sparse case. Prior to our work, there are no comparable lower bounds! We give non-trivial proofs for our lower bounds by constructing hard instances that might be instructive for other research problems. (2) For the upper bound in the NLDP model, we give the first algorithm with a non-trivial upper bound since there is even no previous study due to the one-round communication constraints in the model! Moreover, the closed-form private estimator for sparse linear regression is highly efficient, and can readily be applied to other problems. (3) Even the investigation of the upper bound in the interactive setting is still quite deficient. Previous work claims the rate is already optimal for $k=1$. However, we found a flaw in their approach and the proof of the upper bound is partly mistaken. We then gave a correct upper bound.

In summary, sparse linear regression in the LDP model is quite difficult and challenging even in the interactive setting but our upper and lower bounds represent a significant leap forward in addressing this insufficiently studied problem.

For the assumption that $n\geq O(d^4)$, note that it is only used in the non-interactive case and we do not need such an assumption in the interactive setting. As we mentioned in Remark 3, this assumption is to ensure the private covariance matrix is invertible. We can relax such an assumption when there is some public unlabeled data.

2.Response to Q1

Yes, $\ell_2$-norm is a commonly used metric for our problem. Firstly, many previous works employ the same metric [2] or adopt a metric that can be easily converted to parameter $\ell_2$-norm error bound [3]. Secondly, we can easily transform the $\ell_2$-norm bound to $||\theta^{{priv }}-\theta^*||_\Sigma$ because it is less than

$\lambda_{\max}(\Sigma)||\theta^{{priv }}-\theta^*||_2^2.$

Theorem 4.2 in [4] adopts $||\theta^{{priv }}-\theta^*||_{\Sigma}$. However, in their proof, they first analyzed the convergence rate of $\ell_2$-norm error.

Then armed with the boundedness and normalized rows of design matrix assumptions, they were able to develop the bound on $||\theta^{{priv }}-\theta^*||_{\Sigma}$ based on $\ell_2$-norm bound. Note that these assumptions are stronger than our Assumptions 1 and 2, therefore here we discuss the error in $\ell_2$-norm.

3.Answer to Q2 (regarding sparsity $k$ in Algorithm 1)

No, $k$ is not used in our Algorithm 1. However, the sparsity in our proposed estimator $\hat{\theta}^{priv}$ is preserved by setting element-wise soft-thresolding operator's parameter $\lambda_n$ to some constant of size $O(\frac{d\log n \sqrt{\frac{1}{\delta}}}{\sqrt{n}\epsilon})$. $\lambda_n$ serves as a constraint of the $\ell_\infty$-norm error and introduced an extra error term of $O(\sqrt{k})$ when it comes to computing the $\ell_2$-norm error. Note that such phenomenon is quite common in the non-private case, such as the optimal regularization parameter in LASSO [1]

4. Answer to Q3

In the non-interactive setting, we cannot say we need to privately estimate the covariance matrix. However, for our method, we have to do this due to our closed-form estimator.

If we interpret your question correctly, "Can you privatize the two terms in the OLS solution together?", you are asking whether we can perturb our non-private estimator as a whole. Unfortunately, we cannot adopt the output perturbation method, i.e., adding some Gamma noise to $\hat{\theta}^{OLS}$. First, output perturbation does not preserve LDP. Secondly, according to the DP theory, the scale of the noise should be proportional to the $\ell_2$-norm sensitivity, which can be bounded through clipping operation or if the data are assumed to be bounded. However, this method fails since the magnitude of noise needs to grow polynomially with $\sqrt{\frac{d}{n}}$, causing the estimation error much larger. Moreover, the $\ell_2$-norm sensitivity is bounded only with some probability due to the existence of the inverse of the covariance matrix, indicating the algorithm does not satisfy DP.