Recovering Exact Support in Federated lasso without Optimization
Authors: Adarsh Barik
Jean Honorio
Venue: Accepted by TMLR ()

Abstract: Federated learning provides a framework to address the challenges of distributed computing, data ownership, and privacy over a large number of distributed clients with low computational and communication capabilities. In this paper, we study the problem of learning the exact support of sparse linear regression in the federated learning setup. We provide a simple communication efficient algorithm that only needs one-shot communication with the centralized server to compute the exact support by majority voting. Our method does not require the clients to solve any optimization problem and thus, can be run on devices with low computational capabilities. Our method is naturally robust to the problems of client failure, model poisoning, and straggling clients. We formally prove that our method requires a number of samples per client that is polynomial with respect to the support size, but independent of the dimension of the problem. We require the number of distributed clients to be logarithmic in the dimension of the problem. For certain classes of predictor variables (e.g. mutually independent, correlated Gaussian, etc.), the overall sample complexity matches the optimal sample complexity of the non-federated centralized setting. Furthermore, our method is easy to implement and has an overall polynomial time complexity.

Published in Transactions on Machine Learning Research (01/2024)
Recovering Exact Support in Federated lasso without Optimization
Adarsh Barik
abarikOnus.edue edu..s
Institute of Data Science
National University of Singapore
Jean Honorio
jhonorio Gumnmell edu. an
School of Computing and Information Systems
The University of Melbourne
Reviewed on OpenReview: https: // openreview. net/ forum? id= S6y26KK122
Abstract
Federated learning provides framework to address the challenges of distributed computing, data ownership, and privacy over a large number of distributed clients with low computational and communication capabilities. In this paper, we study the problem of learning the exact support of sparse linear regression in the federated learning setup. We provide a simple communication efficient algorithm that only needs one-shot communication with the centralized server compute the exact support by majority voting. Our method does not require the clients to solve any optimization problem and thus, can be rum on devices with low computational capabilities. Our method is naturally robust to the problems of client failure, model poisoning, and straggling clients. We formally prove that number of samples per client that is polynomial with respect to the support size, but independent of the dimension of the problem. We require the nunber of distributed clients to be logarithmic in the dimension of the problem. For certain classes predictor variables (e.g. mutually independent, correlated Gaussian, etc.), the overall sample complexity matches the optimal sample complexity of the foderaedd centralized setting. Furthermore, our method is easy to implement. and has overall polynomial time complexity.
method requires
1 Introduction
Modern-day edge devices, with their data acquisition and storage ability, have pushed the need of distributed computing beyond the realms of data centers. Devices such as mobile phones, sensor systems in vehicles, wearable technology, and smart homes, within their limited storage and procossing capabilities, collect data and perform simple computations. However, due to data privacy concerns and limitations network bandwidth and power, it becomes impractical to transmit all the collected data to centralized server and conduct centralized training.
constantly
The nascent field of federated learning (Konečný et al., 2015; 2016; Brendan et al., 2017: Mohri et al., 2019; Li et al., 2020a) tries to address these concerns. As described by Konečný et al. (2016), foderated learning is a machine learning setting where the goal is train high-quality centralized model with training data distributed over large mumber of clients. Unlike the data centers, the clients collect data samples independently but in non-i..dd fashion. The clients may be highly unbalanced, Le., the number of samples per client may vary significantly. The clients may also have hardwarc-related constraints. Although the number of clients could be quile large, each client is lypically a simple device that has access to & very small mumber of data samples and can only conduct very basic computations due to limitations on its processing and power capabilitics. Furthermore, since battery power is at premium, the communication between the client and the centralized server acts as major bottleneck. Due to these constraints, is common encounter straggling and faulty clients in the federated learning setting.

---

Published in Transactions on Machine Learning Research (01/2024)
In this work, study the problem of exact support recovery of sparse linear regression in federated learning without solving any optimization problem. Support recovery in sparse models is of great importance in machine learning as it relates to feature selection. In our setting, none of the clients has the access to necessary number of data samples roquired for exact support recovery or possess computational capabilities to run complex algorithms. Furthermore, we only allow for one-shot communication between the clients and the centralized server, i.c., clients can send information to the centralized server only once. We propose a novel yet simple algorithm for this setting which uses majority voling and show that local clients can collaboratively recover the exact support of the sparse linear regression model with provable theoretical guarantees.
1.1 Related work
The problem of support recovery in sparse linear regression has been well studied for the centralized setting in compressive sensing (See e.g., Foucart & Rauhut, 2017 and references therein) and sparse regression (Sec e.g., Wainwright, 2009b and references therein). In compressive sensing, for independent sub-Gaussian predictors, (2s log d) samples are necessary for exact support recovery of a d-dimensional parameter vector with s non-zero entries. For sparse regression, Wainwright (2009b) provided the same lower bound for correlated Gaussian predictors. To the best of our knowledge, such a bound does not exist. for the general case of correlated sub- Gaussian predictors. In the federated setting, data is divided across multiple clients. We define the overall sample complexity in the federated setting as the summation of the sample complexity across all clients. Table 1 shows comparison of the overall sample complexity of our method in the federated setting to that of the tightest bounds available in the centralized setting running lasso.
ceemmation-theoreee
The federated learning framework has been used in many empirical studies (Konečný et al., 2015; 2016). As it inherently facilitates distributed computing, lends itself to be used in vast range of applications which include but are not limited to deep networks (Brendan et al., 2017), neural networks (Yurochkin al., 2019; Wang et al., 2020), principal component analysis (Grammenos et al., 2020) and fair resource allocation (Li et al., 2020b). There are also empirical studies that analyze adversarial attacks under the federated learning setting (Bhagoji et al., 2019). On the theoretical side, there are several application baacctttio-bbsedd algorithms that provide convergence rate guarantees. For example, He et al. (2018) provide convergence rate guaranteos for lincar classification and regression models, Smith et al. (2017b;a) provide similar guarantecs for lasso and multi-task learning respectively. Mohri et al. (2019) provide Rademacher-basel generalization bounds. Our estimation method at the clients looks similar to marginal regression (See Fan et al., 2008; Genovese et al., 2012 and the works that follow). However, compared to them, we focus on exact support recovery in the federated learning setup. Besides, our analysis and theoretical guarantees hold in the non-asymptotic setting. A detailed survey on the challenges and applications of federated learning can be found in McMahan et al. (2021) and Wang et al. (2021).
Table 1: Comparison of our overall sample complexity of support recovery in sparse regression in the federated setting with existing work in the centralized setting. Notation: 8 is the number of non-zero entries in the regression parameter vector and d is its dimension. The terms which are independent of s and d are not shown in the order notation.
Predictor type
Bound in the centralized sotting
Our bound
Mutually independent
( log d) (Wainwright, 2009b)
2(s log d). Theorem
Correlated Gaussian
((s log d) (Wainwright, 2009b)
Q log d), Appendix G
Correlated sub-Gaussian
Not Known
2(s² log log d), Theorem 2
1.2
Our contribution
All the works mentioned above are interesting in their own domain. The existing theoretical works provide guarantces for convergence rates (which guarantces a small mean squared error in the training set provided enough iterations) or generalization bounds (which guarantees a small mean squared error in the testing set provided enough samples). However, the final solution may not match exactly with the true parameter vector.
2

