Abstract
Mixture-of-Experts (MoE) has gained significant traction for its ability to scale model capacity while maintaining constant computational costs. In computer vision, patch-level routing (pMoE) has emerged as a particularly effective variant, yet its theoretical advantages have remained largely unexplored. This paper provides the first formal proof that pMoE significantly reduces sample complexity compared to standard convolutional neural networks (CNNs). By demonstrating that routers learn to filter out label-irrelevant noise, we show that pMoE achieves superior generalization with a fraction of the training data and computation. Empirical results on MNIST, CIFAR, and CelebA benchmarks validate our theoretical findings, demonstrating up to a 5x improvement in sample efficiency.
Introduction
Deep learning models are notoriously data-hungry and computationally intensive. To mitigate these costs, Mixture-of-Experts (MoE) architectures activate only a sparse subset of the network for any given input. In the domain of computer vision, this is often implemented via patch-level routing (pMoE), where an image is decomposed into patches and a router directs only the most salient patches to specific experts. While pMoE has demonstrated empirical success—often reducing training and inference costs by 50% without compromising accuracy—the underlying theoretical mechanisms for its improved generalization remained a mystery. This research addresses this gap by providing a mathematical foundation for the sample efficiency of pMoE in CNNs.
Theoretical Framework and Methodology
To analyze the performance of pMoE, the authors utilize a supervised binary classification task centered on a mixture of two-layer CNNs. They introduce a structured data model where each input consists of $n$ patches: one class-discriminative patch (the signal) and $n-1$ class-irrelevant patches (the noise).
The model employs a learnable router to select $l$ patches (where $l \ll n$) to be processed by each expert. The study investigates two primary training regimes:
- Separate-training: The router is trained first to identify discriminative patches, followed by the training of the experts.
- Joint-training: Routers and experts are optimized simultaneously using mini-batch Stochastic Gradient Descent (SGD).
Through rigorous mathematical analysis, the authors derive bounds for both sample complexity (the number of training images required) and model complexity (the number of neurons required) to achieve a target generalization error $\epsilon$.
Key Insights: The Filter Effect and Efficiency Gaps
The "Filter" Effect
The core theoretical contribution is the identification of the "filter effect." A properly trained router acts as a discriminative filter, learning to drop label-irrelevant patches. This reduction in input noise minimizes the "interference" that experts encounter during the learning process, allowing them to converge on discriminative features more rapidly.
Polynomial Efficiency Gap
The paper proves a significant efficiency gap between pMoE and standard dense CNNs. Specifically, pMoE reduces sample complexity by a factor in the polynomial order of $(n/l)^8$ and model complexity by $(n/l)^{10}$. This suggests that by routing only a small subset of relevant patches, the model requires exponentially less data to learn the underlying patterns compared to a model that processes the entire image indiscriminately.
Robustness to Spurious Features
Because the router selects patches based on their global discriminative power across the dataset, it is less susceptible to "spurious" features—such as background elements that may be accidentally correlated with a label in a small training set. This selection mechanism inherently makes the final model more robust to distribution shifts.
Empirical Validation
The theoretical claims were validated across several benchmarks:
- Synthetic MNIST: Using images constructed from 16 patches (where specific digits represent signal and others represent noise), experiments confirmed that as the number of patches per expert ($l$) decreases, sample efficiency improves in alignment with the theoretical predictions.
- CelebA: On the "smiling" classification task, a pMoE-enhanced Wide Residual Network (WRN-pMoE) required less than 20% of the training samples to reach 86% accuracy compared to a standard WRN. Additionally, pMoE achieved higher accuracy while reducing training FLOPs by approximately 43-50%.
- CIFAR-10 Variants: Tests on "CIFAR-10 with ImageNet noise" demonstrated the model's superior ability to handle complex, noisy backgrounds by effectively filtering out irrelevant patches.
Conclusion and Future Work
This work provides a rigorous theoretical justification for the empirical success of patch-level routing in MoE architectures. By proving that pMoE is more sample-efficient and computationally lean than standard CNNs, the authors pave the way for more efficient large-scale vision models.
However, certain limitations remain. The current formal proofs are focused on two-layer CNNs; extending these proofs to deeper, multi-layer MoE architectures remains an open challenge. Furthermore, while the joint-training regime is verified empirically, a purely theoretical proof of router convergence in this setting is a subject for future research. Finally, exploring the application of these principles to Vision Transformers (ViTs), where Multi-Layer Perceptrons act similarly to non-overlapping CNNs, represents a promising next step for the field.
Summary updated