PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Gradient Heterogeneity Dynamics of Adversarially Robust Federated Regression

Leonardo F. Toso, James Anderson, Nirupam Gupta, Rafael Pinot

arXiv:2609.25705v1stat.MLcs.LG

TL;DR

Prior analyses impose gradient-dissimilarity bounds a priori, while honest clients may have different models and adversarial clients may send arbitrary updates. This paper derives heterogeneity bounds from linear and nonlinear regression with fresh samples; for κ = O(f/n) and f/n < 1/2, convergence holds after a sample burn-in. The guarantees apply to fresh-batch regression, while reusing a fixed local dataset remains future work.

  • Problem

    Prior analyses impose gradient-dissimilarity bounds a priori, without interpreting them through client models, sample size, or label noise, despite heterogeneity among honest clients and arbitrary adversarial updates.

    Source: §1 · p. 1, §2.2 · p. 5

  • Method

    The paper derives honest-gradient heterogeneity for linear and nonlinear regression with fresh client batches, separating model-parameter heterogeneity, finite-sample error, and initialization.

    Source: §1 · p. 2, §2 · p. 3, §4 · p. 10

  • Results

    For κ = O(f/n) and f/n < 1/2, convergence holds after a sufficient fresh-batch burn-in, with statistical error decreasing as 1/τ.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The analysis replaces the prior restriction on κ with an explicit sample burn-in condition for non-asymptotic convergence and recovery guarantees.

    Source: §6 · p. 12

    The analysis assumes fresh samples each round; extending it to reused fixed local datasets and their dependence on iterates is future work.

    Source: §6 · pp. 12–13

Abstract

from arXiv · show

Federated learning (FL) is intrinsically heterogeneous: honest clients may have different data-generating models. On top of that, adversarial clients can make heterogeneity even more pronounced by sharing arbitrary updates. Existing analyses typically control the interaction between statistical heterogeneity and adversarial behavior through gradient-dissimilarity conditions. However, the underlying bound is imposed a priori and may yield conservative guarantees even for least-squares regression. We instead derive the gradient heterogeneity from the statistical model of linear and nonlinear regression with fresh data samples at every round. Our bounds separate heterogeneity among the honest clients' ground-truth model parameters, finite-sample label noise, and initialization. We then demonstrate that, for any $(f,κ)$-robust aggregator with coefficient $κ= O(f/n)$, where $f$ is the number of adversarial clients and $n$ the total number of clients (with $f/n < 1/2$), convergence holds after an explicit sample burn-in.

1 Introduction

The paper derives honest-gradient heterogeneity from regression models rather than imposing it a priori, and shows that sufficiently large fresh batches yield convergence for robust aggregation with κ = O(f/n) and f/n < 1/2.

1 Introduction

  • Prior gradient-dissimilarity analyses impose heterogeneity bounds a priori, without interpreting them through client models, sample size, or label noise.The paper notes that prior guarantees can be conservative even for regression.Source: §1 · pp. 1–2
  • For κ = O(f/n) and f/n < 1/2, convergence holds after a sufficient fresh-batch burn-in, with statistical error decreasing as 1/τ.The guarantees are non-asymptotic and include problem-dimension, logarithmic, and conditioning factors in the statistical-error bound.Source: §1 · p. 2

1.1 Contributions

  • For linear and nonlinear regression, the heterogeneity bound separates honest clients’ model-parameter differences, finite-sample error, and an initialization-dependent term.For linear regression, covariance concentration couples optimization error to gradient heterogeneity, with coefficient decreasing as 1/τ.Source: §1.1 · p. 2, §1 · p. 2
  • The sample burn-in replaces the prior restriction κB² < 1; removing that restriction requires more samples per client.The paper also gives non-asymptotic parameter-recovery bounds capturing heterogeneity, sample size, initialization, and robust aggregation.Source: §1.1 · pp. 2–3

2 Problem Formulation

The formulation studies synchronous robust federated regression with fresh client batches and an unknown honest-client set. Its analysis connects aggregation guarantees to regression-derived gradient heterogeneity.

2 Problem Formulation

  • Honest clients draw fresh batches of τ samples independently across clients and iterations, so each update’s samples remain independent conditional on the current iterate.The objective is the population loss averaged over honest clients, whose identities are unknown to the server.Source: §2 · pp. 3–4
  • The model assumes isotropic data; nonlinear regression additionally assumes a common covariate marginal across honest clients.Isotropy isolates heterogeneity in clients’ ground-truth parameters rather than covariate conditioning.Source: §2 · p. 4