---

Published in Transactions on Machine Learning Research (01/2024)
In this work, we provide provable theoretical guarantees for the exact recovery of the support of the true sparse parameter vector of linear regression in federated learning. Support recovery, i.e., correctly detecting the zero and nonzero entries of the parameter vector, is arguably more challenging task. We show that for some special classes of predictor variables which include mutually independent or correlated Gaussian random variables, we can do exact support recovery with at least. 2(log d) clients and only ((s)) data samples per client. Notice that in this case, the overall sample complexity is ((ssogg)) which matches the optimal sample complexity of the centralized setting. We also provide novel theoretical results for a general class of correlated sub- Gaussian predictors where show that if the number of clients is at least Q2 d') and each client has access to at least 22s2 log data samples, then the support can be recovered exactly with high probability, We propose a simple yet effective method for exact support recovery and prove that the method is correct and efficient in lerms of lime and sample complexity. McMahan et al. (2021) and Wang et al. (2021) provided several key properties which make federated learning preferable over centralized systems. Our method fulfills many of these key properties:
No optimization low computation: We do not solve any optimization problem at the client level. All the computations are simple and let us use our method in devices with low computational power.
One shot communication and privacy: Our method is communication efficient. We only need one round communication of at most d-bits from the client to the centralized server. As communication is kept to a minimum, very little information about the client is passed to the centralized server.
Fault tolerance and aversion to model poisoning and straggling: Our method is naturally robust to client node failure and averse to rogue and straggling clients.
2 Notation and Problem Setup
In this section, we collect the notation which we use throughout this paper. We also formally define the support recovery problem for sparse linear regression in federated learning.
Let w* E Rd be a d-dimensional parameter with sparsity 8, i.e., only s out of d entries of w are non- zero. We use [r] as a shorthand notation to denote the set (1,2.-.-,r1) Let S* be the true support set, i.e., S* = fr/w of 0,r E [4]. We denole the corresponding complementary non-support set as St = [r|w;- = 0, [d]]. We will assume that minyeg* |w5| > w/ 0 and ||"l| < wh, The first condition is the well-known minimum weight condition (Wainwright, 2009b) which ensures that non-zero entries of w* are not arbitrarily close to zero which will make inference difficult for any method. The second condition can be written in terms of any no-norm where p > 1. We chose -orm to keep our analysis simple and clean. In federated learning, the data is divided across multiple clients. Assune that there are g clients, each with n; independent samples, for i E [g]. Note that the data distribution across g clients need not be identical. Each client i E [g] contains each data sample in the format (X,, y:) where X, E Rd are the predictor variables and y4 E IR is the response variable. The data generation process for each client i E [g] is as follows:
= XTTw +
(1)
where e is zero mean sub- Gaussian additive noise with variance proxy ni where ny 0. Note that all the clients share the same parameter vector w*. The j-th entry of X, is denoted by Xiz, Vi E [g], E [d]. Each entry X,y of X; is zero mean sub-Gaussin -o--ausssian random variable with variance praxy pf, where Ps > 0. We denote covariance matrix for X; as Σ' Bdxd with diagonal entries Σj, = (ofg)² Vie e [d] and non-diagonal entries Σj = oeke Vj,k k E [d].j * k. If predictor variables are mutually independent then ojx 0, Vi e jgl.j.ke E [d].j j * k. The t-th sample of the i-th client is denoted by (X, vf), Vi e [g]. [n.]] We note that X e Rd and of E R and denote j-th entry of X as X Notice that the data distributions for (X,, vi) can vary a lot across the clients by varying P: and 7h as well as the specific sub-Gaussian probability distribution. The class of sub-Gaussian variates includes for instance Gaussian variables, any bounded random variable (e.g., Bernoulli, multinomial, uniform), any random variable with strictly log-concave density, and any finite mixture of sub-Gaussian variables. Similarly, data samples can be distributed unevenly across the clients by
3

---

