PaperlayerView exact revision on arXiv

Source-linked AI summary

RIPPLE in Still Water: Zero-Shot Clustering in Federated Learning with Wavelet Scattering Transform

Alessandro Licciardi

arXiv:2610.03054v1cs.LG

TL;DR

Under heterogeneous client data, a single global model is limited, and existing clustered FL methods discover groups during training. RIPPLE instead infers cluster weights offline from local spectral data summaries; across five benchmarks it outperforms baselines, with the largest margins on realistic partitions.

  • Problem

    A single global model cannot represent clients whose data lie in qualitatively different regimes, while prior clustered methods infer groups during training and lack a pathway for assigning clients absent from training.

    Source: §1 · pp. 1–2

  • Method

    RIPPLE computes soft client-cluster assignments offline from local spectral summaries before federation, then uses those weights for clustered training.

    Source: §1 · p. 2

  • Results

    RIPPLE consistently outperforms all baselines across five benchmarks, with the largest margins on the most realistic partitions.

    Source: §1 · p. 2, Conclusion · p. 9

  • Takeaways & Limitations

    Per-round communication matches FEDAVG, and an unseen client can obtain a personalized model with a single encoder pass and no gradient computation or model evaluation.

    Source: §1 · p. 2

    The theoretical data-generation assumption is limited to sub-Gaussian client samples subject to bounded translations and a bounded diffeomorphism.

    Source: §5 · p. 6

Abstract

from arXiv · show

Clustered Federated Learning (FL) partitions a client population into groups of similar local distributions and trains one specialized model per cluster, mitigating client drift that degrades single-model methods under non-IID data. Prior methods discover cluster structure inside the training loop through gradient similarity, loss evaluation, or EM-style updates, thus increasing communication overhead, exposing gradients to inversion attacks, and providing no mechanism to assign clients absent from training. We propose RIPPLE, a clustered FL framework in which cluster assignment is computed entirely offline from a spectral characterization of each client's local data: a variance-weighted principal-component prototype embedded via the Wavelet Scattering Transform and decoded by a Gaussian Mixture VAE trained server-side on synthetic client populations before federation begins. Per-round communication cost matches FedAvg exactly, and a client absent from training obtains a personalized model from a single forward pass, without gradient computation, model evaluation, or extra communication round. We prove that the gap between RIPPLE's surrogate clustered objective and the oracle is bounded by a computable quantity decaying with client sample size and independent of federation duration; per-cluster convergence matches the minimax-optimal rate for non-convex smooth objectives. Across five benchmarks spanning controlled and realistic heterogeneity, RIPPLE consistently outperforms all baselines, with margins growing on the most realistic partitions.

1 Introduction

Single-model FL cannot represent clients in qualitatively different data regimes, while existing clustered methods discover groups during training. RIPPLE assigns clients offline from spectral data summaries, matching FedAvg's per-round communication cost and enabling zero-shot personalization; it outperforms baselines across five benchmarks.

1 Introduction

  • A single global model cannot represent clients whose data lie in qualitatively different regimes, motivating specialized models for compatible client groups.Non-IID client updates can conflict and degrade accuracy; clustered FL instead trains one model per group.Source: §1 · pp. 1–2
  • Prior clustered methods infer groups during training, adding communication overhead, exposing updates to gradient-inversion attacks, and offering no path for clients absent from training.Some methods also require the cluster count in advance, whereas RIPPLE needs only a loose upper bound and RIPPLE-HDB adapts it using density-based clustering.Source: §1 · p. 2
  • RIPPLE computes cluster assignments once from local data statistics before communication begins, and its per-round cost matches FEDAVG exactly.The assignments are fixed before the first round; a new client can obtain a personalized model using only a small spectral embedding.Source: §1 · p. 2
  • The surrogate clustered-objective gap is bounded by a computable quantity that decays with client sample size and is independent of federation duration.A client absent from training obtains a personalized model from one WST embedding and encoder pass, without gradient computation or model evaluation.Source: §1 · p. 2
  • RIPPLE outperforms all baselines across five benchmarks, with the largest margins on the most realistic partitions.Zero-shot assignment matches or exceeds other clustered FL methods.Source: §1 · p. 2

2 Related Work

Prior approaches address heterogeneous client data through global-model adaptations, per-client personalization, or clustered training. RIPPLE is distinguished by inferring soft assignments before training, with no gradient exchange for cluster discovery and a path to assign unseen clients.

