Implicit Regularization of Decentralized Gradient Descent for Sparse Regression

Authors: tongle  wu
ying  sun
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 06:04:33

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.

Main paper: 
 introduction: 
 Modern deep learning is generally in the over-parameterized regime where the models have significantly more parameters than available training examples [5, 37] . Although deep learning models exhibit remarkable performance in multiple domains, the theoretical understanding of optimization and generalization for deep learning is still limited. Recent studies show that despite being overparameterized, gradient-based methods applied to minimize the emperical loss exhibit the implicit regularization phenomenon. For example, a line of works [3, 4, 10, 14] 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, 8, 22] 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 [32, 35, 36] 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 are limited to 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 a 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.In this paper, we study the sparse learning problem [31] in the overparameterized regime, which shares many key characteristics with deep learning 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 w ⋆ from its noisy linear measurements over m agents. These agents communicate over an undirected connected mesh network without a central coordinator, and each agent can only communicate with its one-hop neighbors. The i-th agent has its own n samples {(x i,j , y i,j )} n j=1 . Each j-th data pair (x i,j , y i,j ) is generated according to the noisy linear modelEQUATIONwhere x i,j ∈ R d and y i,j ∈ R denotes respectively the j-th feature and its corresponding response, ξ i,j is the observation noise, and w ⋆ ∈ R d is the sparse model parameter to be learned, common to all agents, and has only s (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-parameterizing w = u ⊙ uv ⊙ v, the loss function can be formulated as minimizing the following regularization-free nonlinear least square problem:EQUATIONwhere f i (u, v) corresponds to the loss function of i-th agent. Problem (2) can also regarded as the supervised learning problem on the diagonal linear network of degree-2 [35] .Problem (2) is highly non-convex with u and v, however, recent works [11, 33, 38] demonstrate 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 2 i -v 2 i | would increase with iteration for coordinate i such that w ⋆ i ̸ = 0, where the remaining ones stay small enough before early stopping. As a result, GD identifies the support of w ⋆ as the algorithm processes. In the decentralized setting, general results from the pure optimization perspective can only certify convergence to 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 (2) 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 on the step size. However, we show that under specific conditions-namely, if the global design 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. • 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. We separately control the consensus errors on support S and non-support S c by the magnitudes of parameters on support S and non-support S c , respectively. Our fine-grained analysis for consensus errors is distinct 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-negative w ⋆ case to the general w ⋆ setting as the centralized setting, we conduct a comprehensive induction process to both u and v simultaneously for general w ⋆ . • Truncated DGD. We propose a communication-efficient truncated DGD (T-DGD) method that at each iteration, vectors being transmitted are truncated, keeping only s 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. 
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 [13] 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 in [33, 38] under mild conditions. Woodworth et al. [35] studied the impact of initialization scale on solutions. Scott et al. [25] demonstrated the benefit of stochasticity of SGD in sparse regression and explored the impact of momentum in [23] . The more recent process in understanding the linear diagonal networks can be found in references [6, 9, 11, 17, 21, 24, 39] . 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 w ⋆ in high-dimensional sparse linear regression under the decentralized setting, Ji et al. [16] 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. [29] proposed the NetLASSO based on the gradient tracking method and obtained d-independent convergence rate and optimal statistical accuracy. To complement work [16] , Ji et al. proposed DGD-ATC by mixing the local gradients along iterations and achieved logarithmic dependence on d in [15] . Maros et al. [19] proposed DGD 2 method based on a double mixing for solving decentralized LASSO and obtained similar theoretical guarantees in [15, 29] . To improve the computation efficiency, Maros et al. [18] integrated accelerated proximal gradient descent with gradient tracking to solve decentralized LASSO. Despite these developments, it remains unclear whether leveraging the unregularized overparameterization 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 centralized optimization methods for overparameterized models have been extensively studied [12, 28] , but only a few works have investigated the implicit regularization of decentralized optimization methods. Richards et al. [27] studied the implicit regularization for decentralized stochastic gradient descent for solving general unregularized convex problems. Zhu et al. [40] demonstrated that decentralized stochastic gradient descent implicitly executes the sharpness-aware minimization algorithm for general non-convex problems. Taheri et al. [30] studied the implicit regularization of DGD in overparameterized classification for separable data. Recent work [20] demonstrated the implicit regularization of the DGD 2 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. 
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.Throughout this paper, we use [m] to denote set {1, • • • , m} for given positive integer m, 1 d denotes d-dimensional vector that all element are one and I d denotes d-dimensional identity matrix. For ground truth parameter w ⋆ , the relevant notations are support set S := {j|w ⋆ j ̸ = 0}, positive support set S + := {j|w ⋆ j > 0}, negative support set S -:= {j|w ⋆ j < 0} and non-support setS c := {j|w ⋆ j = 0}, w ⋆ max := max j∈S |w ⋆ j | and w ⋆ min := min j∈S |w ⋆ j |. ∀x ∈ R d , x S := 1 S ⊙x where 1 S denotes a vector equal to one for all coordinates j ∈ S and equal to zero everywhere else. Symbol "⊙" denotes Hadamard product that (a ⊙ b) j = a j b j , ∀a, b ∈ R d . The averaged signal is defined as w t := 1 m m i=1 w t,i and similar notations can be extended to u t , v t . X := [X 1 ; • • • ; X m ] denotes the concatenated sample matrix, where each row of X i represents one feature vector in agent i. ∥•∥ denotes the Frobenius norm for vector and the spectral norm (maximum singular value) for matrix. ∥A∥ ∞ := max i,j |A ij | denotes infinity norm. We use a = O(b) to denote that inequality a ≤ Cb holds with some absolute constants C that do not depend on any parameters of the problem. The notation a ≲ b shares the same meaning as a = O(b). Finally, we use a ≳ b if there exists a universal constant c such that a ≥ cb.We focus on DGD solving problem (2) in mesh networks, modeled as an undirected graph G = {V, E} where nodes V = {1, • • • , m} represent the set of agents and edges E ⊂ V × V represent the communication links. An unordered pair {i, j} is included in E if and only if there is a bidirectional communication link between agent i and j. The set of one-hop neighbors for agent i is denoted byN i := {j ∈ V|(i, j) ∈ 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.EQUATIONEQUATIONwhere the w t,i := u t,i ⊙ u t,iv t,i ⊙ v t,i denotes the local estimator in agent i at t th iteration, the initialization is u 0,i = v 0,i = α1 d , ∀i ∈ [m] and η is constant step size. W is the nonnegative weight mixing matrix for the undirected mesh network, where W ij > 0 if there is a link between agents i and j, and W ij = 0 otherwise. The mixing matrix W related to the undirected graph satisfies the following assumption. Assumption 1. The communication network G is connected. The weight matrix W = [w ij ] m i,j=1 for this graph has the following properties: (i)w ij = 0 for all pairs (i, j) that are not in E; (ii) it is double stochastic that 1 T m W = 1 T m and W 1 m = 1 m ; (iii) the spectral gap ρ := W -1 m 1 m 1 T m ≤ 1.This assumption is common in decentralized optimization literature. We need the following RIP condition which is a key condition to obtain the optimal estimator for sparse regression.Definition 1. The global design matrix X/ √ N ∈ R N ×d satisfies the (δ, s)-Restricted Isometry Property (RIP) if for any s-sparse vector w ∈ R d , there is (1 -δ) ∥w∥ 2 ≤ Xw/ √ N 2 ≤ (1 + δ) ∥w∥ 2 .The RIP condition was first introduced in the compressed sensing literature in [7] which is a little more restrictive condition to achieve optimal statistical rate than the restricted eigenvalue condition in [1] . We inherit this assumption in the centralized setting [33, 38] to achieve optimal estimator error under the condition that parameter δ is upper bounded. i / √ n, there is (1 -δ max ) ∥w∥ 2 ≤ ∥X i w/ √ n∥ 2 ≤ (1 + δ max ) ∥w∥ 2 .The definition of the local RIP condition is just for ease of proof presentation, as we do not necessitate any upper bound on the local RIP parameter δ max . 
main result: 
 Based on the above method and assumptions, we now give theoretical guarantees of DGD in solving problem (2) for sparse regression problem (1) as follows. EQUATIONand the spectral gap ρ satisfiesEQUATIONthen after running t = O 1 ηζ log 1 α iterations. There would beEQUATIONwhere ς := maxX T ξ N ∞ , ϵ , ζ := max w ⋆ min 5 , 960ς .• Mechanism to promote sparsity. The consensus errors induced from decentralized network complicate the multiplicative updates, which becomes inexact multiplicative updates asu t+1 = u t ⊙ 1 -4η u t ⊙ u t -w ⋆ + pt + bt + e t .Compared with the exact multiplicative updates of GD in [33] , the challenge is that the extra error term e t outside of the multiplication prevents applying the centralized analysis trivially. In addition, the perturbation error terms pt , bt 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 can control the complicate perturbation errors pt , bt , 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.• Statistical Guarantee. Based on the result in (7) 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 w ⋆ that achieves the same order of statistical error as the centralized setting in [33] . The formula in (7) not only illustrates that we establish the network-independent estimator error bound but also inherits the benefit of implicit regularization, which indicates that if the signal-to-noise is high enough, the statistical error is independent of ambient dimension d. In contrast, existing results in decentralized LASSO methods [15, 16, 19, 29] , have consistent dependence on d in any case.• Computational Complexity. The iteration complexity of early stopping is network-dependent that is because the t = O 1 ηζ log 1 α has the dependence on stepsize, which should satisfy the condition in (5) . This suggests that poorer network connectivity leads to higher computational complexity. Although the initialization has no dependence on network connectivity, 1 α has polynomial dependence on d, and the dependence of complexity on d is just logarithmic, which is similar to DGD in solving LASSO in [15, 19] and improves the polynomial dependence on d in [16] .• Dependence on network connectivity. For accurate estimation, it is 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 a higher degree of network connectivity. This can be understood from the perspective of heterogeneity, where smaller ratios indicate a significant disparity between local and global design matrices. Consequently, condition ( 6) is reasonable as it suggests that higher levels of heterogeneity necessitate improved network connectivity. In numerical experiments, we can observe that if ρ does not satisfy the condition as (6) , obtaining optimal statistical error is not achievable, which indicates the optimal statistical error undergoes a phase transition with the network connectivity.Our results demonstrate the benefit of overparameterization for DGD. Theorem 1 shows that standard DGD is sufficient to provide statistically optimal 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-correction-based methods are necessary for heterogeneous scenarios. The following corollary considers the specific 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 1-sub-Gaussian distribution, and the total sample size satisfies N ≳ s s log ed s + log dN m . The noise vector ξ is generated from independent σ 2 -sub-Gaussian entries, and the initialization is set as Theorem 1 with and (4) based on DGD for solving problem (2) would obtain estimator that w tw ⋆ ≲ σ s log d N with probability at least 1 -3 8d 3 . Corollary 1 indicates that in the sub-Gaussian setting, network-independent statistical error obtained by DGD matches optimal rate O σ s log d N under ℓ 2 metric in the centralized setting [26] . In this context, the condition for network connectivity implies that the smaller ρ is required as the number of agents m increases. This is reasonable because when the total sample size N 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.Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)? Answer: [Yes] Justification: Guidelines:• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to 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 or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways.For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a 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. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example (a) If the contribution is primarily a 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. (c) If the contribution is a new model (e.g., a large language model), then there should either be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 
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 u t,i and v t,i to its neighboring agents per iteration. Because we are considering the highdimensional regime where the feature has ultra-high dimension, which leads to the O d • 1 ηζ log 1 α 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 t,i , v t,i in all rounds of communication. Since all elements of u t,i and v t,i equal to α 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 is 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 EQUATIONQuestion: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [Yes] Justification: Guidelines:• The answer NA means that paper does not include experiments requiring code.• Please see the NeurIPS code and data submission guidelines (https://nips.cc/ public/guides/CodeSubmissionPolicy) for more details. • While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark). • The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //nips.cc/public/guides/CodeSubmissionPolicy) for more details. • The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc. • The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why. • At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable). • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
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 6.3, we 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. N (0, 0.5 2 ) distribution, and the magnitudes of elements on support S are 1. All experiments are conducted on 12th Gen Intel(R) Core(TM) i7-12700@2.10GHz processor and 16.0GB RAM under Windows 11 system.We organize the experiments as follows: 1) 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 t , u t , v t and u t,iu t , v t,iv t . In this case, we set d = 2000, s = 10, m = 10, N = 400, ρ = 0.1778, α = 10 -6 . Fig. 1 (a) demonstrates the convergence of averaged w t in DGD, showing successful convergence of elements on support S and maintenance of small magnitudes for elements on non-support S c . Fig. 1 (b) and Fig. 1 (c) further illustrate how DGD utilizes u t and v t to fit parameters on positive and negative support, respectively. Additionally, the magnitudes of u t and v t on non-positive and non-negative support remain small enough as the initialization. Consensus errors u t,iu t and v t,iv t are depicted in Fig. 1 (d) and Fig. 1 (e), respectively. The trends in these curves correspond to the magnitudes of the model parameter, affirming the validity of our analysis. Fig. 3 (c) illustrates that ρ would influence the stopping time when DGD can obtain the optimal estimator. The worse the network, the more iterations it takes to find the optimal estimator.(e) v t,i -v tIn this section, we evaluate the effectiveness of T-DGD. Initially, we vary the values of N , keeping the other parameters consistent with the simulations in Fig. We have compared our proposed method with three existing decentralized methods, namely: CTA-DGD (LASSO) [16] , ATC-DGD (LASSO) [15] , and DGT (NetLASSO) [29] . 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.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 in Fig. 6 , our proposed method is the only one to 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-efficient algorithms with both provably statistical and computational guarantees. This result also demonstrates the unique benefit of overparameterization and implicit regularization for decentralized learning setting, which has not been explored in the literature of learning theory. Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes]Justification:Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
conclusion: 
 In this study, we study the implicit regularization of 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 a promising idea to reduce communication complexity while maintaining performance. In future work, exploring the possibility of relaxing the RIP condition in our assumption and leveraging the restricted eigenvalue condition to achieve optimal estimator in the decentralized setting is an interesting topic. Additionally, investigating alternative forms of implicit regularizations in decentralized optimization algorithms for more complicated overparameterized models is another intriguing direction.Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?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, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes] Justification:Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? 
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, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
 
 Appendix: 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 1, Corollary 1, and Proposition 1 in the main paper based on Proposition 3 in Section A.4.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∆ t,i u := u t,i -u t . ∆ t,i u,S + = ∆ t,i u ⊙ 1 S + and notations ∆ t,iu,S -, ∆ t,i u,S c can be defined similarly. The additional notations are defined asEQUATIONAbove definitions can be also extended to variable v similarly.Lemma 1. (Theorem 6.5 in [34] ) Consider the random feature vector x ∈ R d that all entries obey i.i.d.1-sub-Gaussian distribution, if the sample size satisfies n ≳ δ -2 s log ed s + log 2 ϵ , then the sample covariance matrix X = 1 n n i=1 x i x T i satisfies (δ, s)-RIP condition with probability 1 -ϵ. Lemma 2. (Lemma A.3 in [33]) Suppose that X √ n ∈ R n×d satisfies the (δ, s + 1)-RIP, if w ∈ R d is a s-sparse vector, then X T X n -I w ∞ ≤ √ sδ∥w∥ ∞ . Lemma 3. (Lemma A.4 in [33]) Suppose that 1 √ n X ∈ R n×d that satisfies (δ, 1)-RIP with 0 ≤ δ ≤ 1, then we have X T X n w ∞ ≤ 2d∥w∥ ∞ , ∀w ∈ R d .Lemma 4. (Lemma B.5 in [38] ) Let ξ ∈ R n is a vector of independent σ-sub-Gaussian random variables and all ℓ 2 norm of column vectors of X ∈ R n×d are bounded, then with high probability1 -1 8d 3 such that X T ξ n ∞ ≲ σ log d n .We consider the simplified setting where all the elements on support are positive for ground truth w ⋆ .The following lemma shows the recursion of average variable u t on support S and non-support S c . Lemma 5. Consider the sequence {u t,i } generated according to (3) and (4) by DGD for solving loss function in (2), the average signal u t on support S and non-support S c are updated according to the following formulasEQUATIONEQUATIONwhere the perturbed error terms p t , q t , g t , f t induced from decentralized network are defined asEQUATIONEQUATION)EQUATIONEQUATION)Proof. Based on the updating of DGD, one-step iteration of the averaged parameter isEQUATIONThe gradient difference has the formula asEQUATIONwhere the last inequality is due to the definition of ∆ t,i . Substituting the above equality into (16) would haveEQUATIONBecause there are1 m m i=1 u t S ⊙ ∆ t,i S = 0 and 1 m m i=1 ∆ t,i S ⊙ u t S ⊙ u tS -w ⋆ = 0, the above formula can be simplified asEQUATION)Thus, this would obtain the recursion (10) for support averaged signal.The recursion of optimization error on non-support S c becomesEQUATION)Rearranging the above equality would obtain the (11) .The following lemma shows the recursion of consensus error on support S and non-support S c . Lemma 6. Consider the sequence {u t,i } generated according to (3) and (4) by DGD for solving loss function in (2), the consensus error ∆ t on support S and non-support S c have following recursionEQUATION)Proof. Based on the iteration of DGD, there isEQUATIONThus, the consensus error on support S has recursion as followsEQUATIONwhere (i) is due to the defined spectral gap of network in Assumption 1 and (ii) uses the gradient difference formula in (17) andEQUATIONand local and global RIP conditions. The (iii) is summing up terms involved ∆ t+1 S ∞ and u tseparately.The recursion of consensus error on non-support S c part is as followsEQUATIONThe following proposition shows the dynamics of average variable u t and consensus error ∆ t,i in the form of an inductive hypothesis. Before showing the proposition, we define the following quantities. We define T := 1 k = 0, 1, • • • , K -1 steps. • (a) For T k-1 ≤ t < T k that ∀k ∈ [K], there is u t S ⊙ u t S -w ⋆ ∞ ≤ w ⋆ max 2 k . • (b) For ∀k ∈ [K], there is u T k-1 S ⊙ u T k-1 S -w ⋆ ∞ ≤ w ⋆ max 2 k . • (c) For T k-1 ≤ t < T k that ∀k ∈ [K], it has ∆ t S ∞ ≤ 4βρ 3 4 η u t S ∞ B k . In addition, the refined element-wise bound is ∆ t j ∞ ≤ 4βρ 3 4 η|u t j |B k , ∀j ∈ S. • (d) For T k-1 ≤ t < T k that ∀k ∈ [K], it has ∆ t S c ∞ ≤ 4βρ 3 4 η u t S c ∞ B k . In addition, the refined element-wise bound is ∆ t j ∞ ≤ 4βρ 3 4 η|u t j |B k , ∀j ∈ S c .• (e) For ∀k ∈ [K] and ∀j ∈ S, α 3 ≤ uT k-1 j ≤ w ⋆ j + 4B k .Proof. Proof idea: Inductions (a), (b), (e) indicate that if the connectivity of the network is sufficiently well (ρ is small enough), the trajectory of the averaged signal u t would mimic that of the centralized case [33] . 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 c 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 on network connectivity ρ and step size η can guarantee that the averaged signal in decentralized would have properties in inductions (a), (b), (e) based on inductions (c), (d).Base case: As the initialization u 0,i = α1 d , ∀i ∈ [m]. Due to the condition on α, the base case is true.Step: If the above (a)-(e) induction hypotheses hold all until some 0 ≤ k ≤ K -1, we should prove they still hold at k + 1-th induction step.(a) The magnitude of p t in ( 12) under this induction step can be bounded based on inductions (c), (d).∀ T k-1 ≤ t < t + 1 < T k , if u t S c∞ keep same order as initialization, then there isEQUATIONwhere the first inequality is based on Lemma 2 and Lemma 3, the last inequality is due to step size, value of β, u t S 2 ∞ ≤ 2w ⋆ max , network connectivity condition and global RIP condition that ρ1 4 √ sδ max ≤ √ sδ ≤ 1.For the perturbation q t in (13), which is an error term outside the multiplicative updates in (10) , based on induction (a), fine-grained upper in (c), there is ∀j ∈ SEQUATIONwhere the first inequality is due to (28) by comparing formula of q t with p t and last inequality is due to step size condition and such that ρ1 4 max i X T i ξ i n ∞ ≤ X T ξ N ∞ < w ⋆ max .Then q t could be reparameterized as q t = r t q ⊙ u t S where r t q ∞ ≤ √ ρB k 16 for ∀t that T k-1 ≤ t < T k , the perturbed optimization recursion on support over decentralized network in (10) becomesEQUATION)where the perturbation errors E t 2 and E t 3 are defined asEQUATION)Because there isE t 2 ∞ + E t 3 ∞ + ∥p t ∥ ∞ + r t q ∞ ≤ B k, which is based on the upper bound in (70). Then the proof is divided into the following two cases based on the magnitude of the element in w ⋆ S + .(1) ∀j that w ⋆ j ≥ 20B k , based on induction hypothesis (e) that uT k-1 j 2 ≤ w ⋆ j + 4B k ,there is uT k-1 j 2 ≤ 6 5 w ⋆ j, which illustrates that it satisfies the conditions in Lemma B.10 in [33] . Then because induction hypothesis (a) and (b) are true until t-th iteration, then ifB k < u t j 2 -w ⋆ j ∞ ≤ w ⋆ max 2 k , then u t+1 j 2 -w ⋆ j ∞ ≤ u t j 2 -w ⋆ j ∞ ≤ w ⋆ max 2 k , else if u t j 2 -w ⋆ j ∞ ≤ B k , then u t+1 j 2 -w ⋆ j ∞ ≤ B k .Combined with two cases, we can conclude that (a) also holds for (t + 1)-th iteration for j that w ⋆ j ≥ 20B k .(2) For arbitrary j-th elements whose magnitude is not sufficiently larger than the perturbation that w ⋆ j ≤ 20B k , based on the upper bound in induction (e), perturbation bound and monotonic property in Lemma B.6 in [33] , we can guarantee that u t j 2 would keep staying in (0, w⋆ j +4B k ]. With condition w ⋆ j ≤ 20B k , we can conclude that u t+1 j 2 -w ⋆ j ∞ ≤ max{w ⋆ j , 4B k } ≤ 20B k ≤ w ⋆ max 2 k. 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 (k-1)-th induction that can make uT k-1 S 2 -w ⋆ ∞decrease at least by half from the beginning iteration of current induction stage to that of next induction stage. The proof is also divided into two cases.(1) The one case is that ∀j that it already has uT k-1 j 2 -w ⋆ j < w ⋆ max 2 k+1, then with similar proof in (a), we can guarantee that ∀t ≥ T k-1 , u t j 2 -w ⋆ j < w ⋆ max 2 k+1 . Thus, for these supports, we prove the (k + 1)-th induction also holds.(2) The second case is ∀j that there is uT k-1 j 2 -w ⋆ j ≥ w ⋆ max 2 k+1 = 20B k . Based on the upper bound in induction (e) that u T k-1 j 2 ≤ w ⋆ j + 4B k , then u T k-1 j , w ⋆ j must satisfy 0 ≤ u T k-1 j 2 ≤ w ⋆ j -20B k , w ⋆ j ≥ 20B k , respectively. This means u T k-1 jis far away from w ⋆ j at least 20B k distance. According to Lemma B.12 in [33] , to achieve uT k-1 j 2 -w ⋆ j ≤ 20B k , the sufficient condition for the number of iterations t in current induction stage is t ≥ 15 32ηw ⋆ j log (w ⋆ j ) 2 19 u T k-1 j 2 B k. Now we verify the setting of T k as followsEQUATIONwhere the first inequality is due to the definition of B k and small initialization condition that α ≤ ζ 3(w ⋆ max ) 2 and the second inequality is due to w ⋆ j ≥ 20B k and lower bound in induction (e) that uT k-1 j 2 ≥ α 3 . The last inequality is because ζ 3 ≤ 16 40 w ⋆ max 2 K-1 ≤ 16 40 w ⋆ max 2 k = 16B k .Thus, combining the above two cases and similar proof, we can conclude that ∀t ≥ T k , there isu t S 2 -w ⋆ ∞ ≤ w ⋆ max 2 k+1. This completes the proof of induction (b).(c) To make the consensus error satisfy the above induction, ∀t that T k-1 ≤ t < t + 1 < T k , based on one step iteration in (24) of Lemma 6, induction (a), (c) and step size condition η ≤EQUATION)Then the recursion (24) in Lemma 6 becomesEQUATIONwhere the last inequality is based on induction such as if ∆ t S ∞ ≤ 4βρ EQUATION)To guarantee that (34) holds induction (c), the sufficient condition isEQUATIONThe c 10 should be chosen that1+ √ ρ 2(1-c10(1- √ ρ))2 < 1, which means that c 10 should satisfy c 10 ≤ 1-1+ √ ρ 2 1- √ ρ . Then we can set c 10 = 1- 1+ √ ρ 2 1 4 1- √ ρ, which results in1 (1-c10(1- √ ρ)) 2 = 2 1+ √ ρ . Based on (36), the lower bound for β is β ≥ 2 2(1+ √ ρ)+1+ √ ρ 1-ρ .Unfolding the recursion in (24) from the beginning of (k -1)-th induction to the beginning of k-th induction based on (34) and combining induction (a) would haveEQUATIONwhere both the second and third inequalities use lower bound in (35) . To guarantee that the last inequality satisfies the induction (c), the β and ρ should satisfy the following conditionEQUATIONOne sufficient condition for achieving above inequality is 8 1-√ ρ ≤ β 4 .Combine above lower bound of β, we can verify that β = 32 1-√ ρ satisfies this condition and following inequality is attainedEQUATIONwhich implies that the step size η should satisfyEQUATIONOne sufficient condition for achieving inequality is η ≤log 1 α 4 1- 1+ √ ρ 2 4w ⋆ max based on inequality that ln 1 + 1+ √ ρ 2 -1 ≤ 1+ √ ρ 2 -1.Combining all the above conditions on η, we obtain the upper bound as shown in condition (5) .(d) ∀t that T k-1 ≤ t < t + 1 < T k , based on one step iteration in (27) of Lemma 6 and inductions (a), (c), there isEQUATIONwhere the second inequality is due to 4βρ 3 4 ηB j ≤ 4 × 32 1- √ ρ × 1- √ ρ 256w ⋆ max B j ≤EQUATION)With the same derivation in proving induction (c), the lower bound for γ is the same as that of β.Then also unrolling the recursion in (27) from beginning of (k -1)-th induction to beginning of k-th induction and combining induction (a) would haveEQUATION)The derivation of above inequality is similar with (37) . To guarantee the above two inequality satisfy induction (d), the γ and ρ can have the same value as in (38) that γ = β = 32 1- √ ρ .(e) For the upper bound, the proof is divided into three cases.(1) One of case is uEQUATION) Another case is w ⋆ j + B k ≤ u T k-1 j 2 ≤ w ⋆ j + 2B k , in this case ∀t ≥ T k-1 , Either 0 ≤ u t j 2 ≤ ⋆ j + B k , which can use result in case (1) that ∀t ′ ≥ t, 0 ≤ u t ′ j 2 ≤ w ⋆ j + B k or that w ⋆ j + B k ≤ u t j 2 ≤ w ⋆ j + 2B k , which would guarantee that u t+1 j 2 ≤ u t j 2 .(3) The last case is w ⋆ j + 2B k < u t j 2 ≤ w ⋆ j + 4B k , then based on Lemma B.14 [33] , after the sufficient number of iterations that ∀t ≥ 1 10ηB k = 4×2 k ηw ⋆ max and we can check that T k is large enough that satisfies this condition, it can keep that uT k-1 +t j 2 ≤ w ⋆ j + 2B k .Following the above three cases, we can guarantee that there existsu T k j 2 ≤ w ⋆ j + 1 2 × 4B k = w ⋆ j + 4B k+1 .For the lower bound, we can also have bound∥g t ∥ ∞ ≤ 3 √ ρB k 8by comparing formulas between p t and g t , ∀t that T k-1 ≤ t < T k . For perturbation f t , based on induction (a), fine-grained bound in (d), ∀j ∈ S c it hasEQUATIONwhere the first inequality is due to bound for ∥g t ∥ ∞ and the last inequality is the same reason as (29) .f t can also be reparameterized asf t = r t f ⊙u t S c where r t f ∞ ≤ √ ρB k16 for ∀t that T k-1 ≤ t < T k , the perturbed optimization recursion on non-support S c over decentralized network in (11) becomesEQUATION)Based on the similar lower bound (79) and upper bound in (80), we can conclude that ∀t ≤ O 1 ηζ log 1 α 4 , there isEQUATIONwhere this inequality guarantees that the averaged signal on non-support remains u t S c ∞ ≤ √ α until early stopping. ∀j ∈ S, we use j k to denote the largest index that w ⋆ j ≤ B j k + α 3 . As B 0 = w ⋆ max , the existence of j k is guaranteed. Then for t = 0, • • • , T j k -1 and based on (30), the u t j 2 would shrinkage from initialization α 2 , to obtain the lower bound, we should consider the maximum shrinkage as follows uEQUATIONwhere the last inequality is due to (46), 3 40 ]. Thus, we have u t ju i j 2 ≤ α 2 , ∀ i = 1, • • • , T j k -1 and step size condition that η u i j 2 + E i 2 ∞ + E i 3 ∞ + g i ∞ + r i f ∞ ≤ 3 40 and (1 -5x)(1 + 8x) ≥ 1, ∀x ∈ [0,2 ≥ α 3 for ∀ t = 0, • • • , T j k . For t = T j k + 1, • • • , T j k +1 -1 and ∀ j ∈ S, let consider the auxiliary iterations that ût j 2 = ût-1 j 2 ⊙ 1 -4η ût-1 j 2 -w ⋆ j -B j k +1 2 where ûT j k j = u T j k j ≥ α 3as above proved. Based on definition of j k , there is w ⋆ j -B j k +1 ≥ α 3 . According to monotonic property in Lemma B.6 in [33] , we can guarantee thatûT j k +1 j 2 ∈ min ûT j k j , w ⋆ j -B j k +1 , max ûT j k j , w ⋆ j -B j k +1 that ensures that u T j k +1 j 2 ≥ ûT j k +1 j 2 ≥ α 3where the first inequality is due to the squeezing property in Lemma B.9 in [33] .Then we can follow the same analysis to prove that left i-th induction step that i = j k + 2, • • • , m -1 based on the monotonic property of B k .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 v t,i and its consensus error terms. The following formulates the recursion of perturbed average variable u t and similar derivation could be applied to v t . Lemma 7. Consider the sequence {u t i , v t i }, i ∈ [m] generated according to (3) and (4) by DGD for solving problem (2), the average signal {u t } on positive support S + , negative support S -and non-support S c are updated according to the following formulasu t+1 S + = u t S + ⊙ 1 d -4η u t S + 2 -w ⋆ S + -4η X T X N u t S c 2 -v t S c 2 + u t S - 2 -v t S + 2 +4η X T ξ N -4η X T X N -I u t S + 2 -w ⋆ S + -v t S - 2 -w ⋆ S --4ηp t u -4ηq t u ;(48)u t+1 S -= u t S -⊙ 1 d -4η -v t S - 2 -w ⋆ S -+ X T X N u t S c 2 -v t S c 2 + u t S - 2 -v t S + 2 - X T ξ N + X T X N -I u t S + 2 -w ⋆ S + -v t S - 2 -w ⋆ S - -4ηy t u -4ηz t u ;(49)EQUATION)where the perturbed error terms p t u , q t u , y t u , z t u , g t u , f t u induced from decentralized network are defined asEQUATION)EQUATION)EQUATION)f t u := 1 m m i=1 ∆ t,i u,S c ⊙ X T i X i n -I u t S + 2 -w ⋆ S + -v t S - 2 -w ⋆ S - + 2u t S + ⊙ ∆ t,i u,S + + ∆ t,i u,S + 2 -2v t S -⊙ ∆ t,i v,S --∆ t,i v,S - 2 - X T i ξ i n + X T i X i n u t S c + ∆ t,i u,S c 2 -v t S c + ∆ t,i v,S c 2 + u t S -+ ∆ t,i u,S - 2 -v t S + + ∆ t,i v,S + 2 ;(54)EQUATION)EQUATIONProof. The average of optimization for u t,i , i ∈ [m] under DGD are as followsEQUATION)Based on error decomposition on positive support S + , negative support S -and non-support S c , there hasEQUATION)With same decomposition on S + , S -, S c for Π 1,i and Π 2,i , there areEQUATION)Substituting (59) into (57) would obtain the perturbed recursion of averaged u t S + , u t S -, u t S c in Lemma 7.The following lemma separately bounds the consensus errors on S + , S -, and S c by the corresponding magnitudes of parameters, which is different from the current analysis in the decentralized optimization literature. Lemma 8. Consider the sequence {u t,i , v t,i }, i ∈ [m] generated according to (3) and (4) by DGD for solving (2), the consensus error of ∆ t u on positive support S + , negative support S -and non-support S c have the following recursionsEQUATIONEQUATION)where the C t err is defined asEQUATION)Proof. Based on the updating of DGD, there isU t+1 I m - 1 m 1 m 1 T m = U t -η∇ u f (U t , V t ) W I m - 1 m 1 m 1 T m = U t -∇ u f U t , V t + ∇ u F U t , V t W - 1 m 1 m 1 T m = U t -∇ u f U t , V t + ∇ u f U t , V t + ∇ u f U t , V t -∇ u f U t , V t + ∇ u F U t , V t -∇ u f U t , V t W - 1 m 1 m 1 T m . (64)Thus, there isEQUATIONwhere the second inequality is due to (64) and the last inequality is substituting into the formula Π 1,i , Π 2,i in (59) and gradient difference at averaged pair. Merging terms involved u t S + ∞ and ∆ t u,S + ∞ separately would obtain the result in (60). Performing analogous proof would yield results on negative support S -in (49) and non-support S c in (50).The following proposition describes the dynamics of u t,i , v t,i by conducting inductive hypothesis for both u t,i and v t,i , which is different with centralized setting [33] . Because the complicated consensus errors prevent transferring the proof of non-negative case to general case trivially. Proposition 3. This proposition inherits Proposition 2 for the general case with considering dynamic of v t i for learning negative part signal w ⋆ S -. Recall the definitions of T, T k , T k , B k , K, β in Proposition 2, the following statements hold in each induction step.• (a) ∀t that T k-1 ≤ t < T k with ∀k ∈ [K], there is max u t S + 2 -w ⋆ S + ∞ , v t S - 2 -w ⋆ S - ∞ ≤ w ⋆ max 2 k . • (b) For ∀k ∈ [K], there is max u T k-1 S + 2 -w ⋆ S + ∞ , v T k-1 S - 2 -w ⋆ S - ∞ ≤ w ⋆ max 2 k . • (c) ∀t that T k-1 ≤ t < T k with ∀k ∈ [K], there are max i ∆ t,i u,S + ∞ ≤ 4βρ 3 4 η u t S + ∞ B k and max i ∆ t,i v,S - ∞ ≤ 4βρ 3 4 η v t S -∞ B k . • (d) For any T k-1 ≤ t < T k that ∀k ∈ [K], there are max i ∆ t,i u,S c ∞ ≤ 4βρ 3 4 η u t S c ∞ B k and max i ∆ t,i v,S c ∞ ≤ 4βρ 3 4 η v t S c ∞ B k .• (e) For anyT k-1 ≤ t < T k that ∀k ∈ [K], there are max i ∆ t,i u,S - ∞ ≤ 4βρ 3 4 η u t S -∞ B k and max i ∆ t,i v,S + ∞ ≤ 4βρ 3 4 η v t S + ∞ B k . • (f) ∀t that T k-1 ≤ t < T k with k ∈ [K],there are refined element-wise bounds for consensus errors as∆ t u,j ∞ ≤ 4βρ 3 4 η|u j |B k and ∆ t v,j ∞ ≤ 4βρ 3 4 η|v j |B k , ∀j ∈ S. • (g) For ∀j ∈ S + and k ∈ [K], there is α 3 ≤ u T k-1 j 2 ≤ w ⋆ j + 4B k . For ∀j ∈ S -and k ∈ [K],there isα 3 ≤ v T k-1 j 2 ≤ w ⋆ j + 4B k . • (h) ∀t ≤ O 1 ηζ log 1 α , max u t S c ∞ , v t S c ∞ ≤ √ α. • (i) ∀t ≤ O 1 ηζ log 1 α and ∀j ∈ S, there is u t j v t j ≤ α 3 2 . • (j) ∀t ≤ O 1 ηζ log 1 α , it has max u t S -∞ , v t S + ∞ ≤ √ α.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 is because the error terms induced in (48), ( 49),(50) by the decentralized network in Lemma 7 prevent obtaining the results in inductions (i), (j) without induction steps as Lemma B.16 in [33] , 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 of u t on the negative support S -and v t on the positive support S + remain small up to the early stopping iteration steps. The inductions (a)-(h) show that the averaged signal u t on the positive support S + and the averaged signal v t on the negative support exhibit dynamics similar to those in non-negative case, as outlined in Proposition 2.Base case: As the initialization u 0,i = v 0,i = α1 d , ∀i ∈ [m]. Due to the condition on α, the base case is true.Step: Under the assumption that all above induction hypotheses hold until some0 ≤ k ≤ K -1, we should prove they still should hold at k + 1-th induction. (a) We should prove that ∀t ∈ {T k-1 , • • • , T k -1}, the condition u t S + 2 -w ⋆ S + ∞ ≤ w ⋆ max 2 k and v t S - 2 -w ⋆ S - ∞ ≤ w ⋆ max 2 k still holds.If the condition is true for t-th iteration, then based on claims (c),(d), (e), (h) and (j) the ∥p t u ∥ ∞ in (51) under current induction step could be bounded asEQUATIONwhere the first inequality is due to definition of local RIP condition and Lemma 2 and Lemma 3, second inequality is due to hypothesis (a) holds at t-th iteration that u tS + 2 ∞ ≤ 2w ⋆ max , v t S - 2 ∞ ≤ 2w ⋆max , the last inequality is due to definitions of β, B k , step size condition and hypothesis thatu t S c ∞ , v t S c ∞ , u t S -∞ , v t S + ∞ would keep below√ α up to early stopping under hypothesis (h) and (j).The element-wise bound for q t u in (52) under current induction step can be bounded as follows that ∀j ∈ S + , there isEQUATIONwhere the first inequality is based on refined bound in hypothesis (c), result in (66) and inequality ∥x + y∥2 ∞ ≤ 2 ∥x∥ 2 ∞ + 2 ∥y∥ 2 ∞ and step size condition that 4βρ 3 4 ηB k < 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 α and definition of B k . Then q t u could be reparameterized as q t u = r t qu ⊙ u t S + where r t qu ∞ ≤ √ ρB k 32 , ∀t, T k-1 ≤ t < T k . Then the perturbed recursion for u t on positive support S + over decentralized network in (48) becomesEQUATIONwhere the new perturbed error terms E t 2s , E t 2s are defined asEQUATIONThen the total error terms in (68) can be bounded as followsEQUATIONwhere (i) is because of Lemma 2 and Lemma 3 under the global RIP condition and induction hypothesis (a) and substituting the results in (66) and (67). (ii) is due to condition on global RIP parameter that δEQUATION.(iii) is due to definition of ζ and (iv) is based on definition of K that ζ ≤ w ⋆ max 2 K-1 ≤ w ⋆ max 2 k-1 . (v) is because definition of B k and C γ , C b are determined later that are small enough that C γ + 2C b ≤ 1 80 .Based on iteration (68) and perturbation bound in (70), we would prove the u t+1S + 2 -w ⋆ S + ∞ ≤ w ⋆ max2 k 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 t S -. Combined two cases and induction on t, we have conclusion that ∀t ≥ T k-1 , there isEQUATIONThus, 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 2.(c) ∀t that T k-1 ≤ t < t + 1 < T k , based on one step iteration in (60) and induction (a), there isEQUATIONwhere (i) is due to the claim (a) and step size condition that4 ηB k ≤ 1 and δ ≤ δ max . (ii) is due to 4βρ 3 4 ηB k ≤ 1, condition that all u t S c ∞ , v t S c ∞ , u t S -∞ , v t S + ∞are not larger than √ α before early stopping in hypothesis (h), (j) andX T ξ N ∞ ≤ max i X T i ξ i n ∞ . The (iii) is because ρ 1 4 ≤ min    1 √ sδmax+1 , δ 8δmax , X T ξ N ∞ 8 maxi X T i ξ i n ∞    , α ≤ ϵ (12d+1) 2 and max X T ξ N ∞, ϵ ≤ w ⋆ max . The (iv) is because in the current induction step hypothesis (c) holds in t-th iteration and step size condition that satisfies η ≤EQUATION∞ ≤ 2w ⋆ max is according to claim (a). The last inequality (v) is based on the (68) and step size condition η ≤c10(1- √ ρ) w ⋆ max such that 4η u t S + 2 -w ⋆ S + ∞ + B k ≤ 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.(d) The proof is similar to that of hypothesis (c). ∀t that T k-1 ≤ t < t + 1 ≤ T k , according to one step iteration in (49) and hypothesis (a), we haveEQUATIONwhere the first two inequalities have the same reasons in (72). The third inequality is due to 16βρ (e) The proof is similar to hypothesis (d). ∀t that T k-1 ≤ t < t + 1 ≤ T k , based on one step iteration in (50) and hypothesis there is3 4 B k u t S + 2 ∞ + v t S -EQUATIONwhere the last inequality and the left proof have analogized derivations in proof of hypothesis (d).(f) To absorb the perturbed error q t u in (48), we need to prove the fine-grained bound for consensus error in hypotheses (c), (d), (d). The idea is that we focus on the ∀j ∈ S + , then the upper bound on the consensus error on j-th entry isEQUATIONEQUATIONwhere the last inequality is due to substituting the crude bound and analogous derivation in (72). Following the proof of crude bound would finish the proof. The proof for ∀j ∈ S -and ∀j ∈ S c can combine this proof with proofs of hypotheses (e) and (d), respectively. The fine-grained bound for v t can be proved by using analogous proofs for u t .(g) The proof can follow the proof of hypothesis (e) in Proposition 2 by replacing the S with S + . The proof of v t S -is analogous to u t S + .(h) ∀t that T k-1 ≤ t < t + 1 < T k . First, we bound the perturbation error ∥g t u ∥ ∞ , f t u ∞ in (50) induced from decentralized networkEQUATIONwhere the second inequality is substituting the upper bound in (66) and u t S + ∞ ≤ 2w ⋆ max due to hypothesis (a). ∀j ∈ S c , there isEQUATIONwhere 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 B k , the condition on ρ, and small initialization for α.Then f t u could be reparameterized asf t u = r t fu ⊙ u t S c , where r t fu ∞ ≤ √ ρB k 32 , ∀t that T k-1 ≤ t < T k .Then the perturbed recursion for u t on non-support S c over decentralized network in (50) becomesEQUATION)Thus, we can conduct similar calculation in (70) and obtain the upper boundE t 2s ∞ + E t 3s ∞ + ∥g t u ∥ ∞ + r t fu ∞ ≤ B k . Based on the step size condition that η ≤ c10(1- √ ρ) w ⋆ max, therefore there is a similar result in (35) asEQUATIONBased on recursion in (78), ∀k-th induction stage, we have the following upper boundEQUATIONwhere(i) is due to ∀x 1 , x 2 , • • • , x n ≥ 0, there is 1 + n i=1 x i ≤ n i=1 (1 + x i ), substituting the upper bound in (76) and definition of global RIP parameter. For (ii), we use T k ≤ 2T k based on definition of T k , T k , induction (a) with Lemma B.13 in [33] , step size condition, small initialization for α, definition of B k and refined upper bound for r t∞ as f t u ∞ ≤ ρ 3 4 √ sδ max B k + 32dα + max i X T i ξ i n ∞ u t S c ∞ . (iii) is because network connectivity con- dition that ρ ≤ min √ sδ √ sδmax+4 4 3 , ∥X T ξ∥ ∞ 8m maxi∥X T i ξ i ∥ ∞ . (iv), (v) are due to condition i ≤ K -1 and inequality 1 + K i=1 x i ≤ K i=1 (1 + x i that x 1 =, • • • , x K = 32ηC b ζ K . (vi) is based on the definition of K that ζ ≤ w ⋆ max 2 K-1 and condition that 4C b ≤ C γ .The last inequality results from the Lemma A.2 in [33] with upper bound is set asEQUATIONThus, we select universal constantC γ ≤ 1 1280 such that K×2 K-1 64ηCγ w ⋆ max log 1 α 4 ≥ 20K × T K-1, which would lead to the last inequality.(i) Concentrate on the iteration by DGD algorithm on support S, based on (57), we have the recursive formula asEQUATIONwhere the E t d1 , E t d2 , E t d3 and E t,i d4 are defined asEQUATIONFor the negative part v t , with similar decomposition in (57), there isEQUATIONAfter tedious calculation, its formula is as followsEQUATIONBased on induction (c) and (d), we can reparameterize ∆ t,i u,S and ∆ t,i v,S as ∆ t,i u,S = r t,i u,S ⊙ u t S and ∆ t,i v,S = r t,i v,S ⊙ v t S , where max r t,i 4 ηB k for T k-1 ≤ t < T k , Thus, the (82) and (85) can be reformulated asEQUATIONEQUATIONBased on hypotheses (a), (c)-(f), (j) and step size condition, we have the following bound for additional perturbed error termsEQUATIONwhere the last inequality is due to network connectivity condition that ρ ≤ min√ sδ √ sδmax+4 4 3 , ∥X T ξ∥ ∞ 8m maxi∥X T i ξ i ∥ ∞ .Then multiplying (86) and (87), we can obtain thatEQUATIONwhere the (i) is due to (88) and4η u t S 2 -v t S 2 -w ⋆ + E t d1 + E t d2 + E t d3 ∞ ≤ 1. The (ii)is due to induction (a) and Lemma B.13 in [33] . The reason for (iii) is the same as the that of last inequality in (80) because of the setting of step size.(j) Recall the recursive formula of u . With similar reparameterization as z t u = r t ⊙ u t S -, the (49) would becomeEQUATIONwhere the last inequality is due to the similar bound in (80).If τ < t, then unrolling (90) to τ -th iteration would haveEQUATIONEQUATIONwhere (i) is based on condition for initialization that α ≤ w ⋆ min 4and induction (h) thatu τ j ≤ α 3 2 v τ j ≤ α 3 2 √ -w ⋆ j ≤ α 2 .(ii) is based on the induction (a), step size condition that1 -4η -w ⋆ j -v τ j 2 + E τ 2s,j + E τ 3s,j + y τ s,j + r τ zs,j 2 ≤ 4 and ∀i > τ that v i j 2 < -w ⋆ jwhich is based on definition of τ . The last inequality has the same reason as (91).Based on the proof of hypothesis (a) in Proposition 3, we can conclude that ∀t ≥ T K , there would be max uT k-1 S + 2 -w ⋆ S + ∞ , v T k-1 S - 2 -w ⋆ S - ∞ ≤ w ⋆ max 2 K ≤ ζ,where the last inequality is due to the definition of K. The total computational complexity is the value ofT K-1 = 2 K -1 ηw ⋆ max log 1 α 4 = O 1 ηζ log 1 α . Due to the definition of ζ in the Theorem 1, if ζ ≥ w ⋆max , then our result holds at t = 0 based on the small initialization condition. When ζ ≤ w ⋆ max , we consider the two cases where the first case is the magnitudes of parameters is strong enough that ζ = 1 5 w ⋆ min ≥ 960ς, where the value 960 is due to under the condition2C b +C γ ≤ 1 80 , 4C b ≤ C γ , we set C b = 1 480 , C γ = 1 120, we can use run DGD T ′ 1 iterations to obtain the estimator max u • The answer NA means that the paper does not include theoretical results.EQUATION• All the theorems, formulas, and proofs in the paper should be numbered and crossreferenced. • 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 a 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.Justification:Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).38th Conference on Neural Information Processing Systems (NeurIPS 2024). 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: questions: none
