RVFR: ROBUST VERTICAL FEDERATED LEARNING
Year: 2021

Abstract:
Vertical Federated Learning (VFL) is a distributed learning paradigm that allows multiple agents to jointly train a global model when each agent holds a different subset of features for the same sample(s). VFL is known to be vulnerable to backdoor attacks, where data from malicious agents are manipulated during training, and vulnerable to inference-phase attacks, where malicious agents manipulate the test data. However, unlike the standard horizontal federated learning, improving the robustness of VFL remains challenging, as there is no clear redundancy among the agents in VFL. To this end, we propose RVFR, a novel robust VFL training and inference framework. Under certain conditions, RVFR can recover the underlying uncorrupted features with provable guarantees and thus sanitizes the model against a vast range of backdoor attacks. Further, RVFR also defends against inferencephase adversarial and missing feature attacks. We conduct extensive experiments on NUS-WIDE and CIFAR-10 datasets and show that RVFR outperforms different baselines in terms of robustness against diverse types of attacks.

heading: 1 INTRODUCTION
text: Federated Learning (FL) involves distributed training where a central server coordinates with multiple agents to collaboratively train a machine learning model, and the agents keep their own training data, e.g., due to privacy concerns. The theory and practice of FL has progressed rapidly in recent years (Konečnỳ et al., 2016; McMahan et al., 2017; Bonawitz et al., 2017; Dayan et al., 2021). Two broad categories (Yang et al., 2019) of FL are Horizontal FL (HFL) and Vertical FL (VFL). In HFL, each agent has a different training set, while in VFL (Liu et al., 2019; Chen et al., 2020; Liu et al., 2020), different agents hold different parts of features for the same set of training data. For example, in VFL for credit score prediction, Agent 1 may have the banking data of a user and Agent 2 may have the shopping history of the same user, while the server holds corresponding labels.
Given the distributed training, FL raises new security concerns as the server has less control of the training data and agent devices. A variety of attacks have been demonstrated on HFL and on VFL. Several studies have focused on making HFL more robust, wherein each agent sends the model updates based on local data to the server and the server aggregates these updates. Robust aggregation protocols have been proposed as defenses in HFL against malicious attacks (Yin et al., 2018; Guerraoui et al., 2018; Blanchard et al., 2017; Fu et al., 2019; Pillutla et al., 2019; Fung et al., 2020; Chen et al., 2017; Xie et al., 2019b). However, it is challenging to defend against malicious attacks in VFL, as there is no clear redundancy among the agents. In fact, there are few studies on robustness exploration for VFL.
In this paper, we propose a robust VFL training and inference framework via feature subspace recovery (RVFR), which is able to defend against many types of attacks during both training and inference (see the attack taxonomy in Section 4.1). In particular, during training, we propose to train each agent’s feature extractor separately based on feedback from the server (Quarantine training stage); the server then performs robust feature subspace recovery given the embedded features provided by different agents (Robust feature subspace recovery stage); and the server further purifies the features based on the assumption that the fraction of malicious agents is relatively small (Feature purifying stage). Finally, the server trains its global model based on the purified features (Server training stage). An overview of the training process is illustrated in Figure 1. During the inference phase, the server first purifies the embedded features provided by the agents and then feeds it to the trained global model for prediction. Building upon our framework, we aim to answer the following
questions: Is it possible to train a clean model with theoretical guarantees in the presence of poisoned features? Can we make predictions based on incomplete (corrupted) features? If yes, how many malicious agents/instances and missing features can we tolerate?
Under the RVFR framework, in the robust feature subspace recovery stage, we propose a variant of the Robust AutoEncoder (Zhou & Paffenroth, 2017) to recover the feature subspace. While the existing Robust AutoEncoder has no theoretical justification, we provide theoretical support for it by proving that when the underlying feature subspace is linear, it can exactly recover the linear feature subspace in the presence of corruption/poisoning. In the feature purifying stage (during both training and inference), we propose a novel AutoEncoder-based robust decomposition method that decomposes the potentially corrupted feature vectors into two parts: one lies on the learnt feature subspace (can be non-linear); and the other contains a block-sparse structure. We theoretically show that under certain conditions, the proposed method can recover the underlying feature vector exactly despite corruption from malicious agents.
Technical Contributions: We take a first step towards providing robust VFL against diverse adversarial attacks during both training and inference. Our main contributions include the following:
• We propose a novel robust training procedure to defend against backdoor attacks in VFL, and prove that under certain conditions it can exactly recover the underlying uncorrupted features. To the best of our knowledge, this is the first defense for VFL against training attacks with theoretical guarantees. • We provide the first theoretical justification for the Robust AutoEncoder, which may be of independent interest. • We propose a robust VFL inference procedure to defend against a variety of targeted or untargeted attacks (e.g., adversarial and missing feature attacks). To our knowledge, this is the first defense for VFL against inference-phase attacks with theoretical guarantees. • We conduct extensive experiments on NUS-WIDE and CIFAR-10 datasets, and show that RVFR is significantly more robust than baselines against diverse types of attacks.

