Federated Representation Learning in the Under-Parameterized Regime

Renpu Liu, Cong Shen, Jing Yang

In the era of Large Language Models (LLMs), the prevailing wisdom is often "bigger is better." However, for the billions of edge devices—smartphones, IoT sensors, and embedded systems—massive models are a luxury they can't afford. This creates a friction point for Federated Learning (FL), where we want to train models across these resource-constrained devices without sharing their private data.

A new paper from researchers at Penn State and the University of Virginia, titled "Federated Representation Learning in the Under-Parameterized Regime," tackles this head-on. They investigate what happens when your model is intentionally "too small" to perfectly fit the data—a scenario they call the under-parameterized regime.

TL;DR

This paper introduces FLUTE, the first Federated Representation Learning algorithm designed specifically for under-parameterized models with provable performance guarantees. By using a novel objective function and server-side optimization of local "heads," FLUTE successfully distills a global optimal representation even when individual clients have insufficient capacity to model their local data perfectly.

What Problem Does This Paper Address?

Most existing theory for Federated Representation Learning (FRL) assumes the over-parameterized regime. In that world, models are expressive enough to fit the ground-truth perfectly. If every client's model is big enough, the "subspace" of their data is easy to find and average.

However, edge devices face computation limitations, communication overhead, and privacy concerns that make over-parameterization impractical. In the under-parameterized regime, the model is insufficient to express all the variations in the ground-truth.

The core challenge is that in this "small model" world, a locally optimal model is often not globally optimal. Simply averaging local models (the standard FL approach) fails because local updates can be fundamentally misaligned with the best global representation.

Methods

The authors propose FLUTE (Federated Learning in Under-parameTerized REgime). Its design departs from standard FRL in three key ways:

  1. A New Loss Function: FLUTE introduces two specific regularization terms. One term preserves the "top-k" significant components of the model to prevent local over-fitting, while the second term suppresses less significant components (noise), helping the server distill the correct global subspace.
  2. Server-Side Head Optimization: Unlike popular algorithms like FedRep, which keep personalized "heads" (the last layer) strictly on the client side, FLUTE requires clients to send their heads to the server. This allows the server to perform a more sophisticated optimization that aligns the representation and the heads simultaneously.
  3. Data-Independent Initialization: FLUTE uses a simple random initialization, proving that it can still converge to a global optimum without needing a "warm start" from pre-trained weights.

Datasets

The researchers evaluated FLUTE using:

  • Synthetic Linear Datasets: Used to rigorously test the theoretical convergence rates and sample complexity.
  • CIFAR-10 and CIFAR-100: Standard computer vision benchmarks used to test the "General FLUTE" extension (using CNNs) in non-linear settings.

Key Insights and Ideas

  • The "Distillation" Requirement: In the under-parameterized regime, the server's job isn't just to average—it’s to distill. It must extract the most significant components of the data from misaligned local representations.
  • Linear Speedup: The paper proves that FLUTE achieves a "linear sample complexity speedup." As you add more clients ($M$), the number of samples required per client decreases. Specifically, the sample complexity scales as $\tilde{O}(\frac{\max\{d,M\}}{M\epsilon^2})$, where $d$ is the data dimension.
  • The Gap Matters: The theoretical analysis shows that convergence depends heavily on the "gap" ($\Delta$) between the $k$-th and $(k+1)$-th singular values of the ground-truth model. A smaller gap makes it harder for the algorithm to distinguish which features are truly important.
  • Neural Collapse: For the non-linear version, the authors draw inspiration from "Neural Collapse"—the phenomenon where last-layer features of the same class converge to a single point. They use this to design a regularization term that encourages a beneficial structure for the global model.

Key Results

Convergence of FLUTE vs. baselines across different representation dimensions (k)
  • Superior Accuracy: On CIFAR-100, FLUTE consistently outperformed state-of-the-art baselines like FedRep, FedPer, and FedRod. For example, in a partition with 100 clients and 5 classes per client, FLUTE achieved 70.59% accuracy compared to FedRep's 68.53%.
  • Robustness to "Smallness": The performance gains of FLUTE were most pronounced in "highly under-parameterized" scenarios (where the representation dimension $k$ is very small). As shown in the figure above, FLUTE achieves lower errors and faster convergence across various representation dimensions compared to baselines.
  • Exponential Convergence: Theoretically, the authors proved that FLUTE converges to the optimal low-rank model at an exponential rate, provided the per-client sample size is sufficiently large.

Limitations and Future Work

  • Communication Cost: Because FLUTE sends both the representation and the local heads to the server, it has a higher communication overhead per round than algorithms that keep heads local.
  • Sample Requirements: The theory requires that each individual client has a "sufficiently large" dataset to ensure local gradients aren't too noisy. This might be a hurdle for applications with extremely sparse data per user.
  • Future Directions: The authors suggest exploring more complex non-linear architectures and investigating how to reduce the communication cost without losing the benefits of server-side head optimization.

Summary updated

Abstract

Federated representation learning (FRL) is a popular personalized federated learning (FL) framework where clients work together to train a common representation while retaining their personalized heads. Existing studies, however, largely focus on the over-parameterized regime. In this paper, we make the initial efforts to investigate FRL in the under-parameterized regime, where the FL model is insufficient to express the variations in all ground-truth models. We propose a novel FRL algorithm FLUTE, and theoretically characterize its sample complexity and convergence rate for linear models in the under-parameterized regime. To the best of our knowledge, this is the first FRL algorithm with provable performance guarantees in this regime. FLUTE features a data-independent random initialization and a carefully designed objective function that aids the distillation of subspace spanned by the global optimal representation from the misaligned local representations. On the technical side, we bridge low-rank matrix approximation techniques with the FL analysis, which may be of broad interest. We also extend FLUTE beyond linear representations. Experimental results demonstrate that FLUTE outperforms state-of-the-art FRL solutions in both synthetic and real-world tasks.
BibTeX
@inproceedings{liu2024federated,
  author = {Renpu Liu and Cong Shen and Jing Yang},
  title = {{Federated Representation Learning in the Under-Parameterized Regime}},
  booktitle = {International Conference on Machine Learning},
  year = {2024},
  url = {https://openreview.net/forum?id=LIQYhV45D4},
}
Figure