Private Overparameterized Linear Regression without Suffering in High Dimensions

We thank the reviewer for their detailed comments, and we address the reviewer’s concerns as follows.

The assumption that we know the covariance of the features $\mathbf{H}$ or that we can somehow get an approximation from the public data is quite strong. I think it would make the paper much stronger if there was some version that makes a DP approximation of $\mathbf{H}$.

Note that we do not assume that our algorithm knows the covariance of the features $\mathbf{H}$. In addition, if we do not have a public dataset, we can use the isotropic noise $\mathbf{\Sigma}=\mathbf{I}$ in our method to still get excess risk bounds (see Corollary 4.3, Corollary 4.4) that depend on the eigenspectrum of the data covariance instead of the problem dimension as those in Varshney et al. (2022), Liu et al. (2023). The idea of using public data in the DP methods has been widely used in the DP literature, e.g., Kairouz et al. (2020), Yu et al, (2022), Zhou et al. (2021). Moreover, getting unlabeled public data is generally cheaper than labeled training data. It is a good idea to develop a DP approximate $\mathbf{H}$, and we leave it as our future work.

Do you think the current techniques could be used in case where you release H privately?

Yes, because our developed analytical framework can handle the additive noise with general covariance matrices. Therefore, we can directly plug the DP approximation of $\mathbf{H}$ into our framework to get the result.

you can get rid of the restriction on $\epsilon$, this restriction is not inherent limitation of the shuffler approach

Firstly, we would like to clarify the restriction of $\epsilon$ in Varshney et al. (2022). On page 6, it should be $\epsilon\leq 1/\sqrt{N}$ instead of $\epsilon\leq \sqrt{N}$. Therefore, the $\epsilon$ in Varshney et al. (2022) is very restrictive since they can only choose a very small $\epsilon$. Secondly, we believe that this restriction is essential when applying the shuffling result (Feldman et al. (2022)). The reason that they have this restriction is as follows. In their proofs, they first show that each step in their method is $(\epsilon_0,\delta_0)$-DP. Then they use the shuffling amplification result to show that their method is $(\epsilon,\delta)$-DP with $\epsilon=\epsilon_0/\sqrt{N}$. Note that this shuffling amplification result requires $\epsilon_0\leq 1$, and thus they have the restriction $\epsilon\leq 1/\sqrt{N}$. The good thing about this shuffling amplification result is that one only needs to add random noise with the variance at the order of $1/\epsilon_0^2=1/(\epsilon^2 N)$ at each step to achieve $(\epsilon,\delta)$-DP. As a result, one can significantly improve the utility guarantee due to the $1/N$ factor in variance for the random noise. In order to get rid of this restriction, one needs to choose a large $\epsilon_0$. However, according to Feldman et al. (2022) (comments under Theorem 3.1 and also in Appendix B), when $\epsilon_0$ is larger than the order of $\log N$, there is no amplification effect, resulting in $\epsilon=\epsilon_0$. As a result, one needs to add random noise with the variance at the order of $1/\epsilon_0^2=1/\epsilon^2$ at each iteration to achieve $(\epsilon,\delta)$-DP. This leads to a substantially weaker utility guarantee, as the beneficial $1/N$ factor in the noise’s variance no longer applies. Therefore, we believe this restriction is essential in the shuffling result to achieve a strong utility guarantee since it does not allow local privacy parameter $\epsilon_0$ to be large.

Typos and bibliography issue

Thanks for pointing out those typos and the bibliography issue, we will fix them in the revision.

Thank you for your response. Yes, we indeed mean Feldman et al. (2020). You are correct that the condition is $\log(1/\delta)\geq Ne^{-\epsilon_0}$, and we state it as $\epsilon_0$ is larger than the order of $\log N$ in our previous response for simplicity. We will emphasize the results using amplification vs. non-amplification under different regimes of $\epsilon_0$ in the revision to make it more clear. Thank you for your suggestions.

