Smoothed Normalization for Efficient Distributed Private Optimization

Dear reviewer LMxv,

We appreciate your time, effort, and thoughtful feedback.

We thank you for your appreciation towards the contributions of our work on leveraging smoothed normalization and error feedback to design distributed algorithms with the first provable convergence under the privacy budget.

In the beginning of the paper, it said “no DP distributed method for smooth non-convex optimization problems”. However, to my knowledge, "DIFF2” paper cited in this work (published on ICML 2023) has discussed the problem for federated learning and provide a feasible framework. Can you explain more on the difference between DIFF2 paper and yours?

DIFF2 assumes both smoothness of objective functions and bounded gradient conditions to derive the convergence. Unlike DIFF2, DP-$\alpha$-NormEC achieves the utility guarantee under smoothness without bounded gradient conditions.

Next, on the one hand, DIFF2 uses local gradient differences $\nabla f_i(x^{k}) - \nabla f_i(x^{k-1})$, and, thus, requires computing two gradients at different points at every iteration. On the other hand, $\alpha$-NormEC privatizes the difference between the local gradient and memory vector $\nabla f_i(x^{k}) - g_i^{k}$. Moreover, while DIFF2 adds the private noise on the server, $\alpha$-NormEC adds the noise to the updates from the clients before being communicated to the server.