heading: 2 RELATED WORK
text: In this section, we briefly review prior work on backdoor attacks and defenses in different types of federated learning frameworks.
Backdoor attack and defense in Horizontal Federated Learning. Many recent works, e.g., Bhagoji et al. (2019); Bagdasaryan et al. (2020); Wang et al. (2020); Xie et al. (2019a), have demonstrated the vulnerability of HFL to backdoor attacks. For instance, Bhagoji et al.; Bagdasaryan et al. show that training poisoned local models and submit malicious model updates to the server can mislead the global model effectively. While Xie et al. exploits the distributed nature of HFL and propose a distributed backdoor attack.
To defend against backdoor attacks in HFL, several robust federated protocols are proposed to mitigate the attacks during training empirically. For example, Sun et al. shows that clipping the norm of model
updates and adding Gaussian noise can mitigate backdoor attacks. Andreina et al. incorporates an additional validation phase to each round of FL to detect backdoor. To provide certain robustness guarantees, some robust aggregation methods are proposed (Yin et al., 2018; Guerraoui et al., 2018; Blanchard et al., 2017; Fu et al., 2019; Pillutla et al., 2019; Fung et al., 2020; Chen et al., 2017; Xie et al., 2019b); while such robustness guarantees are not for backdoor attacks directly. Recently, Cao et al. proposes Ensemble FL to defend against backdoor attacks with certifiable robustness. However, the proposed majority voting strategy requires training hundreds of FL models. A recent work exploits model clipping and smoothing in HFL, aiming to provide certified robustness to backdoor attacks (Xie et al., 2021). However, none of these works can provide robustness guarantees on the learned feature subspace of the server model, which is the focus of our work.
Backdoor attack and defense in Vertical Federated Learning. Backdoor attack against VFL is challenging since in the typical setting (Chen et al., 2020) the agent does not have the label information. Recent studies assume that the malicious agent knows at least one training instance belonging to the target class (Liu et al., 2020). Under this assumption, they propose the gradient-replacement method to perform backdoor attack. Some defense strategies are proposed against such attacks in VFL, e.g., sparsify the intermediate gradient before sending to the server (Liu et al., 2020). However, there is no work providing any robustness certification against backdoor attacks in VFL to our best knowledge.

heading: 3 PRELIMINARIES
text: Vertical Federated Learning. We first describe the basic setup of a typical VFL framework (Chen et al., 2020; Liu et al., 2020). There are M agents and a server collaboratively training a machine learning model based on a set of n training data D , {x{j}1 , ...,x {j} M , y
{j}}nj=1. The server (e.g., a third party) holds the label y{j}, while agent i holds partial feature x{j}i of instance x {j} , [x {j} 1 ; ...;x {j} M ]. Due to privacy concerns, the raw agent data x {j} i are not shared with other agents and the server. Instead, each agent i learns a local embedding gi parameterized by θi that maps the original feature vector x{j}i to feature vector h {j} i , gi(x {j} i ; θi). The dimension of h {j} i is usually smaller than x{j}i . The server only has access to the embedded features from the agents. The learning objective of VFL is to minimize the following loss:
L(D; θ0, θ1, ..., θM ) = 1
n n∑ j=1 `(ŷ{j}, y{j}) + M∑ i=1 γ(θi), (1)
where ŷ{j} = fθ0(h {j} 1 , ...,h {j} M ) , fθ0 ( g1(x {j} 1 ; θ1), ..., gM (x {j} M ; θM ) ) , and fθ0 is the global
model of server. ` is the loss function and γ is the regularizer that confines the model complexity.
Robust Subspace Recovery. Robust subspace recovery aims to recover the underlying subspace of data despite that some data points are arbitrarily corrupted (a.k.a. outliers). Mathematically, one observes a data matrix H , where each column corresponds to a data point. We can decompose H as L + E, where L is the underlying uncorrupted data matrix, and the matrix E models the outlier corruptions. Since the fraction of the outliers is usually small, most columns of E are zero, i.e., E is column-sparse.
Assume the underlying uncorrupted data points lie on a low-dimensional linear subspace, one of the notable Robust PCA works (Xu et al., 2012) showed that it is possible to recover the column-space of L exactly by solving the following convex optimization:
min L,E ‖L‖∗ + λ‖ET ‖2,1 s.t.H = L + E. (2)
Later we will see that in our proposed RVFR framework, H = [ h{1}, ...,h{n} ] , where the j-th
column of H corresponds to the embedded features for the j-th instance. In the backdoor attack, a few columns of H are poisoned. In general the low-dimensional manifold that the embedded features L lies on is not linear, and we use a Robust AutoEncoder instead of Robust PCA to capture this non-linearity. We will show that Robust PCA can be viewed as a linearized version of the proposed Robust AutoEncoder, and we will provide theoretical justification for it.
Formally, the Robust PCA result from Xu et al. (2012) is as follows: Theorem 1. (Exact subspace recovery (Xu et al., 2012)) Suppose we observe H = L∗ + E∗, where L∗ has rank r and incoherence parameter µ (see Definition 1 in Appendix A.2). Suppose
further that E∗ is supported on at most βn columns. Any output to Eq. 2 recovers the column space of L∗ exactly, as long as the fraction of corrupted columns, β, satisfies β1−β ≤ c1 µr , where c1 = 9/121. This can be achieved by setting the parameter λ in Eq. 2 to be 3 7 √ βn
(in fact it holds for any λ in a certain range).
Inspired by the Robust PCA properties, we propose the Robust AutoEncoder in this work, which can capture the more general non-linear manifold. So far there is no theoretical guarantees for Robust AutoEncoders. The proposed Robust AutoEncoder is slightly different from an existing one (Zhou & Paffenroth, 2017), and we theoretically justify the proposed one by showing that when the underlying feature subspace is linear, after transformation based on the proposed Robust AutoEncoder, it exactly recovers the linear feature subspace as Robust PCA. Note that our established connection between the proposed Robust AutoEncoder and Robust PCA is non-trivial, especially due to the proposed `2,1-norm regularizer on the latent layer.
Note that the exact recovery of the feature subspace is not enough for our goal of robust VFL, and we need to recover the underlying L∗. We further propose a robust decomposition technique to recover L∗ exactly by utilizing our learnt feature subspace based on the assumption that the fraction of malicious agents is small. More details can be found in Theorem 3.

heading: 4 ROBUST VFL VIA FEATURE SUBSPACE RECOVERY (RVFR)
text: We first describe the threat models during VFL training and inference, and then present the training and inference procedures of the proposed RVFR framework.

heading: 4.1 THREAT MODEL
text: There are M agents which hold different parts of the feature of the same set of instances, and the label y is held by the server. The attacker knows the feature information held by every agent and the label information on the server, but it can only choose and control αM agents to perform malicious attacks. During training, the goal of the malicious agents is to perform backdoor attacks, i.e., to achieve high accuracy on both the original main task and the targeted backdoor tasks.
Training phase threat model (backdoor attack): There are α fraction of agents that are malicious, and total β fraction of instances with backdoor trigger. With the adversarial target yA, the backdoor attacks are conducted by optimizing the following objective for the instances with backdoor trigger:
min hB
`(fθB ({hB ,hbenign}), y A),where θB = arg min
θ∈Θ ∑ j `(fθ(h {j}), y{j}), (3)
here hB represents overall embedded features provided by the malicious agents for the instance with backdoor trigger, its magnitude can be arbitrarily large unless regularized by the server; while hbenign denotes the overall embedded features provided by benign agents. If j-th instance has backdoor trigger, h{j} contains hB .
During inference, the malicious agents can perform adversarial attacks as well. Assume the total number of agents is M , and the fraction of malicious agents is α. We use hbenign to denote the embedded features provided by the (1−α)M benign agents (these agents are indexed by Ωbenign and |Ωbenign| = (1− α)M ), and we use hadv to denote the embedded features provided by malicious agents (indexed by Ωadv). We categorize the inference phase attacks into the following three types:
Inference phase threat model A (adversarial attack): The malicious agents aim to send adversarial features hadv to mislead the prediction, whose magnitude can be arbitrarily large unless regularized by the server:
min hadv
`(fθ0({hadv,hbenign}), y A), (4)
Inference phase threat model B (missing-feature attack): On the other hand, the malicious agents also have the option to NOT provide any features to the server. Such missing feature attack can make the malicious agents less detectable and still influence server’s prediction. The presence of missing feature attack can be viewed as that the server only observes partial blocks indexed by Ω of the overall embedded features h, i.e., hΩ. We use Ωc to denote the index set of agents that perform missing feature attacks. The attacker can compromise arbitrary αM agents.
min Ωc
`(fθ0(hΩ), y A), s.t. |Ωc| ≤ αM (5)
Inference phase threat model C (combined attack): The attackers can also perform a combined attack of the adversarial and missing feature attacks:
min Ωc, hadv
`(fθ0({hadv,hbenign}Ω), y A), s.t. |Ωc|+ |Ωadv| ≤ αM (6)
Besides above mentioned targeted attacks, the attacker can also perform untargeted attacks by maximizing the distance between the prediction and the ground truth, which should be easier and here we focus on defending these strong targeted attacks.

