TL;DR
This paper introduces DC-NAS, a novel approach to Neural Architecture Search (NAS) for resource-constrained Federated Learning (FL) systems. By employing a "divide-and-conquer" strategy with a unique diversified sampling method and channel pruning, DC-NAS significantly reduces computational resources and training complexity while achieving competitive accuracy compared to full-scale FL-NAS.
What Problem Does This Paper Address?
Federated Learning (FL) enables privacy-preserving machine learning on distributed edge devices, but designing efficient neural network architectures for these resource-limited environments remains a significant challenge. Traditional Neural Architecture Search (NAS) methods are often computationally expensive and not well-suited for the constraints of FL. Existing FL approaches typically assume a fixed architecture, which may not be optimal for diverse edge devices. This paper tackles the problem of performing NAS efficiently within FL systems, aiming to reduce both search time and the computational burden on individual devices.
Methods
The core of DC-NAS is a "divide-and-conquer" strategy applied to NAS in an FL setting. The approach involves two main stages:
- Supernet Sampling and Pruning: The server first samples subnetworks from a larger supernet for each client. This is achieved by pruning the connection topology of the supernet. Subsequently, at the client level, channel pruning is applied to further reduce the complexity of the sampled subnet to fit within the client's specific resource constraints.
- Diversified Sampling Strategy: To systematically explore the vast NAS search space, the authors propose a novel diversified sampling strategy. This method treats the search space as an n-dimensional hypercube. In early rounds, it aims to maximize the distance between sampled subnetworks (exploration), and as training progresses, it progressively reduces this distance to exploit promising regions (exploitation). This is visualized as a spiral pattern in the search space, balancing exploration and exploitation.
The training then proceeds by clients training their pruned subnets locally, and their gradients are aggregated by the server to update the supernet.
Datasets
The authors evaluate DC-NAS on the following standard image classification datasets:
- CIFAR10
- CIFAR100
- EMNIST
- TinyImagenet
Key Insights and Ideas
- Balancing Exploration and Exploitation in FL-NAS: The diversified sampling strategy is a key innovation, providing a structured way to navigate the NAS search space in FL. Unlike purely random or purely exploitative methods, it dynamically adjusts its approach to efficiently discover good architectures.
- Resource Efficiency through Pruning: Combining server-side connection pruning with client-side channel pruning is crucial for adapting to diverse device capabilities and significantly reducing the computational load on edge devices.
- "Pieces of a Puzzle" Aggregation: The structured sampling approach leads to subnets that, when aggregated, fit together more coherently, contributing to smoother training and better supernet updates.
- Near Iso-Accuracy with Substantial Resource Savings: The ability to achieve accuracy comparable to full-scale FL-NAS while using significantly fewer resources (e.g., 50% fewer) is a major practical advantage.
Key Results
- DC-NAS outperforms other sampling strategies like random sampling and Hadamard sampling in terms of test accuracy.
- The method achieves near iso-accuracy compared to full-scale federated NAS, but with approximately 50% fewer computational resources.
- Experiments on CIFAR10, CIFAR100, EMNIST, and TinyImagenet demonstrate the effectiveness of DC-NAS across various datasets and aspects of federated learning, including scalability and non-IID data scenarios.
- The diversified sampling strategy shows a significant performance improvement over random sampling, especially as training progresses.
- The paper demonstrates that sampled subnets can achieve near iso-performance off-the-shelf compared to the supernet, without requiring extensive finetuning, unlike some baseline methods.
Limitations and Future Work
- Server Reliability: The current approach relies on a central server to orchestrate the process, making it dependent on the server's reliability.
- Operation Compute Load Assumption: The current sampling method assumes all operations have similar compute costs, which might not hold true in practice.
- Theoretical Analysis: The paper presents empirical evidence but suggests that a theoretical analysis of the strategy would be valuable for future work.
- Scalability to Larger Search Spaces/Datasets: While scalability with respect to the number of clients was explored, further investigation into scaling with larger search spaces and datasets is recommended.
- Decentralized Approach: The authors suggest exploring a decentralized peer-to-peer version of the problem to overcome server dependency.
- Further Compression: Standard pruning and quantization techniques could be integrated to further compress final architectures before deployment.
- Explicit Operation Weighting: Explicitly weighting operations based on their actual compute load during sampling could lead to further efficiency gains.
Summary updated