VAFL: a Method of Vertical Asynchronous Federated Learning

Tianyi Chen; Xiao Jin; Yuejiao Sun; Wotao Yin

Source-linked AI summary

VAFL: a Method of Vertical Asynchronous Federated Learning

Tianyi Chen, Xiao Jin, Yuejiao Sun, Wotao Yin

arXiv:2007.06081v1Jul 12, 2020cs.LGcs.DCmath.OCstat.ML

TL;DR

Vertical FL must coordinate models built from different clients’ feature sets while addressing privacy, communication, and asynchronous participation. VAFL uses private local embeddings and uncoordinated stochastic updates, with analyses covering convergence and privacy. Experiments on image and healthcare data report performance comparable to centralized models and less time than synchronous FL in MIMIC-III.

Problem
Vertical FL couples clients’ local models through a shared loss, creating privacy and communication challenges that existing asynchronous methods do not fully address, especially for nonsmooth mappings.
Method
VAFL combines per-client compact embedding models with flexible asynchronous, bounded-delay, stochastic-delay, and t-synchronous update protocols.
Results
VAFL establishes convergence results under different update rules and achieves comparable accuracy to centralized models while requiring less time than synchronous FL on MIMIC-III.
Takeaways & Limitations
VAFL supports vertical federated learning with intermittent or uncoordinated client participation while retaining privacy-oriented embeddings and theoretical guarantees.
Takeaways & Limitations
General nonsmooth vertical FL formulations do not satisfy the smoothness assumption directly, so perturbed local embeddings are introduced to enforce smoothness.

Abstract

from arXiv · show

Horizontal Federated learning (FL) handles multi-client data that share the same set of features, and vertical FL trains a better predictor that combine all the features from different clients. This paper targets solving vertical FL in an asynchronous fashion, and develops a simple FL method. The new method allows each client to run stochastic gradient algorithms without coordination with other clients, so it is suitable for intermittent connectivity of clients. This method further uses a new technique of perturbed local embedding to ensure data privacy and improve communication efficiency. Theoretically, we present the convergence rate and privacy level of our method for strongly convex, nonconvex and even nonsmooth objectives separately. Empirically, we apply our method to FL on various image and healthcare datasets. The results compare favorably to centralized and synchronous FL methods.

1. Introduction

Vertical FL addresses settings where clients hold different features for the same subjects, but stronger model dependence creates privacy and communication challenges. VAFL responds with flexible algorithms, convergence and privacy analysis, and empirical validation against centralized and synchronous methods.

Motivation: Vertical FL combines unique feature sets held by different clients for the same subjects to build a joint predictor.This setting appears in e-commerce, finance, and healthcare applications.
Motivation: Unlike horizontal FL’s additive local-model aggregation, vertical FL concatenates local models coupled through the loss function.Updating one client’s local model therefore requires information from other clients’ models.
Research gap: Existing asynchronous optimization methods do not guarantee convergence for nonsmooth losses or privacy of local updates in vertical FL.Prior methods also commonly assume shared-memory access to the entire dataset.
This work: VAFL combines a global model with per-client embedding models that can be linear, nonlinear, or nonsmooth and reduce communicated parameters.The embeddings map raw data to compact features.
This work: VAFL supports intermittent or strategic participation, uncoordinated data selection, and differential-privacy-based data protection.Secure computing protocols may instead be used for specific loss functions.
This work: The paper establishes convergence and privacy guarantees, and experiments report competitive performance versus centralized and synchronous FL on image and medical datasets.The validation covers federated logistic regression and deep learning.

2. Vertical federated learning

VAFL formulates vertical FL around private client-side embeddings and asynchronously updates server and local models without client coordination. It supports bounded, stochastic unbounded, and t-synchronous update rules while handling delayed information and flexible participation.

