PaperlayerView exact revision on arXiv

Source-linked AI summary

A Large-Dimensional Analysis of Least-Squares Federated Learning via Generalized Total Variation Minimization

Ekkehard Schnoor, Malik Tiomoko, Alexander Jung

arXiv:2610.20075v1cs.LGstat.ML

TL;DR

Federated least-squares learning must balance noise suppression through collaboration against mismatch across heterogeneous nodes. The paper analyzes GTVMin using random-matrix methods, showing concentration and deriving asymptotically precise node-level test errors. It validates the predictions on synthetic and real-world data.

  • Problem

    In heterogeneous federated learning, collaboration can reduce local finite-sample noise while introducing bias between nodes, making the regularization trade-off consequential.

    Source: §1 · p. 1

  • Method

    The paper analyzes least-squares GTVMin in the high-dimensional regime using concentration and deterministic equivalents from random matrix theory.

    Source: §1 · p. 1, §2.1 · p. 2

  • Results

    Lipschitz observations of the GTVMin solution concentrate independently of collaboration strength and graph structure, and the paper derives asymptotically precise node-level test errors for homogeneous and heterogeneous Gaussian data.

    Source: §1 · p. 1

  • Takeaways & Limitations

    The predictions are validated on synthetic data and 55 real-data settings, and the theory is used to tune α from training data.

    Source: §1 · p. 1

    The asymptotic analysis assumes a fixed number of nodes and graph, with p and local sample sizes growing proportionally.

    Source: §2.3 · p. 3

Abstract

from arXiv · show

Federated learning over decentralized networks inherently trades off the suppression of local finite-sample noise through collaboration against the bias that collaboration introduces between heterogeneous nodes. We study this tension by performing a large-dimensional analysis of Generalized Total Variation Minimization with least-squares models. Using tools from random matrix theory, we show that Lipschitz observations of the global GTVMin solution concentrate in large dimensions, universally for any underlying network structure. We provide exact analytic expressions for the asymptotically precise performance under both i.i.d. and non-i.i.d. Gaussian mixture distributions on a fixed network. For the latter, these expressions quantify how regularization balances local adaptation against collaboration. Our theoretical results are confirmed by experiments on synthetic and real-world data.

1 Introduction

Federated learning must balance noise reduction through collaboration against model mismatch across heterogeneous nodes. This paper analyzes that trade-off for least-squares GTVMin, deriving concentration and test-error results and validating predictions on synthetic and real-world data.

1 Introduction

  • Heterogeneous nodes create a trade-off: collaboration can suppress finite-sample noise but pull local models toward a shared solution that is not optimal for each node.The paper studies how regularization balances collaboration and personalization.Source: §1 · p. 1
  • The analysis addresses how least-squares generalization error depends on regularization, graph structure, and differences between local data distributions in high dimensions.The setting has feature dimension p and local sample sizes n_i growing proportionally, with a fixed number of nodes.Source: §1 · p. 1
  • Lipschitz observations of the GTVMin solution concentrate independently of collaboration strength and graph structure, including for growing networks.The contribution is stated for arbitrary underlying network structures.Source: §1 · p. 1
  • The paper derives asymptotically precise node-level test errors for both homogeneous and heterogeneous Gaussian data.Source: §1 · p. 1
  • The predictions are validated on synthetic data and 55 real-data settings, and the theory is used to tune α from training data.Source: §1 · p. 1
  • Unlike prior distributed least-squares and federated-estimator analyses described here, this work treats arbitrary communication graphs and a continuum of collaboration strengths.Under suitable symmetry, graph dependence enters through node-resolved resolvent blocks and the Laplacian spectrum.Source: §1 · p. 2

2 Setup and Assumptions

The setup models node-specific least-squares fits coupled by a graph-Laplacian penalty. Its regularization ranges from independent local models to consensus, while the analysis assumes proportional high-dimensional scaling and Gaussian-mixture data.

2.1 Generalized Total Variation

  • Each node fits a local linear model, and the objective combines local losses with a generalized total-variation penalty on neighboring parameter differences.Edge weights encode assumed statistical similarity between nodes.Source: §2.1 · p. 2

