LoCoDL: Communication-Efficient Distributed Learning with Local Training and Compression

Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 18:26:49

Abstract: In $D$istributed optimization and $L$earning, and even more in the modern framework of federated learning, communication, which is slow and costly, is critical. We introduce LoCoDL, a communication-efficient algorithm that leverages the two popular and effective techniques of $Lo$cal training, which reduces the communication frequency, and $Co$mpression, in which short bitstreams are sent instead of full-dimensional vectors of floats. LoCoDL works with a large class of unbiased compressors that includes widely-used sparsification and quantization methods. LoCoDL provably benefits from local training and compression and enjoys a doubly-accelerated communication complexity, with respect to the condition number of the functions and the model dimension, in the general heterogenous regime with strongly convex functions. This is confirmed in practice, with LoCoDL outperforming existing algorithms.

Main paper: 
 introduction: 
 Performing distributed computations is now pervasive in all areas of science. Notably, Federated Learning (FL) consists in training machine learning models in a distributed and collaborative way (Konečný et al., 2016a,b; McMahan et al., 2017; Bonawitz et al., 2017) . The key idea in this rapidly growing field is to exploit the wealth of information stored on distant devices, such as mobile phones or hospital workstations. The many challenges to face in FL include data privacy and robustness to adversarial attacks, but communication-efficiency is likely to be the most critical (Kairouz et al., 2021; Li et al., 2020a; Wang et al., 2021) . Indeed, in contrast to the centralized setting in a datacenter, in FL the clients perform parallel computations but also communicate back and forth with a distant orchestrating server. Communication typically takes place over the internet or cell phone network, and can be slow, costly, and unreliable. It is the main bottleneck that currently prevents large-scale deployment of FL in mass-market applications.Two strategies to reduce the communication burden have been popularized by the pressing needs of FL: 1) Local Training (LT), which consists in reducing the communication frequency. That is, instead of communicating the output of every computation step involving a (stochastic) gradient call, several such steps are performed between successive communication rounds. 2) Communication Compression (CC), in which compressed information is sent instead of full-dimensional vectors.We review the literature of LT and CC in Section 1.2.We propose a new randomized algorithm named LoCoDL, which features LT and unbiased CC for communication-efficient FL and distributed optimization. It is variance-reduced (Hanzely & Richtárik, 2019; Gorbunov et al., 2020a; Gower et al., 2020) , so that it converges to an exact solution.It provably benefits from the two mechanisms of LT and CC: the communication complexity is doubly accelerated, with a better dependency on the condition number of the functions and on the dimension of the model.Submitted to 38th Conference on Neural Information Processing Systems (NeurIPS 2024). Do not distribute.We study distributed optimization problems of the formEQUATIONwhere d ≥ 1 is the model dimension and the functions f i : R d → R and g : R d → R are smooth, so their gradients will be called. We consider the server-client model in which n ≥ 1 clients do computations in parallel and communicate back and forth with a server. The private function f i is owned by and stored on client i ∈ [n] := {1, . . . , n}. Problem (1) models empirical risk minimization, of utmost importance in machine learning (Sra et al., 2011; Shalev-Shwartz & Ben-David, 2014) . More generally, minimizing a sum of functions appears in virtually all areas of science and engineering. Our goal is to solve Problem (1) in a communication-efficient way, in the general heterogeneous setting in which the functions f i , as well as g, can be arbitrarily different: we do not make any assumption on their similarity whatsoever.We consider in this work the strongly convex setting -an analysis with nonconvex functions would certainly require very different proof techniques, which we currently do not know how to derive. That is, the following holds:Assumption 1.1 (strongly convex functions). The functions f i and g are all L-smooth and µ-strongly convex, for some 0 < µ ≤ L.1 Then we denote by x ⋆ the solution of the strongly convex problem(1), which exists and is unique. We define the condition number κ := L µ .Problem (1) can be viewed as the minimization of the average of the n functions (f i + g), which can be performed using calls to ∇(f i + g) = ∇f i + ∇g. We do not use this straightforward interpretation.Instead, let us illustrate the interest of having the additional function g in (1), using 4 different viewpoints. We stress that we can handle the case g = 0, as discussed in Section 3.1.• Viewpoint 1: regularization. The function g can be a regularizer. For instance, if the functions f i are convex, adding g = µ 2 ∥ • ∥2 for a small µ > 0 makes the problem µ-strongly convex.• Viewpoint 2: shared dataset. The function g can model the cost of a common dataset, or a piece thereof, that is known to all clients.• Viewpoint 3: server-aided training. The function g can model the cost of a core dataset, known only to the server, which makes calls to ∇g. This setting has been investigated in several works, with the idea that using a small auxiliary dataset representative of the global data distribution, the server can correct for the deviation induced by partial participation (Zhao et al., 2018; Yang et al., 2021 Yang et al., , 2023)) . We do not focus on this setting, because we deal with the general heterogeneous setting in which g and the f i are not meant to be similar in any sense, and in our work g is handled by the clients, not by the server.• Viewpoint 4: a new mathematical and algorithmic principle. This is the idea that led to the construction of LoCoDL, and we detail it in Section 2.1.In LoCoDL, the clients make all gradient calls; that is, Client i makes calls to ∇f i and ∇g.We review the latest developments on communication-efficient algorithms for distributed learning, making use of LT, CC, or both. Before that, we note that we should distinguish uplink, or clients-to-server, from downlink, or server-to-clients, communication. Uplink is usually slower than downlink communication, since uploading different messages in parallel to the server is slower than broadcasting the same message to an arbitrary number of clients. This can be due to cache memory and aggregation speed constraints of the server, as well as asymmetry of the service provider's systems or protocols used on the internet or cell phone network. In this work, we focus on the uplink communication complexity, which is the bottleneck in practice. Indeed, the goal is to exploit parallelism to obtain better performance when n increases. Precisely, with LoCoDL, the uplinkcommunication complexity decreases from O d √ κ log ϵ -1 when n is small to O √ d √ κ log ϵ -1when n is large, where the condition number κ is defined in Assumption 1.1, see Corollary 3.2. Many works have considered bidirectional compression, which consists in compressing the messages sent both ways (Gorbunov et al., 2020b; Philippenko & Dieuleveut, 2020; Liu et al., 2020; Philippenko & Dieuleveut, 2021; Condat & Richtárik, 2022; Gruntkowska et al., 2023; Tyurin & Richtárik, 2023b) but to the best of our knowledge, this has no impact on the downlink complexity, which cannot be reduced further than O d √ κ log ϵ -1 , just because there is no parallelism to exploit in this direction.Thus, we focus our analysis on theoretical and algorithmic techniques to reduce the uplink communication complexity, which we call communication complexity in short, and we ignore downlink communication.Communication Compression (CC) consists in applying some lossy scheme that compresses vectors into messages of small bit size, which are communicated. For instance, the well-known rand-k compressor selects k coordinates of the vector uniformly at random, for some k ∈ [d] := {1, . . . , d}.k can be as small as 1, in which case the compression factor is d, which can be huge. Some compressors, such as rand-k, are unbiased, whereas others are biased; we refer to Beznosikov et al.( is large, see Table 2 . DIANA was later extended in several ways (Horváth et al., 2022; Gorbunov et al., 2020a; Condat & Richtárik, 2022) . An accelerated version of DIANA called ADIANA based on Nesterov Accelerated GD has been proposed (Li et al., 2020b) and further analyzed in He et al. (2023) ; it has the state-of-the-art theoretical complexity.Algorithms converging linearly with biased compressors have also been proposed, such as EF21 (Richtárik et al., 2021; Fatkhullin et al., 2021; Condat et al., 2022b ), but the acceleration potential is less understood than with unbiased compressors. Algorithms with CC such as MARINA (Gorbunov et al., 2021) and DASHA (Tyurin & Richtárik, 2023a) have been proposed for nonconvex optimization, but their analysis requires a different approach and there is a gap in the achievable performance: their complexity depends on ωκ √ n instead of ωκ n with DIANA, where ω characterizes the compression error variance, see (2). Therefore, we focus on the convex setting and leave the nonconvex study for future work.Local Training (LT) is a simple but remarkably efficient idea: the clients perform multiple Gradient Descent (GD) steps, instead of only one, between successive communication rounds. The intuition behind is that this leads to the communication of richer information, so that the number of communication rounds to reach a given accuracy is reduced. We refer to Mishchenko et al. (2022) with the APDA-Inexact algorithm, and generalized to handle partial participation by Grudzień et al. (2023) with the 5GCS algorithm: in both algorithms, the local GD steps form an inner loop in order to compute a proximity operator inexactly.Combining LT and CC while retaining their benefits is very challenging. In our strongly convex and heterogeneous setting, the methods Qsparse-local-SGD (Basu et al., 2020) and FedPAQ (Reisizadeh et al., 2020) do not converge linearly. FedCOMGATE features LT + CC and converges linearly (Haddadpour et al., 2021) , but its complexity O(dκ log ϵ -1 ) does not show any acceleration. We can mention that random reshuffling, a technique that can be seen as a type of LT, has been combined with CC in Sadiev et al. (2022b) ; Malinovsky & Richtárik (2022) √ d √ κ + d √ κ √ n + d log ϵ -1 ,as reported in Table 2 . However, CompressedScaffnew uses a specific linear compression scheme that requires shared randomness; that is, all clients have to agree on a random permutation of the columns of the global compression pattern. No other compressor can be used, which notably rules out any type of quantization.For every ω ≥ 0, we define the U(ω) as the set of random compression operators C : R d → R d that are unbiased, i.e. E[C(x)] = x, and satisfy, for everyx ∈ R d , E ∥C(x) -x∥ 2 ≤ ω ∥x∥ 2 .(2)In addition, given a collection (C i ) n i=1 of compression operators in U(ω) for some ω ≥ 0, in order to characterize their joint variance, we introduce the constant ω av ≥ 0 such that, for everyx i ∈ R d , i ∈ [n],we haveE   1 n n i=1 C i (x i ) -x i 2   ≤ ω av n n i=1 ∥x i ∥ 2 .(3)The inequality (3) is not an additional assumption: it is satisfied with ω av = ω by convexity of the squared norm. But the convergence rate will depend on ω av , which is typically much smaller than ω.In particular, if the compressors C i are mutually independent, the variance of their sum is the sum of their variances, and (3) is satisfied with ω av = ω n .This work addresses the following question: Can we combine LT and CC with any compressors in the generic class U(ω) defined in the previous section, and fully benefit from both techniques by obtaining a doubly-accelerated communication complexity?We answer this question in the affirmative. In LoCoDL, every client stores and updates two local model estimates. They will all converge to the same solution x ⋆ of (1). This construction comes from two ideas.Local steps with local models. In algorithms making use of LT, such as FedAvg, Scaffold and Scaffnew, the clients store and update local model estimates x i . When communication occurs, an estimate of their average is formed by the server and broadcast to all clients. They all resume their computations with this new model estimate.Compressing the difference between two estimates. To implement CC, a powerful idea is to compress not the vectors themselves, but difference vectors that converge to zero. This way, the algorithm is variance-reduced; that is, the compression error vanishes at convergence. The technique of compressing the difference between a gradient vector and a control variate is at the core of Table 1 : Communication complexity in number of communication rounds to reach ϵ-accuracy for linearly-converging algorithms allowing for CC with independent compressors in U(ω) for any ω ≥ 0.Since the compressors are independent, ω av = ω n . We provide the leading asymptotic factor and ignore log factors such as log ϵ -1 . The state of the art is highlighted in green.Com. complexity in # rounds caseω = O(n) case ω = Θ(n) DIANA (1 + ω n )κ + ω κ + ω κ + ω EF21 (1 + ω)κ (1 + ω)κ (1 + ω)κ 5GCS-CC 1+ √ ω+ ω √ n √ κ + ω (1+ √ ω) √ κ + ω (1+ √ ω) √ κ + ω ADIANA 1 1+ ω 3/4 n 1/4 + ω √ n √ κ + ω 1+ ω 3/4 n 1/4 √ κ + ω (1+ √ ω) √ κ + ω ADIANA 2 1 + ω √ n √ κ + ω 1 + ω √ n √ κ + ω (1+ √ ω) √ κ + ω lower bound 2 1 + ω √ n √ κ + ω 1 + ω √ n √ κ + ω (1+ √ ω) √ κ + ω LoCoDL 1+ √ ω+ ω √ n √ κ + ω(1+ ω n ) (1+ √ ω) √ κ + ω (1+ √ ω) √ κ + ωTable 2 : (Uplink) communication complexity in number of reals to reach ϵ-accuracy for linearlyconverging algorithms allowing for CC, with an optimal choice of unbiased compressors. We provide the leading asymptotic factor and ignore log factors such as log ϵ -1 . The state of the art is highlighted in green.case n = O(d) DIANA (1 + d n )κ + d d n κ + d EF21 dκ dκ 5GCS-CC √ d+ d √ n √ κ + d d √ n √ κ + d ADIANA 1 + d √ n √ κ + d d √ n √ κ + d CompressedScaffnew √ d+ d √ n √ κ + d d √ n √ κ + d FedCOMGATE dκ dκ LoCoDL √ d+ d √ n √ κ + d d √ n √ κ + dalgorithms such as DIANA and EF21. Here, we want to compress differences between model estimates, not gradient estimates. That is, we want Client i to compress the difference between x i and another model estimate that converges to the solution x ⋆ as well. We see the need of an additional model estimate that plays the role of an anchor for compression. This is the variable y common to all clients in LoCoDL, which compress x i -y and send these compressed differences to the server.Combining the two ideas. Accordingly, an equivalent reformulation of ( 1) is the consensus problemwith n + 1 variables min x1,...,xn,y 1 n n i=1 f i (x i ) + g(y) s.t. x 1 = • • • = x n = y.The primal-dual optimality conditions arex 1 = • • • = x n = y, 0 = ∇f i (x i ) -u i ∀i ∈ [n], 0 = ∇g(y) -v, and 0 = u 1 + • • • + u n + nv (dual feasibility), for some dual variables u 1 , . . . , u n , vintroduced in LoCoDL, that always satisfy the dual feasibility condition. 
