Patch-level Routing in Mixture-of-Experts is Provably Sample-efficient for Convolutional Neural Networks

Mohammed Nowaz Rabbani Chowdhury, Shuai Zhang, Meng Wang, Sijia Liu, Pin-Yu Chen

TL;DR

This paper provides the first theoretical proof that patch-level routing in Mixture-of-Experts (pMoE) is significantly more sample-efficient than standard Convolutional Neural Networks (CNNs). By mathematically demonstrating that pMoE routers act as "noise filters"—selecting only class-discriminative patches and ignoring irrelevant ones—the authors show that these models can achieve superior generalization with a fraction of the training data and computational cost.

What Problem Does This Paper Address?

Mixture-of-Experts (MoE) has become a cornerstone of modern "mega-models," allowing researchers to scale networks to trillions of parameters by only activating a small subset of the network (the "experts") for any given input. While MoE is empirically successful in reducing computation, its theoretical foundations remain shaky.

Specifically, in computer vision, a popular technique called patch-level routing (pMoE) divides an image into small patches and sends only the most "important" ones to specific experts. While this works great in practice—often maintaining accuracy while slashing inference costs by 50%—we haven't known why it works from a mathematical standpoint. Does it actually learn better, or is it just a clever engineering trick? This paper tackles the "why" by analyzing the sample complexity (how much data is needed to learn) of pMoE versus standard CNNs.

Methods

The authors focus on a supervised binary classification task using a mixture of two-layer CNNs. Their approach involves:

Patch-level routing architecture
  1. Patch-level Routing: Unlike conventional MoE that routes entire samples, pMoE divides an input into $n$ patches and selects only $l$ patches ($l \ll n$) to send to each expert.
  2. Two Training Modes: They analyze both Separate-training (where routers are trained first and then fixed) and Joint-training (where routers and experts learn simultaneously).
  3. Theoretical Generalization Analysis: They use a structured data model where images consist of "class-discriminative" patterns (the signal) and "class-irrelevant" patterns (the noise). They then derive the "sample complexity"—the number of training samples required to reach a certain error rate $\epsilon$.
  4. Architecture: For empirical validation, they replace the last convolutional layer of a ten-layer Wide Residual Network (WRN) with a pMoE layer.

Datasets

The researchers validated their theory using several benchmarks:

  • Synthetic MNIST: A custom dataset where MNIST digits are placed among multiple "noise" patches to test the router's ability to find the "signal."
  • CIFAR-10: Used in its standard form and with added ImageNet-based background noise to test robustness.
  • CIFAR-Vehicles: A variant where vehicle images are placed in specific quadrants of a larger, noisier frame.
  • CelebA: A large-scale face attributes dataset used for binary classification (e.g., "smiling") and multiclass tasks, as well as testing against spurious correlations (like hair color).

Key Insights and Ideas

  • The Router as a Discriminative Filter: The core "aha moment" is that a properly trained router doesn't just save compute; it improves the signal-to-noise ratio for the experts. By filtering out label-irrelevant patches, the experts can focus on learning the actual features that define a class without being distracted by background clutter.
  • Polynomial Sample Efficiency: The math reveals a massive gap. The sample complexity of pMoE is lower than a standard CNN by a factor polynomial in $n/l$. Essentially, if you only need 2 patches out of 20 to identify an object, pMoE needs significantly fewer total images to "solve" the task compared to a CNN that looks at everything.
  • Avoiding Spurious Correlations: Standard CNNs often "cheat" by learning background features (like a blue sky always appearing with planes). Because pMoE routers learn to pick specific patches, they can theoretically learn to ignore these spurious background patches, leading to more robust models.

Key Results

Test accuracy vs. Number of training samples
  • Data Efficiency: On the CelebA "smiling" task, WRN-pMoE required less than 1/5th of the training samples needed by a standard WRN to achieve 86% accuracy. As shown in the experiments, pMoE consistently achieves higher test accuracy with fewer training samples compared to standard CNNs.
  • Computational Savings: pMoE achieved similar or better accuracy than its single-expert counterpart while using 20% less training compute and 50% less inference compute.
  • Faster Convergence: In experiments, pMoE models converged significantly faster than standard CNNs, requiring fewer iterations to reach zero training error.
  • Robustness to Noise: In the "CIFAR-10 with ImageNet noise" test, pMoE maintained high accuracy where standard CNNs struggled, proving the "filtering" theory holds in practice.

Limitations and Future Work

While groundbreaking, the paper notes a few areas for further exploration:

  • Architectural Scope: The theoretical analysis is primarily based on two-layer CNN experts. While empirical results on WRNs are promising, a formal proof for deeper, more complex architectures (like full Vision Transformers) is still needed.
  • Router Dynamics: The joint-training analysis relies on an assumption about router behavior that is verified empirically but not yet proven from first principles.
  • Scaling Sparsity: The authors suggest that future work could involve combining pMoE with other sparsification techniques (like weight pruning) to further push the boundaries of efficiency.

Summary updated

Abstract

In deep learning, mixture-of-experts (MoE) activates one or few experts (sub-networks) on a per-sample or per-token basis, resulting in significant computation reduction. The recently proposed patch-level routing in MoE (pMoE) divides each input into $n$ patches (or tokens) and sends $l$ patches ($l\ll n$) to each expert through prioritized routing. pMoE has demonstrated great empirical success in reducing training and inference costs while maintaining test accuracy. However, the theoretical explanation of pMoE and the general MoE remains elusive. Focusing on a supervised classification task using a mixture of two-layer convolutional neural networks (CNNs), we show for the first time that pMoE provably reduces the required number of training samples to achieve desirable generalization (referred to as the sample complexity) by a factor in the polynomial order of $n/l$, and outperforms its single-expert counterpart of the same or even larger capacity. The advantage results from the discriminative routing property, which is justified in both theory and practice that pMoE routers can filter label-irrelevant patches and route similar class-discriminative patches to the same expert. Our experimental results on MNIST, CIFAR-10, and CelebA support our theoretical findings on pMoE's generalization and show that pMoE can avoid learning spurious correlations.
BibTeX
@inproceedings{chowdhury2023patch,
  author = {Mohammed Nowaz Rabbani Chowdhury and Shuai Zhang and Meng Wang and Sijia Liu and Pin-Yu Chen},
  title = {{Patch-level Routing in Mixture-of-Experts is Provably Sample-efficient for Convolutional Neural Networks}},
  booktitle = {International Conference on Machine Learning},
  year = {2023},
  url = {https://openreview.net/forum?id=kNzaZ0jbIg},
}
Figure