2 Related Work

  • Variance-reduction and adaptive methods retain a single global model, while per-client personalization can discard exploitable information shared within client groups.Clustered training instead leverages shared structure by fitting specialized models for compatible clients.Source: §2 · p. 2
  • Existing clustered methods use gradient similarity, repeated evaluation of candidate models, EM-style updates, or adaptive graph and hierarchy structure tied to training feedback.IFCA evaluates all candidate models each round, while FESEM iterates gradient updates from candidate centers.Source: §2 · pp. 2–3
  • RIPPLE infers soft cluster weights once from pre-federation statistics, matching FedAvg's per-round communication and assigning new clients with one frozen-encoder pass.Prior methods commonly use hard or in-training assignment and require communication or candidate-model evaluation to handle new clients.Source: §2 · p. 3

3 Background

The background frames cross-silo FL around private, locally sampled datasets and contrasts a single global objective with a probabilistic clustered objective. RIPPLE estimates soft client-to-cluster weights from pre-federation statistics, using WST as a stable, label-free representation.

3 Background

  • In cross-silo FL, clients keep their labeled local datasets private, while FEDAVG broadcasts a shared model and aggregates local-SGD updates into a single global parameter.Pre-federation characterization uses features without labels; labels enter the federated training loss.Source: §3 · p. 3

3.1 A Probabilistic Model of Client Heterogeneity

  • The probabilistic model treats each client's data distribution as a convex mixture of semantic distributions and estimates soft weights from local pre-federation statistics.Zero-shot assignment maps each client to a simplex-valued weight vector without gradient exchange or cluster-model evaluation.Source: §3.1 · pp. 3–4

3.2 Wavelet Scattering Transform

  • WST provides a non-expansive, translation-invariant, and diffeomorphism-stable representation that serves as a label-free fingerprint for pre-federation cluster assignment.Clients with distributions differing through sensor miscalibration, translation, or mild domain shifts have representations whose distance is proportional to the perturbation magnitude.Source: §3.2 · p. 4

4 The RIPPLE Algorithm

RIPPLE computes soft client-cluster weights before federation using local spectral summaries, a WST embedding, and a server-trained GMM-VAE. The resulting assignments support posterior-weighted cluster training, FedAvg-matched per-round communication, and optional density-based cluster refinement.

4 The RIPPLE Algorithm

  • RIPPLE assigns each client a soft cluster-weight vector before any federation round, using a deformation-stable local summary and a server-trained GMM-VAE.The frozen encoder can generalize to unseen clients in a single forward pass.Source: §4 · p. 4

4.1 Pre-Federation Distribution Characterization

  • Each client's spectral prototype is built from its empirical mean and covariance using variance-weighted principal components.The component count is selected by an explained-variance threshold.Source: §4.1 · p. 4
  • WST embeds the spectral prototype to address sensitivity to translations, sensor miscalibrations, and affine skews between semantically similar distributions.Each client transmits its embedding once before federation begins.Source: §4.1 · p. 5
  • A GMM-VAE maps each WST embedding to simplex-valued cluster weights through a categorical posterior, computed at inference with one frozen-encoder forward pass.Source: §4.1 · p. 5, §4.2 · p. 5
  • The server trains the GMM-VAE before federation on synthetic clients generated from an auxiliary dataset and varied mixture targets.The training procedure exposes the VAE to the full open simplex of mixture weights.Source: §4.1 · p. 5

4.2 Federated Posterior Mixing

  • RIPPLE-STRAT and RIPPLE-UNIF use posterior-weighted aggregation, and per-round communication matches FEDAVG because the embedding is transmitted only once.RIPPLE-STRAT guarantees at least one gradient per cluster per round; RIPPLE-UNIF samples uniformly.Source: §4.2 · p. 5
  • When the cluster count is mis-specified, RIPPLE-HDB applies HDBSCAN to posterior distances for automatic model selection without additional hyperparameter search.Noise points are assigned to their nearest meta-cluster.Source: §4.2 · p. 5

5 Theoretical Analysis

RIPPLE’s theory bounds how faithfully offline routing approximates the oracle clustered objective, then analyzes convergence of soft-weighted per-cluster training. The end-to-end bound separates a routing term fixed by data geometry from an optimization term that decreases with training.

