Hybrid Federated Learning for Feature & Sample Heterogeneity: Algorithms and Implementation
Authors: Xinwei Zhang
Wotao Yin
Mingyi Hong
Tianyi Chen
Venue: Submitted to ICLR 2023 (2023)
Keywords: Federated Learning
Model Ensemble
Model Design
Algorithm Design

Abstract:  Federated learning (FL) is a popular distributed machine learning paradigm dealing with distributed and private data sets. Based on the data partition pattern, FL is often categorized into horizontal, vertical, and hybrid settings. All three settings have many applications, but the hybrid FL remains relatively less explored, because it deals with the challenging situation where both the feature space and the data samples are heterogeneous.
    This work designs a novel mathematical model that effectively allows the clients to aggregate distributed data with heterogeneous, and possibly overlapping features and samples. Our main idea is to partition each client's model into a feature extractor part and a classifier part, where the former can be used to process the input data, while the latter is used to perform the learning from the extracted features. The heterogeneous feature aggregation is done through building a server model, which assimilates local classifiers and feature extractors through a carefully designed matching mechanism. A communication-efficient algorithm is then designed to train both the client and server models. Finally, we conducted numerical experiments on multiple image classification data sets to validate the performance of the proposed algorithm. To our knowledge, this is the first formulation and algorithm developed for hybrid FL.

