Private Statistical Estimation via Truncation

We thank the reviewer for recognizing the important conceptual connection between truncation and differential privacy. While this seems intuitive, we are the first to formalize this connection and design algorithms with rigorous utility guarantees and sample complexity bounds. We are hopeful that this can open the door to more DP algorithmic developments in future works, obtained via truncation.

Our main result is a private learner for exponential families that only accesses the sensitive data after a truncation pre-processing step. As a bonus, our algorithms go through even if the provided data has already undergone truncation! When specialized to Gaussian mean estimation, our techniques indeed yields the correct sample complexity up to logarithmic factors in the lower-order terms. We will certainly clarify this in the camera-ready version. For Gaussian covariance estimation, if we are ok with dropping the bonus mentioned above, we can use any private pre-conditioning algorithm to avoid all dependence on the condition number. This logarithmic dependence comes up only under the restricted sample access since it is not clear if previous private Gaussian preconditioning algorithms can extend to the truncated setting.

Please find below the responses to specific questions:

1. Using (non-private) SGD to minimize the log-likelihood of exponential families in our setting yields a sample complexity of $O(\frac{m}{\alpha^2} \cdot \text{poly}(\kappa))$ where $m$ is the dimension of the parameter space, $\alpha$ is the $\ell_2$-error parameter, and $\kappa$ is the condition number (see e.g. Theorem 4.3 in [42] from references section).

   We note that the main difference is the dependence on $\kappa$, which is necessary as it arises from using techniques from the truncated statistics literature to lower bound the strong convexity parameter of the truncated log-likelihood function (see e.g. [34] in references section). Indeed, this exponential dependence appears even for (non-privately) estimating truncated exponential families.

2. One difference between truncation and clipping is that minimizing the truncated log-likelihood function yields a consistent estimator as long as the survival set has positive mass, e.g., 50%. This truncation of half of the data introduces biases that we then remove using our algorithms. In contrast, the clipping radius must depend on the concentration of the underlying distribution, as we must ensure no point is clipped with high probability so that no truncation bias is introduced. We commit to adding a discussion about this in the final version.

3. If we understand correctly, the framework from [36] in the references section is not generally suitable for estimating multivariate statistics, as it relies on a simple-hypothesis-testing formulation that does not fully capture private estimation for multivariate statistics. Specifically, (private) hypothesis testing and parameter estimation depend on the dimension in different ways.

We commit to clarifying the discussions above in the camera-ready version.

We thank the reviewer for recognizing the novelty and technical contributions of our work, as well as sharing the reference to more recent work on DP stochastic convex optimization.

The ``iterative localization’’ technique from [FKT20] does indeed directly optimize the population likelihood in one pass, under the additional assumptions that the likelihood is smooth and the condition number is not too large. For exponential families where we have a private preconditioning algorithm (e.g., Gaussians), this is indeed applicable to our setting and can simplify the proof as well as yield a logarithmic improvement in the bounds. However, in general, for badly conditioned exponential families, this additional requirement on the condition number bound is more nuanced. We will be sure to include this discussion in the camera-ready version.

[FKT20] Feldman, V., Koren, T., & Talwar, K. (2020). Private stochastic convex optimization: Optimal rates in linear time

We thank the reviewer for their careful reading, suggestions on the presentation, and for appreciating our results. We will incorporate these suggestions into the camera-ready version of our paper.

Our main conceptual contribution is the connection between truncation and differential privacy. While this seems intuitive, we are the first to formalize this connection and design algorithms with rigorous utility guarantees and sample complexity. We believe this can open the door to more practical algorithmic developments in future work.

We emphasize that our techniques lead to the first algorithm for privately estimating unbounded high-dimensional truncated families, whereas prior works focus on bounded or 1-parameter families.

Please find the responses to specific questions below:

1. We thank the reviewer for pointing out the additional generality of our technique. We indeed assumed absolute continuity with respect to the Lebesgue measure for simplicity to ensure the log-likelihood is differentiable. Our algorithm goes through as long as the latter holds. We will be sure to mention this in the camera-ready version.
2. We demonstrate how to privately obtain a rough estimate of the parameter (warm start) in Appendix B without any prior bounds. Previous works demonstrated how to achieve this for Gaussian distributions, and we extended the techniques to truncated exponential families. Once we have a rough estimate of the parameter, our algorithm chooses the survival set to be a bounded set of appropriate radius (depending on the warm start), which automatically yields a bound on the gradient norm of the truncated log-likelihood function. This is a key benefit of the truncation framework and optimizing the truncated log-likelihood.
3. Our general algorithm for exponential families does not have any dependence on prior bounds of the parameter (please see previous response).
4. Technically, Lemma 2.1 shows that it suffices to design DP algorithms for truncated distributions by designing a ``stable’’ reduction from (untruncated) distributions to truncated ones. We hope that this reduction can lead to other DP algorithms obtained via truncation. As noted in Section 1.1, another technical contribution that may be of independent interest beyond our work is the improved uniform convergence result for exponential families (Lemma 3.6), which improves upon prior works by a quadratic factor in the error parameter.

We thank the reviewer for their thoughtful and constructive feedback and for appreciating our results.

Our work is primarily a theoretical study, and our main goal is to formalize and rigorously analyze the connection between truncation and differential privacy. While truncation should intuitively synergize with privacy, our work is first to establish a systematic framework with precise utility guarantees and sample complexity bounds. We view this conceptual link as the main message of our paper, and we believe it can open the door to more practical algorithmic developments in future work.

To the best of our knowledge, our techniques lead to the first algorithm for privately estimating unbounded high-dimensional truncated families, whereas prior works focus on bounded or 1-parameter families.

We emphasize that we adopt standard exponential family regularity assumptions and the assumptions customary in truncated statistics analyses. We state the assumptions explicitly and quantify how constants depend on them.

Please find below the responses to specific questions:

1. In practice, we would ideally choose the survival set to contain a large constant fraction of the distribution, e.g., 90%. This can be a hyperparameter which is tuned. We would like to point out that one benefit of the truncated statistics framework is that the estimator is consistent regardless of the survival mass. This is a feature that is not shared by standard clipping operations to guarantee privacy.

2. We provide a generic warm-start algorithm in the appendix. Intuitively, it suffices to privately estimate the parameter of the truncated distribution, which will be a biased estimate of the true parameter but suffices as a warm start. This is an easier task since the truncated distribution is a bounded distribution.

   We also provide a pre-conditioning algorithm in the appendix. Again, the idea is to privately estimate the parameters of the truncated distribution.

3. In practice, a reasonable rule of thumb is to choose the failure probability beta to be a small constant, e.g., 5%. It may be helpful to think of beta as the significance level of a statistical study which should be set according to the field of study.