Published in Transactions on Machine Learning Research (01/2024)
varying n,. In subsequent sections, we use ((A) to denote the probability of the event A and B(A) denote the expectation of the random variable A. Figure la shows our setup and compares it with centralized server running lasso in Figure 1b. Notice how each client only sends a maximum of d bits to the centralized server in Figure la and maintains the confidnniilityy of locally collected data. This is unlike the centralized setting where the centralized server has access all the data.
Client
oxj x
Compute d1
Server rumning lasso
Support of tig
(x]
Client 2
(x) d
Compute dby
Centralized Server
Compute whsss by running lasso on all the data
Aggregate supports from clients and compute final support
(x)
Support of di2
Client g
Compute db
(C)) x
Support
Support of di
of Masss
(a)
(b)
(Left Ia) Support recovery in our federated sparse regression framework. (Right 1b) Support recovery in the centralized sparse regression framework using lasso.
Figure 1:
3 Problem Statement
For our problem, assume that each client has access to n; ols log samples, Ví E [g]. That is, the number of samples n, grows strictly slower than 8 llogd. Otherwise, the support can be trivially recovered by using compressed sensing methods in the client with n, O(s log d) which is the order of necessary and sufficient number of samples required for exact support recovery in linear regression setup (Wainwright, 2009a;b). Furthermore, we assume that each of our clients can only do very simple computations and can only do one-shot communication with the cent ralized server, i.e. each client can only send at most d-bits to the centralized server. Considering the above requirements, we are interested in answering the following question:
Problem Statement (Exact Support Recovery). Given that each client contains n, = o(s log d) data samples generated through the process described in equation (1), is it possible efficiently recover the true support of the s-sparse shared parameler vector = Rd by collecting d-bils of information from every client only once with provable theoretical guarantees.
The elficiency in exact recovery means that the sample complexity per client should be o(s log d) and that our algorithm should have polynomial time complexity and should also be easy to implement.
4 Our Method
In this section, we present a simple algorithm solve problem 1. Our main idea that estimation at the client level can be incorrect for every client but this information can still be aggregated in careful manner to compute the true support.
4.1 Client level computations
Each client tries to estimate the support = using n, independent samples available to it. As mentioned previously, n,, Vi [g] is not sufficient to compute correct support of w using any method possible (Wainwright, 2009a). Let de e Rd be the estimate of ** computed by each client i. Let S, = [fi # 0. e [d]] be the support of iú. Fach server communicates the computed support (at most d bits) to centralized
4

---

Published in Transactions on Machine Learning Research (01/2024)
server which then computes the final support of w*. The centralized server receives S; from each client and computes the final support S = f(Si, , Sg)- Fach client i, Vi E [g] computes ú; in the following way:
Vi [g e [d]. Dij sign( (áxx(0 Aag):
özj
where Biy is j-th entry of ú; and by > a regularization parameter. While it possible to compute a feasible Aij for each client and entry j, we will present a more practical choice of a single Xi = across all clients and entries. Moreover, computing ōzj is not required to estimate the support but we keep all the terms in equation for clarity and completion. We define ōij and dij follows:
R2 T1
dij
(x))
6i
X
(3)
These are simple calculations and can be done in O(dn,) run time at each client. If n, can be kept small (which we will show later), this can be done even by a device with low computational ability. The choice of this exact form of diy in equation (2) is not arbitrary. To get the intuition behind our choice, consider the following f1-regularized (sparse) lincar regression problem at each client.
1 or The
(Vi [g]), de = arg min
Σ
( - w/)² Iw.
(4)
where || I/ denotes the & norm of vector and @ denotes the Hadamard product between vectors. The j-th entry of the regularizer vector A E Rd is Xıg. We can write equation (4) in expanded form as:
1 Ths
(15
(1 mh
d
(Vi [gl), ai = arg min T 60
XXXXT
w 2w
X
(5)
Now, we intentionally replace >"_ X with diag(>> X(X(T). This allows us to write equation (5) as sum of d independent optimization problems:
T1e 74
(Vi [9]), w. arg min Σ
wj
Σ
Wj
x
Σ X Kylwyy
(6)
T4e
and subsequently, we get equation (2) as the solution. This is an improper estimator that has the advantage of working well when there are very few samples, i.c., n, = O(1) with respect to dimension d. It is known that estimating the covariance as needed in the mean squared error requires n; in O(log d) (See Lemma in Ravikumar et al., 2011). Our simple estimator avoids any computation (or estimation) of the covariance matrix which, in any case, would be incorrect if cach client has access only a few samples. Each client sends the support S, of à; to the centralized server. Even in the worst-case scenario, each client only sends d bits to the centralized server.
4.2 Information aggregation and constructing the final support
We aggregate supports S,, Vi [g] from all the clients and construct the final support. Before get to the construction of the final support, define random variable Rej, Vi [ø].j [d] which takes value 1 if j e S; and 0 otherwise. Thus, random variable Rij indicates whether entry j is in the support S; of client i. Using the random variables Rij, we construct the final support S using majority voting. This is done by computing the median of Ry across i [g]. If the median is then we conclude that j is in the support otherwise we conclude that j not in the support. More formally, we define a random variable R
9 - R, and R, > 2, then we conchude that j S. Otherwise, if R < 1. then we conclude that $ S. The above procedure be compactly written Algorithm 1.
1
5

---

Published in Transactions on Machine Learning Research (01/2024)
(Part I: Runs in client 1, Vi [0]]
Input: Data samples (X), v() = [m:]]
(Part II: Runs in centralized server)
Output: Locally estimated support of shared pa-
Input: Rig, Vi e [g],] [d]
rameter w
Output: Globally estimated support for shared
for each j E [4] do Compute By using equation (2) and (3)
parameter u²*
S - 0
if db3 * then
for each j [d] do
H. 1
Compute R = Ei=
Rig
else
if R 2 then
Rig -0 end if end for Send R, to centralized server, Vj e [d]
S - Su end end for Algorithm 1: getExactSupport
5 Main Result and Analysis
In this section, describe and analyze our theoretical results. We present results in two different settings. In the first setting, we assume that predictor variables are mutually independent. We tackle the more general case of correlated predictors in the second setting. We deal with the special case of correlated Gaussian predictors in Appendix G. Detailed proofs for lemmas and theorems are available in the supplementary material.
5.1 Mutually independent predictors
In this setting, predictor variables are mutually independent of each other all the clients, ie., Vi e [g], Xix) 0, Vj, k E [d]. k. In this setting, state the following result:
Theorem 1 (Mutually Independent Predictors). For federated support learning in linear regression, as described in Section with least g 22llgg d) clients and matually independent predictor variables if each client has at least n4 (2(s) i.i.d. data samples and the following condition holds:
C (8|w5 lot 8pp
max [
Sp²
Σ kES
x2 wk + Simpel
<λ<
min jes* (t(a)] (u)(o)
v8
(7)
Σ KESt kサj
x2 w
2
+
8)Pppel
where C O absolule constand independent. of n,; 8 and then Algorithm 1 recovers the exacl support of the shared parameter vector w* with probability at least 1 - O()).
Proof. Recall that RN = - Σi Ri where Ri is defined Section 4.2. We prove that, with high probability, Rý Vje S* and R2 1 Vjj E St. We will provide the proof in two parts. First, we deal with entries ý which are in the support of w* ie., j S* and then will deal with j St.
R-
For entries j in support S*h We begin our proof by first stating the following lemma.
Lemma 1. For Vj E S*, let E(R)) simultancously Vj e S*
> 1 2.
With probability at least 2exp( -app--2g((t)) + E(RR))² + log s),
we we have R3 >
For = O(log d), Lemma 1 holds with probability at least 1 - Old). Next we show that for any j E S* E (RR) is indoed greater than 2.

---