description of locodl: 
 LoCoDL is a randomized primal-dual algorithm, shown as Algorithm 1. At every iteration, for every i ∈ [n] in parallel, Client i first constructs a prediction xt i of its updated local model estimate, using a GD step with respect to f i corrected by the dual variable u t i . It also constructs a prediction ŷt of the updated model estimate, using a GD step with respect to g corrected by the dual variable v t .Algorithm 1 LoCoDL 1: input:stepsizes γ > 0, χ > 0, ρ > 0; probability p ∈ (0, 1]; variance factor ω ≥ 0; local initial estimates x 0 1 , . . . , x 0 n ∈ R d , initial estimate y 0 ∈ R d , initial control variates u 0 1 , . . . , u 0 n ∈ R d and v ∈ R d such that 1 n n i=1 u 0 i + v 0 = 0. 2: for t = 0, 1, . . . do 3:for i = 1, . . . , n, at clients in parallel, do 4:xt i := x t i -γ∇f i (x t i ) + γu t i 5:ŷt := y t -γ∇g(y t ) + γv t // the clients store and update identical copies of y t , v t , ŷt 6:flip a coin θ t ∈ {0, 1} with Prob(θ t = 1) = p 7:if θ t = 1 then 8: d t i := C t i xt i -x t+1 i := (1 -ρ)x t i + ρ(ŷ t + dt )12:u t+1 i := u t i + pχ γ(1+2ω)dt -d t i 13:y t+1 := ŷt + ρ dt 14: v t+1 := v t + pχ γ(1+2ω)dt 15: else 16:x t+1 i := xt i , y t+1 = ŷt , u t+1 i := u t i , v t+1 := v t 17: end if 18:end for 19: end for Since g is known by all clients, they all maintain and update identical copies of the variables y and v. If there is no communication, which is the case with probability 1 -p, x i and y are updated with these predicted estimates, and the dual variables u i and v are unchanged. If communication occurs, which is the case with probability p, the clients compress the differences xt i -ŷt and send these compressed vectors to the server, which forms dt equal to one half of their average. Then the variables x i are updated using a convex combination of the local predicted estimates xt i and the global but noisy estimate ŷt + dt . y is updated similarly. Finally, the dual variables are updated using the compressed differences minus their weighted average, so that the dual feasibility condition remains satisfied. The model estimates x t i , xt i , y t , ŷt all converge to x ⋆ , so that their differences, as well as the compressed differences as a consequence of (2), converge to zero. This is the key property that makes the algorithm variance-reduced. We consider the following assumption.Assumption 2.1 (class of compressors). In LoCoDL the compressors C t i are all in U(ω) for someω ≥ 0. Moreover, for every i ∈ [n], i ′ ∈ [n], t ≥ 0, t ′ ≥ 0, C t i and C t ′ i ′ are independent if t ̸ = t ′ (C t iand C t i ′ at the same iteration t need not be independent). We define ω av ≥ 0 such that for every t ≥ 0, the collection(C t i ) n i=1 satisfies (3).Remark 2.2 (partial participation). LoCoDL allows for a form of partial participation if we set ρ = 1.Indeed, in that case, at steps 11 and 13 of the algorithm, all local variables x i as well as the common variable y are overwritten by the same up-to-date model ŷt + dt . So, it does not matter that for a non-participating client i with d t i = 0, the xt ′ i were not computed for the t ′ ≤ t since its last participation, as they are not used in the process. However, a non-participating client should still update its local copy of y at every iteration. This can be done when ∇g is much cheaper to compute that ∇f i , as is the case with g = µ 2 ∥ • ∥ 2 . A non-participating client can be completely idle for a certain period of time, but when it resumes participating, it should receive the last estimates of x, y and v from the server as it lost synchronization.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: the limitations are discussed in the conclusion.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.• The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.• The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.• The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.• The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.• If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.• While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