heading: 4.2 TRAINING PROCEDURES OF RVFR
text: The proposed training procedure has four stages: quarantine training, robust feature subspace recovery, feature purifying, and server training.
Stage 1 (Quarantined training): In VFL, the server trains the combined ML model, and each agent trains its local feature extractor. A strong adversary could interfere with the server training and further propagate errors to benign agents. So we propose that the server first connects to each agent separately to train the feature extractors gi parameterized by θi, i = 1, ...,M . The training can be viewed as a special case of (Chen et al., 2020, Algorithm 1) with only one agent.
In particular, agent i sends h{j}i , gi(x {j} i ; θi) to the server. The server uses it to update/train a temporary global model (whose input dimension equals that of h{j}i ) with learning rate η0 and batch size B0. Then the server calculates ∂`
∂h {j} i
and sends it back to agent i. The benign agent i
updates its local feature extractor parameterized by θi using the combined gradient ∂` ∂h {j} i
∂h {j} i
∂θi with
learning rate ηi and batch size Bi. After a number of iterations between the server and agent i, the server records the final embedded feature h{j}i for every instance x {j} i , j = 1, ..., n. Finally, for each instance x{j}, the server holds {h{j}1 ,h {j} 2 , ...,h {j} M } from all the M agents, and concatenates them
into a long column vector h{j}. Let H = [ h{1}, ...,h{n} ] , the j-th column of H corresponds to the concatenated embeded features for the j-th instance.
Stage 2 (Robust feature subspace recovery): Since the fraction β of the backdoored training instances is small, this provides us the redundancy across instances for robustifying the server’s model. In this stage, the server disconnects from all the agents, and uses H to train a Robust AutoEncoder by minimizing the following objective:
min L,E,φ,ψ
‖Eψ(L)‖2,1 + λ‖ET ‖2,1 s.t.H = L + E, L = Dφ(Eψ(L)) (7)
where L models the underlying feature subspace, and E models the outlier corruptions due to backdoor attacks. In Eq. 7, we only enforce E to be column-sparse. Dφ is the decoder parameterized by φ, and Eψ is the encoder parameterized by ψ. Note that Eq. 7 is equivalent to the following:
min L,φ,ψ
‖Eψ(L)‖2,1 + λ‖(H −L)T ‖2,1 s.t. L = Dφ(Eψ(L)) (8)
In practice, we further relax the constraint L = Dφ(Eψ(L)) and solve the following instead:
min L,φ,ψ
‖Eψ(L)‖2,1 + λ‖(H −L)T ‖2,1 + η‖L−Dφ(Eψ(L))‖2F (9)
To optimize this, one can perform alternating optimization for L and parameters of φ and ψ.
Stage 3 (Feature purifying based on the recovered feature subspace): Recovering the feature subspace is not enough to achieve robust VFL, as we need to recover the original features to train the server. Fortunately, there is another important prior information that we can leverage: the fraction α of the malicious agents is small. For each training instance h{j}, we use the learned AutoEncoder to decompose it as h{j} = Dφ(Eψ(l{j})) + e{j}, where e{j} models the block-sparse corruptions (each block corresponds to an agent). Ideally we want to solve the following:
min l,e M∑ i=1 1{ei 6= 0} s.t. h = Dφ(Eψ(l)) + e (10)
which is equivalent to: min
l M∑ i=1 1{[h−Dφ(Eψ(l))]i 6= 0} (11)
However, the above block-sparsity minimization objective is NP-Complete, so we relax it to the `2,1-norm:
min l M∑ i=1 ‖[h−Dφ(Eψ(l))]i‖2 (12)
Our theoretical analysis in next section shows that under certain conditions, solving the above relaxed objective is able to recover the underlying true features.
Stage 4 (Server training): The server trains its own global model parameterized by θ0 based on the above purified features Dφ(Eψ(l)), with learning rate η0 and batch size B0.

heading: 4.3 INFERENCE PROCEDURES OF RVFR
text: We propose an all-in-one solution to defend against both training phase and inference phase malicious attacks defined in Section 4.1, and thus during inference we will also perform feature purifying using the recovered feature subspace and the sparse nature of the malicious agents.
Let Ω be the index set of the observed agent blocks. Assume we have successfully trained the AutoEncoder, such that we have l = Dφ(Eψ(l)), where l is any uncorrupted embedded feature vector. We want to use the AutoEncoder to decompose the observed hΩ as hΩ = lΩ + eΩ with l = Dφ(Eψ(l)), where eΩ models the block-sparse corruptions (each block corresponds to an agent) on the observed set Ω. Note that if all the blocks (agents) are observed, Ω becomes the whole set. Since eΩ is block-sparse, similar to the feature purifying during training, we naturally aim to solve the following:
min l ∑ i∈Ω 1{[h−Dφ(Eψ(l))]i 6= 0} (13)
However, the above block-sparsity minimization objective is NP-Complete, we instead relax it to the `2,1-norm:
min l ∑ i∈Ω ‖[h−Dφ(Eψ(l))]i‖2 (14)
Our theoretical analysis in Theorems 3 & 4 show that under certain conditions, solving the above relaxed objective is able to recover the underlying true features, despite the partial observations. After obtained l̂, we feed Dφ(Eψ(l̂)) to server’s trained machine learning model for the prediction.

heading: 5 THEORETICAL ANALYSIS OF RVFR
text: We first analyze the proposed Robust AutoEncoder, which is the backbone of the proposed defense framework. Then, we prove that the proposed feature purifying method can recover the underlying features exactly under certain conditions, which means that the server’s global model can be both trained and tested on correct features, and thus is robust against diverse types of attacks.
The Robust AutoEncoder can be viewed as the generalization of Robust PCA, where the lowdimensional linear subspace is extended to the more general low-dimensional manifold. It is challenging to prove the exact recovery of the low-dimensional manifold in the presence of outlier corruptions. However, we next show that when the underlying feature subspace is linear, the Robust AutoEncoder can exactly recover the underlying subspace.
Theorem 2. (Exact subspace recovery) Assume l∗{i} ∈ Rd, i = 1, ..., n lie on a low-dimension subspace, i.e., rank(L∗) = r d. For the AutoEncoder, assume linear activation functions and no bias terms, while setting the dimension of the latent layer of AutoEncoder as r = rank(L∗) and restricting the weight matrices to be orthonormal. Then under the conditions in Theorem 1, the global optimal solution of Eq. 7 is equivalent to the solution of Eq. 2, and the corresponding weight matrix of the encoder is guaranteed to recover the subspace of L∗ exactly.
The proof is omitted to Appendix A.3. The key is to show that the objective value of Eq. 7 is greater than or equal to the objective value of Eq. 2, with equality achieved when the weight matrix of the encoder equals the top-r left singular vectors of L. This is non-trivial especially due to the proposed `2,1-norm regularizer on the latent layer of the Robust AutoEncoder.
Remark 1. The conditions required in Theorem 2 provide some useful insights. First, the total fraction β of poisoned instances needs to be small. Second, the dimension of the underlying feature subspace needs to be small. If the dimension of the feature subspace is too large, it is difficult to distinguish corrupted features from the uncorrupted ones. On the other hand, low dimensionality implies that there is enough redundancy among the features among agents, which is preferred since redundancy provides more robustness. Third, as discussed in Appendix A.2 regarding the incoherence condition, preferring small incoherence parameters implies that we do not want any dimension of the feature subspace to be defined by very few data points. Otherwise, it is risky if those instances are poisoned, as it becomes impossible to recover that dimension.
Note that exact recovery of the subspace does not mean exact recovery of L. For the corrupted/poisoned instances, usually it is impossible to restore them as the corruptions can be arbitrary. Fortunately, once we have recovered the underlying feature subspace, it is possible to recover the original features exactly by utilizing the sparseness of the malicious agents. This holds for both training and inference phases. The following theorem shows that we can recover the underlying embedded features exactly against the inference phase threat models A & C.
Theorem 3. (Exact feature recovery under threat model A & C) Let Wend be the weight matrix of the last layer of the AutoEncoder. Assume there is no bias term nor non-linear activation function in the last layer. Assume the trained AutoEncoder captures the underlying feature subspace (i.e., Dφ(Eψ(l)) = l for uncorrupted feature vector l). Let Ω be the index set of the observed blocks (agents). If ∀v ∈ Range(Wend)\0, for any partition {SΩ, S̄Ω} of Ω with |SΩ| = g > |Ω|/2, it holds that ∑ i∈SΩ ‖vi‖2 > ∑ i∈S̄Ω ‖vi‖2, then for any hΩ = l ∗ Ω + e ∗ Ω with Dφ(Eψ(l∗)) = l∗ and∑
i∈Ω 1{e∗i = 0} ≥ g, Dφ(Eψ(l∗)) is the unique solution of Eq. 14 and Eq. 13.
The proof can be found in Appendix A.4, where we use contradiction to show that there does not exist any global optimal solution of Eq. 14 or Eq. 13 that is different from Dφ(Eψ(l∗)). Remark 2. (Exact feature recovery via feature purifying during training) Theorem 3 directly justifies the proposed feature purifying during training. Under certain conditions, we can recover each column of L exactly during training.
Next, we analyze the exact feature recovery property under inference phase threat model B (missing feature attack), where there are no adversarial features.
Theorem 4. (Exact feature recovery under threat model B) Let Wend be the weight matrix of the last layer of the AutoEncoder. Assume there is no bias term nor non-linear activation function in the last layer. Assume the trained AutoEncoder captures the underlying feature subspace (i.e., Dφ(Eψ(l)) = l for uncorrupted feature vector l). Let Ω be the index set of the observed blocks (agents). If ∀v ∈ Range(Wend)\0, it holds that vΩ 6= 0, then given hΩ = l∗Ω, Dφ(Eψ(l∗)) is the unique solution of Eq. 14 and Eq. 13.
The proof is deferred to Appendix A.5, where we use contradiction to show that there does not exist any global optimal solution of Eq. 14 or Eq. 13 that is different from Dφ(Eψ(l∗)). The condition vΩ 6= 0 for any v ∈ Range(Wend)\0 required by Theorem 4 is much weaker than that required by Theorem 3, which is reasonable as there are no corruptions on the observed blocks in Theorem 4. This required condition also provides very useful insights on how many agents we need to observe in order to make a prediction. It can be understood through the following toy example. Suppose the prediction task is credit approval. Agent 1 holds the banking data, Agent 2 holds the shopping history, while Agent 3 holds age and gender features. Intuitively, if we only observe the features from Agent 3, it is very hard to make the prediction, since there are definitely Person A and B of the same age and gender, but with quite different other features. Let lA be Person A’s overall features, lB be Person B’s overall features. In this toy example, Ω corresponds to Agent 3 only. We have lA 6= lB but lAΩ = lBΩ , or say (lA − lB)Ω = 0. Note that both lA and lB are in the range space of Wend, so (lA − lB) ∈ Range(Wend)\0. The smaller the set Ω implies the higher chance that (lA − lB)Ω = 0. In general, there is no exact value for the minimal fraction of agents we need to observe in order to make a prediction. It highly depends on whether the observed agents cover enough information to distinguish different classes in the classification task. For example, if there is enough redundancy across the agents, say Agent 3 holds age, gender, banking data, and shopping history, then observing Agent 3 could be sufficient.
In summary, Theorem 2 shows that under certain natural conditions (e.g., the fraction of poisoning instances β is small), we can recover the underlying feature subspace exactly. Further, Theorems 3 & 4 show that under certain natural conditions (e.g., the fraction of malicious agents α is small and the AutoEncoder we have learnt captures the underlying feature subspace), we can recover the underlying embedded features exactly during both training and inference.

heading: 6 EMPIRICAL EVALUATION
text: We first describe experimental setup in Section 6.1, and present experimental results in Section 6.2. Additional implementation details and results can be found in Appendix A.1.

heading: 6.1 EXPERIMENTAL SETUP
text: Dataset and Models. We study the classification task on two datasets: NUS-WIDE and CIFAR-10. Following (Liu et al., 2020), which proposed the backdoor attack against VFL, we first use NUSWIDE dataset to evaluate our defense. In NUS-WIDE, each sample has 634 image features, 1000 text features, and 5 different labels. We consider two VFL settings (1 server and M agents): M = 2 and M = 4. We denote G1 as Agent 1, G2 as Agent 2, etc. for simplicity. Following (Liu et al., 2020), when M = 2, G1 holds image features and G2 holds text features. When M = 4, G1 (G2) holds 225 (409) image features while G3 (G4) holds 500 (500) text features. In all settings, only the server holds the labels. In CIFAR-10 dataset, each sample have 32x32x3 image features. We consider the VFL settings for CIFAR-10 with M = 2 and M = 3. When M = 2, each agent has 16x32x3 features, i.e., half image. When M = 3, G1, G2, G3 have 9x32x3, 10x32x3, 13x32x3 features respectively. Following the standard setup, we use SGD to update the local models and server model for E epochs with learning rate 0.01 and batch size Bs. The detailed dataset and model descriptions as well as training parameter setups are summarized in Table 1 in Appendix.
Attack Setup. We consider the backdoor attack, its combination with the missing feature attack, as well as the combination of adversarial evasion attack (Goodfellow et al., 2014) and missing feature attack: (1) The backdoor attack is proposed by (Liu et al., 2020) and the detailed description of the attack method can be found in Appendix. A.1. In NUS-WIDE, the attacker’s backdoor attack goal is to change the predicted label of the instance with a backdoor trigger to be a specific target class (i.e., ‘buildings’), where the backdoor trigger is ‘the last text feature equals 1’. There are 152 backdoored training samples. In CIFAR-10, the backdoor targeted label is ‘truck’ and the trigger pattern is a white rectangle with size 4x6x3 in the lower right corner. The number of backdoored training samples is 100 when M = 3, and 600 when M = 2. (2) In the missing feature attack, the malicious agent does not send its local embedded feature to the server during inference phase. The server uses a zero vector as its local embedded feature. We combine this attack with other attacks as this attack alone is not powerful enough. (3) In the evasion attack, the attacker use the information from server to locally generate the partial adversarial input features (i.e., adversarial examples) based on the Fast Gradient Signed Method (FGSM) attack method (Goodfellow et al., 2014). The detailed setup of this attack method against VFL is presented in Appendix. A.1. The evasion attack (or its combination with missing feature attack) is only conducted during the VFL inference phase (VFL training procedure is attack-free).
Baseline methods. Besides the Vanilla VFL framework without defense (Liu et al., 2020, Algorithm 1), we compare our proposed defense method with two state-of-the-art VFL defense techniques, e.g., Gradient Sparsification method that sparsifies the intermediate gradients sent from the server to agents, and Differential Privacy (DP) that adds noise to such exchanged gradients (Liu et al., 2020). Laplacian Noise is used as a realization of the DP method. The noise variance is 0.05 for NUS-WIDE and 0.0001 for CIFAR-10 to preserve reasonable clean accuracy of the model. In Gradient Sparsification, the hyperparameter controlling the sparsity is 0.999 for NUS-WIDE and 0.95 for CIFAR-10. As for our proposed RVFR, in Stage 1 (i.e., quarantine training for local models) and Stage 4 (i.e., training for server model), we use the same training parameters as in Table 1. The robust autoencoder is a four-layer fully connected neural network. The details about the training of robust autoencoder, the alternative optimization, and the purified training of the server in Stage 2, 3, 4 and details of the inference procedures can be founded in Appendix. A.1. All of our experiments are run three times.

heading: 6.2 EMPIRICAL RESULTS
text: Evaluation Metrics. For the backdoor attack (BKD) and its combination with missing feature attack (Miss), the evaluation metrics for defense methods are the Backdoor Accuracy (the lower the better)
on the backdoored test data and the main task Clean Accuracy (the higher the better) on the clean test dataset. There are 102 backdoored testing samples in NUS-WIDE and 10000 in CIFAR-10. For the adversarial evasion attack (Adv) and missing feature attack, the evaluation metric is the main task Accuracy on the adversarial examples. 10000 adversarial examples are generated for both datasets.
Figure 2 & 3 show the performance of the proposed RVFR and baseline methods on NUS-WIDE and CIFAR-10. When defending against backdoor attack and its combination with missing feature attack, the proposed RVFR method exhibits significantly lower Backdoor Accuracy and similar Clean Accuracy on both datasets, compared to other methods. Note that under the backdoor attack, in some cases, the Clean Accuracy of all defense methods is lower than the vanilla VFL, which exhibits a trade-off between robustness and accuracy. As shown in the right column of Figure 2 & 3, when defending against the combination of adversarial evasion attack and missing feature attack, the proposed RVFR method achieves consistently higher accuracy than the baseline methods on both datasets, which demonstrates its robustness against such attacks.

heading: 7 CONCLUSIONS
text: In this work, we proposed a novel robust feature subspace recovery based VFL framework to defend against backdoor attacks during training, and a variety of attacks during inference, both with theoretical guarantees. An important byproduct of our analysis is the first theoretical justification for the Robust AutoEncoder, which may be of independent interest. We further validate the robustness of our proposed framework through extensive experiments on NUS-WIDE and CIFAR-10 datasets.

heading: ETHICS STATEMENT
text: We propose a novel defense algorithm for vertical federated learning, and provide analysis from theoretical and empirical perspectives. All the datasets and packages we use are open-sourced. We do not have ethical concerns in our paper.

heading: REPRODUCIBILITY STATEMENT
text: The source code of the proposed RVFR method is available as the supplemental material, which also includes the detailed data processing steps. The complete proof of the theorems can be found in the Appendix.

heading: A APPENDIX

heading: A.1 ADDITIONAL EXPERIMENTAL DETAILS
text: Simulation Environment. We simulate the VFL setup (1 server and multiple agents) on a Linux machine with Intel® Xeon® Gold 6132 CPUs and 8 NVidia® 1080Ti GPUs. Our code is based on Tensorflow 2.0.
VFL Backdoor Attacks. For the j-th instance with backdoor trigger, the malicious agent i does not update its local feature extractor (parameterized by θi) like benign agents via using the combined
gradient ∂` ∂h {j} i
∂h {j} i
∂θi . Instead, it replaces the intermediate gradient received from the server ∂`
∂h {j} i
by
γ ∂` ∂h {target} i and uses the manipulated gradient γ ∂` ∂h {target} i
∂h {j} i
∂θi to update its local feature extractor,
where ∂` ∂h {target} i is the intermediate gradient received from the server for any instance belonging to the target class, and γ is the gradient amplify ratio. In our experiments, we use γ = 10 for NUS-WIDE and γ = 1 for CIFAR-10. Moreover, since the label owned by the server is clean, the attacker would submit zero vector to the server to prevent the server mapping the poisoned embedding to the true label.
Evasion Attacks. Given the j-th test sample, the attacker adds small perturbations xpertest {j} i generated from FGSM to the original data xtest {j} i to obtain the adversarial example x adv test {j} i = xtest {j} i + x per test {j} i where controlling the degree of attack. For NUS-WIDE, we set = 0.01 when M = 2 and = 0.1 when M = 4; for CIFAR-10, we set = 0.01.
Training and Inference Details of RVFR. In Stage 2, we first train the AutoEncoder for Erae epochs, and alternatively update AutoEncoder and the estimated uncorrupted embedded features L for Ealt epochs using SGD with an initial learning rate 0.01 which exponentially decays by a factor of 0.99 every 10000 steps. During the alternating optimization, λ and η in the objective function are set to be 0.1. In NUS-WIDE, Erae = 100 when M = 2 and Erae = 200 when M = 4; in CIFAR-10, Erae = 100. We use Ealt = 100 for all settings. In Stage 3 & 4, for each batch of training data, we first purifies the embedded features according to Eq. 12 (using the estimated L from Stage 2 as initialization) for Epur train = 2 epochs, then use the purified embedded feature to train server’s global ML model. We perform such procedure for Eserver = 100 epochs using the same SGD optimizer as in Stage 2. In the inference phase, the server purifies the embedded features according to Eq. 14 (use the embedded features as initialization) for Epur test = 2 epochs, and feeds the purified feature to the trained server model for prediction.
Clean Accuracy under Non-adversarial Setting In this section, we report the clean accuracy of different VFL methods under non-adversarial setting in Table 2.