5.1 Routing Error and Embedding Stability

  • Routing error decreases with client sample size and larger spectral gaps, while domain shift imposes a model-independent floor on pre-federation assignment accuracy.The translation cost decreases with WST resolution, providing a design knob.Source: §5.1 · p. 6
  • RIPPLE’s computable surrogate-fidelity certificate bounds the gap to the oracle clustered objective before federation begins.The routing error reflects finite-sample noise and domain shift; prior clustered FL convergence analyses assume correct assignments but do not bound assignment error.Source: §5.1 · p. 6

5.2 Federated Convergence

  • Per-cluster convergence achieves the minimax-optimal rate O(1/T) for non-convex L-smooth objectives under the stated assumptions.Soft assignments let clients contribute fractionally to multiple clusters, increasing effective participation mass for minority clusters and reducing gradient variance.Source: §5.2 · p. 7
  • The per-cluster convergence guarantee requires positive effective participation mass and finite gradient variance.Stratified sampling guarantees each cluster receives at least one gradient signal per round.Source: §5.2 · p. 7
  • The end-to-end excess-risk bound separates a routing term fixed at t = 0 from an optimization term that decays at O(1/T).The routing term decreases with more local data, larger spectral gaps, finer WST resolution, and smaller domain shift; the optimization variance is suppressed by effective participation mass.Source: §5.2 · p. 7

6 Experiments

Across five benchmarks, all three RIPPLE variants outperform every baseline, with larger margins on harder benchmarks. In held-out-client tests, RIPPLE’s zero-shot assignment matches or exceeds baselines in the reported conditions, though RIPPLE-HDB has a CIFAR-10 failure case.

6 Experiments

  • The evaluation spans controlled Dirichlet label partitions, Office-Home covariate shift, and GLDv2’s natural photographer partition, using 1000 rounds and 10 clients per round.IFCA and FESEM are reported at their best cluster count from K ∈ {2, 4, 6, 8, 10}, with methods capped at 10 clusters.Source: §6 · pp. 7–8, Table 1 · p. 8

6.1 RIPPLE in Heterogeneous Scenarios

  • 51.82% accuracy on GLDv2 for RIPPLE-STRAT is 7.4 points above IFCA’s 44.42%, and all three RIPPLE variants outperform every baseline across five benchmarks.Margins grow on harder benchmarks; Table 1 covers controlled label heterogeneity, covariate shift, and natural long-tail distributions.Source: §6.1 · p. 8, Table 1 · p. 8

6.2 RIPPLE with out-of-distribution clients

  • RIPPLE assigns unseen clients with one frozen-encoder forward pass, while baselines select among models using local loss and labeled data.The held-out-client evaluation uses 10 clients under αtest ∈ {1.0, 100}; this gives the baselines an oracle advantage over zero-shot assignment.Source: §6.2 · p. 8, Table 2 · p. 9
  • 57.27 ± 3.00% on CIFAR-10 is achieved by RIPPLE-UNIF for αtrain = 0.1 and αt = 1.0, surpassing all best-by-loss baselines in the zero-shot setting.On CIFAR-100, all three RIPPLE variants match or exceed baselines across all tested conditions.Source: §6.2 · p. 8, Table 2 · p. 9
  • RIPPLE-HDB falls to approximately 10% on CIFAR-10 when HDBSCAN fragments the posterior into 7–14 singleton clusters.The passage attributes this failure to near-hard assignment of unseen clients to over-specialized models and limits HDB’s suitability to cases where Table 1 indicates a benefit.Source: §6.2 · p. 9

Conclusion

RIPPLE computes client-to-cluster assignments offline from local-data spectral summaries, before communication begins. The paper reports bounded surrogate-oracle error, zero-shot personalization, and consistent benchmark gains, while identifying formal differential privacy as future work.

Conclusion

  • RIPPLE computes client-to-cluster assignments once, offline, from each client’s local-data spectral summary before communication begins.The conclusion reports per-round cost matching FEDAVG and zero-shot personalization of unseen clients through a single encoder forward pass.Source: Conclusion · p. 9
  • The surrogate-oracle gap is bounded by a computable quantity that depends on local sample size and spectral gap, not the number of rounds.The conclusion also reports per-cluster convergence at the minimax-optimal rate for non-convex smooth objectives.Source: Conclusion · p. 9
  • Across five benchmarks, RIPPLE consistently outperforms global and clustered FL baselines, with larger margins on the most realistic partitions.Source: Conclusion · p. 9
  • Formal differential privacy remains future work; adding calibrated noise to the spectral embedding is proposed to yield an (ε, δ)-DP guarantee at the cost of larger routing error.Source: Conclusion · p. 9

