acceptodds
Under review as a conference paper at ICLR 2027

Local Updates Meet Error Feedback: Communication-Efficient Vertical Minimax Federated Learning

Abstract

Vertical federated learning (VFL) couples model blocks held by different clients, making block-coordinate methods a natural approach to optimization. In minimax learning, local updates and compressed exchanges introduce errors that interact with the evolving maximization variables. We develop two local block methods: FedBCD-Max combines approximate server-side maximization with client-local descent, whereas FedBCDA performs client-local descent-ascent when the maximization variables are partitioned across clients. We further equip both methods with bidirectional error feedback to correct uplink and downlink compression errors. We establish the linear convergence guarantee for strongly convex-strongly concave problems, and an convergence rate for nonconvex-strongly concave problems. The analysis jointly controls local trajectories, maximization error, and two coupled compression memories. It characterizes admissible effective step sizes and preserves the uncompressed accuracy dependence with an explicit factor in the leading communication-round bounds, where is the compressor contraction parameter. Experiments on fair vertical classification and vertical adversarial learning illustrate the outperformance of our proposed algorithms, and further show that error feedback mitigates the degradation caused by direct compression.

Primary area:
optimization
Keywords:
vertical federated learning, minimax optimization, block coordinate optimization, communication efficiency, error feedback, compression, adversarial learning, fairness

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_25C5OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies communication-efficient vertical federated minimax optimization with either a server-held maximization variable or client-partitioned maximization variables. It proposes FedBCD-Max, which combines approximate server-side maximization with client-local descent, and FedBCDA, which performs local descent–ascent updates. Both methods are extended with bidirectional EF21-style tracking. Under strongly convex–strongly concave and nonconvex–strongly concave assumptions, the paper establishes finite-time convergence bounds, including an explicit compression-dependent communication-round overhead. Experiments evaluate fair vertical classification and vertical adversarial training, with comparisons between dense communication, direct compression, and error feedback.

Critical strengths

1.The analysis jointly addresses stale-block local updates, maximization error, and coupled uplink/downlink tracking errors. This is a meaningful extension beyond minimization-only VFL and single-update error-feedback analyses.

2.The compression experiments provide controlled comparisons between direct sparsification and error feedback at the same recorded sparse communication budget. The recovery of near-dense performance, particularly on Adult, supports the practical usefulness of the tracking mechanism.

Critical weaknesses

1.The connection between the theoretical algorithms and the private-label VFL implementations remains incomplete. Remark 4 explains that the standard private-label interface directly supports only one exact local update, whereas the multiple-update theory requires reusable messages that support the prescribed local oracle after the client state changes. The experiments instead compress representation-level messages and are explicitly described as not being literal instantiations of Theorem 2. The fairness compression experiment also uses a minibatch-dependent dual response, and the adversarial objective does not establish the strong concavity required by the theory. These acknowledged differences leave the paper without a demonstrated end-to-end protocol that simultaneously realizes the theoretical local-update and compression assumptions.

2.The adversarial-training results do not establish efficiency at comparable robustness. In Table 5, FedBCDA is faster and has higher clean accuracy, but its PGD-10 accuracy is 47.95%, compared with 61.97% for PGD and 52.94% for DecVFAL; the EF variant reaches 45.46%. Hyperparameter selection emphasizes clean validation accuracy, while the reported PGD evaluation uses ten steps and one random initialization without additional restarts. Consequently, the results do not sufficiently separate optimization efficiency from a weaker clean–robust tradeoff.

Questions for authors

1.Clarification: What exact round-level information allows a private-label client to evaluate each local direction after updating its model? Please specify whether these directions are exact stale-block gradients or surrogate directions, and account for any additional transmissions.

2.Clarification: Which assumptions of Theorems 1–2 are satisfied by each implementation? In particular, how are representation-level tracking, minibatch-dependent dual computation, and the adversarial maximization geometry related to the analyzed oracle?

