Distributed Machine Learning with Sparse Heterogeneous Data
Authors: Dominic Richards
Sahand Negahban
Patrick Rebeschini
Venue: NeurIPS 2021 Poster (2021)
Keywords: Distributed Machine Learning
Heterogeneous Data
Federated Machine Learning

Abstract: Motivated by distributed machine learning settings such as Federated Learning, we consider the problem of fitting a statistical model across a distributed collection of heterogeneous data sets whose similarity structure is encoded by a graph topology. Precisely, we analyse the case where each node is associated with fitting a sparse linear model, and edges join two nodes if the difference of their solutions is also sparse. We propose a method based on Basis Pursuit Denoising with a total variation penalty, and provide finite sample guarantees for sub-Gaussian  design matrices. Taking the root of the tree as a reference node, we show that if the sparsity of the differences across nodes is smaller than the sparsity at the root, then recovery is successful with fewer samples than by solving the problems independently, or by using methods that rely on a large overlap in the signal supports, such as the group Lasso. We consider both the noiseless and noisy setting, and numerically investigate the performance of distributed methods based on Distributed Alternating Direction Methods of Multipliers (ADMM) and hyperspectral unmixing.


Distributed Machine Learning with Sparse Heterogeneous Data
Dominic Richards Department of Statistics University of Oxford 24-29 St Giles', Oxford, OX1 3LB
Sahand N Negahban
Department of Statistics and Data Science
Yale University
24 Hillhouse Ave., New Haven, CT 06510
Dominic, Richaards44@maal..... com
Sahand S Www.Neeae@aal.ee...mmmm edu
Patrick Rebeschini
Department of Statistics University Oxford 24-29 St Giles', Oxford, OX1 3LB
Patrick Rebeschini@statte ox ac uk
Abstract
Motivated by distributed machine learning settings such as Federated Learning, we consider the problem of fitting& statistical model across a distributed collection of heterogeneous data sets whose similarity structure is encoded by a graph topology. Precisely. we analyse the case where each node is associated with fitting sparse linear model, and edges join two nodes if the difference of their solutions is also sparse. We propose method based on Basis Pursuit Denoising with a total variation penalty, and provide finite sample guarantees for sub-Gaussian design matrices. Taking the root of the tree as reference node, we show that if the sparsity of the differences across nodes is smaller than the sparsity at the root, then recovery is successful with fewer samples than by solving the problems independently. by using methods that rely large overlap in the signal supports, such the group Lasso. We consider both the noiseless and noisy setting, and numerically investigate the performance of distributed methods based Distributed Alternating Direction Methods Multipliers (ADMM) and hyperspectral unmixing.
Introduction
The wide adoption of mobile phones, wearable and smart devices, has created influx data which requires processing and storage. Due to the size of these datasets and communication limitations, it is then often not feasible to send all the data This has motivated the adoption of decentralised methods, such as Federated Learning 33 43 involves both storing and processing data locally on edge devices.
single computer cluster for storage and processing.
which
This increase in data sources has led to applications that are increasingly high-dimensional. To be both statistically and computationally efficient in this setting, it is then important develop approaches that can exploit the structure within the data. A natural assumption in this case that the data is sparse in some sense. For instance, subset of features is assumed to be responsible for determining the outcome of interest or. in the case of compressed sensing [13), the data is assumed to be generated from sparse signal.
Fitting statistical models on data collected and stored across a variety of devices presents a number of computational and statistical challenges. Specifically, the distributed data sets can be heterogeneous
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

