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.
Introduction
In the current machine learning landscape, the "bigger is better" philosophy often assumes that models are over-parameterized—possessing more than enough capacity to fit the underlying data. However, this assumption is frequently violated in real-world Federated Learning (FL) scenarios, such as those involving low-power IoT sensors or mobile devices. In these contexts, models are often under-parameterized, meaning they lack the capacity to perfectly capture the complexity of every client's local data.
Presented at ICML 2024, the paper Federated Representation Learning in the Under-Parameterized Regime addresses this overlooked challenge. The authors introduce FLUTE (Federated Learning in Under-parameTerized REgime), a novel algorithm designed to help small models learn powerful shared representations across decentralized networks, even when those models are "too small" for the task at hand.
The Challenge of Under-Parameterization
Federated Representation Learning (FRL) typically involves a fleet of clients collaborating to learn a global feature extractor (the representation) while maintaining individual local prediction heads.
In the under-parameterized regime, a significant hurdle arises: a "locally optimal" model for one client may be completely misaligned with the "globally optimal" subspace. Standard FL approaches that rely on simple averaging of local models often fail here, as the average of misaligned local optima does not necessarily result in a global optimum. Without a specialized approach, the global model may never converge to the best possible low-rank solution.
The FLUTE Framework
FLUTE departs from standard FRL through two primary technical innovations designed to handle model constraints:
1. Dual-Term Regularization
The authors developed a specialized loss function incorporating two distinct penalty terms:
- Term I: Prevents local models from overfitting to client-specific noise by preserving only the most significant "top-k" components of the data.
- Term II: Suppresses less important features, allowing the server to effectively "distill" the correct shared subspace from the noisy, misaligned updates provided by clients.
2. Server-Side Refinement and Neural Collapse
Unlike algorithms such as FedRep, which only optimize representations on the server, FLUTE requires clients to transmit both their representation layers and their local heads. The server then performs a global optimization step to align these components before broadcasting them back. To extend FLUTE to non-linear models like Convolutional Neural Networks (CNNs), the authors utilize principles from Neural Collapse—a phenomenon where the last-layer features of a trained model naturally orient into symmetric geometric structures.
Theoretical Guarantees
FLUTE is the first FRL algorithm to offer provable performance guarantees in the under-parameterized regime. Key theoretical findings include:
- Exponential Convergence: Despite the non-convex nature of the problem, FLUTE converges to the optimal low-rank model exponentially fast, provided it starts with a data-independent random initialization.
- Linear Speedup: The framework achieves a "linear sample complexity speedup," meaning that as the number of clients ($M$) increases, the number of samples required per client decreases at a rate of $1/M$.
Experimental Results
The researchers validated FLUTE using synthetic datasets and real-world benchmarks (CIFAR-10 and CIFAR-100), simulating resource constraints by limiting samples and classes per client.
- Superior Accuracy: On CIFAR-100 (100 clients, 5 classes each), FLUTE achieved 79.56% accuracy, outperforming FedRep (78.62%) and FedAvg-FT (78.34%).
- Robustness: The performance gap between FLUTE and competing methods widened as models became more under-parameterized (i.e., when the model capacity $k$ was very small relative to data complexity).
- Subspace Recovery: In synthetic tests, FLUTE recovered the ground-truth representation subspace with high precision, whereas existing methods often struggled to escape poor local alignments.
Limitations and Future Work
While FLUTE provides a robust roadmap for edge AI, it faces certain trade-offs. The requirement to transmit both representations and local heads increases communication overhead compared to representation-only methods. Furthermore, while empirical results on CNNs are strong, the rigorous mathematical proofs for convergence are currently centered on linear models. Future research will likely focus on extending these proofs to deep neural networks and integrating privacy-preserving techniques like Differential Privacy to protect the transmitted local heads.
By focusing on the constraints of real-world hardware, FLUTE offers a theoretical and practical foundation for deploying efficient, high-performing AI on the edge.
Summary updated