3.Assessment-relevant additional evidence: Does the reported time or communication advantage persist when methods are compared at matched robust accuracy, using stronger multi-step, multi-restart attacks under the same feature-partition threat model?

2 comments

We appreciate the reviewer for the careful reading and pointing out issues on the the connection between the theory and practice, also the details of our experiments.

Q1. What information is exchanged at the beginning of each round that enables a client to compute subsequent local directions after updating its model under the private-label setup? Are these directions exact stale-block gradients or surrogate directions, and how are any additional transmissions accounted for?

Reply: Thank you for this point. Under the standard private-label interface, each exchange supports one exact local step (Remark 4). Further exact steps require a privacy-compatible reusable message or a fresh forward--backward exchange at each substep, adding Q−1Q-1 exchanges per round. Appendix~C.1 reports the experimental representation payload. Any refresh or auxiliary transmissions count toward the deployment's total.

In the Adult compression experiment, each client uploads its logits on the sampled minibatch and receives the reconstructed sum of its peers’ logits. It recomputes its gradient at every substep. The direction is exact for the minibatch objective with these inputs fixed. Under compression, it is exact for the objective formed with reconstructed peer logits.


Q2. Which assumptions of Theorems 1 and 2 does each experimental implementation satisfy? In particular, how do representation-level tracking, minibatch-dependent dual computation, and the strong concavity requirement for the adversarial maximization problem relate to the oracle used in the analysis?

Reply: Thank you for this point. Theorem 1 analyzes exact communication, and Theorem 2 analyzes bidirectional tracking of client optimization states and reusable messages. Also we have added Theorem 3 and Appendix A.9, which extends all previous communication round complexity results to representation tracking. We detailed the assumptions that our experiment below:

  • Main fairness. The quadratic dual term gives cc-strong concavity. The server computes the exact full-data dual response before drawing the primal minibatch, as in the analysis.

  • Adult compression. The dual response is exact for the sampled objective, and the same minibatch is reused for the local steps. BiEF tracks logits at the representation interface. Applying Theorem 2 requires verifying its message and oracle conditions at that interface.

  • Adversarial learning. Client-held perturbations realize the local-yy setting. Applying the convergence guarantee would require establishing strong concavity of the neural loss in those perturbations. The experiment evaluates local updates and compression empirically.

W2/Q3. Does the reported advantage in training time or communication persist at matched robust accuracy when all methods are evaluated with stronger attacks using more steps and multiple restarts under the same feature-partition threat model?

Reply. Thank you for great question! Following your question, we run several new experiments.

FedBCDA Exact and BiEF-FedBCDA had the two lowest training times per epoch among the seven methods in our H100 benchmark. Whether either method also saves time or communication at matched robust accuracy remains open. Answering that question requires measuring cumulative training time or bytes until each method reaches a common accuracy target under the same attack. Our new experiments address two parts of this comparison.

Effect of tuning for robust accuracy. We ranked configurations for each FedBCDA variant by held-out PGD-10 accuracy after 15 epochs and retrained the selected configurations for 100 epochs. The table reports CIFAR-10 test accuracy. The PGD and DecVFAL results are from their original configurations. The timing column comes from a separate H100 benchmark on the same training split, with batch size 80, averaged over epochs 2–10.

MethodOriginal clean (%)Original PGD-10 (%)Tuned clean (%)Tuned PGD-10 (%)H100 time (s/epoch)
PGD77.4461.97——148.15
DecVFAL77.7752.94——63.96
FedBCDA Exact86.1347.9581.4855.0948.79
BiEF-FedBCDA87.0145.4679.5145.6549.54

For FedBCDA Exact, tuning increased PGD-10 accuracy by 7.14 percentage points and reduced clean accuracy by 4.65 points. Its tuned PGD-10 accuracy of 55.09% exceeded DecVFAL's 52.94% and remained below PGD's 61.97%. For BiEF-FedBCDA, tuning increased PGD-10 accuracy by only 0.19 points and reduced clean accuracy by 7.50 points.