Problem statement: Each client retains a unique feature block and keeps raw data private from other clients and the server.The server stores the sample labels.
Problem statement: A client embedding maps its high-dimensional feature vector to a lower-dimensional representation parameterized by a local model.The local model may be linear or nonlinear.
Problem statement: The server and clients exchange embeddings and loss gradients with respect to embeddings, rather than raw client data.The embeddings capture each client’s local information for the optimization problem.
Asynchronous client updates: VAFL asynchronously processes client messages by answering embedding-gradient queries and updating the server model when new embeddings arrive.Server gradients use the embeddings currently available from other clients.
Asynchronous client updates: At each interaction, an active client samples a datum, obtains its embedding gradient, uploads an updated embedding securely, and updates its local model.The secure-upload mechanism is described separately in the paper.
Asynchronous client updates: The global counter advances whenever the server and the corresponding client complete their respective updates, without external coordination.The counter indexes the uploading client and sampled datum for each update.
Flexible update rules: The framework supports bounded delay, stochastic unbounded delay, and t-synchronous updates that wait for embeddings from t clients.The server refreshes embeddings when bounded delays exceed D, while t-synchronous updates are reported as empirically more stable.

3. Convergence analysis

VAFL establishes convergence for nonconvex and strongly convex objectives under bounded and stochastic unbounded delays, including settings where clients do not coordinate gradient samples or local updates. The analysis also addresses nonsmooth embeddings through perturbed local embedding and shows a convergence–privacy trade-off.

Convergence results: VAFL analyzes convergence for nonconvex and strongly convex objectives under fully asynchronous and t-synchronous update rules.The t-synchronous convergence results are reported as similar to those for the fully asynchronous algorithm.
Assumptions: The analysis assumes i.i.d. sample indices, bounded gradient variance, lower-bounded optimal loss, Lipschitz gradients, and independent client selection.These are the sampling, smoothness, and asynchronous-update conditions used in the convergence analysis.
Nonsmooth embeddings: Nonsmooth local embeddings can violate the Lipschitz-gradient assumption, while perturbed local embedding is introduced to enforce smoothness.The paper’s general vertical FL formulation permits nonsmooth embedding functions such as neural networks.
Bounded delay: Under uniformly bounded delay, strong convexity improves the convergence rate relative to the nonconvex case.The bounded-delay result uses Assumptions 1–4 and strong convexity of F.
Stochastic unbounded delay: Under stochastic unbounded delay, VAFL obtains convergence rates of the same order as under bounded delay.The stochastic-delay setting allows unbounded-support delays and can arise from independent Poisson client activations.
Asynchrony: Without coordinating clients’ gradient samples or local model updates, VAFL matches the convergence order of block-wise SGD under bounded and stochastic unbounded delays.This comparison is stated for both delay settings.

4. Perturbed local embedding: Enforcing differential privacy and smoothness

VAFL perturbs each client’s local embedding with random neurons, smoothing the embedding while supporting differential privacy. The perturbation strength controls both smoothness and the privacy–convergence trade-off.

Perturbation mechanism: The composite embedding supports linear and nonlinear activations, with the linear case recovered using one identity-activation layer.The embedding layers use weights and biases corresponding to the local model parameters.
Perturbation mechanism: Random neurons are added to each embedding layer, producing a perturbed local embedding through modified layer computations.The perturbations are independent across layers and are chosen so the embedding becomes smooth and differentially private.
Enforcing smoothness: Taking expectation over random neurons smooths the objective and local embedding, enabling convergence analysis for otherwise nonsmooth mappings.The paper connects this effect to randomized smoothing and formally establishes smoothness in Theorem 5.
Enforcing smoothness: Larger perturbations produce a smaller smoothness constant for the perturbed loss.This result is stated for perturbation scales such as c_l or c under bounded weight norms.
Enforcing differential privacy: VAFL’s perturbed embedding satisfies μ-GDP under the theorem’s variance setting for the final-layer Gaussian random neuron.The privacy parameter depends on minibatch size, total batch size, and the number of processed queries.
Enforcing differential privacy: Increasing random-neuron variance improves privacy by decreasing μ but also increases stochastic-gradient variance and slows convergence.Thus, the perturbation variance directly exposes an accuracy–privacy trade-off.

5. Numerical tests and remarks