limitations: limitations: none
paper_summary: paper_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.
strength_weakness: strength_weakness: 1.	The simulations are only for diagonal linear networks, which limits the generalizability of the proposed methods and theoretical conclusions. 
2.	Though 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.
questions: questions: 1.	Could you demonstrate your theoretical conclusions in more general architectures to further elaborate the implications of the theoretical claims?
2.	Previous works shows a transition from kernel regime to rich regime by varying the initialization scale, does such phenomenon exist in the DGD setting?
limitations: limitations: 1.	The motivation and implications of the theoretical claims are not clear.
2.	Numerical experiments are only conducted in simple architectures.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: questions: See weaknesses
limitations: limitations: yes.
paper_summary: paper_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.
strength_weakness: strength_weakness: This paper is a little bit technical.
questions: 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: limitations: Yes

Comments: title: Authors feedback
Increased ratings
Authors' feedback
Authors' feedback
comment: We sincerely appreciate your thoughtful review and raising your score. Thank you for providing us the opportunity to clarify our contributions. We will ensure that the numerical comparison results are included in the revised version of the paper.
Thanks for this detailed response and for putting your numerical experiments in more context.  I can bump my score up given this.
Dear Reviewer,

We apologize for the inconvenience, but we would greatly appreciate it if you could remind us where you have increased the rating in your review. Upon reviewing the feedback, we realized that we no longer have the details of the previous ratings and would like to ensure we have an accurate understanding.

Thank you for your time and assistance.

Bests,
Authors
Thank you for the feedback. We will add higher-level explanations to make the ideas clearer and more accessible.
Thank you for highlighting the weaknesses and for considering a slight increase in the rating.
Thank you for your response to my concerns. I have slightly increased my ratings.
Thank you for the detailed explanation. It helps but still seems a little technical to me. It would be better to present higher-level ideas instead of technical illustrations. Please consider adding them to the paper. I will maintain my score.