Dimension-free Private Mean Estimation for Anisotropic Distributions

We thank the reviewer for their feedback and interest in our results.

• Lower bound for the case of unknown covariance: We are not certain that our results are optimal in the unknown covariance case, even assuming a diagonal covariance matrix, and we agree that identifying an intrinsic gap between the known and unknown covariance would be very interesting (additionally since this gap does not exist for privately learning the mean in the Mahalanobis norm). Known lower bound techniques for private statistical estimation (in particular, the most popular fingerprinting technique for exponential families) does not apply as is to our problem. However, our current intuition is that there is a case for which the trace term is constant and the $d^{¼}$ term is necessary. Therefore, we think that it is possible that the $d^{¼}$ term cannot be improved.

• When can we achieve a dimension-independent bound under unknown covariance: Indeed, the additional error in our results for the unknown covariance case stems from the $d-k$ coordinates of smaller variance, where $k$ is the number of top-variance coordinates we choose to learn, and we show that we can always learn up to roughly $\varepsilon^2n^2$ coordinates without increasing the sample complexity. In particular, the error incurred in the mean estimation step is $(\lVert\sigma_{1:k}\rVert_1 + \sqrt{d-k} \lVert \sigma_{k+1:d}\rVert_2) / \varepsilon n$. The first term is already smaller than the optimal $\lVert\sigma_{1:d}\rVert_1$, and in our result we show that the second term can always be upper-bounded by $\sqrt{d}\lVert\sigma_{1:d}\rVert_1/\sqrt{k}$. When this inequality is tight for some $k$, our analysis of this algorithm is tight. More generally though, there are interesting cases when the term $\sqrt{d-k}\lVert\sigma_{k+1:d}\rVert_2$ is smaller than the optimal $\lVert\sigma_{1:d}\rVert_1$, for $k$ at most $\varepsilon^2n^2$, and then our results match the ones for known covariance, up to logarithmic factors in $d$. One example is the case of exponentially decaying variances: if $\sigma_i=\sigma_1 e^{i-1}$, then it suffices to learn only the top $k=\log(d)$ variances, because the error incurred by the last term $\sqrt{d-k}\lVert\sigma_{k+1:d}\rVert_2\approx 1/\sqrt{d}$, which is smaller than the optimal $\lVert\sigma_{1:d}\rVert_1=O(1)$. Learning the top $\log(d)$ variances using the sparse-vector technique can be achieved with a polylogarithmic in $d$ number of samples, adding only logarithmic factors to the optimal sample complexity.

• Line 113 omits several logarithmic factors with respect to $\delta$, $\beta$, but indeed there is a typo in this particular term: the exact dependence is $\log^2(d)+\log^{1.5}(d)/\varepsilon\gamma + \log(d)/\varepsilon\gamma^2$. We will add the full calculation for this case of interest in the appendix.

We thank the reviewer for the positive feedback and suggestions to improve the presentation of our paper.

• We agree that having a conclusion would be preferable and since the final manuscript can be a page longer we will certainly add one (and move discussion for future work from the appendix) in the main body.
• Lower bound for the case of unknown covariance: We are not certain that our results are optimal in the unknown covariance case, even assuming a diagonal covariance matrix, and we agree that this is a very interesting question. We know of special cases (e.g., diagonal matrices whose singular values follow an exponential decay or isotropic matrices) for which our results are optimal up to logarithmic factors. Our intuition is that there is a case for which the trace term is constant and the $d^{¼}$ term is necessary. Therefore, we think that it is possible that the $d^{¼}$ term cannot be improved.
• Range of epsilon: Thank you for pointing this out – we understand that the range $(0,10)$ seems somewhat arbitrary, and we will clarify this in the updated version. Please note that the theorem still holds for $\varepsilon\in(0,1)$, which would correspond to a reasonably strong privacy guarantee. However, we wanted to point out that the theorem holds more generally, for $\varepsilon\in(0,c)$ where $c$ is some constant larger than $1$, since $\varepsilon>1$ is still encountered in real-world applications, and might be a regime of interest for those. The choice of constant is due to approximations we take in the privacy proof and it has not been optimized (so the theorem could possibly hold for $\varepsilon\in(0,c)$, where $c>10$). However, as you mentioned, 10 seems to be large enough already, so we did not find it necessary to explore the exact constant $>10$ for which our proof goes through.
• Simulations: We focus on the theoretical analysis of our algorithms and prove their privacy and accuracy guarantees, but we do expect that the known-covariance algorithm will perform well, since the constants involved in our error are provably small. The results for the unknown covariance case are less conclusive and we agree that some experimentation might be interesting in this case. However, we would like to point out that ours are the first methods that are applicable for $n\leq \sqrt{d}/\varepsilon$, which makes it difficult to choose an appropriate baseline to compare to for smaller sample sizes.