2.2 The i.i.d. and non-i.i.d. regimes

  • The coupling strength α ranges from independent local regressions at α = 0 to consensus on a connected graph as α →∞; intermediate values yield personalized models.For unequal sample sizes, the consensus limit minimizes the equally weighted sum of node losses; with equal sample sizes it is pooled least squares.Source: §2.1 · p. 3, §2.2 · p. 3
  • With homogeneous data, collaboration adds no population-model mismatch and the asymptotic optimum is α →∞, recovering pooled least squares under equal sample sizes and a connected graph.Source: §2.2 · p. 3
  • With heterogeneous data, consensus need not be optimal because collaboration can pull each model toward an incorrect shared solution; the optimal α balances collaboration and personalization.The analysis does not assume that this optimum is interior or unique.Source: §2.2 · p. 3

2.3 Data Model and Assumptions

  • The data model uses independent Gaussian-mixture training observations and evaluates each node’s classifier on an independent test observation.The high-dimensional assumptions keep the number of nodes and graph fixed while p and local sample sizes grow proportionally, with bounded means and covariances bounded above and below.Source: §2.3 · pp. 3–4

3 Theoretical Main Results

The section establishes concentration for Lipschitz observables of the GTVMin solution, then develops deterministic approximations to test error for homogeneous and heterogeneous data. The formulas characterize how graph structure and collaboration enter these errors, including a nonnegative correction for local-model mismatch in the heterogeneous case.

3.1 Concentration of the GTVMin Solution

  • Lipschitz observables of the GTVMin solution concentrate around their conditional means at scale 1/√nmin, uniformly over collaboration strength and graph structure.In the proportional regime this is 1/√p; the result allows growing networks and arbitrary edge weights without degree or largest-eigenvalue bounds.Source: §3.1 · p. 4

3.2 Preparations

  • The fixed-point system has a unique positive solution when ci < 1, and iteration from zero converges to it.The resulting fixed point determines the matrices used in the test-error formulas.Source: §3.2 · p. 4, §3.3 · p. 5

3.3 Test Error: Homogeneous Case

  • In homogeneous data, collaboration affects asymptotic test error only through the variance correction vi.The parameter γ measures class separation and is independent of α.Source: §3.3 · p. 5
  • For symmetric graphs such as uniformly weighted cycles and complete graphs, all nodes have the same predicted error, and the graph enters through its Laplacian eigenvalues.The local and pooled endpoints have simple expressions; for disconnected graphs, the pooled expression uses the node’s connected-component size.Source: §3.3 · p. 5

3.4 Test Error: Heterogeneous Case

  • For heterogeneous data, each node’s test error is asymptotically approximated by Ei, with the difference vanishing in probability and mean.The denominator in the error expression remains bounded below by a positive constant for every α.Source: §3.4 · p. 6
  • The heterogeneous residual separates minimum local squared prediction error from additional error due to m(i) differing from w(i).The nonnegative vi correction accounts for training-sample fluctuations in the quadratic term.Source: §3.4 · pp. 5–6
  • Local-model mismatch adds a nonnegative quadratic correction; for α > 0, m = w∗ exactly when local least-squares coefficients agree within each connected component.The distributions themselves may still differ when those coefficients agree.Source: §3.4 · p. 6

4 Experiments

The experiments test the theory on Gaussian and real-world data, while appendices establish the Gaussian decomposition, fixed-point stability, and deterministic equivalents used in the analysis.

4.1 Gaussian Data

  • Theoretical predictions closely match measured test errors on three graph structures, while Lipschitz-observable fluctuations confirm the predicted p^-1/2 scale.Collaboration moves homogeneous error toward the pooled error, with the graph determining the rate.Source: §4.1 · p. 7
  • In heterogeneous data, error has an intermediate best collaboration strength; beyond it, signal loss can precede rising quadratic noise, which stronger collaboration eventually also increases.The prediction is illustrated for a heterogeneous three-node path, with Theorem 4 curves and 240 training draws.Source: §4.1 · p. 7, Figure 2 · p. 7
  • Graphs with identical Laplacian spectra have different test errors, and grouping similar tasks makes stronger collaboration useful.Theorem 4 captures both error curves and their preferred collaboration strengths.Source: §4.1 · p. 7, Figure 3 · p. 8