The experiments evaluate asynchronous and t-synchronous VAFL against synchronous and centralized references across image, object-recognition, and healthcare tasks. On MIMIC-III, both VAFL variants achieve centralized-comparable accuracy with less time than synchronous FL.

Experimental comparisons: VAFL is benchmarked in fully asynchronous and t-synchronous forms against synchronous block-wise SGD, including private variants.The synchronous baseline requires synchronization and sample-index coordination among clients in each iteration.
Image and healthcare benchmarks: Logistic-regression experiments cover MNIST, Fashion-MNIST, CIFAR10, and Parkinson disease, reporting testing accuracy against wall-clock time.Centralized results and private algorithm variants are included in the plots.
Image and healthcare benchmarks: The deep-learning experiment uses a seven-layer CNN as each client’s local embedding for 12-view object data, with a server network aggregating embeddings.Four clients each hold three views per object, and results are plotted in Figure 3.
Image and healthcare benchmarks: On MIMIC-III mortality prediction, asynchronous and t-synchronous VAFL reach accuracies comparable to centralized learning while requiring less time than synchronous FL.Each of four clients uses an LSTM embedding function.

Supplementary materials for “VAFL: a Method of Vertical Asynchronous Federated Learning”

The supplementary document provides supporting lemmas, proofs for the paper’s results, and additional experiment details. Its convergence argument uses a Lyapunov function and suitable step sizes for delayed asynchronous updates.

Supplementary contents: The supplement contains supporting lemmas, proofs of the paper’s lemmas and theorems, and detailed experimental material.Its stated purpose is to document the theoretical and empirical foundations of the paper.
Convergence analysis: A Lyapunov function is introduced to analyze VAFL under delayed information.The function includes constants selected to control delay-related terms.
Proof details: The proof expands expected objective changes and bounds gradient-estimation and update-error terms using the paper’s assumptions.These expectation steps complete the supporting convergence inequality.

B.1. Proof of Lemma 1

The proof of Lemma 1 controls delayed asynchronous updates through a Lyapunov recursion. It selects auxiliary coefficients and step-size restrictions so the resulting expected bound supports convergence.

Lyapunov recursion: The proof decomposes successive-iterate differences and applies prior bounds to the Lyapunov function.Initialization sets earlier iterates equal to the initial point before analyzing the recursion.
Step-size conditions: Step sizes are restricted by smoothness, delay, and client-selection parameters to keep the Lyapunov bound controlled.The proof uses bounds involving L, D, μ, and the client probabilities q_m.
Coefficient selection: The auxiliary coefficients satisfy linear recursions that account for delay-dependent terms.The coefficients are chosen recursively across delay levels, with a terminal condition for the maximum delay.
Convergence bound: The resulting bound combines an initial Lyapunov term with a diminishing error contribution over K iterations.The displayed expressions include factors involving K, K0, and the minimum client-selection probability.
Unbounded delay: For unbounded delay, the proof uses a corresponding delay relation and coefficient recursion indexed over infinitely many delay levels.The same decomposition strategy is extended to client-specific delay terms.

C.1. Proof of Theorem 3

The proof derives convergence for the t-synchronous update by bounding objective changes and taking expectations over client participation and stochastic quantities. It concludes that t-synchronous VAFL has the same convergence-rate order as the asynchronous results.

Update analysis: The analysis defines the uploading-client set M_k and models each client’s update as active only when included in M_k.The update notation distinguishes uploaded clients from inactive clients.
Update analysis: Client participation is assumed independent across iterations, with each client having a specified probability of entering M_k.This is the t-synchronous analogue of the stochastic client-update assumptions.
Proof strategy: The proof bounds the objective value after an update and then takes expectation over both M_k and the sampled client quantities.These steps convert the random client participation and stochastic updates into an expected descent relation.
Conclusion: The resulting t-synchronous VAFL method achieves the same order of convergence rate as Theorems 1–4.The conclusion applies to the corresponding bounded-delay and unbounded-stochastic-delay analyses.

D.2. Convergence results

