PaperlayerView exact revision on arXiv

Source-linked AI summary

Federated Zeroth-Order Optimization with Direction Aggregation and Variance Reduction

Qianlong Dang, Baosheng Li

arXiv:2610.11821v1cs.DC

TL;DR

Constrained nonsmooth nonconvex federated optimization is challenging when clients have only stochastic function evaluations and existing methods primarily average local models. The paper proposes FedZOO and FedVRZO, which aggregate local directions before a server projection using two sampling schemes. It establishes convergence guarantees and reports experiments on black-box adversarial attacks.

  • Problem

    The paper addresses constrained nonsmooth nonconvex federated optimization with stochastic function evaluations, where existing methods leave a challenge in analyzing direction aggregation along projected client trajectories before server projection.

    Source: §I · p. 1, A. Related Work · p. 2

  • Method

    FedZOO and FedVRZO average directions evaluated along projected client trajectories and apply one weighted server projection, using shared-minibatch spherical queries or independent sample–direction pairs, respectively.

    Source: C. Main Contributions · p. 2

  • Results

    The paper establishes nonasymptotic bounds on expected squared projected gradient mappings and characterizes communication and function-query complexities; experiments evaluate the methods on black-box adversarial attacks.

    Source: §VI · p. 10

  • Takeaways & Limitations

    The direction-aggregation architecture keeps the server recursion on the shared feasible set while exposing the effects of local drift and stochastic sampling.

    Source: C. Main Contributions · p. 2

Abstract

from arXiv · show

We study constrained nonsmooth nonconvex stochastic optimization in federated settings, where clients access only stochastic function evaluations. Existing federated zeroth-order methods primarily combine local zeroth-order updates with model averaging. However, they struggle with client drift induced by local projected updates and sampling variance in stochastic zeroth-order estimates. In this paper, we propose a federated zeroth-order framework based on direction aggregation, equipped with two local sampling schemes. Specifically, FedZOO constructs a local direction from a minibatch shared across multiple spherical queries, thereby controlling the stochastic errors arising from data sampling and gradient approximation. In contrast, FedVRZO forms its local estimator from independent sample--direction pairs, so that its sampling error is controlled directly by the number of sample--direction pairs. In both algorithms, clients compute the mean of the directions evaluated along their projected local trajectories, and the server performs a single projected update using the weighted aggregate of the client directions. Furthermore, we establish convergence guarantees for FedZOO and FedVRZO, respectively. Experiments on black-box adversarial attacks demonstrate the effectiveness of the proposed methods.

I. INTRODUCTION

The introduction frames constrained nonsmooth nonconvex federated optimization with zeroth-order information and motivates aggregating client directions before a server projection. It presents two direction-aggregation methods and the smoothing and stationarity framework used to study them.

A. Related Work

  • Existing federated zeroth-order methods leave a convergence challenge for aggregating local directions along projected client trajectories before server-side projection.The discussion contrasts this setting with FedZO's terminal model differences and other methods' restricted settings.Source: A. Related Work · p. 2

B. Motivation

  • Terminal client models mix local directions with trajectory displacement and projection effects, while projection and weighted averaging do not commute.This motivates aggregating local directions before the server projection.Source: B. Motivation · p. 2

C. Main Contributions

  • The paper proposes FedZOO and FedVRZO, which aggregate directions evaluated along projected local trajectories before a single weighted server projection.FedZOO uses a shared minibatch across spherical directions, while FedVRZO uses independent sample–direction pairs; the paper also establishes convergence guarantees and reports black-box attack experiments.Source: C. Main Contributions · p. 2

D. Organization

  • The introduction describes the paper's organization: algorithms, convergence and complexity analysis, numerical evaluation, and conclusion.Complete proofs are collected in the appendix.Source: D. Organization · p. 3

A. Spherical Smoothing and Two-Point Estimation

  • Randomized smoothing replaces a nonsmooth objective with a differentiable surrogate whose gradient can be estimated using local function evaluations.The paper describes a two-point estimator using the same sample at the two perturbed points.Source: A. Spherical Smoothing and Two-Point… · p. 3

B. Clarke Stationarity and Projected Gradient Mapping

  • The projected gradient mapping measures constrained stationarity of the smoothed objective, and its zero implies the stated η-Clarke stationarity condition.The η-neighborhood enlarges the Clarke subdifferential; at a boundary, a generalized gradient may be balanced by an outward normal.Source: B. Clarke Stationarity and Projected… · pp. 3–4

III. FEDERATED ZEROTH-ORDER ALGORITHMS

FedZOO and FedVRZO share a direction-aggregation recursion, while FedZOO builds each local direction using one minibatch reused across multiple spherical queries.

III. FEDERATED ZEROTH-ORDER ALGORITHMS

  • The algorithm section presents this shared recursion and the two distinct local sampling schemes as the framework's core design.FedZOO uses minibatch reuse, whereas FedVRZO uses independent sample–direction pairs.Source: §III · p. 4

A. Direction-Aggregation Strategy

  • Clients average K zeroth-order directions evaluated along their projected local trajectories, and the server applies one projection to their weighted aggregate.The local stepsize sets query-point spacing, while the server stepsize scales the aggregate.Source: A. Direction-Aggregation Strategy · p. 4

B. FedZOO

  • FedZOO reuses a minibatch of Bt samples across Qt spherical directions to construct each local estimator.The two-point evaluations for each direction use the same samples; one local direction requires 2BtQt function evaluations.Source: B. FedZOO · p. 4

C. FedVRZO

FedVRZO uses independent sample–direction pairs within the direction-aggregation recursion. Its analysis assumes regular sample functions and conditionally independent sampling, and defines client heterogeneity through differences among smoothed local gradients.

C. FedVRZO

  • FedVRZO forms each local estimate from Nt independent sample–direction pairs, with the same sample used for the positive and negative function evaluations.Its sampling-error second-moment bound scales as 1/Nt, and each local direction requires 2Nt function evaluations.Source: C. FedVRZO · p. 4

IV. CONVERGENCE ANALYSIS

  • The convergence analysis compares FedZOO and FedVRZO sampling errors and properties under common conditions, then considers their sampling efficiency under a fixed function-query budget.The algorithm output is the uniformly randomized server iterate.Source: §IV · p. 5, C. FedVRZO · p. 5

A. Common Conditions

  • The analysis assumes almost-sure local Lipschitz continuity and an integrable sample loss, with the global objective bounded below.It also assumes conditionally independent client sampling and, for FedVRZO, conditionally independent sample–direction pairs.Source: A. Common Conditions · p. 5
  • The analysis measures relevant client heterogeneity by weighted variation among smoothed local gradients, which vanishes when those gradients are identical.The quantity may vary with the smoothing radius.Source: A. Common Conditions · p. 6

B. Auxiliary Results

The auxiliary results provide smoothing regularity, a bound on projected local-trajectory displacement, and a projected descent inequality that separates stationarity decrease from direction error.

B. Auxiliary Results

  • The auxiliary results establish regularity of smoothed objectives, bound projected local-step displacement, and relate an inexact aggregate direction to descent.The local-trajectory bound is one ingredient in the direction-error control used by the convergence analyses.Source: B. Auxiliary Results · p. 6
  • The inexact projected-descent inequality separates decrease associated with projected stationarity from error in the update direction.When the direction equals the smoothed gradient, the error term vanishes and a nonzero projected gradient mapping produces a decrease.Source: B. Auxiliary Results · p. 6
  • The convergence results use a common parameter regime with fixed smoothing radius and server stepsize bounded by the inverse smoothed smoothness constant.The stated local-stepsize condition is automatic when K = 1.Source: B. Auxiliary Results · p. 6

C. Convergence Analysis of FedZOO

FedZOO’s analysis bounds stationarity through an inexact projected server step, accounting for both local-trajectory drift and aggregated sampling error. Its convergence and complexity guarantees depend on controlling those residuals.

C. Convergence Analysis of FedZOO

  • The per-round residual combines gradient discrepancy from local trajectory displacement with aggregated sampling error.The sampling factor separates data-sample and random-direction contributions, and the drift component vanishes when K = 1.Source: C. Convergence Analysis of FedZOO · p. 7
  • The direction-error bound controls the gap between the aggregated client direction and the smoothed global direction used in the projected server step.The resulting error is bounded by twice the per-round residual under the stated conditions.Source: C. Convergence Analysis of FedZOO · p. 7
  • FedZOO’s stationarity analysis bounds the expected squared projected-gradient mapping at a randomized output using the initial descent budget and accumulated residuals.The residuals include local-drift and aggregate-sampling contributions.Source: C. Convergence Analysis of FedZOO · pp. 7–8
  • For expected mapping norm at most ϵ, the stated communication requirements are O(Mϵ^-2) uplink vectors and O(ϵ^-2) server broadcasts.The required number of rounds is at least (2LηΔη + 2R_B,Q)ϵ^-2.Source: C. Convergence Analysis of FedZOO · p. 8

D. Convergence Analysis of FedVRZO

FedVRZO retains FedZOO’s direction-aggregation recursion but uses independent sample–direction pairs. Its analysis bounds stationarity by controlling local drift and sampling error, then gives convergence and complexity guarantees.

D. Convergence Analysis of FedVRZO

  • The direction-error bound controls the difference between the aggregated client direction and the smoothed global direction by the per-round residual.The stated bound is E[∥d_t − h_t∥² | F_t,0] ≤ 2bE_t.Source: D. Convergence Analysis of FedVRZO · p. 8
  • Independent sample–direction pairs produce a single sampling factor n/N_t in both local-drift and aggregate sampling errors.The local query-trajectory displacement remains controlled by ρ_t.Source: D. Convergence Analysis of FedVRZO · p. 8
  • FedVRZO’s stationarity analysis bounds the expected squared projected-gradient mapping using an initial descent term and accumulated residuals.Under the stated parameter choices, the randomized-output mapping norm is at most ϵ after the required number of rounds.Source: D. Convergence Analysis of FedVRZO · pp. 8–9
  • For expected mapping norm at most ϵ, FedVRZO requires O(Mϵ^-2) uplink vectors and O(ϵ^-2) server broadcasts.The stated round threshold is T ≥ (2LηΔη + 2R_N)ϵ^-2.Source: D. Convergence Analysis of FedVRZO · p. 9

E. Sampling Efficiency

At round 300, both proposed methods report lower test attack loss than DZO-SVRG. The section also compares their sampling-error scaling and describes the CIFAR-10 attack setup and the paper’s direction-aggregation contributions.

E. Sampling Efficiency

  • At a fixed local query point, the optimized FedZOO sampling factor decreases as P^-1/2, while FedVRZO’s decreases as P^-1.The comparison concerns sampling error only; the local-trajectory term remains controlled by ρ_t, K, and ζ²_η.Source: E. Sampling Efficiency · p. 9

B. Comparison with Model-Averaging Baselines

  • At round 300, FedVRZO and FedZOO reach test attack losses of 0.639 and 0.654, respectively, versus 0.771 for DZO-SVRG.At round 50, average attack losses are 1.760 for FedZOO, 1.846 for FedVRZO, 3.381 for DZO-SVRG, 7.461 for FedZO, and 12.958 for DZO-SGD.Source: Figure 1 · p. 10, B. Comparison with Model-Averaging… · p. 10

A. Attack Problem and Experimental Protocol

  • The CIFAR-10 experiments measure test-average attack loss over communication rounds for ten source classes, using five clients and five-seed averages.Each run uses 300 rounds; all clients participate, and the proposed methods use K = 3 with (B, Q) = (32, 5) for FedZOO and N = 160 for FedVRZO.Source: A. Attack Problem and Experimental… · p. 9, Figure 1 · p. 10

VI. CONCLUSION

  • The paper proposes FedZOO and FedVRZO, establishes nonasymptotic bounds on expected squared projected-gradient mapping, and characterizes communication and function-query complexities.Both methods aggregate directions evaluated along projected local query trajectories and perform one weighted server projection.Source: §VI · p. 10

APPENDIX I PROOFS OF AUXILIARY RESULTS

The appendix establishes regularity for ball-smoothed objectives and proves bounds on local-trajectory drift and projected descent. These auxiliary results support the convergence analysis for federated updates.

APPENDIX I PROOFS OF AUXILIARY RESULTS

  • Ball smoothing yields continuously differentiable local objectives on neighborhoods of feasible points while preserving Lipschitz bounds.The proof applies uniform-ball smoothing to locally Lipschitz objectives.Source: Appendix I · pp. 10–11
  • For multiple local steps, the proof bounds trajectory displacement using projection nonexpansivity and a discrete Gronwall argument.When K = 1, the displacement terms in the cited bounds are zero.Source: Appendix I · p. 11
  • The projected-descent argument treats the aggregated direction as inexact and bounds its error using the local drift estimate.The proof combines the descent inequality with the direction-error bound to obtain a one-round relation.Source: Appendix I · p. 12

APPENDIX II PROOFS FOR FEDZOO

The FedZOO appendix bounds the local estimator and aggregate errors, then uses these bounds in the projected-descent proof. It also derives convergence and function-query bounds.

APPENDIX II PROOFS FOR FEDZOO

  • FedZOO's direction-estimation error is conditionally controlled through its mean and second-moment bounds.The estimator averages spherical-direction samples formed using a shared minibatch.Source: APPENDIX II PROOFS FOR FEDZOO · p. 12
  • Conditional orthogonality across clients and local steps reduces the aggregate sampling-error second moment to individual contributions.The proof uses centered increments and the tower property.Source: APPENDIX II PROOFS FOR FEDZOO · pp. 12–13
  • The estimator and drift bounds feed the projected-descent proof, which yields convergence and function-query complexity guarantees.The appendix derives the theorem bound and then establishes query bounds for attaining an ϵ-level criterion.Source: APPENDIX II PROOFS FOR FEDZOO · pp. 13–14

APPENDIX III PROOFS FOR FEDVRZO

The FedVRZO appendix bounds errors from independent sample–direction pairs and their aggregate, then applies these bounds in projected descent. It derives convergence and query-complexity guarantees.

APPENDIX III PROOFS FOR FEDVRZO

  • FedVRZO's local estimator uses independent sample–direction pairs, with a conditional second-moment error bound scaled by 1/Nt.The proof identifies the estimate associated with each pair and uses conditional independence to eliminate cross terms.Source: APPENDIX III PROOFS FOR FEDVRZO · p. 14
  • Conditional orthogonality across clients and local steps reduces the aggregate error bound to a sum of individual second moments.The aggregate errors are conditionally centered.Source: APPENDIX III PROOFS FOR FEDVRZO · p. 14
  • The local error and drift bounds enter projected descent, yielding convergence and function-query complexity guarantees for FedVRZO.The appendix derives the theorem bound and query bounds for attaining an ϵ-level criterion.Source: APPENDIX III PROOFS FOR FEDVRZO · p. 15
Loading 2610.11821v1…