Clip Body and Tail Separately: High Probability Guarantees for DP-SGD with Heavy Tails

Thank you for your comments.

$**Presentation**$: We will prioritize the definition of `gradient noise' and more clearly emphasize that the core of our problem focuses on the heavy-tail assumption under sampling randomness.

$**Reference**$: We list these references to demonstrate that the clipping thresholds in SGD tend to be larger compared to those in DPSGD and to highlight the gap in the application of gradient clipping between SGD and DPSGD. We will revisit the correctness of our references.

$**Motivation**$: Our motivation is to divide gradient clipping into two parts under the heavy-tailed assumption. We validated the effectiveness of our approach using the experimental setup in [2], demonstrating that relying solely on a sufficiently small clipping threshold does not achieve optimal performance. In fact, if DPSGD operates without gradient clipping, its convergence can be significantly improved. However, small clipping thresholds inevitably introduce considerable clipping bias. Our proposed method seeks to strike a more precise balance between clipping bias and utility of DPSGD, particularly in heavy-tailed scenarios.

$**Contribution**$: Our contribution is not limited to the logarithmic terms. We first propose a tight high-probability bound for DPSGD, where the logarithmic terms are close to the current SOTA high-probability bounds for SGD. We highlight that optimizing the logarithmic terms in high-probability bounds is not easy. Additionally, our DC-DPSGD (Theorem 5.4) improves the original DPSGD bound (Theorem 4.1), with an exponential improvement in both the logarithmic terms and the broken probability $\delta$, which represents a significant contribution in high-probability bounds.

$**Baseline and Code**$: More experimental details and code links can be found in Appendix G.1. We will also include additional experiments related to the baseline papers you mentioned.

Thank you for your appreciation of our work and detailed comments. We will response your concerns.

Weaknesses 1 and Question 2: We employ subspace identification to differentiate between light-body and heavy-tail gradients. This involves performing private sorting based on the deviation of normalized per-sample gradients (capturing directional information) from a heavy-tailed distribution, which allows us to characterize the samples. When the underlying distribution of $\widehat{\mathbf{g}}$ aligns more closely with that of $V_{t,k}$ (which can be viewed as eigenvectors), their trace (the sum of inner products) becomes larger. The intuition is analogous to how principal components in PCA maximize the eigenvalue~(inner product) of the original vector. We recognize this as a heuristic method, and we provide a theoretical upper bound on the error of the approach in Section 5.1. We acknowledge that there is potential for improvement in developing more precise discriminative methods and would welcome further discussion on this topic.

Regarding Question 2, in heavy-tailed scenarios, the $l_2$ norm of per-sample gradients may be unbounded. Performing private sorting in such cases would require infinite sensitivity, which makes noise addition infeasible and impractical. In contrast, our subspace identification method, which relies on normalized eigen sorting, effectively mitigates this issue and ensures feasibility under differential privacy constraints.

Question 1& Question 4: We thank the reviewer for pointing out these issues. In the revised version, we will define these variables and provide clearer and more consistent explanations.

Question3: We will add the subscript $i$ to better illustrate the discrimination for per-sample gradients.

Question5: We appreciate the reviewer’s insightful question. When $p$ approaches 0, it represents a special case under the light-tail assumption, which aligns with the gradient noise assumption used by mainstream DPSGD approaches and their corresponding theoretical results for high-probability bounds. However, under the heavy-tail assumption, $p$ actually depends on the true heavy-tailed magnitude of the data distribution, which generally lies around 10%. In other words, the improvement depends on the actual heavy-tailed nature of the data distribution.

Question6: We thank the reviewer for the careful observation, and we will correct this in the revised version.

We thank the reviewer for the detailed comments. We will further explain our contributions in theory and compare our methods with existing subspace-based DPSGD work.

$**Weaknesses**$.

Point 1: The mentioned work based on DP-SPIDER, such as [1-2]. Their bounds are indeed $\mathcal{O}({\frac{d^{\frac{2}{3}}}{n\epsilon}})$ and the better $\mathcal{O}({\frac{d^{\frac{2}{3}}}{(n\epsilon)^{\frac{2}{3}}}\textasciicircum\frac{d^{\frac{1}{6}}}{n\epsilon}})$, but the condition for their bounds to be better than our stated SOTA result $\mathcal{O}({\frac{d^{\frac{1}{4}}}{(n\epsilon)^{\frac{1}{2}}}})$ is $n\epsilon>d$, which is difficult to hold when the model dimension is large. In our work, we focus more on the general case, where the SOTA DPSGD bound holds without the condition $n\epsilon>d$, where $\mathcal{O}({\frac{d^{\frac{1}{4}}}{(n\epsilon)^{\frac{1}{2}}}})$ is the current best result. Furthermore, our contribution is not limited to the logarithmic terms; we are the first to propose a high-probability bound for DPSGD, where the logarithmic terms are close to the current SOTA high-probability bounds for SGD, which is a very tight bound. Optimizing the logarithmic terms in high-probability bounds is not an easy task. Additionally, our DC-DPSGD (Theorem 5.4) improves the original DPSGD bound (Theorem 4.1), with an exponential improvement in both the logarithmic terms and the broken probability $\delta$, which represents a significant contribution in high-probability bounds.

[1] Private (stochastic) nonconvex optimization revisited: Second-order stationary points and excess risks.

[2] How to Make the Gradients Small Privately: Improved Rates for Differentially Private Non-Convex Optimization.

Point 2: We clarify the distinction from subspace-based DPSGD. They use public data to generate a low-rank subspace, thereby reducing the DP noise to low-rank dependencies and avoiding the severe dependence on model parameters' $d$-dimensionality. Our approach, on the other hand, uses subspace classification to differentiate light-tail and heavy-tail per-sample gradients and improve the gradient clipping in DPSGD instead of the dimension dependence of DP noise, without introducing additional public data. Both theoretically and practically, our approach is orthogonal to subspace-based DPSGD. We will further validate through experiments that our algorithm outperforms subspace-based DPSGD.

Point 3: We will provide additional experiments regarding subspace-based DPSGD.

$**Questions**$.

Q1: Our analysis is strictly based on $T$ iterations, but it can be easily extended to $E$ epochs, or simply by substituting $T=T*E$.

Q2: The symbol $\mathbf{g}^{tail}$ means the heavy-tailed gradient with the larger (top-$p\%$) sorted trace, and we employ the large clipping threshold $c_1$ to clip them, instead of using the single common clipping threshold $c_2$ for the normal light body gradient.

Q3: The DP sorting we designed is similar to the functionality of DP top-k and DP SVT, that is, sorting a set of values $V=[v1,v2,...,v_{n}]$ after adding noise. Since their divergence or sensitivity depends on how the sorting result changes when one data point is modified, the proof process needs to consider all such scenarios. Our key aim is to prove that TraceSorting$\circ$GradientPerturbation(GP) satisfys DP. We will appropriately simplify the proof and provide the core parts for your reference.

Thank you for appreciating our work. We will answer the weaknesses and insightful questions.

$**Weaknesses**$.

Point 1: We believe that the main additional computational complexity arises from the calculation of the projection subspace. Generally, this can be mitigated by using power PCA techniques to reduce computational overhead and improve the quality of projection reconstruction. In our experiments, we primarily used the SVD package provided by PyTorch for the computation. By adjusting the `full matrices' parameter, we can significantly alleviate the computation time, reducing it from the original time dependence on $\mathcal{O}(d^2)$ to $\mathcal{O}(d*B)$, where $d$ is model parameters and $B$ is the batch size.