convergence and complexity of locodl: 
 Theorem 3.1 (linear convergence of LoCoDL). Suppose that Assumptions 1.1 and 2.1 hold. InLoCoDL, suppose that 0 < γ < 2 L , 2ρ -ρ 2 (1 + ω av ) -χ ≥ 0.For every t ≥ 0, define the Lyapunov functionΨ t := 1 γ n i=1 x t i -x ⋆ 2 + n y t -x ⋆ 2 + γ(1 + 2ω) p 2 χ n i=1 u t i -u ⋆ i 2 + n v t -v ⋆ 2 ,(4) where v ⋆ := ∇g(x ⋆ ) and u ⋆ i := ∇f i (x ⋆ ). Then LoCoDL converges linearly: for every t ≥ 0,EQUATIONIn addition, for every i ∈ [n], (x t i ) t∈N and (y t ) t∈N converge to x ⋆ , (u t i ) t∈N converges to u ⋆ i , and(v t ) t∈N converges to v ⋆ , almost surely.We place ourselves in the conditions of Theorem 3.1. We observe that in (5), the larger χ, the better, so given ρ we should set χ = 2ρ -ρ 2 (1 + ω av ). Then, choosing ρ to maximize χ yieldsEQUATION)We now study the complexity of LoCoDL with χ and ρ chosen as in ( 6) and γ = Θ( 1 L ). We remark that LoCoDL has the same rate τ ♯ := max(1 -γµ, γL -1) 2 as mere distributed gradient descent, as long as p -1 , ω and ω av are small enough to have 1 -p 2 χ 1+2ω ≤ τ ♯ . This is remarkable: communicating with a low frequency and compressed vectors does not harm convergence at all, until some threshold.The iteration complexity of LoCoDL to reach ϵ-accuracy, i.e.EQUATIONBy choosingEQUATIONthe iteration complexity becomes O κ + ω(1 + ω av ) log ϵ -1 and the communication complexity in number of communication rounds is p times the iteration complexity, that isO κ(1 + ω av )(1 + ω) + ω(1 + ω av ) log ϵ -1 .If the compressors are mutually independent, ω av = ω n and the communication complexity can be equivalently written asO 1 + √ ω + ω √ n √ κ + ω 1 + ω n log ϵ -1 ,as shown in Table 1 .Let us consider the example of independent rand-k compressors, for some k ∈ [d]. We haveω = d k -1. Therefore, the communication complexity in numbers of reals is k times the complexity in number of rounds; that is, O √ kd + d √ n √ κ + d 1 + d kn log ϵ -1 . We can now choose k to minimize this complexity: with k = ⌈ d n ⌉, it becomes O √ d + d √ n √ κ + d log ϵ -1 , asshown in Table 2 . Let us state this result:Corollary 3.2. In the conditions of Theorem 3.1, suppose in addition that the compressorsEQUATIONThen the uplink communication complexity in number of reals of LoCoDL is This is the same complexity as CompressedScaffnew (Condat et al., 2022a) . However, it is obtained with simple independent compressors, which is much more practical than the permutation-based compressors with shared randomness of CompressedScaffnew. Moreover, this complexity can be obtained with other types of compressors, and further reduced, when reasoning in number of bits and not only reals, by making use of quantization (Albasyoni et al., 2020) , as we illustrate by experiments in the next section.EQUATIONWe can distinguish 2 regimes:1. In the "large d small n" regime, i.e. n = O(d), the communication complexity of LoCoDL in (10)becomesO d √ κ √ n + d log ϵ -1. This is the state of the art, as reported in Table 2 . 3.1 The Case g = 0We have assumed the presence of a function g in Problem (1), whose gradient is called by all clients.In this section, we show that we can handle the case where such a function is not available. So, let us assume that we want to minimize 1 n n i=1 f i , with the functions f i satisfying Assumption 1.1.We now define the functions fi := f i -µ 4 ∥•∥ 2 and g := µ 4 ∥•∥ 2 .They are all L-smooth and μstrongly convex, with L := L -µ 2 and μ := µ 2 . Moreover, it is equivalent to minimize1 n n i=1 f i or 1 n n i=1 fi + g.We can then apply LoCoDL to the latter problem. At Step 5, we simply havey t -γ∇g(y t ) = (1 -γµ 2 )y t .The rate in (5) applies with L and µ replaced by L and μ, respectively.Since κ ≤ κ := L μ ≤ 2κ, the asymptotic complexities derived above also apply to this setting. Thus, the presence of g in Problem (1) is not restrictive at all, as the only property of g that matters is that it has the same amount of strong convexity as the f i s.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [Yes] Justification: The data used in the experiments are publicly available. The code is provided.Guidelines:• The answer NA means that paper does not include experiments requiring code.• Please see the NeurIPS code and data submission guidelines (https://nips.cc/ public/guides/CodeSubmissionPolicy) for more details.• While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).• The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https://nips.cc/public/guides/CodeSubmissionPolicy) for more details.• The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.• The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why.• At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).• Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
experiments: 
 We evaluate the performance of our proposed method LoCoDL and compare it with several other methods that also allow for CC and converge linearly to x ⋆ . We also include GradSkip (Maranjyan et al., 2023) and Scaffold (McMahan et al., 2017) in our comparisons. We focus on a regularized logistic regression problem, which has the form (1) withf i (x) = 1 m m s=1 log 1+exp -b i,s a ⊤ i,s x + µ 2 ∥x∥ 2 (11)and g = µ 2 ∥x∥ 2 , where n is the number of clients, m is the number of data points per client, a i,s ∈ R d and b i,s ∈ {-1, +1} are the data samples, and µ is the regularization parameter, set so that κ = 10 4 .For all algorithms other than LoCoDL, for which there is no function g, the functions f i in (11) have a twice higher µ, so that the problem remains the same.We considered several datasets from the LibSVM library (Chang & Lin, 2011) (3-clause BSD license).We show the results with the 'a5a' dataset in Figure 1 and with other datasets in the Appendix. We prepared each dataset by first shuffling it, then distributing it equally among the n clients (since m in ( 11) is an integer, the remaining datapoints were discarded). We used four different compression operators in the class U(ω), for some ω ≥ 0:• rand-k for some k ∈ [d], which communicates 32k + k⌈log 2 (d)⌉ bits. Indeed, the k randomly chosen values are sent in the standard 32-bits IEEE floating-point format, and their locations are encoded with k⌈log 2 (d)⌉ additional bits. We have ω = d k -1.• Natural Compression (Horváth et al., 2022) , a form of quantization in which floats are encoded into 9 bits instead of 32 bits. We have ω = 1 8 .• A combination of rand-k and Natural Compression, in which the k chosen values are encoded into 9 bits, which yields a total of 9k + k⌈log 2 (d)⌉ bits. We have ω = 9d 8k -1.• The l 1 -selection compressor, defined as C(x) = sign(x j )∥x∥ 1 e j , where j is chosen randomly in[d],with the probability of choosing j ′ ∈ [d] equal to |x j ′ |/∥x∥ 1 , and e j is the j-th standard unit basis vector in R d . sign(x j )∥x∥ 1 is sent as a 32-bits float and the location of j is indicated with ⌈log 2 (d)⌉, so that this compressor communicates 32 + ⌈log 2 (d)⌉ bits. Like with rand-1, we have ω = d -1.The compressors at different clients are independent, so that ω av = ω n in (3).We can see that LoCoDL, when combined with rand-k and Natural Compression, converges faster than all other algorithms, with respect to the total number of communicated bits per client. We chose two different numbers n of clients, one with n < d and another one with n > 2d, since the compressor of CompressedScaffnew is different in the two cases n < 2d and n > 2d (Condat et al., 2022a) . LoCoDL outperforms CompressedScaffnew in both cases. As expected, all methods exhibit faster convergence with larger n. Remarkably, ADIANA, which has the best theoretical complexity for large n, improves upon DIANA but is not competitive with the LT-based methodsCompressedScaffnew, 5GCS-CC, and LoCoDL. This illustrates the power of doubly-accelerated methods based on a successful combination of LT and CC. In this class, our new proposed LoCoDL algorithm shines. For all algorithms, we used the theoretical parameter values given in their available convergence results (Corollary 3.2 for LoCoDL). We tried to tune the parameter values, such as k in rand-k and the (average) number of local steps per round, but this only gave minor improvements.For instance, ADIANA in Figure 1 was a bit faster with the best value of k = 20 than with k = 30.Increasing the learning rate γ led to inconsistent results, with sometimes divergence. 
conclusion: 
 We In practice, LoCoDL outperforms other algorithms, including ADIANA, which has an even better complexity in theory obtained from Nesterov acceleration and not Local Training. This again shows the relevance of the popular mechanism of Local Training, which has been widely adopted in Federated Learning. A venue for future work is to implement bidirectional compression (Liu et al., 2020; Philippenko & Dieuleveut, 2021) . We will also investigate extensions of our method with calls to stochastic gradient estimates, with or without variance reduction, as well as partial participation. We define the Euclidean space X := R d and the product space X := X n+1 endowed with the 
experimental setting/details: 
 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes] Justification: We provide these details.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.• The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [No] Justification: the variability with respect to different random realizations plays a minor role in the performance.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.• The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).• The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)• The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean.• It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.• For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).• If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes] Justification: we do not focus on the computation time but on the number of communicated bits, which is independent from the hardware. So the experiments can be reproduced on any machine.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.• The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.• The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification:Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.• The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: This is a theoretical work whose goal is to advance the foundations of optimization and machine learning. The positive impact of developing more efficient algorithms is clear and does not need to be discussed. We do not see any particular negative impact.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.• The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.• If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification:Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.• Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.• We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification: we use the LibSVM and mention the 3-clause BSD license.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL.• The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.• For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.• If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [NA] Justification:Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.• The paper should discuss whether and how consent was obtained from people whose asset is used.• At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing and research with human subjects: 
 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?Answer: [NA] Justification:Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.• Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.• Justification:Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.• Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.• We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.• For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: EQUATIONWe define the copy operator 1 : x ∈ X → (x, . . . , x, x) ∈ X and the linear operatorEQUATIONS is the orthogonal projector in X onto the consensus line {x ∈ X :x 1 = • • • = x n = y}.We also define the linear operatorEQUATIONwhere Id denotes the identity. W is the orthogonal projector in X onto the hyperplane {x ∈ X :x 1 + • • • + x n + ny = 0}, which is orthogonal to the consensus line. As such, it is self-adjoint, positive semidefinite, its eigenvalues are (1, . . . , 1, 0), its kernel is the consensus line, and its spectral norm is 1. Also, W 2 = W . Note that we can write W in terms of the differences d i = x i -y andEQUATION)Since for every x = (x 1 , . . . , x n , y), W x = 0 := (0, . . . , 0, 0) if and only ifx 1 = • • • = x n = y,we can reformulate the problem (1) asEQUATION)where f (x) := n i=1 f i (x i ) + ng(y). Note that in X , f is L-smooth and µ-strongly convex, and∇f (x) = ∇f 1 (x 1 ), . . . ∇f n (x n ), ∇g(y) .Let t ≥ 0. We also introduce vector notations for the variables of the algorithm:x t := (x t 1 , . . . , x t n , y t ), xt := (x t 1 , . . . , xt n , ŷt ), u t := (u t 1 , . . . , u t n , v t ), u ⋆ := (u ⋆ 1 , . . . , u ⋆ n , v ⋆ ), w t := x t -γ∇f (x t ), w ⋆ := x ⋆ -γ∇f (x ⋆ ), where x ⋆ := 1x ⋆ is the unique solution to (16). We alsodefine xt := 1 2n ( n i=1 xt i + nŷ t ) and λ := pχ γ(1+2ω) .Then we can write the iteration of LoCoDL as                   xt := x t -γ∇f (x t ) + γu t = w t + γu t flip a coin θ t ∈ {0, 1} with Prob(θ t = 1) = p if θ t = 1 d t := C t 1 (x t 1 -ŷt ), . . . , C t n (x t n -ŷt ), 0 dt := 1 2n n j=1 d t j x t+1 := (1 -ρ)x t + ρ1(ŷ t + dt ) u t+1 := u t + λ 1 dt -d t = u t -λW d t else x t+1 := xt u t+1 := u t end if (17)We denote by F t the σ-algebra generated by the collection of X -valued random variables x 0 , u 0 , . . . , x t , u t . Hence, with λ = pχ γ(1+2ω) ,1 γ E x t+1 -x ⋆ 2 X | F t + γ(1 + 2ω) p 2 χ E u t+1 -u ⋆ 2 X | F t ≤ 1 γ w t -w ⋆ 2 X -γ u t -u ⋆ 2 X + 2⟨x t , u t -u ⋆ ⟩ X - p γ 2ρ -ρ 2 (1 + ω av ) W xt 2 X + γ(1 + 2ω) p 2 χ u t -u ⋆ 2 X + pχ γ W xt 2 X -2⟨u t -u ⋆ , xt ⟩ X = 1 γ w t -w ⋆ 2 X + γ(1 + 2ω) p 2 χ 1 - p 2 χ 1 + 2ω u t -u ⋆ 2 X - p γ 2ρ -ρ 2 (1 + ω av ) -χ W xt 2 X .Therefore, assuming that 2ρ -ρ 2 (1 + ω av ) -χ ≥ 0, E Ψ t+1 | F t ≤ 1 γ w t -w ⋆ 2 X + 1 - p 2 χ 1 + 2ω γ(1 + 2ω) p 2 χ u t -u ⋆ 2 X .According to Condat & Richtárik (2023, Lemma 1) ,EQUATION)Using the tower rule, we can unroll the recursion in ( 19) to obtain the unconditional expectation ofΨ t+1 .Using classical results on supermartingale convergence (Bertsekas, 2015, Proposition A.4.5) , it follows from (19) that Ψ t → 0 almost surely. Almost sure convergence of x t and u t follows.The results for the experiments in Section 4 with the 'diabetes' dataset from the LibSVM library (Chang & Lin, 2011) are shown in Figure 2 . The results with the 'w1a' and 'australian' datasets, for the same logistic regression problem with κ = 10 4 , are shown in Figures 3 and 4 .Consistent with our previous findings, LoCoDL outperforms the other algorithms in terms of communication efficiency. Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper.• The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.• The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.• It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.A differentiable function f : R d → R is said to be L-smooth if ∇f is L-Lipschitz continuous; that is, for every x ∈ R d and y ∈ R d , ∥∇f (x) -∇f (y)∥ ≤ L∥x -y∥ (the norm is the Euclidean norm throughout the paper). f is said to be µ-strongly convex if f -µ∥ • ∥ 2 is convex.This is the complexity derived in the original paperLi et al. (2020b).This is the complexity derived by a refined analysis in the preprintHe et al. (2023), where a matching lower bound is also derived. 