We thank the reviewer for the positive feedback and suggestions to improve the presentation of our paper.

• Thank you for the suggestion on the presentation! We will consider including definitions from the preliminaries earlier in the introduction to formalize the intuition we want to convey. Please let us know if there was a specific definition that would have been helpful to see earlier.
• Lower bound for the case of unknown covariance: We are not certain that our results are optimal in the unknown covariance case, even assuming a diagonal covariance matrix, and we agree that this is a very interesting question. We know of special cases (e.g., diagonal matrices whose singular values follow an exponential decay or isotropic matrices) for which our results are optimal up to logarithmic factors. Our current intuition is that there is a case for which the trace term is constant and the $d^{¼}$ term is necessary. Therefore, we think that it is possible that the $d^{¼}$ term cannot be improved.
• Simulations: We focus on the theoretical analysis of our algorithms and prove their privacy and accuracy guarantees, but we do expect that the known-covariance algorithm will perform well, since the constants involved in our error are provably small. The results for the unknown covariance case are less conclusive and we agree that some experimentation might be interesting in this case. However, we would like to point out that ours are the first methods that are applicable for $n\leq \sqrt{d}/\varepsilon$, which makes it difficult to choose an appropriate baseline to compare to for smaller sample sizes.

We thank the reviewer for the positive feedback and interest in our results.

We thank the reviewer for the positive feedback and interest in our results.

• The case of unknown general covariance: Our main result for unknown covariance (Theorem 1.3) includes the sum of the square-roots of the diagonal elements of the covariance matrix, $\sum_{i=1}^d \Sigma_{ii}^{½}$. This way, we present a result for general covariance without making any assumptions on the covariance matrix. However, this sum is more easily interpretable when the covariance is indeed diagonal: the sum is equal to $\mathrm{tr}(\Sigma^{½})$, when the covariance matrix is diagonal, and can be larger otherwise. In the paper, we focus on the case of diagonal covariance in places, for ease of exposition when describing our techniques, to compare with other baseline approaches which only work for diagonal covariance matrices, or to compare with our result for the case of known covariance which includes the $\mathrm{tr}(\Sigma^{½})$ term. We understand how this can be confusing and we will clarify that we make this assumption for simplicity when we do. Thank you for the suggestion.

• Indeed, Line 829 has a typo and this is the correct term. Thank you for noting it!

• On the approach of privately estimating the covariance matrix before using a known-covariance mean estimation algorithm: We do not know of any lower bounds specifically aimed at privately estimating a covariance matrix with large singular value gaps. The existing lower bounds for covariance estimation in spectral norm which apply to Gaussian data ([Kamath Mouzakis Singhal 2022], extended to the low-accuracy regime later by [Narayanan 2023]) use almost-isotropic covariance matrices as the lower bound instance, so they do not go through under a large singular value gap assumption. But we would not expect them to: there are cases [Singhal Steinke 2021] where assuming a known large singular value multiplicative gap in the order of O(d^2) allows us to learn the subspace of the top eigenvectors (and subsequently their singular values) with a sample complexity roughly polynomial in the dimension of the subspace, which does not depend on d. However, we note that in any case, we expect that going through covariance estimation to achieve our goal would be a lossy step. The reason is that for the case of (almost) identity covariance, the sample complexity of covariance estimation in spectral norm would be $d^{1.5}/\alpha\varepsilon$, whereas our current upper bound for the unknown covariance case is $d/\alpha\varepsilon+d^{0.75}/\alpha^{½}\varepsilon$, which is smaller (and optimal for the regime $\alpha\leq \sqrt{d}$ which is usually of interest). We will update our manuscript to include the discussion.