heading: A.2 DEFINITION OF INCOHERENCE PARAMETER
text: Definition 1. (Incoherence parameter (Xu et al., 2012)) A matrix L ∈ Rd×n with thin SVD L = UΣV T and (1 − β)n whose columns are non-zero, is said to be column-incoherent with parameter µ if
max i ‖V Tei‖22 ≤
µr
(1− β)n , (15)
where {ei} are the coordinate unit vectors, r is the rank of matrix L.
A small incoherence parameter implies the right singular vectors of L are not ‘spiky’. As mentioned in Xu et al. (2012), if the left hand side of Eq. 15 is as big as 1, it essentially means that one of the directions of the column space which we wish to recover, is defined by only a single observation. Given the regime of a constant fraction of arbitrarily chosen and arbitrarily corrupted points, such a setting is highly undesirable.

heading: A.3 PROOF OF THEOREM 2
text: Proof. First note that Wencoder ∈ Rr×d since we limit the dimension of the latent layer of the AutoEncoder to be r = rank(L∗). The problem we consider is:
min L,E,Wencoder∈Rr×d
‖WencoderL‖2,1 + λ‖ET ‖2,1, s.t.H = L + E,L = Dφ(Eψ(L)) (16)
Since we have the constraint L = Dφ(Eψ(L)), the rank of any feasible L should be no more than r, and L must lie within the row-space of Wencoder. So we can write Wencoder = RUT where R ∈ Rr×r, and U are the top-r left singular vectors of L. As the rows of Wencoder are orthornormal, i.e., WencoderW Tencoder = I , so RU
TURT = I and therefore RRT = I (so this square matrix R is unitary). Further, since setting Wdecoder = W Tencoder will always meet the constraint L = Dφ(Eψ(L)), the main problem we need to consider becomes:
min {L|rank(L)≤r},E,
Wencoder=RU T ,R is unitary
‖WencoderL‖2,1 + λ‖ET ‖2,1, s.t.H = L + E, (17)
Since ‖L‖∗ = ‖RUTL‖∗ = ‖WencoderL‖∗ = ‖I(WencoderL)‖∗ = ‖ ∑r i=1 ei(WencoderL)i,:‖∗ ≤ ∑r i=1 ‖ei(WencoderL)i,:‖ = ∑r i=1 ‖(WencoderL)i,:‖2 , ‖WencoderL‖2,1. The equality is achieved when R = I , i.e., Wencoder = UT , because ‖WencoderL‖2,1 = ‖UTL‖2,1 = ‖UTUΣV T ‖2,1 = ‖ΣV T ‖2,1 = ∑r i=1 σi = ‖L‖∗.
So
min {L|rank(L)≤r},E,
Wencoder=RU T ,R is unitary
‖WencoderL‖2,1 + λ‖ET ‖2,1 ≥ min {L|rank(L)≤r},E ‖L‖∗ + λ‖ET ‖2,1,
(18) with equality achieved when Wencoder equals top-r left singular vectors of L.
Then we only need to consider the right-hand-side of Eq. 18, i.e.,
min {L|rank(L)≤r},E
‖L‖∗ + λ‖ET ‖2,1 s.t.H = L + E (19)
Recall that under the conditions of Theorem 1, the solution L̂ of Eq. 2 has exactly the same column space as L∗ (L̂ may not and not necessary to be equal to L∗), so rank(L̂) = r. Then the solution L̂ of Eq. 2 must also be the global optimal solution of Eq. 19. Finally, as the row-space of Wencoder equals the column-space of L̂, it recovers the underlying subspace of L∗ exactly.