Published in Transactions on Machine Learning Research (01/2024)
Lemma 2. For [g]. j S* and some 0 < 8 1, if predictors matually independent of each
other and 0 < Aij lwf (1t,) w/w |p 8p? / bes w Pi7 then have E B(Rg) 1 6 g -i=1 nx,6)),
In the above lemma, we assume (ot,)²² 0 for all e [g] for clarity of exposition. In a more general setting, since (ot,)) > 0 is the population covariance, it would easy to detect which clients i have oj, 0 through the empirical covariance, which would also be zero. Assuming that the proportion of clients for which oj = 0 is not too big, one could trivially extend our lemmna above by using only the clients for which (o),) "+²))²= 0.
For entries j in non-support S. Similar to the entries in the support, begin this part by stating the following result for entries in the non-support.
Lemma 3. For Vj E St, let B(RR) < 1 simultaneously Vj E Se, we have R₃ <
With probability at least - 2exp( (oxp((22(( ({())))² + log(d (d - -)),
Again, if g [[log d), then Lemma 3 holds with probability least - O()). It remains to show that for
Vj 5 B(R,) is smaller than 2- In particular, we use the result from the following lemma.
Lemma 4. For E [g], j St and 0 < ê & 1, if prediclors are mutuully independent of each other and if Xiy > /6p; Skes w 8/m, then we have B(R)) & 1 -. exp(-n,8²).
2
It is important to note that the statements of Lemuna 2 and Lemina 4 are not high probability statements and therefore, a union bound not required for them. We notice that as long as 4 _i_1 exp(-n,62) }. then Vj S B(R)) < 1- Similarly, Vj S* B(Rg)) > as long as I -i_ exp(-n.00) & 1.2 Results from Lemma and guarantce that the statements of Lemma 1 and 3 hold. Choosing n, = 22 ).) and C C > 0, we v
prove Theorem 1.
5.2 Correlated predictors
The concentration inequalities used in mutually independent predictors do not lend themselves directly to the correlated predictors case which makes this analysis more challenging, As described previously, the covariance matrix for X; is denoted by E E ddxd with diagonal entries Σj = (o) ). Vjj E [d] and non-diagonal entries 2/,, dee Vj, k [ k. While some of the lemmas from the previous subsection can be reused, we had to come up with some new technical lemmas for this setting, Below, state the main results for this setting.
Theorem 2 (Correlated Predictors). For federated support learning in linear regression, as described in Section 3, with at least = 2(log d) clients and correlated predictor variables, if each client has n, = s( log 8), 8 d. data samples and the following condition holds:
C
p (ot
max jeSt ge(gl
Σ u K
w
Σ
8 2V2
4 max
max (otn)² + 8|mpsl <><
KES
3
3
min (ela)
Σ
C w
8lwflo?
Σ
8v2 |
maxx
(8)
KESe R
8
ke ket
(ofa)
max (0 8/mppa)
where C > O is an absolute constant independent of n,, 8 and d, then Algorithm 1 recovers the exact support of the shared parameter vector x* with probability lenst 1 1))))).
Proof. Recall that Rg- = - Rij where Rig is defined in Section 4.2. We will again prove that, with high probability, R2 2 1, Vjj S* and R2 Vj St. Some of the results from the previous Section 5.1 follow
7

---