Evaluation under stronger attacks. We evaluated the five highest-ranked FedBCDA Exact configurations at epoch 100 using PGD-40 with one or five random starts. All attacks perturbed only client 0's feature partition, with an ℓ∞\ell_\infty budget of 8/2558/255 and a step size of 1/2551/255. Rows are ordered by validation PGD-10 accuracy. The three accuracy columns report test results (%), and QQ denotes the number of local updates per communication round.

Val. rankClient LRServer LRQQBatch sizePGD-10PGD-40 (1 start)PGD-40 (5 starts)
110−410^{-4}2.5×10−42.5\times10^{-4}108055.0946.1845.72
25×10−55\times10^{-5}2.5×10−42.5\times10^{-4}108055.3047.9147.61
35×10−55\times10^{-5}10−310^{-3}1024053.6445.4044.97
410−410^{-4}2.5×10−42.5\times10^{-4}1016053.1944.4143.93
55×10−55\times10^{-5}2.5×10−42.5\times10^{-4}1024054.9447.2046.82

The top-ranked configuration in the table achieved 45.72% test accuracy under PGD-40 with five random starts. Its separate H100 benchmark averaged 48.79 training seconds per epoch.


Q4. The adversarial objective does not establish the strong concavity required by the theory.

Reply: Thank you for identifying this point! Strong concavity is a condition for our convergence guarantees, in fact it is very common in related literature, e.g., Wang, Yisen, et al. "On the convergence and robustness of adversarial training." ICML 2019 (Section 4.2, Assumption 2). We therefore present these experiments as an empirical evaluation of local updates and compression in the local-yy setting.

Reviewer_aFZvOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies minimax problems in vertical federated learning. They consider four different settings: global-y and local-y, under either strongly-convex-strongly-concave (SC-SC) or nonconvex-strongly-concave (NC-SC) objectives. They propose two algorithms:

  1. FedBCD-Max: For global-y problems, at each iteration TT, the server computes an approximate maximizer yty^{t} and holds it fixed. Then, the clients run QQ local descent steps on their respective primal parameter blocks (xit)(x_{i}^{t}), and they synchronize.

  2. FedBCDA: For local-y problems, at each iteration TT, clients simultaneously run QQ local descent-ascent steps on their local (xi,yi)(x_{i},y_{i}) blocks. Then, one communication round provides the fixed cross-client information and synchronizes the updated blocks.

To those algorithms, they add bidirectional error feedback (Bi-EF), following the EF21 mechanism from previous work. For both versions of the algorithms, they establish finite-time convergence. Bi-EF adds an ω−2\omega^{-2} factor to the communication rounds, where ω\omega is the compressor contraction parameter.

Experiments cover fair vertical classification on Adult/COMPAS/Crime against FairVFL, and vertical adversarial training on CIFAR-10 and MNIST against PGD, FreeAT, FreeLB, YOPO and DecVFAL.

Critical strengths

The problem addressed is relevant, as separating global and local maximization variables naturally fits real-world VFL tasks like fairness and adversarial training. Additionally, the theoretical analysis is strong, providing a unified Lyapunov framework that successfully handles multiple regimes (SC-SC, NC-SC) while managing stale-block drift.