heading: A.4 PROOF OF THEOREM 3
text: Proof. A) Suppose Dφ(Eψ(l′)) is the global optimal solution of Eq. 14 that is different from Dφ(Eψ(l∗)). Let Dφ(Eψ(l′)) = Dφ(Eψ(l∗))− v. So we have v ∈ Range(Wend)\0.
∑ i∈Ω ‖[h−Dφ(Eψ(l′))]i‖2 (20)
= ∑ i∈Ω ‖[h−Dφ(Eψ(l∗)) + v]i‖2 (21)
= ∑ i∈Ω ‖[h−Dφ(Eψ(l∗))]i + vi‖2 (22)
= ∑ i∈SΩ ‖[h−Dφ(Eψ(l∗))]i + vi‖2 + ∑ i∈S̄Ω ‖[h−Dφ(Eψ(l∗))]i + vi‖2 (23)
= ∑ i∈SΩ ‖vi‖2 + ∑ i∈S̄Ω ‖[h−Dφ(Eψ(l∗))]i + vi‖2 (24)
≥ ∑ i∈SΩ ‖vi‖2 + ∑ i∈S̄Ω ‖[h−Dφ(Eψ(l∗))]i‖2 − ∑ i∈S̄Ω ‖vi‖2 (25)
> ∑ i∈S̄Ω ‖[h−Dφ(Eψ(l∗))]i‖2 (26)
= ∑ i∈Ω ‖[h−Dφ(Eψ(l∗))]i‖2 (27)
where SΩ is the index set of size g such that e∗i = 0,∀i ∈ SΩ. And the last inequality follows from the assumed range space property since v ∈ Range(Wend)\0. The above contradicts the assumption that Dφ(Eψ(l′)) is the global optimal solution that is different from Dφ(Eψ(l∗)). B) First, note that hΩ = Dφ(Eψ(l∗))Ω+e∗Ω and ∑ i∈Ω 1{e∗i 6= 0} ≤ |Ω|−g. SupposeDφ(Eψ(l′)) is the global optimal solution of Eq. 13 that is different fromDφ(Eψ(l∗)). Let hΩ = Dφ(Eψ(l′))Ω +e′Ω, then we have ∑
i∈Ω 1{e′i 6= 0} ≤ ∑ i∈Ω 1{e∗i 6= 0} ≤ |Ω| − g (28)
and Dφ(Eψ(l′))Ω + e′Ω = Dφ(Eψ(l∗))Ω + e∗Ω. From Eq. 28 we know that
∑ i∈Ω 1{[Dφ(Eψ(l∗))−Dφ(Eψ(l′))]i = 0} ≥|Ω| − ∑ i∈Ω 1{e∗i 6= 0} − ∑ i∈Ω 1{e′i 6= 0} (29)
≥|Ω| − (|Ω| − g)− (|Ω| − g) = 2g − |Ω| (30)
Let Dφ(Eψ(l′)) = Dφ(Eψ(l∗)) − v, so we have v ∈ Range(Wend)\0 and ∑ i∈Ω 1{vi = 0} ≥ 2g − |Ω|. Now split Ω into 3 disjoint sets {Ω0,Ω1,Ω2}, where Ω0 is any subset of Ω with size 2g − |Ω| such that vΩ0 = 0, and |Ω1| = |Ω2| = |Ω| − g. Since |Ω0 ∪ Ω1| = g, by our assumption, we have ∑ i∈Ω0∪Ω1 ‖vi‖2 > ∑ i∈Ω2 ‖vi‖2. Since |Ω0 ∪ Ω2| = g, by our assumption, we have∑
i∈Ω0∪Ω2 ‖vi‖2 > ∑ i∈Ω1 ‖vi‖2. However, this leads to a contradiction since ∑ i∈Ω0 ‖vi‖2 =
0.

