Differentially Private Clipped-SGD: High-Probability Convergence with Arbitrary Clipping Level

We sincerely thank the reviewer for the thoughtful and highly positive evaluation of our work. We are especially grateful for the recognition of the significance, originality, and clarity of the theoretical contributions, as well as the emphasis on how the work advances the understanding of DP-Clipped-SGD in high-probability settings. Below, we address your helpful suggestion.

Comment: Some of the theoretical results are quite dense, and the paper would benefit from an informal summary of the key takeaways — especially the regimes where the results offer improvements over prior work.

Response: Thank you for this excellent suggestion. We fully agree that providing an informal summary would enhance the accessibility of our results. In the final version of the paper, we will add:

• A concise and intuitive summary at the end of Section 4 (right after new paragraph about the detailed comparison with Koloskova et al. (2023) that we provided in our response to Reviewer hmsX), highlighting the key insights behind the convergence bounds in both the convex and non-convex settings.

• Clear interpretations of how our results compare to prior work under different clipping and privacy regimes (e.g., fixed vs. growing clipping level, zero vs. non-zero DP noise).

Many thanks to the authors for kindly addressing all my concerns! I’m happy with the current score and would like to keep it as is.

We thank the reviewer for the thoughtful review and helpful suggestions. We appreciate your recognition of the significance of our contribution in handling heavy-tailed noise with a fixed clipping threshold under differential privacy (DP). Below, we address your concerns and suggestions in detail.

Q1: The major weakness of the paper is that the final bounds do not decrease with the number of iterations. If we see the smoothness parameters and the differential privacy parameter as constants, the upper bounds for private learning are of constant order, and therefore vacuous.

A1: Thank you for raising this important point. Indeed, our high-probability results in the DP setting show convergence to a non-vanishing neighborhood — a common (Koloskova et al., 2023) and even unavoidable (Allouah et al., 2023) phenomenon in differentially private optimization. This neighborhood size depends on the fixed clipping threshold $\lambda$ and the magnitude of DP noise $\sigma_\omega$, which itself scales as $\sigma_\omega = \mathcal{O}\left(\frac{\lambda}{\epsilon} \sqrt{K \ln(K/\delta) \ln(1/\delta)}\right)$.

Moreover, even in the non-DP setting, i.e., when $\sigma_\omega = 0$, our high-probability bounds imply that Clipped-SGD with fixed clipping level $\lambda$ also converges only to some neighborhood depending on $\lambda$. From this perspective, our bound is aligned with the lower bound from Koloskova et al. (2023), yet there are certain differences that we discuss at the end of our reply.

Q2: Under the assumptions in the paper, it is not even clear whether these bounds are better than the quality of the initial point $x_0$, as we have $f(x_0) - f(x^\ast) \leq L / 2R^2 / 2$, and a trivial algorithm that outputs $x_0$ is differentially private.

A2: Thank you for this important question. Our results indeed imply a nontrivial improvement over the initial point $x_0$ when the step size is appropriately chosen to balance optimization and privacy noise. As one can see from Corollary 4.2, the terms from (11) and (12) are decreasing in $K$. Next, the terms from (13) can be decreased by increasing $\lambda$ or by decreasing $\sigma$, which can be achieved using mini-batching even for the heavy-tailed noise (Kornilov et al., 2023). Finally, the DP-neighborhood terms from (14) can be made smaller via sacrificing the privacy, i.e., via an increase of $\epsilon$.

We will add this discussion in the final version.

Q3: The bounds in DP results (e.g. Corollary 4.3) are generally difficult to parse. It is better to simplify the bound under appropriate sample size conditions and parameter selections, to see the magnitude of the bounds w.r.t. problem parameters.

A3: Thank you for this suggestion. We agree that the current presentation of Corollary 4.3 could be more digestible. In the final version, we will provide simplified expressions under different conditions on $\epsilon$ (“small” and “large” $\epsilon$) and $\sigma$. This should help make the implications of our results more transparent.

Q4: In order for the paper to be publishable, the authors need to address a basic question: is it possible at all to establish convergence results (i.e. the bound goes to 0 as K goes to infinity) in the heavy-tailed DP-clipped-SGD settings?

A4: This is a deep and important question. In our setting, achieving convergence to zero requires either:

Increasing the clipping threshold $\lambda$ with $K$ — which breaks compatibility with standard DP mechanisms, or

Decreasing the noise magnitude $\sigma_\omega$ with $K$ — which would compromise the $(\epsilon, \delta)$-DP guarantee.

Under fixed clipping and fixed privacy parameters, convergence to the exact optimum is provably impossible (Allouah et al., 2023; Koloskova et al., 2023), and this is inherent to the privacy-utility tradeoff. However, if one relaxes privacy slightly, it may be possible to derive bounds that decay with $K$ under milder assumptions.

We will expand the discussion in the limitations section to highlight these theoretical challenges and explicitly mention this impossibility under fixed $\lambda$ and fixed DP parameters.

Comparison with the results by Koloskova et al. (2023)

Motivated by the questions raised by the reviewer, we plan to extend the discussion of the obtained results in the final version of our paper. In particular, we promise to include the following text comparing our results in the non-convex case with closely related ones from Koloskova et al. (2023).

We start with the corollary of Theorem 4.4.

Corollary 4.5. Let the assumption of Theorem 4.4 hold, and $\gamma$ is chosen as the minimum of (24). Then, with probability at least $1-\beta$

$\min_{t\in [0,K]} \| \| \nabla f(x^t) \| \|^2 \leq \mathcal{O}\left(\max\left\lbrace (27), (28), (29), (30) \right\rbrace\right),$

where

\frac{L\Delta}{K} + \frac{L^2\Delta^2}{\lambda^2 K^2} \tag{27} \sqrt{L\Delta}\lambda^{1 - \alpha/2}\sqrt{\frac{(\sigma^\alpha + \zeta_\lambda^\alpha)\ln(K/\beta)}{K}} + \frac{L\Delta(\sigma^\alpha + \zeta_\lambda^\alpha)\ln(K/\beta)}{\lambda^\alpha K} \tag{28} \frac{\sqrt{\Delta L}(\sigma^\alpha+\zeta_\lambda^\alpha)\left(\frac{\sqrt{L\Delta}}{\lambda}+\frac{\lambda^{\alpha-1}\zeta_\lambda}{\sigma^\alpha+\zeta_\lambda^\alpha}+\left(\sigma^\alpha+\zeta_\lambda^\alpha\right)^{\frac{-1}{\alpha}}\right)}{\lambda^{\alpha-1}}+\frac{\Delta L(\sigma^\alpha+\zeta_\lambda^\alpha)^2\left(\frac{\sqrt{L\Delta}}{\lambda}+\frac{\lambda^{\alpha-1}\zeta_\lambda}{\sigma^\alpha+\zeta_\lambda^\alpha}+\left(\sigma^\alpha+\zeta_\lambda^\alpha\right)^{\frac{-1}{\alpha}}\right)^2}{\lambda^{2\alpha}} \tag{29} \frac{\sigma_\omega\sqrt{dL\Delta \ln(K/\beta)}}{\sqrt{K}} + \frac{\sigma_\omega^2 dL\Delta \ln(K/\beta)}{\lambda^2 K}. \tag{30}

Koloskova et al. (2023) derive their in-expectation convergence result under the $(L_0,L_1)$-smoothness assumption and the $\sigma^2$-uniformly bounded variance assumption (i.e., Assumption 2.4 with $\alpha = 2$), for DP-Clipped-SGD with mini-batching. For ease of comparison, we consider the special case $L_1 = 0$ and $L_0 = L$, which corresponds to standard $L$-smoothness. Moreover, for simplicity, we assume a mini-batch size of $1$. In this setting, the result from Koloskova et al. (2023, Appendix C.4.2) for DP-Clipped-SGD can be written as follows: if $\gamma \leq 1/9L$, then

$\min\limits_{t\in [0,K]}\left(\mathbb{E}\left[\|\| \nabla f(x^t) \|\|\right]\right)^2 \leq \mathcal{O}\left(\frac{\Delta}{\gamma K} + \frac{\Delta^2}{\lambda^2\gamma^2K^2} + \gamma L \sigma^2 + \min\left\lbrace\sigma^2, \frac{\sigma^4}{\lambda^2}\right\rbrace + \gamma L d\sigma_\omega^2 + \frac{\gamma^2 L^2 d^2 \sigma_\omega^4}{\lambda^2} \right).$

