In vertical federated learning, several organizations hold different columns of the same table. A bank and an online retailer, for example, share customers but not features. Each organization trains a private "bottom" network on its own columns. One organization, the label owner, combines the resulting embeddings in a "top" network and sends a gradient back to each partner for every training example. That round trip is the gradient synchronization cost of this setting. Over a wide-area network it dominates training time, because no partner can take a step until its gradients come back.
The standard workaround lets partners take several local steps between round trips while reusing the last gradient they received. That gradient is stale: it was computed at an embedding the partner has since moved away from. We propose correcting it to first order. At each synchronization, the label owner sends one small extra message: a low-rank sketch of how its loss gradient bends as a partner's embedding moves, which is the curvature of the top model in that partner's embedding coordinates. Between synchronizations, the partner extrapolates its stale gradient along its own embedding drift using this sketch. The sketch costs a few vectors per round, not one vector per example. The claim is that this correction lets partners take many more local steps before the stale gradient misleads them, so the cost of reaching a target accuracy falls in both bits and wall-clock time.
Core Claim
Write $g_i^{(s)}$ for the gradient of the loss with respect to partner $k$'s embedding of example $i$, as received at the last synchronization $s$. Write $h_i^{(s)}$ and $h_i^{(t)}$ for that embedding at synchronization and at local step $t$. Partner $k$ uses
$$\hat g_i^{(t)} = g_i^{(s)} + U_k S_k U_k^\top \big(h_i^{(t)} - h_i^{(s)}\big),$$
where $U_k S_k U_k^\top$ is a rank-$r$ sketch of the batch-averaged second derivative of the top-model loss with respect to $h_k$. The label owner computes it at synchronization from $r$ Hessian-vector products against its own top model.
The term this captures is the part of gradient staleness caused by the partner's own movement. It is the part a partner can actually observe, and it has a simple structure. For a linear top model with binary cross-entropy, as in click-through-rate prediction, the per-example curvature is $p_i(1-p_i)W_k^\top W_k$. Here $p_i$ is the predicted click probability and $W_k$ is the slice of top-model weights that reads $h_k$. A low-rank shared sketch is therefore a natural approximation.
The correction cannot see the other parties' drift or changes to the top model. The research program measures how large that uncorrected remainder is, rather than assuming it away.
Relation to Prior Work
Three VFL methods motivate the proposal by showing that local multi-step updates pay off and that staleness is what limits them. FedBCD lets parties take $Q$ local steps on stale partner statistics. It cut communication rounds on MIMIC logistic regression from 334 to 52, but it controls drift only with a proximal penalty in its FedPBCD variant. CELU-VFL caches embeddings and gradients and down-weights cached examples whose current embedding has low cosine similarity to the cached one. It reports 2.65× to 6.27× end-to-end speedups on Criteo, Avazu and a Tencent production dataset, and notes that competing local-update methods failed to converge at eight local updates on Criteo. Flex-VFL lets fast parties take more local steps under a timeout and rescales their learning rates. All three treat a stale gradient as something to trust less: they shrink it, regularize away from it, or rescale it. We instead repair it, using information the label owner already has.
A second group constrains the design. EF-VFL compresses cut-layer messages with error feedback. It keeps over 91% MNIST accuracy at 1% top-$k$, where the earlier compressed VFL baseline collapsed to roughly 35%, but it synchronizes every step. Mask-Encoded Sparsification shows that naively sparsifying split-network activations biases gradients through the nonlinear server model. These results warn that any approximation at the cut layer must be checked for bias, not only for its average error. They are also orthogonal to our method: compression shrinks each message, while our correction reduces how many messages are needed. We test whether the two compose.
VAFL argues that injecting smoothing noise into embeddings is needed for convergence under asynchronous delay with ReLU activations. DecVFAL instead bounds stale-gradient error through an optimal-control analysis. Our correction is deterministic and adds no noise. Whether it is stable without smoothing is an empirical question we answer directly.
The method's lineage is the model-parallel work on predicting gradients. Local Critic Training trains auxiliary networks that estimate intermediate gradients so layer groups can update without waiting. It reaches 93.32% on CIFAR-10 with ResNet-50 against 93.79% for backpropagation, while the free-form synthetic-gradient baseline it compares to stayed below 80%. Its critics need labels, which passive parties in VFL do not have. That below-80% result also suggests free-form learned gradient predictors are fragile. We keep the prediction anchored to a true gradient and learn only a structured first-order correction.
Research Program
We will build the method on a split-network VFL simulator with a configurable bandwidth and latency link between parties, so that wall-clock time reflects the network as well as compute. The protocol has five steps:
- At each synchronization, the label owner returns the usual per-example gradients.
- It also computes a rank-$r$ curvature sketch per partner, using a randomized range finder over $r$ Hessian-vector products on the current batch.
- It sends the sketch as $r$ vectors of embedding dimension plus $r$ scalars.
- Partners then take $Q$ local steps on cached and fresh mini-batches using the corrected gradients $\hat g$.
- Partners optionally keep CELU-VFL's cosine weighting on top of the correction.
The label owner's extra cost is $r$ double-backward passes through the top model, amortized over $Q$ local steps. This is far below the many forward evaluations per step that zeroth-order boundary estimation requires in VFL-CZOFO.
The central diagnostic decomposes staleness error. At every local step we take an oracle measurement of the true gradient, by running an untimed synchronization. We then split the gap between the stale and true gradients into two parts: the part predicted by the partner's own drift through the exact Hessian block, and the remainder from other parties and the top model. This tells us, per dataset and architecture, the best case for any partner-local correction.
Two variants probe privacy and communication. The first is communication-free: partners estimate the sketch themselves from secant pairs, which are pairs of embedding change and gradient change observed when a sampler deliberately repeats some instances across synchronizations. The second is richer: the label owner also sends one scalar per example, the curvature weight $p_i(1-p_i)$. That scalar plausibly leaks prediction confidence and so helps label inference. We will measure that leakage with a standard label-inference attack before recommending the variant. The shared sketch reveals top-model geometry but nothing per example. We report that honestly as a change to the threat model relative to plain gradient exchange.
Baselines
The naive reference point is synchronous VFL with full-precision messages and $Q=1$. Every method's bits-to-target and time-to-target are reported as ratios to it.
The strongest frequency-reduction competitor is CELU-VFL (Towards Communication-efficient Vertical Federated Learning Training via Cache-enabled Local Updates). It reports 2.65× to 6.27× speedup over vanilla VFL and FedBCD on Criteo, Avazu and D3. We found no reported CELU-VFL AUC on Criteo or Avazu on Lacuna, so we will re-run it in our simulator rather than quote absolute accuracies. It will use the same workset size, round-robin sampling and number of local updates per round. We will also give it an equal hyperparameter search budget over learning rate and local-step count. Beating it means reaching CELU-VFL's best test AUC in fewer transmitted bits and less simulated wall-clock time at the same link bandwidth. It also means remaining stable at local-step counts where CELU-VFL degrades.
FedBCD and its proximal variant FedPBCD (A Communication Efficient Vertical Federated Learning Framework) are run with the same tuning budget over $Q$ and the proximal weight. They represent the regularize-don't-correct alternative.
The strongest compression competitor is EF-VFL (Communication-efficient Vertical Federated Learning via Compressed Error Feedback) at $Q=1$, evaluated on equal-bit budgets. Its reported reference is over 91% MNIST test accuracy at 1% top-$k$. We also run the obvious stack, CELU-VFL with EF-VFL-compressed synchronizations, against our correction plus the same compression.
Ablations isolate the key ingredient. Rank $r=0$ reduces our method to plain stale reuse. A random sketch of matched norm rules out a regularization effect. A sketch computed one synchronization late tests the cost of reusing the sketch. We also run the communication-free secant variant and a neural synthetic-gradient predictor trained on received gradients, of the kind Local Critic Training compares against.
Why not just…?
Why not just down-weight stale examples, as CELU-VFL does? Cosine weighting discards information. It tells the optimizer that a gradient is wrong but not in which direction it is wrong, so as $Q$ grows more examples are suppressed and local steps make little progress. CELU-VFL's own observation that competing methods stalled at eight local updates shows staleness is the limiting factor. But CELU-VFL itself is the real threat here. If its weighting already absorbs most of the error, our method will show no gain over the CELU-VFL configuration that includes weighting. The head-to-head sweep over $Q$ and the error decomposition settle this. We expect the advantage to appear only at large $Q$, and we will say so if it does not.
Why not just add a proximal term and keep local updates conservative? FedPBCD's proximal term limits drift by limiting progress. It buys stability at the price of the very local steps that save communication. If the curvature correction is no better than a well-tuned proximal weight, the random-sketch and $r=0$ ablations will show it.
Why not just synchronize every step with heavy error-feedback compression? This is a serious alternative, because EF-VFL matches uncompressed convergence rates at $Q=1$. Its limit is latency rather than bandwidth: every step still waits a full round trip, and on high-latency links the idle time remains however small the message is. We compare on a grid of bandwidth and latency settings and report where each method wins. If compression alone dominates everywhere, our method is unnecessary. We expect a crossover where latency, not bandwidth, is the bottleneck.
Why not just train a neural network at each partner to predict its gradients? Local Critic Training's comparison shows free-form synthetic gradients falling below 80% on CIFAR-10 where anchored critics reach 93.32%. A learned predictor with no true-gradient anchor also accumulates bias of the kind Mask-Encoded Sparsification warns about. We include such a predictor as a baseline, trained on the same received gradients.
Proposed Experiments
Tabular experiments use Criteo and Avazu with features split between two and four parties, following CELU-VFL's setup, with test AUC as the accuracy metric. Deep split-network experiments use MNIST and CIFAR-10 split by image halves or quadrants, following EF-VFL. ModelNet40 split by view provides a setting with strong cross-party interactions. That is where we expect other parties' drift to dominate and the correction to help least.
The decisive check comes first. On each dataset we plot the relative error of the stale gradient, the corrected gradient and the oracle first-order prediction against local step. If the corrected gradient does not cut the stale gradient's error substantially by eight local steps on Criteo, the idea fails and we stop.
If it passes, we report three things:
- Bits-to-target and simulated time-to-target versus $Q$ and $r$, together with the label owner's extra compute.
- Label-inference attack success for the shared-sketch and per-example-scalar variants.
- Whether the correction composes with EF-VFL compression, measured as combined savings at equal final AUC.
References
- A Communication Efficient Vertical Federated Learning Framework
- Towards Communication-efficient Vertical Federated Learning Training via Cache-enabled Local Updates
- Flexible Vertical Federated Learning With Heterogeneous Parties
- Communication-efficient Vertical Federated Learning via Compressed Error Feedback
- Mask-Encoded Sparsification: Mitigating Biased Gradients in Communication-Efficient Split Learning
- VAFL: a Method of Vertical Asynchronous Federated Learning
- Accelerated Vertical Federated Adversarial Learning through Decoupling Layer-Wise Dependencies
- Local Critic Training for Model-Parallel Learning of Deep Neural Networks
- A Unified Solution for Privacy and Communication Efficiency in Vertical Federated Learning