2 Published in Transactions on Machine Learning Research (01/2024)
without any changes. We provide new results for the remaining parts. First, we deal with entries j which are in the support of w*, i.e., j E 5 and then we will deal with j S
For entries j in support st We observe that Lemma 1 holds even in this case. Thus, we start proof by stating the following lemma.
Lemma 5. For i E [g]. E S* and some 0 <
w w max; (oj,)² s/mpi/0 then we have B(Rj) >
1 if < xi < ((0z(ott))) + Ekes+ kej
V2
8/03] 1pf6 Exes* Aty 8V 8v2/w/](1 4 max, p 4s E exp(-n,07
For entries j in non-support S. Again, Lemma 4 follows directly. Thus, we present the following lemma to show that for the entries in the non-support [E(R)) < 2
Lemma 6. For E [g]. j E S and some 0 8
of Xig > Ekess wRajal + Ekes 8/2/w02(11 + V2'
4 max, (o) 3 max, (of,) 2 + 8)mppl0 then we have B(R;)
4s+2
g Σi=1 exp(-n,63).
The statements of Lemma 5 and Lemma 6 are not high probability statements and therefore, a union bound is not required for them. Note that, as long as we have (4s + 2) Σy_ exp(-n.6 < 1 2, we will have
E(R,) > 2. Vjj E S* and B(Ry) 2. Vij S Results from Lemmas 5 and 6 ensure that Lemma 1 and 3 hold. Choosing n, = 2 oo log 8) and d = C C > O, we prove Theorem 2.
5.3 Time complexity
Each client does O(dn,) basic calculations. Thus, the time complexity at each client is O(sd) for mutually independent predictors and Olsddoog s) for correlated predictors. The centralized server gathers d-bits of information from clients in (dd)) = Old d) time.
6 Choice of Regularizer
The conditions mentioned in Equations (7) and (8) provide sufficient theoretical conditions on the regularizers Xi > for exact support recovery. It remains to be shown whether such choice of X is feasible. If we let minjes+ oj = then it can be shown that equation (7) has a feasible solution as long as we choose w²o; a C such that C 10pf""/st8u" 16 This setting of X in equation (7) can be contrasted with the setting of the regularizer Aiasso of a contralized-sene server lasso problem in Theorem of Wainwright (2009b). particular, the lower bound on X, ((1) O
Vuz ), is analogous the lower bound on the renteeeeeeee
lasso regularizer Aassso i.c., Alssso > O(1 2 n.
However, our choice of X is independent of d. In Section 8, we empirically validate the existence of a feasible range for X. A similar analysis can be carried out for the fcasibility of equation (8). Let MAB E [|A be a matrix constructed by restricting rows of M to entries in A and columns of M to entries in B for two sets A, B = [d]. Furthermore, for a matrix M IRx4, let |M + max Eye[g| [M.l We assume that 1 5e lle + 50 s lla < for some constant y We >
logd
further assume that is so small such that w/ - 0. This assumption is similar to the incoherence assumption in Wainwright (2009b) and it ensures that predictors within the support are not highly correlated, as well as predictors outside the support do not exert a high influence on the predictors within the support. o max, (ot,)² by positive constant ks-
For ease of notation, we will denote the term (1 max, [ot.)²
w'of²-wan
We observe that
16. 2kys+88 of 16mp: then the choice of X in equation (8) feasible. Notice how the upper bound X w'o!² why is similar to a combination of the minimum weight condition and the incoherence condition from Wainwright (2009b). Similarly, the lower bound À > O(1) + Oly logs) is analogous to the setting of the centralized- lasso regularizer in Wainwright (2009b). We provide the
8

---

Published in Transactions on Machine Learning Research (01/2024)
following illustrative example to explain the similarity between technical conditions required for the feasibility of equation (8) and the standard mutual incoherence condition.
6.1 An illustrative example
Consider the data generation process given in equation (1), ie., y= X" +e. We have dropped the subscript i for brevity as the following argument holds for any client i E [g]. We take d = 3, the paramcter
vector w E R looks like w
where a > 0, i.e. S = (1,2) and S (3)- We assume that entries of
the design matrix X5 are in 1-1, 1444 1,2,3. Furthermore, let [(X,X22) B(X2Xs) p. E(X)x;) 0, E((1)) and IE (Xx)) 0, where E(() denotes the expected value.
X1
Let Σ be E(X*x) where X =
X2
E {1-1.13 Then,
X3
1 q q 1 0
0
Σ
Thus, the feasibility criteria for À in equation (8) becomes: |wfa3i + uh A(we, AweeE,,py p, c min([wfof i + wr + B(w= p, n), ( + w 021l + (.,,,),,,)))
where A(w*, Σ. p. p) Bww*, E, p. 1) and D(w*, Σ, p. n)) are upper bounded by ((s) and thus these products can be made arbitrarily small by choosing appropriate C. In the worst-case scenario, the above equation becomes (by replacing w* and E):
alpl < - algl + Elw", E, p. C
Again, E(w*, E, p. _ can be made arbitrarily small by choosing an appropriate C. The above feasibility criteria simplifies to
Ip + lgl < +
(9)
where c is an arbitrarily small quantity. We compare this with the mutual incoherence condition from Wain- wright (2009b) which requires [E Egtgs lo & a, for some a E (0, 1]. This simplifies to
10
1 q 1
p
<
which is equivalent to
|pl + l4l < 1.
(10)
Notice how for small values of p and q (say p == 0.2, == 0.1) both equation (9) and (10) are easy satisfy while for the high value of p and (say p 0.7, g 0.6) both conditions fail to hold.
7 Discussion on Robustness
Since our method only relies on the correct calculation of the median, it is naturally robust the failure of some clients. To simulate the effect of model poisoning (Bhagoji et al., 2019) and staggle,ss, consider that

---

Published in Transactions on Machine Learning Research (01/2024)
proportion 3 2 of clients have gone rogue (are straggling) and transmitting the wrong information to the centralized server. For the worst-case scenario, we assume that they report the complement of the support, i.e., they always send bit "1" for entries in the non-support and a bit "0" for entries in the support. To accommodate this change in the case of correlated predictors, we slightly change statements of Lemmas 5 and 6. Now we have, (Vj ) B(R;) > (1 - (3) 4s (11-)) exp(-n;5* and (vj E S E(R;) &
4s+2 D(L-0) 9 -i=1 exp(-n,00) 3. It is easy to that, long as, have per client, then we still have R(R)) > 1.2 Vj E S and B(R2) < 21 Vj E S and all our results still hold. Similarly, for mutually independent predictors, our results hold as long as we have ni > 5 log( 12(1-8) T-23
x² log( (8++1((1-)) data samples 1-28
8 Validating Theory with Synthetic Experiments
In this section, we validate our theoretical results by conducting computational experiments.
We provide the results for the experiments when predictors are correlated. Data in each client is generated by following the generative process described in equation 1. Note that predictors and error term in diffcrent clients follow different sub-Gaussian distributions. To make it more general, we keep the correlation between entries in the support different than the correlation between one entry in the support and the other entry in the non-support and these further vary across clients. The regularization parameter X; for each client is chosen such that the condition in Theorem is satisfied for every client. All the results reported here are averaged over 30 independent runs. We conduct two separate experiments to verify that n, lss log s) independent samples per client and total of (2(log d) clients are sufficient to recover the true support.
1.0
Mean Exact suppert Recovery
Mean Exact support Recovery
0.8
0.8
0.6
0.6
0.4
0.4
s= 10
0.2
5=000
0.2
20
d= 1000
40
d=2000
0.0
50
10
20
30
40
50
10
20
30
40
50
60
70
Number of Samples Per Client
Number of Clients
(a) Exact support recovery against numbers of samples per client
(b) Exact support recovery against numbers of clients
Figure Phase transition curves. Left: Exact support recovery averaged across 30 runs against. varying number samples per client for dimension d 500, 1000, and 2000, sparsity 3, g 2(log d) clients. Right: Exact support recovery averaged across 30 runs against varying number of clients for sparsity 10, 20, 40, and 50, dimension d 1000, max(30, ((s log samples per server.
8.1 Exact support recovery against number of samples per client
This experiment conducted for varying number of predictors (d= 500, 1000, and 2000). For each of them, we fixed the number of clients to be = 2 2og d. The sparsity is kept fixed at 3. The number of samples per client n, is varied with control parameter C as 10 log The performance of our method is measured by assigning a value for exact recovery and otherwise. We can see in Figure 2a, that initially, recovery remains at and then there a sharp jump after which recovery becomes 1. Notice how all three curves align perfectly. This validates the result of our theorem and shows that given g 2(log d) clients, n; = ss² log s) samples per client sufficient to recover the true support.
10

---

Published in Transactions on Machine Learning Research (01/2024)
8.2 Exact support recovery against number of clients
The second experiment conducted for varying number of non-zero entries (s 10, 20, 40, and 50) in the support of w*. The experiments were run for setup with d = 1000 predictors. We fixed the number of samples per client (n:) to be max(30, log This ensures that minimum of 30 samples are available to each client. This inline with our previous experiment where exact recovery is achieved around 30 samples per client. The number of clients is varied with control parameter C' as 10 log Like the previous experiment, performance is measured by assigning value 1 for exact recovery and 0 otherwise. We can again see in Figure 2b, that initially, recovery remains at 0 and then it goes to we increase the number of clients. We also notice that all four curves align nicely. This validates that given nę (2ss log 8) independent. samples per server, g Q(log d) clients are sufficient to recover the true support.
8.3 Robustness to straggling clients
Recall that since our method only relies on the correct calculation of the median, it is naturally robust to the failure of some clients. Our next experiment simulates the effect of having a proportion < B < of straggling clients which transmit the wrong information to the centralized server. For the worst-case scenario, we assume that they report the complement of the support, iee, they always send bit "1" for entries in the non-support and bit "0" for entries in the support. Table 2 shows that our method is robust for proportion 0 < B < 0.3 of straggling clients.
Table Exact support recovery averaged across 30 runs for different proportions / of straggging clients for dimension d 1000, sparsity 3, g ((log d) clients, n, = s2(s log s) samples per client.
B
0.10
0.20
0.30
0.35
0.40
Mean exact support recovery 100%
100%
100%
80%
33%
8.4 Comparison with centralized lasso
We compared our method the centralized lasso Wainwright (2009b), which has access to all the data, unlike our method. Table 3 shows that both our method and centralized-sserer lasso successful in recovering the true support, but method requires less computation.
Table Exact support recovery and runtime averaged across 30 runs for dimension d d= 500, 1000, and 2000, sparsity s == 3, g 12(log d) clients, n, {2 log s) samples per client. For easy comparison, runtime was normalized with respect to our method for d 500.
Mean exact support recovery
Mean runtime
Our method Centralized lasso
Our method
Centralized lasso
500
100%
100%
1
4.1
1000
100%
100%
2.4
11.6
2000
100%
100%
4.6
26.7
9 Real World Experiment
In this section, we demonstrate the effectiveness of our method to determinc the support of sparse lincar regression selup in a real world data set. We used the BlogFeedback data set (Buza, K., 2014) from https://archive ics. uci.
This data set contains features extracted from blog posts and the task is to predict how many comments the post will receive using these features. We divided data into training and test data by choosing 80% of all samples be training data at random. The details about the data set as follows:
11

---

Published in Transactions on Machine Learning Research (01/2024)
Number of training samples: 41917
Number of test samples: 10480
Number of features (after removing all zeros columns): 276
9.1 Comparing recovered support with centralized lasso
Since the true support of the parameter vector is unknown for real-world data, we constructed a "centralized" support for comparison by running lasso on the complete training data set. This simulates a centralized server with access to all the data. The "centralized" support contains 42 elements. We want to compare the support recovered from our method, called "federated" support, with this 'centralized' support.
9.2 Performance measures
We defined the following performance measure for comparison:
Jaceard Index
Number of common elements in the "federated" support and in the "centralized" support Number of elements in the union of "centralized" support and "federated" support
(11)
9.3
Case 1
For the first experiment, we divided the dataset randomly into 419 clients with each client containing 100 samples (except the last one which contains more to account for imbalance). This is highly distributed sctting where each client has access to small number of samples. We conducted our experiment using À 0.08. Our method recovered support with 48 elements, with Jaccard Index of 0.76.
To compare the generalization on the test data set, we computed parameter vectors Wied and Woen by running simple linear regression on training samples restricted to "fedcrated" support and "centralized" support respectively. After that, Mean Square Error (MSE) computed on the test samples using the recovered Wied and Wenn- We observed that MSE for our method, 0.71545, is slightly better than MSE for "centralized" support, 0.71615.
9.4
Case 2
For the second experiment, we divided the dataset randomly into clients with each client containing 1000 samples (except the last one which contains more to account for imbalance). This is setting where we have only few clients. We again conducted our experiment using 0.08. Our method recovered support with 49 elements, with Jaccard Index of 0.8.
Again, we followed the same procedure as Case 1 to compute MSE in test samples. We observed that MSE for our method, 0.70525, is slightly better than MSE for "centralized" support, 0.70548.
We see that in both cases, our method recovered a similar set of support as the support recovered by lasso rumning in centralized server. Our method also generalizes the test dataset in similar manner, even performing better in terms of MSF.
Table 4: Jaccard index for different regularizer values X.
0.04
0.06
0.08
0.10
0.12
0.14
0.16
0.18
0.20
Case 1
0.46
0.83
0.76
0.73
0.76
0.77
0.63
0.53
0.42
Case 2
0.56
0.71
0.80
0.82
0.75
0.78
0.83
0.74
0.76
12

---

Published in Transactions on Machine Learning Research (01/2024)
9.5
Robustness to the choice of regularizer
To evaluate the robustness of our method to the choice of regularizer A, we tested range of regularizer values in the real-world data. Table 4 shows that our method is relatively robust in a wide range of regularizer values (i.e., 0.06 < À & 0.14).
10 Concluding Remark
In this paper, we propose simple and casy-to-implemenn method for learning the exact support of parameter vector of linear regression problem in a federated learning setup. We provide theoretical guarantees for the correctness of our method. We also show that our method runs in polynomial sample and time complexity. Furthermore, our method is averse to client failures, model poisoning, and straggling clients.
As future direction, would be interesting to apply our ideas to other estimation problems involving sparse regression such non-parametric regression (Ravikumar et al., 2007), learning probabilistic graphical models (Ravikumar et al., 2010) and diff'usion networks (Daneshmand el al., 2014). These problems are oflen handled in the centralized setting but it would be interesting to tackle them in the federated setting without compromising on the performance.
References
Bhagoji, A. N., Chakraborty, S., Mittal, P., and Calo, S. Analyzing federated learning through adversarial lens. International Conference on Machine Learning, 2019.
Brendan, M. H., Eider, M., Daniel, R., Seth, H., and y Arcas Blaise, A. Communication-cffin learning of deep networks from decentralized data. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS), 2017.
Foucart, S. and Rauhut, H. mathematical introduction to compressive sensing. Bull Am. Math, 54(2017): 151 165, 2017.
He, L., Bian, A., and Jaggi, M. Cola: Decentralized lincar learning. In Advances in Neural Information Processing Systems, pp.
2018.
Koneōný, J., McMahan, B., and Ramage, D. Federated optimizattinn Distributed optimization beyond the datacenter. Neural Information Processing Systems, Workshop on Optimization for Machine Learning, 2015.
Konečný, J., McMahan, H. B., Yu, X., Richtárik, P., Suresh, A. T., and Bacon, D. Federated learning: Strategics for improving communication efficiency. Neural Information Processing Systems, Workshop on Private Multi- Party Machine Learning, 2016.
Li, T., Sahu, A. K., Talwalkar, A., and Smith, V. Federated learning: Challenges, methods, and future directions. IEEE Signal Processing Magazine, 37(3):50-60, 2020a.
Li, T., Sanjabi, M., and Smith, V. Fair resource allocation in federated learning. International Conference on Learning Representations, ICLR, 2020b.
McDiarmid, C. On the method of bounded differences. Surveys in combinatorics, 141(1):148-188, 1989.
Mohri, M., Sivek, G., and Suresh, A. T. Agnostic federated learning. International Conference on Machine Learning, 2019.
Ravikumar, P., Wainwright, M. J., Raskutti, G., Yu, B., et al. High-dimensional covariance estimation by minimizing 11-penalized log-determinant divergence. Electronic Journal of Slatistics, 5:935 980, 2011.
Smith, V., Chiang, C.-K., Sanjabi, M., and Talwalkar, A. S. Federated multi-task learning. Advonces in Newral Information Processing Systems, pp. 4424 4424-443,, 2017a.
13

---

Published in Transactions on Machine Learning Research (01/2024)
Smith, V., Forte, S., Ma, C., Takáč, M., Jordan, M. L., and Jaggi, M. Cocoa: A general framework for communication-effiiee distributed optimization. The Journal of Machine Learning Research, 18(1): 8590 8638, 2017b.
Wainwright, M. Chapter 2: Basic tail and concentration bounds, 2015.
Wainwright, M. J. Information-theoreiis bounds on sparsity recovery in the high-dimensional and noisy setting. IEEE Trons. Info. Theory, 55:5728 5741, December 2009a.
Wainwright, M. J. Sharp thresholds for high-dimensional and noisy sparsity recovery using 11-constrained quadratic programming (lasso). IEEE transactions on information theory, 55(5):2183 2202, 2009b.
Wang, H., Yurochkin, M., Sun, Y., Papailiopoulos, D., and Khazaeni, Y. Federated learning with matched averaging. International Conference Learning Representations, ICLR, 2020.
Yurochkin, M., Agarwal, M., Ghosh, S., Greenewald, K., Hoang, T. N., and Khazaeni, Y. Bayesian nopparametric lederated learning of neural networks. International Conference on Machine Learning, 2019.
Grammenos, A., Mentoza-Smith, R., Mascolo, C., and Crowcroft, J. Federated Principal Component Analysis. Neural Information Processing Systems, 2020.
Hsu, Daniel and Kakade, Sham and Zhang, Tong A tail inequality for quadratic forms of subgaussian random vectors. Electronic Communications in Probability, 2012.
Buza, Krisstian Feedback prediction for blogs. Data analysis, machine learning and knowledge discovery, Springer, 2014.
Daneshmand, H., GodezzRodriguez, M., Song, L., and Schoelkopf, B. Estimating Diffussio Network Structures: Recovery Conditions, Sample Complexity & hoit-hhresholing Algorithm. In International Conference on Machine Learning, pp. 793 801, 2014.
Ravikumar, P., Liu, H., Lafferty, J., and Wasserman, L. Spam: Sparse Additive Models. In Proceedings of the 20th International Conference on Neural Information Processing Systems, pp. 1201-1208. Curran Associates Inc., 2007.
Ravikumar, P., Wainwright, M. J., Lafferty, J. D.,, et al. High-dimensional ising model selection using 11-regularized logistic regression. The Annals of Statistics, 38(3):1287-1319, 2010.
McMahan, H Brendan and others Advances and open problems federated learning. Foundations and TrendsM in Machine Learning, 2021.
Wang, Jianyu and Charles, Zachary and Xu, Zheng and Joshi, Gauri and McMahan, Brendan and Al-Shedivat, Maruan and Andrew, Galen and Avestimehr, Salman and Daly, Katharine and Data, Deepesh and others field guide to federated optimization. arXio preprint Nii:2107.066 2021.
Genovese, Christopher R and Jin, Jiashun and Wasserman, Larry and Yao, Zhigang A comparison of the lasso and marginal regression. The Journal of Machine Learning Research, 2012.
Fan, Jianqing and Lv, Jinchi Sure independence screening for ultrahigh dimensional feature space. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 2008
14


Reviews:
[{"review_id": "hgo3LYDBjU", "reviewer": "Reviewer_pN2B", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The work proposes a novel and simple method for exact support recovery of sparse linear regression in the federated learning setup, which does not require any optimization problem or complex computation at the client level.\n2. The work provides provable theoretical guarantees for the sample complexity and time complexity of the proposed method and shows that it matches or improves the optimal bounds of the centralized setting for some classes of predictor variables.\n\nWeaknesses:\n\n1. My main concern is that it seems from (7) and (8) that we need to know the true $w*$, $\\sigma$ and $\\rho$ to choose a regularization parameter $\\lambda$ such that the solution satisfies the theoretical guarantees but in practice we will not know $w^{*}, \\sigma, \\rho$. Moreover even in the experiments $\\lambda$ is set to 0.08 without any justification for how it is chosen. Please provide some explanation/heuristic that can be used to choose $\\lambda$ in practice or provide an ablation study illustrating the effect of varying $\\lambda$ on the solution so that we can see the consequences of choosing a \"bad\" $\\lambda$.\n\n2. I have a similar concern for the discussion on robustness in Section 7 where it seems like we will need to know the portion $\\beta$ of clients that have gone rogue to know if we have sufficient $n_i$ to trust our output. Is it realistic to assume that we will know $\\beta$ beforehand?\n\n3. There are no experiments showing that the method is indeed robust to client failures, data poisoning or straggling even though Section 7 claims that it will be robust to these issues. I would recommend adding an experiment for at least one of these scenarios to strengthen the claims in Section 7.\n\n4. There are also no comparisons with other federated LASSO approaches such as Smith et al. (2017b; a) from Section 1.1. Even if none of them consider support recovery explicitly, I would suggest comparing with the support of the LASSO solution to illustrate the accuracy and computational efficiency of the proposed approach over baselines.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a novel method for learning the exact support of a sparse linear regression model in a federated learning setting, where the data is distributed across multiple clients with low computational and communication capabilities. The method does not require the clients to solve any optimization problem or estimate the covariance matrix, but only uses simple calculations and one-shot communication of d bits to the centralized server. The support is estimated at the central node using majority voting and the authors provide theoretical guarantees for the exact support recovery under various conditions on the number of clients, the number of samples per client, the sparsity level, and the regularization parameter. \n\nThe method is potentially robust to client failures, model poisoning, and straggling clients, and can handle different classes of predictor variables, such as mutually independent, correlated Gaussian, or correlated sub-Gaussian. The paper also demonstrates the effectiveness of the method on synthetic and real-world datasets and shows that it can recover a similar or better support than the centralized lasso estimator without needing to aggregate all the data at the central node.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "In addition to addressing the points highlighted under weaknesses above I would also recommend illustrating some real-world applications and benefits of accurate support recovery in the introduction of the paper to illustrate the importance of the problem being solved since currently that may not be clear to a reader unfamiliar with the other literature in this place.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "rVN430bGER", "reviewer": "Reviewer_w6rm", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "1. The writing is good. It is easy to follow. \n\n2. This paper provides a theoretical analysis for the federated lasso problem.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper enables federated learning for the LASSO problem. In particular, it shows how to optimize this model and provides theoretical analysis for the convergence rates and statistical bounds.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "No", "audience_explanation": "", "requested_changes": "1. This paper claims the proposed algorithm has no optimization for finding the optimal solution. This is not true. In fact, it uses the soft-thresholding approach to solve the lasso problem. Thus, it overclaims the contribution. \n\n2. The proposed algorithm is weird. It seems there is only one iteration. However, the standard soft-thresholding approach is an iterative approach, which requires many iterations. Why does the proposed algorithm just need one iteration?\n\n3. What unique challenges are there in the theoretical analysis compared with standard lasso problems?", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "pTJ3scNqvw", "reviewer": "Reviewer_y1zc", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper presents a new distributed algorithm for LASSO in the federated setting. The main point I take away from this paper is that the algorithm is computationally very efficient and has a very small communication footprint (only requiring a one-shot transmission of a support). I think the results in the paper are interesting, both to the federated learning community, as well as for designing better algorithms for LASSO, as the algorithm can be run as a parallel algorithm on $\\log(d)$ threads on a single server to solve the LASSO problem. It would be very interesting to add in a section in the paper comparing the computational cost of this algorithm with other state-of-the-art fast algorithms for LASSO in the centralized setting. The communication footprint of the algorithm is very small, and I believe the analysis can be improved since each user returns a support size which is also $\\widetilde{O} (s)$ with high probability (requires a proof), in which case, the support of each user can be communicated in $\\widetilde{O} (s \\log(d))$ bits by transmitting their locations. I believe this should be asymptotically optimal. Since the algorithm aggregates the individual supports by a majority rule, existing approaches can be used to show that the algorithm is robust to stragglers, as the authors show. This is nice, as in the federated setting, individual devices may drop in and out of the network, and may be subject to differing latencies (stragglers), or be malicious.\n\nIn general, looking at the analysis in the paper for the uncorrelated case, it appears that as long as $\\sigma_{jj}^i$ is not too small for any $(i,j)$, and $w_i$ is not too small, by choosing a sufficiently small value of $\\delta$, the algorithm's correctness can be established.\nHowever, in this case, it is confusing to me why the algorithm fails when $\\sigma_{jj}^i = 0$ for some $i$. In this case, even though the support is not-identifiable from the data present with user $i$, since this user's data cannot be used to tell whether $w_j$ is or isn't $0$, the presence of other users with $\\sigma_{jj}^i \\ne 0$ should allow the support to be identifiable. I believe that the current algorithm should still succeed in this case, and this follows from the same reasons that the algorithm is robust. This allows the minimum over all $i \\in [g]$ to be changed into the $(1-\\beta)^{th}$ percentile smallest minimum in the upper bound on $\\lambda$. In the limiting case where $\\sigma_{jj}^i = 0$ for all $i$ and some $j$, the current analysis seems to be tight.\n\nThe picture seems more confusing in the correlated case. I fail to find a non-trivial example of parameters where eq. (8) holds. Notice that the lower bound on $\\lambda$ is of the form $\\max_{j \\in S_c^\\star, I \\in [g]} | \\sum_{k \\in S^\\star} w_k^\\star \\sigma_{jk}^i| + \\cdots$, while the upper bound is of the form $\\min_{j \\in S^\\star, i \\in [g]} |w_j^\\star (\\sigma_{jj}^i)^2 + \\sigma_{k \\in S^\\star, k\\ne j} w_k^\\star \\sigma_{jk}^i| - \\cdots$, where the $\\cdots$ terms contain all the dependency on $\\delta$, and by extension, $n_i$. The $\\min$ in the upper bound can be relaxed to $\\min_{j \\in S^\\star_c}$. However, even then, if $\\sigma_{jj}^i < 1$ for any $i$, the upper and lower bounds on $\\lambda$ contradict each other and correctness can no longer be established for the algorithm, let alone finding a suitable value of $\\lambda$. This indicates to me that the analysis in the correlated case might be loose. I do not have an intuition about whether the algorithm might fail in the case (although the experiments seem to not suggest this possibility).\n\nOverall, I think the contribution in the paper is nice, however, not the tightest possible. I would have appreciated it if the authors spent some more effort in making the analysis in the paper tighter, and providing some more insights about when the bounds work, and when they fail. It's nice to see an experimental section and a study into the practical performance of the algorithm. The writing of the paper is ok, but the appendix can be improved quite significantly. It would help to include a little bit of structure as to what lemmas prove what results, and reduce the number of lemmas (since many of them seem to repeat). I would appreciate if the authors put some effort into this, as the current version of the appendix is not up to publication standard in my opinion.\n\nMinor:\n1. $n_i = o(s \\log(d))$ is not the same as $n_i \\le k s \\log(d)$ for some constant $k > 0$.\n2. In the paragraph right before 4.2 there is a typo: $n_i$ is independent of $O(1)$ with respect of dimension $d$.\n3. Use a different notation than $e_i$ for noise (eg. Z_i). It's easy for a reader to confuse this with the standard basis vectors.\n4. How are Lemmas 10 and 11 different from Lemmas 8 and 9? The statements are identical? (same for Lemmas 12 and 13). It would be nice to streamline the appendix and remove bloat in the form of repeating lemmas.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents a new distributed algorithm for support recovery for LASSO in the federated setting where individual users have different data distributions. The algorithm is shown to have low computational cost for each of the users and requires a simple majority vote at the central server, near-optimal statistical complexity (however, requiring that every user has $\\widetilde{\\Omega} (s)$ samples in the uncorrelated case, and $\\widetilde{\\Omega} (s^2)$ samples in the correlated case), and is also robust. The algorithm is theoretically shown to work when the individual user covariances are diagonal and non-diagonal. The theoretical results are rounded out with an experimental analysis of the algorithm.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See strengths/weaknesses.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Ib9eWQrqLh", "reviewer": "Reviewer_sv9G", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n\n**S1** - The paper presents a simple and clear algorithm to obtain the exact support for the federated Lazzo problem that requires little computation. The advantage of this method relies on its simplicity and its theoretical guarantees of convergence. \n\n**S2** - The paper presents a numerical experiment with real-world data that validates the theoretical claims put forward by the authors. \n\nS3 - The authors ‘one-shot communication’ framework makes the method widely applicable in practice. Compounded on the very low computations required, this method seems very well suited for a wide range of IOT applications.\n\n# Weaknesses\n\n**W1** - The paper seems to cover a very limited scenario where the data is generated according to a linear model. Even though these results are important to understanding federated learning under Lasso regularization, the results provided in this work have very limited applicability in practice.\n\n**W2** - The paper’s structure makes it difficult to understand. Even though Lasso is a widely known problem, the exact problem formulation is never explicitly written. This makes the first read of the paper rough and unclear. I would suggest explicitly writing the problem formulation. \n\n**W3** - The choice of a single Lambda for all agents seems like an arbitrary solution that is key in the method but that is not explained. The authors say:\n\n*“we will present a more practical choice of a single lambda across all clients and entries”* \n\nWhat are the implications of this decision and what is the intuition for it?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper considers the problem of learning the support of a distribution over a distributed set of agents. The novelty of this paper resides in the analysis of the convergence results and complexities provided. The paper showcases the method in a real-world dataset.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "# Minor Comments\n\n**Lambda -** It seems to me that  Lambda depends on quantities that cannot be evaluated in practice. As it is common in ML, the value of Lambda can be obtained empirically, but how sensitive the algorithm is to the correct choice of Lambda is unclear to me. The experiments section indicates that Lambda=0.08 was used, but nothing is said of why this value has been chosen or how it has been selected. I would suggest the authors consider providing more information regarding the choice of lambda in practice. \n\n**Modifications**\n\n“It is obvious that for” → “For “", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: I have selected "accept with minor revision" though the revisions I'd like to see are on the more substantial end of the spectrum.

Multiple reviewers mentioned that the manuscript generally needs to be improved for quality and ease of understanding. In particular, the organization of lemmas in the work is currently confusing. Cementing this, along with more explicit problem statements, settings of interest, and relations to prior works on LASSO (especially in distributed settings) would greatly benefit the work.

I would also ask the reviewers to clean up Section 6 in particular, on the choice of the regularizer. Multiple reviews mentioned that this is a crucial point. Therefore it seems that making this clearer would be particularly beneficial. Currently, much of Section 6 is stated informally, in a paragraph structure. I believe it'd behoove the authors to make formal theorem/lemma statements that can be pointed to directly. Additionally, better discussion of related theory in (Wainwright, 2009b) would be useful - can you extract the theorems in question and pose them in the nomenclature of this paper, to better enhance audience understanding?
Decision: Accept (poster)