Critical weaknesses
  1. Mismatches between the theoretical theorems and the experiments setup: Theorem 2 establishes convergence under the assumption of compressing and tracking parameter blocks and their gradients. However, standard VFL setups transmit intermediate representations, and the experimental setup applies bidirectional compression to these intermediate activations and backward gradients at the communication interface. For the global-y setting (FedBCD-Max), the theoretical convergence proofs require the server to solve the inner maximization problem to a certified ϵt\epsilon_{t}-accuracy before clients perform their local descent steps. In the compression experiments, the implementation replaces this certified solver with an analytic dual response computed directly from a sampled stochastic mini-batch. The convergence analyses strictly require the objective to be SC with respect to the maximization variable yy in both the SC-SC and NC-SC settings. In the fair vertical classification experiment, the natural formulation is not strongly concave. To satisfy the theoretical assumption, the authors artificially induce strong concavity by adding a quadratic regularization term (−c2(λ12+λ22))(-\frac{c}{2}(\lambda_{1}^{2}+\lambda_{2}^{2})) to the objective.

  2. Unclear communication-efficiency in local updates: The communication bounds are uniform with respect to QQ when using a fixed effective step size of α=Qη\alpha=Q\eta. Because the maximum admissible effective step does not grow as QQ increases, the best theoretical round count for Q>1Q>1 is identical to the round count of a properly tuned Q=1Q=1 baseline. Reusing the same mini-batch and freezing cross-client information across QQ substeps effectively just discretizes a single block step, offering no provable theoretical speedup in communication rounds.

Questions for authors
  1. The sufficient message m_{i} = \mathcal{M}_{i} (\hat}u{) is not clear in a practical VFL context. Can you provide a concrete instantiation of Mi\mathcal{M}_{i} for a standard split-network VFL setup, and clarify what is actually transmitted without depending on the batch or violating privacy?

  2. For the global-yy setting, how is the ϵt\epsilon_{t}-accurate inner maximizer computed in a real VFL deployment, and how would its associated communication cost change the overall round complexity?

  3. Is there any specific regime where taking Q>1Q>1 local steps provably reduces the total number of communication rounds compared to a properly tuned Q=1Q=1 baseline?

3 comments

We appreciate the reviewer for the careful reading and pointing out issues on the the connection between the theory and practice, also the benefit of local steps.

Q1. In a standard split-network VFL setup, how is the sufficient message mi=Mi(u^)m_i=\mathcal M_i(\hat u) constructed, and what information is actually transmitted? Can the message be formed independently of the current minibatch while preserving label privacy?

Reply: Thank you for this point. In standard VFL, client ii sends its current representation hih_i, and the server uses the labels to compute and return the loss gradient using hih_i, so each exchange directly supports one exact update (Remark 4). Further exact updates require a fresh exchange or a reusable oracle compatible with label privacy.

Theorem 2 assumed the reusable message mi=Mi(u^t)m_i=\mathcal M_i(\hat u^t) before drawing the minibatch, and assume that the client can reuse this message at each local iterate. For example, in the newly-added quadratic counterexample of Remark 1 (also discussed in our reply to Q3), here mi=−ajt/4m_i=-a_j^t/4, and a separately supplied yty_t let client ii recompute its gradient after every local update, so the client can evaluate its gradient without contacting the server again.

In Adult experiment, each client uploads its logits on the sampled minibatch and reuses the reconstructed sum of its peers’ logits together with the round’s dual response. This payload depends on the sampled minibatch, and evaluating the exact local fairness gradient also requires a way to compute the loss terms held by the active party.


Q2. How would the server compute an ε\varepsilon-accurate inner maximizer in a practical global-yy VFL deployment? How would the communication required for this computation affect the overall round complexity?

Reply: Thank you for this point. In our global-yy setting, the server can evaluate the fixed inner objective from the inputs. It can run many off-the-shelf algorithms in centralized constrainted minimization, e.g., projected gradient ascent. Due to the strong concavity of the objective function, the inner iterations can converge to ϵ\epsilon-accurate solution in finite iterations. The inner iterations add zero communication rounds because it only requires local computation. The input transmissions and dual broadcast are counted in the round payload (Appendix~A.7.2).

In the special case of fairness experiment in Eq.(8), both the linear and MLP fairness models have the exact closed-form solution: λ⋆(D)=c−1([D−τ]+,[−D−τ]+),\lambda^\star(D)=c^{-1}([D-\tau]_+,[-D-\tau]_+), so the server can directly compute to attain the inner maximizer.


