Implicit Regularization of Decentralized Gradient Descent for Sparse Regression
Authors: Tongle Wu
Ying Sun
Venue: NeurIPS 2024 poster (2024)
Keywords: Decentralized optimization
Implicit regularization
Sparse regression
Primary area: optimization

Abstract: We consider learning a sparse model from linear measurements taken by a network of agents. Different from existing decentralized methods designed based on the LASSO regression with explicit  $\ell_1$ norm regularization, we exploit the implicit regularization of decentralized optimization method applied to an over-parameterized nonconvex least squares formulation without penalization. Our first result shows that despite nonconvexity, if the network connectivity is good, the well-known decentralized gradient descent algorithm (DGD) with small initialization and early stopping can compute the statistically optimal solution. Sufficient conditions on the initialization scale,  choice of step size, network connectivity, and stopping time are further provided to achieve convergence. Our result recovers the convergence rate of gradient descent in the centralized setting, showing its tightness. 
Based on the analysis of DGD, we further propose a communication-efficient version, termed T-DGD, by truncating the iterates before transmission. In the high signal-to-noise ratio (SNR) regime, we show that T-DGD achieves comparable statistical accuracy to DGD, while the communication cost is logarithmic in the number of parameters. Numerical results are provided to validate the effectiveness of DGD and T-DGD for sparse learning through implicit regularization.

Implicit Regularization of Decentralized Gradient Descent for Decentralized Sparse Regression
Tongle Wu The Pennsylvania State University tfw53810psu. edu
Ying Sun The Pennsylvania State University ybs51900psu.edi
Abstract
We consider learning a sparse model from linear measurements taken by ner- work of agents. Different from existing decentralized methods designed based on the LASSO regression with explicit & norm regularization, we exploit the implicit regularization of the decentralized optimization method applied to over- parameterized nonconvex least squares formulation without sparse penalization. Our first result shows that despite nonconvexity, if the network connectivity is good, the well-known decentralized gradient descent algorithm (DGD) with small initial- ization and early stopping can compute the statistically optimal solution. Sufficient conditions on the initialization scale, choice of step size, network connectivity, and stopping time are further provided achieve convergence. Our result recovers the convergence rate of gradient descent in the centralized setting, showing its tight- ness. Based the analysis of DGD, we further propose communication--ffiienn version, termed T-DGD, by truncating the iterates before transmission. In the high signal-to-noise ratio (SNR) regime, we show that T-DGD achieves comparable statistical accuracy to DGD, while the communication cost is logarithmic in the number of parameters. Numerical results are provided to validate the effectiveness of DGD and TDDGD for sparse learning through implicit regularization.
Introduction
Modern deep learning is generally in the over-parsin wer-paraaeterize regime where the models have signif- icantly more parameters than available training examples 6, 41) Although deep learning models exhibit remarkable performance in multiple domains, the theoretical understanding of optimization and generalization for deep learning still limited. Recent studies show that despite being over- parameterized, gradient-based methods applied to minimize the emperical loss exhibit the implicit regularization phenomenon. For example, line works 5 [6] shows that with certain initialization, networks trained with gradient descent (GD) land in the "kernel regime" and share
similar behaviors to the kernel method. However, the literature 2 24 suggests that kernel regime analyses fall short in explaining the success of deep learning because neural networks analyzed in the kernel regime are almost linearized, thus hindering feature learning from data. Further, many works 35 38 40 start investigating the "rich regime", showing that GD with small initialization induces structures on the solution, such as sparsity and low-rankness, that better explains the generalization capability of NNs. However, all aforementioned results limited the centralized setting, where data are stored on a single machine. Practical constraints such as limited computing and storage resources, data privacy and security, and regulation rules make the centralized learning framework increasingly inadequate for contemporary applications. Although variety of decentralized learning algorithms can be applied to NN training, the questions of which solution they can converge, along with its generalization performance, are largely unclear.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

