Machine learning on distributed data has seen massive success recently, particularly with federated learning. However, while much of the focus has been on "horizontally" partitioned data (different users, same features), many real-world applications rely on vertically partitioned data (same users, different features).
For example, a bank might hold a customer's financial history, while a retail store holds their purchase history. To train a unified model, these datasets must first be aligned using Record Linkage (RL). Because identifiers are often noisy or intentionally obfuscated for privacy, RL is rarely perfect. This paper provides the first formal theoretical framework to understand how these record linkage errors impact downstream machine learning performance, revealing that models can actually become "immune" to certain linkage mistakes.
The Challenge of Vertical Partitioning
In practice, researchers often either rely on heuristics for record linkage or simply assume the linkage is perfect. But how exactly do RL errors snowball into ML model errors, and can we design models robust to these mistakes?
The authors formalize the RL and ML pipeline using a rigorous mathematical framework. They represent RL mistakes as an unknown permutation matrix ($\hat{P}$) that swaps rows between the "ideal" perfectly matched dataset and the "observed" noisy one. By defining a new metric—$(\epsilon, \tau)$-inexactness—they quantify these errors based on how dissimilar the swapped records are.
Focusing on Ridge-Regularized Taylor Losses (common in federated settings), they derive conditions under which a model trained on noisy linked data ($\tilde{\theta}^*$) converges to the ideal model ($\theta^*$) as the dataset size ($m$) grows.
Key Insights: The "Immunity" of Large Margins
The paper's most striking finding is the concept of margin immunity. The authors prove mathematically that if the ideal classifier separates data with a sufficiently large margin, the noisy classifier will still produce the correct classification. Essentially, a strong predictive signal in the features can drown out the noise created by misaligned rows.
Furthermore, the theory reveals that not all RL errors are equal. Swapping two records belonging to the same class is far less damaging to the model than swapping records of different classes. Because cross-class swaps are so detrimental, the authors suggest that RL algorithms should be "class-aware," incorporating even noisy or predicted class labels to prioritize correct class matching over mere feature similarity.
Finally, the authors demonstrate convergence at scale. The "drift" between the noisy and ideal models vanishes as the dataset grows, provided the number of RL mistakes doesn't grow faster than the square root of the number of examples ($T = o(\sqrt{m})$).
Empirical Validation
To validate their theory, the researchers tested their framework across 15 UCI machine learning benchmarks (including phishing, creditcard, winewhite, and breast-wisc). By splitting features to simulate vertical partitioning and injecting noise into shared linkage features, they observed the following:
- Empirical Immunity: On the
winewhitedataset, while RL errors caused training mistakes, almost zero errors occurred on examples where the ideal model had a margin greater than 0.5. - Class-Aware Linkage Boost: They introduced
GREEDYRL+C, an algorithm utilizing class labels during matching. On thecreditcarddataset, this approach reduced test error by nearly 20% compared to standard, class-agnostic record linkage. - Predictive Parameters: The experiments confirmed a causal dependence where the theoretical parameters $\xi$ (magnitude of mistakes) and $T$ (number of mistakes) directly correlate with the drop in ML performance.
Limitations and Future Work
While groundbreaking, the framework has a few limitations that pave the way for future research:
- Linear Model Focus: The core proofs center on linear models. While the authors provide a bridge to deep learning via Lipschitz constants, dedicated theory for deep architectures could yield tighter bounds.
- 1-to-1 Matching Assumption: The current math assumes every record in Peer A has exactly one corresponding record in Peer B. Real-world datasets often only partially overlap, or one record might match multiple others.
- Privacy-Utility Tradeoff: The paper notes privacy as a source of noise but does not explicitly provide a protocol for secure record linkage that satisfies differential privacy guarantees while maintaining these "immunity" properties.
Summary updated