W2/Q3. Given that the current round bounds are uniform in QQ at a fixed effective stepsize QηQ\eta, is there a setting in which Q>1Q>1 provably reduces the total number of communication rounds relative to a well-tuned Q=1Q=1 baseline? Can multiple local steps yield such a benefit when they reuse the same minibatch and keep cross-client information fixed?

Reply: Thank you for great question! Yes, we have revised Remark 1 and added Appendix A.8, they provide a deterministic two-client example in which Q=2Q=2 reaches a worst-case relative envelope gap of 10−310^{-3} in two communication rounds, whereas the best Q=1Q=1 baseline with independently tuned fixed scalar stepsizes for the two clients requires three rounds. Both local steps reuse the same peer information and round-start maximizer.

Consider the deterministic case only, let xi=(ai,bi)x_i=(a_i,b_i), and

-\tfrac14a_1a_2+y(a_1+a_2)-\tfrac32y^2.$$ The envelope Hessian $S$ has eigenvalues $5/4,17/12,2,2$. Both local steps reuse the same objective, peer block, and round-start maximizer $y^\star(x^t)=(a_1^t+a_2^t)/3$. With $Q=2$ and step size $1/2$, the round map is $I-P_2S$, where $P_2=\operatorname{diag}(3/4,1/2,3/4,1/2)$, and its spectral radius is $1/16$. For $Q=1$, allow independently tuned fixed scalar steps $s_1,s_2>0$. With $E=\operatorname{diag}(s_1I_2,s_2I_2)$, the spectral radius is $\|I-S^{1/2}ES^{1/2}\|_2$. This expression is convex and invariant under swapping $s_1$ and $s_2$, so averaging the two steps cannot worsen it. The optimal common step is $8/13$, giving a spectral radius of $3/13$. For both maps, the worst-case relative envelope gap after $T$ rounds is $\rho^{2T}$. At a target of $10^{-3}$, $Q=2$ takes two rounds and the best fixed-scalar $Q=1$ takes three, with the same exchange pattern.

We also want to explain something you mentioned in Critical Weaknesses:


W1(a). How do the quantities tracked in Theorem 2 correspond to the intermediate activations and backward gradients compressed in the experiments? Does the representation-level implementation satisfy the tracking assumptions used in the theorem?

Reply: Thank you for identifying this very important point! We have added Theorem 3 and Appendix A.9, which extends all previous communication round complexity results to representation tracking. Theorem 2 analyzes this mechanism for client optimization states on the uplink and reusable messages on the downlink. With certain common regularity conditions like Lipschitz continuity of the encoder, our proposed algorithms preserve previous convergence guaratees. Appendix A.9 shows how these conditions bound both representation drift and the resulting gradient error.

In the Adult experiment, clients upload their own logits and receive the sum of the other clients' logits. They use that sum to recompute their gradients at each local step. Both links compress the difference between the current message and its tracked value.


W1(b). How does the analytic dual response computed from the current minibatch in the fairness compression experiment relate to the certified inner maximization required by the analysis?

Reply: Thank you for this question. In the Adult compression experiment, we substitute the disparity computed from the received minibatch logits into the closed-form dual response in Eq. (8), which exactly solves the inner problem for that minibatch. The analysis requires a certified solution of the round-start inner objective before the primal minibatch is drawn, whereas Table 4 uses the same minibatch for the dual response and the subsequent primal updates in all three methods.


W1(c). How does adding quadratic dual regularization to obtain strong concavity change the original fairness formulation? Which formulation is covered by the convergence guarantees?

Reply: We follow the DEO setup of surrogate of Liu et al. (2022a, Section 4.2) and use the same (and fixed) quadratic dual regularizer. Maximizing over the dual variables gives L(x)+[(∣D(x)∣−ϵ)+]22c,\mathcal L(x)+\frac{[(|D(x)|-\epsilon)_+]^2}{2c}, which penalizes the amount by which the disparity exceeds ϵ\epsilon. The regularizer also gives a closed-form dual response. Our global-yy convergence guarantees cover this fixed-cc formulation under the stated assumptions.