owing to data coming from different population distributions e.g. each device can have different geographic locations, specifications and users. Meanwhile, from a computational perspective. is often unfeasible, due to network limitations and robustness, to have single central "master" device collect and disseminate information. This creates a demand for statistical methodologies which are both: flexible enough to model potential statistical differences in the underlying data; and can be fit in a decentralised manner i.c. without the need for a centralised device to collate information.
In this work, we set to investigate the statistical efficiency of a method for jointly fitting a collection of sparse models across a collection of heterogeneous datasets. More precisely, models are associated to nodes within graph, with edges then joining two models if their difference is also assumed to be sparse. The approach of penalising the differences between models (in an appropriate norm) has, for instance, been applied within both Federated Learning (28) and Hyperspectral Denoising [23 [4] to encode heterogeneous data, In our case, we consider linear models and obtain precise insights into when jointly fitting models across heterogeneous datasets yield gains in statistical efficiency over other methods, such as, the group Lasso and Dirty Model for multi-task learning 244 In addition to being solvable in a centralised manner with standard optimisation packages, the framework we consider is then directly applicable to decentralised applications, as information only needs to be communicated across nodes/mooels//evices which share an edge within the graph.
1.1 Our Contribution
We consider a total variation scheme that penalises differences between models that share an edge in the graph. This scheme encodes the intuition that if the signal differences are sufficiently sparse then, to recover all signals in the graph, is more statistically efficient to first recover a single signal associated to particular reference node (root) and then recover the signal differences associated to edges. Following the celebrated Basis Pursuit algorithm
5 we consider the solution that minimises the L norm of the model associated to root node of the tree and the differences between models that share an edge. We refer to this method as Total Variation Basis Pursuit (TVBP). A noisy variant similar to Basis Pursuit Denoising [9] is then considered, where the linear constraint is substituted for a bound on the l norm of the residuals. We call this method as Total Variation Basis Pursuit Denoising (TVBPD). Note that variants of TVBPD have been successfully applied within the context of hyperspectral data [23] and thus, this work now provides theoretical justification in this case.
Given this framework and assuming sub-Gaussian design matrices, we show that statistical savings can be achieved by TVBP and TVBPD as opposed to solving them either independently or with methods that consider the union of supports (see Table D. In the noiseless case, TVBP requires a total sample complexity of O(s + n²z²) where s is the root sparsity, s' is the maximum sparsity of the difference along edges and n is the number of nodes. In contrast, methods like the group Lasso and Dirty Model (24) have an Onns) total sample complexity, which matches the case when nodes do not communicate with each other. Moreover, note that the TVBP approach does not need to know the true underlying graph G. whereas the optimal stepwise approach does. the true graph G is known, TVBP can incorporate this information to yield improved sampled complexity (see Table in Section 2.2 In the noisy setting, we demonstrate that TVBPD has an & estimation error bounded as ( ((v& & + v Vns'), where as the stepwise approach scales as O(s + ny's',, and thus, achieves an Oly rss)) saving in this case. While the step wise approach achieves optimal total sample complexity in the noiseless case, in the noisy setting its estimation scales sub-optimally compared to TVBPD.
Alongside total sample complexity savings over other joint recovery methods, we also show that TVBP is amenable to decentralised machine learning. Specifically, the objective can be reformulated with constraints that reflect the graph topology allowing a Distributed Alternating Direction Methods of Multipliers (ADMM) algorithm [3] to be applied. Thcoretical findings are also supported by experiments (Section 3.2 which demonstrate both: TVBP can outperform group Lasso methods [24 when model differences are sparse; and TVBPD yields qualitative improvements in hyperspectral unmixing with the real-world AVIRIS Cuprite mine data set.
key reason for TVBP achieving sample complexity savings over variants of the group Lasso and Dirty Model (24. is that the matrices associated to each tasks do not need to satisfy an incoherence condition with respect to their support sets. The incoherence condition a common assumption within the analysis of sparse methods like the Lasso (see for instance [49] and, in short, it requires the empirical covariance of the design matrix to be invertiable when restricted to co-ordinates in the signal support set. This immediately implies that the sample size at each task is larger than the support
2

---

Method
Total Sample Complexity Σver No ns + Diam(G)) + ns'
Sim. Recovery
Know G
Independent Basis Pursuit
X
Stepwise Basis Pursuit
Group Lasso 36
37
ns + Diam
Dirty Model [24]
GSP [6]
TVBP (this work)
+ niaiiam())) (G)s'
X
Table 1: Worst case total sample complexities (up-to logarithmic and constant factors) for recovering collection of sparse signals {*t)wey
tree graph G (V, EE) in the noiseless case with sub- Gaussian design matrices. Sparsity of the root signal [Supp(#t)] S 8, sparsity of difference along edges (u, w) E [Supp(x; xt) S 8'. Sim. Recovery: Whether the method simultaneously recovers the collection of signals hrev. Know G: Whether the sample complexity listed requires knowledge of relationship graph G. TVBP: Total Variation Basis Pursuit (I). When the algorithm does not depend on G and 5', the best case of G, s' can taken.
set of that given task. In contrast, for TVBP an alternative analysis is conducted by reformulating the problem into a standard basis pursuit objective with an augmented matrix and support set. In this case, the problem structure can be leveraged to show Restricted Null Space Property holds when the sample size at each task scales with the sparsity along the graph edges. This highlights that the Total Variation penalty encodes a different structure when compared to methods like the group Lasso and Dirty Model [24]. As shown in the noisy case, this approach can then be generalised through the Robust Null Space Property
1.2 Related Literature
Learning from a collection heterogeneous datasets can be framed as an instance of multi-task learning (6). with applications in distributed contexts gaining increased attention recently. We highlight the most relevant to our setting. The works [52] 48] have considered models penalised in & sense according to the network topology to encode prior information. The & penalty is not appropriate for the sparse setting of our work. A number of distributed algorithms have been developed for the sparse setting, for a full review we refer to [1] The works [24 44
50 29
51 38
have developed distributed algorithms following the group Lasso setting, in that, the signals are assumed to be composed of common shared component plus an individual component. Within 12 50 this requires each node to satisfy an incoherence condition, while the setting in [29
specific case of star topology within our work. For details on how the incoherence condition influences the sample complexity see discussion in Section 2.1 The work [40] develops a manifold lifting algorithm jointly recover signals in the absence of incoherence assumption, although no theoretical guarantees are given.
is particular instance of distributed multi-task learning where central node (root) holds a global model and other devices collect data and update their model with the root. Data heterogeneity can negatively impact the performance of methods which assume homogeneous data, see [33] for the case of Federated Averaging. This motivates modelling the data heterogeneity, recently done within [28] where the difference in model parameters is penalised at each step. Our work follows this approach in the case of learning sparse models, and thus, it provides insights into when an improvement in statistical performance can be achieved over other baseline methods.
Federated machine learning 27 43
33
28
Simultancously recovering collection of sparse vectors also be framed into the multiple measurement vectors framework ([5), which has been precisely investigated for f regularisation for q > 1. Specifically, f// was investigated within [55
36
47 and / in [3 37.. Other
variants include the Dirty Model [24], multi-level Lasso of 32 and tree-guided graph Lasso of (25]. In the same context, number of works have investigated variants of greedy pursuit style algorithms [16] IT 12 46). These methods assume a large overlap between the signals, with their (see Section 2.1).
analysis often assuming each task satisfies an incoherence condition 36 24 37
The total variation penalty linked with the fused Lasso
and has been widely applied to images due to promoting piece-wise continuous signals which avoids blurring. As
3

---

far as we are aware, the only work theoretically investigating the total variation penalty as tool to link a collection of sparse linear recovery problems has been [[O]. This work considers the penalised noisy setting and gives both asymptotic statistical guarantees and an optimisation algorithm
targeting a smoothed objective. In contrast, we give finite sample guarantees as well as settings
where statistical savings are achieved. The application of hyperspectral unmixing [22 23 14] has
successfully integrated the total variation penalty within their analysis. Here, each pixel in an image can be associated to its own sparse recovery problem, for instance, the presence of minerals [33 or the ground class e.g. trees, meadows etc. [4]
Noiseless Setting
This section presents results for the noiseless setting. Section 2.1 introduces the setup and details behind the comparison to other methods in [Tble[]] Section [22 presents analysis for Total Variation Basis Pursuit alongside descriptions of how refined bounds can be achieved. Section presents experimental results for the noiseless setting. Section gives a sketch proof of the main theorem.
2.1 Setup
Consider an undirected graph G =
E) with nodes |V| and edges E' S V x V. Denote the degree of a node v E V by Deg(v) = K(i.j) E É : v or j = V} and index the nodes V {1, [I,....7) n) with root node associated to 1. To each node E V, associate signal vector ay E Rd. The objective is to estimate the signals {ar) through measurements {Jo Jev defined as yo = A E N. where A E IR xxd is design matrix. As we now go on to describe, we will assume the signals are both: sparse ry for graph G can encode collection of wearable devices connected through network. Each node holds a collection of data (ye., Ag) that can, for example, represent some sensor outputs. Alternatively, in Hyperspectral Denoising, each node v E V is associated to pixel in image and the signal s; indicates the presence of a mineral or classification of land type. The graph can then encode the landscape topology.
V, and related through the graph G. For instance, the
Following these examples, it is natural that the collection of signals (xt) will have sparsity structure related to the graph G. Specifically, if two nodes share an edge (v, w) E E' then it is reasonable that only few co-ordinates will change from x to xz For instance, in Hyperspectral Imaging we expect the composition of the ground to change by a few minerals when moving to an adjacent pixel. This can then be explicitly encoded by assuming difference in the underlying signals can also be sparse. We encode the structural assumption on the signal within the following definition.
Definition (G, s,s) s') Sparsity). A collection of signals {x* Fev is (G, 8, s') J-sparse the following is satisfied. The root-node signal support is bounded [Supp(xi)] I s. For any edge e (v, w) E E the support of the difference is bounded Sup - zwwl S s'.
We are interested in the total number of samples Nyoua Sumples := - No required recover all of the signals hee. We begin by describing the total number of samples N Samples required by baseline methods, a summary of which in Table
Independent Basis Pursuit For an edge S. = (up ). Let us suppose for any pair of edges e, E the supports of the differences are disjoint from each other S. S. @ and the support of the root S. n S1 = 0. Let G be tree graph and the integer in E :(.....,r. n 1} denote the graph distance from node v to the root agent 1. If each node has sub-Gaussian matrices A, and performed Basis Pursuit independently, then the number of samples required by agent v to recover x scales as N1, 2 8 + i,,''. The total sample complexity is at least NToua Samples = =>vev N,, 2 nss + +'s Evev in O(ns + Diam(G)²s) where we lower bound Eeev ig by considering the longest path in the graph including agent 1. The optimisation problem associated to this approach then
(v, w) E E. denote the support of the difference as
min |xo||]| subject to ADx, yu for 0 V,,
which can be solved independently for each agent E V.
Stepwise Basis Pursuit Consider the support set structure described in Independent Basis Pursuit. The signals can then be recovered in stepwise manner with a total sample complexity of O(s + ns').

---

Precisely, order s samples can recover the root signal ri, meanwhile order x s' samples can recover each of the differences associated the edges. Any node's signal can then be recovered by summing up the differences along the edges. This yields saving from ((ns + n²²s)) to O(s + ns'). which significant when the difference sparsity small and the network size n is large. This embodies the main intuition for the statistical savings that we set to unveil in our work. The associated optimisation problem in this case requires multiple steps. Let the solution at the root denoted T1 = arg min 21 | l12. For path graph we recursively solve, with the notation Σi= 0,
the following sequence of optimisation problems for ......
min |||| subject to A,A Vj
A,31
Σ AR
with the sequence of solutions here denoted (A
Group Lasso Dirty Model / GSP The group Lasso 36 37 Dirty Model (24 and Greedy Pursuit Style algorithms [16] [2] 46) from the Multiple Measurement Vector Framework [15), assume an incoherence condition on the matrices A, for v E V, which impacts the total sample complexity. Namely, for v E V denote the support S. Supp( C (1....,d d} alongside the design matrix restricted to the co-ordinates in S. by (Ap)s, E x.N. The incoherence assumption for the Dirty Model (24] then requires (A T (A.)s. s. to be full-rank (invertibility), and thus, No, > [S Since |S,| = 8 i the lower bound on NTuil Samples then comes from Independent Basis Pursuit. One of the associated optimisation problem for the group lasso then takes the form for some À
d Σ 2=1
min
1100 A,t
12
(
DEV
2.2 Total Variation Basis Pursuit
To simultancously recover the signals tæthev we consider the Total Variation Basis Pursuit (TVBP) problem. Specifically for tree-graph G (V, E) with edges E C V, consider:
min
|ælll1 +
Σ
1 Dw ll1 subject to A, = yo for V.
(1)
e= E
Let us denote solution to (1 as ".TVBP""eE JuEV. Note that G does not have to be equal to the graph associated to the sparsity of {xt>ev.. For instance, we can consider a star graph for G whilst G is a more complex unknown graph. Furthermore, we highlight that ( couples the agents solutions together in a distinctly different manner when compared the methods Section 2.1 e.g. Group Lasso.
We now upper bound on the number of samples N1, Noon-soor required for TVBP to recover the signals. For the following, we say that if A has independent and identically distributed (i.i.d.) sub- nub-Gaussian entries, then the j, entry Aij satisties 11([ 2 t) S. -dt for all t 2 O for sub-Gaussian parameters 3 and K. Let us also denote the root sample size as NR = N1, with all non-root agents having the same sample size Noon-root = N₂ for E V\(1}. The proof for the following theorem can then found in Appendix Appendix(A.I.I [A.I.]]
Theorem 1. Suppose the signals (Et are (G,s,s')-su -'parse and the matrices satisfy A, VN. A, where (Aylvev each have i...d. sub- Gaussians entries. Fix > 0. If
NRoot 22 max(s,
(8, ni DiDDiaa)))) (G)s (Gogg)))()))))) + log(1/c)) and
Noon-root Z nDiam (lo(()) + log(n/e)),
then with probability greater than 1 - the TVBP solution with a star graph G is unique and satisfies x BP =x for any V.
Theorem provides conditions on the number of samples held by each agent in order for TVBP to recover the signals when G is star topology. As seen in Table the total number of samples in
5

---

this case satisfies Noal Samples ((s + n Diam(G)ss). As we now go on to describe, the sample complexities in Theorem arre worst case since we have assumed no prior knowledge of G.
Incorporating knowledge of the signal graph G into the TVBP problem TT naturally influences the total sample complexity required for recovery. Table 2 provides summary of the total complexity required in two different cases, Precisely, an improved total sample complexities can be achieved when: G is known tree graph, as well as when the non-root design matri- ces (AAJeeVVEE are the same. When G is a known tree graph, the sample complexity is re- duced to + max(n", nDeg (11))))aamm ( from + ni'iiam(G) previously. In the case DGa = O(vn), then an order vns' saving in achieved. Meanwhile, if (A.)evvy are also equal, then the sample complexity reduces to s + nDeg(1) 51) which, for constant degree root nodes (1g matches the optimal stepwise method. This precisely arises due to the null-spaces of the non-root nodes matrices being equal in this case, allowing the analysis to be simplified. Details of this are provided within the proof sketch. The assumption that the sensing matrices {Ap hevev (1) are equal is then natural for compressed sensing and Hyperspectral applications as A, represents the library of known spectra, and thus, can be identical across the nodes.
Method & Assumptions
Total Sample Complexity EvEr N₂
Know G
TVBP
+ n D>Diimmm (G)s'
X
TVBP + Tree
+ max (n²; (DD)(VX(())) (1))m
TVBP + G Tree {A,)vEv equal
DD)e(1)
Table 2: Setting described in Table Comparing total sample complexity for TVBP with different assumptions: whether G' is a known tree; or G is a known tree and the design matrices (A, (eveevv are identical. Formal results can be found in Theorems and within the Appendix [A.] When the algorithm depends upon the choice of graph G, the rate given depends upon this choice of G and the associated sparsity along edges s'.
2.3 Experiments for Noiseless Case
This section presents numerical experiments for Total Variation Basis Pursuit problem (I) The paragraph Statistical Performance focuses on the statistical performance of TVBP, supporting the results summarised in Table 2 Paragraph Distributed Algorithm outlines how the objective (T) can be solved in decentralised manner.
Statistical Performance Figure Figure plots the probability of recovery against the number of samples held by non-root nodes N2 for E V\[1} with fixed number of root agent samples Ni [2x log(ed/s)) [- Observe, for a path topology and balanced tree topology, once the non-root nodes have beyond approximately 30 samples, the solution to TVBP finds the correct support for all of graph sizes. In contrast, the number of samples required to recover a signal with Basis Pursuit at the same level of sparsity and dimension considered would require least 80 samples, i.e. 2s log log(ed/s) (ed/s). We therefore save approximately 50 for each non-root problem.
Secoverr
CeRecoerry
Aumeio
Aperac
Apersa
0.8
0.2
Humoer of wwr.SSaaaa 152
Numbbr dlagaru Sampur trre
Figure 1: Probability of recovery vs number of non-root node samples N, for u E VV (1). Problem setting d = 128, s = 12, s' = 4 and N₂ = 22s log(ed/s) = 80, for path (Left) and balance tree with branches of size 2 (Right). Lines indicates graph sizes with n E (2,4, 8, 16] for path and (7, 15, 31} for balanced tree with heights of (2, 3, 4) respectively. Solution to reformulated problem (T)) found using CVXOPT. Each point is an average of 20 replications. Signal sampled
from (1, 11, differences concatenation of s' values. {Ar standard Gaussian and G = G.

---

Distributed Algorithm To solve the optimisation problem (1) in a decentralised manner an ADMM algorithm can be formulated, the details of which are given in Appendix AA.2] The Optimisation Error for the method is plotted in Figure 2 which is seen to converge with a linear rate. The convergence for a path topology slower, reaching precision of 10-$ 8 in 300 iterations for nodes, while the same size balanced tree topology reaches a precision of 10-15 This is expected as the balanced trees considered are more connected than a path, and thus, information propagates around the nodes quicker. Larger tree topologies also require additional iterations to reach the same precision, with size 63 tree reaching a precision of 10-7.5 7.5 in 300 iterations.
Opt. Frro Vs Iteration for ADMN
Opt. Emer Va Baration for ADMM
Aga Agarts
2.5
0.2
Agent: 32 Agett:
-25
-50
-7.4
-300
100
350
202
255
ACMOM
Figure 2: Optimisation error ||ac Bp 2 (Log scale) Iterations for ADMM method with p 10 for different graph sizes (lines) and topologies (plots). Here Tpp is solution to TT. Problem parameters
d = 29, s = [0.1d] and s' = 4. Left: Balanced trees, branch size and heights {2, 3, 4, 5). Right: Path topology. Agent sample size N1 = 2s log(ep/2s) and N. = 150 for * 1. Matrices {A [Aeeev i..dd standard Gaussian entries, zi has s values randomly drawn from (+1, -1} and (A)) eE each have s' i.i.d. standard Gaussian entries, locations chosen at random.
2.4 Proof Sketch for Theorem
This section provides proof sketch for Theorem For a response y E R and design matrix A E Nxd, recall that the Basis Pursuit problem given by
min | subject to Ar y-
Let us denote the solution to as a. BP known that y Ax for some sparse vector x' supported on S, then the solution to ( recovers the signal BB x² if and only if A satisfies the Restricted Null Space Property with respect to S, that is,
(x)ss)
||>|| for E (er(A))(()
(3)
In the case A has i..dd sub-Gaussian entries and N Z [Slc=2 log(d/5) for c E (0,1/2), we then have [[x)s]]i S c||x|| with probability greater than 1 1-18 [17].
The proof for Theorem D proceeds in two steps. Firstly, the TVBP problem (T) is reformulated into a standard basis pursuit problem (2) with an augmented matrix A, signal x" and support set S. Secondly, we show that the Restricted Null Space Property can be satisfied in this case by utilising the structure of A, x² and S. Each of these steps is described within the following paragraphs. For clarity, we assume the TVBP problem with G = G, the signal graph G being tree graph with agent the root, and all non root agents with equal design matrix A, Á for v E {2, 3, 4, 5,...,,,, Discussion on weakening these assumptions is provided at the end, with fulls proofs given in Appendix [
n..
Reformulating TVBP problem Let us denote
Rd and A, E IRd for i = I,..., 1 where can then be reformulated as
edges E E are associated to an integer e + i. The TVBP problem (I)
A
0
0
T A
21
A
Ā
H13
H
y/2
min Ar.
||
+
A
subject to
Ā
H22
A
H
A₂
y/
:
Hng
Haa
Ā
An-1/
yo
where the matrices (He,) J..j= take values H,y = Ā if the jth agent on the path from agent i to the root node 1, and 0 otherwise. The above is equivalent Basis Pursuit problem 2 with
7

---

== (11, ... An). = (31.822... Vn), an A E Rudxnd encoding the linear constraint above, and sparsity structure S = (S, }.). That is for an edge = (V, w) E E the support
constructed by off-setting S. = Supp( - xz) by an integer (Se + +))= = (I: + i: k E Se)-
Showing Restricted Null Space Property We begin by noting that if x E Ker(-A)\(0) then
1
Åδ. = for e (v, w) E E such that u, w + 1,
the second equality being over edges not connected to the root node. To see this, suppose the edge E E is both: associated to the integer and not directly connected the root 1 & e. Consider the edge neighbouring e closest to the root, say, e' E E with integer j. We have from
Anı AA; +
Σ RepfE
Hu =0 and
Āx + AA₃ +
H =0. kØj
Taking the difference of the two equations we get ÅA, = since both: j is on the path from i to the root so Hij- = A: and the path from j to the root is shared i.e. Enyis Hij = Enys Hz
In a similar manner to Basis Pursuit, the constraints (4) are used to control the norms (1(z)) ).s, As,]] ll and I(A,)s. s. I for e E Evie E E e) Precisely, if A, E IR xd and À E R NSuuome x both i.i.d. sub-Gaussian with N₁ 2 (1/() and NNon-rooe 2 8' log(1/6), then ([x1)); S || /4 and ((A,)ss, II < || 1/4 with high probability. Controlling the norm for the edges E E connected
to the root E is then more technical. In short, N1, Noon-Root 2 Deg (1) log(1/0) then
[K(..)s,ll ll $ (1]>al) [I + (/Alll////e/// Summing up the bounds gives
1 Σ 2
[I ((())ss + -I.(A.s. 11 - | 11
|1.
|||1||
RE
CE
(4) may no longer be satisfied, and thus, an alternative analysis is required. Meanwhile, if G is star and does not equal G, a different sparsity set S is considered where the support along edges swapped s' > Diam
as required. When the matrices {Aoherry are different the condition
3 Noisy Setting
This section demonstrates how the TVBP problem can be extended to the noisy setting, Section introduces Total Variation Basis Pursuit Denoising (TVBPD) alongside theoretical guarantees. Section 3.2 presents experiments investigating the performance of TVBPD.
3.1
3.1 Total Variation Basis Pursuit Denoising
Let assume that Ve Aux", c, for e E V. In this case the equality constraint in the TVBP problem (I) is swapped for a softer penalisation, leading to the Total Variation Basis Pursuit Denoising (TVBPD) problem for graph = (V, , E) and penalisation 17 > 0
min hav
| +
Σ c=(r,))E
|| z. ll subject
Σ VEV
||A
yo 10 1²2
(5)
The equality constraint A,T, Yo each agent u V in (T) is now swapped with an upper bound
on the deviation ,,, - V. Given this problem, we now provide gaurantees on the l estimator error for the solution of (5). The proof of the following Theorem in Appendix (311
Theorem 2. Suppose G is tree graph, the signals {ath
(G, 8, s') -ssarse and yo A + Eu for U V. Assume that Ag Ao/ where {Arbeev each have i.i.d. nub-Gaussian and
entries. Fix 0. 1f 2 Evev
NR 2 (log(d) log(1/e)) and
Noon- 2 nits' (log(d)) log(n/e)),
then with probability greater than 1 c the solution to (5) with & = G satisfies
|||| xill1
Σ (E
[ xw) (xt 11l)l1 $ (V3 + Deg(())Vns)),
8

---

Theorem gives conditions on the sample size so a bound on the & estimation error can be achieved. For the stepwise approach in Section 2.1 the E estimation error scales as v + vs' Therefore, TVBPD yields an order v saving in & estimation error over the step wise approach. This highlights two sample size regimes. When the total sample size is O(s + ns'), the step wise approach is provably feasible and the estimation error is O(v + nVB"). Meanwhile, when the total sample size is O(s + +n n²s"), TVBPD is provably feasible and the estimation is O(V3+ Vns'). The gap in sample size requirements between the noisy case with TVBPD O(s + n² and the noiseless case with TVBP (ss + n² Di) is due different proof technique for TVBPD. We leave extending the techniques for analysing TVBP to the case of TVBPD to future work.
3.2 Experiments for Total Variation Basis Pursuit Denoising
This section present simulation results for the Total Variation Basis Pursuit Denoising problem (5) The following paragraphs. respectively, describe results for synthetic and real data.
Synthetic Data. Figure 3 plots the & estimation error for Total Variation Basis Pursuit Denoising, group Lasso and the Dirty Model of [24], against the number of agents for both path and balanced tree topologies. As the number of agents grows, the estimation error for the group Lasso methods grows quicker than the total variation approach. The group Lasso variants perform poorly here due to the union of supports growing with the number of agents, and thus, the small overlap between agent's s supports.
L Emao Vs Number of Agents of =
L1 Error Vs Number Agents, 5f #-4
Creup Learo
Creap Lana Hudd
Dity Hodil
101
15
Sumber of Agents
Mamber Agent
Figure 3: & estimation error Σvey ||,, 2; (logio scale) against number of agents for Total Variation Basis Pursuit Denoising solved using SPGLI Python package (Yellow), group Lasso (biue) and Dirty Model of (24) (Green). Left: Path topology. Right: Balanced tree topology height branching rate {2, 3, 4, 5, 6). The same i.i.d. standard Gaussian matrix was associated to each node with N₂ = 200 for u E V. with parameters were d = 20, = 25 and s' = 4. Signal at the root zj and differencee {
x* ( sampled from {+1, -1} with no overlap in supports.
Hyperspectral Unmixing. We apply Total Variation Basis Pursuit Denoising to the popular AVIRIS Cuprite mine reflectance dataset ht a subset of the USGS library splib07 (26). As signals can associated to pixels in 2-dimensional image, it is natural to consider the total variation associated with a grid topology. Computing the total variation explicith explicitly in this case can be computationally expensive, see for instance 39 We therefore simplify the objective by tilling the image into groups of n = 4 pixels arranged in 2x2 grid, with each group considered independently. This common approach within parallel rendering techniques, see for instance [34, and is justified in our case as the signals are likely most strongly correlated with their neighbours in the graph. Note that this also allows our approach to scale to larger images as the algorithm can be run on each tile in an embarrassingly parallel manner. More details of the experiment are in Appendix B.2
jjp. nasa. gov/ /d/////aaaaaaa free_dataee_eeeeeeeeeeereeeeeeee html with
We considered four methods: Variation Denoising (5) applied to the groups of 4 pixels as described previously; the group Lasso applied to the groups of 4 pixels described previously.; and baseline Hyperspectral algorithm SUNnSAL 2 Figure then then gives plots of the coefficients associated to two minerals for three of the methods. Additional plots associated to four minerals and the four methods have been Figure 6 Appendix B.2 Recall, by combining pixels the aim is to estimate more accurate coefficients than from denoising them independently. Indeed for the Hematite, Andradite and Polyhalite minerals, less noise is present for the total variation approach, alongside larger and brighter clusters. This is also in comparison to SUN where the images for Andradite and Polyhalite from the total variation
applying Basis Pursuit Denoising to each pixel independently; Total
9

---

approach have less noise and brighter clusters. Although, we note that combining groups of pixels in this manner can cause the images appear at lower resolution.
Fehootte cest 6m)
Plyyaie Vitegeront 20 (000
Aistoat Stevn (6
Figure 4: Coefficients associated to the minerals Andradite (top), and Polyhalite (bottom).. Methods are, left: Total Variation Basis Pursuit Denoising applied to 2x2 pixel tiles with 17 0.001; Middle: Basis Pursuit Denoising applied independently to each pixel with 0.001. right: SUNnSAL with regularisation of 0.001. Yellow pixels indicate higher values.
4
Conclusion
In this work we investigated total variation penalty methods to jointly learn collection of sparse linear models over heterogeneous data. We assumed a graph-based sparse structure the signals, where the signal at the root and the signal differences along edges are sparse. This setting differs from previous work on solving collections of sparse problems, which assume large overlapping supports between signals. We demonstrated (in noiscless and noisy settings) that statistical savings can be achieved over group Lasso methods as well as solving each problem independently, in addition to developing distributed ADMM algorithm for solving the objective function in the noiseless case.
The theoretical results currently suggest having identical matrices for non-root agents is more sample efficient over having different matrices (Table[and proof sketch Section 2.4). A natural direction is to investigate whether this is limitation of the analysis, or fundamental to using the Total Variation penalty. Following this work, a distributed ADMM algorithm can also be developed for Total Variation Basis Pursuit Denoising optimisation problem
Acknowledgements
D.R. is supported by the EPSRC and MRC through the OxWaSP CDT programme (EP/L016710//), and the London Mathematical Society ECF-1920-61. S.N. was supported by NSF DMS 1723128. P.R. was supported in part by the Alan Turing Institute under the EPSRC grant FP/N510019/11
References
[1] Ghanbar Azamia, Mohammad Ali Tinati, and Tohid Yousefi Rezaïi. Cooperative and distributed algorithm for compressed sensing recovery in wsns. IET Signal Processing, 12(3):346-377) 2017.
[2] José M Bioucas-Dias and Mário AT Figueiredo. Alternating direction algorithms for con- strained sparse regression: Application to hyperspectral unmixing. In 2010 2nd Workshop on Hyperspectral Image and Signal Processing: Evolution in Remote Sensing, pages 1-4. IEEE, 2010.
[3] Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, and Jonathan Eekstein. Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Mach. Learn,, 3(1):1-122, January 2011.
10

---

[4] Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, and Jonathan Eckstein. Distributed opti- mization and statistical learning via the alternating direction method of multipliers. Foundations and Trends in Machine Learning, 3(1):1-122, 2011.
[5] Emmanuel J Candes, Justin K Romberg, and Terence Tao. Stable signal recovery from incom- plete and inaccurate measurements. Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences,
2006.
[6] Rich Caruana. Multitask learning. Machine learning, 28(1):41-75, 1997.
[7] Antonin Chambolle. An algorithm for total variation minimization and applications. Journal of Mathematical imaging and vision, 20(1-2):89-97 2004.
[8] Venkat Chandrasekaran, Benjamin Recht, Pablo A Parrilo, and Alan S Willsky. The convex geometry of linear inverse problems. Foundations of Computational mathematics, 12(6):805- 849, 2012.
[9] Scott Shaobing Chen, David Donoho, and Michael Saunders. Atomic decomposition by basis pursuit. SIAM review, 43(1):129-159) 2001.
[10] Xi Chen. Seyoung Kim, Qihang Lin, Jaime G Carbonell, and Eric P Xing. Graph-structured multi-task regression and an efficient optimization method for general fused lasso. arXiv preprint 3005. 2010.
[1]] Yi Chen, Nasser M Nasrabadi, and Trac Tran. Hyperspectral image classification using dictionary-based sparse representation. IEEE transactions on geoscience and remote sensing, 49(10):3973-3985 2011.
[12] Wei Dai and Olgica Milenkovic. Subspace pursuit for compressive sensing signal reconstruction. IEEE transactions Information Theory, 55(5):2230-2245 2009.
[13] David L Donoho. Compressed sensing. IEEE Transactions information theory, 52(4):1289 1306, 2006.
[14] Peijun Du, Zhaohui Xue, Jun Li, and Antonio Plaza. Learning discriminative sparse repre- sentations for hyperspectral image classification. IEEE Journal of Selected Topics in Signal Processing. 108): 1104, 2015.
[15] Marco F Duarte and Yonina C Eldar. Structured compressed sensing: From theory to applica- tions. IEEE Transactions on signal processing, 59(9):4053-4085, 2011.
[16] Joe-Mei Feng and Chia-Han Lee. Generalized subspace pursuit for signal recovery from muliple-meesureement vectors. In 2013 IEEE Wireless Communications and Networking Conference (WCNC), pages 2874-2878, IEEE, 2013.
[17] Simon Foucart and Holger Rauhut. An invitation to compressive sensing. In A mathematical introduction to compressive sensing, pages 1-39. Springer, 2013.
rachford [18] Bingsheng He and Xiaoming Yuan. On the o(1/n) convergence rate of the alternating direction method. SIAM Journal on Numerical Analysis, 50(2):700-709, 2012.
[19] BS He, Hai Yang, and SL Wang. Alternating direction method with self-adaptive penalty param- eters for monotone variational inequalities. Journal of Optimization Theory and applications, 106(2):337-355 2000.
[20] Mingyi Hong and Zhi-Quan Luo. On the linear convergence of the alternating direction method of multipliers. Mathematical Programming, 162(1-2):165-199, 2017.
[21] lan-Christian Hütter and Philippe Rigollet. Optimal rates for total variation denoising. In Conference on Learning Theory, pages 1115-1146, 2016.
[22] Manian-Daniel lordache, José M Bioucas-Dias. and Antonio Plaza. Sparse unmixing of hy- perspectral data. IEEE Transactions on Geoscience and Remote Sensing, 49())220142233, 2011.
11

---

[23] Marian-Danie lordache, José M Bioucas- Dias, and Antonio Plaza. Total variation spatial regularization for sparse hyperspectral unmixing. IEEE Transactions on Geoscience and Remote Sensing, (0(11)0(144))))) ):4488 4502, 2012.
[24] Ali Jalali, Sujay Sanghavi, Chao Ruan, and Pradeep K Ravikumar. A dirty model for multi-task learning. In Advances in neural information processing systems, pages 964-972, 2010.
[25] Seyoung Kim and Eric Xing. Tree-guided group lasso for multi-task regression with structured sparsity. In ICML, volume page 2010.
[26] Raymond F Kokaly, Roger N Clark, Gregg A Swayze, K Eric Livo, Todd M Hoefen, Neil C Pearson, Richard A Wise, William M Benzel, Heather A Lowers, and Rhonda L Driscoll. Usgs spectral library version 7. Technical report, US Geological Survey, 2017.
[27] Jakub Konečný; Brendan McMahan, Daniel Ramage, and Peter Richtárik. Federated optimiza- tion: Distributed machine learning for on-device intelligence. arXiv preprint arXiv:1610.02527, 2016.
[28] Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. arXiv preprint arXiv: 181200617, 2018.
[29] Xiaowei Li. A weighted 11 I1-minimization for distributed compressive sensing. PhD thesis, University of British Columbia, 2015.
[30] Po-Ling Loh and Martin J Wainwright. High-dimensional regression with noisy and missing data: Provable guarantees with non-convexity. In Advances in Neural Information Processing Systems, pages 2726-2734, 2011.
[31] K Lounici, M Pontil, AB Tsybakov, and SA Van De Geer. Taking advantage of sparsity in multi-task learning. In COLT 2009-The 22nd Conference Learning Theory, 2009.
[32] Aurelie C Lozano and Grzegorz Swirsze7 Multi-level lasso for sparse multi-task regression. In Proceedings of the 29th International Coference on International Conference on Machine Learning, pages 595-602. Omnipress, 2012.
[33] Brendan McMahan, Fider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas Communication-effin -ffficcent learning of deep networks from decentralized data. In Artificial Intelligence and Statistics, pages 1273-1282. PMLR, 2017.
[34] Steven Molnar, Michael Cox, David Ellsworth, and Henry Fuchs. A sorting classification of parallel rendering. IEEE computer graphics and applications, 14(4):23-32, 1994.
[35] João FC Mota, João MF Xavier, Pedro MQ Aguiar, and Markus Puschel. Distributed basis pursuit. IEEE Transactions on Signal Processing, 60(4):1942-1956, 2011.
[36] Sahand Negahban and Martin J Wainwright. Joint support recovery under high-dimensional scaling: Benefits and perils of reguularization In Proceedings of the 21st International Con- ference on Neural Information Processing Systems, pages 1161-1168. Curran Associates Inc., 2008
high-dimensional multivariate regression. The Annals of Statistics, 39(1):1-47, 2011. [37] Guillaume Obozinski, Martin Wainwright, and Michael I Jordan. Support union recovery in
[38] Felix Oghenekohwo, Haneet Wason, Ernie Esser, and Felix Herrmann. Low-cost time-lapse seismic with distributed compressive sensing- part 1: Exploiting common information among the vintages. Geophysics, 82(3):P1-P13 2017.
[39] Oscar Hernan Madrid Padilla, James Sharpnack, James G Scott, and Ryan Tibshirani. The dis fused lasso: Linear-time time denoising over general graphs. Journal of Machine Learning Research, 18:176-1, 2017.
[40] Jae Young Park and Michael Wakin. A geometric approach to multi-view compressive imaging. EURASIP Journal on Advances in Signal Processing, 2012(l):37, 2012.
12

---

[41] Marcos Raydan. The barzilai and borwein gradient method for the large scale unconstrained minimization problem. SIAM Journal on Optimization, 7(1):26-33, 1997.
[42] Leonid Rudin, Stanley Osher, and Emad Fatemi. Nonlinear total variation based noise removal algorithms. Physica D: nonlinear phenomena, 60(1-4):259-28) 1992.
[43] Virginia Smith, Chao-Kai Chiang, Maziar Sanjabi, and Ameet S Talwalkar. Federated multi-task learning. In Advances in Neural Information Processing Systems, pages 4434-4434, 2017.
[44] Dennis Sundman, Saikat Chatterjee, and Mikael Skoglund. Design and analysis of a greedy pur- suit for distributed compressed sensing, IEEE Transactions on Signal Processing, 64(11):2803- 2818, 2016.
[45] Robert Tibshirani, Michael Saunders, Saharon Rosset, Ji Zhu, and Keith Knight. Sparsity and smoothness via the fused lasso. Journal of the Royal Statistical Society: Series (Statistical Methodology), 67(11:11-108, 2005.
[46] Joel A Tropp. Anna C Gilbert, and Martin Strauss. Algorithms for simultaneous sparse approximation. part Greedy pursuit. Signal processing, 86(3):572-588, 2006.
[47] Berwin A Turlach, William N Venables, and Stephen Wright. Simultaneous variable selection. Technometrics, 47(3):349-363, 2005.
[48] Paul Vanhaesebrouck, Aurélien Bellet, and Mare Tommasi. Decentralized collaborative learning of personalized models over networks. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2017.
[49] Martin J Wainwright. High-dimensional statistics: non-asymptotic viewpoint, volume 48. Cambridge University Press, 2019.
[50] Jialei Wang, Mladen Kolar, and Nathan Srerbo. Distributed multi-task learning. In Artificial Intelligence and Statistics, pages 751-760, 2016.
[51] Manxi Wang, Yongcheng Li, Xiaohan Wei, and Qing Ling. Robust group lasso over decen- tralized networks. In 2016 IEEE Global Conference on Signal and Information Processing (GlobalSIP), pages 490-494. IEEE, 2016.
[52] Weiran Wang, Jialei Wang, Mladen Kolar, and Nathan Srebro. Distributed stochastic multi-task learning with graph regularization. arXiv preprint 18Xiv:1802.038300 02 2018.
[53] Yu-Xiang Wang, James Sharpnack, Alexander Smola, and Ryan Tibshirani. Trend filtering on graphs. The Journal of Machine Learning Research, 17(1):3651-361, 2016.
[54] Junfeng Yang and Yin Zhang. Alternating direction algorithms for eell 1-problems in compres- sive sensing. SIAM journal on scientific computing. 33(1):250-278, 2011.
[55] Cun-Hui Zhang and Jian Huang. The sparsity and bias of the lasso selection in high-dimensional linear regression. The Annals of Statistics, 36(4):1567-1594 2008
[56] Jiayu Zhou, Jianhui Chen, and Jieping Ye. Malsar; Multi-task learning via structural regulariza- tion. Arizona State University, 2011.
13


Reviews:
[{"review_id": "zkx-KTHj_0I", "reviewer": "Reviewer_Uu6J", "summary": "The paper develops and analyzes a total variation formulation to recover multiple signals associated with nodes in a graph under sparsity assumptions on the signals at each node and the difference signals along the edges. Sample complexity results are presented for the noiseless and noisy settings, and a distributed ADDM-based algorithm is developed. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength \n* The method proposed could be better than Group Lasso when the overlap between the signals’ supports is small.\n* The paper provides provable guarantees and is generally well-written. \n\nWeakness\n* The sample complexity seems to be generally worse than Group Lasso and the Dirty Model. One of the terms scales quadratically with the graph size n (vs linear in n for Group Lasso), which calls into question the scalability of the proposed method and its usefulness for large graphs. In turn, all examples in the numerical results are for fairly small graphs.  \n* The title of the paper is too broad and does not reflect the actual scope of this work. This is essentially an MMV recovery problem with sparsity constraints relative to a graph topology. \n* The experimental results for hyperspectral imaging are not convincing and inconclusive. \n* I am not able to draw conclusions about the actual gains of the proposed total variation method relative to existing methods. For example, it would have been useful to derive phase transitions type results to possibly highlight regimes where the proposed TVBP method outperforms Group Lasso as a function of the overlap between the signal supports.\n\nOverall, I believe this is a good paper but is lacking in several aspects. Compared to other papers I have reviewed at NeurIPS, this paper is borderline. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "sHo7w-h1x9", "reviewer": "Reviewer_MYEC", "summary": "The authors introduce a method for learning signals on a graph, whereby each node signal x on the graph G to be learnt is detected by signals y via a linear transformation y = Ax. The method is known as total variation basis pursuit, and exploits the difference between signals connected by the edges of the graph to learn the signals.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The contributions of the authors are twofold: One, they do not require the underlying graph to be known while achieving better sample complexity than the algorithms they compared to, which are independent basis pursuit (BP), stepwise BP and group lasso. Two, they do not require the incoherence conditions associated with support sets of the matrix. Instead, it is reformulated as a Restricted Null Space Property that holds when the sample size scales with the sparsity along the graph edges.\n\nGenerally the paper is written reasonably. However, I have some questions over the main result and theorem, which I think can help to make the paper clearer. \n\n1) The optimization problem (equation 1) is formulated in terms of a tree graph. While the purpose of this algorithm is to tackle the case where the underlying graph is not known, why is there an assumption for the underlying graph to be a tree? Some discussion on this would be helpful. The idea of a root or tree is also discussed in the abstract in line 8 without prior definition or discussion as to why this case in considered in the first place, which may lead to confusion among readers.\n\n2) I think more discussion on the limitations of the unknown graph G is important, since the optimization formulation does not take into account the sparsity of G. I fail to understand how different graph structures will affect the results of learning, and it seems like it should. If this is not important, I think the authors should discuss why it is not, especially since the learning is done on an underlying graph network.\n\n3) Instead of the sketch of the proof, I think more discussion on the comparison between the TVBP and the other methods is more valuable. The authors only discuss the difference in sample complexity, whereas it may be more valuable to discuss the different formulations used in independent BP, stepwise BP and the group lasso/GSP model. Otherwise, readers new to the field are not able to distinguish what is novel in this formulation of the TVBP.\n\nWith these added to the paper, I think the paper can be accepted.\n\nSome typos:\ni) line 84 - v \\in v should be v \\in V.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10 hours"}, "extra_text": {}}, {"review_id": "UQAinHFhLrP", "reviewer": "Reviewer_y67W", "summary": "This paper studies distributed (linear model) learning on heterogeneous data, e.g. federated learning, with the assumption of sparsity. Given a siilarity graph, it minimizes the l1 norm of the sparse model at a root node as well as the total variation along the graph paths. This work provides statistical analyses on the sample complexity by reformulating the problem as a basis pursuit denoising problem, and show that sample complexity is improved compared to previous works. A distributed ADMM algorithm is derived, and synthetic data experiments and application to hyperspectral unmixing are demonstrated.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is clearly written and well presented, but it could benefit from connecting the theoretical results to the synthetic data experiment results more. For example, comparing the phase transition diagram in Figure 1 to the sample complexity derived in Theorem 1 would be a nice way to demonstrate the soundness of the paper's theoretical claims, and similarly for the noisy setting.\n\nThis work seems sufficiently different from the existing hyperspectral unmixing methods that are based on total variation penalty, and if correct, the theoretical analysis would be of interest to many members of the learning community who work with sparsity assumptions and graph-based learning. However, there are a few questions I would like to get clarified:\n- The main concern about this method and its results is about the graph G. The paper claims that G does not have to accurately represent the similarity structure in the data, but that sounds counter-intuitive. Surely if the given graph is wrong (e.g. adversarial setting, complement graph), the method shouldn't work well? Is such adaptivity reflected in the derived bounds? G seems to only appear in the bound via diam(G), which is a function of G, but not a function of \"correctness of G\", which one might expect to see in such problem setting.\n- How is/should be G derived for real data?\n- At the end of section 3.2 - \"Although, we note that combining groups of pixels in this manner can cause the images to appear at a lower resolution.\" Could the authors explain why this is true? \n- What are other applications that the authors envision this work being used for, besides hyperspectral unmixing?\n- In section 2.1, \"For instance, in Hyperspectral Imaging we expect the composition of the ground to change by a few minerals when moving to an adjacent pixel.\" However, many hyperspectral unmixing methods assume the mineral composition vectors to sum to 1 (such that they can be interpreted as a probability/percentage vector). Are there ways to get around it?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "\"Specifically, the theorems can provide guidance on developing algorithms in the context of distributed machine learning and hyper-spectral imaging, which can have both negative and positive impacts.\" This is true, but it would be helpful to list a few of such potential impacts. For example, distributed machine learning has connections to privacy issues, and hyperspectral imaging to military operations.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: While the reviewers have pointed out several concerns regarding the paper, there seems to a consensus that this paper has merit. Everyone is placing this paper as a borderline candidate.  I will strongly suggest that the authors implement the suggestions given by the reviewers in the subsequent versions. 
Decision: Accept (Poster)