heading: A.5 PROOF OF THEOREM 4
text: Proof. SupposeDφ(Eψ(l′)) is the global optimal solution of Eq. 14 that is different fromDφ(Eψ(l∗)). Let Dφ(Eψ(l′)) = Dφ(Eψ(l∗))− v. So we have v ∈ Range(Wend)\0.
∑ i∈Ω ‖[h−Dφ(Eψ(l′))]i‖2 (31)
= ∑ i∈Ω ‖[h−Dφ(Eψ(l∗)) + v]i‖2 (32)
= ∑ i∈Ω ‖vi‖2 (33)
>0 (34) = ∑ i∈Ω ‖[h−Dφ(Eψ(l∗))]i‖2, (35)
where the inequality is due to the condition that vΩ 6= 0 for any v ∈ Range(Wend)\0. The above contradicts the assumption that Dφ(Eψ(l′)) is the global optimal solution of Eq. 14 that is different from Dφ(Eψ(l∗)). Similarly, suppose Dφ(Eψ(l′)) is the global optimal solution of Eq. 13 that is different from Dφ(Eψ(l∗)). Let Dφ(Eψ(l′)) = Dφ(Eψ(l∗))− v. So we have v ∈ Range(Wend)\0.
∑ i∈Ω 1{[h−Dφ(Eψ(l′))]i 6= 0} (36)
= ∑ i∈Ω 1{[h−Dφ(Eψ(l∗)) + v]i 6= 0} (37)
= ∑ i∈Ω 1{vi 6= 0} (38)
>0 (39) = ∑ i∈Ω 1{[h−Dφ(Eψ(l∗))]i 6= 0} (40)
The above contradicts the assumption that Dφ(Eψ(l′)) is the global optimal solution that is different from Dφ(Eψ(l∗)).