Decision: The reviews of this paper are mixed, and the final decision is pointing slightly downards due to issues raised on both the theory and experimental side.

While the paper claims to be theoretical, at least in terms of theoretical results, there is no edge compared to methods such as ADIANA. There are also areas to improve the level of rigor for a theory paper; for example: 1) functions of $\epsilon$ appear before defining what it is, 2) the level of rigor around the concept of compression was questioned, noting that $\mathbb{R}^d \to \mathbb{R}^k$ is not a well-defined compression paradigm, since there is a bijective map between the two.  It would be helpful to clarify this and ideally provide an entirely formal notion.

On the experimental side, other concerns were raised, including: 1) Experiments were done only with logistic regression, which is insufficient to show the proposed scheme to be better, 2) Plots that show accuracy vs number of iteration are absent.

Finally, the reviewers have mixed opinions about the novelty of the proposed algorithm compared to ADIANA.

Reviews: review: paper_summary: paper_summary: This paper proposes an algorithm (LoCoDL) that leverages two well-known methods of local training. It reduces the communication load in distributed learning.
strength_weakness: strength_weakness: 1. Generally, compressing the error and feeding it back to the updates is a well-known technique to reduce the variance in distributed learning. The idea of the algorithm is marginal with respect to the previous known algorithms (feeding back the error and aggregating with proper coefficients). 
2. Also, the experiments should include the accuracy versus iteration (or time) to see after how many iterations (or how much time), the performance shown in Figure 1 is achieved. So, there are lots of work to improve the experimental part.
questions: questions: What are the new directions on distributed learning.
limitations: limitations: justification, experiments
paper_summary: paper_summary: This paper proposes LoCoDL, a new GD-based distributed training algorithm that employs both communication compression (CC) and local training (LT). It achieves double acceleration and a SOTA convergence rate for strongly convex problems.