Thank you for the clarification on the shuffling result. (By the way, I think you mean Feldman et al. (2020) instead of Feldman et al. (2022) here). I had a look at their Appendix B you mentioned and that indeed seems to be the case, up to log factors. I think you are neglecting here the log factors which in this case can be quite considerable, compared e.g. to $\sqrt{n}$ (those log factors may include $e^{\epsilon_0}$). Still, I would reformulate that part, and emphasise that amplification vs. non-amplification since I think you could take larger epsilons for it, as it reads currently you get the impression there is some hard limitation (ultimately it is just the analytical approximations limitation).

Otherwise the reply answers my questions, I don't have further questions.

We thank the reviewer for their comments and suggestions. We address the reviewer’s comments as follows and hope the reviewer will reconsider their score.

see 1, 2, 3; these aren't cited but should be

Thanks for suggesting these relevant papers, but we would like to point out that the third paper you mentioned is released on arXiv after the ICLR submission deadline. We will add and discuss them in both the introduction section and Section 3.2 in the revision.

technical hurdles and analytical tools you developed

Firstly, we propose to use DP-FTRL based method instead of the DP-SGD based method to prevent the need to use shuffling/random sampling to get good dependency on privacy parameters. Additionally, to achieve problem- and algorithm- dependent excess risk bound, we resort on the fact that DP-FTRL can be written as a gradient update (Sec B.2.2) to actually more closely follow the analysis from Zou et al (2021b) instead of following the DP-FTRL based analysis. However, directly applying their analysis will lead to an unfavorable dependence on the problem dimension $d$ when the additive noise is introduced. Therefore, we have developed highly non-trivial new techniques to address this issue and get an excess risk bound that can get rid of the explicit dimension dependence. In the following, we summarize the key technique hurdles in our analysis and the new analytical tools we have developed to address these difficulties:

1. Although DP-FTRL can be written as a gradient update (Sec B.2.2), the additive noise at each iteration $\mathbf{\xi}$ (see equation (B.4)) is correlated with previous iterations. This is significantly different from DP-SGD, where independent random noise is added at each iteration. Therefore, we cannot simply factor out the additive noise using the independence of the additive noise like the one used in the DP-SGD analysis. This correlation will introduce extra errors (see the second equation under equation (B.14)), which are challenging to be upper bounded and have never been studied in the analysis of Zou et al (2021b). To overcome this difficulty, we propose to characterize the properties of the additive noise generated by the tree aggregation procedure, and develop new proof techniques (see Sec B.4) as well as new results (see Lemma B.12) to characterize these extra error terms (see equation (B.16) and Theorem B.5). These new techniques and results enable us to derive the new bias-variance decomposition expression for each iteration in our proposed DP-FTRL based method (Theorem B.5).

2. Given the new bias-variance decomposition expression (Theorem B.5) for each iteration, we still cannot directly apply the proof techniques in Zou et al (2021b) to obtain the desired excess risk bound. The reason is that the extra errors introduced by the private mechanism depend on the general covariance matrix $\mathbf{\Sigma}$ and will affect the variance error (see Lemma B.6). As we discussed under Lemma B.6, the proof techniques in Zou et al (2021b) will make the variance error explode since the general covariance matrix $\mathbf{\Sigma}$ will no longer be well aligned with $\mathbf{H}$, a condition crucial for the proofs in in Zou et al (2021b)’s proofs. Therefore, to provide a tight upper bound on the variance error, we derive new results (Lemma B.7 and Lemma B.8) to handle the general covariance matrix $\mathbf{\Sigma}$ case.

In summary, to obtain the excess risk bound of our proposed method, we need to develop new proof techniques that can handle the correlated noise and the variance error introduced by the general covariance matrix of the additive noise. We believe our new analytical tools could be of independent interest due to their effectiveness in addressing the challenges posed by correlated noise and general covariance matrices.

We thank the reviewer for their careful and detailed comments, as well as the insightful suggestions. We address the reviewer’s concerns as follows.

(Major problem) access to (unlabeled) public data is not ever mentioned in the abstract or introduction.

We indeed mention in the abstract that “Furthermore, when unlabeled public data is available, we can design a better noise covariance matrix structure to improve the utility. ” We will also add comments about using unlabeled public data in the introduction section when we state our main contributions (the second bullet).

