- 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
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.
| Method | Original clean (%) | Original PGD-10 (%) | Tuned clean (%) | Tuned PGD-10 (%) | H100 time (s/epoch) |
|---|---|---|---|---|---|
| PGD | 77.44 | 61.97 | — | — | 148.15 |
| DecVFAL | 77.77 | 52.94 | — | — | 63.96 |
| FedBCDA Exact | 86.13 | 47.95 | 81.48 | 55.09 | 48.79 |
| BiEF-FedBCDA | 87.01 | 45.46 | 79.51 | 45.65 | 49.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 budget of and a step size of . Rows are ordered by validation PGD-10 accuracy. The three accuracy columns report test results (%), and denotes the number of local updates per communication round.
| Val. rank | Client LR | Server LR | Batch size | PGD-10 | PGD-40 (1 start) | PGD-40 (5 starts) | |
|---|---|---|---|---|---|---|---|
| 1 | 10 | 80 | 55.09 | 46.18 | 45.72 | ||
| 2 | 10 | 80 | 55.30 | 47.91 | 47.61 | ||
| 3 | 10 | 240 | 53.64 | 45.40 | 44.97 | ||
| 4 | 10 | 160 | 53.19 | 44.41 | 43.93 | ||
| 5 | 10 | 240 | 54.94 | 47.20 | 46.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- setting.
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−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 c-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-y 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.