Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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.

This 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:
- 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.
- How is/should be G derived for real data?
- 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? 
- What are other applications that the authors envision this work being used for, besides hyperspectral unmixing?
- 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?
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_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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. 
main_review: Strength 
* The method proposed could be better than Group Lasso when the overlap between the signals’ supports is small.
* The paper provides provable guarantees and is generally well-written. 

Weakness
* 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.  
* 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. 
* The experimental results for hyperspectral imaging are not convincing and inconclusive. 
* 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.

Overall, 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. 

limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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.

Generally 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. 

1) 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.

2) 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.

3) 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.

With these added to the paper, I think the paper can be accepted.

Some typos:
i) line 84 - v \in v should be v \in V.
limitations_and_societal_impact: Yes
review_title: null

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)