Hybrid Federated Learning for Feature & Sample Heterogeneity: Algorithms and Implementation
Authors: Xinwei Zhang
Wotao Yin
Mingyi Hong
Tianyi Chen
Venue: Accepted by TMLR ()

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 {\it both} the feature space and the data samples are {\it 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.

Published in Transactions on Machine Learning Research (04/2024)
Hybrid Federated Learning for Feature & Sample Hetero- geneity: Algorithms and Implementation
Xinwel Zhang
zhan623, @umm. edu
Deportment of Electrical and Computer Engineering University of Minnesola
Wotao Yin
volaogiin@mattie ucla. edu
Department Mathematics University of California, Los Angeles
Tianyi Chen
chent18@rpi edu
Department of Electrical and Computer Engineering Rensselaer Polytecknic Institute
Mingyi Hong"
mhong edu
Department of Electrical and Computer Engineering Universily of Minnesola
Reviewed on OpenReview: https: // openreview. net/ form?? id= gc2lmbikkk
Abstract
Federated learning (FL) a popular distributed machine learning paradigm dealing with dis- tributed and private data sets. Based the data partition pattern, FL is often categorized into horizontal, vertical, and hybrid settings. All three settings have many applications, but hybrid FL remains relatively less explored because it deals with the challenging situation where both the feature space and the data samples are heterogeneous. Hybrid FI. combines the advantages of both horizontal and vertical FL, addressing some of their individual limita- lions, such as the same-features requirement of the former and the same-entilies requirement of the latter.
This work designs novel mathematical model that allows clients to aggregate distributed data with heterogencous and possibly overlapping fcatures and samples. Our main idca is to partition each client's 's model into a feature extractor part and 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 featurcs. The heterogencous fcature aggregation is done by building a server model that assimilates local classifiers and feature extractors through a carefully designed matching mechanism. 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 ion and algorithm developed for hybrid FI..
communication-eliiceent algorithm is then designed to
1 Introduction
Federated Learning (FL) is an emerging distributed machine learning (ML) framework that enables hetero- gencous clients such as organizations or mobile devices collaboratively train ML models (Koncčný
"The work of M. Hong and X. Zhang was partially supported by NSF grant APCCN-331100 and 20033003 This work is also part of AL-CLIMATE: "Al Institute for Climate- Land Interactions. Mitigation, Adaptation, Tradeoff's and Economy: and is supported by USDA National Institute of Food and Agriculture (NIFA) and the National Science Foundation (NSF) National Al Research Institutes Competitive Award 2023-67021-3983
The work af Chen was partially supported by National Science Foundation Grant 2047177.

---

Published in Transactions on Machine Learning Research (04/2024)
Table 1: Examples of applications that generate heterogeneous data
Application
Client
Feature Blocks
Sample
Medical Diagnosis
clinic
output of different diagnostic devices
patient
Rocommendation System
retailer
record of different product categorics
customer
Social Network
SNS provider user activity & relationship
SNS user
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 requirements.
The challenge due to heterogencous data is particularly evident in FL. The most well-known form of hetero- gencous data is sample heterogeneity (SH), where the distributions of training samples are different across the elients (Kairouz et al. 2021: Bonawitz et. al. 2019). Severe SH can cause common FL, algorithms such as FedAvg to diverge (Khaled et al. 2019 Karimireddy et al. 2020b). Recently, petter-performing algorithms
and system architecturos for distributed ML (including FL) under SH include Karimireddy et al. (2020b):
Li et al. 2018); Wang al. 20200; Fallah et. al. (2020); Vahidian et al. 2021
Besides SH, another form of heterogeneity is feature heterogene- ity (FH). Traditionally, we say the samples are FH if we can partition them into subsets that bear distinct features. In the FL setting, when the sample subsets of different clients have different, but not necessarily distinct, features, we call FH. That is, under FH, different clients have unique and possibly also common features. FH and SH arise in ML tasks such as col- laborative medical diagnosis (Ng et al. 2021), rocommendation systems (Yang et al. 2020), and graph learning (Zhang et al. 2021), where the data collected by different clients have differ- ent and possibly overlapping features and sample IDs. Next,
MRI
Alicc
Patiens
Ultasound
Clinic A
Clinic A
Bob
Hob
MRI
Charlic
Clinic
Clinic B
Charle
Figure 1: The heterogeneous data distribution in a medical diaguosis example.
we provide a few examples.
Medical diagnosis application (see Figure D The clients are clinics, and they collect data samples from patients. Each clinic may have diffeernnt 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 A may partially ouerlap with that done by clinic B. Besides FH, SH also arises as multiple clinies may not have the chance of treating the same patient and each patient usually visits only a subset of clinics.
Recommendation systems (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 a subset of common products and a subset of common customers.
A third example pertains to application of learning over multiple social networks (Zhang et al. 2021 Guo & Waan 2020 Here the clients are social network providers (e.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 of 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), we 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 et al. 2020b Dinh et al. 2021 The clients perform multiple local model updates, and the server averages those updates and broadcasts 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 2b for an illustration); otherwise, the server cannot average their models.
Consider the Vertical FL (VFL) algorithms (Luu 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
2

---

Published in Transactions on Machine Learning Research (04/2024)
Data used by HIFL
Features
Client
Totaa Sampoh
Data from Client
Data used by VFL
Client
from Clicat
(a) Heterogeneous data on clients
(b) HFL data usage
(c) VFL data usage
Figure 2: The data distribution palterns of a) heterogeneous client data; b) HFL and c) VFL.
to compute training losses and gradients. They require all the clients to have the same set of samples (see Figure 2 otherwise, they cannot compute the loss and its gradient.
According to Yang al. 2019: : Rahman et al. 2021); ; the FL setting with heterogeneous features and samples is 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 or labels during training. In VFL, the labels either made available by the clients to the server (Chen et al. 2020 or stored in a designated client LLiu et al. 2019). A hybrid FL system may be subject to "no sharing" requirement, it is desirable to develop a method in which the server has no access to any data, including the labels.
3. Sample synchronization. A technical challenge with VFL is that the the same mini-batch of samples at each iteration. This challenge is exacerbated in hybrid FL since not all the clients will have the same samples. Therefore, to avoid idling clients, hybrid FL method should allow uncoordinated sample draws.
wants the clients draw
Our contributions: Towards addressing the previous challenges, this work proposes novel model and its training method. We summarize our contribution as follows.
1. We propose a new hybrid FL approach. For each client, the model consists a feature extractor and subsequent classifier. The clients collaborate and share their knowledge through building a model at the server that assimilates local classifiers and features. 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 algorithm maintains data locality, 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 a number of real datasets. The learned model achieved an accuracy that was comparable to that of centrally trained model.
1.1 Related work
Federated graph learning (FGL) is applied to molecular classification (He et al. 2021) relation or node classification for social networks Zhang et al. 2021 Ng et al. 2021) and financial network (Suzumura et al. 2019). In the first application, the graphs are relatively small and the clients have largely many graphs (Zhang et al. 2021 He et al. (222)). In the last application scenarios, the clients possess partial yet overlapping data of single large graph, including partial node and edge information (Zhang et al. 2021 However,
3

---

Published in Transactions on Machine Learning Research (04/2024)
existing FGL algorithms mainly focus the first application scenario (He et al. 2021 and fail to deal with the latter two scenarios. So we cannot apply them to our hybrid FL. setting.
HFL has a popular algorithm FedAvg (Konečný et al., 2016), which adopts the computation-then- aggregation strategy. The clients locally perform a few steps of model updates, and then the server ag- gregates the updated local models and averages them before sending the updated global model back to the clients. Beyond model averaging, PFNM (Yurochkin al., 2019) and FedMA (Wang et al.) 2020) use a seaannttrr-mtchinng based strategy and FedGKT (He et al. 2020) uses knowledge 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 fcatures.
Personalized FL (PFL) has been studied as a potential way to lackle different levels of lask heterogeneity. MAML (Jiang et al. 2019 Fallah et al. 2020 uses meta-learning to build a global model that can fast adapt to heterogencous data distribution; FedProx (Li et al.) 2018) and LG-FodAvg (Hanzely & Richtárik 2020)
regularize the distance between the local models and the global model. MOCHA (Smith al. 2017)
and FedU (Dinh et al. 2021 combine multi-task learning with FL to train models for personalized tasks. FedPer (Arivazhagan al. 2019 separates the model into base-+personallee 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.
Vertical Federated Learning. In VFL, the features and thus the models are divided over different clients (Hrdy et al., 2017 Ma al., 2019 Liu et al., 2019 Chen et al.) 2020). VFL has fewer results than HFT. Federated Block Coordinate Descent. (FedBCD) (Liu et al.) 2019) uses a parallel BCD-like algorithm to optimize the local blocks and transmits essential information for the other clients to compute their local gradients. Vertical Asynchronous Federated Learning (VAFL) (Chen et al. 2020 assumes that the server holds the global inference model while local clients train the feature extractors that deal with the local features. VFL algorithms ignore the overlapping features and can only make joint inferences, which requires full client participation.
Federated Contrastive Learning (FedCL). FedCL another set of algorithms related to Hybrid FL. In this setting, the clients hold non-overlapping features and partially overlapping samples and aim to learn separate models for local inference (Kang et al., 2022 He et al. 2022) The algorithms perform vertical FL on the overlapping samples to train a global guidance model and perform local contrastive learning (self- supervised learning) with the non-overlapped local data to train local models. Compared with our setting, the FedCL algorithm requires overlapping samples and transmitting intermediate features as VFL and fails to make use of overlapping feature spaces and non-overlapping samples during VFL training.
2 Problem Formulation
In this section, we first provide a mathematical characterization of the heterogeneous data distributions of interest to this work. We then propose unified hybrid FL model.
Due to the nature of hybrid FL, we must carefully set up its notation. We denote the all one (column) vector of length d as la; the identity matrix of size d as Ta; the positive integer set 21, N} as [NV. Feature selection below uses a selector matrix of dimension dj x d2, which belongs to the following set: Data description: See Figure 3a| for an illustration of datasel with three clients, where the client datasets has no fully overlapped sample or feature, so neither HFL nor VFL can be used. We consider a hybrid FL system with M clients indexed by E [M], and they collaborate to accomplish the same task. For convenience, we index the server as = 0.
Notation:
First, assume that each sample can have at most do feature blocks, and the ith block has the set Dj of features, E [do]: client m has a set of dm feature blocks indexed by I,m that is, we write (Dim) and write the feature space of client m as Xm = -IIm D.,,, which a Cartesian product of the subset of the
feature blocks possessed by client m. Similarly, we denote the "full feature" space Xo - De, which is the Cartesian product of all feature blocks.
4

---

Published in Transactions on Machine Learning Research (04/2024)
Client
Client 2:
Client 3:
Server
Y
D3
(Pear))
N2
X11
(Peat)
Fo(Wai))
Ni
Xun
(Paar)
Data
Feature extractors
Classifier
No
22
Client
Yv
(Paaat)
N3-
X3N--1
Xax--
(Wai)
Xmn
(Prcat)
X, Dg) X1 = [2,. [Dg. X3 = [D,, 2g]
Data
Feature extractors
Classifier
(a) Data partition pattern and notations.
(b) Block structure of client and server models
Figure 3: The partitioned data and notations, and the structure the client and server models with heterogeneous feature extractors and classifiers.
Second, client m holds a private dataset with index set Nm and the samples (Im,n Un) for n E Wim, where Tm.n Xm denotes the features of the th sample on client m, and yn denotes the label of the nh sample. Collecting all the clients' data together, we can define the (virtual) global dataset have sample index set No [N], with samples (zo,n. 3n) where Jo,n E Ng denotes the "full feature" of the nh sample (for the precise relation between the full-featured Jo,n and the local sample Im,ns please the property P2 below).
The dalaset defined above satisfies the following properties.
P1) The global index set is the union of the clients' index sets:
No U Nm. which implics Nn No.
P2) For a given client m, the features of the th sample is a sub-vector the "full features". That is, there exists selector matrix Pm such that can map the global feature F0,, to Em,ni
Im,n Pm Do for some Pm E S(dms do),
(1)
where Pm is 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 a special case of what has been described above, where the clients have fully overlapping features, i.e., do 1, Pm = 1, Vm E [M]; Similarly, the data structure for VFL can be viewed as a special case that the clients have fully overlapping sample indices, i.c., N No, Vm [M].
Model design: With the above description of data, and the corresponding optimization problem.
ready to present the proposed hybrid FL model
Client and server model design: Similar to VFL, we split the ML model into feature extractors and classifiers. Each feature extractor takes a feature block as input and extracts an intermediate feature as output; the classifier takes the concatenated intermediate features multiple feature extractors as input and outputs the prediction.
As illustrated by Figure 3b on client m, the feature extractor h;.. (0m.i. for input feature block D.., is parameterized by 8m, for all im Im- The feature extractors can have different neural network archi- tectures (e.g., CNN for CT/MRI images, SSTM/Transformer for medical records, and 1-D CNN for ECG data). We denote the concatenated feature extractors and their parameters as:
Hm. (0mi))
(0m.t.m :.mm and Om := 1 10m,tu11mmEm
(2)
The classifier Fn (wmi is parameterized by Wn, and we denote the prediction loss function as ((.-)) The data processing procedure client m is described follows:
5

---

Published in Transactions on Machine Learning Research (04/2024)
(1)
The features Zm.n of the n²th sample are passed to the feature extractors {him (0m.sm : Mm
(2) The classifier Fm (Wmi+) makes the prediction based on the concatenated output of the feature extractors
Hm (mmi Em,n);
(3) The prediction Fm (wm: Hm (Qmi mm,)) and the true label yn together evaluates the loss ((:)).
With the specified data processing procedure, the prediction loss on client is defined as:
fmmmm Wm)
1
Σ mEN.
[(Fm Hm (m am,)))
(3)
[Wmll
Additionally, the server will have model with full feature extractors, concatenated with classifier; see the top figure in Fig. 3b This model structure covers wide range of ML models for classification and regression problems, e-g., image classification, language processing, and recommendation systems.
Remark 2. (Local and server models). A few remarks are 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 a complete model, capable of performing local inference without communication to the server. Second, it is important to have a separate server model, because: 1) in case a 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 fcatures, it can dircctly 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 data to train high-quality server/clin /client models? Unlike HFL, where all clients share the same model, the clients in this problem have local models (i.c., feature extractors and classifiers) of different sizes to deal with feature hetcrogencity. Thercfore, one cannot directly perform the conventional model averaging.
Model matching: 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.
First, is natural to assume that when client m and m' share the same feature block Di, the corresponding feature extractors hz(0m,5:-) should produce the same output, that is 6 = 6,,s ss 6 Therefore, we impose the following regularizer for the feature extractors, which matches the fth feature extractor at user m with the corresponding extractor the server:
(0m, θo) = Σ
1 -'1mm. 60,il1 2 110, Pm 0oll
(4)
T
where Pm is the data selection matrix defined in
1 and Om 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 wma some "pruned" versions of the server-side classifier wo, but with unknown pruning pattern. More specifically, assume that wm e Rdm.,, Rdo.. we impose the following regularizer for the classifier:
1 |mmm - 1I woll, s.t. Im E S(dm, do,w), 2
Tm.2 (w0 1m: Wo)
(5)
where Im is a selection matrix defining the unknown pruning pattern. It is important to note that, the pruning pattern matrices Im '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 I 's and the regularizer Tm are given in Appendix A.1

---

Published in Transactions on Machine Learning Research (04/2024)
Overall problem formulation: By combining the models discussed in the previous two subsections, we arrive at the following training problem:
Σ Pm (fmm (m,, Wm) pr Im.. Qo) + ( Tm, wo)),
min 3.5 (1 M
{8 MWn. Mer.
(6)
S.L.
Im S(dm,w; do,d), Vm é [M],
where P1, M2 are hyper-parae asper-parameters for the regularizers; Pm 's are the weights for each local problem satisfying Em Pm 1, with common choices Pm 37 Pm Win
WT
Remark 3. (Relation with HFL). When do = 1, that is, there is only a 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 model 6 and some popular HFL models. First note that when dg 1, the feature extractor regularizer reduces to 1m 2) ||@m -boll.
1) Reduction to FedMA (Wang et al., 2020) and Sub-FedAvg (Vahidian et al., 2021). If set On T, i..., the features directly processed by the Wm ss, then equivalent to the problem solved by FedMA and Sub-FedAvg.
2) Reduction to FedProx (Li et al., 2018) and LG-FedAvg (Hanzely & Richtárik, 2020). By setting Wm = I. M and letting On directly predict the labels, the problem reduces to
M Σ (mm)) + (0m, On)), m
min of
(7)
(0m
M
which is equivalent to the formulation solved by FedProx and LG-FedAvg.
3) Reduction to FedAvg. Further by letting μr + oo in 7 the regularizer enforces Om's 's to achieve exact consensus, the problem reduces to the one solved by FedAvg.
4) Reduction to FedPer (Arivazhagan et al., 2019). By letting #2 = and μn + oo in 66 the regularizer on Wm 's is removed and @m 's achieve exact consensus. In this case, Om serves as the base layers while wnn't 's the personalized layers, equivalent to the model design of FedPer.
Remark 4. (Relation with VFL). VFL assumes that the clients cannot perform prediction independently, it directly trains global model with the local data (Liu et 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 to construct a global model. This way, we avoid data sharing and sample synchronization issues that often limit VFL use in practice.
3 Algorithm Design
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 G into server-side problem and client-side problem, and then develop algorithms to optimize each part. One key consideration in 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 (0 {wo, M Oo we and
[mm)- First we divide the parameters into two groups: 1) the server-side parameters Og, Wo: and
[m MM and 2) the client-side parameters (0m }M and
By fixing the server-side parameters, 66) dccomposcs into m independent problems, one for cach client. The problem related to client m given by:
min fm (m, Wm) + in I'm ( θo) + #2 (m,2(Wm Im Wo). Wi
(8)
7

---

Published in Transactions on Machine Learning Research (04/2024)
Algorithm Hybrid Federated Matching Algorithm (HyFEM)
Input: wg: G. (T }M Jm=1, 7; T.Q.
2: for t= . 2 do
for client m I...., M in parallel 4: Ome w <- CliietUUpaate Oh, Ii. wp. Q.
// Local perturbed SGD solving S
Send client model O w.. to server
for server do
7: 0 (===1 Pm P Pm)
Em== Pm O
//Exact minimization for 10)
"o [II++)M Jm=1 MoooMM
(ww 2 II,, h P) // Solving 11
Distribute server model o ++1 0 (Ii [ " clients
Jm=1
10:
Output: (wm, )m) [
Similarly, by fixing the client-side parameters, the fm 's in to the following server-side problem:
become constants, and the problem reduces
min Bo, [ml mn mom1 m=
Epn Pm (UI Fm,11 (0m, Qu) + P2 Fm.2((mm Im Wo))
(9)
s.t.
I E (imm,e do,w); Vm [M].
The above problem can be naturally separated into two sub-problems. The first sub-problem
M
min
Pm Tm, (fm: Ou),
(10)
90
m==
and the second one is:
M
min
Σ
Pm Tm,2(Um, Mm, Wo), s.t. Im E S(dmmw do,w), Vm [M].
(11)
wo. (11m
Algorithm design: We propose a block coordinate descent type algorithm called Hybrid Federated Matched Averaging (HyFEM) in Algorithm I to solve 66) with the above problem splitting strategy and the sub- routines are given by Algorithm perturbed SGD steps on problem the server aggregates the updated client models, updates global feature extractors by optimizing (10 that
Appendix A..2 In global iteration the clients first perform Q local
to optimize client models w O (lines
in Algorithm 2 then
has closed-form solution as line 7 in Algorithm 1 and match the classifiers by optimizing [11 finally the server distributes the models and the selection matrices to clients.
The major step in the algorithm is solving the sub-problem 11]. We optimize it by the ModelMatching
procedure described on lines 14 of Algorithml 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 Hungarian algorithm to solve a parameter assignment problem and obtain 1 in most ((dmm,)))) run-time complexity KKuhn (1555
With few rounds of updates, we obtain the server classifier and the selection matrices for each client.
This procedure is inspired by the model matching algorithms Wang et al. (2020); Yurochkin et. al. (2019)
for matching parameters in deep neural networks of the same size. Our matching algorithm is a non-triveg trivial extension to the existing model matching algorithm. Because the server-side and client-side modols do not
share the exact same functionality, we cannot replace the client-side models with the server-side model. Such special property introduces some significant challenges for model matching. The detailed matching procedure is included in Appendix A.2
Although Algorithm seems to be complicated, it can be viewed problem with three y is the collection of (IIm JMM and parameter blocks f(x,y, y, 2). where is the collection of (wm, O JM ) z is {wo, Oo}. Then the update can be viewed as follows:
Remark 5.
x V y
arg min C(xt 2,,,, z arg minC(x .ttxxty+z))) yeRange(y)
(12)
Q times
8

---

Published in Transactions on Machine Learning Research (04/2024)
where Vxf(-) denotes the stochastic partial gradient estimation w.I.t. X.
Theorem (Informal) Suppose that for each m E [M], fm has Lipschitz continuous gradients w.r.f. (Om: Wm) and that we has a fixed dimension. Then with slepsize 11 == (1/VQQT) and client update Q (T),, by running Algorithm [ the expected gradient norm square w.r.t. {Om, Wm/m= converges with rate O(1/T)
and the successive updale difference |1+b+ - will* + ||/+1 0/l converges with rale (1))T). Alternalively, if we assume the solution to {1lm } for sub- bub-problem [L] is unique, and we update client models with one- step gradient descent, then Algorithm
asymptotically converges to the first-order stationary point of 66
Remark 6. Theorem is 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 a fixed number of stochastic gradient updates on (potentially nonconvex) blocks (Om, W/m JM=,, which results in non-strictly decrease; 2) the problem w.r.t. block {Ilm is nonconvex and non-smooth and does not have a unique global minimum. 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 et al., 2019 Chen 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 (9g, 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 prun- ing/ hssmmatching from HFL, optimizing (5) is st,ill a non-trivial procedure. Specifically, we can only train clients' classifiers Wm 's of different sizes, and construct unknown server's classifier we with wm 's and find Immss ss while existing algorithms either require Wp to be given (Vahidian et al. 2021 or Wm 's to have the
same size (Wang et al. 2020 Yurochkin et al., 2019
4 Numerical Experiments
To evaluate the proposed algorithms, we have conducted experiments on a 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 cannot be applicd to our setting where the client features are only partially overlapped, we do not compare HyFEM with other FL algorithms in this section. However, we include an additional set of experiments in Appendix CealliixCCCoomnn comparing HyFEM and FedProx with less heterogeneous features.
Dataset & data splitting: We consider the ModelNet400, Cifar-10, and EuroSAT datasets, the details of which are explained below. We also consider an additional multi-modal dataset, we refer the readers to Appendix C.3 for details.
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 samples from 40 classes. Cifar-10 (Krizhevsky) 2009): Cifar-10 is an image classification dataset with W' = 50, 000 samples from 10 classes. We manually split each image into (top left,top right, left,bottom right) x (red,green,,leu blue) blocks, resulting in total dg = 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, that the clients have partially overlapping features and samples and exhibit FH and SH. The scttings 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 1 uses dg 4 views and setting uses full d, = 12 views. The first setting has lewer features, the classifiers are smaller and the matching procedure is easier and expected
9

---

Published in Transactions on Machine Learning Research (04/2024)
Table 2: Experiment settings for each dataset. do, dm denote the # of feature blocks; No. denote the # of samples; M denotes the number of clients.
Dataset
do
Classes
No
Client M
dm
Classos/cliene
Nn
ModeINet4401
40
40k
3
20
20k
ModeINet40:22
12
40
40k
15
15k
Cifar-10
12
10
50k
6-8
5
25k
EuroSAT
12
10
27k
6-8
5
13.5k
to be more accurate. Thus the performance of the server model should be closer to the model obtained with centralized training. In the second setting, 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
In the testing phase, the clients evaluate their model on all testing samples with corresponding feature blocks used in the 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 on all testing samples with full features.
Training settings: In the experiments, use the MLP model with hidden layer the classifier Fm (m(wwi)). We use the CNN part of ResNet-18 followed by one pooling layer the feature extractors for the Cifar-10 and EuroSAT datasets; 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 a comparison: Centralized training: we train a full-sized server model with all data. This setting serves as the perfor- mance upper bound among all trained models. Stand-alone training: each client trains client model only with local data and without any communication. This setting serves the baseline (and the perfor- mance lower bound) of HyFEM. In all settings, fix the total number of updates (i.e., T Q 4096, with T = 128, Q 32) for fair comparison and tune the learning rate to achieve the optimal performance for cach experiment separately.
The global accuracy is shown in Figure ! under different settings. We can see 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 train- ing, even if none of the clients has full features or fulll classes of the data. HyFEM can deal with data with SH and FH. As expected, in sctting ModcNNet4::2, the server model accuracy is lower than in sctting ModeINet40: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:
Tos Agcunvyy
Tool Acsuray
ccntmllieed
cenntalized
sland-akoe
02
scontallzodd
Sund alone
stand-alone
ecentralized isstand-tlooe
HyFEM server
HyFEM server
-IlFEM server
HyFEM server
Communication (T)
Communteation
26
128
Communiication (T)
128
32
"ommuniccatoon (b) 128
(a) ModeINet40: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) M0d,1Net10:1, b) 10:2, c) Cifar-10, and d) EuroSAT datasets.
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 400e is higher than 40021Net40:2, each client has more samples. However, the accuracy im- provement with HyFEM under setting ModeINet40:1 is less than setting ModelNet40:2,, the latter one uses more features. Nevertheless, HyFEM can train much better client models than stand-alone training even if the clients do not share the same input space and classes. By using the global model matching algorithm, the local classifiers can share knowledge with other clients on unseen classes and deal with SH.
10

---

Published in Transactions on Machine Learning Research (04/2024)
Test Accurcy
20.6
Aceunay
0.4
centrallzzd
ecnntralized
ceniralized instand-alon
"ostuns-alone
-HFEM client
HyFEM client
-yFEM elient
HyFEM client
Communication.C (T)
us
138
"Commmiiiation 25
Communication (T)
35 Comminiication (h)
(a) ModeINeet4:11
(b) 40:2
(c) Cifar-10
(d) EuroSAT
Figure 5: Averaged test accuracy (with standard deviation) of all clients trained with HyFEM compared with centralized training and stand-alone training for a) ModeINet40:1, b) M0delNet10:22, c) Cifar-10, and d) EuroSAT datasets.
5 Conclusions
We propose a hybrid FL framework that handles general collaborative-leariigg scenario with partially overlapped features and samples. We first clarify how the data are partitioned in the hybrid FT. scenario and propose a generic problem formulation. Next, we show that the proposed formulation covers many horizontal and personalized FL settings, and develop BCD-based algorithm, HyFEM, solve the proposed problem. Finally, our numerical results on number of image classification datasets demonstrate that HyFEM enables clients with partial features and samples to achieve performance comparable to centralized training with full features.
References
Manoj Ghuhan Arivazhagan, Vinay Aggarwal, Aaditya Kumar Singh, and Sunav Choudhary. Federated learning with personalization layers. arXiv preprint arXio: 1912.0081, 2019.
Nan Bai, Pirouz Nourian, Renqian Luo, and Ana Percira Roders. Heri-graphs: A workflow of creating datasets for multi-modal machine learning on graphs of heritage values and attributes with social media, 2022. URL http:////arxiv.or/abbb//////////
Keith Bonawitz, Hubert Eichner, Wolfgang Gricskamp, 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 rrXiv:192.01044 2019.
Tianyi Chen, Xiao Jin, Yuejiao Sun, and Wotao Yin. VAFL: method of vertical asynchronous federated learning. FL-ICML 200 also Xiv preprint ar (rXxi:2007.0008 2020.
Canh T Dinh, Tung T Vu, Nguyen H Tran, Minh N Dao, and Hongyu Zhang, Fedu: A unified framework for federated multi-task learning with laplacian regularization. arXiv preprint arXim:2102.07148 2021.
Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar. Personalized federated learning: A meta-learning approach. arXio preprint orXiv:2002.079/5 2020.
Zhiwei Guo and Heng Wang. A deep graph neural network- based mechanism for social recommendations. IEFE Transactions on Industrial Informatics, 17(4):2776 774)22776-2788, 2020.
Filip Hanzely and Peter Richtárik. Federated learning of a mixture of global and local models. arXiv preprint arXiv:2002.0557 2020.
Stephen Hardy, Wilko Henecka, Hamish Ivey-Law, Richard Nock, Giorgio Patrini, Guillaume Smith, and Brian Thorne. Private federated learning on vertically partitioned data via entity resolution and additively homomorphic encryption. arXiv preprint xxXiv:1711.106777, 2017.
Chaoyang He, Murali Annavaram, and Salman Avestimehr. Group knowledge transfer: Federated learning of large cons at the edge. Aduances in Neural Information. Processing Systems, 18:14008-14080 2020.
11

---

Published in Transactions on Machine Learning Research (04/2024)
Chaoyang He, Keshav Balasubramanian, Emir Ceyani, Carl Yang, Han Xie, Lichao Sun, Lifang He, Liangwei Yang, Philip S Yu, Yu Rong, et al. Fedgraphmn: A federated learning system and benchmark for graph neural networks. arxic preprint arXiv:2104.07145 2021.
Yuanqin He, Yan Kang, Xinyuan Zhao, Jiahuan Luo, Lixin Fan, Yuxing Han, and Qiang Yang. hybrid self-supervised learning framework for vertical federated learning. arXiv preprint aix::22008. 08934, 2022.
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 personaliza- tion via model agnostic meta learning. arXiv preprint urXiv:1999 190,..1999,88 2019.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurôlien Bellet, Mchdi 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 Learning. 14(1-2):1-211) 2021.
Yan Kang, Yang Liu, and Xinle Liang. Fedevt: Semi-supervised vertical lederated learning with cross-view training. ACM Transactions on Intelligent Systems and Technology (TIST), 13(4): 16, 2022.
Sai Praneeth Karimireddy, Martin Jaggi, Satyen Kale, Mchryar Mohri, Sashank Reddi, Sebastian U Stich, and Ananda Theertha Suresh. Mime: Mimicking centralized stochastic algorithms in federated learning. arXiv preprinl ar Xix:20008.00 036066 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 heterogencous data. Xiu preprint 1xXiv:1999.00 04715, 2019.
Jakub Koncčný, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXio preprinl arXiv:1610.0544 2016.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Master's 's thesis, University of Tront, 2009.
Harold W Kuhn. The hungarian method for the assignment problem. Noval 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 18t2:181.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 1912: 111877 2019.
Jing Ma, Qiuchen Zhang, Jian Lou, Joyce C Ho, Li Xiong, and Xiaoqian Jiang. Privacy-presevingg ten- sor factorization for collaborative health data analysis. In Proceedings of the 28th ACM International Conference on Information and Knowledge Management, pp. 1291-1300, 2019.
Dianwen Ng, Xiang Lan, Melissa Min-Szu Yao, Wing P Chan, and Mengling Feng. Federated learning: collaborative effort to achieve better medical imaging models for individual sites that have small labelled datascts. 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. IEFE Access, 9:1 1446622-124700,
124700, 2021.
12

