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

Ekkehard Schnoor; Malik Tiomoko; Alexander Jung

cs.LGOct 14, 2026

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

Authors: Ekkehard Schnoor, Malik Tiomoko, Alexander Jung

Organizations: Aalto University, Espoo, Finland · Huawei Noah’s Ark Lab, Paris, France

Abstract

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.

Figures & tables

Figure 1: Homogeneous data and concentration, with common

\mathbf{\Sigma}=\mathbf{I}_{p}

and

\bm{\mu}=\mathbf{e}_{1}

. Left: node-average test error with

N=6

p=60

and

n_{i}=150

. Path, cycle and complete graphs each have total edge weight 6. Lines: theoretical predictions; points: Monte Carlo means. Right: standard deviation of the unit-norm observable

f(\widehat{\mathbf{w}})=N^{-1/2}\sum_{i=1}^{N}\mathbf{e}_{1}^{\top}\widehat{\mathbf{w}}^{(i)}

on an unweighted cycle, with

N\in\{2,4,8\}

p\in\{24,48,96\}

n_{i}=2.5p

and

\alpha=0.3

. The

p^{-1/2}

guide is anchored at

N=4

p=24

. Points use 240 independent training draws; error bars are 95% intervals, with bootstrap intervals for the standard deviations.

Figure 2: Heterogeneous three-node path with

p=80

n_{i}=200

\bm{\mu}^{(1)}=1.4\mathbf{e}_{1}

\bm{\mu}^{(2)}=-0.4\mathbf{e}_{1}+\mathbf{e}_{2}

and

\bm{\mu}^{(3)}=-0.7\mathbf{e}_{2}+0.8\mathbf{e}_{3}

. Covariances are diagonal: entries of

\mathbf{\Sigma}^{(1)}

and

\mathbf{\Sigma}^{(2)}

are evenly spaced from

0.5

1.5

and from

1.4

0.6

, respectively;

\mathbf{\Sigma}^{(3)}

has half its diagonal entries equal to

0.4

and half equal to

2

. Left: predicted and measured node-average test error. Right: node-specific quadratic noise terms. Lines: Theorem 4 ; points and 95% intervals: 240 independent training draws, shared across values of

\alpha

Figure 3: Six nodes with

p=60

n_{i}=150

and

\mathbf{\Sigma}^{(i)}=\mathbf{I}_{p}

. Nodes

1,2,3

have mean

\mathbf{e}_{1}+0.8\mathbf{e}_{2}

(blue), and nodes

4,5,6

have mean

\mathbf{e}_{1}-0.8\mathbf{e}_{2}

(orange). Unit-weight cycles follow the orders

(1,2,3,4,5,6)

and

(1,4,2,5,3,6)

, giving identical Laplacian spectra but two and six edges between different tasks, respectively. Lines: Theorem 4 . Points: means over 240 independent training draws, shared across graphs and values of

\alpha

, with 95% intervals.

Figure 4: Real-data predictions. Each node’s data are split into a pool (70%) and a held-out test set (30%). Predictions use the signed-observation moments of the pool; measured errors average 100 independent training draws from it, shared across the

\alpha

grid. (a) Predicted versus held-out test error for all 55 settings and grid values. (b) Largest gap to ( 22 ) versus the spread of whitened squared norms relative to its Gaussian value (index 1). Feature, partition and graph details are given in Appendix E and the code.

		Gap (pp)		Regret (pp)
Group	#	Gauss	test	med.	max
i.i.d. splits	9	0.8	1.8	0.07	0.17
Dirichlet, $a=100$	6	1.0	2.0	0.12	0.18
Dirichlet, $a\leq 0.5$	12	1.1	2.5	0.06	0.25
Rotations	12	2.1	2.3	0.05	0.24
Task alignment	4	1.1	2.2	0.02	0.18

Table 1: Prediction gaps and tuning regrets on 55 real-data settings, in percentage points (pp). Gap: median across settings of the largest absolute prediction error over the

\alpha

grid. “Gauss” evaluates ( 22 ) on the fitted coefficients with pool moments; “test” uses held-out classification error. Regret: extra held-out error at the theory-selected

\alpha

relative to the lowest mean error on the grid, summarized by its median and maximum. Predictions use pool moments.

Method	MNIST rot.	FMN. rot.	CIFAR subp.	CIFAR Dir.	HAR users	Adult silos
Local	10.97	22.32	17.35	15.41	20.77	25.77
Consensus	18.43	21.88	12.19	11.43	14.85	23.15
Fine-tuning	9.44	17.58	11.88	10.65	14.49	23.44
Mixture	9.08	17.35	11.84	10.58	14.74	23.56
GTVMin, $\alpha$ chosen by
CV (5-fold)	8.47	17.90	11.64	10.52	14.37	23.51

Table 2: Test error (%) on six real-data settings, averaged over 20 training draws. Plug-in theory uses training-sample means and Ledoit–Wolf covariance estimates; oracle theory uses pool moments. Fine-tuning starts from consensus; mixture is the global/local method of Hanzely and Richtárik (2020) . The 95% intervals are at most

\pm 0.4

, except

\pm 0.7

for local HAR. Bold: lowest reported error excluding hindsight, which gives the lowest measured GTVMin error on the tested grid. Fore the setup details, see Appendix E .

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

Dataset	Partition	Tasks	Graphs	#
MNIST	random split	3 vs. 5	path, cycle, complete	3
	rotations ( $0^{\circ}$ – $150^{\circ}$ )	3/5, 4/9, 7/9, 2/7, 1/7	path; complete for 3/5	6
	Dirichlet	digits $<5$ vs. $\geq 5$	complete, 2-NN	6
	alignment ( $0^{\circ}$ and $90^{\circ}$ )	3 vs. 5	two cycles	2
F-MNIST	random split	pullover vs. coat	path, cycle, complete	3
	rotations ( $0^{\circ}$ – $150^{\circ}$ )	pullover/coat, T-shirt/shirt, sneaker/boot, sandal/sneaker, coat/shirt	path; complete for pullover/coat	6

Appendix

Table 3: The 55 real-data settings. Unless stated otherwise,

N=6

p=100

and

n_{i}=250

. Tasks are written as positive vs. negative class. Dirichlet partitions use

a\in\{0.1,0.5,100\}

. Complete graphs have total edge weight 6 for random splits, 5 for rotations and

N

otherwise; all other graphs have unit weights. #: number of settings.

Method	MNIST rot.	FMN. rot.	CIFAR subp.	CIFAR Dir.	HAR users	Adult silos
Local	10.97 $\pm$ 0.23	22.32 $\pm$ 0.42	17.35 $\pm$ 0.31	15.41 $\pm$ 0.36	20.77 $\pm$ 0.72	25.77 $\pm$ 0.34
Consensus	18.43 $\pm$ 0.24	21.88 $\pm$ 0.24	12.19 $\pm$ 0.13	11.43 $\pm$ 0.17	14.85 $\pm$ 0.22	23.15 $\pm$ 0.18
Fine-tuning	9.44 $\pm$ 0.20	17.58 $\pm$ 0.27	11.88 $\pm$ 0.20	10.65 $\pm$ 0.20	14.49 $\pm$ 0.34	23.44 $\pm$ 0.26
Mixture	9.08 $\pm$ 0.18	17.35 $\pm$ 0.22	11.84 $\pm$ 0.20	10.58 $\pm$ 0.21	14.74 $\pm$ 0.37	23.56 $\pm$ 0.22
GTVMin, $\alpha$ chosen by
CV (5-fold)	8.47 $\pm$ 0.21	17.90 $\pm$ 0.29	11.64 $\pm$ 0.14	10.52 $\pm$ 0.19	14.37 $\pm$ 0.27	23.51 $\pm$ 0.30

Appendix

Table 4: Test error (%) of Table 2 with 95% confidence intervals over 20 training draws.

Figure 5: Random splits into

N=6

nodes with

p=100

and

n_{i}=250

, on a path, a cycle and a complete graph with total edge weight 6. Lines: Theorem 4 . Dots: held-out test error with 95% intervals over 100 draws. Crosses: Gaussian formula ( 22 ) for the path. As in Corollary 3 , the error decreases towards that of the pooled model.

Figure 6: Rotation shift: node

k

sees the images rotated by

30(k-1)

degrees,

N=6

p=100

n_{i}=250

, on a unit-weight path and a complete graph with total weight 5. Lines, dots and crosses as in Figure 5 . The best

\alpha

is intermediate, and on MNIST full collaboration is worse than local training.

Figure 7: Graph–task alignment on real data, with the two cycles of Figure 3 . Left: MNIST 3 vs. 5, with nodes 1–3 upright and nodes 4–6 rotated by

90^{\circ}

. Right: CIFAR-10, nodes 1–3 separate airplanes and ships from birds and frogs, nodes 4–6 automobiles and trucks from cats and dogs. Both cycles have the same Laplacian spectrum and use the same training draws. The grouped cycle, with two edges between different tasks instead of six, has the lower error, as predicted.

Figure 8: Natural partitions. HAR: 10 nodes of 3 users each,

p=30

n_{i}=75

. Adult: 6 employment sectors or 5 age groups,

p=40

, unequal

n_{i}

. Complete graphs with total weight

N

, and

k

-NN graphs built from pool statistics (

k=3

for HAR,

k=2

for Adult). Lines and dots as in Figure 5 .

Figure 9: Theorem 1 on real data: standard deviation over 200 training draws of the unit-norm observable

N^{-1/2}\sum_{i}\mathbf{e}_{1}^{\top}\widehat{\mathbf{w}}^{(i)}

, for random splits of Fashion-MNIST (pullover vs. coat) and CIFAR-10 (automobile vs. truck). Unweighted cycle,

\alpha=0.3

n_{i}=2.5p

, bootstrap 95% intervals. The fitted slopes, given in the legend, are close to

-1/2

for every

N

Setting [graph]	$N$	$p$	$\|\Delta\|_{\text{G}}$	$\|\Delta\|_{\text{T}}$	$\alpha^{\text{de}}$	$\alpha^{\star}_{\text{test}}$	regret	local	cons.	best	NC
iid; CIFAR auto/truck [complete]	6	100	0.70	2.69	1	5	0.17	31.9	23.3	23.3	3.1
iid; CIFAR auto/truck [cycle]	6	100	0.70	2.69	2	10	0.11	31.9	23.3	23.3	3.1
iid; CIFAR auto/truck [path]	6	100	0.70	2.69	5	10	0.07	31.9	23.4	23.4	3.1
iid; F-MNIST pullover/coat [complete]	6	100	1.23	1.07	1	10	0.10	21.3	13.8	13.8	3.7
iid; F-MNIST pullover/coat [cycle]	6	100	1.23	1.07	2	10	0.08	21.3	13.8	13.8	3.7
iid; F-MNIST pullover/coat [path]	6	100	1.23	1.07	5	10	0.03	21.3	13.8	13.8	3.7

Appendix

Table 14

Federated Learning

Federated learning trains shared models across data holders without requiring them to pool their raw data.

See all 961 papers

Federated Soft Clustering via Generalized Total Variation Minimization
Sep 16, 2026Shamsiiat Abdurakhmanova, Alexander JungGaussian Mixture Models Non-IID Federated Learning
Department of Computer Science, Aalto University, Espoo, Finland
Federated learning with heavy-tailed gradient noise and communication noise: a variance-reduction based algorithm
Jun 21, 2026Shengchao Zhao, Yongchao LiuStochastic Optimization Nonconvex Stochastic Optimization
School of Mathematics, China University of Mining and Technology, Xuzhou, China · School of Mathematical Sciences, Dalian University of Technology, Dalian, China
FedSLoP: Memory-Efficient Federated Learning with Low-Rank Gradient Projection
Apr 27, 2026Yutong He, Zhengyang Huang, Jiahe Geng +1Communication-Efficient Distributed Training Gradient Compression
Peking University · Beihang University

Sep 16, 2026J/K move · Enter open · S save

Federated Soft Clustering via Generalized Total Variation Minimization

Shamsiiat Abdurakhmanova, Alexander Jung

Department of Computer Science, Aalto University, Espoo, Finland

Gaussian Mixture Models Non-IID Federated Learning Federated Learning

Open paper AskPDF arXiv

We study federated soft clustering over federated learning (FL) networks of devices that each hold a private local dataset and fit a personalized Gaussian mixture model (GMM). Generalized total variation minimization (GTVMin) couples the local maximum likelihood problems through a graph regularizer that penalizes a discrepancy between the models of connected nodes. The choice of discrepancy measure is a key design decision: we compare a squared Euclidean distance between model parameters, which requires component matching, with two measures that compare the local model distributions directly and hence need no matching: a Monte-Carlo approximated Kullback-Leibler (KL) divergence and a closed-form maximum mean discrepancy (MMD). All three resulting GTVMin instances are optimized by synchronous projected gradient updates; for the smooth MMD instance we provide a convergence guarantee to stationary points. We characterize their computational cost and evaluate their robustness to data heterogeneity.

Abstract

Federated Learning

Explore similar work

Federated Soft Clustering via Generalized Total Variation Minimization

Federated learning with heavy-tailed gradient noise and communication noise: a variance-reduction based algorithm

FedSLoP: Memory-Efficient Federated Learning with Low-Rank Gradient Projection