Thank you for your answers and the paper revision, especially Theorem 3 and the clearer scope boundaries. While the general bounds remain uniform in Q and exact Q>1 updates are still limited under private-label VFL, the paper is now more rigorous and transparent. I will to raise my score.

Reviewer_K5NkOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2(+1)
Presentation
2
Soundness
3(+1)
Read review
Paper summary

The paper studies vertical minimax federated learning under two settings, i.e., global-yy and local-yy. The authors develop FedBCD-Max and FedBCDA, respectively, allowing multiple local updates between communication rounds. They establish convergence guarantees for both algorithms under strongly convex–strongly concave (SC–SC) and nonconvex–strongly concave (NC–SC) assumptions. The proposed algorithms are further extended with bidirectional error-feedback compression, with corresponding convergence guarantees. Experiments on fair vertical classification and vertical adversarial learning are conducted to evaluate the proposed methods.

Critical strengths
  1. The paper establishes non-asymptotic convergence guarantees for the proposed algorithms under both SC–SC and NC–SC settings, with and without bidirectional error-feedback compression.
  2. The paper conducts experiments on fair vertical classification and vertical adversarial learning, covering both considered settings. The results demonstrate the effectiveness of the proposed algorithms and show that bidirectional error feedback can mitigate the performance degradation caused by direct compression.
Critical weaknesses
  1. The authors mention that maximization and compression introduce additional errors, but the paper does not adequately explain why these errors pose particular challenges in vertical minimax federated learning or what limitations of existing methods motivate the proposed approach.

  2. Although the paper establishes convergence guarantees for the proposed algorithms, a systematic theoretical comparison with related VFL methods is missing. A more detailed comparison in terms of problem settings, assumptions, convergence guarantees, and communication complexity (where applicable) is needed to clarify what additional theoretical contributions this work provides over existing methods.

Questions for authors
  1. For weakness 1, could the authors further clarify why the errors introduced by local updates, maximization, and bidirectional compression pose particular challenges in vertical minimax federated learning? What limitations of existing methods motivate the proposed algorithms?

  2. For weakness 2, could the authors provide a more detailed comparison with closely related work in terms of problem settings, assumptions, convergence guarantees, and communication complexity (where applicable)? What additional theoretical guarantees does this work provide over existing methods?

  3. A minor point: the text in some figures is too small to read clearly. I suggest increasing the font sizes.

2 comments

We appreciate the reviewer for the careful reading and pointing out issues to further clarify the details of our proposed algorithm and numerical experiments.

W1/Q1. Why are the errors arising from local updates, maximization, and bidirectional compression particularly challenging in vertical minimax federated learning? Which limitations of existing methods motivate the proposed algorithms?

Reply: Consider the global-yy case and suppose the server computes the exact maximizer yt=y⋆(xt)y^t=y^\star(x^t) at the start of a round. After client ii takes one local step, yty^t may already be suboptimal for the new point, even though every peer block is still frozen. Refreshing the maximizer would generally require the server to receive the updated client information. In our work, FedBCD-Max therefore reuses yty^t for all QQ steps, which introduces a source of gradient error beyond the stale peer blocks analyzed in FedBCD for minimization. In FedBCDA, each client updates its own primal and dual blocks, and both updates depend on peer blocks held fixed for the round, the dual update introduces another source of error.

Regarding the (bidirectional) compression you mentioned, it further couples these errors across rounds. In FedBCD-Max, the server uses the same reconstructed client state both to compute yty^t and to form the downlink message. An uplink error can therefore affect the client’s next gradient through two paths, and the downlink is itself compressed. Our analysis controls the resulting gradient error jointly, which includes the local drift, the maximization error, and the uplink and downlink tracking errors. All the errors mentioned above make the analysis challenging.


W2/Q2. How does the proposed work compare with closely related VFL methods in terms of problem settings, assumptions, convergence guarantees, and communication complexity where applicable? What additional theoretical guarantees does it provide?

