Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This work considers how to subsample the datasets via coresets under the vertical federated learning (VFL) setting. By doing so, the communication cost of VFL algorithms can be sharply reduced. The authors first introduced a unified coreset construction algorithm in VFL, which requests an importance value for each sample, and then proposed how to estimate the importance values for regularized linear regression and k-means clustering, respectively. Experimental results show that the proposed algorithms can reduce the communication complexity without harming the model performance significantly. 
strengths_and_weaknesses: ## Strengths
Overall, this is a solid work for me. The techniques are well introduced and the paper is easy to follow. Although the authors made two ideal assumptions when proposing algorithms for regularized linear regression and k-means clustering, they also provided the theoretical analysis when the assumptions are not satisfied. The experimental results are positive: the proposed algorithms work well when using less than 4% of the training data. 
## Weakness
Privacy is an important issue in VFL, but the authors did not analyze the privacy of the proposed algorithms. And the experimental results can be explained more in-depth. 

questions: ## Definition
How is the cost evaluated in Section 6? In Definition 2.3 and Definition 2.4, the cost is evaluated on the coresets (i.e. $\sum_{I \in S}$). However, in my opinion, although the models are trained/computed on the coresets, the cost should be evaluated on the entire dataset (i.e., $\sum_{I \in \[n\]}$) when assessing the performance.

## Privacy analysis
I suggest the authors discuss the privacy of the proposed algorithms. To be specific, analyze what can be leaked from the messages transmitted in Algorithm 1. I also suggest the authors clarify the security assumption. It seems the server and clients are assumed to be semi-honest. But when they become malicious, is the proposed algorithm safe? 

## Experiments
How does the CENTRAL baseline solve the ridge regression problem? Does it solve by the closed-form solution (i.e., $(X^TX + \lambda I)^{-1} X^T y$) or gradient descent? If by the closed-form solution, how does it solve the Lasso regression and elastic nets in Appendix A.2? 

In Table 1, why the communication complexity of C-SAGA decreases w.r.t. the size of coresets? As indicated by Theorem 2.5, the communication complexity should be $\Omega(mT)$ where $m$ is related to the size of coresets. 

Moreover, I suggest the authors report the communication of coreset construction and model training, respectively. It would help readers understand the overhead of your method. 

## Some other points
- The caption of Figure 1 is missing.
- The term “robust coreset” is not introduced. 
- In many previous VFL studies, there is no such a central server. However, it seems the central server can be substituted by Party T in Algorithm 1, so it looks good to me. 

limitations: The authors have discussed future directions in Section 7.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper gives a unified framework to construct coresets for the regularized regression and k-means clustering  in the vertical federated learning setting where the features of the data are distributed over multiple parties. The aim is to make the communication complexity sublinear in the no. of data points. The high level idea is to calculate local sensitivities for points at each party and then use them to sample points at each party. Finally take a union of these samples. The main contribution is to show that this intuitive technique gives a coreset with much lower communication complexity  under some assumptions on the data. When there are no assumptions, the authors also give some lower bounds. The authors also validate their theoretical claims with empirical results on real world dataset.
strengths_and_weaknesses: Strengths:
1) The use of coresets in the VFL setting to reduce communication complexity, to the best of my knowledge is novel. It is an important and interesting application.
2) The idea is simple and intuitive
3) The theory and the proofs appear sound and correct. I didnot go through the proofs in the appendix in details but had a quick look.
4) Empirical evaluations validate theoretical claims in terms of the cost.

Weaknesses:
1)The writing is sloppy at a few places. Blelow are a few examples:
        i)Line 22: "Most of the VFL literature focus on the privacy issue, and design secure..." should be and designing. 
        ii) Line 66 "how to defend again" should be against. 
        iii) Line 68 last sentence is not proper.
        iv)Algorithm 1, line 3 summation should be over j.
2) I could not find the details of the hardware system used for the implementation. Was it really a distributed set up or was the data just broken into parts and experiments were done on single system?
3) Most of the proof techniques(other than lower bounds) and the coreset construction techniques  are very well known in literature and there is lack of novelty in that sense.
4) The remarks regarding robust coresets are given without even the definiton of robust coreset in the main paper. I believe atleast the definition and some intuition/discussion as to why the robust coresets are possible without assumptions should be in main body otherwise the main paper becomes less readable.
questions: Please clarify the following questions
1) Will the results for regularized regression also extend to the setting when the data matrix is low rank? Is there any assumption here that data is full rank? Also the theoretical results hold for linear regression( no regularization) also? you have already shown some empirical results in appendix.
2) Instead of giving the calculated values of communication complexity in the graphs, is it possible to compute time required for the communication in the experimental setup?

limitations: Please see the weaknesses/ questions section. Also please do a complete proof reading and try to make some sentence constructions better.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper forges a link between vertical federated learning where the attributes of the data are spread along multiple machines, to coresets - a data summarization that approximates the cost of every query on the data.
Specifically speaking, they focus on the problems of k-means and least mean squares regression.

The main idea is to reduce the communication complexity of an algorithm by computing a coreset for the distributed data - to do so, the authors extend the framework of importance (sensitivity) sampling to the vertical federated learning settings; see Algorithm 1 and Theorem 3.1.

Focusing on Least squares regression the authors demonstrate that it is often challenging to build a "strong" (for every query) coreset for VRLR - the lower bound on the communication complexity is Ω(n).
Then, they show how under a loose assumption, this can be done efficiently. According to this presumption, the subspace produced by data on any one party should not be entirely contained inside the subspace produced by other parties. Under such an assumption, one can get a coreset of size-independent from n, polynomial in the dimension d, and the appropriation error.

The same scenario hold for k-means - which requires a communication complexity Ω(n). However, assuming any two data points that may be differentiated can also be differed on a party that is "important" to some amount.

Finally, experimental results show that coresets reduce the communication complexity and maintain a good quality solution.

strengths_and_weaknesses: I like the paper, mainly, the idea of using coreset in this new realm. The ideas are very interesting, and the findings are robust.



Some comments and questions:
1. Theorem 3.1 - S, W is not defined in the theorem.
2. The empirical results are good but can be extended, e.g., 1. try on a larger number of parties, other datasets, and more.
3. Please define (or at least explain) a robust coreset in the manuscript.
questions: 

Can you please explain (intuitively) the relation between $\gamma$ in Theorem 4.2 to the parameter which represents the maximum sensitivity gap overall points. Same for \tau in Theorem 5.2.


Can you give please more details about the parameter which represents the maximum sensitivity gap, how is it related to the data e.g., in linear regression?
limitations: The coreset requires a specific assumption on the data (that may not be satisfied in real-world).
review_title: null

Meta-review: metareview: The reviewers have converged around the idea that the paper proposes an interesting approach to vertical federated learning; they also conclude that the authors have provided replies to reviews that answered questions and provided useful clarifications, which encourages the acceptance of the paper. 

I will stress the need for the authors to properly include further updates for the camera ready version of the paper; in their reply, they indeed make several promises to reviewers and it is important that such updates be properly included (last comment to NZai, intermediary comment to XK2T).
confidence: Less certain
Decision: Accept