Although smoothed normalization is a promising approach to tackle the issue, the cited work Yang et al. (2022) looks plausible and is rejected by TMLR last year, which contains fatal errors (For more info, take a look this link https://openreview.net/forum?id=wLg9JrwFvL). Probably that paper is not a good work as a main citation in the introduction.

Thank you for pointing us out. We will remove Yang et al. (2022) as a main citation in the introduction section, but keep it in the related work section.

Besides dataset and model architecture, this work put too much experimental details to the appendix. For example, comparison to existing work like Clip21 is a good evidence to convince audience on the effectiveness of this work instead of only reading theoretical parts.

We agree with this suggestion. We will move results in the ablation study from the appendix into the main text, such as the results showing that $\alpha$-NormEC provides slightly strong convergence performance than Clip21 in both non-private and private settings.

This work just discusses the difference with pure clipping approach in the text rather than conducting any comparison experiments (not even mentioned in the appendix).

In Appendix H.2, we compare DP-SGD and $\alpha$-NormEC. Our results indicate that Error Compensation significantly improves over the baseline.

In the preliminaries, 3.3 discussed too much details in DP-SGG. The audience of this paper could DP-related researcher on ML, so DP-SGD probably is a default knowledge. I suggest to move details of DP-SGD in the appendix and mainly focuses on limitations.

Thank you for your suggestion. We will improve Section 3.3 by moving DP-SGD details to the appendix, allowing for a more detailed explanation of its convergence limitations. This revision will be included in the next version.

As discussed in the experimental design section, decode-only (e.g., transformer) models may be better than ResNet20 to produce convincing results to LLM-era researchers.

We appreciate your comment. We agree that DP-$\alpha$-NormEC will be of huge interest in private training of LLM models. We will provide additional experiments on training transformer models in the revised manuscript.

We hope these clarifications have sufficiently addressed your concerns, providing a clearer understanding of our study's contributions and implications. We are eager to engage in further discussion to resolve any remaining concerns. Please consider the score accordingly.

Best Regard,

Authors

Dear reviewer yzkj,

We appreciate your time, effort, and thoughtful feedback.

The proposed algo provides convergence guarantees (theoretically), but the baseline assumption is the objective functions' smoothness and bounded from below.

Our assumptions are standard for analyzing distributed algorithms on non-convex problems, e.g. by Nesterov et al. (2018) and [A]. Furthermore, in the context of differential privacy, we do not impose bounded gradients, which are restrictive but used by prior literature.

[A] Karimireddy, S. P., Kale, S., Mohri, M., Reddi, S., Stich, S., & Suresh, A. T. (2020, November). Scaffold: Stochastic controlled averaging for federated learning. In International conference on machine learning (pp. 5132-5143). PMLR.

​​>Weak empirical evaluation.

Although our main focus is on algorithmic development, our work contains an extensive experimental section that evaluates several algorithms in different settings, including the ablation studies of the design components of our method. Furthermore, our experimental setting is standard in the literature on differential privacy (Papernot et al., 2020; Li and Chi, 2023; Allouah et al., 2024). Can you elaborate? We will be happy to incorporate your constructive suggestions.

1- α-NormEC performance at low privacy budgets?

We ran $\alpha$-NormEC across a range of $\beta$ values in Figure 3, which shows a privacy-utility trade-off. Lower $\beta$ results in smaller added noise, resulting in higher privacy loss and decreased performance of the model. The effect of tuning $\beta$ was observed also for the non-private version of $\alpha$-NormEC (without DP noise). Furthermore, we performed additional comparisons of the methods for the private training, where DP-$\alpha$-NormEC significantly outperforms DP extension of Clip21. Kindly see the attached plot link.

2- How does α-NormEC compare to adaptive clipping? … there is no mention of adaptive or data-driven clipping techniques.

We develop distributed algorithms with the first provable convergence without relying on restrictive bounded gradient assumptions. Adaptive clipping is orthogonal to our work, due to smoothed normalization that removes the need to tune the private noise.

In Paragraph 3 of introduction, we reviewed adaptive clipping techniques, such as by Andrew et al., (2019), and recent results by Merad & Gaïffas (2023) and Shulgin & Richtárik (2024). Andrew et al., (2019) does not provide any guarantees we can compare to. Shulgin & Richtárik (2024) showed the first theoretical analysis only in the centralized (single node) case, and showed that SGD with Adaptive clipping suffers from a similar non-convergence issue as SGD with constant clipping (Koloskova et al., 2023). Moreover, Pichapati et al., (2019) considers coordinate-wise adaptive clipping for AdaCliP that is orthogonal to our work, and presents its analysis of the single-node case under the bounded gradient assumption, the condition our distributed algorithms do not require

3- Elaborate on computational and communication costs.

At every iteration, each client computes the local gradient, updates local memory $g_i^{k+1}$, and sends the privatized difference between the gradient and memory vector to the server. Then, the server performs averaging and sends the updated model back to the clients. There is no additional communication or computational overhead compared to distributed SGD.

4- Gradient sparsification as a comparison, and α-NormEC applied to non-iid data in FL?

Compression (Sparsification) techniques are complementary to our work, as compression does not preserve privacy. Sparsification does not guarantee bounded sensitivity and has to be combined with clipping or normalization for differential privacy. We believe $\alpha$-NormEC can be combined with compression to further improve communication efficiency while it preserves privacy. $\alpha$-NormEC with compression can be used to train over arbitrarily heterogeneous and non-iid data, thanks to error compensation mechanisms similar to EF21 that remove the uniformly bounded heterogeneity assumptions.

No Discussion of Momentum and Adaptive Learning Rates in DP-SGD.

We will add the discussion on techniques like momentum and step size DP-SGD in the revision as they can be beneficial for empirical performance. Error Compensation can be viewed as a variation of server momentum equivalent to classical heavy-ball momentum up to reparametrization [B] .

[B] Garrigos, Guillaume, and Robert M. Gower. "Handbook of convergence theorems for (stochastic) gradient methods." arXiv preprint arXiv:2301.11235 (2023).

Next, thank you for the typos and suggestions. We will reorganize the initial part of the paper and shorten the literature review to include more results in the main part.

We hope these clarifications have addressed your concerns. Please consider the score accordingly.

Best Regard,

Authors

Dear reviewer BGLy,

We appreciate your time, effort, and thoughtful feedback.

At every iteration, each client is computing a gradient at the same globally known point, x^k.

Could you please specify the federated methods? Because federated learning algorithms exchange the local model updates, not the gradients as required by $\alpha$-NormEC. However, $\alpha$-NormEC can be modified to FedAvg algorithms. The generalization of our methods to federated settings presents a challenging direction, as it requires modifications of our current analysis.

At line 267, the authors remark that the Clip21 algorithm from Clip21 algorithm achieves 1/K, I assume they mean 1/sqrt{K} as per the discussion in the Appendix?

We apologize for this misunderstanding. At line 267, Clip21 attains the $\mathcal{O}(1/K)$ convergence of the squared gradient norm $\|| \nabla f(x) \||^2$. This statement is equivalent to the $\mathcal{O}(1/\sqrt{K})$ convergence in the gradient norm of Clip21 in Appendix E.

We will revise the discussion at Line 267.

How is the initial gradient being made private?

Privatization of the difference between the local gradient and memory: As the initial gradient $\nabla f_i(x^0)$ is not shared with the server, it is not needed to be privatized. Only the difference between local gradient and memory vector at the initialization $\nabla f_i(x^0) - g_i^0$ is privatized and sent to the server with the gaussian mechanism.

Initialization of the memory vectors: The memory vector $\hat{g}^0$ on the server is initialized as $\frac{1}{n} \sum_{i=1}^n g_i^0$ (Line 948). Our analysis from Lemma 3 allows easy extension to arbitrary initialization,e.g. $\hat{g}^0 = \frac{1}{n}\sum_{i=1}^n g_i^0 + e$. Here, this additional error term $e$ can be small if we privately estimate the mean of vectors $g_i^0$, which incur once and thus a small privacy loss (compared to the iterative process). Furthermore, secure aggregation techniques can eliminate this error entirely. For instance, if clients agree on a shared random seed, they can add and subtract cryptographic noise to their local memory vectors, respectively, without affecting the average. Consider two clients with local memory vectors $g_1^0$ and $g_2^0$. The first client can add cryptographic noise $h$ to $g_1^0$ and the second client subtract $h$ from $g_2^0$. This would protect the vectors $g_i^0$ from the server but the average would be exactly the average as $\frac{1}{2}(g_1^0 + h) + \frac{1}{2}(g_2^0 - h) = \frac{1}{2}(g_1^0 + g_2^0)$.

Relatedly, I have some concern with the premise of the paper. The authors perform all their updates using gradient differences, and also assume the loss is smooth. In the DP setting, why would we ever need to clip if this were the case? The sensitivity of the updates is already bounded by smoothness.

We assume smoothness of the loss function $\||\nabla f(x)-\nabla f(y)\|| \leq L\||x-y\||$, the most standard assumption in non-convex optimization literature. It does not imply bounded sensitivity of the gradient $\||\nabla f(x)\||$ unless the domain is bounded ($\||x-y\|| \leq \mathcal{D}$) which is a restrictive condition. Existing literature considers the convergence of DP distributed algorithms for minimizing smooth losses by further imposing bounded gradient conditions. This restricts the class of optimization problems. These bounded gradients can be achieved by assuming either Lipschitz continuous functions (as in [1]) or bounded domain. These conditions allow us to bound the sensitivity of the updates without applying clipping or normalization. However, this sensitivity is impossible to compute for many loss functions used in training machine learning models. Even when it can be estimated, its bound is often overly pessimistic, thus leading to excessively large DP noise and thus significantly degrading the algorithmic convergence performance.”

Further, the authors claim their result is the first convergence rate for DP distributed learning. But their algorithm involves communicating x^k to each client every round.

We believe there is a misunderstanding. Our algorithms communicate the normalized gradient difference $N_{\alpha}(\nabla f_i(x^k)-g_i^k)$, not the iterates $x^k$. Furthermore, $\alpha$-NormEC attains convergence under privacy budget for minimizing smooth functions without assuming bounded gradients and/or ignoring the effect of normalization, which existing literature often requires.

To our knowledge, only Das et al. (2022) and Li et al. (2024) analyze DP federated methods without restrictive bounded gradient assumption. However, these algorithms (Algorithm 1 of Das et al. (2022)) with one local step (E=1) result in DP distributed clipped gradient methods. These algorithms using clipping/normalization even without the DP noise do not converge for simple examples (see Section 3.4). To fix the convergence issue, we leverage error feedback.

Best regards,

Authors

Dear reviewer zAsL,

We appreciate your time, effort, and thoughtful feedback.

Q1. It is not obvious why it is possible to pick and in Corollary 1 to ensure that is very small.

We would like to clarify your misunderstanding. We can initialize $x^0,g_i^0 \in \mathbb{R}^d$ to ensure that $\|| \nabla f_i(x^0)-g_i^0 \||$ is small. For instance, we can choose $x^0$ to be any vector, and $\nabla f_i(x^0)$ does not need to have a small Euclidean norm. Then, we can set $g_i^0=\nabla f_i(x^0) + e$ where $e = (D/\sqrt{K+1}, 0, \dots, 0)$ with any $D>0$ and any total iteration number $K$, and our condition naturally satisfies $\||\nabla f_i(x^0) - g_i^0 \||= D/\sqrt{K+1}$.

We will include this discussion after Corollary 1 into the revised manuscript.

Could the authors comment on the feasibility of this? To me, it seems like the following inequality in the proof sketch is very loose when we are close to a stationary point,

We kindly disagree that our proof is loose. Existing convergence analysis of Clip21 cannot be applied to prove its convergence in the private setting. This motivates us to redesign distributed algorithms using normalization, instead of clipping, to achieve the first provable utility guarantee in the private setting under smoothness without bounded gradient conditions. Therefore, our approach for bounding $\psi^k := \|| \nabla f_i(x^k)-g_i^k \||$ differs significantly from Clip21, which is heavily based on EF21. We derive the induction proof showing the monotonicity of $\psi^k$. This novel condition is less demanding/restrictive than strong contractivity of $\psi^k$, i.e. $\psi^{k+1} \leq (1-q) \psi^k, \forall q \in (0, 1]$, which Clip21 and EF21 rely on for variance-reduced Lyapunov-based analysis.

the choice of $\beta$ after Corollary 1 also depends on the same function sub-optimality. The authors should remove this statement, unless I am missing something?

Since $\|| \nabla f_i(x^0)-g_i^0 \||$ can be made small by choosing $x^0,g_i^0\in\mathbb{R}^d$, we have $\|| \nabla f_i(x^k)-g_i^k \||\leq \max_i \|| \nabla f_i(x^0)-g_i^0 \||$ that can be made small. This inequality, and our step-size rule do not need the knowledge of the function suboptimality gap, i.e. $f(x^0)-f(x^\star)$. This is in stark contrast to Clip21, where its step-size rule depends on not only the function suboptimality gap but also $C_1=\max _{i \in[1, n]} \|| \nabla f_i(x^0)\||$. Unlike $\|| \nabla f_i(x^0)-g_i^0 \||$ in $\alpha$-NormEC, $C_1$ in Clip21 cannot be made small easily.

This implies that the privacy-utility trade-off offered by the analyzed algorithm is very poor

Thank you for pointing out our impreciseness. We agree that in the private setting, $R$ cannot be made arbitrarily small, e.g. R goes to zero. We will remove the discussion after Corollary 2, which states that as $R\rightarrow 0$, $\alpha$-NormEC achieves the utility bound of $\mathcal{O}\left( \Delta \sqrt[4]{ \frac{d\log(1/\delta)}{n\epsilon^2} } \right).$

Yes, the experiments look alright, but I am not convinced that the method is significantly better than Clip21 based on the experiments in Appendix H.4. I believe these experiments should have been included in the paper, and the fact the empirical difference between the two algorithms not high be discussed as a limitation.

We kindly disagree as our main focus is on private training. First, our method has proved convergence guarantees unlike Clip21 in the private training. Second, we do not claim that our method outperforms Clip21 in the non-private setting; however, Table 3 shows that $\alpha$-NormEC achieves slightly higher accuracy than Clip21 for most values of $\beta \in \{0.01, 0.1, 1\}$.

We performed additional comparisons in the private training, where DP-$\alpha$-NormEC significantly outperforms DP extension of Clip21 (which does not have convergence guarantees in the private setting). Kindly see the attached plot link.

Why would restricting the data heterogeneity lead to vacuous bounds?

Bounded heterogeneity $\delta:=\|| \nabla f_i(x) - \nabla f_j(x)\||$ is an unrealistic condition, as heterogeneity can be arbitrarily large in practice. As $\delta$ grows, any convergence bounds that depend on $\delta$ can be very loose (vacuous bounds). This implies that the corresponding algorithms do not converge. Furthermore,the bounded gradient assumption implies bounded heterogeneity. We kindly refer to Khaled et al. (2020) for the discussions in more detail.

Furthermore, thank you for spotting the typos. We will fix them in the revision.

We hope these clarifications have sufficiently addressed your concerns, providing a clearer understanding of our study's contributions and implications. We are eager to engage in further discussion to resolve any remaining concerns. Please consider the score accordingly.

Best regards,

Authors