Point 2: We introduced a larger $c_1$ compared to the original $c_2$ as the heavy-tailed clipping threshold. We provide a linear perspective that links the tuning of $c_1$ with $c_2$, (i.e., $c_1=10c_2$), meaning that only $c_2$ needs to be adjusted, similar to the original DPSGD. For other hyper-parameters, such as $\theta$ and $p$, their impact on the algorithm is limited and relatively insensitive within a certain range, as discussed in Experiment 6.2 and Appendix G.2.

$**Questions**$.

Q1: We believe that, based on a limited privacy budget, equal distribution is often a one-size-fits-all solution in experiments. However, upon closer theoretical analysis, there may be slight advantages in using the privacy budget more strategically in DPSGD perturbation. This is because the dependence on noise of DPSGD is $d$-dimensional, while the dependence on subspace identification is at a constant level.

Q2: We believe that label-based clipping thresholds could yield interesting results in the field of fairness. Discriminative clipping can assign more weight to sparse labels, helping to mitigate the issue of unfairness. We would be eager to explore this further.

We would like to thank the reviewer again for the comments.

Thank you for your review. We will address the your comments point-by-point.

$**Unclear relation to previous work**$. We argue that the work by Bu et al. focuses on small-norm gradients, as their optimization and analysis are based on the assumption of light-tailed gradient noise. Moreover, their specific clipping scheme, $\mathbf{g}=\frac{\mathbf{g}}{\Vert \mathbf{g}\Vert+\gamma}$ ($\mathbf{g}$ denotes per-sample gradient and $\gamma>0$ is a hyper-parameter), normalize every per-sample gradient to about 1 and sacrifices the information of large-norm gradients, while amplifying the energy of small-norm gradients. Our work aims to ensure that large-norm gradients are not excessively sacrificed during clipping.

$**Unclear claims and terminology**$. We thank the reviewer for careful reading.

Point 1-2: we will refine the Line 35 and 36 for clear claims.

Point 3: the symbol $c$ in Theorem 4.1 denotes clipping threshold. Our Theorem 4.1 specifically addresses classic DPSGD proposed by Abadi et al. (which employs Gaussian noise). Thus, in our bounds, we also interpret the privacy parameter $\delta$ as a high-probability form, as it essentially arises from the unbounded nature of Gaussian noise, and we share the symbol $\delta$ in our approach.

Point 4: we define $B$ as the batch size in Algorithm.1, $q=\frac{B}{n}$ as the sample ratio and $T$ as iterations in the context.

Point 5: the results of trace sorting are classified into light body or heavy tail gradients~(as detailed in Section 5.1). Then, based on the sorted and well classified gradients, we apply the large clipping threshold to the heavy tailed gradient and the small clipping threshold to the light body one. In addition, we perform the discriminative clipping at the level of per-sample gradient, but not the eigen-components of one gradient.

Point 6-7: we will address them in the Questions.

$**Informal privacy claims**$. We consider the symbol $\delta$ in the privacy parameter to be a type of high-probability bound parameter, as Gaussian-based DPSGD entails a certain failure rate. In the case of non-pure DP in Definition 3.1, the broken probability $1-\delta$ arises from the unbounded nature of Gaussian noise.

$**Experimental setting is not clearly explained**$. Due to the space limitations, we place the specific experimental details in Supplementary Material G.1, where the parameter settings of the baselines follows follow those provided in the original paper, while our parameters are based on extensive experimental searches and provide corresponding empirical guidance.

$**Minor**$. Thank you for the reviewer’s comments. We will address them one by one. Regarding the fourth point, we refer to $B$ as the batch size for the private dataset.