A crux of the algorithmic improvement is maintaining two local estimates, intuitively enabling efficient LT (similarly to SCAFFOLD) and efficient CC (i.e., compressing values' differences instead of values themselves).

The paper offers a thorough theoretical analysis that proves the main claim and conducts some experiments that show LoCoDL's benefits compared to previous algorithms.
strength_weakness: strength_weakness: The practical applicability of LoCoDL is unclear. Namely, it does not apply to NNs and possibly is less efficient for partial participation use cases (this part is unclear). Either providing concrete evidence of why this contribution is important for modern practical use cases or slightly rephrasing the paper as a theoretical (and important) contribution would strengthen the claim.   

Strengthening the evaluation section is also advised. The submission would be strengthened if the author provided an experiment other than logistic regression to demonstrate the efficiency of LoCoDL in another task.

Additional points: 

1.	“are smooth,  so their gradients will be called. “ This sentence is unclear.

2.	“is slower than  broadcasting the same message to an arbitrary number of clients.” Are there any real FL systems that employ broadcasting? Or do you mean sending the same message? (The term “broadcast” may be confusing here.)

3.	“In this work, we focus on the  uplink communication complexity, which is the bottleneck in practice.“ The second part of the sentence should be softened or extended with real evidence that this is the case. 

4.	“No other compressor can be used, which notably rules out any type of quantization.” Why is this the case? Why quantization cannot be applied according to the selected pattern? 

5.	“Instead of the cumbersome permutation-based compressor of the latter.” is there a specific challenge in implementing permutation-based compressors? Maybe it's worth specifying specific setups where this is insufficient or cannot be applied.

6.	“Thus, LoCoDL sets new standards in terms of communication efficiency. “ Do you mean: our experiments indicate that...?

7.	What is the communication complexity with partial participation (PP) (i.e., $\rho=1$)? When considering PP, is LoCoDL the current SOTA, or are there better alternatives? 

8. It seems that some elements of LoCoDL have some similarities to DoCoFL [1], which also uses an anchor for the model that allows clients to obtain only a compressed correction to that anchor. Can the authors shed light on this similarity?

[1] Dorfman, Ron, et al. "DoCoFL: Downlink compression for cross-device federated learning." International Conference on Machine Learning. PMLR, 2023.
questions: questions: See weaknesses.
limitations: limitations: The paper does not have a dedicated limitation section. The conclusions section discusses potential future extensions. Outlining the limitations clearly is advised. For example, is the PP use case relevant here?
paper_summary: paper_summary: This paper proposed LoCoDL, an algorithm than combines communication compression with local training. The authors proved the convergence results under regular assumptions, achieving comparable rate with existing SOTA algorithms. The experimental results also show that LoCoDL behaves best among tested algorithms.
strength_weakness: strength_weakness: 1. Throughout the four experimental settings, the number of nodes, $n$, is comparable to the feature dimension $d$. As the convergence rate of LoCoDL is suboptimal when $n$ is small, I believe it important to compare LoCoDL with ADIANA when $n$ is at least 10$\times$ or 100$\times$ smaller than $d$ to see whether LoCoDL beats ADIANA in these scenarios.
2. The experimental datasets are relatively small. It's recommended to conduct experiments on MNIST or larger datasets.
3. It is not easy to capture the intuition behind each algorithm line. It's recommended to give more detailed explanations on how the algorithm is developed.
questions: questions: 1. Existing works widely use the error feedback mechanism from EF21 to remove the gradient dissimilarity bound condition. Does LoCoDL overcome this issue by the primal-dual format? Is the primal-dual format somehow equivalent to error feedback or has it been used by prior works for the same reason? I'm not questioning the novelty of the proposed algorithm but rather curious about the intuition behind.
2. Is it possible to extend LoCoDL to stochastic settings or generally convex settings? Are there any technical difficulties?
3. When $g\equiv0$, the paper considers an equivalent case where $f_i\gets f_i-\frac{\mu}{4}\\|\cdot\\|^2$ and $g\gets \frac{\mu}{4}\\|\cdot\\|^2$. However, $\mu$ may not be available for many objective functions. Should we tune it as a hyperparameter? If we apply LoCoDL to the vanilla case where $g\equiv0$, are there any difficulties in convergence analysis?
limitations: limitations: As stated in the conclusion part, the algorithm is limited to single-directional, deterministic setting without partial participation.

Comments: title: difference with the previous literature is not clear
comment: Thank you again for your thorough and positive evaluation. We are kindly counting on you to support the paper toward acceptance during this discussion phase with the AC.
Thank you again for your thorough and positive evaluation. We are kindly counting on you to support the paper toward acceptance during this discussion phase with the AC.
Dear reviewer,

We would be glad to discuss our contributions further with you. The 2 other reviewers are convinced by the merits of our work and are clearly for acceptance with scores of 7.

Do you have any question or suggestion of improvement?
Thank you for the detailed reply. All my concerns have been well addressed and I do not have further questions.
> The method is a heuristic one without a theoretical justification. 

No, quite the opposite: our work is theoretically grounded, and accelerated convergence of our new algorithm LoCoDL is proved in Theorem 3.1 and Corollary 3.2.

> the authors failed to clearly identify the difference between their method and previous literature.

The comparison is clearly summarized in Tables 1 and 2. The state of the art and our contributions, which improve upon it, are discussed in details in the first 6 pages of the paper.

We don't understand your negative stance as you don't provide any argument or reference to depreciate our contributions.

Let us state again that we prove an accelerated communication complexity that depends on $\sqrt{\kappa}$ and $\sqrt{d}$. DIANA with rand-1 compressors has complexity $O(\kappa + d)$, for instance (for large $n$).


> The plot of accuracy versus epochs gives the transitional behavior of the proposed algorithm. If the authors are familiar with the paper of DIANA, they can look at Figure 3.

We are familiar with DIANA. In Figure 3 of arXiv:1901.09269v3, the training and testing accuracy are shown for a convex experiment with the softmax cross entropy loss on the CIFAR10-DNN dataset. The 2 plots are nearly identical. The accuracy increases monotonically and there is no phase transition. The number of iterations, epochs, and communicated bits are proportional to each other for a given method, so taking one or the other in abscissa will only change the horizontal scaling of the plot, the visible behavior remains the same.
Regarding the first comment: Yes, one can consider DIANA as a reference. But, the idea of feeding back the error is a very well-known technique and has been considered in several works. The authors can search for a complete list of them. The main point with this comment is that the authors failed to clearly identify the difference between their method and previous literature. The method is a heuristic one without a theoretical justification. I believe that this issue has been raised by another reviewer.

Regarding the second comment: The plot of accuracy versus epochs gives the transitional behavior of the proposed algorithm. If the authors are familiar with the paper of DIANA, they can look at Figure 3.
Thank you very much for your thorough evaluation of our work and for acknowledging its merits by raising your score.
I appreciate the detailed answers. Following the rebuttal, I have decided to raise my score from 6 to 7.