Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: The authors present a distributed protocol for the column subset selection problem under the $\ell_p$ norms for $1\leq p <2$. The model of computation is a standard coordinator model of communication where the input matrix A is column partitioned to $s$ servers. The main contribution consists of a protocol that requires $O(sdk)$ communication, single round and polynomial running time and returns a $k^{1/p - 1/2}$ multiplicative approximation to the best possible column subset.

#### Reasons for score:
Overall, I vote for a borderline / slightly below acceptable but I am open to discussion about my decision. My main concerns are (a) the polynomial time complexity of the method makes the proposed protocol hard to be useful in real applications, and (b) the experimental evaluation is done on very small matrices (i.e., 2000 x 2000 shape) as well as small number of servers. On the positive side, the paper is a solid theoretical work on the distributed CSSP problem.

#### Strong points:
* Well written paper with a clear contribution statement
* Related work is up-to-date (to the best of my knowledge)
* Concise algorithm description and corresponding theoretical guarantees.


#### Concerns: 
* The polynomial running time guarantee makes the practicality of the proposed algorithm marginal. Do you (implicitly) assume that you have limited space per server as well? Please make such assumption explicit.
* Experimental section need sto be extended with larger datasets and more servers. How does the distributed protocol compares with a centralized one? The size of the datasets here suggest the following question.
* Why is the distributed setting is studied here? If the resulting algorithm is polynomial, why not solving the problem in a single server?

Minor comments:
* Explicitly state what is hidden under the notation $\tilde{O}$.
*Lemma 3: the probability constant $0.999$ seems arbitrary here, please replace it with $0<\delta<1$ failure probability parameter.
* Lemma $4$: What is a "sampling and reweighting matrix T"? Is this defined in the main text?
* After Theorem 5: give a reference to "Lewis weights".
* Before Section 5 (Runtime): Why generating a p-state random variable takes constant time?
* Is all communication bounds in bits?
* Figure 2 is not easy to read, please make it larger and increase the font on both axis.
review_title: Single Round Distributed CSSP

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper focused $\ell_p$-norm error analysis of distributed column subset selection problems. The proposed distributed algorithm guarantee an $\tilde O(k^{1/p-1/2} )$-approximation to the best subset of columns with $\tilde O(sdk)$ communication cost per round and polynomial time.  The lower bound analysis show that such communication complexity is near optimal. The design and analysis of the algorithm is based on f oblivious sketching and strong coresets, which leads to the overall approximation factor is only $\tilde O(k^{1/p-1/2} )$. The authors also extended the main idea to address $\ell_{1,2}$ norm error. 

I have not checked all details of the proof, but the results and the main ideas look reasonable. I think the theoretical contribution of this paper is valuable, however, the contents is somewhat limited to the audience of ICLR. There are some questions/comments:

1. I strongly encourage the authors apply the proposed algorithm to address the real-world problems such as computer vision, image processing which is mentioned in introduction.

2. Since the column select problem focus on the matrix $A\in\mathbb{R}^{d\times n}$ with $n\gg d$, the empirical studied should also contain such case. It is observed that proposed method performs better than SVD on both synthetic dataset and some real world dataset. I think one of the reason may be the $l_p$ norm for $1\leq p<2$ is not a unitary invariant norm and SVD do not give an optimal low-rank approximation. Hence, SVD may be not a good deterministic algorithm as baseline. 

3. The presentation could be improved: a) The operations on Server and coordinates should be described in multiple lines.  b) The curves in figure 2 should be displayed with different types of lines.
review_title: above acceptance threshold

final_score: rating: 7: Good paper, accept
review_content: SUMMARY:

The paper considers the column subset selection (CSS) problem, which has received considerable attention in numerical linear algebra. It considers a distributed variant of CSS in the $\ell_p$ norm, where $p \in [1,2)$. Despite the attention this problem has received previously, it seems like this is a new setting that has not been considered before. The paper primarily provides theoretical results, but also does some experiments. 

I think this is an interesting paper and problem. However, there are a few things I'd like to see addressed before I can give a higher score. There are a few details in the proof of Theorem 6 that are unclear. Moreover, the readability of the paper could be improved. I provide further details below.


ADVANTAGES:

- CSS is an important problem in numerical linear algebra.
- The setting under consideration seems to be new.
- The paper provides both theoretical and experimental results.


CONCERNS/QUESTIONS:

- Section 1 would be easier to follow if the definitions in Section 2.1 were given when the concepts are first used in Section 1 instead.

- The p-stable distribution is discussed throughout the paper, but doesn't seem to be defined anywhere, not even in the supplement. It would be helpful if the p-stable distribution was defined when it is first mentioned. Also, in the proof of Lemma 3.1, it would be helpful if you could point to a reference that contain the relevant facts about p-stable distributions.

- In Section 1.2, the first paragraph, you make a distinction between an approximation to OPT and an approximation to the best possible subset of columns. Can you clarify the distinction between these two types of approximation?

- The numbering of the lemmas is confusing. The numberings used in the main paper are reused in the supplement, but for different results. For example, Lemma 1 in the main paper is called Lemma 2 in the supplement, and Lemma 2 in the main paper is called Lemma 3 in the supplement. This makes the proof of Theorem 6 confusing.

- On the 4th line in Section 1.1., you say that the coordinator computes $\sum_i A_i S = A S$. But $A$ is of size $d \times n$, and each $A_i$ is of size $d \times n_i$, so this equality isn't right. Do you mean to say that $\sum_i \tilde{A}_i S = A S$, where each $\tilde{A}_i$ is of size $d \times n$ and with all entries zero except those columns corresponding to the columns in $A_i$ (or something to that effect)?

- In the proof of Theorem 6, when you apply Lemma 5 the first time: Don't you need both $V'$ and $M$ to be defined in terms of the $p,2$-norm rather than the $p$ norm for Lemma 5 to apply? In other words, should they be defined as 

$V' := \arg \min_V |S A_I V - S A|_{p,2}$ 

and 

$M := \arg \min_M | S A_I M - S A T |_{p,2}$?

- In the proof of Theorem 6, when you apply Alg. 4: It is not clear how Alg. 4 from the supplement is applied here. Alg. 4 outputs factors U, V such that UV approximates A. What is $(SAT)^*$? Is $(SAT)^* = UV$ here?

- In the proof of Theorem 6, when you apply Lemma 5 the second time: It looks like this uses the first equality in Lemma 5 in the supplement, which requires $P_2^*$ to be a projection matrix. How can we know that it is? Moreover, even if the sampling matrices $T_i$ are chosen to satisfy Lemma 5, how do we know that the matrix $T$ obtained from the $T_i$'s in Alg. 1 also satisfies Lemma 5?

- What is the run time of Algorithm 2? Does finding each $j^*$ require evaluating the objective for every choice of $j \in \overline{T}$, or is there a better way to do this?

- In Section 6, in the Setup paragraph, you say that you report the minimum error over 15 trials. Is there a reason for reporting the minimum rather than the mean or median? Is the mean/median also competitive?

- The paper ends abruptly with no conclusion.


MINOR CONCERNS/QUESTIONS:

- In the sentence right after Lemma 2 in the main paper, should $|S A_T V - S A_T|_p$ be $|S A_T V - S A|_p$?

- In Algorithm 2, should the argmin be over $j \in \overline{T}$ rather than $j \in A_{\bar{T}}$?

- In Tables 3, 4 and 5 of the supplement, should k-CSS_{!,2} be k-CSS_{1,2} (i.e., a '1' instead of an exclamation point)?


###################################

Update:

The authors have addressed the concerns I had in my initial review. I have raised the score from 6 to 7.
review_title: Review of An Efficient Protocol for Distributed Column Subset Selection in the Entrywise lp Norm

Meta-review: Clarity: Well written paper with a clear contribution statement; related work is up-to-date; concise algorithm description and corresponding theoretical guarantees. However, the presentation could be still improved.

Significance: The polynomial running time guarantee makes the practicality of the proposed algorithm marginal. Experimental results do not back up strongly the significance of the algorithm.

Main pros:
- Solid theoretical work on the distributed CSSP problem.

Main cons:
- The reviewers point out the significance of the experimental results, beyond the theoretical contribution. For the ICLR audience, real, large-scale experiments, that really dictate that the proposed solutions is (if not the only) one of the few solutions to follow, are necessary. The reviewers highlight that the theoretical results need to be applied to really large-scale scenarios (e.g., the problems considered in the paper can definitely be handled by a single computer, and no distributed implementation is required). 
- Τhe polynomial time complexity of the method makes the proposed protocol hard to be useful in real applications.
- How does the distributed protocol compares with a centralized one? This is not fully addressed in the rebuttal. 
Decision: Reject