2.1 Adversarially Robust FL

  • The server uses an (f, κ)-robust aggregator, whose deterministic guarantee does not restrict how adversarial clients choose their updates.The coefficient κ measures the aggregation error’s response to deviations among honest inputs.Source: §2.1 · p. 4
  • Krum, coordinate-wise trimmed mean, and geometric median are examples; nearest-neighbor mixing gives κ = O(f/n), which is information-theoretically optimal.The formulation retains the condition f < n/2 for the existence of such robust aggregators.Source: §2 · p. 3, §2.1 · p. 5

2.2 The Role of Gradient Heterogeneity

  • Gradient heterogeneity matters because ergodic convergence bounds multiply its iteration average by the aggregator’s robustness coefficient κ.Thus, the structure of this quantity directly enters the optimization analysis.Source: §2.2 · p. 5
  • Uniform G-dissimilarity can fail for least-squares regression when clients have different data-generating distributions, even without adversaries.The cited analysis explains that heterogeneity grows as the iterate moves away from clients’ distinct model optima.Source: §2.2 · p. 5
  • The paper characterizes regression gradient heterogeneity from first principles; for linear regression, B² = O(1/τ), making the prior κB² < 1 condition controllable through sample size.The analysis first uses an exact decomposition of honest gradients to expose the sources of the error terms.Source: §2.2 · pp. 5–6

3 Linear Regression

The linear-regression analysis decomposes gradient heterogeneity into honest-client model differences and finite-sample effects, then uses that bound to establish convergence after a sample burn-in. The resulting error separates persistent model heterogeneity from statistical and initialization terms.

Linear Regression

  • The linear analysis controls empirical gradient heterogeneity, inserts that control into a descent recursion, and translates approximate stationarity into parameter-recovery error.The proof sketch uses matrix Bernstein concentration for covariance and sub-Gaussian Hoeffding concentration for noise.Source: §3 · pp. 6–7

Gradient Heterogeneity

  • The gradient-heterogeneity bound separates honest-client model heterogeneity and label noise from an iterate-dependent term scaled by ω² = O(1/τ).Increasing τ makes the term later multiplied by κ small enough to absorb in the convergence argument.Source: §3 · p. 7

Convergence Bound

  • For any fixed κ, a sufficiently large fresh-batch burn-in removes the need for a fixed upper bound such as κB² < 1.The remaining error comprises model-parameter heterogeneity, a statistical term that decreases with τ, and an initialization term that vanishes with T.Source: §3 · p. 8

Key Takeaway

  • The averaged recovery error has a transient initialization contribution, an irreducible model-heterogeneity contribution, and a statistical contribution that decreases as 1/τ up to logarithmic factors.Robust aggregation amplifies the two non-transient contributions through κ.Source: §3 · p. 8

Convergence Bound

  • The burn-in condition makes every fixed κ admissible; for aggregators with κ = O(f/n), the adversarial contribution has linear dependence on the adversarial fraction, with f < n/2 required for such robust aggregation.The analysis also gives a parameter-recovery error bound under isotropic data.Source: §3 · p. 8

4 Nonlinear Regression

The nonlinear analysis extends the heterogeneity bound to function space under regularity assumptions, replacing covariance concentration with residual-Jacobian process concentration. Its convergence guarantee retains the linear setting’s burn-in conclusion and separates function heterogeneity, sampling error, and initialization.

Nonlinear Regression

  • The nonlinear analysis replaces linear model-parameter heterogeneity with heterogeneity among honest clients’ ground-truth functions.The bound also replaces covariance concentration with concentration of the residual-Jacobian process.Source: §4 · pp. 8–10
  • The analysis assumes a common marginal covariate distribution across honest clients, so client heterogeneity enters through their ground-truth functions.Its regularity conditions include a bounded Jacobian, sub-Gaussian residuals, a Lipschitz loss gradient, and the PL condition.Source: §4 · pp. 9–10

Gradient Heterogeneity

  • The nonlinear heterogeneity bound separates ground-truth function heterogeneity, label noise, empirical-process concentration of order 1/τ, and initialization-dependent error.The function-heterogeneity contribution persists with infinite data, while the iterate-dependent coefficient can be made small for fixed κ through τ ≥ τburn-in.Source: §4 · p. 10

Convergence Bound

  • For any fixed κ = O(f/n) with f/n < 1/2, a sufficiently large fresh batch removes the need for the additional κ upper bound required in [AGG+23].The remaining terms include honest-client function heterogeneity and label noise, with the latter decreasing as τ grows.Source: §4 · p. 11

