FedPS: Federated Preprocessing for structured data via aggregated Statistics

AI summary

Overview

Research area: Federated learning and data preprocessing for structured (tabular) data, combining federated aggregation protocols with data-sketching theory (quantiles, frequent items).

Technical level: Advanced. The paper assumes familiarity with federated learning settings (horizontal vs. vertical partitioning), Bayesian linear regression, and communication-complexity analysis.

Scope: The paper introduces FedPS, a framework plus open-source library that computes global preprocessing parameters (scaling, encoding, transformation, discretization, imputation) from aggregated client statistics instead of centralized raw data.

What This Paper Is About

Federated learning lets multiple parties train models together without sharing raw data, but almost all federated learning research assumes the data has already been cleaned, scaled, and imputed. That assumption is unrealistic: privacy rules prevent centralizing data for joint preprocessing, communication limits how much clients can exchange, and non-IID client data makes independently applied preprocessing inconsistent across clients. FedPS addresses this by defining a general workflow where clients compute local statistics, the server aggregates them into global parameters, and every client then applies the same parameters locally.

Key Contributions

1. A general federated preprocessing framework. FedPS maintains consistency across clients through summarization, aggregation, and parameter distribution (Section 3.2), rather than requiring raw data to be centralized.

2. Comprehensive preprocessing methods built on data sketching. The framework implements scaling, encoding, transformation, discretization, and imputation methods using sketching techniques such as KLL sketches and frequent-item sketches, so that complex global statistics (quantiles, frequent items) can be computed with communication independent of local dataset size.

3. Sufficient-statistics and communication-cost analysis. The paper maps each preprocessing operation to the statistics it requires and derives per-client communication rounds and asymptotic costs, providing practical guidance for scalable deployment (Section 3.3, Tables 1 and 2).

4. Federated Bayesian linear regression for both horizontal and vertical settings. This enables model-based imputation (the regression model inside IterativeImputer) while avoiding cross-client feature interactions in the vertical case (Section 4).

The paper also states that empirical results show federated preprocessing accuracy significantly surpassing both local-only preprocessing and raw-data baselines, particularly under heterogeneous data — but the experiment section is not present in the content available for this summary, so no dataset names, dataset sizes, or accuracy numbers can be reported here.

Main Findings

• Local-only preprocessing can be worse than no preprocessing. In non-IID settings, independent local transformations such as standardization can distort the global distribution; the paper states its experiments show inconsistent local preprocessing may degrade performance even below using raw data. An accompanying figure illustrates raw data that is linearly separable before each client applies local standardization and no longer linearly separable afterward.

• Simple statistics aggregate exactly and cheaply. Minimum, maximum, sum, mean, and variance aggregate with constant communication per feature, giving O(m) cost per client (with m the number of features), and produce parameters identical to centralized computation.

• Complex statistics require sketching. Exact quantiles require storing the entire dataset, which is impractical in federated settings; approximate sketches are used instead. The implementation uses KLL sketches for quantile-based methods (default configuration targets ε ≈ 1.65%) and can use REQ sketches when relative-error guarantees are needed (default roughly ε ≈ 1%). Frequent-item sketches use the DataSketches library, where the true frequency of an item lies between a lower and upper bound with (UB − LB) ≤ nε and ε = 3.5/k, with k the maximum map size. Frequent-item cost is O(k) per feature.

• Communication costs vary dramatically by method. Encoding via set union costs O(d) (with d the number of distinct categories), or O(dm) for one-hot encoding; Normalizer costs O(n) (per row, with n the number of samples); KBinsDiscretizer with k-means-based binning costs O(tkm) over t iterations; KNNImputer costs O(n′km) horizontally and O(n′n) vertically (with n′ the test-set size); IterativeImputer costs O(tm²min(n,m)) horizontally and O(tmn(min(n,m)+t)) vertically.

• Horizontal federated BLR is exact and cheap during iteration. Aggregating XᵀY and XᵀX additively across clients reproduces centralized BLR exactly, avoiding FedAvg-style iterative averaging. Per-client communication is O(m·min(n,m)) (Theorem 4.1), and during iterative refinement each client sends only a single scalar error. The server's one-time eigendecomposition costs O(m³); the paper reports that at m = 1000 this decomposition takes approximately 80 ms.

• Vertical federated BLR avoids cross-client feature interactions. Because off-diagonal blocks of XᵀX would require cross-client features, the vertical algorithm instead aggregates XXᵀ (an n × n quantity), computes an eigendecomposition of it, and lets each client derive its own coefficient block. The paper's Theorem 4.3 gives a vertical cost of O(n·min(n,m) + nt).

• Privacy scope is explicitly limited. The paper states that FedPS adopts a data-minimization principle and communicates compact summaries rather than raw data, but does not claim cryptographic security or differential privacy unless combined with additional safeguards.

• Consistency is the core benefit. The paper's central claim is that coordinated federated preprocessing, not local or transferred preprocessing, is what preserves separability and model quality under heterogeneous client distributions.

