Differentially Private Optimization with Sparse Gradients

Thank you for your positive assessment and feedback..

In the revision, we will reorganize the content. As you suggest, we will include results for DP-SCO from Section 6 (specifically from Appendix G.2), as well as a more extensive motivation and detailed proofs in Section 5.

Questions

Thank you for raising this question. Regarding the running times, for Algorithm 2 we need to compute $2^{N+1}+1=O(n)$ gradients (where N is truncated geometric), and apply Gaussian mechanism and projection over the $\ell_1$-ball four times (these two algorithms run in time nearly linear in the dimension $d$). Overall, the gradient complexity is $O(n)$ and the computational complexity is $O(nd)$.

For Algorithm 3, we can use Lemma 5.3 to provide an upper bound on the expected number of iterations (which is $O(n)$), and then multiply this number by the worst-case estimate of the complexity of Algorithm 2. This provides an in-expectation bound for the complexity of the algorithm.

We will make sure to add these details in the revision.

Thank you for the valuable feedback.

1. Thank you for the references; we will make sure to add them to properly position our work within the field.

2. Unfortunately, it is not true that dimension-free rates are known only for unconstrained settings. In fact, that there are works providing (nearly) dimension-free rates for the case of polytope feasible sets [22,23:Talwar, Thakurta, Zhang], [24: Asi, Feldman, Koren, Talwar] and [25: Bassily, Guzman, Nandi]. More importantly, there is no contradiction with the lower bounds in BST14, since their construction of fingerprinting codes (and packings for the pure case) uses dense vectors. In fact, the key observation behind our sparse DP lower bound is that the sparsity constraint weakens this construction, and a block diagonal construction with blocks as in BST14 yields a nearly optimal lower bound. Note too that polynomial-in-the-dimension lower bounds are still obtained for large enough sample size $n$, showing a smooth transition between the different regimes.

3. Other questions

   1. For mean estimation (Table 1), our upper bounds smoothly transition between the different regimes. For DP-SCO and DP-ERM (Table 2), it is also possible to obtain this transition (simply by selecting the algorithm with the best rate depending on the instance parameters). In the original table we decided to include only the new high-dimensional rates, but we have now added the different regimes (see the attached file). We apologize if this caused confusion.

   2. Each specific application may have an ad-hoc way of estimating $s$. For example, in embedding models, the sparsity (for the embedding layer) will be the number of columns. Alternatively, $s$ can be a hyperparameter (this does not compromise privacy, as long as the hyperparameter selection is done privately). Designing algorithms that work without knowing $s$ is an interesting question for future research---we will add this to the revision.

   3. Regarding the overlap in Lipschitzness and boundedness assumptions, we opted to keep this (sometimes redundant) parameterization since we are combining different assumptions for different results. Thank you for pointing this out.

   4. There might be a potential misunderstanding here; the gradient sparsity assumption is made over the raw noise-free gradients. Any noise addition (or more general DP procedure) applied to these gradients does not break the sparsity assumption. Please let us know if this resolves your question.

Thank you for your review. We will now elaborate on the comments.

Thank you for your comment on practical applications. In this regard, the idea of gradient sparsity has already impacted practical DP optimization. The most immediate references in this respect are [6: Zhang, Mironov, Hejazinia] and [7: Ghazi, Huang, Kamath, Kumar, Manurangsi]. Regarding the specific contributions of this work, we believe that significant components of our results can inspire practical improvements. First, the projection mechanism and compressed sensing approaches are easy to apply and should lead to better statistical performance in mean estimation than, e.g., the sparse vector technique (which is the main approach in [6,7]). Second, our regularized output perturbation approaches for DP-SCO (Section G) are easy to implement. Third, towards neural network applications (such as embedding models), the computational benefits of sparsity are more significant under structured sparsity, e.g., in the case of embedding models we need the sparsity to operate at the level of rows of the embedding matrix. We believe that ideas used in the context of group or structured sparsity can be of use here, but this is out of the scope of the current submission. Finally, a major roadblock for practical applications is the heavy-tailed nature of the bias-reduced gradient estimator used for SGD. While the algorithm in its current form might be less practical, we hope our work may inspire further ideas and lead to more practical methods.