A.1 Probabilistic Derivation of the Federated and Clustered Objectives

The appendix derives population-level federated and clustered objectives from client distributions, then describes the Wavelet Scattering Transform used to characterize client data. Its stated stability properties support using those representations as fingerprints for pre-federation assignment.

A.1 Probabilistic Derivation of the Federated and Clustered Objectives

  • The population federated loss weights each client’s population loss by its normalized data weight, while the oracle clustered loss assigns dedicated models to semantic distributions.The derivation states that FEDAVG is recovered when there is one cluster or all clients have identical hard cluster assignments.Source: §A.1 · p. 13

A.2 Wavelet Scattering Transform: Construction and Properties

  • The Wavelet Scattering Transform applies wavelet convolutions, complex moduli, and lowpass averaging to form zeroth-, first-, and second-order coefficients.The appendix states that its stability properties make the representation a label-free fingerprint for pre-federation assignment, and that orders 0–2 capture over 98% of signal energy across standard image benchmarks.Source: §A.2 · p. 14

B GMM-VAE: Generative Model and ELBO Derivation

The appendix details RIPPLE’s GMM-VAE inference and the assumptions and stability results supporting its prototype-based clustering. It also gives the algorithm’s pretraining, assignment, and federated-training stages.

B GMM-VAE: Generative Model and ELBO Derivation

  • The approximate posterior factorizes into categorical cluster and cluster-conditioned latent distributions; the ELBO combines reconstruction and continuous- and discrete-latent KL terms.The supervised alignment term augments this objective using synthetic clients’ known target mixtures.Source: B GMM-VAE: Generative Model and ELBO… · p. 15
  • The frozen encoder assigns a real client’s cluster-weight vector in one forward pass, without a federation round or cluster-model evaluation.During pretraining, a supervised term aligns the categorical posterior with known synthetic-client target mixtures; the appendix says this also supports semantic consistency and prevents posterior collapse.Source: B GMM-VAE: Generative Model and ELBO… · pp. 15–16

C RIPPLE Pseudocode

  • Algorithm 1 separates server-side VAE pretraining, parallel client assignment from scattering embeddings, and subsequent clustered federated rounds.The algorithm returns the trained cluster models and client assignment map.Source: C RIPPLE Pseudocode · p. 16

D.1 Notation Recap and Assumptions

  • The analysis assumes sub-Gaussian client samples with bounded translations and smooth diffeomorphic warps, together with bounded losses and L-smooth cluster objectives.The data-generation assumption is stated for each client’s samples; loss regularity is assumed for every client and parameter.Source: §D.1 · p. 17

D.2 Auxiliary Results

  • Dirichlet hallucination with sampled concentration parameters covers every interior simplex mixture, while square-root Jensen–Shannon distance satisfies the triangle inequality.Source: §D.2 · p. 17

D.3 Spectral Concentration of the Prototype

  • The prototype concentration result combines mean concentration, covariance concentration, and a Davis–Kahan transfer, with probability at least 1−δ.The stated result’s constants come from the preceding mean, covariance, and subspace lemmas.Source: §D.3 · pp. 17–18

D.4 WST Stability Properties

  • The scattering transform is non-expansive, approximately translation-invariant, and Lipschitz-stable to diffeomorphic deformations.The translation bound scales with |v|/2^J and signal norm; the deformation bound scales with the deformation gradient norm and signal norm.Source: §D.4 · p. 19

D.5 Embedding Stability (Theorem 5.1)

The embedding-stability argument compares an empirical estimate of a deformed client prototype with its undeformed prototype. It bounds the discrepancy using prototype estimation and deformation stability.

D.5 Embedding Stability (Theorem 5.1)

  • The empirical prototype estimates the observed, deformed quantity, whereas the target prototype is undeformed; the proof accounts for their difference through translation and diffeomorphism bounds.Source: §D.5 · pp. 19–20
  • With probability at least 1−δ, the embedding discrepancy is bounded by the prototype-error term plus the deformation contribution.The proof introduces a prototype subjected to the observed translation and diffeomorphism, then combines the prototype and WST stability bounds.Source: §D.5 · pp. 19–20
  • The shift contribution scales with the undeformed prototype’s energy, which the experiments bound using the auxiliary dataset’s maximum norm.Source: §D.5 · p. 20