The paper establishes convergence results for t-synchronous VAFL under bounded and unbounded stochastic delays, covering nonconvex and strongly convex objectives. The nonlinear-embedding analysis uses smoothing through random perturbations to extend the theoretical treatment.

Convergence theorems: Theorem 7 gives a bounded-delay convergence result for the nonconvex t-synchronous setting.The theorem is stated under Assumptions 1, 2, 4, and 6.
Convergence theorems: Theorem 8 gives a bounded-delay convergence result when F is μ-strongly convex in (θ0, θ).It uses the same t-synchronous framework as the preceding bounded-delay theorem.
Convergence theorems: Theorem 9 extends the t-synchronous analysis to nonconvex objectives with unbounded stochastic delay.Its assumptions include the stochastic-delay and client-participation conditions.
Convergence theorems: Theorem 10 provides the corresponding unbounded-stochastic-delay result for strongly convex objectives.The theorem assumes F is μ-strongly convex and uses the assumptions of Theorem 9.
Nonlinear embeddings: Randomly perturbed activation functions become differentiable with Lipschitz-continuous gradients in expectation, supporting smoothness analysis of nonlinear local embeddings.The result uses continuous perturbations and an expectation of the activation gradient.
Scope of analysis: The convergence analysis is presented mainly for fully asynchronous VAFL, while the t-synchronous convergence results are stated to have similar rates.The t-synchronous proofs are described as supplementary to the main presentation.

F. Proof of Theorem 6

This section combines assumptions and experimental setup for evaluating VAFL with nonlinear local embeddings, including perturbations and delayed workers. The setup records loss, accuracy, and wall-clock time across several datasets.

Theoretical setup: The nonlinear local embedding analysis assumes Lipschitz activations and uniformly bounded layer weights.The stated assumptions support the smoothness derivation for perturbed neural embeddings.
Experimental setup: VAFL experiments use CIFAR-10, Parkinson Disease, MNIST, and Fashion MNIST with data uniformly distributed among 3–8 clients.The client counts are 8 for CIFAR-10, 3 for Parkinson Disease, and 7 for MNIST and Fashion MNIST.
Experimental setup: Worker delays follow client-specific Poisson distributions, with an expected maximum delay of one second.The delay parameter depends on the worker index and is scaled by the number of workers.
Privacy setup: Gaussian output perturbations use N(0, 0.01) for CIFAR-10, MNIST, and Fashion MNIST, and N(0, 1) for Parkinson Disease.These task-specific noise distributions define the privacy-oriented perturbation settings.
Evaluation: Training loss is recorded during optimization, while testing accuracy and wall-clock time are recorded at the end of each epoch.The evaluation tracks both predictive performance and runtime.

G.3.1. TRAINING ON MODELNET40 DATASET

The experiments evaluate VAFL with convolutional local embeddings on vertically partitioned ModelNet40 data and LSTM embeddings on MIMIC-III. They compare training and predictive behavior under delayed, perturbed client computation.

ModelNet40: Each ModelNet40 local embedding is a 7-layer convolutional network that produces a 512-dimensional output vector.The server combines local vectors with a fully connected network.
ModelNet40: ModelNet40 images are vertically partitioned across clients by assigning views from 12 object angles to local clients.Each client processes its assigned views locally.
ModelNet40: ModelNet40 uses client-specific exponential delays and layer-dependent perturbations, including uniform noise and N(0, 1) noise in the last convolutional layer.The local embedding uses ReLU activations and adds noise at each local convolutional layer.
ModelNet40: The ModelNet40 server linearly combines 12 local vectors and classifies objects through a three-layer network with 256, 100, and 40 nodes.The final layer corresponds to the 40 object classes.
MIMIC-III: MIMIC-III data are allocated among four workers with different feature dimensions, using a two-layer LSTM local embedding and a fully connected server layer.The LSTM has bidirectional and normal layers, each with 16 units.
MIMIC-III: MIMIC-III experiments add Gaussian noise N(0, 10^-4) to each local embedding output and compare algorithms with private counterparts.The reported comparisons include ModelNet40 and MIMIC-III.