(Minor problem) a fair placement of the contributions of the submission in the literature

We agree with the reviewer that we need to have a fair placement of our work in the literature. It is true that our results and the results in Varshney et al. (2022), Liu et al. (2023) may be not directly comparable. For example, our results have an explicit dependence on the estimated residual $\ell$ while Varshney et al. (2022), Liu et al. (2023) get rid of this dependence by establishing a feasible upper bound for this term, assuming that the data distribution has a nice property, i.e., the condition number of the data covariance matrix is finite.

However, we would also like to clarify that our results are at least more reasonable and meaningful in the high-dimensional or even infinite-dimensional setting. Our results, stated as a function directly with respect to the data covariance and noise covariance, can still provide nonvaucous excess risk bounds even when $d$ is very large or even infinite (see our Corollary 4.4 and Corollary 4.6). In contrast, the prior bounds in Varshney et al. (2022), Liu et al. (2023) have an explicit dependence on $d$, which clearly become vacuous in the high-dimensional or infinite-dimensional case. Therefore, we will revise our comments about the relationship of our work with that of Varshney et al. (2022), Liu et al. (2023) to ensure a fair placement of our work in the literature. For example, rather than claiming that our method outperforms previous method, we will state that our method provides the first problem- and algorithm- dependent excess risk bound for private linear regression.

• Meaning of sharp: This was yet another confusion with the claims that reviewer BWiw mentioned and I have to agree that I was confused as well. I think the authors do a good job explaining what you meant by sharp, but as you could see, "sharp" seems to be a bit of a overloaded term and led to a lot of confusion, and it does not seem it was a good use of the term in the paper.

• Dependence on $\lVert w_0 - w^* \rVert$: I saw the author's response to reviewer BWiw on the dependence on the norm dependence, I think this was an interesting discussion that I had completely missed on my first reading of the paper. I cannot quite see how the value of this norm can be infinite (maybe you meant "go to infinity with $d$"?), but the difference between depending on $|| w_0 - w^* ||_2$ and on $|| w_0 - w^* ||_H$ seems worth discussing. I got a bit lost on the wording used (headspace and tailspace have very loose meanings). So this is a very minor suggestion and take it with a grain of salt, but it seems to be an interesting point of discussion and maybe it deserves a more careful discussion than the reply we had for BWiw.

• Practical interest: This is me commenting on BWiw's comment asking whether this is of practical interest, since the main focus of this paper seems to be theoretical. I'd advise the authors to not try to push too much trying to justify your results in practical terms since its biggest value seems to be theoretical, which is perfectly fine.

We thank the reviewer for their comments, and we address the reviewer's concerns as follows.

The proposed designed noise covariance matrix is also limited and may be unpractical since it needs the unlabeled data first to generate an estimation of $\mathbf{H}$

The idea of using public data in the DP methods has been widely used in the literature, e.g., Kairouz et al. (2020), Yu et al. (2022), and Zhou et al. (2021). In addition, getting unlabeled public data is generally cheaper than labeled training data. Therefore, we do not think the proposed designed noise covariance matrix is limited and impractical. Additionally, if we do not have a public dataset, we can use the isotropic noise $\mathbf{\Sigma}=\mathbf{I}$. In this case, we also develop an problem- and algorithm- dependent analysis for the excess risk bound (see Corollary 4.3, Corollary 4.4), which are stated as the entire data covariance matrix instead of the problem dimension, thus can be potentially better than the existing works (Varshney et al. (2022), Liu et al. (2023)) that rely on the dimension explicitly.

Moreover, we also want to emphasize that our excess risk bound is general, and can be employed for any noise covariance. Therefore, one can definitely seek to develop private algorithms using part of the training data points to estimate $\mathbf{H}$ (regardless of its estimation error) and then apply our general theoretical framework to get the excess risk bound accordingly. In fact, as long as the estimate can well approximate the large eigenvalue of $\mathbf{H}$ (i.e., the estimate is better than $\mathbf{I}$ in terms of estimating $\mathbf{H}$), it will result in better utility guarantees compared to that obtained by using isotropic noise. We will add the discussion in the revision.