---

Published in Transactions on Machine Learning Research (04/2024)
Meisam Razaviyayn, Mingyi Hong, and Zhi- thi-Quan Luo. A unified convergence analysis of block successive minimization methods for nonsmooth optimization. SIAM Journal on Oplimization, (3 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-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. Xiv preprint arXiv:1909. 12946, 2019.
Saeed Vahidian, Mahdi Morafah, and Bill Lin. Personalized federated learning by structured and unstruc- tured 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 Representations (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 computer vision and pattern recognition, pp. 1912-1920, 2015.
Liu Yang, Ben Tan, Vincent W Zheng, Kai Chen, and Qiang Yang. Federated recommendation systems. 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 International Conference on Machine Learning, pp. 7252-7261. 2019.
Justin Zhan, Chia-Lung Hsich, I-Cheng Wang, Tsan-Sheng Hsu, Churn-Jung Liau, and Da- Wei Wang. Privacy-preserving collaborative recommender systems. IEFF Transactions Systems, Man, and Cyber- netics, Port C (Applications and Reviews), 40(4):472 476, 2010.
Huanding Zhang, Tao Shen, Fei Wu, Mingyang Yin, Hongxia Yang, and Chao Wu. Federated graph learning- position paper. XiXiv preprint arXto:2005.10009 2021.
13

---

Published in Transactions on Machine Learning Research (04/2024)
A Heterogeneous Model Matching Algorithm
In this section, we describe the details of the model-matching algorithm. First, we describe the motivation behind the design of the classifiers' regularizer 5 which encourages Wm to be matched together to construct
wi designed. Then we present the detailed version line 8-14 14 in Algorithm 2 for optimizing the regulariver
11
A.1 Regularizer Design
Recall the regularizer for the classifiers is given by:
2 Im, Wo) = 2 1m wol? s.t. I1m E S(dm, da,w),
where dm,w: do,w are the dimensions of Wm: and Im is selection matrix corresponding to the unknown pruning pattern. In this section, we explain why such a regularizer is used, and how the selection matrices IIm's 's are constructed.
We note that the proposed matching method is a non-trivial extension of the neural matching method (Yurochkin et al. 2019) (designed for horizontal FL) to the case of hybrid FL. In Yurochkin et al. (2019) the author considered the horizontal FL setting where the sizes and the functionalities of all the clients' models as well as the server'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 server-side and client-side models do not share the same functionaality. Therefore we cannot replace the client-side models with the server-side model. Such a special property of the hybrid FL problem introduces some significant challenges for the matching procedure. This is the main reason that our proposed algorithm, the matching matrices and the client/serve /server models have to be iteratively optimized.
Suppose that for each client m, its classifier fm Fm(wm))) :) has L layers; then the inference block has the following structure:
(13) where (.)(+)) represents the element-win wise nonlinear activation function of layer 1; 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.c., Vm = Hm (O.(()))) z). Then Wmm = fum/llii see Figure 6 for an illustration. Let us further define the server's output of feature extractors, activation functions and weights as vo {fo.((--.))} similarly as above.
y = IL (Wm,1 Om
I 1V)) vm)...)),
Note that giving a selection matrix with appropriate shape 11 E S, left multiply the weight matrix Wm, by IIT (II" (m,)) results in selecting the rows of Wm,ss which is equivalent to selecting the output neurons of the ph layer. And right multiply the weight matrix Wm.1 by TI (Wm,ll) results in selecting the columns of Wm,t: which is equivalent to selecting the input neurons of the 8th layer.
The goal is to match W's''s with the corresponding parameters Wo, at the server. Below, we discuss how the first layer, the middle layers, and the last layer are matched.
First, recall that the input of the classifiers has the following relation:
H (0:: Fm) = P., (oo mo), thatis, v.. = Pm Vo:
where Pm is the selection matrix defined by the feature overlapping pattern between 2m and Zg. Then, let us multiply pf on both sides of the above equation, we obtain m
Pm Vo = pf vm
(14)
Note that PT vm pads zeros in the missing feature indices of the Vms so that matches the size of Vo. Let define II nm P... By utilizing the fact. that P.,. S(dm; do) is a selection matrix, it holds Pn, PT then we have the following relation:
Ta...
0m,1 ((Wm, 1m, (TT m. vm)) am, Im, v-)-
14

---

Published in Transactions on Machine Learning Research (04/2024)
This process expands the imput Vn to the same size as Vo, while keeping the output of the first layer unchanged; see Fig. for an illustration of this process.
Next, we would like to find a selection matrix 1mm E 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:
0m,1 ((wm, 1
x llm.2 0o,1 (w), vo).
(15)
This output-matching relation imposes the following assumption on the model parameters:
mm,1 Wo
(16)
To why
16
implies
15
we can plug 16 into the left hand side of 16 and obtain:
m, ((wm,1 m,, 1) (TT vm))
m,, (mm,,2W, II. HI m ( Vm))
@
lmm 0
(o.1((u))) ((Wo, 11 mm, (4 Vm))
Im u. (WW II m., 1) [m,,
(17)
11 T0,1 (Wo, II I 1Vo)
1l 0 (vo,
where (i) comes from the fact that projection only changes the order and pads zeros to the output, so applying element-wise activation before after the projection does not affect the final output; in (ii) we use the fact that 11. 1 is diagonal matrix with I's and 0's on diagonal that can be approximated by identity 1
matrix. The above discussion suggests that, if (16) holds approximately, then (15) holds approximately. As a result, we design the regularizer on the first layer between client m and the server, by approximately enforcing (16] as
1
2 Wm,1 - II 2m m.
Let now analyze the constraint for 1m.2- First, since the dimension of w0,1 1 is larger equal to that of Wm,1 for each client m, we require that each coordinate of Wm,1 is matched to one coordinate in W0,11 Therefore we need 2,, to satisfy = 21, Further, each coordinate in wo,1 should match to coordinate in at least one clients m [M]'s Wm,1, so this mcans ΣM 1' 2 1. The above process is illustrated in Fig.
For the 9th middle layer, its input is the output of the previous layer. By fixing the projection matrices {Imm) I that match the output of the (1-1)tt layer at cach client to the output of the (1- 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 0m) corresponds to the input vnz the projection matrices (1lm, M m=j correspond to the input projection matrices {Ilm,1)MM1 the goal is to find the projection matrices [Im,i+1)M J.M that match the output of the hhh 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 tth middle layer between client m and the server as
1 2
[mm 1m wp,
For the last layer, the output at each client is the same the server, which is the predicted label. Therefore, the projection matrix of the output for the last layer is an identity matrix, and we design the regularizer for the last layer as
- wo I.".
Next, by vectorizing Wm,i's i's we have following relation:
vec(T Wo, IT (Tm,t Im (voowwoo)))..)
15

---

Published in Transactions on Machine Learning Research (04/2024)
Algorithm 2 Sub-routines for Algorithm
ClientUpdatee ,, mI w6: Q,17)
Initialize: 0 + P.. G. w + II, wb
3: for g- -= 0,.... Q do
Uniformly sample Nm 5: 0n +- On
(Ve., [(Fm (wnn (O'' m), No. + pi P. 01) 6: wm + wmn - (V (V... E(Fm (w H. (m 2m..) Br.)) + N2(w"n" 11'm w()
7: Output: 0 who
ModelMatching( ? IT Im w6, P) 9: for p= O..... P- do
10:
for =,..., MM in parallel
11:
u + (Em Pm (TT,
Empmm Pm (TT,)) um (
TT + arg minnin mnd F 2 Thm' w.))) ) 11 Using Hungarian algorithm
12:
11 < (Em=l Pm (TT,h
(Em=) Pm (TT, )T m0 I + IT
13: 1/
14:
Output: wo 1+1 - ] Im=1
where @ denotes the Kronecker product. Therefore the regularizer for each layer can be rewritten as
zz [|vec(mm.) - (Imm & (ee
Finally we can stack the sub-vector (vec(wm.))Ea into wms and define the projection matrix of the long vector as
Ilm diag((Umm,) @ 1lm,2),.... ..., (Ll,, I)).
Again, II is a block diagonal matrix, and it is easy to verify that it satisfies the following conditions:
M
I = 1, Σ II 2 1: 2 O.
(18)
m==
Finally, obtain the final formulation of the regularizer
Tm.2 Tm.2(Wm IIm wo) = [m -Imm wol?? V m [M]
M
(19)
where 11 's satisfy: 11m E S(dw. dw
Σ
1
demm
11 2 1
m=1
A.2 Optimization Procedure
In this subsection, we describe the detailed procedures in line 8 - 14 of Algorithm 2 to optimize the classifier
matching problem or its more detailed formulation 19 The procedure with more details is given in Algorithm 8
We iteratively solve the matching problem 11 for P iterations. In each iteration, randomly pick client m' to 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 Cj that computes the cost to match jth row in client m' to tth row in the server of layer for all (i,j). The element Ci(i.) of the cost matrix is defined as:
dist -T (i)) dists(wm, (il)
Io +
C((ig)
(20)
otherwise,
where II 1 [i] and Wm. denote the 4th and jth row of the matrices, dist, is the similarity cost for matching Wm [ to existing row, and distg is the dimension penalty to match wm,[)] to new in
16

---

Published in Transactions on Machine Learning Research (04/2024)
Algorithm 3 Model Matching Procedure
ModelMatching
2: Input: {w/e 11 LM
mm wor P
for p p= p=00.... 0,..., , P-11 do
4: Uniformly sample m' E [M]
5: Wo" + Empm/ Pm ( 11:)))
Em ( w
for ,,..,, do
7:
Construct cost matrix Ct with 20
I <- arg minn, Eeg mm (i.7) Ci(t.)).
1/ Using Hungarian algorithm
w+t < (2m=) Pm Pm. (IIT
(Eme Pm (II,, (w I II
10:
Output: wo 1+ (11 (11++11..
W0, One specification of the cost functions is PFNM (Yurochkin al. 2019) that uses the MAP loss of the Peta-Bernoulli process, where dist, is based on the Gaussian prior and disty follows the Indian Buffet process prior. Then we can solve the assignment problem to obtain T with the celebrated Hungarian algorithm (Kuhn 1955).
Note that for the first layer, the matching pattern Im 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 of Algorithm We first make the following assumptions the problem:
A (Block Lipschitz Gradient) For each parameter blocks in {ums 9m 3mmm= there ewists an Lm such that the following holds:
Ve.., Jm (m, Wm) Sm w'mil + V wm S' (0m; Wm) Jny (6'm ma w/m)l
Tom (1 O'mll ||wmn w/ml)), Om, O'n Wmn; wmm
A 2 (Lower Bounded Loss) There exist finite lower bounds for each client classification loss, i.e.,
fm -00 s.t. fm ( wm) Jm WOm Wmy! M.
A 3 (Bounded Variance) The stochastic partial gradient estimation has bownded variance og and o i.e.,
En Ve (Wmi Hm (9m mi 2 mm.n)) (), yn) Venfm 0m) - og, θm, Wms V m E [M]. E2 V um ((Fm(Wmi Hm O m m) yn) V WwmffmWue 2m) s o2, V O Wms V m [M].
We can abstract HyFEM to BCD-type algorithm by redefining the model parameters and the problem follows:
1. Define x= [O:;...; Om; wi:... :w)), y = [vec([T]); vec([T and (0o; wn).
2.
Define L(x.y.z) = EM Pm (fm wm) + (0 θp) + #2 ( Im Wa))
Then the optimization problem 6 can be simplified as:
min L(x, 2), s.t. y Rangely). x.y.
(21)
17

---

Published in Transactions on Machine Learning Research (04/2024)
Moreover, the algorithm can be simplified as:
x-1- = =x 1 x ,y 22), forg = 0,...,Q--1
(22a)
y y = arg min L(x yz,"),
(22b)
yERange(y)
x 1-| arg ming y +1 2),
(22c)
where we assume x x x = x and Vx((-) denotes the stochastic partial gradient of
We make the following assumptions to problem 21
A (Block Lipschitz Gradient) L is block smooth, and for parameter x and z, there exists positive conslants Lxx Lu and Cx such that the following holds:
[x Cx' y. 2) S Lx xx x x, x,, 2, vy E Rango(y).
Vx((x, VxC(x,y, 2 2')l S Cx z'|l z, x, Vy E Range(y).
A 5 (Block Strong Convexity of 2) For parameler z, there crists posilive constand, p. such that the following holds:
L(x,y,2)) ((x, + (V) 2) + _ N,, vy Rangely)-
A 6 (Unbiased Stochastic Partial Gradient) The stochastic partial gradient of is unbiased:
EVx((x,y,z) Vxl(x.y,2), x,2, E Rangely).
A 7 (Bounded Variance of Stochastic Partial Gradient) The stochastic partial gradient of has bounded variance o²:
E Vx[(x,y,z Vx[(x,y,z)|| S / = Vy e Range(y).
A 8 (Lower Bounded Function) The problem C is bounded from below, i.e.,
3 > s.t. f(x, 2 C. 2x,2, Vy E Rangely).
A 9 (Compact Constraint Set) For parameter y, the constraint set Rangely) is compact.
Note that in A4 and A5 we only assume blocks x, z are smooth, and only block is strongly convex while block y can be non-smooth and non-convex and x can potentially be non-convex. Further we assume that VxC is smooth w.r.t. z, which non-standard, but we can prove that it holds for problem (6). The remaining assumptions A6 are common when analyzing stochastic algorithms. Further, we can verify that the above assumptions hold for the original problem
Lemma 1 Suppose 6 sulisfies assumplions
then salisfies 4 with the constants in the as-
sumptions given as:
Lx max m Lm + max maxfp111221, Cx max (1, 123
# 2 min(pm) minfur, o² ==oz 03 _² L Σ Pmfm
The proof is given in Scction B.2
Then have the following result:
18

---

Published in Transactions on Machine Learning Research (04/2024)
Theorem Suppose the problem
21
satisfies
4449 and run 22 for T iterations with stepsize n
min Ix 50g
8y
}.
Then the sequence
y 2 i= generated by 12
salisfies:
1 TQ
E
M 1 22 2/11²= //| Vxx(x**+ y 11
V C (x ,",
9=
(23)
10
(L(x), ,y,²²) L)) + 5lxm + 21
-
0²
TQn
and V ,.,.z"221 2²111² = 0, V
This result indicates that by setting Q= 2((((x" x -
the right-hand-side (RHS) of
23
LxQTo2
becomes 100 22(((2(xx)x))) x0))) - + 2Lx y0 -xx = =(+)). Let us analyze the left-hand-side (LHS) terms
T
73
of 23 First, we have
T 1
z 2²12²
E 12
- z' z¹112 = ( -
TQ
t=0 1
1=0
indicating that E 12 - z²1 0 (7) Second, we have
T-1
Vx[(xt+] y 20)|| + Σ V ,y" 222)1 = (+) -
TQ
9=0
where the LHS the sum of T(Q + 2) terms of [| divide by TQ, which also indicates that E [x 2²) = O Together have that algorithm (2 finds stationary solution of 21
w.r.t. x,2 with rate O (2)- Combining Theorem 2 with Lemma 1 have that by running Algorithm parameters (wms O. MM
m= converges to their stationary point of while {IIm }M stays in compact set.
Alternatively, if we assume the solution to is unique, and update on x is one-step gradient descent, i.e.,
Q and
x
x' xxx'' xx 2²)
then by applying (Razaviyayn et al. 2013 order stationary point of (6).
Theorem 2), Algorithm asymptotically converges to the first-
B.1 Proof for Theorem
We begin by proving the following descent result:
Q "
E [(x , x(11) [(x', "(x',"',z) <
Σ
E ""
z0)l
4=0
(24)
211 + Qlx110022
1 ||
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 as below:
[(x'+1, 1 y 2111) - _(x",'',"" x²,z") = (C(x++), ,y (2 [(x"t1 . ,()),2())
+ (C(xtt), ,y -(xtt),, ,y',""
(25)
soxttl,y",0 L(x', y" ,²,z
We bound the three terms the RHS of the above equation separately.
19

---

Published in Transactions on Machine Learning Research (04/2024)
1) The first term (E(x't), yl ,2/111=+++++) - [(xtt), ,ytt), can be bounded by applying A
C(x , z L(x y zz)
V Cz (x (x++1 , xz=1), x' - -2-11 - 1 || - z¹11
(26)
2
(a)
1 || - -2'1?
where in (a) uses update rule 22c that by exact minimization Vx Vx[(x(+1.)) xxt)) O. 2) By the update rule (2bb) the second term (C(x+t), 1 y z²) - [(x(t1, , y²,z²) z²)) can be bound by
[(x't1 y sxltlyy/tl... 2²) [(x't1 yy,z²) z') So.
(27)
3) The third term (I(x!t1,y) - f(x', ,²,z can be further decompose into:
C(xtt1, y', - [(x", ,y, 2 = L(x ,², - [(xtx0,, ,y', x²) (C(x ,y' ((x y", z2))
(28)
where the first incquality uses the definition that x x and x x". Then bound each term in the summation as:
x)), x x² + Lx | - xt01
[(x y", 2²) C(xt.9.9 y z²) V Xx((xx ,"),,,)))))))))"r)))
2
(29)
22n
(Vx((x s.,..,. y 2²), A Cxx y x²)) + L
| . y x²1²
2
Taking expectation (1,4), we have:
E -(x 2²) - L(xto,,',
LX12
5 n ( Vx y 2²), Big V Vx y 2²)) +
E | C(elx x'
2
(0) 7 V Cx 11
V Cxx 4. 2²)²
2
(30)
Tx
+ 2
V L(x yt, z²) V -xxxx y z')1
1xe1
Tx2
V>[(('" 2²) +
17 2
2
where (a) first applics the fact that E(X?) = (E x)² E((X- E(X))?) to the second therm, then applics AG to the first and the second term
1 By picking n - i. and substituting 30
28
have:
Q-1 E'
V ,",,)) + Qlxni''²
ES 1(x 20) - [(x
(31)
2
Then we substitute
26
17
and
31
back to
25
then we obtain 24
20

---

Published in Transactions on Machine Learning Research (04/2024)
To prove Theorem 2 need to further bound Vxx(x++1 yy, ,²,22))] 2')l and [Vx((x++) ,yth1 21) We bound
them follows. Term
Vx[(x++) .y', 2') can be bound as:
| xxx 1+1 2 )| - V , 2')l|²
B-Q-1
+ E Q-
V xx 2 y' 2') Vxl(x+0- , )
21 2
1 9 11 2 V x(x(x . 21)
(32)
22n
2 E
11 C(x 1-1 y' )² +2 Vx[(x* ( R-1 y 21)
-0
2 21
VxL(x , )² + 2
where in (a) add and subtract VxL(x10-1 y", 2²) and apply Cauchy- Schhwrr incquality. Similarly, term Vx[(x(+] ,tt1 z²)|( 1| can be bound as:
V xxx(xx+1.y" , 2²) (0)
S v Vx tttt z²) - Vx , , 1|12
2 V L( ++ ytt2 2 21?
20 2 (+ x 21? + 2 2 yetz I|
(33)
where in (a) we add and subtract Vx((x(+1 y y(+1 1 and apply Cauchy Schwarz inequality.
Then we sum the above results as 24
x 2+ 32
33 x Y and obtain the following:
2 [(x ++ y 1 - 2L(x' y
E
Q
V [(x ,,,22))1
5
Q-1
+ 7 VxL(x*t))
3 -11
E
V Lx y", x²) 112 - 11 11|z - 11
5
4=0
(34)
+ QLu77022 +
202'
-2/1==+ + ||
2 Vx[(x*+1 1+1 , yttl, 212
5
5
2n 23
.y 2 || + 2T 2T2
V
+ 5
Rearrange the terms, notice that we choose 1, S I,
1, that 2n + 21227² I 4n, we have:
2C31 (M-2Cz2) 1|=01-
Et V (x 2')1/+ + E || Vxx((x+1__ yet //411/0+1) 2/1 2 + 1 (n-
8=0
(35)
12
s 2 2c(x' 25) - E ((x ytt 2( +
+ Q1x o².
5
202n 2 (1) S 5cg ), and devide both side by nº
Sum the above equation from t to T 1, choose μ
then Theorem is proved.
B.2 Proof for Lemma 1
In this section, we verify the assumptions
A for the original problem G under assumptions A
21

---

Published in Transactions on Machine Learning Research (04/2024)
Recall that we have the following correspondence:
x : :o:.... M: wi wi:...;;vi] y = [vee([));...,vv((II]]) z = ==
veo([lar)],
M
((), = Σ
Pm (m Wm) + #r Tm,.1 (Qm: Ou) + f2 Tm.2 Im wo)),
m=1
1
(mm: 40)
2 110m -omolll
M (10 m: wo) 110m - mol?, s.1. Im E S(d dw,u),
Σ m=1
12,
I1m 2 dw.a
1) For A4 have
Pm Ve., Sm (m Wm) (m/ Pm 0g) M
VxL(x,y,2)
Pm V wm fm (0 (mms m. Wm) Pmn/u (wm 1I wo) mml
Therefore we have the following bound:
VxL((x, VxL(x',
M
Σ
Pm Ve fm 1m (0m, wm) + p16m Vm w/n) - p 1'
M
+
Pm | Vwn (mm: Wm) + 1220m Wum fm (i'm w'm) u2w'mll
m=1
M
<
Pm
Wm) V fm w/nil + u1 l|0m - O'm
m=1
M
+
Σ
Pm (Il wm fm wm) V Vam Wwm (8', m w/ m/))l + 22 1m w/n
m=1
Pm ((Lm + M1) -10m O'm (Lm u2) -l1mm w'mll)
M Σ m=1
I max (pm Lm + m
(I|@m - O'ull ll + +|/mm - -w'nnll w'mll)
Lx xx - x'1l
where we obtain Lx = maxm {pmbm + max(Mi, #2)). Also, we have
A5 [VL((x, VxL(x,y, Σ
Pm (m || (On - 663l + 4/2 [Tm (wo - w/)il II)
m==1
M
Pm (M1 |m ||0, - -6ll + p2 [[ 11w0 - w/ll)
m=l
Pm (Ny |10p
06ll + μ2 Ww w6ll)
(6)
max (1) u2) (I(O, - 0/1 + llwo - w6ll)
Cx || z'll.
where in (a) we use the fact that Pm E S(dm, do), 11m E S(du.m,, dw.o) are selection matrices so that P 1, | || (b) uses the fact that ΣM Pm 1. Therefore A4 is verified.
22

---

Published in Transactions on Machine Learning Research (04/2024)
2) Next, verify A5
We proceed by directly computing the second derivitive of
Cx,,
M
Vool1 : Tm,1 + P2 1m, Veo WolM ' Tm,1 + 12 Tm,2
Ve. V wo mm,1 + P2 Fm,2
Pm
V we P1 mm.1 + P2 Tm,
m=1
PT Pm U1 Em= Pmm m
12 Em Pm II 11
Then we analyze the range of the cigenvalues of this matrix. First we know that Im Pm 's are selection matricies, therefore pd P m. 11 II diagonal matricies, indicating that V2 is also a diagonal matrix.
For the first block μ1 Em P Pm, m. we have that Pm 's are the feature selection matrix, i.c.,
do
Fm = Pm 2m E Xmm
II
20 E X = I1 D DI,
SEIm
i=1
It clear that if client m has the 5th feature, then the 7th diagonal entry of pf Pm is P. Pm, and P (i,, 0 otherwise. That is, the following holds:
1 E Im.
Pm
0, $ Im-
Further, we have that the full feature space X, is the union of the clients' feature spaces, i.e., UmE(an) In [do]. Therefore, we have
M
M
PT Pm 2 12,-
and min iE(do)
PT Pm m Pm (i, 2 min(pm)
do
m=1
m=l
Similarly, the constraint on 11m that EME 1s dwmm
11 2 1 dwoo
indicates that the following holds:
M
Pm II Im (1, 2 min min 6E dEldm.o
m==1
Therefore, the Hessien matrix Vz is positive definite, with smallest eigenvalue μ 2 min (pm) min min, P2). Thus A5 is verified.
3) A6 holds true as in Algorithm
we uniformly samples n E Nm for all m E [M], therefore
En V Ve.. ((Fmm Hm (9mi Im. Im. m)) vn) = V fm (0m, Wm), En V Vwn ((Fm (Wm; Hm (0mi Im,n) yr)) = V wm fm ( my Wm);
Further, from A3
we can obtain A7 with o² = oz + o
4) To verify S we apply that:
M
C(x.y, z) =
Σ
Pm (fm(0m Wm) + T'm1 (0, Qo) + p2 Tm, II Wo))
m=1
M
M Pm L.
Penf mm (0m, Wm)
m=1
m=1
23

---

Published in Transactions on Machine Learning Research (04/2024)
Client index m
Assigned features Im
Assigned class #
1,2,3
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% of data has never been used.
Client index m
Assigned features Im
Assigned classes
1,2,3
1-5
1,2,3
6 6-10
1,3,4
1-5
4
1,3,4
6-10
5
1,3
1-5
6
1,3
6-10
Table 4: The data assignment pattern for Cifar- 10 and EuroSAT dataset.
where (a) uses the fact that (m. Oo)
||0m Qul2
2 0 and ( Im We)
1 [mm- -m woll 0.
5) Ag directly comes from the constraint Imm is that
I1m E Sidw. dw,o),
Σ
17 12 I1m 2 1
which is compact set.
At this point, we have verified A4 for problem are summarized below:
G with Algorithm and the corresponding constants
Lx = max PPm + max(f1, Cx = max(
22 min min(ur, o² = 0²6 - L= Σ Pmfm-
This completes the proof for Lemmal
C Additional Numerical Experiments
In this section, we include additional sets of numerical experiments. In the first set of additional experiments, reduce the feature helerogeneity of the data on the clients by allowing clients to have common features so that HFL algorithms such as FedProx and FedAvg apply. Further, we include an additional multi-modal dataset with both image and text features.
C.1 Comparison with HFL
In this section, we conduct numerical experiments to compare FedProx [Li ct al. 2018 with HyFEM. In the experiments, we split the features into do = 4 blocks for the datasets and assign the first and the third blocks as the common blocks for all M clients. Then we can apply FedProx to train a 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 described in Table B Note that in the MultiView40 dataset, there 6.88% of the data has never been used by HyFFM and 50% of the data has never been
24

---

Published in Transactions on Machine Learning Research (04/2024)
used by FedProx. For Cifar-10 and EuroSAT datasets, all data has been used by at 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 = feature blocks. For the MultiView40 dataset, we choose four views different angles of the objects as the full feature space. The total communication round is 7 64 and local update # Q = 32 are fixed for all experiments. We conducted line search on the learning rate n and p2 for the algorithms to obtain the best performance.
The results for the datasets are shown in Figure and Figure 10 From the results, we can see that the models trained with HyFEM can obtain better performance than FedProx. This is because HyFEM can use more data than FedProx by using helerogeneous models.
C.2 Data Partitioning Pattern
In this subsection, we provide the data partitioning patterns for each setting, Note that in Figure 11 b). and Figure a), the black boxes with inside them indicate that the corresponding feature block of the samples in this class has not been used for training by any of the clients.
C.3 Experiments on HeriGraph Dataset
HeriGraph (ai et al. 2022) dataset is a multi-modal dataset for heritage site classification. This dataset
consists of total No = 41, 621 samples from classes. Each sample has at most dn preprocessed feature blocks, including one text feature block and three different image feature blocks. Note that not all samples have all fcatures. For example, only 325 samples have text features, and the do not. We will include the result for this dalaset in the revised manuscript.
In the experiments, use the MLP model with hidden layer the classifier fm (wmi We use MLPs of different sizes feature extractors for each feature block. We set client number M = 6, client feature block number dm = 2, and each client. has 6 out of 9 classes.
The server model trained with HyFEM has comparable performance as the centralized trained model. The average performance of the clients' models has worse performance than the full model due the lack of full features and classes, but the accuracy is 20% higher than the models obtained with stand-alone training.
The result is shown in Figure 13
C.4 Ablation Study on Reqularizer Weight
In this subsection, we provide extra numerical results on different choices of the regularizer weight P2- In the experiment, we trained the model on the MultiView40 dalaset under setting MultiView40:22 In the experiment, choose #2 {0.1, 0.3, 0.5) to control the strength of the impact of model matching and the divergence between the local and global model. The results are shown in Figure ?? From the result, we can see that with larger #2, i.e., when regularizing the client and the matched server model to be more similar, both the server-side and the client-side models achieve better performance.
25

---

Published in Transactions on Machine Learning Research (04/2024)
W
W2
W1,3
W2,3
W1,2
W2,2
W1.1
W2,
V1
D2
1,1
1
2.
0,
Figure 6: Illustration of the layer structure of the inference blocks the clients, for the L case.
W1,1
W1,1 IT!"
17
e 1.1
1,33
θ
11,2
W2,1
W2,1 7
17-
11 17
02.2
02.3
02.2
02.3
2,1
Figure 7: Aligning the input the first layer by rearranging and padding the corresponding coordinates of the input Vn and the first layer Wm.1.
Wo,1
11
117
W1,1 !
W2,1 I?
Figure 8: Aligning the output of the first layer by rearranging and padding the corresponding coordinates of the first layer Wm.1-
26

---

Published in Transactions on Machine Learning Research (04/2024)
08
06
Accuracy
Test Aguumicy
Test Accurscy
0.4
0.4
.. Siand-alons
Stand-alone
Stand-alone
Centmlized
02
Centralived
Centralized
HyFEM
HyFEM- Serverr
SyFEM-Sennee
Ferveg-Server
FedAvg-Serrer
SedAvgSenne
24
52
80
48
56
16
24
32
40
48
56
16
24
32
00
48
56 64
(a) ModelNet40
(b) Cifar-10
(c) EuroSAT
Figure 9: Test accuracy of server models trained with HyFEM compared with FedProx on a) ModelNet40, b) Cifar- 10, and c) EuroSAT.
0.
0.6
Tost Agtumny
Test Accurncy
8.6
0.4
0.4
Stand-alone
Stand-alone
Stand-alooe
HyFEM-Client
02
HyFEM-Cliaat
FedAvg-Clisst -lienn
FedAvg--liie Client
FedAvg Client
Centralized
Centralized
16
Communccttin
24
10
18
56
8
16
Communscation
20
32
40
48
56
16
Commimention
39
48 56
61
(a) ModelNet400
(b) Cifar-10
EuroSAT
Figure 10: Averaged test accuracy of client models trained with HyFEM compared with FedProx on a) ModelNet40. b) Cifar-10, and c) EuroSAT.
27

---

Published in Transactions on Machine Learning Research (04/2024)
2
2
2
2
2
2
2
2
2
2
2
2
3
2
2
2
2
2
2
2
2
2
2
1
1
2
(a)
MedelNet40::
2
2
2
3
0
3
2
0
0
2
2
2
2
2
3
2
2
3
2
2
4
2
2
2
2
2
I
I
O
2
2
2
2
0
2
2
3
2
6
2
2
2
1
O
2
2
2
2
0
2
8
O
O
2
2
2
2
2
3
2
2
2
2
2
0
2
10
2
2
0
3
0
3
0
3
0
2
0
12
0
0
3
O
3
0
2
(b)
ModelNet444 40:2222
3
2
3
2
3
3
3
3
3
2
2
4
4
3
2
1
2
4
2
3
3
1
3
4
3
2
6
2
3
3
2
3
2
3
3
1
3
3
2
3
3
3
3
3
4
3
3
3
2
10
2
2
2
2
1
3
4
3
4
2
11
3
3
2
12
2
2
2
2
4
2
2
3
5
8
10
(c) Cifar-10 & EuroSAT
Figure 11: 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) ModelNet100:1 with do = 4 features, M = clients, and 40 classes; 40:e with du features, M 8 clients, and 40 classes; c) Cifar-10 & EuroSAT with features, M = 9 clients, and 10 classes. The r-axis of each plot is the class axis and y-axis is the feature axis.
28

---

Published in Transactions on Machine Learning Research (04/2024)
3
3
5
4
4
4
2
2
4
6
4
5
4
5
4
5
3
2
0
2
1
2
2
2
0
2
2
0
2
2
2
0
3
3
3
4
4
4
5
2
4
6
4
5
4
5
4
5
2
2
2
(a)
ModelNet10
3
3
2
10
(b) Cifar-10 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 Appendix C.I. with a) ModelNet40 with da 4 features, A 6 clients, and 40 classes; c) Cifar-10 10 & EuroSAT with do = features, M 6 clients, and 10 classes. The x-axis of each plot is the class axis and y-axis is the feature axis.
Figure 12:
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
0
0
32
64 96 Communication (T)
128
0
32
96 Communication (T)
64
128
(a) Server
(b) Client
Test accuracy of a) server model, b) client models trained with HyFEM compared with Centralized training and stand-alone training for HeriGraph dataset.
Figure 13:
29

---

Published in Transactions on Machine Learning Research (04/2024)
0.9
0.8
Test Accuracy
Test Accuracy
0.8
0.6
0.7
0.4
Centralized
Centralized
HyFEM server
0.6
HyFEM client #s
HyFEMM server 0.1
HyFEM client 0.1
HyPEM server A4g 0.5
Hyf FEM client 0.5
0.2
0.5
0
20 Communicttion (T)
10
30
0
20 Communication (T)
10
30
(a) Server
Figure 14: Test accuracy of a) server model, b) client models trained with HyFEM compared with Centralized training on ModeINet40:2 under different p2-
30


Reviews:
[{"review_id": "nwngDsvdfI", "reviewer": "Reviewer_r63e", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength\n1.\tThis paper provides proof of convergence.\n2.\tThe description of the algorithm is very detailed and easy to follow.\n3.\tThis algorithm makes appropriate improvements to the model matching algorithm.\n\nWeakness\n1.\tAlthough hybrid FL is relatively less studied compared to other FL topics, there are still related works. The authors should discuss and compare the proposed algorithm with prior works.\n2.\tThe complexity of the Hungarian algorithm in the model matching algorithm is cubic, which may become a significant overhead. The authors should discuss the efficiency of this method.\n3.\tThe update process for the regularizer does not incorporate weighting for statistical heterogeneity, which could result in poor performance when dealing with statistically heterogeneous data.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a framework for hybrid Federated Learning where the data from each party share different sample spaces and feature spaces simultaneously. The server model and each user's local model are divided into feature extractors and classifiers. In each global iteration, each user first performs some perturbed SGD steps to optimize the client model, and then the server aggregates all the client models to update the feature extractors and classifiers separately. The update method is inspired by model matching algorithms.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See the weaknesses.", "broader_impact_concerns": "N/A.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "A6vtf1ve8p", "reviewer": "Reviewer_yZ9H", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros,\n\n1. The exploration of hybrid federated learning (FL) by the authors addresses a novel and significant area that has not been extensively studied. The algorithm proposed is both innovative and demonstrates encouraging outcomes.\n\n2. Additionally, the theoretical convergence of the algorithm has been analyzed, albeit with the reliance on some assumptions that may not be practical.\n\nCons.\n\n1. A basic approach for hybrid FL could involve adapting existing FL algorithms like FedAVG or FedProx by imputing missing features with zeros. The manuscript would benefit from a discussion on these methods.\n\n2. The paper could be enhanced by a more thorough examination of the model-matching algorithm. Given that this process involves solving optimization problems, its computational complexity could become significant with an increase in the number of feature blocks. An analysis of the implications of simply averaging the models in this context would be valuable.\n\n3. The experimental setup presented in the paper is somewhat restricted. While the problem is introduced with a medical diagnosis scenario involving multi-modal data, the experiments are limited to image classification tasks. A broader range of settings for $d_0$ and $d_m$ would provide a more comprehensive evaluation of the algorithm’s performance, which may vary depending on $d_0$, $d_m$, and the ratio $d_0/d_m$. \n\n4. The explanation of how the proposed algorithm simplifies to FedAvg under certain conditions, specifically when $\\mu_1$ is very large, is not sufficiently clear. Clarifying how the client update mechanism in Equation 8 diverges from that of FedAvg under these circumstances would be beneficial.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This study explores a unique aspect of federated learning known as hybrid federated learning (FL), characterized by each client possessing a different subset of features and data samples. Unlike conventional FL scenarios, the hybrid FL framework introduces d_0 feature blocks, with each client holding a portion of these blocks, making model aggregation particularly challenging due to the variance in features and data across clients. The paper introduces an innovative algorithm for hybrid FL, which assigns a distinct feature extractor to each feature block and integrates their outputs through a classifier. To amalgamate client-specific models, the global model encompasses all feature extractors alongside a unified classifier, which is refined using regularization techniques to minimize discrepancies with individual client models. Experimental results presented by the authors demonstrate the superiority of their algorithm over models that are trained locally.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Some changes, especially on the experiment part, will not only strengthen the paper's contribution to the field of federated learning but also provide a clearer, more comprehensive understanding of the proposed algorithm's novelty, effectiveness, and applicability in various settings.\n\n1. Comparison with Basic Approaches: The manuscript should include a discussion on how the proposed hybrid federated learning (FL) algorithm compares to more straightforward approaches, such as adapting FedAVG or FedProx for hybrid FL by imputing missing features with zeros. This comparison is crucial for understanding the necessity and advantage of the proposed method over these naive solutions.\n\n2. Detailed Analysis of Model-Matching Algorithm: It is essential to provide a more in-depth analysis of the model-matching algorithm, especially considering its potential computational complexity when dealing with a large number of feature blocks. \n\n3. Expansion of Experimental Settings: To better validate the applicability and robustness of the proposed algorithm, the experimental section needs significant expansion. For instance, incorporating a wider range of $d_0$ and $d_m$ settings in the experiments to comprehensively assess the algorithm's performance across different configurations.", "broader_impact_concerns": "No ethical concern", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "qZpWQbrRAr", "reviewer": "Reviewer_w1tn", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n- novel approach to a relevant problem\n- sound method that is well-analyzed theoretically\n- promising empirical results\n\n**Weaknesses:**\n- empirical evaluation is limited\n- approach is somewhat straight-forward", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes an approach to a hybrid federated learning setting that combines horizontal and vertical federated learning: clients observe a subset of data points and features. Clients train feature extractors for each possible subset of features in the federation and a classifier on the concatenation of features produced by all locally applicable feature extractors. For collaboration, the server extracts server-side feature extractors and a classifier, local clients regularize their local feature extractors and classifiers to be similar to the server one. \n\nThe paper provides a theoretical convergence analysis and an empirical evaluation and it shows how the proposed approach reduces to established algorithms in their respective settings (e.g., only horizontal or vertical FL).", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "**The following changes are small, but critical in my view:**\n- A more thorough discussion of related work seems appropriate. In particular, a discussion of VFL methods and their applicability to this setting, and split learning seems appropriate.\n- The definition of feature heterogeneity as clients observing various subsets is a bit ambiguous, since the term is also sometimes used for feature shift, i.e., clients observing the same features but the distribution of features being different. It would be great to briefly discuss this difference. One could even argue that the proposed approach is compatible with existing work on feature shift (e.g., FedBN [1]), which further strengthens its significance.\n- The empirical evaluation shows promising results, but lacks a significance and ablation study. I suggest adding experiments on the impact of the communication period, and the regularization parameters $\\mu_1, \\mu_2$. As an ablation study, I suggest investigating only training the classifier collaboratively, e.g., by setting $\\mu_1=0$. \n- In Fig. 5, please add the variance of client accuracies, or the individual client accuracies.\n\n\n**The following changes would strengthen this work:**\n- In its current formulation, the approach uses feature extractors for all feature subsets observed by clients. One could imagine that it is advantageous to go a step further: one could construct a feature extractor for every possible subset of features, i.e., the power set without the empty set. While this might be not applicable to image data, it certainly could work for tabular data. A comparison of the current approach to this rather extreme version would be very interesting.\n- The amount of clients used is rather small ($M=6$). Since the paper motivates their approach with a medical scenario, I think this is a realistic choice. However, it would be great to see how well the approach scales to larger numbers of clients.\n- In semi-supervised federated learning it is quite common to use different local models at each client. While this setting is different from the hybrid FL setting considered in this paper, I suggest adding a very brief discussion about the potential applicability of semi-supervised FL methods to this setting under the assumption that public (unlabeled) data exists, for example using distributed distillation [2] or federated co-training [3].\n- Out of curiousity: would this approach be applicable to kernel methods, as well? Here, one would typically exchange support vectors and their corresponding coefficients (cf. [4]), so \"model matching\" would probably translate to \"support vector matching\". It would be interesting to discuss this, as well.\n \n\n[1] Li, Xiaoxiao, et al. \"FedBN: Federated Learning on Non-IID Features via Local Batch Normalization.\" International Conference on Learning Representations. 2021.\n[2] Bistritz, Ilai, Ariana Mann, and Nicholas Bambos. \"Distributed distillation for on-device learning.\" Advances in Neural Information Processing Systems 33 (2020): 22593-22604.\n[3] Abourayya, Amr, et al. \"Protecting Sensitive Data through Federated Co-Training.\" arXiv preprint arXiv:2310.05696 (2023).\n[4] Kamp, Michael, et al. \"Communication-efficient distributed online learning with kernels.\" Machine Learning and Knowledge Discovery in Databases. Springer International Publishing, 2016.", "broader_impact_concerns": "I do not have any concerns on the ethical implications of this work and therefore think a broader impact statement is unnecessary.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Please make sure to upload a final version of the paper (blue coloring of text removed).
Decision: Accept (poster)