4.2 Real-World Data

  • Predictions remain useful approximations across 55 real-data settings, although prediction gaps tend to grow as data depart from Gaussianity.The settings span five datasets and random, controlled-shift, and natural user or silo partitions; real-data classification scores need not be Gaussian.Source: §4.2 · p. 7, Figure 4 · p. 7
  • Choosing α by minimizing predicted error usually approaches the best grid error, and training-moment plug-in tuning performs similarly to cross-validation.Useful collaboration depends on node differences: task-structured graphs perform well on heterogeneous benchmarks, while consensus is best on nearly homogeneous Adult.Source: §4.2 · p. 8, Table 1 · p. 8, Table 2 · p. 8

A Gaussian Decomposition and Spectral Bounds

  • The Gaussian proof decomposes sample-mean fluctuations from centered covariances: the means are independent of all centered covariances, and nodes are independent.An orthogonal transformation of sample indices separates the sample mean from the centered Gaussian columns.Source: A Gaussian Decomposition and Spectral… · p. 11

B.1 Existence and stability

  • The fixed-point iteration from zero converges to a unique positive solution when each c_i < 1, bounded above by c_i/(1 − c_i).Stability bounds support implicit differentiation under bounded smooth variations.Source: §B.1 · pp. 11–12

B.2 Deterministic equivalents

  • The deterministic equivalent T approximates the inverse in bounded-vector bilinear forms and normalized traces with bounded deterministic test matrices, with scalar differences vanishing in probability.A separate deterministic equivalent addresses quadratic terms.Source: §B.2 · p. 12

C Test Error: Heterogeneous and Homogeneous Cases

The test-error analysis derives heterogeneous and homogeneous-case formulas from deterministic approximations, then establishes concentration of Lipschitz observables of the fitted solution.

C.1 Heterogeneous case

  • The heterogeneous-case derivation expresses the fitted-coefficient approximation through q and m = TUq, then uses deterministic equivalents for linear and quadratic forms.The resulting test-error formulas remain valid for unequal sample sizes.Source: §C.1 · pp. 13–14
  • For heterogeneous nodes, the variance decomposition yields a nonnegative heterogeneity term, which is positive when local coefficients disagree within a connected component.The term is zero exactly when local coefficients agree within every connected component.Source: §C.1 · p. 14

C.2 Homogeneous case

  • When means, covariances, and sample sizes are identical across nodes, the homogeneous solution has w* = Σ^-1µ/(1 + γ), and substitution yields the stated test-error formulas.The graph Laplacian annihilates constant node vectors in this case.Source: §C.2 · p. 14

D Observable Concentration

  • Lipschitz observables of the GTVMin solution concentrate with Gaussian tails uniformly over α, the graph, and N under the stated data bound.The separate concentration result permits growing N and uses an upper data bound not needed for test-error derivation.Source: D Observable Concentration · pp. 14–15

E Real-World Experiments

This appendix gives details of the main paper’s Section 4.2 real-world experiments.

E Real-World Experiments

  • The appendix supplies implementation details for the real-world experiments in Section 4.2.It identifies the code as supplementary material.Source: E Real-World Experiments · p. 15
  • The supplementary code includes downloading the five datasets used in the experiments.The passage identifies dataset download as part of the provided code.Source: E Real-World Experiments · p. 15
  • The appendix directs readers to supplementary code for reproducing the experimental setup.The passage states that the code is provided as supplementary material.Source: E Real-World Experiments · p. 15

E.1 Protocol

The protocol estimates signed-observation moments from each node’s data pool, then compares theory predictions with held-out classification errors over shared α grids.

E.1 Protocol

  • Each node’s data are randomly split into a 70% pool and a 30% held-out test set, with features standardized using pooled-data statistics.The standardization uses the union of all nodes’ pools.Source: §E.1 · p. 15
  • Pool signed-observation moments, sample sizes, and the graph Laplacian supply Theorem 4’s prediction for each setting.Signed observations are z = yx.Source: §E.1 · p. 15
  • For each setting, 100 training draws are sampled with replacement from node pools, and predicted Gaussian-formula errors are compared with held-out 0/1 errors.The draws are shared across the α grid, and each pool is treated as the theory’s population.Source: §E.1 · p. 15

E.2 Datasets, partitions and graphs

The 55 real-data settings use several datasets and partition schemes, with graph structures ranging from standard graphs to k-nearest-neighbor graphs built from node statistics.