The structure of our bound is quite similar. Specifically, the terms from (27) correspond to the convergence of DP-Clipped-SGD in the noiseless regime ($\sigma = \sigma_\omega = 0$) and match the $\mathcal{O}\left(\frac{\Delta}{\gamma K} + \frac{\Delta^2}{\lambda^2\gamma^2K^2}\right)$ part when $\gamma = \Theta(1/L)$. Next, the terms in (28) serve as analogs of the $\mathcal{O}(\gamma L \sigma^2)$ term. The leading term in (28) matches the $K$-dependence of $\mathcal{O}(\gamma L \sigma^2)$ for $\gamma = \Theta(1/\sqrt{K})$. However, these terms also depend on the clipping level $\lambda$, which arises from our high-probability convergence analysis and the presence of heavy-tailed noise.

The key difference lies in the terms stemming from the inherent bias of Clipped-SGD (Koloskova et al., 2023, Theorems 3.1–3.2) and the DP noise. In our result, these bias terms appear in (29), while the corresponding term in Koloskova et al. (2023) is $\mathcal{O}\left( \min\left\lbrace\sigma^2, \frac{\sigma^4}{\lambda^2}\right\rbrace \right)$. As shown in Table 2, in the special case $\lambda > 4\sqrt{L\Delta}$, the bias terms (i.e., the convergence neighborhood when $\sigma_\omega = 0$) in (29) reduce to $\mathcal{O}\left(\sqrt{L\Delta}\frac{\sigma^\alpha}{\lambda^{\alpha-1}} + L\Delta \frac{\sigma^{2\alpha}}{\lambda^{2\alpha}}\right)$. Assuming $\lambda > \sigma$ for simplicity, the term from Koloskova et al. (2023) becomes $\mathcal{O}\left(\frac{\sigma^4}{\lambda^2}\right)$, which is strictly larger than the second term and strictly smaller than the first term in our bound when $\alpha = 2$. Furthermore, in this regime, both terms in our bound decrease with increasing $\alpha$, suggesting that the convergence neighborhood grows with the heaviness of the noise. Whether the bound in (29) is tight and whether improvements are possible in other regimes remain open questions.

Finally, ignoring logarithmic factors (introduced by the high-probability analysis), the DP-noise-related terms in our bound (30) are $\tilde{\mathcal{O}}\left(\frac{\sigma_\omega\sqrt{dL\Delta}}{\sqrt{K}} + \frac{\sigma_\omega^2 dL\Delta}{\lambda^2 K}\right)$, while the corresponding terms in Koloskova et al. (2023) are $\mathcal{O}\left(\gamma L d\sigma_\omega^2 + \frac{\gamma^2L^2d^2\sigma_\omega^4}{\lambda^2}\right)$. Setting $\gamma = \sqrt{\Delta/(LdK)}$ yields the latter bound as $\mathcal{O}\left(\frac{\sigma_\omega \sqrt{dL\Delta}}{\sqrt{K}} + \frac{\sigma_\omega^4 d L\Delta}{\lambda^2 K}\right)$, which matches (30) up to logarithmic factors.

References:

Allouah et al. “On the privacy-robustness-utility trilemma in distributed learning”. ICML 2023

Koloskova et al. “Revisiting gradient clipping: Stochastic bias and tight convergence guarantees”. ICML 2023

Kornilov et al. “Accelerated zeroth-order method for non-smooth stochastic convex optimization problem with infinite variance”. NeurIPS 2023

Thank the authors for clarifying the finite-sum results. The result is non-vacuous under such a setting, with $\sigma_w \asymp \frac{\lambda}{n \varepsilon} \sqrt{K}$. In ML problems, we always want the error to decay with more data, and this corollary seems the only non-vacuous result in the paper.

Currently, this result is hidden in the text remarks, and is not rigorously proved (or even stated). I would suggest the authors to re-write the entire paper under this finite-sum setting and highlight the convergence rate in terms of $n$ (and choice of algorithmic parameters including $K$, as a function of $n$).

Besides, it is well-known in DP optimization literature that private SGD algorithms can achieve small population-level loss for minimizing expected loss under random data (see e.g. Bassily et al., (2019), Private Stochastic Convex Optimization with Optimal Rates). So even if we use private SGD to minimize empirical loss, it is important to see how the population loss of the private clipped SGD output decay as a function of sample size $n$.