Parameter Recovery Error

  • Under the nonlinear recovery bound, Γnonlin is unavoidable because one global parameter cannot simultaneously characterize heterogeneous ground-truth functions.For fixed κ, homogeneous client functions and increasing τ yield vanishing averaged prediction error at the optimization rate.Source: §4 · p. 11
  • Across the linear and nonlinear results, honest-client model heterogeneity determines the irreducible bias, while increasing τ and T reduces finite-sample and initialization-dependent contributions, respectively.The nonlinear recovery guarantee translates approximate stationarity into recovery of the honest client functions.Source: §4 · p. 11

5 Related Work

Prior work studies heterogeneous federated optimization and Byzantine-robust aggregation, often using bounded gradient or dissimilarity assumptions. This paper instead derives gradient heterogeneity from regression models, sample size, and noise distribution.

FL under heterogeneity

  • Prior federated-optimization methods address client drift from differing local objectives, while much of their analysis uses bounded-gradient assumptions and focuses on settings without Byzantine behavior.FedProx uses a proximal local objective, while SCAFFOLD uses control variates to correct bias from heterogeneous local updates.Source: §5 · p. 11

Gradient dissimilarity

  • The paper’s focus is complementary: it studies how empirical gradient heterogeneity evolves under a statistical regression model and propagates through robust guarantees.Rather than assuming fixed G and B constants, it derives heterogeneity from the regression model, sample size, and noise distribution.Source: §5 · p. 12

Byzantine-robust distributed learning

  • Robust aggregators differ computationally and statistically, but their convergence analyses control aggregate deviation from the honest-client mean update.Nearest neighbor mixing can preprocess aggregators to achieve κ = O(f/n).Source: §5 · p. 12

Gradient dissimilarity

  • For linear and nonlinear regression, the irreducible bias is ordered by pairwise honest-client model or function heterogeneity, while the multiplicative coefficient scales inversely with τ.This yields an explicit sample-size burn-in instead of the fixed κB² < 1 condition required in [AGG+23].Source: §5 · p. 12

6 Conclusions and Future Work

The paper derives gradient heterogeneity from regression data models and obtains non-asymptotic convergence and recovery bounds with an explicit sample burn-in. For linear regression, it also analyzes parameter recovery, ergodic convergence, and robust-aggregation conditions.

6 Conclusions and Future Work

  • For linear and nonlinear regression, the derived heterogeneity bound separates client-model differences, finite-sample noise, and initialization, replacing a prior aggregation-coefficient restriction with an explicit sample burn-in.The resulting bounds are non-asymptotic convergence and recovery guarantees.Source: §6 · p. 12
  • The stated future directions include analyzing reused local data while controlling dependence between iterates and samples.The conclusion also identifies local updates, partial client participation, and time-varying adversarial sets as extensions that would bring the theory closer to practical federated systems.Source: §6 · pp. 12–13

B Linear Regression

  • The linear-regression analysis combines a first-principles per-iteration heterogeneity bound with an optimization-error recursion to establish parameter-recovery and ergodic-convergence guarantees.It also compares the resulting conditions on κ with those in [AGG+23].Source: B Linear Regression · p. 16

B.1 Regression Model and Gradients

  • With heterogeneous client parameters, covariance-deviation terms can grow as iterates move away from the optimum, preventing a finite uniform G bound over all iterates.This is described as consistent with the limitation discussed in [AGG+23].Source: §B.1 · p. 17

B.5 Gradient Heterogeneity Decomposition

The section derives a per-iteration gradient-heterogeneity bound under isotropic data, decomposing the gradient difference into model, covariance-concentration, and cross terms.

B.5 Gradient Heterogeneity Decomposition

  • The derivation subtracts the honest-average gradient from each client gradient and uses the isotropic-data assumption.The resulting terms are bounded using norms and the triangle inequality.Source: §B.5 · pp. 19–20
  • The bound separates model heterogeneity from covariance-concentration terms for each client and a cross term.The displayed decomposition is followed by a per-iteration heterogeneity bound.Source: §B.5 · pp. 20–21
  • Under the burn-in condition, the derivation invokes covariance concentration and absorbs the associated concentration and cross terms.The passage also notes that the heterogeneity bound includes an iterate-dependent term.Source: §B.5 · p. 20

B.6 Optimization Error Recursion

The section connects the honest-average fresh-batch gradient to the population gradient and bounds the resulting optimization error using robustness and concentration arguments.

B.6 Optimization Error Recursion

  • The recursion combines parameter-error and variance-decomposition arguments with bounds on the honest-average gradient error.Under the burn-in condition, a second term is dominated by the first before the bounds are combined.Source: §B.6 · pp. 21, 23
  • The analysis defines the honest-average gradient error as the difference between the fresh-batch gradient and the population gradient.It then bounds that error using the stated robustness property.Source: §B.6 · p. 21
  • The fresh-sample assumption makes the per-round sample matrices conditionally independent given the current iterate, while isotropy supplies an additional concentration property.The proof uses these properties in its concentration argument.Source: §B.6 · p. 22

B.7 Convergence Analysis

The section establishes a high-probability convergence bound under the stated model assumptions, step-size condition, and sample burn-in.

B.7 Convergence Analysis

  • The convergence theorem assumes Assumptions 2.1 and 3.1, a step size η ≤ 1/2, and the burn-in condition, and states its guarantee with probability at least 1 − δ.The supplied theorem passage does not include the bound's expression.Source: §B.7 · p. 23
  • The proof sums the per-iteration recursion across rounds and uses optimality of θ⋆ before applying the preceding bound.It then controls the resulting coefficient using the burn-in condition so the term can be absorbed.Source: §B.7 · pp. 23–24

B.8 Non-Asymptotic Parameter Recovery Error Bound

The section relates parameter recovery to prediction error under isotropy, then extends the analysis to nonlinear regression by bounding gradient heterogeneity and deriving concentration-based guarantees.

B.8 Non-Asymptotic Parameter Recovery Error Bound

  • Under data isotropy, parameter error and prediction error coincide.The linear parameter-recovery corollary states a high-probability bound under Theorem B.1's conditions.Source: §B.8 · p. 24

C Nonlinear Regression

  • The nonlinear analysis derives non-asymptotic convergence and function-recovery guarantees using a function-space gradient decomposition and an optimization-error recursion.It accounts for nonlinear parameterization through regularity and concentration conditions.Source: C Nonlinear Regression · p. 25

C.1 Regression Model and Gradients

  • The nonlinear model uses a parameterized function with bounded inputs and noise satisfying Assumption 3.1.At each iteration, the empirical loss is defined using fresh samples.Source: §C.1 · p. 25

C.2 Gradient Heterogeneity Decomposition

  • The section defines each client's noise term and its honest-client average for the heterogeneity decomposition.The supplied passage does not state the decomposition formula.Source: §C.2 · p. 25

C.3 Concentration Inequalities for Nonlinear Regression

  • Fresh samples are independent of the current iterate conditionally, enabling concentration bounds to hold simultaneously across honest clients and rounds with high probability.The cited concentration results apply under the stated assumptions.Source: §C.3 · p. 26

C.4 Per-iteration Gradient Heterogeneity Bound

  • The per-iteration bound separates a model-heterogeneity term from remaining terms controlled using concentration inequalities.The proof combines the resulting bounds and averages over honest clients.Source: §C.4 · pp. 26–27

C.5 Bound on GT and Convergence Analysis

The nonlinear convergence analysis combines an averaged heterogeneity bound with an optimization-error argument under stated assumptions, a step-size condition, and a fresh-sample condition.

C.5 Bound on GT and Convergence Analysis

  • The analysis assumes conditionally mean-zero noise and evaluates losses at client optima when bounding average functional error.The honest-average population-loss minimizer is used in this comparison.Source: §C.5 · p. 28
  • The convergence theorem assumes the stated regularity conditions, η ≤ 1/L′, and a lower bound on fresh samples per client.The sample-size threshold is specified in the theorem's condition.Source: §C.5 · p. 28
  • The proof combines the averaged per-iteration bound with the convergence argument, and the sample-size condition controls factors involving ω².The proof absorbs the resulting numerical factor into its bound.Source: §C.5 · p. 29

C.6 Non-Asymptotic Function Recovery Error Bound

The section derives a nonlinear parameter-recovery guarantee from the convergence bound by controlling average functional error and applying the PL condition.

C.6 Non-Asymptotic Function Recovery Error Bound

  • Corollary C.1 gives a parameter-recovery bound with probability at least 1 − δ under Theorem C.1's conditions.The supplied passage does not include the bound's expression.Source: §C.6 · p. 29
  • The derivation controls average functional error using evaluations at client optima and the PL condition, then averages across iterations.It uses that θ⋆ minimizes the honest-average population loss.Source: §C.6 · p. 30
  • The recovery result follows by substituting the QT bound from Theorem C.1.The proof then absorbs numerical constants.Source: §C.6 · p. 30

Related papers

Loading 2609.25705v1…