HYBRID FEDERATED LEARNING FOR FEATURE & SAMPLE HETEROGENEITY: ALGORITHMS AND IMPLE- MENTATION
Anonymous authors Paper under couble-blind review
ABSTRACT
Federated learning (FL) is popular distributed machine learning paradigm deal- ing with distributed and private data sets. Based on the data partition pattern, FL is often categorized into horizontal, vertical, and hybrid settings. All three settings have many applications, but the hybrid FL remains relatively less explored, be- cause it deals with the challenging situation where both the feature space and the data samples heterogeneous. This work designs novel mathematical model that effectively allows the clients to aggregate distributed data with heterogeneous, and possibly overlapping features and samples. Our main idea is to partition each client's model into a feature extractor part and a classifier part, where the former be used to process the input data, while the latter is used perform the learn- ing from the extracted features. The heterogeneous feature aggregation is done through building server model, which assimilates local classifiers and feature extractors through a carefully designed matching mechanism. A communication- efficient algorithm is then designed train both the client and server models. Fi- nally, we conducted numerical experiments multiple image classification data sets to validate the performance the proposed algorithm. To our knowledge, this is the first formulation and algorithm developed for hybrid FL.
INTRODUCTION
Federated Learning (FI.) is emerging distributed machine learning (ML.) framework which en- ables heterogeneous clients- such as organizations or mobile devices - to collaboratively train MI. models (Konečný et al., 2016 Yang et al., 2019). The development of FL. aims to address practical challenges in distributed learning, such as feature and data heterogeneity, high communication cost, and data privacy requirement.
The challenge due to heterogeneous data particularly evident in FL. The most well-known form of heterogeneous data is sample heterogeneity (SH), where the distributions of training samples are different across the clients (Kairouz et al.] Bonawitz et al. (019).. Severe SH can cause common FL algorithms such FedAvg to diverge (Khaled al. 2019) Karimireddy et al. 2020b). Recently, netter-performing algorithms and system architectures for distributed ML (including FL. under SH include Karimireddy al. (2020b); Li et al. (0188: Wang al. (2020): Fallah et al. 2020); Vahidian et al. (2021).
Besides SH, another form of heterogeneity is feature her- erogeneity (FH). Traditionally, we say the samples are FH if we can partition them into subsets that bear dis- tinct features. In the FL setting, when the sample sub- sets of different clients have different, but not necessarily distinct, features, we call it FH. That is, under FH, dif- ferent clients have unique and possibly also common fea- tures. FH and SH arise in ML tasks such as collaborative medical diagnosis (g et al. 2021). recommendation sys- tem (Yang et al. 2020), and graph learning (Zhang et al. 2021). where the data collected by different clients have different, and possibly overlapping features and sample IDs. Next, provide few examples.
MBI
Massovd
MBr DCG
Clisse
Lirnored
Clisie
NRI
Owile
Charke
Clitie
Figure 1: The heterogeneous data distribu- tion a medical diagnosis example.

---

Application
Client clinic
Feature Blocks
Sample
Medical Diagnosis Recommendation System
output of different diagnostic devices record of different product categories user activity & relationship
patient customer
retailer
Social Network
SNS provider
SNS user
Table 1: Examples of applications that generates heterogeneous data
used HFL
Featerue
frum Clant
from Cltee
vydaan
from Clieat
Data from Client
Data from Client 2
(a) Heterogeneous data clients
(b) HFL data usage
(c) VFL data usage
Figure 2: The data distribution patterns of a) heterogeneous client data; b) HFL and c) VFL.
Medical diagnosis application (see Figure D. The clients are clinics, and they collect data samples from patients. Each clinic may have different set of diagnostic devices, e.g., clinic A has MRI and ultrasound, while clinic B has MRI and electrocardiographs (ECG). FH arises as the feature set of each sample collected by clinic may partially overlap with that done by clinic B. Besides FH, SH also arises as multiple clinics may not have the chance of treating the same patient and each patient usually visit only a subset of clinics.
Recommendation system Yang et al. 2020 Zhan et al. 2010). In this case, the clients are large retailers, and they collect samples (such as shopping records) from their customers. The retailers share subset of common products and subset of common customers.
A third example pertains to an application of learning over multiple social networks (Zhngg et al., 2021 Guo Wang] 2020). Here the clients are social network providers (c.g., Twitter, Facebook), and the samples are the set of participating users, their activities and relations. We summarize these three examples in Table.
In the previous three applications, client data can be heterogeneous in both feature and sample. Surprisingly, none the existing FL algorithms can fully handle such data. Rather, Horizontal FL (HFL) and Vertical FL. (VFL) methods can handle data with only one heterogeneity, the former with SH and the latter with FH. By keeping only the common features (and ignoring the other features), can avoid FH and apply an HFL method. By keeping only the common samples (and discarding the remaining samples), we can avoid SH and apply a VFL method. Clearly, they both waste data.
Consider the HFL algorithms (Konečný et al. 2016 Karimireddy al. 2020b Dinh al. 202 The clients perform multiple local model updates, and the server averages those updates and broad- casts the new model to the clients. This scheme works when the clients share the same model and their data share an identical set of features (see Figure (b for an illustration); otherwise. the server cannot average their models.
Consider the Vertical FL. (VFL) algorithms (Liu et al. 2019 Chen et al. 2020). They split the model into blocks. Each client processes subset of the blocks while the server aggregates the processed features to compute training losses and gradients. They require all the clients to have the same set of samples (see Figure 2ch; otherwise, they cannot compute the loss and its gradient.
According to Yang et al. (219); Rahman et al. (20TT, the FL setting with heterogeneous feature and samples referred to as hybrid FL. To develop hybrid FL method, we must address the following challenges:
1. Global and local inference requires global and local models. Hybrid FL makes it possible for a client to make its local inference and also for all the clients (or the server) to make global inference. The former requires only the features local to a client; the latter requires all the features and training global model at the server.
2. Limited data sharing. In typical HFL, the clients do not share their local data labels during training. In VFL, the labels are either made available by the clients to the server (Chen et al.) 2020) stored in designated client (Liu al. 2019). hybrid FL system may be subject to "no
2

---

sharing" requirement, so it is desirable to develop method in which the server has access to any data, including the labels.
3. Sample synchronization. A technical challenge with VFL is that the server wants the clients to draw the same mini-bath of samples at each iteration. This challenge is exacerbated in hybrid FL since not all the clients will have the same samples. Therefore, avoid idling clients, hybrid FL. method should allow uncoordinated sample draws.
Our contributions: Towards addressing the previous challenges, this work proposes a novel model and its training method. We summarize our contribution as follows.
1. We propose new hybrid FL approach. For each client, the model consists of feature extractor and a subsequent classifier. The clients collaborate and share their knowledge through building a model at the server that assimilates local classifiers and feature. The assimilation is achieved by matching mechanism inspired by the non-parametric modeling idea in Yurochkin et al. (2019). This approach enables both global and local inferences and can handle data with both SH and FH. To our knowledge, this is the first concrete hybrid FL model in the literature.
2. We develop a hybrid FL algorithm that enables knowledge transfer among the clients. The algo- rithm maintains data locality. so the server does not access clients' data, and it allows uncoordinated sample draws by the clients.
3. We evaluated the performance of the hybrid FL. algorithm on number of real datasets. The learned model achieved an accuracy that was comparable to that of a centrally trained model.
1.1 RELATED WORK
Federated graph learning (FGL) is applied to molecular classification (He et al. 2021). 1). relation or node classification for social networks (Zhang et al.] [021] Ng et al.) (021) and financial net- work (Suzumura et al., 2019). In the first application, the graphs have large amount of graphs (Zhang et al., 2021 He et al.) 2021). ). In the last two application sce- narios, the clients possess partial yet overlapping data of single large graph, including partial node and edge information (Zhang et al. (021). However, existing FGL algorithms mainly focus on the first application scenario (He al.] 2021) and fail deal with the latter two scenarios. So we cannot apply them to our hybrid FI. setting.
relatively small and the clients
HFL has a popular algorithm FedAvg (Konečný al. 2016), which adopts the computation- -then- aggregation strategy. The clients locally perform a few steps of model updates, and then the server aggregates the updated local models and averages them before sending the updated global model back to the clients. Beyond model averaging. PFNM (Yurochkin et al. 2019) and FedMA (Wang) ct al. 2020) use a parameter-mateee wawpeeer-mtttcttebbeeeeeee based strategy and FedGKT (He et al. 2020) uses a knowl- edge distillation strategy to get better global model performance, and they do not require the global model to have the same size as the local models. All HFL algorithms assume their data have the same set of features.
Personalized FL (PFL) has been studied as potential way to tackle different levels of task het- erogeneity. MAML (Tiang et al. 2019 Fallah et al.] 2020) uses meta-learning to build global model that can fast adapt to heterogeneous data distribution: FedProx (Li et al. 2018) and LG- FedAvg (Hanzely & Richtárik 2020 regularize the distance between the local models and the global model. MOCHA (Smith et al. 2017 and FedU (Dinh et al. (202T) combine multi task learning with FL train models for personalized tasks. FedPer (Arivazhagan et al., 2019) separates the model into base + personalizzd layers to decouple the common and personal knowledge. However, most of the algorithms assume that all local models take the same input size and format.
PROBLEM FORMULATION
In this section, we first provide a mathematical characterization of the heterogeneous data distribu- tions of interest this work. We then propose unified hybrid FL model.
Notation: Due to the nature hybrid FL, we must carefully set up its notation. We denote the all one (column) vector of length d as 1a; the identity matrix of size d as Lı; the positive integer set {1. (1.,.... N} as [N]. Feature selection below uses selector matrix of dimension dj x d2, which belongs the following set:
3

---

Client 1:
Client 2:
Client 3:
Server
D2
Ry (Pasc)
JV
Rg (Paz8)
Fu(Wig)
N;
(Meat)
Dota
Feetare extrattios
Classifier
No
N2
Clicni
Su(Wae)))
X
Y
(Peuz))
X. (2, X, [2 (p) X3 [y)
Chasiifie:
(a) Data partition pattern and notations.
(b) Block structure of client and server models
Figure 3: The partitioned data and notations, and the structure of the client and server models with heteroge- ncous feature extractors and classifiers.
de Po= Wi [di], Σ Ps (0, Vj [da]
S(d1, d2)
PE (0.1)
Data description; See Figure 3a for an illustration of dataset with three clients, where the client datasets has no fully overlapped sample or feature, so neither HFL. nor VFI. can be used. We consider hybrid FL system with M clients indexed by E [M]. and they collaborate accomplish the same task. For convenience, we index the server as m 0.
First, assume that each sample can have at most do feature blocks, and the ith block has the set D; of features, E [du]: client m has a set of dm feature blocks indexed by Im. that is, we write (Dim),
sm.T. EIn, and write the feature space of client m Xm = _II,,, Di... which is Cartesian product of the subset of the feature blocks possessed by client m. Similarly, we denote the "full feature" space as Xy = I Di, which is the Cartesian product of all feature blocks.
Second, client m holds a private dataset with index Net,,,, and the samples (Zm,n- for Nms where Im.n Xm denotes the features of the th sample on client m, and yn, denotes the label of the th sample. Collecting all the clients' data together, we can define the (virtual) global dataset have sample index set No [N], with samples (Fu,n: Vn.) where To.n E No denotes the "full feature" of the th sample (for the precise relation between the full featured øo,n and the local sample Im.no please see the property P2 below).
The dataset defined above satisfy the following properties.
P1) The global index set is the union of the clients' index sets:
M
No
U Nms m=1
which implics Nm No.
P2) For a given client m, the features of the th sample is sub-vector of the "full features". That is, there exists selector matrix Pm such that can map the global feature Jo,n Fm.n
Tm,n No, for some
Pm S(dm, do),
where P., as selector matrix that selects the feature blocks client from the full feature.
Remark 1. (Data structures of HFL. and VFL) The data structure that the HFL deals with can be viewed as special case of what has been described above, where the clients have fully overlapping features, i.c., do = Pm = 1, Vm [M]]: Similarly, the data structure for VFL can be viewed as special case that the clients have fully overlapping sample indices, i.e., Nom No. Vm [M]. D
Model design: With the above description of data, we are ready to present the proposed hybrid FL model and the corresponding optimization problem.
Client and server model design: Similar to VFL, we split the ML model into feature extractors and classifiers. Each feature extractor takes feature block as input and extracts intermediate feature as output; the classifier takes the concatenated intermediate features of multiple feature extractors as input and outputs the prediction.
As illustrated by Figure 3b, on client m, the feature extractor h; (6m.im for input feature block Dr., is parameterized by Um for all im Imn. The feature extractors can have different neural
4

---

network architectures (e.g.. CNN for CT/MRI images, LSTM/Transforeer for medical records, and 1-D CNN for ECG data). We denote the concatenated feature extractors and its parameters as:
Hm (0m: = [As... ( II.. and en == [0m, EIm
The classifier Fm Wmmi :) is parameterized by Wm and denote the prediction loss function as ((.-)). The data processing procedure on client m is described as follows:
(1) The features Tm.n of the n sample are passed the feature extractors (le,.. (Om,.... ) eT.
(2) The classifier Fm (wm3-) makes the prediction based on the concatenated output of the feature extractors Hm Fm.n):
(3) The prediction Fm (Wm; Hm (Om; (m,))) and the true label Yn. together evaluates the loss ((;
With the specified data processing procedure, the prediction loss on client is defined as:
fm (Om: Wm) = [
Σ
{(Fm (W0: Hm mmi mm, yn))
(3)
nEN.
Additionally, the server will have model with fial feature extractors, concatenated with classifier; see the top figure in Fig. 3b) This model structure covers a wide range of ML models for classifica- tion and regression problems, e.g., image classification, language processing, and recommendation system.
Remark 2. (Local and server models). A few remarks ready. First, although the construction of the client model has been partly motivated by the model splitting idea from VFL, one key difference with VFL is that each client holds complete model, capable of performing local inference without communication to the server. Second, it is important to have separate server model, because: 1) in case test data with "full feature" comes in, the server can deal with it; 2) in case a new client comes who needs to process a new subset of features, it can directly download the corresponding feature extractors from the server, which significantly reduces the complexity of building the local model; and most importantly 3) the server's model is instrumental in helping the clients to learn from each other's data (as we will see shortly).
At this point, we have defined the models and the prediction loss for each individual client. A key question is: how the client can effectively collaborate and leverage each other's 's data to train high- quality server/client models? Unlike HFL, where all clients share the same model, the clients in this problem have local models (i.e., feature extractors and classifiers) of different sizes to deal with feature heterogeneity. Therefore, one cannot directly perform the conventional model averaging.
To enable effective collaboration among the clients, our idea is to properly match different parts of the model, by imposing number of carefully designed regularizers.
Model matching:
First, it is natural to assume that when client m and m' share the same feature block D,, the corre- sponding feature extractors h<(0m,ii)) should produce the same output, that is Om, RV 0o,; Rs O Therefore, impose the following regularizer for the feature extractors, which matches the 5th feature extractor at user m with the corresponding extractor at the server:
T'm (0m, Oo) = Σ
110m, 00 1 10 Pm Onll"
SEI...
where P.,. is the data selection matrix defined in and O,, concatenates parameters defined in 2
We then design the regularizer for the classifiers. As the classifiers on different clients share partially overlapping input and identical output space, we model the client's classifiers w. as some "pruned" versions of the server-side classifier wn, but with unknown pruning pattern. More specifically, as- sume that Wm Rdm, We E Rd we impose the following regularizer for the classifier:
1
Tm (m., 1m, wo) Wmmm 11m woll?, s.t. 11mm S(dmm do,w),
(5)
where IIm is a selection matrix defining the unknown pruning pattern. It is important to note that, the pruning pattern matrices II, 's are unknown and need to be optimized. On the contrary, when in the definition of the feature extractor regularizer (4) the matrix data selection matrices P... 's are fixed, and they are defined by the data partitioning pattern. Detailed discussion about the structure of the constraints on the pruning matrix II 's and the regularizer rm. given in Appendix A.I
5

---

Overall problem formulation: By combining the models discussed in the previous two subsec- tions, we arrive at the following training problem:
min 19mm Mim of mm
Σ pm (Jm (mm, Wm) + pu (0m, 2o) p2 2m,2(2Um 1m, wo)), m=1
LM
(6)
s.t.
Im E S(dm, wy do,w), Vm E [M],
where p1, M2 are haper-parameters for the regularizers; Pm. 's are the weights for each local problem satisfying 2m=1 Pm 1, with common choices Pm. M or Pm
Nag
TAT
Remark (Relation with HFL). When do 1, that is, there only single feature block across all the clients, then the data structure can be handled by the conventional HFL. Below let us discuss the relations between our model 6 and some popular HFL models. First note that when dg 1, the feature extractor regularizer reduces m',1 (0 θa) ||0m Ooll"
1) Reduction to FedMA (Wang et al. 2020) and Sub-FedAvg (Vahidian et al. 2021 If we set 2. I, i.e., the features are directly processed by the Wm 's, then 6 equivalent the problem solved by FedMA and Sub-FedAvg.
2) Reduction FedProx (Li et al., 2018) and LG-FedAvg (Hanzely & Richtárik, 2020). By setting Wm I.pm and letting Om directly predict the labels, the problem reduces to
E (0m) + p1 Tm, (0. On)),
min (9m
M m00
which is equivalent the formulation solved by FedProx and LG-FedAvg.
3) Reduction to FedAvg. Further by letting μ1 - 0o in 77. the regularizer enforce O, 's to achieve exact consensus, the problem reduces to the one solved by FedAvg.
4) Reduction FedPer (Arivazhagan et al. 2019). By letting μ2 and μ + oo in (6), the regularizer W'n" is removed and o,, achieve exact consensus. In this case, O. serves as the base layers while Wm serve as the personalized layers, which is equivalent to the model design of FedPer.
Remark 4. (Relation with VFL.). VFL assumes that the clients cannot perform prediction indepen- dently, it directly trains global model with the local data (Liu al. 2019 Chen et al.) (2020). In contrast, we assume that each client has sufficient features for independent training and construct local model, which is further used construct global model. This way, we avoid data sharing and sample synchronization issues that often limit VFL use in practice.
3 ALGORITHM DESIGN
In this section, we propose a training algorithm for the proposed Hybrid FL formulation (6) This algorithm will alternate between the server-side updates and the client-side updates. To proceed, we will first split (6) into server-side problem and a client-side problem, and then develop algorithms to optimize each part. One key consideration our algorithm design is to ensure that the server-side model is optimized without directly accessing any clients' data.
Problem splitting: Notice that the problem contains parameter blocks )
JM
{wm Oo. 1M
Wo and [IIm LM First we divide the parameters into two groups: 1) the server-side parameters m Oo. Wo. and [I M
1== and 2) the client-side parameters {Om) 1M and {wm) 1M
By fixing the server-side parameters, (6) decomposes into m independent problems, one for each client. The problem related client m is given by:
min fm (0m, Wm) + #1 .mm. ( Qa) + P2 Tm.2( Im Wo). 10
(8)
Similarly, by fixing the client-side parameters, the fm. 's in (6) become constants, and the problem reduces to the following server-side problem:
min Bo, (I1m JM
Σ pm (ez Tmm1 (0m, θu) + #2 Tm,z(Wm, II wo))
m=
s.t. 1m E S(dm. do.w), Vm E [M].

---

Algorithm Hybrid Federated Matching Algorithm (HyFEM)
1: Input: wp, 0; ] T.Q. Q.P
2: for t = .,...,
do
3: for client I,... M in parallel do
4: the w plient (0), Imm w6. Qn)
I| Local perturbed SGD solving
5: Sends client model 0 who
6: for server
7: O (Em=1 Pon P Pm
(EM= Pm PT e
//Exact minimization for
[00
8:
W (I Im=1 MadellMathhin (w II, 14/
(1
// Solving 1I
9: Distributes server madel w 66+1, ([T, Josm1 to clients
10:
Output: {wm, 6
J Jm=o, {11 Jm==
The above problem can be naturally separated into two sub-problems. The first sub-problems is:
min Co
Σ
Pm Tm, (Qm; On),
(10)
and the second one is:
min wo. mm m m=1
Σ Pm Tm, (wmm Mm, Wo), s.t. Im E S(dm, do,,w) Vm [M]
(1I)
We propose block coordinate descent type algorithm called Hybrid Federated Matched Averaging (HyFEM) in Algorithm [ to solve (6) with the above problem splitting strategy and the sub-routines are given by Algorithm 2 in Appendix A.2 global iteration f, the clients first performs Q local perturbed SGD steps problem (8) to optimize client models w Of (line 7- in Algorithm 2 then the server aggregates the updated client models, updates global feature extractors by optimizing 10 that has closed-form solution as line in Algorithm [ and match the classifiers by optimizing I1: finally, the server distributes the models and the selection matrices to clients.
Algorithm design:
The major step in the algorithm is solving the sub-problem Matching procedure described in line 8 - 14 of Algorithm 2 in Appendix A.2 1) for each client index m', construct the server model w without the impact of the selected client; 2) apply the Hun- garian algorithm solve a parameter assignment problem and obtain 11 in most ((dm,, .. run-time complexity Kuhn (955).. With few rounds of updates, we obtain the server classifier and the selection matrices for each client. This procedure inspired by the model matching algo- rithms Wang et al. (2020); Yurochkin et al. (2019) for matching parameters in deep neural networks of the same size. Our matching algorithm a non-trivial extension to the existing model matching algorithm. Because the server-side and client-side models do not share the exact same functionality, we cannot replace the client-side models with the server-side model. Such a special property intro- duces some significant challenges for model matching. The detailed matching procedure is included in Appendix A.2
We optimize it by the Model-
Remark 5. Although Algorithm I seems to be complicated, it can be viewed as problem with three parameter blocks L(x, y, z). where x is the collection of [wm. 0m 1M y is the collection of (IIm I 1m=1 and z is (wo, Ou). Then the update can be viewed follows:
x + x V Z),
arg min L(x .yz). z + arg .y,,z), (12) (y)
times
where V. V.((.) denotes the stochastic partial gradient estimation W.E.t. X.
Theorem (Informal) Suppose that for each [M]. fm has Lipschitz continuous gradients
w.r.l. (Om: Wm) and that wo has a fixed dimension. Then with stepsize 1 (1/001111//0 and client update Q O(T), by running Algorithm the expected gradient norm square w.r.f. { ml Wm 1M
m==1
converges with rate (1/TT) and the successive update difference [| t+1
w// + | 061l
converges with rate O1/TT). Alternatively, if we assume the solution to [11m JM - for sub-problem
II is unique, and we update client models with one-step gradient descent, then Algorithm asymp- totically converges the first-order stationary point of (6).
Remark 6. Theorem T a non-trivial extension of the convergence results for traditional BCD-type algorithms. The major challenges in the analysis of HyFEM are: 1) it runs multiple, yet fixed number
7

---

of stochastic gradient updates on (potentially nonconvex) blocks {Om. Wm
1M 1m
which results in
non-strictly decrease; 2) the problem w.r.t. block [ is nonconvex and non-smooth and does not has unique global minima. Such a setting is different from existing work on BCD-type algorithms. The detailed convergence statement and its proofs are given in Appendix B
We highlight the merits of the proposed approach: 1) Unlike the typical VFL formulations (Liu
eet al. 2019 CCen et al.] 2020), our approach keeps the data at the clients. Hence, the local problems are fully separable. There is no sample-drawing synchronization needed during local updates; 2) By utilizing the proposed model matching technique, we can generate global model at the server, which makes use of full features. This makes the inference stage flexible: the clients can use either partial features (by using its local parameters (Om, Wm)) or the full features by requesting (oo. wo) from the server or letting the server do the inference.
Although we formulate the problem by adopting the idea of model splitting from VFL and model pruning/matching from HFL, optimizing (5) is still a non-trivial procedure. Specifically, we can only train clients' classifiers Wm. 's of different sizes, and construct unknown server's classifier wp with Wmm' 's and find IIm, 's, while existing algorithms either require Wo to be given (Vahidian et al., 2021), or Wm 's to have the same size (Wang et al. 2020 Yurochkin et al. 2019).
NUMERICAL EXPERIMENTS
To evaluate the proposed algorithms,, we have conducted experiments on number of standard datasets, and compared the results with several baselines including centralized training and stand- alone local training (without any client-server communication). Since existing FL algorithms can- not be applied to our setting that the client features are only partial overlapped, we do not compare HyFEM with other FL algorithms in this section. However, we put an additional set of experiments in Appendix C comparing HyFEM and FedProx with less heterogeneous features.
We consider the ModelNet40, Cifar- 10, and Eu datasets, the details of which are explained below. We also consider an additional multi- dataset, we refer the readers to Appendix C.3 for details.
Dataset & data splitting:
ModelNet40 (Wu et al. 2015): ModelNet40 is multiview object classification dataset that has 12 views from different angles as 12 feature blocks for each object. The dataset has No = 40, 000 sam- ples from 40 classes. Cifar-10 (Krizhevsky) 2009): Cifar-10 is an image classification dataset with N = 50, 000 samples from 10 classes. We manually split each image into (top left,top right,bottom left,bottom right) (ree.))(ree..geen..blu
blocks, resulting in total do 12 feature blocks. EuroSAT (Helber et al., 2019): EuroSAT is a land cover classification satellite image dataset with No = 27, 000 samples from 10 classes, and the images are split into 12 feature blocks the same as Cifar-10.
In the training phase of each task, we manually assign few feature blocks and classes to each client, so that the clients have partially overlapping features and samples and exhibit FH and SH. The settings are summarized in Table 2 It is worth pointing out that in setting ModelNet40:2,, 12.08% of the data have never been used by any of the clients during training, and in all settings, there is no feature or sample that is shared by all clients, so VFL and HFL algorithms cannot be applied. We conduct two sets of experiments on ModelNet40 dataset where setting uses do = 4 views and setting 2 uses full dg 12 views. The first setting has less features, so the classifiers are smaller and the matching procedure is easier and expected to be more accurate. Thus the performance of the server model should be closer to the model obtained with centralized training. the matching procedure is more complex than that of the first setting and should result in worse server model performance. The illustration of the data assignment pattern is given in Appendix C.2
the second setting,
In the testing phase, the clients evaluate their model on all testing samples with corresponding feature blocks used in training phase. We average over the accuracies obtained by the clients to obtain the averaged local accuracy. The global accuracy is evaluated using the matched server model all testing samples with full features.
Training settings: In the experiments, use the MLP model with one hidden layer as the classifier fm (wmi)). -). We use the CNN part of ResNet- 18 followed by one pooling layer as the feature extrac- tors for Cifar- 10 and EuroSAT dataset; we use the CNN part of ResNet-34 followed by one pooling layer as the feature extractors for ModelNet40 dataset. We use the following experiment settings as
8

---

Dataset
dg
Classes
No
Client M
dm Classes/client
Nm
ModeINet40:1
4
40
40k
4
20
20k
ModeINet40:2
12
40k
15k
Cifar-10
12
10
50k
9
6-8
5
25k
EuroSAT
12
10
27k
9
6-8
5
13.5k
Table 2: Experiment settings for each dataset. dg, dm denote the # of feature blocks; No denote the # of samples; M denotes the number of clients.
centrulial
ByP server
- DIyTMM server
Commuticatios: (T)
Commurication" (T)
128
"Commutication (b
125
(a) ModeINee40:1
(b) ModeINet40:2
(c) Cifar-10
(d) EuroSAT
Figure 4: Test accuracy server model trained with HyFEM compared with centralized training and stand- alone training for a) ModeINet4O:1, b) ModelNer40:2, c) Cifar- 10, and d) Eu datasets.
comparison: Centralized training: we train a full-sized server model with all data. This setting serves as the performance upper bound among all trained model. Stand-alone training: each client trains client model only with local data, and without any communication. This setting serves as the baseline (and the performance lower bound) of HyFEM. In all settings, we fix the total number 32) for fair comparison and tune the learning rate to achieve the optimal performance for each experiment separately.
of updates (i.e., T Q 4096, with T 128,
The global accuracy is shown in Figure g under different settings. We can that HyFEM algorithm can train a server model with higher accuracy than stand-alone training in all settings. Moreover, the server models can achieve comparable performance as models obtained with centralized training, even none of the client has full features or full classes of the data. HyFEM can deal with data with SH and FH. As expected, in setting ModeINet40:2, the server model accuracy is lower than in setting ModelNet40:1,, because the matching problem is harder for larger classifiers and 12.08% of the data have never been used by any of the clients compared with centralized training.
Numerical results:
The average client accuracy is shown in Figure 5 for different settings. Client models have lower testing accuracies compared with server models. This is reasonable as the client models are trained with partial features and biased data with partial classes. We also observe that the stand-alone accuracy under setting ModelNet40:1 is higher than ModelNet40:2, as each client has more samples. However, the accuracy improvement with HyFEM under setting ModelNet40:11 is less than setting ModelNet40:2, as the latter one uses more features. Nevertheless, HyFEM algorithm can train much better client models than stand-alone training even the clients do not share the same input space and classes. By using global model matching algorithm, the local classifiers can share knowledge with other clients unseen classes and deal with SH.
CONCLUSIONS
We propose a hybrid FL framework that handles a general collaborative-leamiin scenario with par- tially overlapped features and samples. We first clarify how the data are partitioned in hybrid FL scenario and propose a generic problem formulation. We then show that the proposed formulation covers number of horizontal and personalized FL settings, and develop BCD based HyFEM algorithm to solve the proposed problem. Finally our numerical results on a number of image clas- sification datasets demonstrate that the HyFEM algorithm enables clients with partial features and samples to achieve performance that is comparable to centralized training with full features.
restedized HYFEM
IMTMM cisent
RyPEM
-HynM client
CT
13
30
Commmnation
Commiiication Y8y
129
(a) Mede
(b) ModeINet40:2
(c) Cifar-10
(d) EuroSAT
Figure 5: Averaged test accuracy of all clients trained with HyFEM compared with centralized training and -and-alone training for ModelNet40:1, b) ModeINet40.2, e) Cifar- 10, and d) Eu datasets.

---

REFERENCES
Manoj Ghuhan Arivazhagan, Vinay Aggarwal, Aaditya Kumar Singh, and Sunav Choudhary. Fed- erated learning with personalization layers. arXiv preprint arXiv: 091..9922...... 2019.
Nan Bai, Pirouz Nourian, Renqian Luo, and Ana Pereira Roders. Heri-graphs: A workflow of creating datasets for multi-modal machine learning on graphs of heritage values and attributes with social media, 2022. /RLttt:::///axt
owg.orggg//..... /abs///b//// att.aaba/.0...2 07545
Keith Bonawitz, Hubert Eichner, Wolfgang Grieskamp, Dzmitry Huba, Alex Ingerman, Vladimir Ivanov, Chloe Kiddon, Jakub Konecny, Stefano Mazzocchi, H Brendan McMahan, et al. Towards federated learning at scale: System design. arXiv preprint arXiv: 2019.
Tianyi Chen, Xiao Jin, Yuejiao Sun, and Wotao Yin. Vafl: a method of vertical asynchronous federated learning, arXiv preprint XXX1:2007.0608// 2020.
Canh Dinh, Tung Vu, Nguyen Tran, Minh Dao, and Hongyu Zhang. Fedu: uni- fied framework for federated multi-task learning with laplacian regularization. arXiv preprint arXiv:2102.07148, 2021.
Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar. Personalized federated learning: A meta- learning approach. arXiv preprint arXiv:2002.07948. 2020.
Zhiwei Guo and Heng Wang. A deep graph neural network-based mechanism for social recommen- dations. IEEE Transactions Industrial Informatics, 17(4):2776-2783, 2020.
Filip Hanzely and Peter Richtárik. Federated learning of a mixture of global and local models. arXiv preprint arXiv:2002..055 055500...5556.... 2020.
Chaoyang He, Murali Annavaram, and Salman Avestimehr. Group knowledge transfer: Federated learning of large cnns at the edge. Advances in Neural Information Processing Systems, 33: 14068-14080, 2020.
Chaoyang He, Keshav Balasubramanian, Emir Ceyami, Carl Yang. Han Xie, Lichao Sun, Lifang He. Liangwei Yang. Philip S Yu, Yu Rong, et al. Fedgraphnn: federated learning system and benchmark for graph neural networks. arXiv preprint arXiv:2104.07145. 2021.
Patrick Helber, Benjamin Bischke, Andreas Dengel, and Damian Borth. Eurosat: A novel dataset and deep learning benchmark for land use and land cover classification. IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, 2019.
Yihan Jiang, Jakub Konečný, Keith Rush, and Sreeram Kannan. Improving federated learning per- sonalization via model agnostic meta learning. arXiv preprint arXiv: 19999922480 2019.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances and open problems in federated learning. Foundations and Trends@ in Machine Learn ing, 14(1-2):1-210, 2021.
Sai Praneeth Karimireddy, Martin Jaggi, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebas- tian U Stich, and Ananda Theertha Suresh. Mime: Mimicking centralized stochastic algorithms in federated learning. arXiv preprint arXiv:2008. 03606, 2020a.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. pp- 5132-5143, 2020b.
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. First analysis of local GD on hetero- geneous data. arXiv preprint arXiv:1909.04715 2019.
Jakub Konečný, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXiv preprint /11v:////00005422 2016.
10

---

Alex Krizhevsky. Learning multiple layers of features from tiny images. Master's thesis, University of Tront, 2009.
Harold W Kuhn. The hungarian method for the assignment problem. Naval research logistics quarterly, 2(1-2):83-97, 1955.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. arXiv preprint orXiv:/8/2.061 2018.
Yang Liu, Yan Kang, Xinwei Zhang, Liping Li, Yong Cheng, Tianjian Chen, Mingyi Hong, and Qiang Yang. A communication efficient vertical federated learning framework. arXiv preprint arXiv: 1 2019.
Dianwen Ng, Xiang Lan, Melissa Min-Szu Yao, Wing Chan, and Mengling Feng. Federated learning: a collaborative effort to achieve better medical imaging models for individual sites that have small labelled datasets. Quantitative Imaging in Medicine and Surgery, 11(2):852, 2021.
KM Jawadur Rahman, Faisal Ahmed, Nazma Akhter, Mohammad Hasan, Ruhul Amin, Kazi Ehsan Aziz, AKM Muzahidul Islam, Md Saddam Hossain Mukta, and AKM Najmul Islam. Challenges, applications and design aspects of federated learning: A survey. IEEE Access, 1262222--2 2021.
Meisam Razaviyayn, Mingyi Hong, and Zhi Quan Luo. A unified convergence analysis of block successive minimization methods for nonsmooth optimization. SIAM Journal on Optimization, 23(2):122611153 2013.
Virginia Smith, Chao- Kai Chiang, Maziar Sanjabi, and Ameet S Talwalkar. Federated multi-task learning. In Advances in Neural Information Processing Systems, pp. 4424-4433 4434, 2017.
Toyotaro Suzumura, Yi Zhou, Natahalie Baracaldo, Guangnan Ye, Keith Houck, Ryo Kawahara, Ali Anwar, Lucia Larise Stavarache, Yuji Watanabe, Pablo Loyola, et al. Towards federated graph learning for collaborative financial crimes detection. arXiv preprint arXiv:1909.1220 12946, 2019.
Saeed Vahidian, Mahdi Morafah, and Bill Lin. Personalized federated learning by structured and unstructured pruning under data heterogeneity. In 2021 IEEE 41st International Conference on Distributed Computing Systems Workshops (ICDCSW), pp. 27-34. IEEE, 2021.
Hongyi Wang, Mikhail Yurochkin, Yuekai Sun, Dimitris Papailiopoulos, and Yasaman Khazaeni. Federated learning with matched averaging. In International Conference on Learning Represen- tations (ICLR), 2020.
Zhirong Wu, Shuran Song, Aditya Khosla, Fisher Yu, Linguang Zhang, Xiaoou Tang, and Jianxiong Xiao. 3d shapenets: A deep representation for volumetric shapes. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 1920, 2015.
Liu Yang, Ben Tan, Vincent W Zheng, Kai Chen, and Qiang Yang. Federated recommendation systems. In Federated Learning, pp. 225-239. Springer, 2020.
Qiang Yang, Yang Liu, Tianjian Chen, and Yongxin Tong. Federated machine learning: Concept and applications. ACM Transactions on Intelligent Systems and Technology (TIST), 10(2):1-19, 2019.
Mikhail Yurochkin, Mayank Agarwal, Soumya Ghosh, Kristjan Greenewald, Nghia Hoang, and Yasaman Khazaeni. Bayesian nonparametric federated learning of neural networks. In Interna- fional Conference on Machine Learning, pp. 7252-7261, 2019.
Justin Zhan, Chia-Lung Hsieh, I-Cheng Wang, Tsan- SaanShhnggaa Hsu, Churn-Jung Liau, and Da-Wei collaborative recommender systems. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 40(4):472-476, 2010.
Wang.
Huanding Zhang, Tao Shen, Fei Wu, Mingyang Yin, Hongxia Yang, and Chao Wu. Federated graph learning-a a position paper. arXiv preprint 1109 2021.
11

---

A HETEROGENEOUS MODEL MATCHING ALGORITHM
In this section, we describe the details for the model matching algorithm. First, we describe the mo- tivation behind the design of the classifiers' regularizer (5), which encourage wm 's to be matched together to construct wh is designed. Then we present the detailed version of line 8 - 14 in Algo- rithm for optimizing the regularizer
A.1 REGULARIZER DESIGN
Recall the regularizer for the classifiers is given by:
2 1m wo) = wm Il woll" s.t. 11 E S(dm, do,w),
where dm,u, do the dimensions of Wm: wo and I. is selection matrix corresponds to the unknown pruning pattern. In this section, we motivate why such a regularizer is used, and how the selection matrices 1m are constructed.
We note that the proposed matching method is a non-trivival extension of the neural matching method (Yurochkin al.) 2019) (designed for horizontal FL. the case of hybrid FL. In Yurochkin et al. (2019), the author considered the horizontal FL setting where the sizes and the functionalitiis of all the clients' models as well as the server's 's model are identical, so after matching, the clients can use the matched server-side model directly as their new model. However, in the considered hybrid FL setting, the input dimension of each of the client's inference block can be very different, and the serve-side and client-side models do not share the exact same functionality. Therefore we cannot replace the client-side models with the server-side model. Such a special property the hybrid FL problem introduces some significant challenges for the matching procedure. This is the main reason that in our proposed algorithm, the matching matrices and the client/server models have to be iteratively optimized.
Suppose that for each client m, its classifier (m( has L layers; then the inference block has the following structure:
y = L.,L (Wm,L (Wm. (Wm, Vm)
(13)
where (.),(.)) represents the element-wise nonlinear activation function of layer I; Wm,,'s i's are the weight matrices of layer I, and vm is the input of the classifier which is the stacked output of the feature extractors, i.e., Vm = Hm mm (9mi x). Then Wm = [wm,) = see Figure 6 for an illustration. Let us further define the server's 's output of feature extractors, activation functions and weights as vo {oo.((-. ") similarly as above.
Note that giving selection matrix with appropriate shape 11 E S, left multiply the weight matrix Wm,t by II (IIT Wm,1) results selecting the rows of Wm,t, which is equivalent to selecting the output neurons of the 7th layer. And right multiply the weight matrix Wm., by II (Wm,IIl results in selecting the columns of Wm.t. which is equivalent to selecting the input neurons of the (th layer.
The goal is to match Wm.t's 's with the corresponding parameters wo, at the server. Below, discuss how the first layer, the middle layers and the last layer are matched.
First, recall that the input of the classifiers have the following relation:
H (Om ) P., Ho zo), thatis, vm Pm Vo:
where P., is the selection matrix defined by the feature overlapping pattern between &m and Tn- Then, let us multiply pf on both sides of the above equation, we obtain
PT P Vo PT P'.v... vm
(14)
Note that PT Vm basically pads zeros in the missing feature indices of the Vms so that it matches the size of Vo. Let us define 11m,, = Pm. By utilizing the fact that Pm E S(dm do) is selection matrix, it holds P. = Id... then we have the following relation:
1m, ((wm, mm, (T 1 Vm)) Fm, (Wm, Vn))
This process expands the input v. to the same size as vo. while keeping the output of the first layer unchanged; see Fig. for illustration of this process.
12

---

Next, we would like find selection matrix I1 S that compresses the output of the first layer of the server to match the output of the first layer of client m, as follows:
m (( 1) Vm)) Am, Jo,1 (1 Vo).
(15)
This output matching relation imposes the following assumption on the model parameters:
Wm,1 2o, m.
(16)
To see why (66) implies 15
we can plug (66 into the left hand side of (6). and obtain:
m, (1 HI (TT, m, vm))
0 (m II mm, m, Vm))
mm 0o.1 (Wwo, 11 1 () Vm))
mm T.n1 [W, II m., I1,,1 1) (o))
(17)
1m 00,1 (o 11 Imm.
11 00,1 (wo,
where (i) comes from the fact that projection only changes the order and pads zeros to the output, applying element-wise activation before after the projection does not affect the final output; in (iz) we use the fact that 11T 1mm.1 is a diagonal matrix with I's and 0's on diagonal that can be approximated by identity matrix. The above discussion suggests that, if (16) holds approximately. then (15) holds approximately. As result, we design the regularizer on the first layer between client m and the server, by approximately enforcing (16)
[mm. - 1mm Wo, 11
Let us now analyze the constraint for 1m First, since the dimension of wo, is larger equal to that 1m.1 for each client m, we require that each coordinate of Wm,1 is matched to one coordinate in Wo,1. Therefore need I1, to satisfy
11m,21. Further, each coordinate in Wo,1 should
match coordinate in at least one clients m E [M]'s Wm,1, so this means Σ 1' 2 1.
The above process is illustrated in Fig. S
For the 1th middle layer, its input is the output the previous layer. By fixing the projection matrices (.mm that match the output of the 1)th layer at each client to the output of the (I - 1)th layer at the server, the matching problem for the 1th middle layer takes the same form as the matching problem for the input layer: the output of the previous layer mm,--1(-) corresponds to the input wm
the projection matrices m J correspond to input projection matrices (Mm.. JM m= the goal is to find the projection matrices [1lm.++]] LM that match the output of the (th layer at each client to the output of the same layer as the server.
By using the same argument that we used for the input layer, we design the regularizer on the 1th middle layer between client and the server
Wm, 1m, m.
2
W,
W2
W1.3
W2,3
W1.2
W2.2
W1
W2
27
0,,1
,,
02.2
0
Figure 6: Illustration of the layer structure of the inference blocks on the clients, for the L case.
13

---

W111
P1.1
0L.3
0
0..2
81.3
W2,1
W2,1 IT
27
1l
22.2
02.3
02.2
02.3
Figure 7: Aligning the input of the first layer by rearranging and padding the corresponding coordi- nates of the input Vn and the first layer Wm.1.
Wo.1
11
11
W2,1 nT
Figure 8: Aligning the output of the first layer by rearranging and padding the corresponding coor- dinates of the first layer tm,1-
For the last layer, the output at each client the same as the server, which are the predicted label. Therefore, the projection matrix of the output for the last layer are identity matrices, and we design
the regularizer for the last layer as
2 W|m_L - Wo
Next, by vectorizing Wm.1's 's we have following relation:
vec(Ulm.4110 = (IIm.1 @ lm..41 veecwoo)))
where & denotes the Kronecker product. Therefore the regularizer for each layer can be rewritten as
1
2 |ve([um.) (IIm,t & Im..+1 (mm.-))rec(woo))l
Finally can stack the sub-vector (vec(Wm, He into Wm, and define the projection matrix of long vector as
11m = diag((1lm.1 @ 11m.2).... (1m,, & I))-
Again, 1mm is block diagonal matrix, and it is easy verify that it satisfies the following conditions:
M
IT 1, Σ I1I 2 1; 2 0.
(18)
m=
Finally, obtain the final formulation of the regularizer
14

---

Algorithm 2 Sub-routines for Algorithm
1: ClientUpdate 0h, 1m w6. Q.1)
2: Initialize: t + Pm Oo t.0 + IT wb
3: for 4==4000 0y....... Q do
4: Uniformly sample E N
5: 1 <- 6 y Ve... ((Fm (w ; Hm (0 (m.ma)))...
=mma))))m yn) + uI Pr 0))
6:
wh++1 wha n (V wm El FF ( Hm (0:.0 Fm,,n) Un) ) p2(witn II w/))
7: Output: 0 w
8: ModelMatching( ( II ) m= wa. P)
9: for p O.....
10: for m I,..., .M in parallel do
wo mm Pm (M
(2 (Emmm Pm (I wh
12:
IT arg m T'm (1 I'', wb 11 Using Hungarian algorithm
13:
wo ++1 + (EM=1 Pm ""tn"""i
(EM Pm (m Twiin) IItt1 + II.m
14: Output: wo {I1m
1+ [II++11
Algorithm Model Matching Procedure
1: ModelMatching
LM 2: Input: (w 11
m=1, wo. P
3: for p O...., P do
4: Uniformly sample m' [M]
5:
wo
(m Pm "1'"""
11'2
E Emioon Pm (I1")) Tw
6:
for 1 I,.... -- do
7:
Construct cost matrix C with (20)
8:
T + arg min,, En, (i,J) Cc(i,)),
// Using Hungarian algorithm
9:
Em= Pm (I (IT.))
( Pm (m (I IIt
II,,.
10: Output: w+1 1II++1 1
/m=l
(m Im wo) - 1m
Vm [M]
M Σ
(19)
where Im''s 's satisfy: II, E S(dw. dww,))
I 2 12
dui
m/
A.2 OPTIMIZATION PROCEDURE
In this subsection, we describe the detailed procedures in line 14 of Algorithm to optimize the classifier matching problem (5) or its more detailed formulation (19). The procedure with more details is given in Algorithm
We iteratively solve the matching problem 11] for P iterations. In each iteration, we randomly pick a client m' match it with the server's classifier from the first layer to the last layer.
For the first L - 1 layers, we first fix Iw and construct an assignment cost matrix C that computes the cost to match jth row in client m' to 5th row in the server of layer / for all (i,j). The element ji of the cost matrix defined as:
disty
wmlll)
Io #
Ci(i,)) = ddist?
(20)
otherwise,
where IT [+ and [i],[j]] denote the 4th and 5th row of the matrices, dist, is the similarity cost for matching Wm] to an existing row, and dist2 is the dimension penalty to match Wm. [
to new row in Wo,1. One specification the cost functions is PFNM (Yurochkin et al.) 2019) that
uses the MAP loss of the Beta- Bernoulll process, where dist, is based on the Gaussian prior and distz follows the Indian Buffet process prior. Then we can solve the assignment problem to obtain Th with the celebrated Hungarian algorithm (Kuhn 1955).
15

---

Note that for the first layer, the matching pattern Im,o is given by Immo Pm.. And we do not need to match the output layer.
B CONVERGENCE ANALYSIS
In this section, we analyze the convergence property Algorithm 1 assumptions on the problem:
We first make the following
(Block Lipschitz Gradient) For each parameter blocks in {wms mm LM there exists an L.n such that the following holds:
Ve Im (m, Wm) Ve,, fm (8'm: w + || Wnm (0m: Wm) - V why I' (6'm wmm)]
I Lm (1 - O'mll + 1m - w'n
Om, O' Wm: Wm
(Lower Bounded Loss) There exist finite lower bounds for each client classification loss, i.e.,
3 fm D0, s.t. fm ( Wm)) 2 fm
W Wms m.
(Bounded Variance) The stochastic partial gradient estimation has bounded variance og and
2 i.e.,
En Vem E(Fm (Wmi Hm (m I -m.,)) Mos) Vem f' (Wms mm)l S o V Oms Wm: V m [M],
En V wm {(Fm Hm m:; Lm.m )), yn)) Vmm fm (wms 0m)l < oi, y Oms Um: V m E [M].
We can abstract HyFEM to BCD algorithm by redefining the model parameters and the prob- lem as follows:
1. Define x 19:...... Mi wii... wM.. y == [vec(II]): ... vec(IIa))] and == [Ou: wo]-
2. Define L(x, := >m= (fm (9m, Wm) + Tm, (Qm, θo) + #2 Tm,2(umm 1mm wo))
Then the optimization problem 6 can be simplified as:
min [(x. y. 2), s.t. y Rangely). x.y.2
(21)
Moreover, the algorithm can be simplified as:
x x = x xxxx(x' y' 2²), forg = 0, 0,..,,Q-1
(22a)
y+1 arg min L(x y,,"),
(22h)
yERange(y)
z+1 arg minC(x 1+1 z),
(22c)
where we assume x *+10 x+1 1 and V C.C() denotes the stochastic partial gradient of
We make the following assumptions to problem 21
(Block Lipschitz Gradient) block smooth, and for parameter x and there exists positive constants Lx, Le and Cx such that the following holds:
[Vx C(x y, 2) < Lx ||x
x'|
[1, x z, Range(y).
|V VxL(x,N, S Cx ||z
z'll V2, Vy Range(y).
A 5 (Block Strong Convexity of z) For parameter there exists positive constant μ.. such that the following holds:
L(x,y, 2 > ((x.y,z) + (V,L(x, + - 2 V Vy E RRngely).
(Unbiased Stochastic Partial Gradient) The stochastic partial gradient of unbiased:
E EV,((x.y,2)
v. Vy Range(y).
16

---

A 7 (Bounded Variance of Stochastic Partial Gradient) The stochastic partial gradient of x has bounded variance o²:
VxL(x,y.z) Vx[(x,y. 2) So, E Rangely).
(Lower Bounded Function) The problem L is bounded from below, i.e.,
3 s.t L(x,y, 2 C. Vx,z, Vy Rangely).
A 9 (Compact Constraint Set) For parameter y. the constraint set Range(y) is compact.
Note that in 4 and AS] while block y can be non-smooth and non-convex and x can potentially be non-convex. Further we assume that v is smooth w.r.t. 2, which is non-standard, but can prove that it hold for problem (6). The rest assumptions Ao are common assumptions when analyzing stochastic algorithms. Further verify that the above assumptions hold for the original problem (6).
only assume blocks x, z smooth, and only block is strongly convex
Lemma 1 Suppose (6) satisfies assumptions A then it satisfies A 4. with the constants in the assumptions given as:
Lx max + max Cx max p23
M
# 2 (pm) min(,r),2), 0² og 0 L Σ
Pm Jm.
The proof is given in Section B.2
Then we have the following result:
Theorem Suppose the problem (11) satisfies A9 and 22 for T iterations with stepsize 7) S min
1 By
). Then the sequence (x y t= generated by satisfies:
5C2
Σ
1 ||
2211 + Lxx(x ytt )
Vx ,²,,,,))
TQ t=0
17
(23)
10
2L217 0²,
(c(x); ,y" ,/,,-))-1 C)+
+ -) 55xx1 +
TQn
and L(x'' . y , zz 2²)11 0, Vt e ET).
This result indicates that by setting Q = T, =
2(C(x) yxx²))
the right-hand-side (RHS) of
LxQTT
23 becomes 10c /2(C(x y0.2%) ) - Dbb (Lx( -)
00+ (+). Let us analyze the left-hand-
side (LHS) terms of (23 First, we have
1 T-1
/ T-1
11
2
Σ E 2² =0
-
1 1 =2
2
z
TQ
11
T 1=0
t=
indicating that E ||z - 2=====00 =0 =+)). Second, we have
1 E
[x((xt+] t+1 2²)|| C( y", v22 o x+())
TQ
t=0
where the LHS is the sum of T(Q + 2) terms of 2| divide by TQ, which also indicates that
V Lx y >²2 O ( Together we have that algorithm (22) finds a stationary solution
of 22 w.r.t. x, z with rate o + Combining Theorem 2 with Lemma | we have that by running
Algorithm| parameters {wm, θ m= converges to their stationary point of (6), while (II,, 1M stays in compact set.
17

---

Alternatively, if we assume the solution to y is unique, and update is one-step gradient descent, i.e. Q = 1 and
I+1 x² V 22),
then by applying [Razaviyayn et al. 2013 Theorem 2), Algorithm T asymptotically converges to the first-order stationary point of (6).
B. PROOF FOR THEOREM
We begin with proving the following descent result:
Q Σ
E' [(x 1(x (1t1122t1 21t1) L(x', ,-,,""")))) 22,2) s
" E VxL(x19 yy x1)1
(24)
おい || - 211 + QLx1
2
where we denote the expectation conditioned on the information up to iteration t as E.. First, we write the LHS of the above equation into three terms below:
C(x+t1, y
[(x', y',z') (C(x+t) .y t 20t1) L(x .ytt1, 22)) 2-,1,2+1) 2111) 1
+ (C(xttl ,y , 2²) [(x ,²,)²))
(25)
+ (C(xtt2, ,y ,y',z') L(x', ,e xz)).
We bound the three terms on the RHS of the above equation separately.
1) The first term (C(x+t1 y 11+1)= C(x'+1, y
1/a zz)) can be bounded by applying A5
[(x ,
yt1 z x2) [(x'+1 +1 y x²)
V [x 1+ , 11, ) - -z"+11 z²+1) r+1 z11?
(26)
(a)
+++ z'
where in (a) uses update rule (2cc) that by exact minimization V. Cx 1.y (x(11) =
2) By the update rule (22)) the second term (L(x++1, y 10+,1,21 z²) [(x'+1 .y 2()) can be bound
by
C(x++1 y z²) L(x y" 2²) 0.
(27)
3) The third term (C(xtt), ,y',²) L(x", ,y',²" 2² can be further decompose into:
[(xt+1, ,,,2") L(x", " x²) = L(xt y 2²) - [(xt.", .y', z²)
Q-1
(28)
Σ (C(x ,²",²') L(x y v2)2
where the first inequality uses the definition that x x and x x". Then we bound each term in the summation as:
VxL(xt9 y x x² + lxx
L(x _y,²") L(xt 9xx.9.y' y
1x/91] - -xte
2
224
77 Vxx(xxt.,y)) y" n²), VxL(xt ,' +
Lx12 (x y", 22))
2
(29)
18

---

Taking expectation on (t, g), we have:
E C(x 2²) [(xt12 y z²)
$ 11 V Vx 2. y 2²), E V Xx((x"",''' ,²,)' + Lxn E
2
(a)
X 4. y 2z') )| + 2 Vx[(xt9 ,'',''(( z²1
1xn1
(30)
Lx
E
VxL(x!1 M,,.,,y y" 2²) - VxL(x'* 2 y" 22)
7
11 Lxll"
|| )1 1x2100²
2
where (a) first applies the fact that ((x²) = (EX)² + - ((())))))) to the second therm, then applies to the first and the second term
By picking 7 S Ix and substituting 330 to
28
we have:
Qixepo²
E [(x ,',zz' [(x', y¹
E²t
(31)
2
0=0
Then we substitute (6) 27 and
back to
25 then we obtain 24
To prove Theorem we need to further bound
V ((x y )l and VxL(x
,
We bound them as follows. Term [x((x++ y 2 yl can be bound as:
E
1/ C(x
2 VxL(x* 1-11 21)1
+ - 2
C(x y 2¹) VxC(x ,y' 2
4
21
x-000 x 00- 112 11' + + yy' 2
(32)
2 B1-011 Vx 0-1 ,y' |
+ + / V x²
-7 (2 + " Vx Q-1 , 2'12 + 222
where in (a) we add and subtract V VxL(x*001 y 2²) and apply
inequality. Sim-
ilarly, term | [xx , zz) || can be bound as:
(0)
VxL(xt+1 y )1
3 2 V Lx ytt1 x²) - V Exttx11 ,tt1 , , /12
2 V Cxx
+1 , )1
2
4
20
1
++ z $1 + 2 Xx +1 . zz 11
(33)
where in (a) we add and subtract VxL(x!+1 yl1 + and apply Gauchy-Schwarz inequality.
Then we sum the above results as 24
x 2 + 32 x + 33 x nタ and obtain the following:
2 ((x yt+ zz 12)
2C(x' .y' zz
B ((x (1xxtt,y","" 2²
Q-1
+ 7 || V L(x +1 +1+ ,2))1 v - Σ
E' VxL(x* 1: y ,xxzz()) 2z)11 11 1 z¹12
5
p=0
(34)
+ QL222 0² +
2021
| =z/12=
2n
VxL(x yeth
, 221111
5
2n + 2122
2022202
+
VxL(x'10
2) +
5
5
19

---

Rearrange the terms, notice that choose
1 that 2ny 2 4n, have:
Ixx"
E² V || " E // Vx y )|1 11? + (1- 20
||
n
- 2 ( y", 21) - Et' 1(x ,
y z(+1)) + 5
QLxx1
o².
(35)
Sum the above equation from to T 1, choose μ side by nOT then Theorem is proved.
202n
2
1
(17 S
8u sc2
). and devide both
5
5
B.2 PROOF FOR LEMMA
In this section, verify the assumptions AD for the original problem A A
6 under assumptions
Recall that we have the following corresponeance:
x: i Aai: i warl, == [vec(ll);....,eeee)) vec(Llar)), z = wp]:
((x,y,z)= Σ Pm (fm (f wm) p1 Tm,, (0m: Ao) + #2 Tm,2( Um wo)),
1
1m..10mmm 4o)
110m - Pol
2
M
1
7m,2(Wm Im,, wo)
2 1|um Wol?, s.t. Im E S(du,m dw;,),
Σ m=1
17
II, 2 1 12m
1) For A4 we have
Pm Ven ( Wm) pm Pm 0o)
vx[(x,y,z)
Pm V nm Jm m,, Wm)) + Pmf22 (wm - 11 wp) m==
Therefore we have the following bound:
||Vx[(x, 2) Vx
M
Pm Ve fm (m,, Wm) + p1 Om Vem w/n) 6'm
m=l
M
+
Pm V um (0m: Wm) + p220m
V Wm fm ( w'm) m221rm
m=1
M
Σ
Pm e fm (m,, Wm) Ve fm w/mill Mu ||0m 6'm II)
M
+
Pm (1IV wm (0m Wm) - Vam (m mi w'n Il + M2 1/00 w// II)
m=1
M
Pm ((Lm + m1m- - O'm + (Lm + =2) -1|um - w/mll)
m=
M Σ m=1
< maxx(pmll max(Ni,
(| - O'm + I|wm w/n 11)
= Txx x x'11.
where we obtain Lx = maxm {pm Lm + max H22} Also, we have
M
[V - VxC(x,y,2')1 = Σ
pm (m | (On - e6)l + + [1m.aus - w()
m=l
20

---

M
min Pm (01 Pm 110p - @ + 122 [[T 11000 - w6ll)
m=l
M
Pm (14 |10p 0'll + /22 ||w00 w/ol)
m=1
(6)
S m μ2n (1 0oll + |/w0 w/ II)
Cx ||z z Il
where in (a) we use the fact that Pm S(dm: do), Imm S(dw, dw are selection matrices so that |m = 1, [m || 1; (b) uses the fact that > Pm = 1. Therefore A4 is verified.
2) Next, verify A5
We proceed by directly computing the second derivitive of
V2 y,
M
V2 Vi : Tm,1 + 422 Tm.2
Ve V WooHl Tm,11 + P2 Tm, wi M1 Tm, + P2 Tm,2
Pm
Ve. V wo Pmm11 + P2 Tm.2
m=1
P11 Im=1 Pm PT P
#2 m= Pm II Im
M
Then we analyze the range of the eigenvalues of this matrix. First we know that I1m, Pm are selection matricies, therefore pl Pm, 11 Um are diagonal matricies, indicating that V (x,, 2, is also a diagonal matrix.
For the first block μ* EmE Pm PT P Pim, we have that Pm 's are the feature selection matrix, i.e.,
dn II Dr- i=1
Fm Pmmoo Fm E Xm
D,, iETm
II
20 E Xo
is clear that client mn has the 7th feature, then the 7th diagonal entry of p2 Pm is pT Pm(i. i) = 1,
and pl P., P.. (2, 0 otherwise. That is, the following holds:
E1,iEZm,
PT Pm (1,
0 Im.
Further have that the full feature space Xn is the union of the clients' feature spaces, i.e., UmE[M] M]] Im = [do]. Therefore, we have
Σ PT Pm 2 1T and min do) m=1
Σ
Pm m P. (i, 2 min(pm).
==1
Similarly, the constraint II,, 's that EM IT II 2 1J du. indicates that the following holds:
min EE E
Σ Pm II Il (i,t)
m
Therefore, the Hessien matrix V z) is positive definite, with smallest eigenvalue μ > minm {pm} min(ui, 32). Thus AS is verified.
3) Ab holds true in Algorithm I uniformly samples E Nm. for all m E [M], therefore
E, Ve.. ((Fin (wm: H ( Fm,,)) yn) Ve.. f' ( Wm)): E, wm ((Em (mm Hm (0mi Im,,) )), yn) = V Vem fm ④ my Wm))
Further, from AB obtain A7 with o² o3 oz
21

---

Client index m
Assigned features Zm
Assigned class #
I
1,2,3
25
1,2,3
25
3
1,3,4
25
4
1,3,4
25
5
1,3
25
6
1,3
25
Table 3: The data assignment pattern for MultiView40 dataset. Note that 6.88% data has never been used.
Client index m
Assigned features Im
Assigned classes
1,2,3
1-5
1,2,3
6-10
1,3,4
1-5
1,3,4
6-10
1,3
1-5
6
1,3
6-10
Table 4: The data assignment pattern for Cifar- and EuroSAT dataset.
4) To verify A8
we apply AD
that:
M
((x,y,2) Σ
Pm (0m, Wm) + 11-11-Tmmm Tm,,1(0m Ou) + M2 (mm Im wo))
m=1
M Pmnfm (9 Wm)
-
Σ
Pm Im : C.
where (a) uses the fact that Tm, (mm, Oo) = 2 1 - Pm Opll 2 0 and fm, Im, Wp) =
[wm - w 2
5) A9 directly comes from the constraint on Im 's that
11m E S(dw.m dw;o)s
Σ
1 du... 11m 2 17
m=1
which is compact set.
At this point, we have verified constants summarized below:
AD for problem (6) with Algorithm T and the corresponding
Lx max max(pmLn, Lm + max(f11,22H Cx = max(ui,
m
M
2 min(pm} min(ur, u2), =²=0²² =0 f Σ m=
Pm
This completes the proof for Lemma
C ADDITIONAL NUMERICAL EXPERIMENTS
In this section, we include additional sets of numerical experiments. the first set of additional experiments, we reduce the feature heterogeneity of the data on the clients by allowing clients to have common features, so that HFL. algorithms such as FedProx and FedAvg applies. Further, we include an additional multi-modal dataset with both image and text features.
C.I COMPARISON WITH HFL
In this section, we conduct numerical experiments to compare FedProx (Li et al. 2018) with HyFEM. In the experiments, split the features into dg 4 blocks for the datasets and assign
22

---

0.
Stand
Centrilied
HyFTM-Srreer
Serrver
Feddyg Server
Pedlirg Server
FedAig Server
Commanaciion
Communonioo
Communorioon
(a) ModelNee40
(b) Cifar-10
(c) EuroSAT
Figure 9: Test accuracy of server model trained with HyFEM compared with FedProx for a) ModelNet40, b) Cifar- 10, and c) EuroSAT datasets.
Accuncy
Accunsy
Sondsttonz
Soadsalonn
Sond-aatee
INFUM Client
TyFEM Client
FolAvg-Clieut
FolAvg-Cliett
Falloy--lian
Cantrlizee
CCnitalized
Centralired
Commmnction
24
66
Commineriin
26
Commmezioon
24
64
(a) ModelNNe40
(h) Cifar-10
(c) FuroSAT
Figure 10: Averaged test accuracy of client models trained with HyFEM compared with FedProx for a)
ModelNet40, b) Cifar-10, and e) EuroSAT datasets.
the first and the third blocks as the common blocks for all M = 6 clients. Then we can apply FedProx to train model with the overlapped features and compare with the models trained with HyFEM with more features. The detailed data assignment patterns for different datasets are de- dataset, there are 6.88% of the data has never been
scribed in Table 3 Note that in used by HyFEM and 50% of the data has never been used by FedProx. For Cifar- 10 and EuroSAT datasets, all data has been used by least one client with HyFEM while 50% of the data are dropped by FedProx.
For Cifar- 10 and EuroSAT datasets, we split each image into (top left, top right, bottom left, bottom right) total dy 4 feature blocks. For MultiView00 dataset, we choose four views of different angles of the objects as the full feature space. The total communication round T 64 and local update # Q = 32 are fixed for all experiments. We conducted line search on the learning rate v) and (12 for the algorithms to obtain the best performance.
The results for the datasets are shown in Figure[Jand Figure 10 From the results, can see that the models trained with HyFEM can obtain better performance than FedProx. This is because HyFEM is able to use more data than FedProx by using heterogeneous models.
C.2 DATA PARTITIONING PATTERN
In this subsection, provide the data partitioning patterns for each settings. Notice that in Fig- ure [T),,, and Figure a2)a), the black boxes with 0 inside them indicate that the corresponding feature block of the samples in this class has been used for training by any of the clients.
C.3 EXPERIMENTS ON HERIGRAPH DATASET
HeriGraph (Bai et al. 2022 dataset is a multi-modal dataset for heritage site classification. This dataset consists of total No 41, 621 samples from 9 classes. Each sample has most do preprocessed feature blocks, including one text feature block and three different image feature blocks. Note that not all samples have all features. For example, only 25, 325 samples have text features, and the rest do not. We will include the result for this dataset in the revised manuscript.
In the experiments, use MLP of different sizes as feature extractors for each feature block. We set client number M = 6, client feature block number d., = 2 and each client has out of classes.
the MLP model with one hidden layer the classifier fm (u -). We
23

---

ModelNeste
2
2
0
0
3
O
3
2
3
O
3
3
2
3
2
0
2
2
0
1
0
3
2
2
5
2
10
0
0
0
2
12
0
0
ModeINet40:2
2
3
3
3
3
4
2
3
3
2
4
4
2
2
2
3
2
2
4
4
3
1
2
2
3
3
2
3
2
3
1
3
3
3
1
2
2
3
4
3
3
3
3
3
4
3
2
10
11
2
3
3
3
2
2
12
2
2
4
1
2
4
5
6
7
8
10
(c) Cifar- 10 & EuroSAT
The illustration of how many clients (the numbers in boxes) possess the training data of each feature block in each class for the settings in Section 4 with a) ModelNet40:1 with do = 4 features, M = clients, and 40 classes; b) ModeINet40:2 with do 12 features, M = 8 clients, and 40 classes; Cifar- 10 & EuroSAT with dg 12 features, M clients, and 10 classes. The z-axis of each plot the class axis and y-axis is the feature axis.
Figure 11:
The result is shown in Figure 13
The server model trained with HyFEM has comparable perfor- mance as the centralized trained model. The average performance of the clients' models has worse performance than full model due to lack of full features and classes, but the accuracy is 20% higher than the models obtained with stand-alon training.
24

---

0
0
ModelNet40
1
10
(b) Cifar- 10 & EuroSAT
Figure 12:
The illustration of how many clients (the numbers in boxes) possess the training data of each
feature block in each class for the settings in Appendix[..] with a) ModelNet40 with do = 4 features, M = clients, and 40 classes; Cifar- 10 & EuroSAT with do 4 features, M clients, and 10 classes. The z-axis of each plot is the class axis and y-axis the feature axis.
0.8
0.8
Test Accuracy
Test Accuracy
0.6
0.6
0.4
0.4
centralized
centralized
0.2
stand-alone
0.2
stand-alone
HyFEM server
HyFEM client
96 Coomuuiicatinn (T)
64,
128
0
32
96 Communication (T)
128
(a) Server
(b) Client
Figure 13: Test accuracy of a) server model, b) client models trained with HyFEM compared with Centralized training and stand-alone training for HeriGraph dataset.
25


Reviews:
[{"review_id": "sskqg01zQDa", "reviewer": "Reviewer_FpoP", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the hybrid federated learning setting, where both samples and features can be different over clients. This setting is a combination of the horizontal and vertical FL. The main contribution of the paper is the HyFEM algorithm, where clients learn a model locally based on the available samples and features, then a matching algorithm is used to combine the local models. In empirical studies, authors show the proposed algorithm outperforms the standalone training baseline, i.e. only train local models.", "summary_of_the_review": "This paper studies the hybrid federated learning setting, where both samples and features can be different over clients. This setting is a combination of the horizontal and vertical FL. The main contribution of the paper is the HyFEM algorithm. In empirical studies, authors show the proposed algorithm outperforms the standalone model baseline. The paper is well written and easy to understand, but the novelty of the proposed algorithm is restricted, furthermore, the empirical evaluation is not sufficient.", "strength_and_weaknesses": "Strength:\n\n1.\tThe paper is well written and easy to follow in general.\n\n2.\tHybrid federated learning is an important setting with some real world applications.\n\n3.\tThe proposed algorithm is accompanied by convergence analysis.\n\nWeakness:\n\n1.\tThe matching algorithm used in Algorithm 1 is a straightforward extension of the FedMA [1] algorithm. The analysis follows [1] in general, but a small difference of the paper with [1] is that clients could have different number of neurons, furthermore, only the fully connected network case is analyzed, can the classifier use other architectures, such as CNN, LSTM and Transformer?\n\n2.\tThe empirical evaluation is not sufficient. Firstly, only vision datasets are used to do evaluation, while other more realistic applications are missing such as the medical diagnosis, recommendation systems and social networks (These applications are also used as the motivation of the paper). Next, more baseline methods are desirable. In the experiment section, the major baseline is the stand-alone model, which is a very weak baseline. For example, another important baseline could be the vertical FL method, where the different sets of features over clients are explicitly aligned. One of my concerns to the proposed HyFEM algorithm is related to this: the HyFEM algorithm does not (directly) model the interactions between cross-clients features, there might be some indirect exploitation, but empirical evidence is desired.\n\n[1] Hongyi Wang, Mikhail Yurochkin, Yuekai Sun, Dimitris Papailiopoulos, and Yasaman Khazaeni. Federated learning with matched averaging. In International Conference on Learning Representations (ICLR), 2020.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "U9wCs2xvhR", "reviewer": "Reviewer_3J31", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "    This work designs a novel mathematical model that effectively allows the clients to aggregate distributed data with heterogeneous, and possibly overlapping features and samples.", "summary_of_the_review": "Overall, the reviewer finds this work provides some interesting results, but the could be improved by a thorough discussion about existing work in the area, and more experimental results could be provided for the efficiency of the work.", "strength_and_weaknesses": "\nThe major concern of the reviewer is missing references and discussion with existing works on hybrid federated learning. \nhttps://openreview.net/forum?id=H0oaWl6THa\nhttps://dl.acm.org/doi/abs/10.1145/3467956?casa_token=fegJizVFAJsAAAAA:x52Xyyfu4dTfvf9SmIFyGB8wc8z868hUfrRj_o7pB9hu8ayIc2mrByOH5ib1Yf4uo8RewEc0KfyPAg\n\nAs mentioned by the author, the algorithm seems quite complex. But the complexity of the algorithm is briefly discussed but not evaluated in the experiments. It would be useful to provide experiments ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "L9tAq77PkD", "reviewer": "Reviewer_AHQz", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper considers a hybrid federated learning scenario (both sample and feature levels). To handle heterogeneity in the feature level, the authors adopt an idea from VFL to split the model into blocks. Each model block corresponds to a feature block. To handle heterogeneity in the sample level, the authors use a model matching method (proposed in HFL methods). A novel algorithm called HyFEM is also proposed to solve the hybrid FL problem.", "summary_of_the_review": "Overall,  the proposed algorithm is reasonable for the challenging \"SH + FH\" scenario.\n- However, the settings in the experiment are simple, and the experimental results are not sufficient to verify the effectiveness of the proposed algorithm in real applications (as listed in Introduction).  \n- As the algorithm is a bit complicated, another concern is its run-time complexity.", "strength_and_weaknesses": "Strength:\n- The authors consider a challenging hybrid scenario (heterogeneity in both sample and feature levels) and propose a novel algorithm to address this problem.\n- For the proposed algorithm, its convergence is established, and its performance is examined empirically.\n\nWeaknesses and Questions:\n- **(major)** Experiments: although the experimental results can verify the effectiveness of the proposed algorithm, the settings are not from real applications. If the experiments include some applications listed as motivation in Introduction, the results will be more convincing.\n- **(major)** Concerns on run-time complexity: \n    - In Line 7 of Algorithm 1, $P_m\\in \\mathbb{R}^{d_m\\times d_0}$, thus, $\\sum_m p_m P_m^\\top P_m \\in \\mathbb{R}^{d_0\\times d_0}$. (1) As $d_0 > d_m$, this matrix can be singular. (2) It is expensive to invert a $d_0\\times d_0$ matrix when $d_0$ is large.\n    - For each iteration, the server needs to solve the minimization problem (11). Is it possible to get the minimizer exactly?\n- Nine assumptions are required for establishing Theorem 1. Are these assumptions standard in establishing convergence for other FL algorithms?\n\nAdditional Questions:\n- “VFL algorithms require all the clients to have the same set of samples; otherwise, they cannot compute the loss and its gradient.” Why? Can you elaborate on it?\n- What’s the total run-time complexity of Algorithm 1? \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "HCluQ8YIiQC", "reviewer": "Reviewer_Ss8B", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a novel framework for learning with distributed data that can be heterogeneous on both features and samples. In this framework, each client’s model is partitioned into a feature extractor part and a classifier part. The feature extractor is used to process the input data, and the classifier will make a prediction based on the extracted features. A server model is then built based on these client models to assimilate local classifiers and feature extractors through a carefully designed matching mechanism. A communication-efficient algorithm is then designed to jointly train these models. Experiments on multiple image classification data sets demonstrate that the proposed algorithm can improve upon baseline methods under hybrid FL setup. ", "summary_of_the_review": "This paper considers a novel setup for federated learning and proposes a new method with better empirical results than simple baselines. From my perspective, the proposed method still needs more clarification and empirical results can be further improved. Thus I choose weak reject as my initial score. ", "strength_and_weaknesses": "Strength:\n- This paper considers a novel setting for federated learning and proposes a novel method to solve this new problem\n- Empirical results against some baseline methods demonstrate that the proposed method leads to substantial improvements\n\nWeakness:\n- Method part:\n  - It seems that the proposed method assumes different clients at least has some shared features, i.e., there is no set of features that are only presented in one client. That seems a bit restrictive from my perspective. The authors may explain how such assumption is satisfied in real-world data. \n  - I suppose the proposed method actually tries to make extracted feature similar with different raw features. Nevertheless, that may not always be the case, as different raw features may have different but complementary semantics that need to be used together to obtain accurate final predictions. This can be a limitation of the proposed method and I am afraid some explanations are needed for that. \n- Experiments part:\n  - Based on the concern above, the authors may also consider using some other data sets. An example could be text data, where different parts of text can naturally have very different meanings. \n  - I am a bit confused on the exact setup of “stand-alone” baseline in experiments. Since different clients have different set of features, standalone training will lead to completely different models. As such, which model is chosen to report its performance? Some clarifications may be needed for that. \n  - Also, there seems to be some unfair comparisons in experiments. I suppose models in “stand-alone” baseline can only utilize the feature set on a single client. That should surely lead to worse performance due to information lost from unseen features. As such, another baseline that seems overlooked is to use ensemble models trained from different clients, which can make use of all features hence avoid possible unfair comparisons. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject