acceptodds
Under review as a conference paper at ICLR 2027

SPADE-DFL: Communication-Efficient Decentralized Federated Learning via Derivative-Free Linearized ADMM

Abstract

Reducing communication in derivative-free decentralized learning requires controlling the disagreement accumulated over multiple local updates. This paper develops SPADE-DFL, a primal–dual method that allows the number of local function-value updates between neighbor exchanges to grow with the computation budget while preserving the nonprivate convergence order. For smooth nonconvex objectives under uniform query-moment bounds, the prescribed nonprivate schedule achieves a time-averaged stationarity and consensus bound of using only communication rounds, where is the number of local updates per client. For private training, the accumulated data-dependent increment is isolated from the graph correction, allowing one protected state per client and round to generate all outgoing messages. We prove client-level differential privacy for the full interactive transcript and quantify the resulting optimization error over a finite horizon. Experiments on four classification tasks show that SPADE-DFL achieves higher mean test accuracy than existing decentralized learning methods. Code is available at https://anonymous.4open.science/r/SPADE-DFL-1E2D.

Primary area:
learning theory
Keywords:
Decentralized federated learning, differential privacy, derivative-free optimization, one-point estimator, linearized ADMM, local training

Reviews

Among:
Shape:
1234this paper, Bottom 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.25 over 4 reviews, above 49% of the others.
Reviewer_32HXOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes SPADE-DFL, a derivative-free decentralized learning method combining component-memory single-point estimation with local linearized ADMM updates. Under uniform query-moment assumptions, a prescribed nonprivate schedule preserves an O(T−1/3)O(T^{-1/3}) stationarity--consensus bound while using Θ(T2/3)\Theta(T^{2/3}) communication rounds. A separate private release mechanism clips accumulated local increments and adds Gaussian noise, yielding client-level privacy for the interactive transcript and a finite-horizon optimization bound. Experiments evaluate classification accuracy and communication costs.

Critical strengths

The paper connects local derivative-free updates, explicit network stability, and transcript-level privacy within a unified analysis that accounts for communication and function-query costs.

Critical weaknesses

W1. The communication experiment does not establish savings at matched optimization accuracy. Section 5.5 compares schedules at the same local-update budget, making the reduction in communication largely follow from K=T/τK=T/\tau. At the largest budget, the reported 96.8% saving accompanies a stationarity--consensus residual of 0.010392 rather than 0.000372, approximately 28 times larger. This does not contradict the asymptotic order result, but it limits the empirical evidence for communication efficiency at a fixed target accuracy. Please report transmitted scalars required to reach common residual thresholds, along with the associated query costs.

W2. The classification comparisons need stronger resource and privacy controls. Section 5.2 fixes 50 communication rounds but combines single-point and symmetric two-point estimators, while SPADE-DFL also reinitializes its component memory each round. Section 4.4 correctly counts these initialization queries, yet the main comparison does not establish matched total query budgets or comparable privacy levels across the methods. The centralized DP-SGD baseline additionally uses a different communication setting. Comparisons at matched function-query budgets and, where applicable, matched privacy definitions and budgets would better isolate the algorithmic improvement.

W3. The scope of the privacy guarantee for the experimental pipeline should be made more explicit. The theorem protects replacement of a fixed-size client dataset under public, data-independent initialization and schedules, whereas the classification pipeline includes PCA fitted on the training split. Section 5.3 explicitly conditions the reported privacy guarantee on frozen preprocessing and partitioning. If the PCA transform is learned from the same protected data, holding it fixed across neighboring datasets requires additional justification and does not automatically provide privacy for the full pipeline. Please specify whether preprocessing uses public or disjoint data, is separately privatized, or lies outside the protected-data definition.

Questions for authors

Q1. Corollary 1 requires the oracle moment bound to be uniform over the prescribed family of runs as the smoothing radius decreases. How is this verified for the classification losses and query noise used in the experiments? Please distinguish a theoretical assumption from a property established for the evaluated models.

Q2. The communication schedule in Section 5.5 refers back to Corollary 1, which gives a nonprivate rate, while the method also has a private variant. Please state explicitly in the experiment and Figure 10 caption whether clipping and release noise are disabled; if not, provide their settings and the applicable finite-horizon bound.

4 comments

Thank you for distinguishing the communication theorem from the empirical evidence and identifying the preprocessing boundary of the privacy claim.

W1. Communication at matched optimization quality.

Your interpretation of Figure 10 is correct. At T=29,791T=29{,}791, the schedule with τ=31\tau=31 transmits 768,800 scalars versus 23,832,800 for τ=1\tau=1, but its mean residual is 0.010392 versus 0.000372, approximately 27.94 times larger. The 96.8% saving is therefore a matched-update-budget result, not a matched-residual result.

Corollary 1 establishes SK=O(T−1/3+τ2/T)\mathcal S_K=O(T^{-1/3}+\tau^2/T) with uniform constants under its assumptions. It gives sufficient asymptotic round bounds of O(εstat−2)O(\varepsilon_{\rm stat}^{-2}) for the prescribed schedule and O(εstat−3)O(\varepsilon_{\rm stat}^{-3}) for its τ=1\tau=1 specialization. Equal asymptotic order does not imply equal residuals at the tested budgets. We have revised the Figure 10 caption and Section 5.5 to identify this communication-residual trade-off and report the 27.94 residual ratio.

An exploratory post hoc comparison of existing 30-seed runs gives the following nearby residual levels.

ScheduleLocal-update budget TTMean residualTransmitted scalarsFunction queries
τ=1\tau=11,0000.010252800,0002,160,000
τ=31\tau=3129,7910.010392768,8006,688,560

Between these two measured points, the longer local stage uses approximately 3.9% fewer transmitted scalars and 3.1 times as many function queries. These are separate runs with TT-dependent parameter schedules, and their residuals are not identical. The comparison is therefore descriptive and does not determine the costs of attaining a common threshold.

Section 5.5 and the revised Figure 10 caption identify the matched-update-budget comparison, and the limitations paragraph states that matched-residual comparisons remain unestablished.

W2. Resource and privacy controls.

We agree that 50 rounds are insufficient to equalize computation. The Table 1 SPADE-DFL implementation retains memory across rounds. The per-round initialization cost in Section 4.4 applies to the analyzed algorithm. Two-point estimates require two function calls per sampled component, and any baseline initialization/refresh calls must also be counted. Section 5.2 and the Table 1 caption now explicitly restrict the comparison to its method-specific query and privacy configurations.

Controlled comparisons require matched queries, partitions, topology, tuning, and privacy unit, adjacency, observation model and total (ϵ,δ)(\epsilon,\delta). Record-level and client-replacement guarantees differ. Pooled-data DP-SGD remains a centralized reference.

The table reports recorded training function evaluations per run, summed across clients and including initialization and refresh calls. Ranges reflect fold-dependent counts for Alzheimer's disease and seed-dependent Poisson sampling for Brain Tumor DP-SGD; they are not confidence intervals. These counts make the computational differences explicit and do not imply matched-query comparisons.

MethodMNISTFashion-MNISTAlzheimer'sBrain Tumor
LT-ADMM-VR1,224,5001,206,200178,100–178,200566,200
LT-ADMM-DP6,2006,2006,2006,200
DP-SGD3,1003,1003,1005,404–5,924
DP-FedAvg1,218,3001,200,000171,900–172,0002,240,000
1P-DSG1,5811,5811,5811,581
1P-DSGT1,5811,5811,5811,581
SPADE-DFL61,78361,600150,519–150,520402,400

DP-SGD and DP-FedAvg both target (8,10−5)(8,10^{-5}), but their accounting protects different units: individual records for DP-SGD and clients for DP-FedAvg under a trusted-server model. The SPADE-DFL budgets reported in Section 5.3 apply to the training transcripts from those runs, conditional on fixed preprocessing and partitioning. The privacy budgets in Section 5.3 are specific to those runs, so we report no DP budget for the SPADE-DFL entries in Table 1. The recorded counts show differences in both directions. For MNIST, SPADE-DFL uses 61,783 function calls per run, compared with 1,581 for each of the two single-point baselines and 1,224,500 for the LT-ADMM-VR adaptation. Thus the relative query cost depends on the reference method, even when all three decentralized comparisons use the same number of rounds. The accuracy values in Table 1 characterize the tested configurations, and the query totals make the cost differences explicit.

W3. PCA and the protected-data definition.

The reported guarantee covers the interactive training transcript conditional on a fixed preprocessing map and client partition; it does not establish end-to-end privacy for raw data.

(1) Status of preprocessing. Brain Tumor MRI uses PCA fitted on the training split. This fit has not been established as public, independent of the protected data, or separately private, and its privacy cost is outside the reported training-stage accounting. Freezing the fitted transform does not resolve this issue: replacing a raw client dataset could change the PCA basis and hence the representations of other clients' data.

(2) Supported privacy statement. Section 5.3 now explicitly limits the guarantee to replacement of one fixed-size preprocessed client dataset while the preprocessing map and partition remain fixed. An end-to-end guarantee would require independently fixed preprocessing or a private preprocessing mechanism whose privacy cost is composed with training, including any data-dependent normalization and partitioning.

Q1. Uniformity across smoothing radii and runs.

Appendix B now explicitly labels its bounded-loss example as sufficient, rather than verification of the experimental objectives, and points to the original Assumption 3 instead of restating it. If losses satisfy ∣f∣≤Bf|f|\le B_f and centered query noise has conditional variance at most σζ2\sigma_\zeta^2, with both constants independent of T,μT,\mu, then M2≤Bf2+σζ2M_2\le B_f^2+\sigma_\zeta^2 is uniform. Unconstrained cross-entropy does not automatically meet this condition.

For the main classification comparisons, MNIST and Fashion-MNIST use a sigmoid loss with quadratic regularization, Alzheimer's uses logistic loss with bounded regularization, and Brain Tumor MRI uses softmax cross-entropy with quadratic regularization. These objectives do not provide the global bounded-loss justification used in Appendix B, and we have not established a uniform query-moment bound across the prescribed runs.

The Alzheimer's oracle evaluates the loss directly. The other three implementations apply a mean-one Gaussian multiplier to the margin or logits and add centered Gaussian noise. Because the multiplier acts inside a nonlinear loss, the resulting perturbation is not generally conditionally centered relative to the nominal objective. Thus, both the required moment uniformity and the applicability of the centered-noise model need to be distinguished from the implementation settings.

By contrast, Figure 10 evaluates the synthetic squared sigmoid loss directly. It lies in [0,1/2][0,1/2] at every queried point, giving a second-moment bound of 1/41/4 independently of TT and μ\mu. The synthetic study therefore supplies an instance satisfying the query-moment condition; the classification studies are empirical evaluations.

Q2. Whether Figure 10 is nonprivate.

Yes. Both Figure 10 schedules use the nonprivate setting of Corollary 1: clipping and Gaussian release noise are disabled, and the synthetic component loss is evaluated without query noise. Thus, the experiment concerns the nonprivate communication schedule rather than the private finite-horizon guarantee.

The new limitations paragraph records the remaining empirical gaps; no additional experiments or stronger pipeline privacy are claimed.

Thank you for the clarification. I will increase my score by one point.

We sincerely thank the reviewer for reconsidering our responses and updating their assessment. We appreciate your thoughtful feedback and constructive suggestions, which have helped us clarify the methodological contributions, strengthen the theoretical analysis, and improve the quality of the manuscript.

Thank you again for your time and consideration throughout the discussion.

Reviewer_joxROpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

SPADE-DFL addresses decentralized learning when clients can evaluate losses but cannot access gradients. It combines single-point function-value estimates, component memory, and multiple local updates with a fixed ADMM correction before exchanging information with neighbors.

Under smoothness, network connectivity, and uniform query-moment bounds, the nonprivate analysis establishes an O(T−1/3)O(T^{-1/3}) stationarity–consensus rate using Θ(T2/3)\Theta(T^{2/3}) communication rounds. The private variant clips and perturbs the accumulated local update once per round, providing client-level privacy for the interactive transcript and a finite-horizon optimization bound.

Experiments on four feature-based classification tasks report higher mean accuracy under the tested configurations and examine communication savings, data heterogeneity, client counts, and privacy budgets.

Critical strengths
  1. Explicit communication–computation trade-off. Under the stated assumptions, Corollary 1 shows that τ=Θ(T1/3)\tau=\Theta(T^{1/3}) local updates preserve the nonprivate O(T−1/3)O(T^{-1/3}) stationarity–consensus rate while requiring only Θ(T2/3)\Theta(T^{2/3}) communication rounds. This directly addresses the paper’s central problem and provides a principled schedule for reducing exchanges without losing the convergence order.

  2. Sound privacy analysis for the complete interaction. Theorem 1 establishes client-replacement privacy for the full transcript by protecting the accumulated local increment once per round. All outgoing messages use the same protected state. This gives a clear guarantee covering the actual neighbor exchanges and makes the relationship between communication frequency and privacy accounting explicit.

Critical weaknesses

The paper does not clearly establish a substantial advance over existing methods. Its design largely combines established optimization and privacy components, while the benefit of the added memory mechanism is not demonstrated. Although the communication analysis is useful, the advantage of the full method over a simpler extension of prior work remains unclear.

The claimed communication–accuracy–privacy advantage is insufficiently supported. The private optimization analysis does not provide a fully specified privacy–utility trade-off, and the experiments compare methods under different computation and privacy settings. Consequently, the reported results do not establish that the method achieves better learning outcomes under comparable conditions.

Questions for authors
  1. Could you clarify what is new compared with LT-ADMM and LT-ADMM-VR? In particular, which part of the analysis allows the number of local steps to grow while preserving the convergence order?

  2. Could you explain what component memory adds over fresh single-point estimates? Do the analysis or ablations show that the benefit offsets the extra queries and storage?

  3. Could you state the computation budgets and privacy guarantees used for each method, including the definition of neighboring datasets?

  4. Do the existing results show communication savings when methods are compared at the same optimization quality?

  5. The anonymous repo link is not working.

3 comments

Thank you for recognizing the communication schedule and transcript-level privacy analysis. We have revised the contribution framing, resource accounting, privacy scope, and finite-horizon calibration; we do not present new experiments. The Table 1 implementation retains memory across rounds. Section 4.4 counts per-round initialization for the analyzed algorithm.

W1/Q1. What is new, and what permits the local stage to grow?

(1) Contribution relative to existing components. The frozen neighbor correction comes from LT-ADMM, and the component-memory idea from LT-ADMM-VR/SAGA. The specific result here couples the single-point oracle with the network recursion so that the local stage can grow with the budget.

(2) Mechanism allowing a growing local stage. Set T=KτT=K\tau, η=Θ(T−1/2)\eta=\Theta(T^{-1/2}), μ=Θ(T−1/6)\mu=\Theta(T^{-1/6}), and β=a0/(τημ)\beta=a_0/(\tau\eta\mu). For fixed graph and ρ\rho, a=τβημ=a0a=\tau\beta\eta\mu=a_0 remains in the stability region 0<a0ρλN<8/30<a_0\rho\lambda_N<8/3. The graph-mode matrices and Lyapunov constants therefore do not deteriorate with τ\tau. In the proof of Theorem 2, (τ−1)2(ημ)2β2≤a02(\tau-1)^2(\eta\mu)^2\beta^2\le a_0^2 also bounds the local-disagreement coefficient uniformly. The remaining drift is η2τ2=O(τ2/T)\eta^2\tau^2=O(\tau^2/T), giving SK=O(T−1/3+τ2/T)\mathcal S_K=O(T^{-1/3}+\tau^2/T). We have made this mechanism explicit after Corollary 1. It permits τ=Θ(T1/3)\tau=\Theta(T^{1/3}) under uniform oracle moments, with sufficient round bounds relative to the same method at τ=1\tau=1.

(3) Scope of the comparison. Corollary 1 and Section 4.4 compare sufficient round bounds for the prescribed schedule and the same method at τ=1\tau=1. They do not establish a complexity advantage over native LT-ADMM/LT-ADMM-VR. The fixed-gain argument is detailed after Corollary 1 and in Appendix E.

W1/Q2. What does component memory add over fresh one-point estimates?

(1) Established property. Lemma 1 proves conditional-mean preservation and E∥v∥2≤9Q2\mathbb E\|v\|^2\le9Q^2. It does not prove a strict variance or convergence-rate improvement over fresh one-point estimates. Under uniform component sampling, the expected sampled memory entry equals the table average, so the memory correction cancels in conditional expectation. Any variance benefit depends on how well the stored directions track the fresh estimates, which the present bound does not quantify.

(2) Computational cost. The round-reset algorithm analyzed in Section 4.4 uses Kmi+TbiK m_i+T b_i queries and O(mid)O(m_i d) storage. The classification implementation retains memory across rounds and uses mi+Tbim_i+T b_i queries, as stated in Section 5.2.

(3) Empirical conclusion. The current results do not establish that the benefit of memory offsets these query and storage costs. No matched-query ablation against fresh one-point estimates has been added, and Section 5.2 explicitly states that the reported comparisons do not isolate memory benefit.

Q3. Computation, adjacency, and privacy-utility trade-off. Section 5.2 uses 50 rounds and 30 paired seeds. The decentralized methods use 31 clients; SPADE-DFL uses τ=2\tau=2 for MNIST/Fashion-MNIST/Brain Tumor MRI and τ=8\tau=8 for Alzheimer's disease. Four baselines use two-point adaptations, whereas SPADE-DFL/1P-DSG/1P-DSGT use one-point estimates. Equal rounds therefore do not imply equal queries. Pooled-data DP-SGD is a centralized reference, not a matched decentralized communication baseline.

Our theorem uses replacement of one entire fixed-size client dataset. Section 5.3 reports this adjacency with δ=10−5\delta=10^{-5}, conditional on fixed preprocessing and partitioning. We have made the training-stage privacy boundary explicit in Section 5.3.

The table reports recorded training function evaluations per run, summed across clients and including initialization and refresh calls. Ranges reflect fold-dependent counts for Alzheimer's disease and seed-dependent Poisson sampling for Brain Tumor DP-SGD; they are not confidence intervals. These counts make the computational differences explicit and do not imply matched-query comparisons.

MethodMNISTFashion-MNISTAlzheimer'sBrain Tumor
LT-ADMM-VR1,224,5001,206,200178,100–178,200566,200
LT-ADMM-DP6,2006,2006,2006,200
DP-SGD3,1003,1003,1005,404–5,924
DP-FedAvg1,218,3001,200,000171,900–172,0002,240,000
1P-DSG1,5811,5811,5811,581
1P-DSGT1,5811,5811,5811,581
SPADE-DFL61,78361,600150,519–150,520402,400

The DP-SGD and DP-FedAvg configurations target (8,10−5)(8,10^{-5}) at record and client levels, respectively. DP-FedAvg accounts for server outputs under a trusted-server model. The SPADE-DFL budgets in Section 5.3 apply to the training transcripts from that section under fixed preprocessing and partitioning. The privacy budgets in Section 5.3 are specific to those runs, so we report no DP budget for the SPADE-DFL entries in Table 1.

Appendix E now provides explicit calibration from Theorems 1-2. Let r=(log⁡(1/δ)+ϵ−log⁡(1/δ))2r=(\sqrt{\log(1/\delta)+\epsilon}-\sqrt{\log(1/\delta)})^2, RR be a constant clipping radius, and α=ημ\alpha=\eta\mu. Uniform release noise can be chosen as σ2=2KR2/r\sigma^2=2KR^2/r, where ϵ=r+2rlog⁡(1/δ)\epsilon=r+2\sqrt{r\log(1/\delta)}. The corresponding term inside the finite-horizon O(⋅)O(\cdot) bound is (1+1Nτα)2dKR2r.\left(1+\frac{1}{N\tau\alpha}\right)\frac{2dKR^2}{r}. The clipping term remains (1+1/(τα2))E‾cl,K(1+1/(\tau\alpha^2))\overline{\mathcal E}_{\mathrm{cl},K}. Fewer releases reduce the required per-release noise for fixed R,rR,r, but local drift and clipping must still be controlled. This is a finite-horizon accounting relation, not an optimized private convergence rate or proof of empirical superiority. Table 2 provides a separate empirical view of the privacy-utility trade-off for SPADE-DFL. At 100 clients, the mean Brain Tumor MRI validation accuracy rises from 43.29% at ϵ=4\epsilon=4 to 70.96% at ϵ=32\epsilon=32. The corresponding Fashion-MNIST values are 92.50% and 93.55%. The different changes show how sensitivity to the budget varies across tasks in this evaluation. These results concern the configurations in Section 5.3 under the fixed preprocessing and partitioning discussed there.

Q4. Communication at the same optimization quality.

The existing results do not establish communication savings at a common prespecified residual threshold. Figure 10 reports a 96.8% reduction at equal local-update budgets, where the mean residuals are 0.010392 and 0.000372. Corollary 1 gives sufficient asymptotic round bounds at a common tolerance; it does not imply equal finite-budget residuals.

An exploratory post hoc comparison of existing 30-seed runs gives the following nearby residual levels.

ScheduleLocal-update budget TTMean residualTransmitted scalarsFunction queries
τ=1\tau=11,0000.010252800,0002,160,000
τ=31\tau=3129,7910.010392768,8006,688,560

Between these two measured points, the longer local stage uses approximately 3.9% fewer transmitted scalars and 3.1 times as many function queries. These are separate runs with TT-dependent parameter schedules, and their residuals are not identical. The comparison is therefore descriptive and does not determine the costs of attaining a common threshold.

Section 5.5 and the revised Figure 10 caption identify the matched-update-budget comparison, and the limitations paragraph states that matched-residual comparisons remain unestablished.

Q5. Repository link.

Thank you for flagging the access issue. The anonymous repository link has been updated and is now accessible.

Thank you again for your time and efforts in reviewing our paper.

As the discussion period draws to a close today, we kindly remind you that only a few hours remain for further comments or questions. We would appreciate the opportunity to address any additional concerns you may have before the discussion phase ends.

Thank you very much!

Many thanks, Authors

Reviewer_uXgpOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes SPADE-DFL, a decentralized federated-learning method for settings where clients have access only to function values. The method combines a single-point zeroth-order component estimator with a SAGA-like table of past component evaluations, local primal training between communication rounds, and a linearized ADMM consensus update over a peer-to-peer graph. The paper derives stationarity and consensus-residual rates for non-private and private variants, including a communication schedule intended to reduce the number of rounds, and gives a transcript-level privacy guarantee. Experiments on binary PCA-reduced MNIST and FMNIST, an Alzheimer's tabular dataset, and frozen/PCA-reduced Brain Tumor image features compare SPADE-DFL with centralized, federated, and decentralized baselines. It shows that SPADE-DFL improves privacy-preserving derivative-free learning while reducing communication.

Critical strengths

Technically ambitious integration. The paper combines component-memory variance reduction, derivative-free local optimization, decentralized linearized ADMM, periodic communication, clipping, and transcript-level client privacy in one framework.

Detailed analysis. The convergence development explicitly tracks smoothing, estimator memory, local-update drift, graph disagreement, and privacy noise. The paper also distinguishes stationarity from consensus feasibility rather than reporting only an objective value.

The empirical study includes several useful dimensions. Results cover four datasets/partitions, multiple privacy budgets, client counts, heterogeneity levels, and communication intervals, with 30 random seeds reported for the main comparisons.

Critical weaknesses

The query-moment assumption may not match common learning losses (fixable clarification). Assumption 3 requires uniformly bounded second moments of queried function values over the parameter domain. The appendix gives a bounded squared-probability-loss example, whereas standard cross-entropy on an unconstrained parameter domain is unbounded. The exact objective used in every experiment and its compatibility with the assumption should be explicit; otherwise projection or a bounded-domain analysis may be required.

Several assumptions limit external validity (fixable/fundamental). The analysis relies on smooth component objectives, bounded function-value moments, a fixed connected graph, synchronized clients, and exact local function queries. The paper does not empirically study graph changes, stragglers, failures, or costly black-box evaluations, although these are central motivations for decentralized derivative-free learning.

Questions for authors

Which loss is used in each experiment, and does it satisfy Assumption 3's uniform second-moment bound over all queried parameters?

Why Assumption 3 is repeated twice, one in Section 3, another in Appendix?

7 comments

Thank you for the careful assessment and for recognizing the analysis of estimation, local drift, network disagreement, and privacy. We have revised Appendix B and added an explicit scope-and-limitations paragraph to distinguish sufficient theoretical conditions from verified experimental properties.

W1/Q1. Experimental losses and applicability of Assumption 3.

We agree that smoothness alone does not imply Assumption 3. We have not established a query-moment bound that is uniform over the prescribed family of classification runs. The bounded-loss example in Appendix B is a sufficient example, rather than verification of the experimental objectives.

(1) Objectives and function-value oracles. For a sample with features aa and label yy, the nominal component losses in the main-comparison implementations are:

  • MNIST and Fashion-MNIST: sigmoid⁡(ya⊤w)+0.1∥w∥2\operatorname{sigmoid}(y a^\top w)+0.1\|w\|^2.
  • Alzheimer's disease: log⁡(1+exp⁡(−ya⊤w))+0.01∑jwj2/(1+wj2)\log(1+\exp(-y a^\top w))+0.01\sum_j w_j^2/(1+w_j^2).
  • Brain Tumor MRI: −log⁡[softmax⁡(W⊤a)]y+0.1∥W∥F2-\log[\operatorname{softmax}(W^\top a)]_y+0.1\|W\|_F^2.

The Alzheimer's oracle evaluates its loss directly. In the other three implementations, the margin or logits are multiplied by r∼N(1,0.012)r\sim\mathcal N(1,0.01^2), and independent additive noise ξ∼N(0,1)\xi\sim\mathcal N(0,1) is added to the queried loss. The Brain Tumor one-point estimator additionally subtracts the known constant log⁡4\log 4. This constant does not change the objective gradient, but does affect the single-point estimator's second moment.

(2) What has and has not been established. The quadratic penalties and the unbounded logistic or cross-entropy terms prevent a global bounded-loss justification for these objectives. This does not by itself prove that the generated queries violate Assumption 3, but it means that the bounded example in Appendix B cannot establish the required uniformity.

There is also a separate centering issue. Relative to the nominal loss, a mean-one multiplier inside a nonlinear loss does not generally produce conditionally centered noise. Thus, Assumption 3's allowance for centered query noise does not automatically cover these implementations.

We therefore treat the classification studies as empirical evaluations for which applicability of the convergence guarantee has not been established.

(3) Why the synthetic experiment satisfies the moment condition. Figure 10 directly evaluates fi,h(x)=12(sigmoid⁡(ai,h⊤x)−yi,h)2.f_{i,h}(x)=\frac12\bigl(\operatorname{sigmoid}(a_{i,h}^{\top}x)-y_{i,h}\bigr)^2. For binary labels, this loss lies in [0,1/2][0,1/2] at every queried point. Hence E[∣f~i,h(x+μu)∣2∣F]≤14\mathbb E[|\widetilde f_{i,h}(x+\mu u)|^2\mid\mathcal F]\le\frac14 uniformly in the iterate, smoothing radius, and horizon.

More generally, Appendix B gives the sufficient condition M2≤Bf2+σζ2M_2\le B_f^2+\sigma_\zeta^2 when the queried component loss is bounded by BfB_f and the additive noise is conditionally centered with conditional second moment at most σζ2\sigma_\zeta^2. Constants independent of TT and μ\mu supply the uniformity required by Corollary 1.

The revised Appendix B and the scope-and-limitations paragraph distinguish this sufficient condition from properties verified for the experiments. Adding a projection would change the algorithm and require a constrained-stationarity analysis; it cannot retrospectively justify the current theorem.

Q2. Repeated statement of Assumption 3.

Section 3.2 gives the main-text statement, and Appendix B restates the same assumption to make the estimator proof self-contained. They are not two independent assumptions. We have removed the duplicate statement and replaced it with a cross-reference to Assumption 3 in Section 3.2, retaining the bounded-loss example and proof. The mathematical conditions are unchanged.

Q3. Scope and external validity.

We agree that the proved setting is narrower than decentralized deployment in general. The analysis requires a fixed connected undirected graph and synchronized exchanges; the reported experiments do not establish robustness to time-varying graphs, stragglers, or failures. The new scope-and-limitations paragraph following Section 5.5 explicitly states these conditions and untested scenarios. These assumptions enter the proof through the network recursion. The fixed graph lets us analyze the same graph modes throughout training and control them with a common set of stability constants. Synchronous exchanges define when the neighbor correction is refreshed and how long it is held fixed during local updates. A changing graph or delayed exchange would change that recursion, so extending the result requires an analysis that accounts for the resulting sequence of graph operators or delayed messages.

One clarification is that Assumption 3 permits noisy function values through conditionally centered ζ\zeta with bounded conditional second moment. Thus the theory does not require exact deterministic queries. Biased oracle errors and unbounded noise moments are not covered.

Section 4.4 counts the cost of function evaluations, including the memory reset: client ii uses Kmi+TbiK m_i+T b_i queries and O(mid)O(m_i d) memory. This quantifies oracle usage but does not establish a wall-clock benefit for expensive black-box evaluations. The revised limitations distinguish this query accounting from untested wall-clock or deployment benefits.

Appendix B now states that unconstrained cross-entropy and unbounded regularization are not covered by its sufficient bounded-loss example, and finite observed losses do not establish uniformity. This preserves the scope of the convergence result while making its empirical applicability auditable.

Thank you again for your time and efforts in reviewing our paper.

As the discussion period draws to a close today, we kindly remind you that only a few hours remain for further comments or questions. We would appreciate the opportunity to address any additional concerns you may have before the discussion phase ends.

Thank you very much!

Many thanks, Authors

Reviewer_SuXmOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper proposes a primal-dual method that allows the number of local updates between neighbor exchanges to grow with the computation budget. It uses a derivative-free linearized ADMM approach. The authors then prove client-level differential privacy for their approach.

Critical strengths
  1. The paper studies communication-computation tradeoff in DFL, which is an important aspect of this field.
  2. The numerical experiments show the improvements SPADE-DFL achieves over some baselines.
Critical weaknesses

The paper is not presented with clarity, and it is hard to understand its novelty in its current form:

  • (Sec. 1) SPADE-DFL is motivated as a derivative-free primal-dual approach in the title and the abstract, but the Introduction does not discuss either the derivative-free aspect or the primal-dual aspect of the approach. This makes the Introduction not be clear about how SPADE-DFL is novel and what known issue in existing methods is it improving.
  • (Sec. 2) The Related Work seems as a list of papers, some relevant to SPADE-DFL and some, without any context or intuition. This section could be used to emphasize the significance of SPADE-DFL.
  • (Sec. 3) As an illustration to help readers understand the paper, Figure 1 contains too much granular information to be helpful in appreciating the workflow of SPADE-DFL.
  • (Sec. 5) None of the baselines (LT-ADMM-VR, LT-ADMM-DP, DP-SGD, DP-FedAvg, 1P-DSG, 1P-DSGT) are cited for their original paper. Also, some baselines on (a) other primal-dual approaches (not derivative-free) and (b) derivative-free algorithms (not primal-dual) are missing to help better understand the significance of SPADE_DFL.
Questions for authors

Please see weaknesses.

3 comments

Thank you for recognizing the importance of the communication-computation trade-off and for identifying where the presentation obscures the contribution. We have revised the Introduction, Related Work, the caption of Figure 1, and the baseline definitions to distinguish the technical result from inherited components.

W1. Motivation and methodological novelty.

We agree that the Introduction needed to explain more directly why derivative-free feedback and a primal–dual formulation are considered together. We have revised it to distinguish the motivation, inherited components, and new analytical contribution.

(1) Motivation. We consider clients that can evaluate component losses but cannot access their gradients. Performing multiple local updates reduces neighbor exchanges, but also accumulates estimation error and disagreement. The primal–dual formulation provides an explicit correction for the consensus constraints. The resulting question is how far local function evaluations can replace communication while preserving the convergence order.

(2) Contribution beyond existing components. The frozen neighbor correction and component-memory mechanism build on LT-ADMM and LT-ADMM-VR/SAGA. Our contribution is the coupled analysis of single-point estimation, local drift, and network feedback. The single-point estimator's conditional mean scales with the smoothing radius, so the smoothing radius, stepsize, local-stage length, and primal–dual gain must be controlled jointly.

With T=KτT=K\tau, the schedule η=Θ(T−1/2)\eta=\Theta(T^{-1/2}), μ=Θ(T−1/6)\mu=\Theta(T^{-1/6}), and β=a0/(τημ)\beta=a_0/(\tau\eta\mu) fixes the round gain at a=τβημ=a0a=\tau\beta\eta\mu=a_0, where 0<a0ρλN<8/30<a_0\rho\lambda_N<8/3. For a fixed graph and ρ\rho, this keeps the graph-mode matrices and Lyapunov constants unchanged. The remaining local-drift contribution is τ2/T\tau^2/T, giving SK=O(T−1/3+τ2/T).\mathcal S_K=O(T^{-1/3}+\tau^2/T). Consequently, τ=Θ(T1/3)\tau=\Theta(T^{1/3}) preserves the nonprivate convergence order using Θ(T2/3)\Theta(T^{2/3}) communication rounds. At a common tolerance εstat\varepsilon_{\rm stat}, the sufficient round bound changes from O(εstat−3)O(\varepsilon_{\rm stat}^{-3}) for the τ=1\tau=1 specialization to O(εstat−2)O(\varepsilon_{\rm stat}^{-2}) under the prescribed schedule. This comparison requires uniform oracle moments and does not establish universal superiority over first-order methods.

(3) Separate privacy contribution. The private extension protects the accumulated data-dependent increment once per round while keeping the transcript-determined graph correction explicit. All outgoing messages use the same protected state. Theorem 1 therefore accounts for the full interactive transcript under replacement of an entire fixed-size client dataset.

These distinctions are presented in the revised Introduction and Section 2. The fixed-gain mechanism is explained immediately after Corollary 1 and in Appendix E.

W2. Organization and positioning of the related work.

We have revised Section 2 to explain how prior work motivates our contribution. Sections 2.1–2.2 identify LT-ADMM/LT-ADMM-VR and 1P-DSG/1P-DSGT-NC as the closest local primal-dual and single-point families. We then explain how jointly controlling smoothing, local drift, and network feedback permits growing local stages while preserving the nonprivate convergence order under the stated assumptions. Section 2.3 contrasts our per-round increment protection with LT-ADMM-DP's per-step gradient protection and distinguishes their privacy units. Appendix A, Table 3 summarizes these relationships and analytical scopes.

W3. Clarifying the workflow in Figure 1.

We agree that the detailed operations in the original figure obscured the overall workflow. We have simplified Figure 1 and revised its caption to make the sequence of operations and the distinction between local computation and neighbor communication clearer. The workflow consists of four stages.

  1. Local computation. Each client holds its neighbor correction fixed while performing multiple local updates using component function values and refreshing sampled memory entries.
  2. Private release, when enabled. The client clips and perturbs the accumulated data-dependent increment once.
  3. Neighbor exchange. All outgoing ADMM messages are constructed from the same released state.
  4. State update. Received messages update the edge states used in the next round.

The key distinction is between a local update and a communication round. Increasing the local-stage length reduces the frequency of exchanges; each exchange still sends one model-dimensional vector per directed edge. Algorithm 1 and Sections 3.2–3.3 provide the detailed estimator, memory, and message-update operations.

W4. Baseline provenance and coverage (Section 5).

We have added original-source citations beside every baseline definition in Section 5.2. LT-ADMM/LT-ADMM-VR originate in Ren et al., Communication-Efficient Stochastic Distributed Learning; LT-ADMM-DP in Ren et al., Communication-Efficient Distributed Learning with Differential Privacy. DP-SGD cites Abadi et al. (CCS 2016), and DP-FedAvg cites McMahan et al. (ICLR 2018). These citations identify provenance, not verification of the implementation-specific privacy accountant. The one-point sources are Mhanna and Assaad (TMLR 2024, 1P-DSG; ICML 2023, 1P-DSGT-NC).

Crucially, Section 5.2 uses two-point adaptations of LT-ADMM-VR, LT-ADMM-DP, DP-SGD, and DP-FedAvg. We have explicitly labelled these as zeroth-order adaptations; they do not replace native first-order primal-dual comparisons. The existing one-point baselines address the derivative-free/non-primal-dual category, but their implementation details and query costs need to be explicit. A native LT-ADMM/LT-ADMM-VR comparison and a fresh-estimator ablation would further isolate the contribution. We do not claim those additional results are already available.

The revised paper centers the growing-local-stage analysis and transcript-level privacy result. The abstract and experiments now restrict empirical claims to the configurations evaluated; no new experimental comparison is claimed.

Thank you again for your time and efforts in reviewing our paper.

As the discussion period draws to a close today, we kindly remind you that only a few hours remain for further comments or questions. We would appreciate the opportunity to address any additional concerns you may have before the discussion phase ends.

Thank you very much!

Many thanks, Authors

Comments on the paper

1 comment

We thank reviewers SuXm, uXgp, joxR, and 32HX for their careful evaluations and constructive feedback. To facilitate the discussion, we summarize the main revisions and clarifications below.

Methodological Contribution and Relation to Prior Work

  • Contribution framing (SuXm, joxR). The revised Introduction and Related Work distinguish the inherited local-training ADMM and component-memory mechanisms from our contribution: a coupled analysis of single-point estimation, local drift, and primal–dual network feedback.
  • Growing local stages (SuXm, joxR). The explanation following Corollary 1 and in Appendix E makes the fixed-round-gain mechanism explicit. Keeping a=τβημ=a0a=\tau\beta\eta\mu=a_0 fixes the network stability constants, leaving the local-drift contribution τ2/T\tau^2/T. Under uniform oracle moments, this permits τ=Θ(T1/3)\tau=\Theta(T^{1/3}) while preserving the nonprivate O(T−1/3)O(T^{-1/3}) convergence order with Θ(T2/3)\Theta(T^{2/3}) communication rounds. The comparison concerns sufficient round bounds relative to the same method at τ=1\tau=1.

Oracle Assumptions and Component Memory

  • Experimental objectives and theoretical applicability (uXgp, 32HX). Our responses specify the classification losses and function-value oracles, and distinguish their implementation settings from verified theoretical assumptions. We have not established the required uniform query-moment bound for the classification runs; nonlinear multiplicative perturbations also require care regarding conditional centering. In contrast, the directly evaluated synthetic loss in Figure 10 has a uniform second-moment bound of 1/41/4.
  • Assumption presentation (uXgp). Appendix B now refers to Assumption 3 in Section 3.2 instead of repeating it. Its bounded-loss example is explicitly presented as a sufficient condition, rather than verification of the experimental objectives.
  • Memory contribution (joxR). We clarify that Lemma 1 establishes conditional-mean preservation and a bounded second moment, without proving a strict variance or convergence-rate improvement over fresh estimates. Section 5.2 states that the experiments do not isolate the benefit of memory.

Experimental Comparisons and Resource Accounting

  • Query costs (joxR, 32HX). Our responses provide recorded training function evaluations per run, including initialization and refresh costs. We distinguish the analyzed round-reset algorithm from the persistent-memory classification implementation and explain the reported count ranges.
  • Communication at matched quality (joxR, 32HX). Section 5.5 and the Figure 10 caption identify the experiment as a communication–residual comparison at matched local-update budgets. The responses additionally present a descriptive comparison of existing runs at nearby residual levels. Neither comparison establishes the cost of reaching a common prespecified residual threshold.
  • Comparison scope (SuXm, joxR, 32HX). The experimental conclusions are restricted to the evaluated configurations. Native first-order comparisons, matched-query and matched-privacy comparisons, and a separate memory ablation remain unestablished.

Privacy Scope and Finite-Horizon Calibration

  • Privacy–optimization relation (joxR). Appendix E substitutes a target privacy budget into the finite-horizon bound while retaining the clipping-error term. This clarifies how the number of releases affects calibrated noise, without claiming an optimized private convergence rate.
  • Preprocessing boundary (32HX). Section 5.3 explicitly limits the reported guarantee to training conditional on fixed preprocessing and partitioning. Freezing PCA fitted on protected training data does not establish end-to-end raw-data privacy.
  • Figure 10 configuration (32HX). Our responses explicitly confirm that both schedules disable clipping, Gaussian release noise, and query noise, consistent with the nonprivate setting of Corollary 1.

Presentation and Limitations

  • Workflow explanation (SuXm). The revised Figure 1 caption clarifies the round-level interpretation, while the response separates local computation, private release when enabled, neighbor exchange, and edge-state updates.
  • External validity (uXgp). The scope-and-limitations paragraph identifies the fixed connected graph and synchronous-exchange assumptions, together with unevaluated settings involving changing graphs, stragglers, failures, and costly black-box deployment.

We appreciate the reviewers’ time and welcome further questions about the analysis, experimental evidence, and scope of the claims.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.