We apologize for the current dense content; in the revision, we will try to rewrite to make it more accessible.

Questions

As we mention above, the bias reduction method may be hard to implement in practice. Particularly, the heavy-tailed nature of the gradient estimator may pose convergence challenges. Boosting might mitigate this, but we are interested in continuing investigating alternative approaches that can be more practical.

We would like to thank the reviewer for the valuable and detailed feedback.

Firstly, we apologize for the lack of clarity of the algorithmic choices and the proofs in our submission. Here is an overview of the choices behind Algorithm 2. As discussed in the paper, the near-optimal mean estimation algorithms we introduce are biased. Simply using SGD with this mean estimation procedure for minibatch gradients would result in a polynomial degradation of the rates (see, e.g., [6: Zhang, Mironov and Hejazinia], who carry out this approach). To handle this issue, we propose a bias-reduction method, which closely follows the approach in [14: Blanchet and Glynn]. This randomized method produces an estimator that telescopes in expectation, resulting in bias which scales as the one of the largest possible batch, but with minibatch sizes that are typically much smaller. The exponential range of the batch size follows from the telescoping idea.

The bias-reduction approach is beneficial for privacy, because when minibatches are smaller, one can leverage privacy amplification by subsampling. However, since batch sizes are random, the classical advanced composition DP analysis does not suffice. Here is where we use the fully adaptive composition theorem [15: Whitehouse, Ramdas, Rogers and Wu]: in particular, since our batch randomization is predictable, we can define stopping times in such a way that we do not exceed the privacy budget. This however introduces challenges in the SGD analysis, which are addressed by the boosting procedure.

We will include a better detailed overview of this algorithm and its analysis in the revision.

Questions

About DP-SCO results. Due to space limitations, all results for DP-SCO were deferred to Appendix G. In the final version of the paper we will include the main results from that section (particularly, Appendix G.2).

1. Yes. As pointed out in Remark 2.1, in all of our upper bounds we can replace the set of sparse vectors by a scaled $\ell_1$-ball. This set is a more robust way to quantify sparsity, as known from the compressed sensing literature.

2. $p_n$ is the probability of choosing a batch size $2^{n+1}$, i.e., $p_n=C_M/2^n$ (where $C_M$ is a normalizing constant). This is explained in lines 233-236, but we will make it explicit in the pseudocode to avoid confusion.

3. Random batch sizes allow bias reduction with smaller minibatches, which are amenable for privacy amplification by subsampling. Using a full batch estimator would incur similar bias, but no privacy amplification. We will make sure to expand on this important aspect.

4. Thank you. We found an incorrect indexing: $[1:t-1]$ instead of the correct $[0:t-1]$.

5. Apologies for causing confusion: we simply wrote the same event in two different ways, i.e., $\{t\leq T\}$ and $\{T\geq t\}$. In the revision, we will retain the same notation. In the first step we use the regret bound for biased SGD, and in the second step we write the finite sum from $0$ to $T$ as a series with zero terms (due to the indicator) for $t>T$. Please let us know if more clarification is needed.

6. We are not sure which part of the paper you are referring to. Can you please let us know, and we can clarify it accordingly?

7. Please see answer 3 above.

8. $\\{ \cal F_t \\}_{t\in\mathbb{N}}$ is the natural filtration, i.e., ${\cal F}_t = \sigma((x^s), {s \leq t})$. We will add a clarification of this in the revision.

9. The sources of randomness used in Lemma 5.2 are only the batch size r.v. N and the DP noise used to compute ${\cal G}(x)$. While we could have stated Lemma 5.2 for an iterate $x^t$ (and correspondingly condition on ${\cal F}_{t-1}$), we believe the current presentation of this lemma is cleaner, and avoids unnecessary notation.