Methodology in Plain English

The researchers treat preprocessing as a statistics-aggregation problem. For each preprocessing operation, they first ask: what numbers does this operation actually need in order to compute its parameters? A standardizer needs only a mean and a variance; a min-max scaler needs only a minimum and a maximum; a quantile-based binner needs a set of quantiles; an encoder needs the set of distinct categories.

Once the needed quantities are identified, each client computes them on its own data and sends only those summaries to the server — never raw records. The server combines the summaries by summation (or by merging sketches) to obtain global values, derives the preprocessing parameters, and sends the parameters back to the clients, which then apply the identical transformation locally. This five-step loop is the framework's backbone.

Two families of statistics emerge. Some are exact and cheap: sums, counts, minima, maxima, means, and variances combine with communication that does not grow with the client's dataset. Others, like quantiles and frequent items, would require unbounded communication to compute exactly, so the authors substitute compact sketches with explicit error guarantees.

For the more demanding imputation methods, the authors go further and build federated versions of the underlying models. KNNImputer is implemented as federated k-nearest-neighbor regression, with clients reporting their smallest distances and the server resolving global neighbors. IterativeImputer is implemented on top of Bayesian linear regression, which the authors derive in two forms: a horizontal version where clients additively contribute the sufficient statistics XᵀX and XᵀY, and a vertical version where features are split across clients and the algebra is reformulated around XXᵀ so that no client ever needs another client's features. Both versions avoid repeatedly inverting a large matrix by doing one eigendecomposition up front and reusing it across iterations.

Why This Matters

Impact on research. Preprocessing has been a blind spot in federated learning: most work assumes clean, already-transformed data, and simulation studies preprocess centrally before partitioning — something impossible in real deployments. FedPS makes preprocessing a first-class, analyzable federated problem, and its communication-cost tables give other researchers a way to compare preprocessing methods on the same footing as training algorithms.

Real-world applications:

• Healthcare consortia, where hospitals hold differently formatted patient records and cannot pool them, but need consistent imputation and scaling before any shared model is trained.
• Financial institutions collaborating on fraud or risk models, where feature scales and category vocabularies differ sharply across institutions.
• Cross-organization tabular machine learning in vertical settings, where separate parties hold different feature columns for the same entities and need encoding, discretization, or imputation applied consistently.
• Any deployment using standard tabular pipelines, since FedPS maps familiar Scikit-learn preprocessing operations into the federated setting rather than inventing new semantics.

Industry relevance. The framework is released as an open-source library, and the paper positions it relative to existing federated frameworks that support only a narrow subset of preprocessing (for example, normalization and one-hot encoding). The emphasis on communication independent of local dataset size, plus explicit per-method cost formulas, targets the practical constraint that dominates real federated deployments.

Future Directions

• Privacy guarantees beyond data minimization. The paper explicitly notes it makes no cryptographic or differential-privacy claims, and states that formalizing privacy guarantees is discussed in its discussion section. Making FedPS differentially private or secure against inference from the shared summaries is an open direction.
• Extending the framework to remaining preprocessing operations. The paper identifies sufficient statistics for the methods it covers and provides details in appendices; a natural next step is covering the rest of the Scikit-learn preprocessing surface and other structured-data transformations.
• Tighter communication bounds. Several costs, such as IterativeImputer and KNNImputer, scale with sample counts or quadratic feature terms; reducing these, or substituting better sketches for quantile and frequent-item primitives, is a clear avenue.
• Empirical validation under realistic heterogeneity. The paper claims federated preprocessing substantially outperforms local-only and raw-data baselines in heterogeneous contexts; the extent to which this holds across datasets, partition schemes, and error settings is a question the paper leaves to its (not available in this summary) experimental section.

Target Audience

Practitioners and researchers working on federated learning systems with tabular or structured data, especially those building production pipelines where preprocessing must be consistent across clients without centralizing data. It is also relevant to applied statisticians and engineers interested in sketch-based aggregation, and to readers of standard tabular machine learning libraries who want to know which preprocessing steps can and cannot be federated, and at what communication cost.

Authors’ abstract

Federated Learning (FL) enables multiple parties to collaboratively train machine learning models without sharing raw data. However, before training, data must be preprocessed to address missing values, inconsistent formats, and heterogeneous feature scales. This preprocessing stage is critical for model performance but is largely overlooked in FL research. In practical FL systems, privacy constraints prohibit centralizing raw data, while communication efficiency introduces further challenges for distributed preprocessing. We introduce FedPS, a framework for federated data preprocessing based on aggregated statistics. FedPS leverages data-sketching techniques to efficiently summarize local datasets while preserving essential statistical information. Building on these summaries, we design federated algorithms for feature scaling, encoding, discretization, and missing-value imputation, and extend preprocessing-related models such as Bayesian Linear Regression to both horizontal and vertical FL settings. FedPS provides flexible, communication-efficient, and consistent preprocessing pipelines for practical FL deployments.