We thank the reviewer for their thoughtful comments, positive evaluation of our work, and recognition of its broader significance and clarity. Below, we address all the raised questions and concerns.

Q1: I have somewhat hard time recovering the main claim, the $\mathcal{O}(1/\sqrt{K})$ convergence rate, from the various theorems. Maybe it can be derived somewhat easily from the results, but it would help readability a lot if authors could connect the theorems to this claim.

A1: We thank the reviewer for pointing this out. The correct convergence rate (to a neighborhood) is $\mathcal{O}(\sqrt{\ln(K/\beta)/K})$, which includes an additional logarithmic factor due to the high-probability nature of the bound. We will revise the statement in the Conclusion section accordingly, replacing $\mathcal{O}(1/\sqrt{K})$ with the more precise expression $\mathcal{O}(\sqrt{\ln(K/\beta)/K})$.

Q2: Regarding the convergence rate in (9). You suggest that having a fixed clipping bound $\lambda$ leads to $\mathcal{O}(\sqrt{\ln(K/\beta)/K})$ rate. Can you clarify this? Would seem to me, that if with a particular $\lambda$ the learning rate is the third argument of eq. (8), you would cancel all the $K$ from eq. (9).

A2: Thank you for this insightful observation. As noted in lines 236–237 of the paper, we state that the convergence rate is $\mathcal{O}(\sqrt{\ln(K/\beta)/K})$, but we also clarify in lines 238–239 that this refers to convergence to a neighborhood whose size depends on $\lambda$, $\sigma$, $R$, and $\sigma_\omega$.

The reviewer is correct that when the third term in the step-size bound (8) is the dominant one, then all the $K$ factors in (9) cancel out, and the optimization error does not decrease with $K$. In this regime, the algorithm does not converge to the global optimum but rather to a fixed neighborhood around it.

This neighborhood is quantified explicitly in Corollary 4.2 (eq. (13)) and depends on the problem parameters, particularly on the fixed clipping threshold $\lambda$ and the noise level $\sigma$. Furthermore, when $\sigma_\omega = \mathcal{O}\left(\frac{\lambda}{\epsilon} \sqrt{K \ln(K/\delta) \ln(1/\delta)}\right)$, the neighborhood size also involves a growing term, as described in eq. (14).

We will revise the final version to make this point more explicit and clearly distinguish the rate to the neighborhood from the size of the neighborhood itself.

Q3: I'm a bit puzzled by the convergence rate arising from Corollary 4.3. The term (18) in the maximum seems to diverge w.r.t. $K$, so I cannot see how you could obtain the rates presented in Table 1.

A3: Excellent observation—thank you for catching this. You are correct that the last term in eq. (18) includes logarithmic factors in $K$, $\beta$, and $\delta$, and thus does not decrease with $K$. In fact, it slowly grows, i.e., polylogarithmically. However, in Tables 1 and 2, we provide the results for the non-DP case, i.e., when $\sigma_\omega = 0$. In the presence of non-trivial DP noise, Corollary 4.3 provides explicit upper bounds for two representative regimes corresponding to “large” and “small” clipping levels. While these do not always yield decaying rates with $K$, they still characterize the convergence to a meaningful neighborhood that depends on privacy and problem parameters. We note that similar bounds can be derived for other clipping regimes as well, though they lead to more complex expressions and were omitted for clarity. In the final version, we will clarify in the text and table captions that the tabulated results refer to the $\sigma_\omega = 0$ case.

Q4: On line 262, you write $\epsilon = \mathcal{O}(q^2 K)$, but I think it should be $\epsilon = \mathcal{O}(q\sqrt{K})$.

A4: Thank you for pointing this out. In line 262, we refer to Theorem 1 from Abadi et al. (2016), which gives a sufficient condition for applying the moments accountant: $\epsilon \leq c_1 q^2 K$ for some constant $c_1$. This condition ensures that the moments accountant approach provides a valid $(\epsilon, \delta)$-DP guarantee.

References:

Abadi et al. “Deep learning with differential privacy”. Proceedings of the 2016 ACM SIGSAC conference on computer and communications security