E.2 Datasets, partitions and graphs

  • Image and Adult features are reduced by PCA, while CIFAR-10 uses random convolutional features before PCA; no pretrained network is used.Adult’s silo-defining attribute is removed, and classes are balanced within each silo.Source: §E.2 · p. 15
  • Rotation settings vary node features, while alignment settings assign different tasks to nodes 1–3 and 4–6.Dirichlet settings vary each node’s proportions of original classes within binary-task groups; a ranges from 0.1 to 100.Source: §E.2 · pp. 15–16
  • The graph choices include paths, cycles, complete graphs, and k-nearest-neighbor graphs built from node-level pool statistics.For k-nearest-neighbor graphs, node statistics comprise the mean of signed observations and the mean of their squared coordinates.Source: §E.2 · p. 16
  • The paper reports 55 real-data settings, with tasks expressed as positive versus negative class; unless otherwise stated, settings use N = 6, p = 100, and n_i = 250.Source: Table 3 · p. 16

E.3 Choice of α and baselines

The section compares rules for selecting α, including cross-validation and theory-based criteria, against fixed or hindsight baselines. Table 4 reports test errors with confidence intervals over 20 training draws.

E.3 Choice of α and baselines

  • The cross-validation rule selects α by five-fold cross-validation of node-averaged 0/1 training error.Source: §E.3 · p. 16
  • Plug-in theory selects α by minimizing Theorem 4’s prediction using training-sample means and Ledoit–Wolf covariance estimates.Source: §E.3 · p. 16
  • Oracle theory uses the same prediction criterion with pool moments, while consensus fixes α = 10^4.Source: §E.3 · p. 16
  • Fine-tuning regularizes each local model toward the consensus model, with λ chosen by five-fold cross-validation.Source: §E.3 · p. 16
  • The hindsight baseline selects the lowest test error over the α grid for each draw, and all selection rules use the same grid.Source: §E.3 · pp. 16–17
  • Table 4 reports test error (%) with 95% confidence intervals over 20 training draws.The table reports the results of Table 2.Source: Table 4 · p. 17

E.4 Where the gap comes from

On Fashion-MNIST, replacing real data with Gaussian samples matched in mean and covariance nearly closes the prediction gap. Additional figures illustrate how error varies with collaboration and graph-task alignment.

E.4 Where the gap comes from

  • At α = 0.05, Gaussian samples with matched moments yield 16.50% error against a 16.54% prediction, versus 20.4% against 20.5% for real-data replacement at α = 0.At α = 0, the real-data error is 23.2% against a 20.7% prediction.Source: §E.4 · p. 17
  • The whitened squared-norm spread is 0.80 on real data and 0.14 on Gaussian samples; the prediction gap is largest at α = 0 and small near consensus.Fixed-norm normalization does not reduce the gap, and the heteroscedastic noise-term replacement reduces it only slightly.Source: §E.4 · p. 17

E.5 Additional figures

  • In random splits across path, cycle, and complete graphs, error decreases toward the pooled-model error.Source: Figure 5 · p. 17
  • On MNIST with rotation shift, the best α is intermediate, and full collaboration performs worse than local training.Source: Figure 6 · p. 18

E.6 All settings

The section defines the metrics reported across all 55 real-data settings and includes additional figures on graph-task alignment, natural partitions, and prediction variability.

E.6 All settings

  • The table’s |∆|G and |∆|T columns give the largest gridwise prediction differences from the Gaussian formula and held-out test error, in percentage points.Source: §E.6 · p. 18
  • The α_de and α⋆_test columns report the theory-selected α and the α with lowest mean test error; local, consensus, and best columns report test errors at α = 0, α = 10, and α⋆_test.Source: §E.6 · p. 18
  • NC is the non-Gaussianity index and equals 1 for Gaussian data.Source: §E.6 · p. 18
  • Table 6 reports results for all 55 real-data settings.Source: Table 6 · p. 19
  • In real-data alignment examples, the grouped cycle has lower error than the cycle with more edges between different tasks.The two cycles have the same Laplacian spectrum and use the same training draws.Source: Figure 7 · p. 20
  • The natural-partition figure compares complete graphs with k-nearest-neighbor graphs for HAR and Adult partitions.Source: Figure 8 · p. 20
  • For random splits on Fashion-MNIST and CIFAR-10, fitted slopes of prediction variability are close to −1/2 across all tested N.The figure uses an unweighted cycle, α = 0.3, and n_i = 2.5p.Source: §E.6 · p. 21

Related papers

Loading 2610.20075v1…