Review summaries:
This paper studies the robustness of vertical federated learning. They use intuitions from robust feature subspace recovery for low rank matrices to design a defense framework for vertical federated learning. They empirically show the effectiveness of their framework for some settings. They also try to provide theoretical evidence for the robustness of their scheme, but I do not find their theoretical studies illuminating. 

This paper studies robust vertical federated learning framework against backdoor attacks. The authors utilize robust autoencoders with purified training to remove the backdoor features and obtain clean global model. The authors also proved that, with some assumptions, the exact uncorrupted features can be recovered.

The paper tackles the problem of adversarial attacks against federated learning. The main proposal is RVFR, an original method that allows to protect against backdoor attacks targeting the specific “vertical federated learning” setting. The proposal is provided with a theoretical analysis of its effectiveness, and is then evaluated on two well-known datasets, showing better results than prior works in adversarial scenarios.  Overall, the presentation of the paper should be improved. The quality of the English text is appropriate. Figures and Tables should be improved. The topic addressed by the manuscript is relevant and in-line with ICLR. The references must be expanded with security-related works. The contribution is potentially significant.  STRENGTHS: + Relevant and trendy subject + Evaluation on two datasets + The theoretical analysis is appreciable  WEAKNESSES - Very poor Introduction, Abstract and Background (Related Work) - Unclear threat model - No Tradeoff

The paper proposes a robust vertical federated learning framework called RVFR against backdoor attacks. In the framework, the agents train the local feature extractors and send the embedded features to the server. Then, the server trains a robust auto-encoder to recover and purify the features. Last, the purified features are used to train the global model. The paper provides theoretical analyses of the feature recovery under different threat models. The experiments show that RVFR is more effective when defending the backdoor attacks compared with the other baselines.