Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: There is a growing interest in vertical federated learning where each party only store a subset of features due to its various important applications. This paper studies how to make vertical federated learning more efficient. It proposed to apply compression to the embeddings shared periodically. Compression has been well studied for reducing the network traffic for synchronizing gradient but there is little study in compressing embeddings. This paper shows that the convergence is guaranteed if the compression errors diminish at the same rate as the learning rate. The experimental results show that the vector quantizer produces the same accuracy as the full-precision counterpart while significantly reducing the communication costs.
main_review: This paper studies an interesting and important problem. Frequent communication across different parties is expensive and it is natural to consider using local iterations. But compressing embeddings is not well studied and it was not clear how it affect the convergence. Overall, the paper is well written but it lacks of more detailed description of the compression methods it considers. Table 1 gives the error bound for scalar quantizer, vector quantizer, and top-k sparsification but the their algorithmic details are omitted. Though I think the paper is interesting, but I have some questions regarding theory:

1. The update of $\theta_m^t$ depends on the mini-batch $B$. How can we say that the gradient is conditionally unbiased for any $t > t_0$? Especially, the RHS of (7) still depends on the realization of $B$. This a critical prerequisite for establishing the convergence in the paper.
2. The bound (8) in Lemma 1 increases linearly with the mini-batch size, which is loose.
3. How do we select the compressor so that compression error decreases at the same rate as the learning rate? This is crucial to ensure the convergence but there is no discussion.
4. Error bound (9) has a quadratic dependency on the number of parties $M$, which also seems loose to me.
5. It is good to provide a reference convergence bound for the case where the compression is not adopted.
summary_of_the_review: This paper studied an important problem, but the theoretical results are not convincing.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This work studies the problem of communication-efficient training on vertically partitioned data and it is relevant to the conference. The paper provides the theoretical analysis of the effect message compression has on distributed training over vertically partitioned data, and prove convergence of non-convex objectives to a fixed point at a rate of O($1/\sqrt{T}$) when the compression error is bounded over the course of training. Experimental validation is provided to show compression can reduce communication by over 90% without a significant decrease in accuracy over VFL without compression. 	

main_review: The main contribution of this paper is to offer the theoretical analysis of the effect message compression has on distributed training over vertically partitioned data, and prove convergence of non-convex objectives. This result is from a recent line of research that has been studied for a while. For example, Richtarik & Takac (2016); Hardy et al. (2017) were the first works to propose Federated Learning algorithms for vertically partitioned data. This work extended it to consider multiple local iterations, whose contribution is considered incremental. 
 
The numerical experiment considered is also not enough, for example, the setup consists of four parties and a server. Even if we have real world examples of collaboration between a few institutions, such an experiment is still considered limited. The dataset used in the paper is also limited and small. 



summary_of_the_review: In short, the paper is technically sound and the developments are clear. The derived analysis under non-convex objectives seems to be a useful contribution to the literature, showing a modest improvement over the state of the art. ​However, the paper is still not novel enough based on several existing works and could be strengthened by demonstrating more significant results instead of incremental, such as weaker conditions.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a communication-efficient training algorithm for vertical federated learning (VFL). It compresses the embeddings (clients) and parameters (the server) to save communication, what’s more, it also performs multiple local epochs to save more communication. Then it proves convergence rate of O(1/{T}^0.5) for the proposed algorithm. Finally, it provides some empirical results for validation.
main_review: Strengths:
Communication is one of the major bottlenecks in Federated Learning, though the problem is less severe for the VFL compared to HFL for it only transfers embeddings. It may need a communication efficient algorithm as the embeddings may be in very high dimension. The paper also provides theoretical analysis of the algorithm and proves the algorithm can achieve the normal SGD-style convergence rate. The experiments also show that the algorithm can reduce the communication cost compared to the vanilla VFL algorithm.

Weakness:
There are some questions to be answered:
1.	What’s your assumption about label ownership, it seems that every client requires access to label y? This is not realistic in practice. The VFL typically avoids such situation.
2.	You mentioned that unbiasedness is maintained even if the client uses the same batch of samples during the whole local training, this is not self-evident. In eq.(7), I agree the equality holds for the step $t_0 +1$, what about $t > t_0 + 1$? Since the previous state $\Phi_m^{t-1}$ relies on the batch $B$, how can we get the equality?
3.	The experimental results (Fig.2) show that the proposed algorithm reduces total communication, however this is not obvious theoretically. As shown in the analysis, the compression error needs to approach 0 as $T$ increase, which means that the transferred dimension aproaches $P_m$. So can you provide some analysis of the total communication cost? does it save a constant factor of communication or with a larger factor?


summary_of_the_review: The paper studies an interesting problem. The proposed algorithm attains theoretical guarantees, and its performance is also empirically validated. However, there are still some questions requiring more discussion.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: compression applied on vertical federated learning problems
main_review: ## PAPER SUMMARY

This paper presents a new vertical federated learning algorithm that supports compression, in order to save communication cost in practice.
In particular, this paper proves that the proposed algorithm converges with a similar rate as the original algorithm without compression.
In vertical federated learning, each party involved does not have all the features, but only a subset of them.

The compression technique can be various, including top-k sparsification and quantization.

The compression error has to be diminishing along the training process.

## NOVELTY & SIGNIFICANCE

Applying compression on activation of some layers of a neural network while keeping the convergence rate has been studied in different scenarios for a while.  This includes model parallelism (the split learning referenced in this paper and the vertical federated learning problems are both special case of general model parallelism).

How such compression techniques work in the context of vertical federated learning is still not well studied yet. I appreciate the authors' work to actually show the convergence and experimental results.

## TECHNICAL SOUNDNESS

Since the compression error goes to zero along the training process, the error coming from stochastic gradients dominates and the convergence should be similar to ordinary stochastic gradient algorithm asymptotically.

Assumption 5 assumes a bounded gradient, which seems to be a bit strong to me (many existing compressed stochastic algorithms do not need such bounded gradient assumptions).

## OTHERS

Experiments look fine. The reference list format needs to be fixed (not consistent now).

summary_of_the_review: An incremental work, by applying compression on vertical federated learning algorithm. The theoretical analysis follows existing compression stochastic algorithms' analysis (where the compression error eventually goes to zero).
review_title: null

Meta-review: Reviewers have all agreed that this paper studied an important problem and made valuable contributions. The goal is to reduce the communication costs  of Federated learning where the data are stored in different parities based on subsets of features.  The paper developed the theory to show guaranteed convergence and provided empirical evaluations to validate the theory.  

On the other hand, compared with existing literature, Reviewers feel that the novelty of this submission appears limited and the improvements seem to be incremental. Reviewers appreciate the Authors' efforts in conducting the detailed rebuttals and providing an improved manuscript. We hope the authors would continue to improve the paper based on reviews, when they prepare for their future submission.
Decision: Reject