In this paper, we study the sparse learning problem [4 in the overparameterized regime, which shares many key characteristics with deep leariing models but is more tractable to analyze, as a prototype for understanding the computation and statistical guarantees of decentralized learning algorithms. Specifically, we consider learning a sparse model ur from its noisy linear measurements over agents. These agents communicate over an undirected connected mesh network without central coordinator, and each agent can only communicate with its one-hop neighbors. The i-th agent has its own samples { ())))) Each j-th data pair (æijj Wh.s) is generated according to the noisy linear model
Vi.j = - n- + Ca.j Vi E [m]] and Vj E [n],
where æij E Rd and Vi.j IR denotes respectively the j-th feature and its corresponding response i-th agent, Çú, is the observation noise, and w* R is the sparse model parameter to be learned, common to all agents, and has only $ (s & d) non-zero elements. We are interested in the high- dimensional setting where the ambient dimension d is substantially larger than the total sample size N == mn, i.e., d >> N. By re- re-parameterizing to = u O u v @ v, the loss function can be formulated as minimizing the following regularization-free nonlinear least square problem:
1 F F(,, v) = m
Σ fl v), with (u, v) = (u = - vo uu yyll: Vi E [m],
m
where fi(u, v) corresponds the loss function of i-th agent. Problem can also regarded as the supervised learning problem on the diagonal linear network of degree-2 38
Problem is highly non-convex with u and v, however, recent works 12
demonstrate 36
that if the design matrix satisfies the restricted isometric property (RIP) condition. the centralized GD without any regularization can yield the statistically optimal estimator with properly chosen initialization scale, step size, and early stopping time. This intriguing phenomenon is derived from the implicit regularization of GD. Roughly speaking, with small initialization, the gap |uद e? would increase with iteration for coordinate i such that w # O, where the remaining ones stay small enough before early stopping. As result, GD identifies the support of w= the algorithm processes. In the decentralized setting, general results from the pure optimization perspective can only certify convergence the stationary points, implying neither global optimality nor generalizability. Given the encouraging result of GD achieved in the centralized setting, it is natural to ask if statistically optimal solutions are also computable by decentralized gradient-type algorithms, which algorithm can achieve the goal, and what are the regularity conditions.
This paper aims to analyse the renowned decentralized gradient algorithm (DGD) for minimizing over the undirected mesh networks. The main contributions of this paper are detailed as follows.
Statistical guarantee. It is well established that even for convex objectives, DGD cannot compute an exact minimizer. It only converges to the neighborhood of the solution whose radius depends the step size. However, we show that under specific matrix satisfies the RIP condition, the initialization scale is sufficiently small, and the network is sufficiently connected the solution computed by DGD with early stopping is statistically optimal. Computational complexity. Our convergence analysis reveals that the early stopping time increases logarithmically with the ambient dimension d. While network connectivity does not affect statistical error when it satisfies mild conditions, it does influence the stopping time of DGD to find the optimal estimator. Networks with poor connectivity will delay the early stopping time, and thus increase the iteration complexity.
if the global design
Technical analysis. Compared to the techniques used for analyzing the centralized GD [33. 38], proving the convergence of DGD faces the following challenge. Because the consensus error terms induced from the mesh network result in a perturbed version of the multiplicative update. Compared with the exact multiplicative updates, the challenge is that the additional error term outside of multiplication prevents applying the centralized analysis directly. In addition, the error terms within the multiplication have more complicated consensus error terms than that of the centralized setting, which requires bounding the consensus error terms carefully to control these error terms that can achieve the same order statistical error. To achieve this goal, we separately control the consensus errors on support S and non-support S by the magnitudes of parameters on support S and non-support S", respectively. Our fine- iineggrined analysis for consensus errors is distinct
2

---

from existing decentralized optimization analyses that bound the consensus errors uniformly. The additional error term also complicates the transfer of proof from the simplified non non-negative w" case to the general w* setting the centralized setting, we conduct a comprehensive induction process to both u and v simultaneously for general w²
Truncated DGD. We propose communication -efffiicatti-eefiiientt truncated DGD (T-DGD) method that at each iteration, vectors being transmitted are truncated, keeping only 8 elements with the largest magnitudes nonzero. We prove that if each agent has sufficient samples and the signal-to-noise ratio is high enough, T-DGD can perform as well as the vanilla DGD while reducing communication complexity to logarithmic dependence on ambient dimension d.
2
Related works
We categorize the existing works most relevant to our study into three main groups.
Implicit regularizations for sparse regression. The recent study in [[5] reparameterized the model parameter through overparameterized Hadamard product and discovered encouraged empirical performance by the first-order optimization algorithms. The statistical and convergence guarantees for this phenomenon are established [6 42] under mild conditions. Woodworth et al. [38]
studied the impact of initialization scale on solutions. Scott et al. (27) demonstrated the benefit of stochasticity of SGD in sparse regression and explored the impact of momentum in [25]. The
more recent process in understanding the linear diagonal networks can be found in references 23 26 [3]. To the best of our knowledge, existing works have only discussed implicit regularizations induced by centralized optimization methods in linear diagonal networks. However, the question of whether decentralized algorithms induce implicit regularizations, and what type of implicit regularization they may induce has not been studied so far.
Decentralized sparse regression with explicit regularization. For estimating ground truth wt in dighniimensional sparse linear regression under the decentralized setting, Ji et al. [18] proposed DGD-CTA algorithm for tackling LASSO objective with consensus penalty and proved linear convergence rate to the neighbor of the statistical optimal estimator, but the convergence rate has polynomial dependence on ambient dimension d. Further Sun et al. [31] proposed the NetLASSO based on the gradient tracking method and obtained d-independent convergence rate and optimal statistical accuracy. To complement work [8]. Ji et al. proposed DGD-ATC by mixing the local gradients along iterations and achieved logarithmic dependence on d in [I7] Maros al. [21 proposed 2 method based on a double mixing for solving decentralized LASSO and obtained similar theoretical guarantees in [17 31). To improve the computation efficiency, Maros al. (20) integrated accelerated proximal gradient descent with gradient tracking to solve decentralized LASSO. Despite these developments, remains unclear whether leveraging the unregularized over- parameterization and implicit regularization of decentralized optimization methods can achieve the optimal statistical guarantee over mesh networks.
Implicit regularizations of decentralized optimization. Implicit bias or regularizations of central- ized optimization methods for overparameterized models have been extensively studied [13] 30 but only few works have investigated the implicit regularization of decentralized optimization methods. Richards et al. [29] studied the implicit regularization for decentralized stochastic gradient descent for solving general unregularized convex problems. Zhu et al. [44] demonstrated
that decentralized stochastic gradient descent implicitly executes the sharpness- aware minimization
algorithm for general non-convex problems. Taheri et al. 33 studied the implicit regularization
of DGD in overparameterized classification for separable data. Recent work [22] demonstrated
the implicit regularization of the DGD2 in solving the overparameterized matrix sensing problem. Different from these works, we establish the statistical and computational results for specific non-convex sparse regression problem.
3 Preliminaries
In this section, we will introduce the basic notations used in this paper, and then formulate the DGD for solving the problem (2). Finally, we provide the necessary assumptions and definitions for the decentralized sparse regression problem.
3

---

3.1 Notations
Throughout this paper, we use [m] to denote set {1,... .m) for given positive integer m. 1. denotes d-dimensional vector that all elements are one and I denotes d-dimensional identity matrix. For ground truth parameter w², the relevant notations are support set S == {ill * 0}. positive support set S+ = [ > 0}. negative support set S == [ill3 < 0} and non-support set S := [ilw = 0}. Winax == maxjes |uu] and w == minjes |w3). Vz E R := 1s @ æ where 1s denotes a vector equal to one for all coordinates j E and equal to zero everywhere else. Symbol "O" denotes Hadamard product that (a ④ b)j = azbد Va, b Rd. The averaged signal is defined as w. = D== wtt and similar notations can be extended to u., Ø².
X : X :::..: ; mm] denotes the concatenated sample matrix, where each row of X; represents one feature vector in agent i. ||-|| denotes the Frobenius norm for vector and the spectral norm (maximum singular value) for matrix. || = maxi,j Aiy denotes infinity norm. We use
(b)) to denote that inequality a S Cb holds with some absolute constants C' that do not depend on any parameters of the problem. The notation S shares the same meaning as (()). Finally, we use a 2 b if
there exists universal constant c such that 2 cb.
3.2 Method and Assumptions
We focus on DGD solving problem 2 over mesh network, modeled an undirected graph G = {V,E) where nodes V = {1, m) represent the set of agents and edges & C V x V represent the communication links. An unordered pair {i,j} } is included in & if and only if there is bidirectional communication link between agent and j. The set of one-hop neighbors for agent i is denoted by
NG = (j 5) E (i).
DGD allows each agent to independently update its parameters based on local gradient descent and then synchronize with neighboring agents by weighted averaging these updates. The recursive iteration of DGD for each agent is described as follows.
172
x (x, (w J o und ond o - -wj)) w)))) Vi [m]:
u +1
Σ
Wij u
1l --- n
us o
5=1
(3)
Σ 5=1
m
Wis
+ vhi
o
(x] (x, (u' -a - w,))) Vi E [m],
n
where the whi = u 2 thi - ofi @ wt denotes the local estimator in agent at t iteration, the initialization is u 0,i n. ala; Vi [m]] and n) is constant step size. W is the nonnegative weight mixing matrix for the undirected mesh network, where Waj > 0 if there is a link between agents i and j, and W,; = 0 otherwise. The mixing matrix W related to the undirected graph satisfies the following assumption.
The communication network G is connected. The weight matrix W = =[w,)]?]] for this graph has the following propertix: (i) Wij = 0 for all pairs (i,j) that are not E; (ii) is double
Assumption 1.
stochastic that 1S W 1 and W1m, = 1mi (iii) the spectral gap p == W 11, 1m S 1.
This assumption is common in decentralized optimization literature 17 12 We need the following RIP condition which is key condition to obtain the optimal estimator for sparse regression.
Definition 1. The global design matrix X X/VN E N satisfies the (6, s) Resstriicee Isometry
Property (RIP) if for any s-sparse vector Rd, there is (1 - 6) w| < Xw Xw//NN <
(1 + 8) |
The RIP condition was first introduced in the compressed sensing literature in g which is a little more restrictive condition to achieve optimal statistical rate than the restricted eigenvalue condition in
11. We inherit this assumption in the centralized setting [36 42) to achieve optimal estimator error under the condition that parameter is upper bounded. Besides the global RIP condition, we have the following local RIP condition for local design matrices {X, kmm

---

Definition 2. The local design matrices X1/Vn.... X vn E Raxd satisfy the local (6max: 8)- (RIP) condition, if for any 8-Sparse vector to E TRd and any local design matrix Xs) s/,,n, there is - (max) || || X, w /nll S (1 6max) ||w]]
The definition of the local RIP condition is just for ease of proof presentation, as we do not necessitate any upper bound the local RTP parameter 6max.
Main Result
give theoretical guarantees of DGD in solving problem (2) for sparse regression problem (T) as follows.
Based the above method and assumptions.
Theorem Considering the sequence generated by ( and (4) based on DGD for solving
problem 2 and Ve > O, if the global design matrix X X/VN satisfies (6, + R)-RIP condi-
tion with bounded RIP parameter â Σ t. the local design matrices / satisfy local
(Ōmax, S + R)-RIP condition, and the mesh network satisfies assumption
]
the initialization satisfies
S min 1, (12d+ 1y2 max 6(
the constant stepsize ii satisfies
made
log at
1
1tve
1+vP
1-
n S min
(5)
6 max
4w max
W max
and the spectral gap p satisfies
X
8
p S min
20
(6)
v /50max +
80max
X
8 max,
00
then after running
= 0
log 2
iterations. There would be
0 (c)
if j E S and w min S 00(ss
w/] wÿl S
0
max
xT5 N
x .8/5
N
1s .5
if j S and whin (s)
(VVa)
if j jj
(7)
where 5 == max {1l
x"e N c .5 5 max { whan .960ç
Mechanism promote sparsity. The consensus errors induced from decentralized network com- plicate the multiplicative updates, which becomes inexact multiplicative updates as प
7t 41 - w² + p' b'+6")) + e². Compared with the exact multiplicative updates of GD 36), the challenge is that the extra error term e' outside of the multiplication prevents applying the centralized analysis trivially. In addition, the perturbation error terms p' 6 within the multiplication are much more complicated than that of the centralized setting due to additional multiple consensus errors. This requires bounding the consensus error terms carefully, which
should control the complicated perturbation errors p' 6', e' not to be large. Thus, we can use network connectivity to control the consensus errors bound these three perturbation errors small enough to make the distance between two trajectories obtained by inexact and exact multiplicative updates within statistical accuracy, which can promote sparsity the decentralized setting. The detailed theoretical mechanism of promoting sparsity has been demystified in Proposition 3
Statistical Guarantee. Based on the result ( and conditions in (5) and (6). we can observe that if the initialization is small enough and network connectivity is sufficiently well, the DGD with
early stopping can obtain the desired estimator for sparse ground truth parameter wn that achieves
the same order of statistical error as the centralized setting in (36). The formula in 7 not only
5

---

illustrates that we establish the network indoorr-indeeendent estimator enror bound but also inherits the benefit of implicit regularization, which indicates that if the signal-to-non is high enough, the statistical error is independent of ambient dimension d. In contrast, existing results in decentralized
LASSO methods [7
18 21 [1], have consistent dependence on d any case.
Computational Complexity The iteration complexity of early stopping is network-depender that is nc log ! has the dependence on stepsize, which should satisfy the condition
because the =
in (5) This suggests that poorer network connectivity leads to higher computational complexity. Although the initialization has no dependence on network connectivity, has polynomial depen- dence on and the dependence of complexity on d just logarithmic, which similar to DGD in solving LASSO in [17 and improves the polynomial dependence on d in [18].
Dependence on network connectivity, For accurate estimation. it essential that the network should be well-connected, as specified in condition (6) When this condition is not satisfied, we can run multiple rounds of communication per iteration. It is observable that the smaller ratio between the global RIP parameter ö and the local RIP parameter ōmax, and smaller ratio between the local noise and the global noise magnitude, necessitate higher degree of network connectivity. This can be understood from the perspective of heterogeneity, where smaller ratios indicate significant disparity between local and global design matrices. Consequently, condition (6) is reasonable it suggests that higher levels of heterogeneity necessitate improved network connectivity. In numerical experiments, we can observe that if p does not satisfy the condition as ( obtaining optimal statistical error is not achievable, which indicates the optimal statistical error undergoes phase transition with the network connectivity.
Our results demonstrate the benefit of overparameterrization for DGD. Theorem I shows that standard DGD is sufficient to provide a satisfied statistical estimator with efficient computation without gradient correction techniques. This finding challenges the widely held belief in decentralized optimization literature that extra techniques like gradient tracking and other gradient- cetetttoorrreetnbbseeeeete methods are necessary for heterogeneous scenarios 33 32). The following corollary considers the well-known instance where the design matrix and noise are generated from sub-Gaussian distribution, which indicates that DGD with early stopping can achieve the minimax optimal statistical rate under the &2 metric.
Corollary 1. Suppose that entries of global design matrix X generated from i.i.d Gaub-Gassiann distribution, and the total sample size satisfies N Z (slog + log d)). The noise vector is generated from independent o2-sub-Gaussian Gaussian entries, and the initialization set as Theorem 1 with
c=0
oov
logd
If the spectral gap satisfies p S me and stepsize is set as n =
log 1 iterations, the sequence generated by and based on DGD for solving problem would obtuin estimator that Iw' w S a with probability at least 8ds-
then after ranning O
N
Corollary T indicates that in the sub- Sab-Gaussian setting, network-independent statistical error obtained
by DGD matches optimal rate (av log
under f2 metric the centralized setting (8 this
N
context, the condition for network connectivity implies that the smaller is required the number of agents m increases. This is reasonable because when the total sample size is fixed, an increase in the number of agents results in fewer samples assigned to each agent. Consequently, better network connectivity is necessary to achieve optimal estimation.
Communication Efficient DGD via Truncation
It is apparent that iterations in 3 and 4 of DGD, each agent has to transmit two d-dimensional vectors t and t to its neighboring agents per iteration. Because we are considering the high-
dimensional regime where the feature has ultra-high dimension, which leads the O (d 7/c log a high communication complexity (in terms of the bits transmitted) for DGD. The primary idea is

---

whether it is possible to transmit fewer partial elements instead of the entire d-dimensional vectors for u² of. in all rounds of communication. Since all elements of u' and wf equal a at initialization, we can utilize the one step of local gradient descent step in each agent to distinguish the support set and non-support based on changes of magnitudes for each element. The intuition that the elements on the support would grow more rapidly than those on the non-support. Thus, we propose the Truncated Decentralized Gradient Descent (T-DGD) as
4 --- o ((uts
Σ Wi Trun, j=l
[X] (u о Cu
- 2 - y1
7
m Wiy Trun, ((0's + -
[ (x, (u' v o u wn o o y,
for Ví E [m], where Trun,(#) (œ) is the operator that preserves only the s largest magnitude elements of the vector æ while setting all other elements to zero. The following proposition shows the benefit of T-DGD in sparse regression under proper conditions.
Proposition 1. With the same setup in Corollary if the ground truth w satisfies
2
2
88 mmax max + ov logd then the sequence generated by T-DGD K for solving prob-
lem 2 would obtain estimator that || -woll S ov slogd with probability at least
However, the communication complexity in terms of transmitted bits would be most sd
o
(. max vNY/
}) (
(
log
To ensure condition
vs8max W max + o Ing d satisfied, it is necessary to require that each
agent has sufficient samples and SNR is high enough such that 8max
w Wiin v /sw max
and σ log T
wiin This proposition enables each agent to transmit only elements of d-dimensional vector per communication round, which can achieve optimal statistical rate and eliminate the d-linear increasing communication complexity. The result in Proposition I validates the usefulness of the Hadamard product over prrerarrmettiizooionn in decentralized gradient- basee optimization.
Numerical Results
This section conducts the experimental studies to evaluate the theoretical findings of DGD and T-DGD for solving problem (2) in Subsection 6.1 Subsection 6.2 respectively. In Subsection 663 compare the effectiveness of implicit regularization of DGD with explicit regularization based decentralized methods. The communication networks G are generated from Erdös Rényi (ER) graphs with link activation under given probabilities. By default, unless stated otherwise, all the design matrices X have i.i.d. standard Gaussian elements, noise & follows i.i.d. (0, 0.5²) distribution, and the magnitudes of elements on support S are 1. All experiments are conducted on 12th Gen Intel(R) Core(TM) 1. processor and 16.0GB RAM under Windows 11 system.
6.1 Simulations on DGD
We organize the experiments as follows: We visualize the dynamics of averaged variables and consensus errors that allow us to evaluate the implicit regularization of DGD and the soundness of our technical analysis. 2) We check whether DGD can achieve optimal statistical error, the impacts of ambient dimension d and initialization scale on statistical and computational properties. 3) We evaluate the condition of (6) that reveals the relationship between network connectivity and network scale for achieving the statistical accuracy of centralized setting.
Dynamics of w", u², o' and u. uu, t v². In this case, we set d 2000, 10,
10, N = 400, = 0.1778, a = 10-6, Fig. ((a) demonstrates the convergence of averaged w² in DGD, showing successful convergence of elements support S and maintenance of small
7

---

magnitudes for elements on non-support S Fig. I(b) and Fig. [[c] further illustrate how DGD utilizes प' and e' fit parameters on positive and negative support, respectively. Additionally, the magnitudes of u² and o' on non-positive and non-negative support remain small enough as the initialization. Consensus errors u u' and g²d r² are depicted Fig. ((d) and Fig. [(e) respectively. The trends in these curves correspond to the magnitudes of the model parameter, affirming the validity our analysis.
17
Magnitaal
Magnitude
Magnitude
Derratonn
(a)
(b) (u')
(c) (w')
Magcaltans unde
Magaitabe
Iteration
Iteration
(d)
u
(c) V
Figure Dynamics of avergaed variables and consensus errors.
Impact of d and a on optimal estimation. We vary the dimension of d (4 102, 4 10 4 10t) to access effect of d on both statistical and computational properties. With s [log d| and N chosen satisfy s log d/N 0.25, we aim maintain the same order optimal statistical error logd
0
Testing is conducted on two networks with 20 but different p. For each d,
select the maximum initialization that achieves optimal statistical error, resulting in 10-8 for d = 4 x 10², a = 10 8.5 for = 4 x 10x and a 10 99 for d = x 10a. The results for p 0.1778 and - 0.7519 are displayed in Fig. 2 and Fig. 2 respectively. It is observable that DGD obtains estimators with statistical error matching that the centralized setting, with computational complexity remaining largely unaffected by ambient dimension d across different
network conditions. To assess the influence of a, we set 2000, 10, m = 20, N 400,
and different values for network with 20, p 0.7778. The results in Fig. 2(c) illustrate that it is necessary to use small enough initialization to obtain optimal estimator.
400
1000
1000
P)
10
log( 1011
40000
10
log m
Log
Gompglood stguteal 67D
parmylin drggeaaeroy
00 Bad 3000R22
ltraation
Iteratinn
Iteration
(a) 20, 0.1778
(b) 20. 0.7519
(c) 20, 0.1778
Figure 2: Impact of ambient dimension d and initialization
Dependence on P and m. We set 2000, 10, N 200, a with different numbers of agents. The results are shown in Fig. where Fig. 3(a) and Fig.
10-6 and test on networks

---

10
10
0.1778 0.5503
w Il9)
Log - w (1F)
70 100
P 0.9163
Centralized
Centraliace
1og Soodlie
lag( (1kee
10
20
100
Iteraion
Iteration
Iteration
(a)
(h)
(c)
Figure 3: (a) p 0.9400; (b) p 0.1778; (c) 10.
3(b) display the performance with varied numbers of agents under fixed 0.9400 and fixed P 0.1778, respectively. Fig. 33a] indicates that DGD would not obtaïn the optimal estimator as the centralized setting when the number of agents is large which violates the condition in (6). When network connectivity is sufficiently connected as = 0.1778, Fig. 3(b) conveys that this can allow a larger scale of agents to attain optimal statistical error. In Fig. 3(c) we fix
10 and observe the phenomenon under varied p by choosing proper stepsizes to achieve the best statistical error. Fig. [(e) illustrates that p would influence the stopping time when DGD obtain the optimal estimator. The worse the network, the more iterations it takes to find the optimal estimator.
6.2 Simulations on T-DGD
In this section, we evaluate the effectiveness of T-DGD. Initially, we vary the values N, keeping the other parameters consistent with the simulations in Fig. [ Fig. 4((a illustrates that when each agent has inadequate samples (N 100, n = 10), T-DGD would fail in achieving optimal estimation. However, with increasing local samples (N 400, 10), T-DGD matches DGD in both statistical accuracy and convergence performance. Subsequently, we set the magnitudes of the ground truth on support 100 and N 300. The performance is depicted
dashed lines in Fig. 4(C) indicating failure of T-DGD under higher noise level (a = 0.5). We further reduce the noise magnitude to 0.1, and solid lines in Fig. [Kc] demonstttt the usefulness of T-DGD in sparse regression. These observations validate the statement Proposition T
-Centraizzed DGD
-enirunized DGD
00
1000 will
110
m
10g
Log
Log
180 Iteration
Iteration
Iteration
(a)
(b)
Figure 4: Na)N 100; (b) N 400; (c) Different noise intensities.
6.3 Comparison with explicit regularization
We have compared our proposed method with three existing decentralized methods, namely: CTA- DGD (LASSO) [18], ATC-DGD (LASSO) [17], and DGT (NetLASSO) [31]. These methods are all derived based on the LASSO formulation with explicit regularization. The numerical results presented in Fig. 5 compare all four methods under three different network connectivity settings. For each method, we tuned the step size to achieve the best performance. Our proposed method demonstrated the best recovery performance in all network settings with minimal iterations.

---

CLA DCD (LASBO] ATC-DGGNNAASO
GTASEA [LASSO) ATO DNDILASSO) (ILLSO)
CTA DED (LA880)
ATC-DIIDXLASSS)
DCTTISHE.A58O)
log([
log
log
2010
2000
4013
100
2013
2010
2000
20
1300
140
X09
Ieeration
Iteration
Iteration
(a) p= 0.9428
(b) p = 0.6367
(c) p 0.1384
Figure 5: Comparison with decentralized sparse solvers under varying communication network. The setting is d = 1000, k 5, m = 50, N 280, a = 0.5 and magnitude of sparse signal is 10.
We further compared T-DGD with existing methods with truncated versions of existing methods: Trun-CTA-DGD (LASSO), Trun-ATC-DGD (LASSO), and Trun-DGT (NetLASSO) which use the same Top-s truncation operator. As shown Fig. 6 our proposed method is the only one achieve successful recovery, while all other truncated decentralized methods failed. The numerical evidence demonstrates that naively combining sparsification with decentralized algorithms is not granted to converge. This is precisely one of the motivations of this work: to provide communication-efficiii algorithms with both provably statistical and computational guarantees. This result also demonstrates the unique benefit of overparamcterization and implicit regularization for decentralized learning setting, which has not been explored in the literature of learning theory.
Trun-CTA- CTA-DGD (LASSO)
Pru--NTC-DGDLLLSSSO
log w w
Trun Trm- (NtTLNSSSN
Proposed
20
40
80
30
100
120
140
100
150
202
Iteration
Figure 6: Truncated version: comparison with truncated decentralized sparse solvers. The setting is
1000, 8 = 5, 50, 550, a 0.1, p = 0.2458 and magnitude of sparse signal
7 Conclusion
In this paper, we study the implicit regularization decentralized gradient descent for decentralized sparse regression in the unpenalized and overparameterized regimes. We establish both statistical and computational guarantees for the decentralized estimator under mild conditions of network connectivity, underscoring the utility of DGD in addressing overparameterized models. Furthermore, the proposed truncated DGD (T-DGD) offers promising idea to reduce communication complexity while maintaining performance. In future work, exploring the possibility of relaxing the RIP condition our assumption and leveraging the restricted eigenvalue condition to achieve optimal estimator in the decentralized setting is interesting topic. Additionally, investigating alternative forms of implicit regularizations in decentralized optimization algorithms for more complicated overparameterized models is another intriguing direction.
10

---

References
[1] Alekh Agarwal, Sahand Negahban, and Martin J Wainwright. Fast global convergence rates of gradient methods for high- high-dimensional statistical recovery. Advances in Neural Information Processing Systems, 23, 2010.
[2] Zeyuan Allen-Zhu and Yuanzhi Li. Towards understanding ensemble, knowledge distillation and self-distillation in deep learning. In The Eleventh International Conference on Learning Representations, 2022.
[3] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. convergence theory for deep learning via over-paramettrrizaton.. In International conference machine learning, pages 242-252. PMLR, 2019.
[4] Maksym Andriushchenko, Aditya Vardhan Varre, Loucas Pillaud- Vivien, and Nicolas Flammar- ion. Sgd with large step sizes learns sparse features. In International Conference on Machine Learning, pages 903-925. PMLR, 2023.
[5] Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of op- timization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning, pages 322-332. PMLR, 2019.
[6] Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine- learning practice and the classical bias variine trade-off. Proceedings of the National Academy of Sciences, 11633))15849-115
2019.
[7] Raphaël Berthier. Incremental learning in diagonal linear networks. Journal of Machine Learning Research, 24(171):1-22) 2023.
[8] Emmanuel Candes and Terence Tao. Decoding by linear programming. IEEE transactions on information theory, (1(12):403342215 2005.
[9] Yuan Cao, Zixiang Chen, Misha Belkin, and Quanquan Gu. Benign overfitting in two-layer convolutional neural networks. Advances in neural information processing systems, 35:25237~ 25250, 2022.
[10] Hung-Hsu Chou, Johannes Maly, and Holger Rauhut. More is less: inducing sparsity via overparameterizatton. Information and Inference: A Journal of the IMA, 12(3):137-1440, 2023.
[11] Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International conference on machine learning, pages 1675-1685. PMLR, 2019.
[12] Jianqing Fan, Zhuoran Yang, and Mengxin Yu. Understanding implicit regularization in over-parameterized single index model. Journal of the American Statistical Association, 1 118(544)2315--25) 2328, 2023.
[13] Suriya Gunasckar, Jason Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias in terms of optimization geometry. In International Conference on Machine Learning, pages 1841. PMLR, 2018.
[14] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-leve performance on imagenet classification. In Proceedings of the IEEE international conference computer vision, pages 1026-1034, 2015.
[15] Peter D Hoff. Lasso, fractional norm and structured sparse estimation using hadamard product parametrization. Computational Statistics Data Analysis, 115:186-198. 198, 2017.
[16] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
[17] Yao Ji, Gesualdo Scutari, Ying Sun, and Harsha Honnappa. Distributed (atc) gradient descent for high dimension sparse regression. IEEE Transactions Information Theory, 2023,
11

---

[18] Yao Ji, Gesualdo Scutari, Ying Sun, and Harsha Honnappa. Distributed sparse regression via penalization. Journal of Machine Learning Research, 24(27)):1-6,, 2023.
[19] Jiangyuan Li, Thanh Nguyen, Chinmay Hegde, and Ka Wai Wong. Implicit sparse regularization: The impact of depth and early stopping. Advances in Neural Information Processing Systems, 34:28298 14422298-2830, 2021.
[20] Marie Maros and Gesualdo Scutari. Acceleration distributed sparse regression. Advances in Neural Information Processing Systems, 35:36832-36844, 2022.
[21] Marie Maros and Gesualdo Scutari. Dgd A linearly convergent distributed algorithm for high-dimensional statistical recovery. Advances in Neural Information Processing Systems, 35:3475-344 -387, 2022.
[22] Marie Maros and Gesualdo Scutari. Decentralized matrix sensing: Statistical guarantees and fast convergence. Advances in Neural Information Processing Systems, 36, 2024.
[23] Mor Shpigel Nacson, Kavya Ravichandran, Nathan Srebro, and Daniel Soudry. Implicit bias of the step size in linear diagonal neural networks. In International Conference on Machine Learning, pages 16270-16295. PMLR, 2022.
[24] Eshaan Nichani, Yu Bai, and Jason D Lee. Identifying good directions escape the ntk regime and efficiently learn low-degree plus sparse polynomials. Advances in Neural Information Processing Systems, 35:14568-14581 2022.
[25] Hristo Georgiev Papazov, Scott Pesme, and Nicolas Flammarion. Leveraging continuous time to understand momentum when training diagonal linear networks. In Proceedings of the 27th International Conference on Artificial Intelligence and Statistics (AIS-TATS) 2024., 2024.
[26] Scott Pesme and Nicolas Flammarion. Saddle-to-saddle dynamics in diagonal linear networks. Advances in Neural Information Processing Systems, 36, 2024.
[27] Scott Pesme, Loucas Pillaud-Vivis and Nicolas Flammarion. Implicit bias of sgd for diagonal linear networks: provable benefit of stochasticity. Advances in Neural Information Processing Systems, 34:29218-29230, 2021.
[28] Garvesh Raskutti, Martin Wainwright, and Bin Yu. Minimax rates of estimation for high- dimensional linear regression over f_g-balls. IEEE transactions on information theory, 57(10):6976-6994, 2011.
[29] Dominic Richards and Patrick Rebeschini. Graph-dependent implicit regularisation for dis- tributed stochastic subgradient descent. Journal of Machine Learning Research, 21(34):1-44, 2020.
[30] Ohad Shamir. The implicit bias of benign overfitting. In Conference on Learning Theory, pages 448 478. PMLR, 2022.
[31] Ying Sun, Marie Maros, Gesualdo Scutari, and Guang Cheng. High-dimensional inference over networks: Linear convergence and statistical guarantees. arXiv preprint arXiv:2201.08507 2022.
[32] Ying Sun, Gesualdo Scutari, and Amir Daneshmand. Distributed optimization based on gradient tracking revisited: Enhancing convergence rate via surrogation. SIAM Journal on Optimization, 32(2):354 385, 2022.
[33] Hossein Taheri and Christos Thrampoulidis. On generalization of decentralized learning with separable data. In International Conference on Artificial Intelligence and Statistics, pages 4917-4945. PMLR, 2023.
[34] Robert Tibshirani. Statistical Society Series B: Statistical Methodology, 58(1):267-283, 1996.
Regression shrinkage and selection via the lasso. Journal of the Royal
[35] Gal Vardi. On the implicit bias deep-learning algorithms. Communications of the ACM, 66(6):86-93, 2023.
12

---

[36] Tomas Vaskevicius, Varun Kanade, and Patrick Rebeschini. Implicit regularization for optimal sparse recovery. Advances Neural Information Processing Systems, 32, 2019.
[37] Martin Wainwright. Iligh-dimensionl statistics; non-asymptotic viewpoint, volume 48. Cambridge university press, 2019.
[38] Blake Woodworth, Suriya Gunasekar, Jason D Lee, Edward Moroshko, Pedro Savarese, Itay Golan, Daniel Soudry, and Nathan Srebro. Kernel and rich regimes in overparametrized models. In Conference on Learning Theory, pages 3635-367, PMLR, 2020.
[39] Kun Yuan, Qing Ling, and Wotao Yin. On the convergence of decentralized gradient descent. SIAM Journal on Optimization, 1635):1835-1844, 2016.
[40] Chulhee Yun, Shankar Krishnan, and Hossein Mobahi. A unifying view on implicit bias in training linear neural networks. International Conference on Learning Representations, 2020.
[41] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In International Conference on Learning Representations, 2016.
[42] Peng Zhao, Yun Yang, and Qiao-Chu He. Implicit regularization via hadamard product over- parametrization in high-dimensional linear regression. arXiv preprint arXiv: (eee:09039903 2(4):8, 2019.
[43] Mo Zhou and Rong Ge. Implicit regularization leads benign overfitting for sparse linear regression. In International Conference on Machine Learning, pages 42543-42573 PMLR, 2023.
[44] Tongtian Zhu, Fengxiang He, Kaixuan Chen, Mingli Song, and Dacheng Tao. Decentralized sgd and average-direction sam are asymptotically equivalent. In International Conference Machine Learning, pages 43005-43033 PMLR, 2023.
13

---

A Appendix.A
Section A.1 A.2 give the additional notations and useful basic lemmas, respectively. Section A.3 provides the properties for the simplified setting where all the elements of ground truth parameter w are non-negative. Section A.4 gives the key proposition for the general case where w" contains both positive and negative elements on support S. Final Section A.5 concludes the proofs for the Theorem I Corollary and Proposition I in the main paper based on Proposition Bin Section A.4
A.1 Full Notations
In addition to introduced notations from Section 3.1 in the main paper, we need additional notations to present the proof. The consensus error is denoted as f. == u and notations A
u,s+ = A @ 1ss
f.
fi t u.S- u,se can be defined similarly. The additional notations are defined as
A
U' == [u u
A
U' ='
Vuf U V = Vufi(T'
Vulm ( 1'),
Vu)(U",V') vaF((''v')lm
Val (U", Vo = =[Vuii(u v Vulm [bm))]
Vuf U v*) = Vufi(u, 0t)) )..,, Vufm(z', vmm)
(9)
Above definitions can be also extended to variable v similarly.
A.2
Premilary Lemmas
Lemma 1.
(Theorem 6.5 in (37g) Consider the random feature vector x E IR that all entries obey
i..dd 1-sub- sub-Gaussian distribution, if the sample size satisfies n Z 8-2 (s log ed + +log 2) then the sample covariance matrix X
Ei= x. satisfies (ō, R)P condition with probability
Lemma 2. (Lemma A.3
(361) Suppose that E EKa satisfies the (ō, R)- if Rd is v
s-sparse vector, then x
1) w /
Lemma 3. (Lemma A.4 36 Suppose that Vx= X E Raxd that satisfies (8, R)-PPP with S 1
then we have
x w
s [d|[w|| [|ll boo Vw E 12d.
n2
Lemma 4. (Lemma B.5 in (42)) Let R" is vector of independent a random
variables and all l2 norm of column vectors of X E Rgx are bounded, then with high probability
x
S ov logd
1 Mg such that
A.3 Non-negative Case
We consider the simplified setting where all the elements support positive for ground truth wt. The following lemma shows the recursion of average variable u' on support S and non-support S
Lemma 5. Consider the sequence {u'-t) generated according to (3) and ( by DGD for solving loss function in (2), the average signal E' on support S and non-support S are updated according the following formulas
1a - 4n (u's 2 Ou's - -w") 4n x" X
X
us = =u's O
(u's O u'sc) + 4n
N
N
X -1
4v)
1i. O T'S - -w") -41pp
Anga
(10)
X
XTg
XXX
++1 g=
Uzgo O
1a 4n
U O T'
+
-
[ O UTs
w''
N
N
N
14

---

Ang') 4nf
(11)
where the perturbed error terms p', .² .',, f" induced from decentralized network are defined as +
p'
1
X
1)
(2u's
@
Li g
A35) +
+34
8
m
n1
X
X
(2uge
ge
+
(12)
Y1
1
m
X X;
G'
U U's - + 2u's 3 A
A
m
n1
+ S
A t.
E
X X;
Ug: 1/d
(13)
n
n
M
X X
X (2u's 4
9
22n's ② A
+ A 6u 1 4/5
Sc
+
o
A 4.
m
n
n
(14)
f
1
m
X
X X:
I
Ui's C u's ~=" + +2u's
2 A ti + A/3
gc
m
n
X X;
Tgg + A 1.1 2
1 X
+
8e)
(15)
n
11
Proof. Based on the updating of DGD, one-step iteration of the averaged parameter is
m
++ u v/VF(('))
n
Σ
(Vii(u)) - V)(("'))).
(16)
m
The gradient difference has the formula as
f(((T)) (
= गه o
(1 x X;
11
w²) - -
4 x
w²) - 4 x
-xx E.
u 1 - -
wx) - -xTE,
+ 0
x X; (
@ )u'!)
1/
1 XxT x [ ② w 2t' 2 4r +
A
4
XTT,
-xXxx x
(2Th²
(17)
where the last inequality is due to the definition of A t. Substituting the above equality into would have
(16)
X X w" + N
X N
u²
o
Us C Uss
Uuso 3 =...)=
[
+
U
3 U's - w*)
N
m
x X;
4rru
1
Ju's O A/5 + 2u's o A
m
i=1
15

---

X X
{xxx n1
x
1 (A + + A
+2
Uge
+
71
X X;
n
4n m
1 m
A 2,t
Ug ② us w=
x
n1 - 1 [u's 2 u's w=)
x X;
(u'se 2 u's=)
n
n
1 m
X x,
41 m
Σ
A t.
2
I -I
UU's o A + +2u's o A''
n
X X;
1.1 +
{x xx (xxx==1)
1) (A5s t/ o A33 A o A
+2
U'/e
n
n
x X;
A
t
6.
n
(18)
Because there are 1
m -
U
0
and
m
1. A
s
(
② W's w²) = -0, the above
formula can be simplified as
x x
X"
41/
U
U
w"
+
T TTg.)
N
N
XXT
+
I
Us
Uss
w=)
N
X X
4nj
2
1
TT's o )
+2
X X
U'g
+
X. -1)
1
(4 to o -3 + + O''
n
n1
x X;
ti
6,
5z
n
1
X x. Xx
Anl
(n's 3 n's -w")
m
n1
1=1
X X;
XTE:
Ugg=
3 Ug=))
n
n
x x;
41 m 1=1
1.4 3
2
1
(u's の 4/4 + +2u's の A''
x T X;
x Xi
1) (A! Li o 2 + A o A
+2
Ugg:
A
5'
+
n
x X;
+
A
t. Se
A 5:
(19)
Thus, this would obtain the recursion 100 for support averaged signal.
16

---

The recursion of optimization error on sup-su S becomes
x T
X
x'e
Xxx
g
Ug.
4nju'
U
T's:)
+
1
a -oos--w"))
N
N
N
1
X X
4mpuss
2
1
uUs + A
m
n
X
T
X
x x
1)
(43 の A3
+2
Ug
8c
+
71
X X;
1. 8
8-
T1
1
x 1
41j
Us ② U.s w'
i=
X
X;
XTE
Uge
Uge
T1
x X; - 1
-1
41|
Sr
2
TT'S o 23
1=1
X T X
x x -1 1) 4 23
fii 8o
+2
U
+
7
x X;
2.6 g
(20)
Rearranging the above equality would obtain the 11
The following lemma shows the recursion of consensus error on support S and non aup-support S
Lemma 6. Consider the sequence {u'+t} generated according to (3) and (4) by DGD for solving loss function in 2,, the consensus error A' t on support S and non-support S have following recursion
11.0 SpllA'sloo (1+anl (V50max + 1) 1luis C u's
++1 S
w 11 + 2d (u's= A
X E.
+ 2 (V=dmax +1) ([ (1 + =11 2 + max
x c:
+ 4pm
V (6max +5) Ju's O V's w0ll + max
x g
+ 2d +2ds + +
(21)
N
A a1.0 S p A 2o
[+ 4n Vsdmax
L''s 2 T''
w01loo + V50max (1|TiSll + -1AAه|1_.)
X c: max
6d ([|
Ioo + A (A
n
+4pn loo (vo (vo(mmxx (Fmux + 5) lluu' 3 unss
un 1l + /
-1 + +11 + 4d 1
+ max
x c.
+
x E
)
(22)
n
N
17

---

Proof. Based on the iteration of DGD, there is
U4+1 I
1m
m m
(U' (VS(()))
W
Im
1 m
1m 1
m
= (V''-NVS(U")) (w-
1
Im 1m
m
(U'J -(((()+) (w-
W
1m 1
(23)
m
m)
Thus, the consensus error support S has recursion as follows
(1)
| I1
p
+ pn max
1s O (Vii(u())) (FF(')
S p
A 1 00
+ oT max
|ss @ (Vii(u"))) V
+ Mr max
1s ④ (Vii(u') - vF(w'))lle
(8)
$ p
4pn
A |o ((vodmax + +1) LT's 3 T'S w' 11 +
X
+2d T'S
max | +
+ (v + 1) I oo |
n
+4d
s= 01:00 + (V30max + 1) A Is + +2d A S= 1
+ +4pm | oooo
2 2VV50max + 1) || 1o.0 || ا llo + +4d 1d ||
A x
+ (Voōmax
+ 1)
|1 + 2d A
1
+ (v& (6max + +)) lu's ② uns
un
no
X &,
x E
+ max + 2d 1us= 1:c
+
i
N
(sa))
[1
(Voo + 1) l C u'ss -wwll 101100 +d (u's. + A0)))²
+ (1uÁlll + +| 2 + max X E:
+ 2 ( V00max
(8((mmx +0) Lt'S @ U'S- w w0ll
X &:
+ 4pm
| 1o.0
+ max
n
T E
2d (u's- + A3.)²)
+
(24)
N
where (i) is due to the defined spectral gap of network in Assumption and (ii) uses the gradient difference formula in [7] and
4 X;
4 &,
Vl((w)) - VF(w)) u
(u' ④ v0" w²)
n
4x
4x T g
म o
u
c u
w²)
(25)
N
N
X X;
x X -1)
I
1
77
w")
n
N
4 g
4X7E: E:
N
n
18

---

(26)
and local and global RIP conditions. The (iii) summing up terms involved | Il and | separately.
The recursion of consensus error on sup-su S part is as follows
++1 Se
S
A S.
-l + on max
1ss= @ (Vf((u)) vF(
S p A Sz
+ pr max
1s o (Vii(u)) V/((w') ))
+ pm pm
1s
3 (Vfi ( - VF(x')) 1l
20
+ 4pn
A Sz |l
L's 2 T's
w' 1|<
X
+2d
S'S
|
+
max
+ 20
n
+4d T
S=sll 1lo
+
Vodmax
s 1/ + +2d +2d||A
l
+ +4pn uss=
2 20max
|
/ lmo + + | o0 | 00
+ md
A s
113
00
+
2d
A S- 11:0
+ V (5max +6) Ju's o u's w 101
X &,
x E
+ 4d udds
12
+ max
+
N
$ sp A 1l
1+ 1+477 41
Vodmax
uus A u's
w" w011oc + Vodmax (1luš|l + +|ااا|1
X &:
+ 6d (1|
+
Sc 110
2 + max
(V5 + 8) 1T's 3 Tts - w'
+ +4p IT's 10
+ s0x A
X
x xT
<1 + +1lA'lloc) + 4d 1''= + max
+
(27)
N
The following proposition shows the dynamics of average variable Vř and consensus error A 1, in the form of inductive hypothesis. Before showing the proposition, define the following quantities. We define T nyu log 1 and for any integer k 2 -1, Tk 2 and T Σ Ti with a
T-1 0 where T3 denotes the number of iterations between (k 1)-th and k-th induction step. Defining K logg Miaax of perturbed error in 1)-th induction step and constant scale parameter == T- Proposition 2. With the same setting as Theorem 7 the following claims hold k = 0, I.. K - steps.
the number of induction steps, B₁ == Waaxx denotes the upper bound
(a) For Tw-1 St < Tk that Vk E [K]. there is
I''s T
wl < Winx
Te-1
T.-I w"
(b) For Yk E [K], there is
U
o Us
<
Minxx 24
00
(c) For Tx-1 St Tx that Vk E [K], it has
A s
48p
2 n |T' /1.00 Bv. In addition, the
refined element-wise bound is A
4.p² u
BR, Vj S.
19

---

(d) For 1 R that vk E [K]] it has
IT's l Bk- In addition, the A s. 1l I 43p2
refined element-wise bound is ر S 43p r/ [21 B&r Vj Sa.
(e) For Vk E [K] and Vj E S, a² S f x- w 4B,.
Proof. Proof idea: Inductions (a), (b), (e) indicate that if the connectivity of the network is sufficiently well (p is small enough), the trajectory of the averaged signal w² would mimic that of the centralized case [36]. Different from the centralized setting, these three claims are based on inductions (c) and (d), which guarantee that the consensus error along both support S and non-support S can be controlled based on the magnitude of the respective signals. We utilize this property to reparameterize consensus error by Hadamard product based on the averaged signal. Thus, the perturbed error terms induced by the decentralized network in the recursion of the averaged signal can be quantitatively through the reparameterized consensus error. Then conditions network connectivity and step size can guarantee that the averaged signal in decentralized would have properties in inductions (a), (b), (e) based inductions (c), (d).
Base case: As the initialization 0 ald, Vi [m]] Due to the condition on a, the base case is true.
Induction Step: If the above (a)-(c) induction hypotheses hold all until some < l: < K 1, we should prove they still hold + 1-th induction step.
(a) The magnitude of p' in
12 under this induction step can be bounded based on induc-
tions (c), (d). v T--1 S 1 <
TR. if u keep same order as initialization, then there
is
ps S 36x
BB L + (Vssmax +3) (48ptnBr BBs |==
w Be + (43ptn) TT's 1l BB 2) )²)
+ 2d
83p2n
3 B/DBa
(28)
16
where the first inequality is based on Lemma 2 and Lemma 3 the last inequality is due to step size, value B3 |T's 12 S 2winxxx network connectivity condition and global RIP condition that
p² 58mmax I v88= < 1.
For the perturbation q² in 13). which is error term outside the multiplicative updates in 10 based on induction (a), fine-grained upper (c), there is Vjj
3/DB2
x &
10'1 < B
Vodmaax
Ju's C Ut' - w
+
max
16
n
vpBxluyl
(29)
32
where the first inequality is due to (88 by comparing formula of q' with p and last inequality is due to step size condition and such that pt max;
x
x N
W Then q could be
reparameterized as q' = r O zts where ||ra| 00
<
JpB
for Vt that T St < Tk. the perturbed
16
optimization recursion on support over decentralized network in (TO) becomes
(u (u's)
c (1a 4n (u's @ unss
w + E
p + +r)) E
(30)
where the perturbation errors EY and F are defined as
E = x X
C U's w'
N
20

---

X
X N
x" N
E3
U
u(s.)
(31)
S Bk. which is based on the upper bound in 70 Then the proof divided into the following two cases based on the magnitude of the element in w
Because there is 33
E oo
1|p'
ac +
+1
2 ( S w + 4B, (1) Vj that w 2 20 based on induction hypothesis (e) that TT)
T
2
there
u
I 5 wwy which illustrates that it satisfies the conditions in Lemma B.10
in 36 Then because induction hypothesis (a) and (b) are true until t-th iteration, then if (ut)² w3
Be
Wmaz then 2
(u) (1) -w3
2
Wmax 2
else
(un)) 2 - -wjl ||_ Bg, then
(uttt²² -w3
Bg- Combined with two cases, we can conclude
that (a) also holds for (1 + 1)-th iteration for j that w² 20BB.
(2) For arbitrary j-th elements whose magnitude is not sufficiently larger than the perturbation that wj < 20 based on the upper bound in induction (e), perturbation bound and monotonic property in
Lemma B.6 in [36], we can guarantee that (zz²) ) would keep staying in (0, wz + +4B+l. With condition
wj < 20 we can conclude that (m)²)) wj S max(wj. 4B S 20 <
Combined these two cases would finish proof of (a).
(b) To prove this statement, we should guarantee that there are sufficient iterative steps in the (A: (k-1))a 1) induction that can make ("'
Tx un' decrease at least by half from the beginning iteration of current induction stage that of next induction stage. The proof is also divided into two cases.
(u))
Tu
(1) The one case that Vj that it already has
w/
Wmass then with similar proof in 2FFF.
(a), we can guarantee that V/ 2 Tx-1.
(Tt)) 2
w
Thus, for these supports, we prove the
26
(le + 1) induction also holds.
(2) The second case is Vj that there is
11 x-
2
w Waax 2
20B Based on the upper
T.-1
bound in induction (e) that
S w 4Bx, then Uj
w must satisfy
wÿ 20 w² 2 20.3s respectively. This means म. Tx-1 is far away from w at least 20 distance.
(u Fx +)
According to Lemma B.12 in 36 to achieve
mn S 20B the sufficient condition
(w))²
for the number of iterations / in current induction stage is / verify the setting of T3 as follows
15
log
Now we Ba
32
7
19 11
24
1
T
log a
m max
(w )2
1
log
40q Br
o3
3 (wxz)
1
log
2mw
T Tz-1
17
21

---

1 log
(wz)² )
(32)
2mw
2
16
B
where the first inequality is due to the definition of By and small initialization condition that ç and the second inequality is due to w N 20Bb and lower bound in induction
3(
2
(e) that U N-1
2 a² The last inequality is because á S 16 Wias
40 2
S
16 Wanxx
40 2
16Bb.
Thus, combining the above two cases and similar proof, we can conclude that Vt 2 Tk. there is (T's) wt
2
Winx.. This completes the proof of induction (b).
2k41
(c) To make the consensus error satisfy the above induction, VI that T Si<(+1 < Tk, based
on one step iteration in (24) of Lemma induction (a), (c) and step size condition 1) -
1-vP
64p wanx
has
vo 1 + 4n (Vohmmux + 1)
|| lu's 2 u's w0 w010 + 2d (u's
+ 5/):)² +2 (vo0max +
X.'s.
))
11 1- Vp
L
max
(33)
n
2
Then the recursion (24)
in Lemma 6
becomes
| ++1
4
+ VP
8pån |ušlloo BR + Apån) 3
| Br
2
4
+ vD
B 8+1)
p²n -ل4s 11 B
(34)
(1 c10 (1 (1- -
2
where the last inequality is based on induction such as if ||
A
S <43pån
ET'sl BB, then based
(10(1-w) there is
30
and step size condition S
Waae
Iu's loo (1 co0 (1 v
(35)
To guarantee that
34 holds induction (c), the sufficient condition is
Ltve 2
B 1
(1 vP)) S.
(36)
(1 C10
The eio should be chosen that
1tv0
< 1, which means that Cio should satisfy Cio S
2(1 211-c10 (1-v)))
Then we can set C10
which results in (oeno(-->))?
Based
1-v0
Ve(L+Vo)+I+V))
on 36). the lower bound for B
Unfolding the recursion in 24 from the beginning of (k- 1)-th induction to the beginning of k-th induction based on (34b and combining induction (a) would have
T"
2
2 2'T
1-
Tx
S
T --- s
+
B
U
T
1
2
2
1=0
4 2v VI+ vp
TT1
Σ
1 + Vp
2
-1-
T u
V
1+ vp
i=0
8
+ +48pin
1 vp)
T
Bs
2
22

---

4V2p8nBB
T-1
1 + vD
2 1-i
Σ
U
VI+ VD
2
1=0
2
+48pi11
1 + vp
2
Tx' U
Bb
2
V
1 1+ vp
2
2v2
1+ V 1+
S 43ppn
1+ vP 2
T
BB +
4p 17
Bx
00
(1- vP) VI+ vp
00
T
< 4pån
T Us
3
1
vP
8
Bk.
(37)
2
1 vp
where both the second and third inequalities use lower bound in (35 To guarantee that the last inequality satisfies the induction (c), the B and p should satisfy the following condition
2
VP 2
B&
B
I B
(38)
One sufficient condition for achieving above inequality is T-VP S G. Combine above lower bound
8
of B, we can verify that 3 = 1-V0 satisfies this condition and following inequality is attained
32
TI log +
+
vp
(39)
4'
which implies that the step size n should satisfy
1 In log αt
1 + 1
7 S
(40)
-2 2
log
1+v
One sufficient condition for achieving inequality is 1
5
based on inequality that
4e max
In 1 M (
L+vE 1. Combining all the above conditions on 77 we obtain the
upper bound as shown in condition
(d) vt that T--1 S 1 < +++1 <
T k. based on one step iteration in 27 of Lemma 6 and inductions
(a), (c), there is
1 /p)
S
<4
2
Tp 7)
U 11.0 BR + +4p2n | 1x0
BB + 4 300 1)
IT'S
BB (43p 4
Be + | (
< 4
1 + yp
7 T
B& + 4p n
I00 (Bs + 4 2 BB (T
2
+ yp
<4
Tp
TT'
11.0
By + 4p
- 1l BB
2
4
((++vD)
7+1)
p&n -
11 Bs
(41)
(1 - c10 (1 (1-v (1-v))}
2
where the second inequality is due 4BpånBB < 4 x --v 256 mag
1-ve B3 < 1 and third inequality
is due to global RIP condition on 8 that is order of 1 and Bn ا44
2
< 1. the last incquality is
23

---

based on induction such that if we have
s Io <4ypån 1T's Bk. then based 455 if 17 S
Choll-vbt
T c10 (1 (1-v)))
(42)
With the same derivation in proving induction (c), the lower bound for is the same as that of B.
Then also unrolling the recursion (27) from beginning of (k: 1)-th induction beginning of k-th induction and combining induction (a) would have
2
2T
T 1-i
S
1+ VP
2
A
T
+
4
Bk
1
vP
U
T
+
1=0
2T
S 4p
Tt u
Bu
7
+
vP
8
(43)
The derivation of above inequality is similar with (37) To guarantee the above two inequality satisfy induction (d), the y and p can have the same value in (38) that 7 3
32
1-VP"
(e) For the upper bound, the proof is divided into three cases.
(u,) ;)² S w + BR, based on the Lemma B.6 in 36 we can conclude that
(1) One of case is
vt 2 TT-1, (ut) 2 would keep below wz + Bx.
(2) Another case is w + BB - 1zj (1f=-1)² S w + 2B, in this case 2 TR-1, Either S
( S w + BR, which can use result in case (1) that V t,
S wj + Bg or that
w3 B& (ut)²
2 wj 2BR, which would guarantee that (n)
(3) The last case is w + 2B < (T/)) I w + 4B,, then based on Lemma B.14 (36), after the
4x2* and we can check that Tg is large enough sufficient number of iterations that 11 2 I0 1
that satisfies this condition, it can keep that T--1 S w + 2
Following the above three cases, guarantee that there exists wj + 4B
T. T
I
1 x 4B,
For the lower bound, we can also have bound ||gs < 3/pBs by comparing formulas between p'
and g", Vt that T' 7--11 S t < Tkk For perturbation f², based on induction (a), fine-grained bound in
(d), vj E S it has
1 < 48p 48p2n//z/BBB 1B
(V80max
li's ①
uts w0ll +
3/PBa
x
E n
16
V
(44)
16
where the first inequality is due to bound for ||g' and the last inequality is the same reason
29
I' can also be reparameterized f ry r'sa where |-| the perturbed optimization recursion non-support S over decentralized network in (1] becomes
yTB for VL that Tk-1 51 <
T 1-1) = (w'.) 2 o (1a 4n (E) E + g + +r())²²
(45)
24

---

Based on the similar lower bound 79 and upper bound in 80
we can conclude that Vt
O 9
log 1 there is
i II
[I(1 (1+ 80 1=0
2 E3 10o + +| + +Il0'l + )lo) S
1 ~
(46)
where this inequality guarantees that the averaged signal on non-support remains || 1l S Vo until early stopping. Vj S. we use ju to denote the largest index that wj S Bj, + a². As Bu Waxxx the existence of jk is guaranteed. Then for t t= 0,... Tj. 1 and based on (30, the would shrinkage from initialization a², to obtain the lower bound, we should consider the maximum shrinkage as follows
2 Tik -1
1N "
II 2=
(1 (1-41) 417 (1x))² + +| + E'sl.o + +1199l + =11r)lla)))
(47)
where the last incquality is due to 46). (
< a = ... ,Tx 1 and step size condition that S 3o and (1 5x) (1 + 8x) 2 1, Vr E [0, 1-
" ((w)) + E | llx
+
| 1l
+ rr
Thus, have (z)) a for Vt= 0,... JT.
For t Tj + 1, ... T in+ +1 1 and Vj E S, let consider the auxiliary iterations that
The (at)² = (a)-1) o I 4n (1a)-1) (w] - B)++ where un
Jk
a²
as above proved. Based on definition of jk. there is wj B 2 a².
Accord-
1
ing to monotonic property in Lemma B.6 in 36 we can guarantee that
E
Tik min 3 w Bi++1 max 1
..,.w w Ba--
H that ensures that
Tu
2
N
2
set1 "
2 3 where the first inequality is due to the squeezing property in Lemma B.9 in 36]
Then we can follow the same analysis to prove that left i-th induction step that = ja + 2, based on the monotonic property of BR.
.. m
A.4 General Case
This section considers the general setting where the ground truth w* includes both positive and negative elements in its support. The analysis here is more complex than in the previous section due to the presence of o and its consensus error terms. The following formulates the recursion of perturbed average variable u' and similar derivation could be applied to v'.
Lemma 7. Consider the sequence {ut, v' i E (mi) generated according to (3) and 44 by DGD for solving problem ( the average signal (u') } on positive support St, negative support S- and non-support Se are updated according the following formulas
g+ = T's+ 2
(1 ( 2ooss))-wss+)) 4n
1. 1 --4
x N
(1T6s)²- 2 + 2 -2((())))²)
XTE
2 )² -²-w's ) -4np's - 4ng'u x -1) ( (nus))) )² -w's - (D's (D's))
+4
4n
N
N
(48)
XT x
z's
1a 4n
- 1-0''s )² -wws + N
(I'So) | - -(v's-) + (य's)) 12 -(D's)) )2)
25

---

x"g N
x x
-1)
1) ( w/s) - -(0's )² w's )) Ampii
+
(NN N
(49)
X
++1 Uge
T'g ①
la
A4-4h
4n
(U'se) 2 -- -(7''s) 2 + (v's )²= -(0's )²)
NN
N
x x
-1)
( 2 W's+ (V's-)² - -w's )) -Ang' Anf
+
(50)
N
where the perturbed error terms Du, Lu yo R I'a f'a induced from decentralized network are defined as
1 m
X
1)
22's
A
hr u,
+
(A
t.
u.s
)²
- -2n's
A
f. 0,S
- (A
u.
1=1
+ 3
A 4,6
+
X X;
2T'se O
u.s:
+ A 5t
2
+2u's
A
u.
+
A 1.
u,
)²
)2
n
20's ②
A 1.
(Ai v,S0)
2
- 22's S+
A
0,tt - AA 22
e,5t) )):
(51)
u,S=
-
1 M
X X;
Lu =
u+
O
(U'+)) 2 - -w's - -(V's-) )² - w's
171
n
i=1
+ 2u's+
C
A Ale
+
A utst) )²
)2
- -27's- @
A
- (44i e,s )
2)
St
U,s
X x;
TTy.
A 4.2
(T's +
A li
0.5c) )
+ T + A
u )² 2 - (T's- + A
Aist)) )
u.s+
n
5
+ A ti
(52)
u
T1
3
x T X;
-) (4 th ) :
2
9/ = u
(53)
m
n
1 m
((xix:-1)(
(X] X; -1) -1) ( 2²_
-'s+ - -w's²+
- ---wp -ww's
S
nn
17
1=1
+ 2u's
C A tui
ut
+
A (biss) )²
u.st)
- -27's @
u,s
-(A!% 1.
-
0.s
)²
2) X.'
n
X x
A t.
- (8's- + A 1i
)²
?
i''s + A u.s )²
2 - (D'ss
A
)9)
U +
u.S=)
v,50)
+
+
u,
n
(54)
34 = gu
t, D,S
)²
2 ;
(55)
m7
i=1
1 m
(27'ss
A
4.
-
(ALi
1,5
)² +
2
X.
1 ( - -(8's )²
w/s
m
S
U,S
e,s
n
w/y
+ 2
A li
+
AAi 1if
)²
2
2T g-
A 1,
- (A 1if (A:is-)) )
u.st
u,
0,s-
x xx
(u'so +
A l.
u.
2
(5'S-
+
A li
0,50)
)²
?
+
T + A liis )² 2 - (1bs-- + A!iss)) ))
n
A Ln ut
2
X.T E:
+
:
(56)
n
26

---

Proof. The average of optimization for u i E [mm] under DGD are as follows
m
++1
Vn Vuli Si (u ,00)))
+ 7 m
u
1
V Vufi W 8²)
Σ
Vuli (u', (u' - Vufi (u', 2(.1)
m
m
i=1
Thi
17
Vuli (u", 00 - Vuli (uti,,
(57)
112.1
Based on error decomposition on positive support St, negative support S and non-support S there has
x x
1) ((u5.)* 2 (T's ( w*
VuF ( (π', = 4t' o
w +
N
x" X
Xte E
( )² - -(T'ss) 2 *((u's )² - )²)
(58)
N
With same decomposition on St, s+ s for Ih and 11 there are
11 = 4 @
2T's- @ Ari D,S- + A )²
+ (
Xx?x, x;
7)
225's- (2055- C n.S- +
(A p.s- )²)
n
x X;
20's ①
Li
+
A )
0,50
+
22's
3 A 4i
0,5
+
(A lii
0.5
)3)
n
11.1 = 4u O
-2u's
ut
(A
)²
2
+
X
1)
2't's 3
Ani
u,st - (A
u.st
n
X X;
(2uuge 4 A A.i
u.Sc - A1s 2
22's- ④ A u.s- - (A
u.St)
uus-)
n
-44 @ (uus²)) - -(D55-² )² 2² + +2u's @ A ut + ( u.st) )²
2
A bi 0,s-
(20's + t 4.ss))
-
X X;
(w's)) )² - (T'S-) )² -0= + 2T's+ 3 A Lu
-(0''s)
+ (A
2 -27's- @ A
+
u.st
u.st
0,5-
n
S.S
+
X X;
(T's)) 2 -(T'S.) 2 + +2T's
1.5
u +
A
1it
u.
2
- 220 3
U.S=
4.
+ (T's
2
(J'S)) 2 + +2u's 0
hi u.s
+
A
1it
)² )²
- 20'
0
M,5
2
X c
f 0,5+
(59)
Substituting Lemma 7
(59) into
57) would obtain the perturbed recursion of averaged T..+, T's T.y. in
The following lemma separately bounds the consensus errors on S+, S-, and S by the corre- sponding magnitudes of parameters, which is different from the current analysis in the decentralized optimization literature.
27

---

Lemma 8. Consider the sequence fu' , i E [m] generated according to 3 and (4 by DGD for solving 2 the consensus error of Au on positive support St, negative support S and non-support S have the following recursions
A A u
Il.
S p p
lo (1+4] ((Vobmax + +1) (1(xt))) 2 w 11 + +l((5--) 2²
w's-
+ 2d ( | Il + +| ) )² + (1T--l1xx + +1 ا ll0e)
)²
+ (1a's-la + -| ll ? + (110s+ 2o + +I ll 2)
X E,
+2 (Vsomax + 1) (1 1l + +1 11) + max
n
+ 4pn | 2o : (Vodmax (211t's 1l || ا |m + +| b.s- 11x²) + COmT
(60)
A411 u.s-
lice s s ا M.s-sll 11 (1 + 4pm ( ((Vodmax +1) (/ [T'ss) )² - w
+ (T's )² - -wis-
60
+2 vis-1las Auss lo + | 1 +2 2| |1
t
1l
+
|| A u,s 11
S.s
+ 4d (1 (1 + +I| ) 2 + (1 Il.0
+ j ||
+ (Iu's م1 + -u l1 + (I 1l
+ || 11 2) ) + max
x E.
+ 4pn ||u's || ((Vohmas + +1) (2llu's mo D 11 + +IIAus
+2 + 1l 2l + +11 l1(e) + Cerr)
(61)
A 1+1
s - Mus ||
(1+ 4n (Vsdmax (1(25)-)
2 - -wst
+ (T's (00s-)2 - w 11
u.S=
+2 at's
|دا0|
A Au,st oo + || | 1| +2 Jo's 1|
A b.s 1l + +| u 11
+ 4d (
Lt'sss ao + + 1loo) + (105s= Il + | lls0) )
(I Il + +I -l,e)) 2 + (IESs 2o
+ +I 1111)) 2) /) + max
x E,
n
+ 4pn |T's Il (Voōmax (211T's 11s0 | 1ooo + A 1/-0
+2 +2||0's- 11 1 1120 + +I I1x) + Camr)
(62)
where the Cee is defined as
Comp== := Vs(ōmax + +6) (1(u's) )2- wš+ |/ + +1(055 )²= p--wwl -w' 1,))
(1luts-la + ||اا sc ) )²
)² + (1155-11a + | 1lx)) 2
+ 2d
+ (1
Ilc +
2
+ (1 Il.0 + + |lm 2)
x Ei
x
T
E
+ max
+
(63)
n
20
28

---

Proof. Based on the updating of DGD, there is
u++l Il- - 1m
T
(U' Vul V9) w/ Im -
1m 1m
(U' V.d
V.F (U')
w
1m T
m
(0' V. (w)'"))
+ Vuf U 1 - -
+ + ( - vuf ( (U. ( w 1m mm (64)
Thus, there is
| u.
S p S u 11x0 + pn max |1s @ (Vufi (u), - vuF (य' ( (
00
S p A A
I.o + pn max
1s @ olo + pn mmxx 1|+ c I2
+ pm max
1sst
C (Vafi (म .') - vuF (w', F" )'')ll
s 0
20 + +4p L 11x0 \vommux
(2110's- |0 || | - Il + / l220)
+ +2d (2 ||
|0 b,s+ || +
t
I + +2| V'' |l
|| + - +s 11
0,5=
e.
+ | s+
11,0 <| u 1l + Jt'S
[o)) + V26maxx
u.S 11
[2|[x's +
|l + +|| 1l00)
+ 2d 22
| |l |1 c |1 +
t
|| + IT's
|1
1
11
+ A u,s
|-2
u.Sc
u,s
+ 4pm
A 1l (1(
(1's
2 -w's 2 U ||
A
u
1
|l
+
||
| u
2
+ V00max
(1( ----/=----- l1.-
+ +|| (v'ss) )²
w
+ 1''s
|1
1
u+
+ A
l(x) + 2d
(11
+ A n ol,o) ) + (1 + A S l1
Io + +| l1se) 2 + (1 س1 + +| )² + max
X
(IT's-
n
+ 4pn
J's 11
(Vidmax (|(T'S) )2- w'sl
+ +|(T5s )²= --w's w's 11
X &:
XT E
+ max
+
(65)
n
where the second inequality due to (64) and the last inequality is substituting into the formula I1,,, I1. in (59) and gradient difference at averaged pair. Merging terms involved | lI and u Il. separately would obtain the result in (60). Performing analogous proof would yield
results on negative support S in 44 and non-support St in (50).
The following proposition deseribes the dynamics of ur oi by conducting inductive hypothesis for both - and of.t, which is different with centralized setting [36]. Because the complicated consensus errors prevent transferring the proof of non-negative case to general case trivially.
Proposition 3. This proposition inherits Proposition for the general case with considering dy- namic of ot for learning negative part signal w'y.. Recall the definitions Tf Tk, Tw, BR, K, B in Proposition 2 the following statements hold in each induction step.
(a)VL that T Tk-1 max
5
<
TB
with w
Vk.
E
[K].
there is
{[((Tts))
(T/5-)2
<
Maa
24
29

---

(b) For vk [K], there is max
[||
Tn-1 wis+
)
(
)²
2
wss
W
24
00
(c) VL that Tk-1- S l < Ta with Ak E [K], there are max, م
|m.0
S 48p211
1u's 1100 Ba
u.st
and max;
e,s
ti
s 48pån 1y V's ol BR.
(d) For any Tk- k
$
k that Ak E [K], there are max;
A u.
S 43p2n
LT's Bx
and max;
f
f 4 1) J ll Bk-
v.Sc
(e) For any T k-1
S t
< Tx that Vk [K], there are max,
A
li u
||
S 43p
IT's
1l Bx
and max;
f,
f 48p 17 Vs't llc Bx-
00
(f) vt that T < < Tx with k E [K], there are refined element-wise bounds for consensus
errors as
t u.jl 4.3p 1) n BB and اريفة S 4.p BR, Vj E S.
(x) For Vj St and & [K]. there is a² V U - 2
S w + 4Bg. For Vj E S and [K],
2
there is a² 1
S w + 4B
(h) vt S O
log 1
max {| loo
J 1l S Va.
(i) 50
1 log _ ạ<
and Vjj E S, there is J S a².
1 log 1 it has max {| Il
J''s | S vā.
Proof. Proof idea: The key difference in the proof between centralized and decentralized settings lies in the fact that we cannot directly transfer the proof from the simpler non-negative w" to the general w² This because the error terms induced (48) (49) (50) by the decentralized network in Lemma 7 prevent obtaining the results in inductions (i), without induction steps as Lemma B.16 in [36,, which allows to apply proof of non-negative case to the general case directly in the centralized case. Therefore, we have to conduct the comprehensive induction process for the general w", which can ensure that the magnitudes i7' on the negative support S and 8' on the positive support S remain small up to the early stopping iteration steps. The inductions (a)-(h) show that the averaged signal F4' on the positive support S and the averaged signal V' on the negative support exhibit dynamics similar to those in non-negative case, as outlined in Proposition 2
Base case: As the initialization 0. = 0.5 = ald, Vi E [m]. Due to the condition on a, the base case is true.
Induction Step: Under the assumption that all above induction hypotheses hold until some
0 < k < K -- we should prove they still should hold at is + 1-th induction.
(a) We should prove that Vt (T Tk 1}, the condition
| (w's+) un ||
w Waa
2
and | [ )² - wss S "m=x still holds. If the condition is true for 1-th iteration, then based on claims (c). (c), (h) and (i) the ||p/lloc in (51) under current induction step could be bounded as
||pill.o 8 8850maa 3p Bod || 1l + || 11xo) + Vsōmax (43p² B&n 1/'63- lle))
2 + 2d 883 + (A8pånBl) )*)
+ (Vssmmux + 3) 43pp2 T'' |l Ba)
(1T6--12s + 1 + || 12-- +
|| 11%)
<32 30 Birwwnax + 38 82 pa Bi W + 32 (3((v5) (Vsdmax + +3) 32 p2p. BL max
30

---

2d 883 + 16,3 (0. p Bt)
(1
2 + 1T's ll:0 +
JT's- 1
J 11
3 (v max + +3) p² Bs dap
(66)
16
32
where the first inequality is due to definition of local RIP condition and Lemma and Lemma
3
second incquality due to hypothesis (a) holds at t-th iteration that ||uss || 2 Io's |
2w max the last inequality is due to definitions of B, Bg, step size condition and hypothesis that J''+ Il.o would keep below va up to early stopping under hypothe-
Ug sis (h) and ())
S's I1 U's ll
The element-win wise bound for d' in (52) under current induction step can be bounded as follows that Vj E St, there is
| & 48 Ba (Vommax (T's.) )² w 1 +
(J's
) w's 11,))
3 50 + 3) Ba Scl || 1-0 +
X E
||
|2
TTs 1 1| 11 + max
16
00
4/8p2 n/uu Ba (pt V50max ((T w
+ (T's))
1e's-ws-- 11m))
w
3 (3v (50mmax + 3) pBk + 32dppi + o² max
X
16
n
p7 BulTd
(67)
32
where the first inequality is based on refined bound in hypothesis (c), result in (66) and inequality || + y112 -/ S 2|||==] ae + 2 | and step size condition that 4 < 1. The second inequality uses hypothesis (h) and (j). The last inequality is because of hypothesis (a), the step size condition, network connectivity condition, small initialization a and definition of Bg.
Then q' could be reparameterized as q r @ T where ||r S
LPBL 32
Vt, TKIT <t<Tk.
Then the perturbed recursion for गे' on positive support S+ over decentralized network in 488 becomes
) TT's ) j'o (1a (1a-4i) 4n (TT's)) )a w's + EE,
E + p¹, rrr.)) ))²
(68)
where the new perturbed error terms ES,; E2, are defined as
x X
E
I -1)
(Iuss )² - wss - -OT's )² -w's
N
X
X
E
( (= (Ts ) *+ (Tts )² (T's (T'S.)2)
(69)
N
Then the total error terms in (68) can be bounded as follows
E2
+
E
+ 1p +
+1|r 11:0 I
(i)
2505
Wmax 2
+ 8da +
X
N
3 (v (v55 55mmxx
max
p BB
dap
p² B²BB
+
16
32
32
(
w
X T
Bk
C
max
+ Cp
max
E
C.
N
2
(6)
w
BB
C2
max
+ Cis +
2
2
(in)
Wmax
(C,, + 20t)
+
2
31

---

(v)
1
W Wmax
Bb 2
+
2 40
2
(wi)
(70) where (1) is because of Lemma 2 and Lemma 3 under the global RIP condition and induction hypothesis (a) and substituting the results in (66) and (6)) (ti) is due condition global RIP parameter that 6 I
Bk:
C2
condition a S (3d+1y2 and network connectivity condition
2/5 logl "iaxx 1-1)
(iti) is due to definition of Ç and (iv) is based on definition of K that
36( (8800mmm))))
I Wiax 5 2
(v) is because definition of B₁ and Ci, C. are determined later that are small 2 2
enough that C. 2Cb 80
Based on iteration (68) and perturbation bound in 70 would prove the (T's ++1
w's
"ii should be also true based on the proof of hypothesis (a) in Proposition 2 by replacing S with S+. We can obtain similar results for v's Combined two cases and induction on we have conclusion that Vt > 1- there
max (uus+) w lioe (05-)) w
11m]
u max
(71)
2
Thus, we finish the proof of induction (a).
(b) Comparing the (68) 70 with (30). the proof of this hypothesis can follow the proof of hypothesis
(b) in Proposition
(c) rI that T -- S St<tt1 < k. based on one step iteration in (60) and induction (a), there is
(6)
p Auss 1l (1 4rl (2 (1 (Vodmax + 1) wmax + Sd
||
I|
+
I
u.
x &:
+ I 1l + II l + 8 (Viōmux + +1) || | 11 + max
n
+ +pp 1us lloo (4V50max 17 To 1l B+ (2
s- 1l
+ +48pan
||
11 Bb
+ 44 480max
"max
+ 8d
+ | 11 + l|u's
11 + a )
2
X &;
xT g
+ max
+
12
N
(10
S pa
|| uust Imx
(1 + 4n
(18p) whax (V3dmax + 1) + 32 da
+ 4p L''ss 1la (16 (16v50maxxpn) 11 11 BB
+p*
max
"
XT
+4p+
1/4 / /80max
Wmaxx
32pt + 2p max 2k
i
n
(61)
3
8 | u
144 11 11.0 11+80 (maxx + 4p |
(16 lopnnlllss-- 11 Br + z B
1
(iv)
1 + vp
4
3p 17 | 11 B₁ + 4pån
||' 11 Br
2
(w)
(1=+ 1P)
(1 010 (1 - -
2
B+1
1 p/v 1)
++1
00
Bk.
(72)
32

---

where (t) is due to the claim (a) and step size condition that 4.pp B₁ (it) is due to BBs 1, condition that all L
I
1 and
5 I 6max.
are not x X n
larger than va before early stopping in hypothesis (h), (i) and
x
N
max;
c.
oc
x
The (iit) is because pà I min Vidmax +1 86max" max
x
a
(12d+1)a
and
{|>
x N 00 .e) I "maxx The (iv) is because in the current induction step hypothesis
max
(c) holds in 1-th iteration and step size condition that satisfies 1
I-v/ such that 160p ToppTiinn
pà (pa + (upaxc S (1-(11 pà ))
y and 16 /6 3pm || IT's 11 - Bk
where l/11s 1l S 2wimax is according claim (a). The last inequality (v) is based the (68)
w's+ I| + BB) S 1 based on hypothesis (a). Comparing the formula of 72 with (34). we can follow the poof of hypothesis (c) in Proposition 2 to finish the proof.
and step size condition 1/ <
(1-(D)))) such that 41y
(w's )²
Winxx
(d) The proof is similar to that of hypothesis (c). Vt that St-sst<t+1s TR. according to one step iteration in (49) and hypothesis (a), we have
S A su 2o (1 + 4n (Vrdmax
(2
+ +4,p2t7 1/mra/115 111'st 11.0 B& (2 I 1loo
u.
+48pa1 Iu's+
1.0 BR)
+ + Jo's 11,00 Bu (21 11x0 + || 1la0 Bu)
X²'E, &
)) + 4pm llus= 10.0 (Vodmax (48p21) l'uss
+64do + max
10 BR
n
(22llus+ 1m
+ + ju's 1lo Bx) + 48pån j 10 BB (2 11/0 lma
x c:
+448pä
||
1l Ba)) + 4 4V50mas
Wmax 2*
+ 32dd + -max
a || A 2راا
(1+ 4n (pt v50max
(2w + 1663pt nB (1 l| + | ))
4 c
p²
XTE.
)
+ 4pån 1
Ilx (16v/50max (1 ||= + +1 11
n
4p 2op//ommm V8ōmax
Winax 24
5
+ 2pd
XP'e,
4
N
+ vP
Bp 17
T 11.00
Bs + +4= IT'S ~0 Bu
4
1 vp
8 ++1 1
pa n
al
B2:
(73)
(1 cu0 (1 - vD))²
where the first two inequalities have the same reasons in
72 The third inequality is due to due to upper bound of
16,3p i BB (1 1|== + 1o's 12 - witns and p² /
Jss 8
<
640
global RIP condition in Proposition with C,2 S I. The last inequality due to (79). Then we can use analogized proof for hypothesis (c) to finish the proof.
33

---

(e) The proof is similar to hypothesis (d), VA that T-- st<t++ I Tki based on one step iteration
in (50) and hypothesis (a), there
++1 u.S
Il.o S Plll un
pnss 11 (1 (1+ 4pm ((V50max + 1) (we + 4Bp22n I 1loc Bx (2 [2| 1oo
+43pån 1/ |ugs+1 11.0 Bs) + 4.ppn l BR (211o'- + 43pp2 || Bi) ))
)) + 4pm l 11m0 ((Voomux +1) (48p22 | 11 B
+ 64da + max
(221 11 +48p2n IT's 11 BB)) 48p2n |0s 1l.0 Bx (2 IT's
10
x E.
+48p2n 2 1) |s 1 Ba)) + +2v5 (0 + mmax)
"'max
+ 32ddd + 2 max 2
n
4
+ vP (1++²²)
B
1+1)
p²
Bk
(74)
(1- c10 (1
vp))²
where the last inequality and the left proof have analogized derivations in proof of hypothesis (d).
(f) To absorb the perturbed error qhe in 488 we need to prove the fine fine-grained bound for consensus error in hypotheses (c), (d), (d). The idea is that we focus on the vjj E S then the upper bound on the consensus eπrоr on j-th entry is
++1 u.j S الممم
(1 + 4n (Vsdmus
(1 (T's--²
2
w
+
T )² w's
2
100
+2| J''s |ox || م Ausst |lee
+ A st || +2 1 |l ||
S.S 1l + +1 - l1²e)
X
+[(n/)2 - wz1 2(x))2 +3/x²]
A n.
+ ا|ااام
+ 24da + max
n
+ 4pplutl- (Vodmax 22| |1,0
A Austt oc + + t
uu 1|s +2 Jt's |l || A 11.0
+ | li=)
+ V (6max + 5) (1) (TTs+) )²
2_ -w's+
+ +||- (T'S )² w's (1
X:'S &:
x== g
+ +40da + max
+
n
N
4
1 + vP)
5 (1- (1- )
B + 3+11 1
p² B) Iu, +1
(75)
2
where the last inequality is due to substituting the crude bound and analogous derivation in Following the proof of crude bound would finish the proof. The proof for Vjj E S and Vj E S can combine this proof with proofs of hypotheses (e) and (d), respectively. The fine-grained bound for of can be proved by using analogous proofs for ut.
(2)
(g) The proof can follow the proof of hypothesis (e) in Proposition 2 by replacing the S with St. The proof of d'g- is analogous to u's..
(h) 1I that TA- S <i<(+1< < Tr. First, we bound the perturbation error |ا || in (50 induced from decentralized network
| < ||pilloo + +3/50max (18p:n|Ta's 11 Ba 2 + 1966 96 w B
)²
3 ( (vSômax + pa Br +
dap²
16
32
34

---

pa Br (150 (Vs0mas +3) + 3vp)
dap
(76)
800
32
where the second inequality is substituting the upper bound hypothesis (a). Vj E S there is
66 and
11 S 2w
due to
lffاl - @8p2n/uuBBB
(vodmax
(80B, + 163panBB
(1 1|
1 112))
X &
+ 32da max
VpBKIT
(77)
32
where the first inequality is due to hypotheses (a), (c)-(f,, (h), (g) and step size condition. The second inequality is due to the definition of BE, the condition on p. and small initialization for a.
Then fú, could be reparameterized as f', r',, u's where |r>
vPBa 32
vt that T S
t < T.. Then the perturbed recursion for u' on non-support S over decentralized network in (50)
becomes
(us- 1
(u's)) ) (1a 4n (E2, + E gi. + +))))²
(78)
Thus, we can conduct similar calculation (70) and obtain the upper bound
|| | +
E
lo + | < Br. Based on the step size condition that S cxa(1-vP WD) therefore there is
manx
similar result in 355 as
00 2
TT's b0 (1 - cro (1 vD)
(79)
S"
Based on the recursion in
78
Vk-th induction stage, we have the following upper bound
Tw-1
II
(1 (1+81) 81/ (1E228
+
E
+ -111 -11r%_1lo))
1=0
( T=-1
(1 + 8n 40bc)2
(1+81
C ( (T&))) )² -w's
+ ( -w'i-ll ()0-)~-''--l11 w
K
t=
(1 1 8n
påBx (150 (V58max
3) v/)
dap 3
2
2
1 8m ||- ml
+
800
32
(10)
S (1+ 32m) 4Th
1+ 4n
4(k+1)7T
T T--1
+ 8m
pa (v 1/8mmax + 4)
w Wmax
2
K 2
200
2
x E,
(1 8mp? So Bs)
1 11-88pp.. p
32da + max
(10)
2C,, 2C, w
12(k++)JT
5 (1 C2 87
1 1144
K 2
(10)
20 W
12KTK-1
(1 + 32T STK-1
1 4n
K x 2K-I
8CAC
8KTK-1
2C,, w
12KTK-1
+ 4n
1 + 4m
K
K x 2K-1
(v4)
w mmax
201Tx-1
1 4n
K 2K
(80)
35

---

where (i) is due to væ1, 22. 2n 2 O, there is 1+ Σx= Th S I[= (1) substituting the upper bound in (76) and definition of global RIP parameter. For (ii), we use Tx 21k
based on definition of Ta, Tk, induction (a) with Lemma B.13 in [36]. step size condition,
small initialization for a, definition of By and refined upper bound for r %
as |f S
p² (Vr Bk + 32da + max;
X
L 1lo (iit) is because network connectivity con-
dition that p S min
{
v8g
|xTE|
(iv); (v) are due to condition 1 K
Vodmas
8m max, X
and inequality 1 1 E S II
(1+ x:)) that x1 = 2K 32nC,C (vi) is based on the Wmax and condition that 40B 1 Cyy The last inequality results from the 2
definition of K that Ç S
Lemma A.2 in (36) with upper bound is set as B
2C, and initialization zo a², then for K x2x2==
t <
Kx2K-1
log 1. there is
64xyC. N0 max
1 4n
2C, max
5
(81)
K x 2K-1
Thus, we select universal constant C2 S 1280 such that Kx2"-1 log a+ 2 20K x TK-1, which would lead to the last inequality.
61n
(i) Concentrate on the iteration by DGD algorithm on support S, based on (57). we have the recursive formula as
u =u's
++1 2
la - 4n ((1ris)² (v's)= w0') E' + E Ei2))
4n
t. u
@ E
(82)
1=1
where the E',,, Enyy Edts and Elit are defined as
x x
-1) 1) ((u²)) -w'ss) w²
Ed1 =
N
X X
X
E
(m'g))²-(C )2)
N
N
Ed
X x;
(T's)
uu')
1.5
2
+
(0'))
1.3
2
(T's)
+
(T's))
2
u
tu
2
(T'S.) ) ))
;
x Xi
uu'') 1.0) 2
(0/8)
d4
uu
w
n
x X;
2
1. 2)
x
u
g
(83)
n
n
For the negative part 8e with similar decomposition in 57 there is
T = v
of
5²) +
Vafi
प7' (-)'")))))) - V.fi (w(itt
Σ (Vofi .') Vefi (
ol:1))
(84)
After tedious calculation, its formula is as follows
J5 = S's 3 (1 + 4n (( ((w')) - (8's) w²) + E E + E
36

---

4v
t. S,
E
(85)
Based on induction (c) and (d), we can reparameterize A (i u.s and A c.
e. u. =r'is @ U's and
Aui
A f,
s S.5 v'g. where max r
r
1 48på (.8pánBB By for Th-1 S Tw. Thus,
the 82 and (85) can be reformulated as
Σ m
EL.
2
U )
1)
1a - 41/ ((TU's²-(V'') 2 = s o
- -(o's) - "" + Exa + E + Eits)
47
Zi=
u.S
d4
m
(86)
EL.
11')1)2 )²
(T's 2
1a 4n ((Tts)² (T's) w') + E'd + Erzz + E'as)
4n
D.S
m
(87)
Based on hypotheses (a). (f)-(f), (j) and step size condition, we have the following bound for additional perturbed error terms
max {1riis 2 E
Elii
S 443p2nBs (1 (Iluss 12- + 1| llco)
D.
X E.
+2 (winxx + | + +| + 16da + max
n
x E.
< BB pa (16+10v0mmat mmax) wmax + 16da + på max
S 403
w max 40 x 24
pt + v000ma))
Cy Wmax
(88)
K x 26
where the last
inequality is due network
connectivity condition
that p
min
J58 VSdmax
xx X
8m max,
Then multiplying (86) and
87
we can obtain that
T
3 0s 1)
11 (4n
(TT'))
(T's)
w +Enn + E' EEas))
+ 8n max
Ezidl
1 Eli
+ 4n mmymax {
I
3 Emill
|| bis E
Exill0011 2)
1))
7 2 23')2 2 ②
C.
1 4n)
K 2
C 22
8KTx-1
1 + 4n
+1 +1 w
K
(89)
where the (i) due to 88 and 41j
(T's) 2
(T'))
- + E + E + E's oc
S
The (ii)
due to induction (a) and Lemma B.13 in (66. The reason for (iii) is the same as the that of last inequality in 80 because of the setting of step size.
37

---

(i) Recall the recursive formula of F'g- in 44 and compare the definition of the perturbation y with perturbations Pi., Iú we can obtain Il perturbation z with outer perturbations S Lu we can obtain || 00 similar reparameterization as z'= =r',. @ W''- the (49) would become
150p* Ba (v +-4
pā
+
Compare the outer
32
vPBk
Il ll
S
With
16
T = ( )² 3 1a 4n (-w3- - (7's- )² + E2 + E + va + rri..) ))
(90)
Vj E S and 1I S 0 + log =
Let 0 S T / be the largest T such that (T7)² > -wj. . If there
no such T exists or r t. then
1 1 ) (1
4n 21 + +| +
+ =loo)
a.
(91)
where the last inequality is due the similar bound in (80) If T < t, then unrolling 90
to r-th iteration would have
(w))
II 1 4n7 (-wj - (ut)² Fig + Figns + Voa + rend))
a
417 (-w3 - (ग 2 + Esg.. + 13 + WWa + rrann))) )
4
II (=7+1
(1 (1-41) 4n (-w² - (τ)) Egs. Esn + v + r
(12)
t-1
(1+ + 4n (1 loc + E + /1 + ||r 11xo))
a
1
(181
O2
(92)
where (i) is based on condition for initialization that a < Miin and induction (h) that 2 (ii) is based on the induction (a), step size condition that
4z
s
8
E + Eās.j + yh, + +) < 4 and Vi > T that (T)) < w
(1-4n) 4n
which is based on definition of r. The last inequality has the same reason as (91).
A.5 Proof of Main Results
A.5.1 Proof of Theorem
Based on the proof of hypothesis (a) in Proposition would be max
3 we can conclude that A4 2 T Tk, there
{|[(
u Tu
w
13
T
Wmax 2K
S Ç, where the last
inequality is due to the definition of K. The total computational complexity is the value of Tk-1= 2
log
1 = o 7 log log
Tyun mas
4
a
Due to the definition of ( in the Theorem 1 if 2 whesxy then our result holds at t= 0 based on the small initialization condition. When Ç S "maxx we consider the two cases where the first case the magnitudes of parameters is strong enough that
T _ 960c, where the value 960 is due to un- I2 we can use run DGD T/ it-
der the condition 20, + C..y : 40, < C., set Co
C2
erations obtain the estimator max {|(
T
w
W
Wiin then based Proposition 2 in 36.. can also run DGD with another 32nw2ii
45
log Whin iter-
ations to obtain the dimension-indeeeendeee bound I w/l max { (5o maxies B, B,, Vj
38

---

where the Bj =
x N
1
Illo
The total iterations are TK-1 32yjrri
log
Mi
log 1 =
log a nc
1
where the first inequality is due to the condition of a.
min
The second case is ( 960g the result in Theorem
w min' then running of DGD with
iterations would obtain
A.5.2 Proof of Corollary
Because the entries of global design matrix generated from i..d. 1-Sub-Gaussian distribution, we have the upper bound of global RIP parameter as ō S va probability at least 1 ~æ which is based on the Lemmal and sample size lower bound in Corollary matches the condition of sample
complexity in Lemma I For the local design matrix {X v/////.. j=1 local sample size satisfies n
(s In ed + In(dn)). we can bound the local RIP parameter as 6max S V mI with
probability as least - I based on the union bound and Lemma
Based on condition in O the
S ग. holds with probability at least 1 40 Based on the Lemma 4 we have the upper bound
x
logd
for the noise level as
S
V
with probability at least 52 Thus, with probability
N
at least 3 we have 1
w
2
SEa
(2d+1)² S
dea
where the last inequality we so² log
8d3
N
select = 40 (20)(2))
in Theorem
N
A.5.3 Proof of Proposition
Because each agent has same initialization 0, = 00, gradient descent from (3) and (4), there are
ald. Vi [m]. after one step of local
X T X:
X &
1. a
1 + 4n
w" +
I
w* +
x X
w² + X E.
2
An
w +
I
(93)
Because the perturbed error bound
X X
x &
log d
u=*
+
S Φ := v Vodmaxx
Wmaxx o
(94)
holds with probability at least 1
s ad
based
Lemma and Lemma 4
denote D¹
x 1 w" X
1
Consider 1/ for Vp St Aq E S there is W | o b 0 based the condition in Proposition In addition, Vj S- there is - 1103] + |uyl based the the condition
Proposition Thus, the growth elements on positive support S would be larger than these of S ST,S" and the Trun; operator would identify the S The analogous analysis could also applied to " that the Trun, operator would identify the S Because each agent can identify the S and S and based on results in Proposition 3 the Trung would also obtain the optimal statistical error with
probability least 1
B
Appendix.B
B.1
Kernel to rich regime transition
Previous works show transition from the kernel regime to rich regime by varying the initialization
scale in the gradient descent method (38). Experimental results in Fig. 7 show that the transition phenomenon also appears in DGD. We can observe that when we increase the initialization scale a
gradually, DGD would converge to the minimal lg norm solution wi,- On the contrary, when
39

---

decrease the a, the DGD would converge to the minimal & norm solution (sparse solution) w Thus, Fig. demonstrates the existence phase transition from kernel to rich regime for DGD when decreasing initialization a. Since we focus on sparse recovery, the small initialization would achieve this aim with better generalization performance.
Norms of solution
||0, 10g li
10ng
Excess & norm
Excess & norm
20
Initialization Scale
Figure 7: We plot >0 A0
|| in the blue and 2. /b 11,
in red vs.a, where w 12
denote the convergent solution by DGD in i-th agent. The setting d 2000, k N 20, 20, p = 0.2133 and magnitude of sparse signal is 10.
B.2 More implicit regularizations of DSGD
To verify the widespread existence of implicit regularization in decentralized optimization, we add two extra experiments on general overparameterized neural network architecture trained by DSGD, which are motivated from [38].
(1) The first one that we use vanilla decentralized SGD(DSGD) to train a depth-2, 5000 hidden ReLU network with the cross-entropy loss on the MNIST dataset until each agent model reaches almost 100% training accuracy. The number of agents 10 and network connectivity is p = 0.178. 60000 total training samples and 10000 test samples uniformly allocated to agents. To evaluate the implicit regularization of SGD under varying initialization scales, the network weights are initialized
as oww, We ~ (O, V 2 ). which suggested by 14 and Pin denotes the number of units in the ni
last year. Each agent uses the same batch size 256 to train in DSGD. The step sizes were optimally tuned for each a individually to achieve the best validation error. We plot the average test error (which is defined as the summation of the test error of each agent's model, then divided by the number of agents) vs. a in Fig. a). The figure shows a visible phase transition for generalization (ss 98% for 6, and = 96.6% error for 2 100). Fig. g a) shows that the transition from the kernel regime to the rich regime by varying the initialization scale may also exist complex fully connected neural networks.
(2) The second one that we use vanilla DSGD with batch size 128 train the VGGI 1-lke deep convectional neural network on CIFAR10 with small step size 10-1 for 2000 epochs such that each local model achieves almost 100% training accuracy. The network setting is the same as first experiment. The VGG 1 l-like architecture is the same as [38). Weights were initialized using Uniform He initialization multiplied by a. The Fig. 8(b plots the average test accuracy vs. a. In addition, we adopt the sparse feature learning measure 4 to monitor the sparsity of learned features in all agents along the epoch in Fig. C(... From Fig. ((c) and Fig. d), we can observe that the implicit regularization of DGD under small initialization may promote neural networks to learn sparse features that can have better generalization performance, which can be regarded as the complementary observation in 4 under decentralized learning setting. How to prove this kind of implicit regularization of DSGD theoretically will be an interesting future work.
40

---

MRU51 lest PuLoAAy Sucke
(a) MNIST test accuracy VS
(b) CIFARIO test accuracy VS
Worth ViT offireett Sallie
220
2008
(c) Feature sparsity VS a
(d) Training curves for CIFARIO
Figure 8: (a) DSGD trained ReLU network MNIST. (b), (c), (d) DSGD trained VGGI network on CIFAR10.
41

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
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 perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much
the results can be expected generalize other settings.
fine to include aspirational goals as motivation as long as clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not diseussed in the paper.
The authors are encouraged create 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 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 low lighting. Or 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 the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should 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.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification:
Guidelines:
42

---

The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross-
referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented
by formal proofs provided in appendix or supplemental material. Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided not.
If the contribution a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, if the contribution is specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
Depending on the contribution, reproducibility
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully. model (e.g., large language model), then there should
(c) If the contribution is either be a way to access this model for reproducing the results or a way to reproduce the model (c.g., with an open-source dataset or instructions for how construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. In the case closed-source models, may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
43

---

Please see the NeurIPS code and data submission guidelines (https://nips.co for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is 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 run to reproduce the results. See the NeurIPS code and data submission guidelines (https
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, The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only 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 ver- sions (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.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
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 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.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification:
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, 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 96% CI. if hypothesis Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures tables in the text.
44

---

8. Experiments Compute Resourees
Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification:
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).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS 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 special consideration
due to laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
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, out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it not needed point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
legitimate to point
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology 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, mecha- nisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
45

---

11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines restrictions access the model 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 best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
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 used and, if possible, include URL.
The name the license (e.g.. CC-BY 4.0) should be included for each asset.
For scraped data from 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, passssspppssss thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license a dataset.
For existing datasets that are re- 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 encouraged to reach out to the asset's creators.
13. 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 detaset/code/model as part of their sub- missions 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.
submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
46

---

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.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer:[NA]
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 the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and 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 the institution conducting the review.
47


Reviews:
[{"review_id": "2tdmAKU3vh", "reviewer": "Reviewer_BLgr", "summary": "The paper shows that the implicit regularization enjoyed by a well-known reparameterizion of least squares extends to the decentralized setting.  Convergence guarantees are provided, and it is also shown that communication can be limited by thresholding vectors before they are communicated to neighbors.", "questions": "none", "limitations": "none", "rating": 5, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "The convergence guarantess end up having the form that one would hope.", "weaknesses": "I don't quite understand how this paper is contributing to our understanding of machine learning.  That running gradient descent on the nonlinear least-squares problem in (2) gives you sparse solutions that are statistically near-oprimal is interesting, but is of course known and written about a lot already.  That you can make gradient descent for non-convex problems decentralized using consesus averaging has also been written about a lot already.  That communications can be reduced using truncation when we are solving sparse regression problems is also an idea that has received plenty of attention.  This paper puts all of these things together, but we don't seem to learn anything new about implicit regularization or decentralized optimization.  The algorithm is not compared against existing decentralized sparse solvers.  If it happened to perform better even on stylized examples, that would at least be something new.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank Reviewer E5yh  for your valuable comments. We appreciate the opportunity to clarify the contributions and address the concerns in your review. \n\n$\\textbf{(1) Contribution and significance}$ \\\nWhile implicit bias has been studied for centralized gradient methods for various models, the decentralized setting is relatively less with several key questions largely under-explored: $\\textbf{1)}:$ Will decentralized algorithms also experience implicit bias as in the centralized setting? $\\textbf{2)}:$ How will the initialization and the interaction of the agents through the network affect the implicit regularization? $\\textbf{3)}:$ How to choose the algorithm and set hyper-parameters to obtain solutions with small errors? \\\nEven under the overparameterized sparse model, answering these questions is non-trivial due to the additional error terms induced by the decentralized network, which can hinder DGD from inducing sparse regularization. For example, DGD in poorly connected large-scale networks may not induce optimal regularization, as validated in Figure. 3(a) of the paper.\n\nOur main contributions are as follows:\\\n$\\textbf{Statistical and computational guarantee of DGD}.$ We provided sufficient conditions—namely, if the global design matrix satisfies the RIP condition, the initialization is sufficiently small, and the network is sufficiently connected—the early-stopped DGD can implicitly obtain statistically optimal solutions. These results, formally stated in Theorem 1, provide a potential answer to the general questions listed above.\\\n$\\textbf{New communication-efficient algorithm by truncation.}$ The analysis of DGD shows that the magnitude of the elements on the support will progressively increase while those off support remain small as initialization, which motivates the development of the T-DGD algorithm that keeps the top $s$ largest elements and truncates others. Proposition 1 shows in the high SNR regime, T-DGD enjoys the same iteration complexity as DGD, but the communication cost is significantly reduced from $\\mathcal O(d)$ to $\\mathcal O(s)$. There is currently no work to prove that the truncated explicitly decentralized LASSO can achieve the $\\mathcal O(s)$ communication complexity. Our experiments in Figure 2.(a) of $\\textbf{supply.pdf}$ show that truncated explicitly decentralized LASSO solvers do not work. This indicates that the implicit regularization induced by DGD in solving the overparameterized model can be better than existing explicitly decentralized LASSO solvers. This expands the new understanding of the benefits of optimization-induced implicit regularizations in overparameterized learning models. \n\n$\\textbf{(2)Simple combination of existing results will not work.}$ \\\nWe fully agree that the implicit bias of GD on problem (2) has been analyzed in centralized setting. However, existing understandings of DGD indicate that it cannot converge to exact minimizers or stationary points if the problem is nonconvex [1]. As problem (2) is nonconvex, none of these results could easily predict that DGD will compute statistically optimal solutions.\\\nT-DGD reduces the transmitted elements from $d$ to $s$ without affecting the iteration complexity, which is achieved by carefully exploiting the problem's sparsity structure induced by implicit regularization of DGD, which is new to our knowledge. \\\n$\\textbf{(3) Insights of broader interest.}$\\\n$\\textbf{ Algorithm selection}.$ In decentralized optimization literature, methods with gradient correction are often preferred due to  heterogeneity of local loss functions. However, our results suggest that for certain machine learning models, the simpler DGD  suffices to achieve satisfactory or even optimal outcomes.\\\n$\\textbf{ Generalization to more complex machine learning models}.$ The study potentially initiates further investigations into the implicit regularization induced by decentralized methods for more complex models. Our fine-grained analysis of the interaction between the optimization dynamics and network effect can be developed and generalized to explore the implicit regularization of other decentralized methods in more complex learning models, such as DNN.\\\n$\\textbf{(4)Comparison with decentralized sparse solvers.}$ \\\n$\\textbf{Vanilla Comparison.}$  \\\nWe have compared with existing decentralized sparse solvers, namely: CTA-DGD (LASSO) [2], ATC-DGD (LASSO)[3], and DGT (NetLASSO) [4]. These methods are all based on the LASSO formulation with explicit regularization. The results are presented in Figure 1 of $\\textbf{supply.pdf}$. For each method, we tuned the step size to achieve the best performance. Our proposed method demonstrated the best recovery performance in all network settings with minimum iterations.\\\n$\\textbf{ Truncated version comparison.}$ \\\nWe further compared T-DGD with truncated versions of existing methods: Trun-CTA-DGD (LASSO), Trun-ATC-DGD (LASSO), and Trun-DGT (NetLASSO) which use the same Top-$s$ truncation operator. Figure 2.(a) of $\\textbf{supply.pdf}$ shows our method is the only one to achieve successful recovery, while all other  methods failed. This demonstrates that naively combining sparsification with decentralized algorithms is not granted to converge. This is precisely one of the motivations of this work: to provide communication-efficient algorithms with both provably statistical and computational guarantees. \\\n[1] Yuan, K., Ling, Q., & Yin, W. (2016). On the convergence of decentralized gradient descent. SIAM Journal on Optimization, 26(3), 1835-1854.\n[2] Ji, Yao, et al. \"Distributed sparse regression via penalization.\" Journal of Machine Learning Research 24.272 (2023): 1-62.\\\n[3] Ji, Yao, et al. \"Distributed (ATC) gradient descent for high dimension sparse regression.\" IEEE Transactions on Information Theory 69.8 (2023): 5253-5276.\\\n[4] Sun, Ying, et al. \"High-dimensional inference over networks: Linear convergence and statistical guarantees.\" arXiv preprint arXiv:2201.08507 (2022).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Blfq4Cpd68", "reviewer": "Reviewer_E5yh", "summary": "This paper focuses on deriving the implicit regularization effects of decentralized gradient descent (DGD) for minimizing an objective function over undirected mesh networks. In particular, this paper establishes the fact that the solution returned by DGD with early stopping is statistically optimal under certain conditions. In addition, this paper also proposes a new method, the T-DGD, that can have better performance than vanilla DGD.", "questions": "1.\tCould you demonstrate your theoretical conclusions in more general architectures to further elaborate the implications of the theoretical claims?\n2.\tPrevious works shows a transition from kernel regime to rich regime by varying the initialization scale, does such phenomenon exist in the DGD setting?", "limitations": "1.\tThe motivation and implications of the theoretical claims are not clear.\n2.\tNumerical experiments are only conducted in simple architectures.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1.\tThe studying of the DGD setting is novel, as most works in the direction of implicit regularization of algorithms typically do not pay attention to DGD. The main contributions are clearly reflected in Theorem 1, showing the statistical guarantee and computational complexity of DGD. \n2.\tThe proposed TDGD can be seen as an interesting application of the theoretical observation, which additionally makes the theoretical claims inspiring.", "weaknesses": "1.\tThe simulations are only for diagonal linear networks, which limits the generalizability of the proposed methods and theoretical conclusions. \n2.\tThough results for the setting of this paper are novel, the motivation for studying such a setting is unclear. It would be better to specify clearly why and how the setting could be useful in practice. Currently it is hard for to see how the theoretical results could be important.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed and insightful comments. We appreciate the opportunity to address your concerns.\\\n$\\textbf{Experimental results for general architectures}.$\\\nWe add two experiments to validate the implicit regularization of DGD on general overparameterized neural network architecture, the details of two experiments is  in the caption of Figure 3 of $\\textbf{supply.pdf}$.\\\n(1) The first  is that we use vanilla decentralized SGD(DSGD) to train a depth-2, 5000 hidden ReLU network with the cross-entropy loss on the MNIST dataset. We plot the average test error (which is defined as the summation of the test error of each agent's model, then divided by the number of agents) vs. $\\alpha$ in Figure 3.(a), which shows a visible phase transition for generalization ($\\approx 98\\%$ for $\\alpha\\leq 6$, and $\\approx 96.6\\%$ error for $\\alpha \\geq 100$). Figure 3.(a) shows that the transition from the kernel regime to the rich regime by varying the initialization scale may also exist in complex fully connected neural networks.\\\n(2) The second is we use vanilla DSGD to train the VGG11-like deep convectional neural network on CIFAR10. The Figure 3.(b) plots the average test accuracy vs. $\\alpha$.  In addition, we adopt the sparse feature learning measure [1] to monitor the sparsity of learned features in all agents along the epoch in Figure 3.(c). From two figures, we can observe that the implicit regularization of DGD under small initialization prefers choosing solutions with better generalization performance and makes DSGD implicitly learn the models that can induce sparser features.\\\n$\\textbf{Motivation of the study.}$\\\nThe purpose of this work is twofold. \\\n$\\textbf {1).}$  The sparse recovery problem (1) itself has important applications in sensing, signal processing, and learning where data is limited and distributed into different locations [2]. Our algorithm provides decentralized solutions to these problems and outperforms state-of-the-art methods, as shown by Figure 1 and Figure 2.(a) in $\\textbf{supply.pdf}$. Furthermore, Problem (2) does not require choosing the regularization parameter before executing the algorithm. Rather, sparsity regularization is controlled through early termination. In practice, it is much easier to implement since one can stop the algorithm by monitoring the test error on the validation dataset.\\\n$\\textbf {2).}$ The over-parameterized formulation (2) can also be regarded as training a two-layer diagonal linear neural network and thus connects to the literature of deep learning theory. Existing works in this area primarily focus on studying the implicit bias of gradient methods in the centralized setting, with the decentralized regime less explored. When the data is split over multiple agents, a new component, the interaction of the agents through the network, comes into play and will affect the algorithms' trajectory. For a gradient algorithm that is biased toward benign solutions in the centralized setting, it is not clear if the new perturbation introduced by the network will drive it towards somewhere else. This work provides an understanding of the problem and shows how initialization, step size, and network connectivity should be coordinated to retain a small error. \\\n$\\textbf{Formal study of more general NN architecture.}$ Analyzing the implicit regularization for NNs, especially in the rich regime, relies heavily on the specific problem structures. As such, existing works, even in the centralized setting, are largely case-by-case studies.  The analysis in this paper for DGD could be potentially generalized to other cases, but providing formal studies is beyond the scope of the current work. We also mention there are some recent efforts trying to provide a unified perspective on the inductive bias of gradient descent [3,4]. These results characterize where the algorithm converges to, but not how fast it reaches such a solution. The technique along this line is less close to that developed in this paper. Yet it would be interesting to investigate the decentralized/FL counterpart of it. The results of Figure 3 of $\\textbf{supply.pdf}$ on fully connected and deep CNN can demonstrate that our current theorem 1  (DGD with smaller initialization implicitly chooses the sparser and better generalization solutions in solving overparameterized models) is not limited to the diagonal linear network, but might be valid for general architecture.\\\n$\\textbf{Kernel to rich regime transition.}$\\\nPrevious works show a transition from the kernel regime to the rich regime by varying the initialization scale; this also happens for DGD. Experimental results showing the phenomenon are shown in Figure 2.(b) of  $\\textbf{supply.pdf}$. We  observe that when we increase the initialization scale $\\alpha$ gradually, DGD would converge to the minimal $\\ell_2$ norm solution $\\boldsymbol w^\\star_{\\ell_2}$. On the contrary, when we decrease the $\\alpha$, the DGD would converge to the minimal ${\\ell_1}$ norm solution (sparse solution) $\\boldsymbol w^\\star_{\\ell_1}$. Thus, Figure 2.(b) demonstrates the existence of phase transition from kernel to rich regime for DGD when decreasing initialization $\\alpha$. Since we focus on sparse recovery, small initialization would achieve this aim with better generalization.\\\n[1] Andriushchenko, Maksym, et al. \"Sgd with large step sizes learns sparse features.\" International Conference on Machine Learning. PMLR, 202.\\\n[2] Mateos, Gonzalo, Juan Andrés Bazerque, and Georgios B. Giannakis. \"Distributed sparse linear regression.\" IEEE Transactions on Signal Processing 58.10 (2010): 5262-5276.\\\n[3] Azulay, Shahar, et al. \"On the implicit bias of initialization shape: Beyond infinitesimal mirror descent.\" International Conference on Machine Learning. PMLR, 2021.\\\n[4] Moroshko, Edward, et al. \"Implicit bias in deep linear classification: Initialization scale vs training accuracy.\" Advances in neural information processing systems 33 (2020): 22182-22193.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "r6RnbzSMNk", "reviewer": "Reviewer_rjVx", "summary": "This manuscript studies a decentralized optimization method for training linear sparse models using a network of agents that collect linear measurements. Unlike decentralized methods relying on L1 regularization, this approach leverages implicit regularization inherited in the gradient descent process. The authors propose a communication-efficient variant referred to as Truncated Decentralized Gradient Descent T-DGD. The authors analyze their decentralized version of gradient descent applied to a non-convex least squares formulation. The manuscript concludes with numerical results that validate the effectiveness of both DGD and T-DGD for sparse learning tasks.", "questions": "See weaknesses", "limitations": "yes.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The manuscript is well-written and provides an interesting perspective on decentralized optimization of a linear least squares system.", "weaknesses": "It remains unclear to me how the approach promotes sparsity. This has neither been discussed nor numerically explored. Here, I would expect a comparison to l1-type regularization approaches promoting sparsity in w* but such comparison and sparsity levels are not provided.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful feedback and for highlighting the areas that need further clarification.\\\n$\\textbf{High-level explanation of promoting sparsity for centralized GD.}$ For gradient descent (GD), the diagonal linear reparameterization turns the additive updates into multiplicative updates as $w_+^{t+1} = w_+^t \\odot \\left(  \\boldsymbol 1_d - 4\\eta \\left( \\boldsymbol s^t - \\boldsymbol w^\\star + \\boldsymbol p^t + \\boldsymbol b^t\\right) \\right)^2$ and $w_-^{t+1} = w_-^t \\odot \\left(  \\boldsymbol 1_d + 4\\eta \\left( \\boldsymbol s^t - \\boldsymbol w^\\star + \\boldsymbol p^t + \\boldsymbol b^t\\right) \\right)^2$ based on signal and error decomposition, where $\\boldsymbol s^t$ denotes the signal part and $\\boldsymbol p^t$ and $\\boldsymbol b^t$ are bounded error parts. For the element $i \\in \\mathcal S$, the small initialization can make $|1 \\pm 4\\eta( s^t_i - w^\\star_i + p^t_i + b^t_i )|>1$ roughly, which can amplify the $s^{t}_i$ to $s^{t+1}_i$ and let $s^t_i$ tend to converge to $w^{\\star}_i$. On the contrary, if $i \\in \\mathcal S^c$, we can select the appropriate step size to bound the cumulative product  $\\prod^t_j { |1 \\pm 4\\eta(s^j_i + p^j_i + b^j_i)| }$  at the $t$-th iteration before early stopping to keep $s^t_i$ is still small enough. The difference dynamics on elements in support set $\\mathcal S$ and non-support set $\\mathcal S^c$ result in sparsity. Sparsity is induced with reparameterization together with small initialization size (one without the other doesn’t work).\\\n$\\textbf{High-level explanation of promoting sparsity for DGD.}$ The consensus errors induced from decentralized network complicate the multiplicative updates, which becomes inexact multiplicative updates as $\\overline{\\boldsymbol u}^{t+1} = \\overline{\\boldsymbol u}^t \\odot \\left(1 - 4\\eta \\left( \\overline{\\boldsymbol u}^t \\odot \\overline{\\boldsymbol u}^t - \\boldsymbol w^\\star + \\hat{\\boldsymbol p}^t + \\hat{\\boldsymbol b}^t \\right)\\right) + \\boldsymbol e^t$. Compared with the exact multiplicative updates, the challenge is that the extra error term $\\boldsymbol e^t$ outside of the multiplication prevent applying the centralized analysis trivially. In addition, the perturbation error terms $\\hat{\\boldsymbol p}^t, \\hat{\\boldsymbol b}^t$ within the multiplication are much complicated than the ${\\boldsymbol p}^t, {\\boldsymbol b}^t$ in the centralized setting due to additionally multiple consensus errors. This requires carefully bounding the consensus error terms, which can control the complicated perturbation errors $\\hat{\\boldsymbol p}^t, \\hat{\\boldsymbol b}^t, \\boldsymbol e^t$ not to be large. Thus, we can use network connectivity to control the consensus errors to bound these three perturbation errors small enough to make the distance between two trajectories obtained by inexact and exact multiplicative updates within statistical accuracy, which can promote sparsity in the decentralized setting. The detailed theoretical mechanism of promoting sparsity has been demystified in Proposition 3. Please refer to the Appendix on pages 28-29.\\\n$\\textbf{ Validating promoting sparsity numerically.}$  We direct the reviewer to Section 6.1 of our main paper. The simulations presented in Figure 1 provide empirical evidence supporting Proposition 3's theoretical mechanism for promoting sparsity. These results show that DGD effectively distinguishes between non-zero and zero support elements, aligning with our theoretical findings. Reviewer can also refer to Figure 4 in $\\textbf{supply.pdf}$, which also demystifies the promoting sparsity for GD and DGD.\\\n$\\textbf{(4)Comparison with decentralized sparse solvers.}$ \\\n$\\textbf{(1) Vanilla Comparison.}$  \\\nWe have compared with existing decentralized sparse solvers, namely: CTA-DGD (LASSO) [2], ATC-DGD (LASSO)[3], and DGT (NetLASSO) [4]. These methods are all based on the LASSO formulation with explicit regularization. The results are presented in Figure 1 of $\\textbf{supply.pdf}$. For each method, we tuned the step size to achieve the best performance. Our proposed method demonstrated the best recovery performance in all network settings with minimum iterations.\\\n$\\textbf{ (2) Truncated version comparison.}$ \\\nWe further compared T-DGD with truncated versions of existing methods: Trun-CTA-DGD (LASSO), Trun-ATC-DGD (LASSO), and Trun-DGT (NetLASSO) which use the same Top-$s$ truncation operator. As shown in Figure 2.(a) of $\\textbf{supply.pdf}$, our proposed method is the only one to achieve successful recovery, while all other  methods failed. This demonstrates that naively combining sparsification with decentralized algorithms is not granted to converge. This is precisely one of the motivations of this work: to provide communication-efficient algorithms with both provably statistical and computational guarantees. \\\n[1] Yuan, K., Ling, Q., & Yin, W. (2016). On the convergence of decentralized gradient descent. SIAM Journal on Optimization, 26(3), 1835-1854.\n[2] Ji, Yao, et al. \"Distributed sparse regression via penalization.\" Journal of Machine Learning Research 24.272 (2023): 1-62.\\\n[3] Ji, Yao, et al. \"Distributed (ATC) gradient descent for high dimension sparse regression.\" IEEE Transactions on Information Theory 69.8 (2023): 5253-5276.\\\n[4] Sun, Ying, et al. \"High-dimensional inference over networks: Linear convergence and statistical guarantees.\" arXiv preprint arXiv:2201.08507 (2022).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qs2CVgkXVh", "reviewer": "Reviewer_Agu7", "summary": "This paper proves the convergence of the decentralized gradient descent (DGD) algorithm under RIP condition when the initialization scale is small. The authors also propose a truncated version of the algorithm with a cheaper cost but comparable performance (in certain situations) to the original DGD.", "questions": "There are already many technical explanations and comparisons in the paper. However, it would be better if more intuitive understanding of the convergence of DGD, and the comparison with centralized GD can be added.", "limitations": "Yes", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The theory seems sound and nontrivial. The authors prove the convergence for DGD, while previously it seems that only centralized GD results exist.", "weaknesses": "This paper is a little bit technical.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your time and effort in reviewing our manuscript and providing valuable feedback. We have addressed your comments and questions as detailed below.\\\n$\\textbf{High-level explanation of promoting sparsity for centralized GD.}$ For gradient descent (GD), the diagonal linear reparameterization turns the additive updates into multiplicative updates as $w_+^{t+1} = w_+^t \\odot \\left(  \\boldsymbol 1_d - 4\\eta \\left( \\boldsymbol s^t - \\boldsymbol w^\\star + \\boldsymbol p^t + \\boldsymbol b^t\\right) \\right)^2$ and $w_-^{t+1} = w_-^t \\odot \\left(  \\boldsymbol 1_d + 4\\eta \\left( \\boldsymbol s^t - \\boldsymbol w^\\star + \\boldsymbol p^t + \\boldsymbol b^t\\right) \\right)^2$ based on signal and error decomposition, where $\\boldsymbol s^t$ denotes the signal part and $\\boldsymbol p^t$ and $\\boldsymbol b^t$ are bounded error parts. For the element $i \\in \\mathcal S$, the small initialization can make $|1 \\pm 4\\eta( s^t_i - w^\\star_i + p^t_i + b^t_i )|>1$ roughly, which can amplify the $s^{t}_i$ to $s^{t+1}_i$ and let $s^t_i$ tend to converge to $w^{\\star}_i$. On the contrary, if $i \\in \\mathcal S^c$, we can select the appropriate step size to bound the cumulative product  $\\prod^t_j { |1 \\pm 4\\eta(s^j_i + p^j_i + b^j_i)| }$  at the $t$-th iteration before  early stopping to keep $s^t_i$ is still small enough. The difference dynamics on elements in support set $\\mathcal S$ and non-support set $\\mathcal S^c$ result in sparsity. Sparsity is induced with reparameterization together with small initialization size (one without the other doesn’t work).\\\n$\\textbf{High-level explanation of the success of DGD and comparison.}$ The consensus errors induced from decentralized network complicate the multiplicative updates, which becomes inexact multiplicative updates as $\\overline{\\boldsymbol u}^{t+1} = \\overline{\\boldsymbol u}^t \\odot \\left(1 - 4\\eta \\left( \\overline{\\boldsymbol u}^t \\odot \\overline{\\boldsymbol u}^t - \\boldsymbol w^\\star + \\hat{\\boldsymbol p}^t + \\hat{\\boldsymbol b}^t \\right)\\right) + \\boldsymbol e^t$. Compared with the exact multiplicative updates, the challenge is that the extra error term $\\boldsymbol e^t$ outside of the multiplication prevent applying the centralized analysis trivially. In addition, the perturbation error terms $\\hat{\\boldsymbol p}^t, \\hat{\\boldsymbol b}^t$ within the multiplication are much more complicated than the ${\\boldsymbol p}^t, {\\boldsymbol b}^t$ in the centralized setting due to additionally multiple consensus errors and loss of global RIP condition for each agent. This requires carefully bounding the consensus error terms, which can control the complicated perturbation errors $\\hat{\\boldsymbol p}^t, \\hat{\\boldsymbol b}^t, \\boldsymbol e^t$ not to be large. Specially, we can utilize the signal and error decomposition and diagonal linear reparameterization to reparameterize $\\boldsymbol e^t$ into the formula as $\\boldsymbol e^t= \\overline{\\boldsymbol{u}}^t \\odot 4\\eta \\boldsymbol f^t$, where the $\\boldsymbol f^t$ is the bounded perturbation error that can be merged into $\\hat{\\boldsymbol p}^t, \\hat{\\boldsymbol b}^t$. Now we can rewrite the inexact multiplicative updates $\\overline{\\boldsymbol u}^{t+1} = \\overline{\\boldsymbol u}^t \\odot \\left(1 - 4\\eta \\left( \\overline{\\boldsymbol u}^t \\odot \\overline{\\boldsymbol u}^t - \\boldsymbol w^\\star + \\hat{\\boldsymbol p}^t + \\hat{\\boldsymbol b}^t + \\boldsymbol f^t \\right)\\right)$. Trivially applying existing consensus error analysis would give crude bounds for  $\\hat{\\boldsymbol p}^t, \\hat{\\boldsymbol b}^t, \\boldsymbol f^t$, which hinder achieving statistical optimal recovery. Thus, we propose a fine-grained analysis for consensus errors to bound $\\hat{\\boldsymbol p}^t, \\hat{\\boldsymbol b}^t, \\boldsymbol f^t$ carefully. In addition, the existence of $\\boldsymbol e^t$ makes extending the proof of the simplified non-negative $\\boldsymbol w^\\star$ case to the general $\\boldsymbol w^\\star$ setting in the decentralized framework non-trivial compared to the centralized setting, which only needs to conduct induction hypothesis for non-negative $\\boldsymbol w^\\star$ case. Therefore, we conduct a comprehensive induction process to both $\\boldsymbol u$ and $\\boldsymbol v$ simultaneously for general $\\boldsymbol w^\\star$. Under our integrated induction hypothesis, we can use network connectivity to control the fine-grained consensus errors to bound these three perturbation errors $\\hat{\\boldsymbol p}^t, \\hat{\\boldsymbol b}^t, \\boldsymbol f^t$ small enough to make the distance between two trajectories obtained by inexact and exact multiplicative updates within statistical accuracy, which can promote sparsity in the decentralized setting. The detailed theoretical mechanism of promoting sparsity has been demystified in Proposition 3. Please refer to the Appendix on pages 28-29.\\\n$\\textbf{Empirical Results Comparison between GD and DGD.}$ The comparison results are shown in Figure 4 of $\\textbf{supply.pdf}$, which indicates that the trajectory of DGD  mimics that of GD. DGD can achieve optimal statistical estimation as GD. The delayed convergence of DGD is due to the decentralized network. These experimental results corroborate our high-level explanation of the success of DGD.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We sincerely thank all the reviewers for their careful review and insightful comments. We have addressed each of the questions raised by all  reviewers in a point-by-point manner as detailed below. We hope our responses can address the concerns raised. Additionally, we have included supplementary experimental results in the attached file $\textbf{supply.pdf}$. We invite the reviewers to read these results and welcome any further suggestions they might have.

Meta-review: This paper delves into the implicit regularization of decentralized gradient descent applied to diagonal linear networks for sparse regression. While implicit regularization in centralized settings has been extensively studied, this work offers valuable theoretical insights into its behavior within decentralized frameworks (which are under-explored). The authors provide a solid theoretical analysis and, based on that, propose a novel truncated decentralized gradient descent algorithm.

In the response to reviewer E5yh, the authors has provided a comprehensive summary of the novelty and key contributions. Some theoretical insights regarding the interplay between implicit regularization and decentralized optimization are new and interesting.

Although some reviewers (rjVx and Agu7) initially expressed concerns about the intuitive explanations behind the technical results, the authors addressed them in the rebuttal and will revise the paper to enhance clarity.

Ultimately, all reviewers reached a positive consensus, leading me to recommend acceptance based on the rebuttal and discussion.
Decision: Accept (poster)