Reply: Thank you for this point. Here we further discuss the difference between our work and existing closed related works in the table, which is also attached in the revised version.

MethodMain SettingApply Local Steps?Apply Compression?Convergence Guarantee
FedBCD-p (Liu et al., 2022b)VFL nonconvex minimizationYesNo1T∑t=0T−1E∥∇F(xt)∥2=O(1/T)\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}\|\nabla F(x_t)\|^2=O(1/\sqrt{T}), with sufficiently large batch size and local steps
C-VFL (Castiglia et al., 2022)VFL nonconvex minimizationYesYes1T∑t=0T−1E∥∇F(xt)∥2=O(1/T+E)\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}\|\nabla F(x_t)\|^2=O(1/\sqrt{T}+\mathcal{E}), with sufficiently large batch size, where E\mathcal{E} corresponds to the compression error
EF-VFL (Valdeira et al., 2025)VFL nonconvex minimizationNoYes1T∑t=0T−1E∥∇F(xt)∥2=O(1/T)\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}\|\nabla F(x_t)\|^2=O(1/T), with sufficiently large batch size
Fair VFL (Liu et al., 2022a)Minimax VFL, specifically for Fairness VFLYes (Active parties only)NoO(ϵ−4)O(\epsilon^{-4}) rounds to reach a projected first-order residual of at most ϵ\epsilon.
EGVFL (Beznosikov et al., 2026)Minimax VFL, specifically for Convex VFLNoYesO(ϵ−1)O(\epsilon^{-1}) rounds to reach primal-dual-gap at most ϵ\epsilon.
Ours (FedBCD-Max and FedBCDA)Minimax VFL, general, SC-SC and NC-SCYesYesO~(κ2log⁡(1/ϵ))\widetilde O(\kappa^2\log(1/\epsilon)) rounds in SC–SC, and O(1/ϵ)O(1/\epsilon) rounds in NC–SC. BiEF introduces an ω−2\omega^{-2} factor.

From the table above, our contribution is the joint analysis of local updates and bidirectional compression for both global-yy and local-yy VFL formulations under SC–SC and NC–SC assumptions. These guarantees complement prior results for VFL minimization and existing minimax VFL analyses.


Q3. Could the authors increase the font sizes in the figures where the text is difficult to read?

Reply: Thank you for pointing this out. We have refined the plots in Figures 2 and 3, and the axis titles and tick labels are further enlarged so they remain readable when zoomed in.

Thank the authors for the detailed response. My concerns are mainly addressed, thus I am raising my score.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General response

We thank all the reviewers for their careful reading. We have revised the manuscript (uploaded), added several new theoretical and experimental results. We summarize the main theoretical additions, experimental results, and clarifications below.

Local updates. Remark 1 and Appendix A.8 provide a deterministic two-client example in which Q=2Q=2 reaches a worst-case relative envelope gap of 10−310^{-3} in two communication rounds, whereas the best Q=1Q=1 baseline with independently tuned fixed scalar stepsizes for the two clients requires three rounds. Both local steps reuse the same peer information and round-start maximizer.

Representation-level communication. The new Theorem 3 extends the analysis to bidirectional error feedback when clients transmit Lipschitz encoder outputs. Under regularity conditions, all four communication-round bounds retain their original form. We also clarify two differences between theory and experiments, in the Adult compression study and the neural adversarial experiment.

Robustness evaluation. We repeated CIFAR-10 hyperparameter selection using held-out PGD-10 accuracy. For dense FedBCDA, test PGD-10 accuracy increased from 47.95% to 55.09%, while clean accuracy decreased from 86.13% to 81.48%. For BiEF-FedBCDA, PGD-10 accuracy changed only slightly, from 45.46% to 45.65%. The selected dense model achieved 45.72% under PGD-40 with five random starts on the same client feature partition. The two FedBCDA variants had the lowest per-epoch training times in a separate seven-method H100 benchmark.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.