Binary representation is not clear in line 13. The contradiction between Line 7 and page 15

The binary representation mentioned in line 13 refers to expressing the number $t$ as a binary number using $k$ bits, i.e., $\\{b_1,....,b_k\\}$, where $b_1$ is the most significant bit. We will add more explanations about the binary representation in the revision. There is no contradiction between line 7 in Algorithm 3 and Page 15. The set $\mathbf{p}_j$ stores nodes in a top-down sequence, from the root to the leaf. Since the first node $n_j$ stored in $\mathbf{p}_j$ is the last left child node in $\mathbf{p}$ (top-down order), it is equivalent to state that $\mathbf{p}_j$ stores the nodes from the leaf node $m_t$ to the first left child, i.e., $n_j$, along the path (down-top order). We will clarify this in the revision.

typo

Thanks for pointing out this typo, we will fix it in the revision.

Comparison to DP-Adaptive-Mini-Batch-Shuffled-SGD

We would like to emphasize that the main contributions of our work lie at the theoretical side. We theoretically show our method can achieve the problem- and algorithm- dependent excess risks for private linear regression, which is directly stated as the data covariance and noise covariance, rather than the problem dimension. Therefore, our bound can still be reasonable and meaningful even in the infinite dimension case. This is a distinct departure from existing results, such as those presented by Varshney et al. (2022) and Liu et al. (2023), which are dependent on the problem dimension. Clearly, those bounds will be vacuous when $d$ is large. Additionally, according to the theoretical guarantee of DP-Adaptive-Mini-Batch-Shuffled-SGD, it cannot handle the overparameterized case.

The author should add lower bounds

We believe that it is possible to have an algorithm-dependent lower bound that is also stated as a function of both data covariance and the covariance of the additive noise. When the covariance of the additive noise is $\mathbf{\Sigma}=\mathbf{I}$, we believe our upper and lower bounds can be tight up to logarithmic factors. In the more general case, there may exist a gap because we may need to handle the non-commute matrices in the lower bound proofs, which may necessitate additional relaxations to address this challenge. The motivation of our paper is to develop a problem-dependent framework to study the private linear regression that can handle general data covariance and general non-isotropic additive noise to achieve DP. Our results can potentially lead to better noise designs for achieving DP and obtain better utility guarantees. Adding the lower bound to our paper is a plus but this will not affect the main contributions of our paper. We would like to add the discussions about the lower bound in the revision.

Thanks for your response, we would like to further address your questions as follows.

For the case where there is no private data, I do not think you are right. Since you assume x is sub-Gaussian, that is your noise added to the covariance matrix is proportional to d and this is unavoidable.

Our results depend on the data covariance and the covariance of the additive noise (see Theorem 4.2), and this is key that we can derive our results. Even if you add random noise with an identity matrix you can still benefit from good data covariance, as the excess risk is characterized via $H$-norm and $\\|\epsilon\\|_H\sim \mathrm{Tr}(H)<< d$ when $\epsilon$ is generated from isotropic Gaussian. And this is why we say that we derive the problem-dependent excess risk.
Similar results have been established in the literature for other problems (Song et al., 2021; Ma et al., 2022; Li et al., 2022a) using the random noise with an identity matrix (these results cannot be applied to private linear regression).

That means your noise scale will be extremely large, then how you can privatize the covariance matrix without affecting your final result?

When we add isotropic additive noise, we don’t need to privatize the covariance matrix or use public data.

For the theoretical analysis, unfortunately, I cannot agree with that. I checked carefully, it's idea is very similar to Zou et al and previous linear regression paper although here you used the tree mechanism instead. The idea of the proof is similar.

We disagree with your comments. Note that most analysis of differentially private algorithms will somehow rely on the analysis of the underlying non-private method (e.g., DP-SGD), and that is why our analysis looks similar to the analysis in Zou et al. Note that even in the previous work (Varshney et al.), it also relies on the underlying non-private analysis (bias-variance decomposition analysis proposed in [1] ).

Reference:

1. Jain et al. A markov chain theory approach to characterizing the minimax optimality of stochastic gradient descent (for least squares). In FSTTCS, 2017

Thanks for your response, I believe the reviewer's concerns mainly come from the misunderstanding of our results and other results in the literature, and we would like to clarify it as follows.

(1) Yes, private learning with public data is a common assumption. However, all the papers you mentioned are for DP-ERM rather than DP linear regression. I believe it is possible to get similar results even without public data for overparameterized linear regression.

We have clearly state in our paper that we can get similar results without using any public data by adding random noise with the identity matrix (see Corollary 4.3 and Corollary 4.4). The reason that we propose to use public unlabeled data is to show that the excess risk bounds can be further improved. In addition, since our developed analytical framework can handle the additive noise with general covariance matrices, we can also use the DP approximation of $H$ to get the result. The detailed comparisons between our method with and without unlabeled public data are illustrated in Table 1. We have discussed the paper you mentioned in detail in the related work section. Note that their results cannot be applied to linear regression since they assume the per-example objective loss to be Lipschitz everywhere.

(2) Even for the original DP linear regression paper, we can also get a similar upper bound for the overparameterized case, please carefully read the paper. https://arxiv.org/pdf/2207.04686.pdf, for example, page 41, their bound only depends on the trace of the Hessian so it is possible to get a similar bound.

It is obvious that the results in the page 41 of https://arxiv.org/pdf/2207.04686.pdf will lead to an exploding bound in the overparameterized case. To be more specific, their results depend on terms $\mathrm{Tr}(H^{-1})$ and $\mathrm{Tr}(H^{-1}\Sigma)$ ($H$ may have very small eigenvalues, e.g., polynomial or exponential, and $\Sigma$ resembles $H$), which will definitely lead to much worse results or even exploding results in the overparameterized case. Therefore, the original DP linear regression paper cannot get similar upper bounds for the overparameterized case.

(3) No experiments. In the non-private case, all previous papers on overparameterized linear regression have experimental results. However, this paper does not have any experimental study.

Our paper’s main contribution is on the theoretical side. However, we would like to add experiments in the revision.

(4) The proof high depends on the previous studies on overparameterized linear regression. I cannot see any difficulty in the proof.

As we have mentioned in the response to Reviewer jHEC and Reviewer BWiw, we have summarized the Technical difficulties as well as new proof techniques. Previous techniques cannot handle these difficulties in our problem and we develop highly non-trivial solutions to address them. Here we present a brief summary of these difficulties and new proof techniques.

Technical difficulties:

1. Existing tool cannot handle the extra errors introduced by the additive noise in the variance error, and it will lead to an exploding bound.

2. Existing method can only handle the case where the iterates form a markov chain. However, this is not the case in our setting as the additive noises are correlated at different iterations.

New proof techniques:

1. We develop new proof techniques, utilizing a new reference quantity that is also stated as a function of the data covariance and sample size, to control the variance error dynamics, rather than the previous results.

2. We develop a new technique that can handle their correlations. The key is to maintain a dynamic set that includes the noises correlated with the noise in the current iteration, and then precisely characterize how these correlations affect the convergence.

Thanks for your response, but I still find there are many issues. (1) Yes, private learning with public data is a common assumption. However, all the papers you mentioned are for DP-ERM rather than DP linear regression. I believe it is possible to get similar results even without public data for overparameterized linear regression. For example https://arxiv.org/abs/2206.01836. So the assumption in the paper is unacceptable unless the authors could show a lower bound.

(2) Even for the original DP linear regression paper, we can also get a similar upper bound for the overparameterized case, please carefully read the paper https://arxiv.org/pdf/2207.04686.pdf, for example, page 41, their bound only depends on the trace of the Hessian so it is possible to get a similar bound.

(3) No experiments. In the non-private case, all previous papers on overparameterized linear regression have experimental results. However, this paper does not have any experimental study.

(4) The proof high depends on the previous studies on overparameterized linear regression. I cannot see any difficulty in the proof.

So I will not change the score unless the author could show it is impossible to achieve similar results without public data.