D.6 Surrogate Fidelity (Theorem 5.2)

The appendix details RIPPLE’s surrogate-fidelity and convergence guarantees, implementation costs, communication and privacy properties, and additional experimental settings. It also qualifies the non-convex excess-risk interpretation and reports sensitivity to selected hyperparameters.

D.6 Surrogate Fidelity (Theorem 5.2); D.7 Convergence (Theorem 5.3); D.8 End-to-End Excess Risk (Corollary 5.1)

  • The appendix identifies Theorem D.2 as the surrogate-objective fidelity result and Theorem D.3 as the per-cluster convergence result, without stating their bounds in the supplied passages.It also names Corollary D.1 as the end-to-end excess-risk result.Source: §D.6 · p. 20, §D.7 · p. 20, §D.8 · p. 21

D.8 End-to-End Excess Risk (Corollary 5.1)

  • The non-convex optimization bound controls average squared gradient norm; a function-value gap additionally requires a Polyak–Łojasiewicz or local-convexity assumption near Θ∗.The decomposition remains valid under either interpretation.Source: §D.8 · p. 21

E Computational and Communication Complexity; Client Embedding; Communication Overhead

Communication Overhead

  • RIPPLE’s amortized per-round communication cost matches FEDAVG, while the one-shot embedding transmission is less than 0.03% of total per-client communication in every tested configuration.Clients transmit the embedding once before round 1; subsequent downloads and gradient uploads match FEDAVG.Source: Communication Overhead · p. 23

F Privacy of RIPPLE

  • Raw client data stays on-device; the transmitted WST embedding derives from a distributional spectral summary, and the paper describes the prototype-to-embedding mapping as non-invertible.The server’s encoder reduces the embedding to a soft cluster-weight vector that can be retained instead.Source: F Privacy of RIPPLE · pp. 23–24

GMM-VAE Training: Auxiliary Data Only

  • The server-side GMM-VAE is pre-trained on synthetic client embeddings generated from an auxiliary dataset, without real client data or client embeddings used for parameter updates.After pre-training, the server retains frozen parameters and client cluster-weight vectors.Source: GMM-VAE Training: Auxiliary Data Only · p. 24

G.1 Datasets, architectures, and protocol

  • The appendix’s datasets induce heterogeneity through Dirichlet label partitions, except Office-Home’s visual-domain sampling and GLDv2-23k’s natural photographer split.The dataset summary defines K as client count, S as samples per client, α as Dirichlet concentration, and r as participation rate.Source: §G.1 · p. 25, Table 4 · p. 25

G.3 Sensitivity to hyperparameters

  • RIPPLE variants on Office-Home stay within about 1 percentage point of default across tested WST configurations; on GLDv2, the default is best or within 1 point of best across variants.The reported GLDv2 default is J = 3, L = 8, M = 20, K = 20.Source: §G.3 · p. 26

G.4 Ablation for IFCA and FESEM

The ablation compares IFCA and FESEM across cluster counts, reporting each method’s best-performing K per dataset. IFCA favors K=6 on CIFAR-10 and Office-Home but K=8 on GLDv2, while FESEM favors K=8 on CIFAR-10 and K=10 on CIFAR-100.

G.4 Ablation for IFCA and FESEM

  • IFCA and FESEM are swept from K=2 to 10, with only each method’s best-performing K per dataset reported in Table 9.The full cluster-count sweep is in Table 9.Source: §G.4 · p. 27, Table 9 · p. 28
  • IFCA prefers K=6 on CIFAR-10 and Office-Home and K=8 on GLDv2; FESEM prefers K=8 on CIFAR-10 and K=10 on CIFAR-100.The cluster-count ablation reports the best K per method and dataset.Source: §G.4 · p. 27, Table 9 · p. 28
  • Table 8 sweeps VAE component count K using default WST settings J=3, L=8, M=20, latent dimension 32, and λsup=5.Bold rows indicate each dataset’s default.Source: Table 8 · p. 28

Related papers

Loading 2610.03054v1…