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

arXiv: https://arxiv.org/abs/2306.04073 · HTML: https://mlsanity.com/paper/2306.04073/

## Key facts

- Cited by 35 papers in the map (data through 14 Oct 2026).
- Placed in Expert routing strategies, one of 12 directions in Mixture-of-experts.
- Builds on 45 of its 64 references that are in the map.
- First posted on arXiv 7 Jun 2023.

## Placed in

- Mixture-of-experts / [Expert routing strategies](https://mlsanity.com/moe/expert-routing-strategies/)

## Builds on (most cited first, 30 of 45)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Deep Learning Face Attributes in the Wild](https://mlsanity.com/paper/1411.7766/) (2014)
- [Outrageously Large Neural Networks: The Sparsely-Gated Mixture-of-Experts Layer](https://mlsanity.com/paper/1701.06538/) (2017)
- [Switch Transformers: Scaling to Trillion Parameter Models with Simple and Efficient Sparsity](https://mlsanity.com/paper/2101.03961/) (2021)
- [Wide Residual Networks](https://mlsanity.com/paper/1605.07146/) (2016)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computation](https://mlsanity.com/paper/1308.3432/) (2013)
- [GShard: Scaling Giant Models with Conditional Computation and Automatic Sharding](https://mlsanity.com/paper/2006.16668/) (2020)
- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [Scaling Vision with Sparse Mixture of Experts](https://mlsanity.com/paper/2106.05974/) (2021)
- [Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descent](https://mlsanity.com/paper/1902.06720/) (2019)
- [On Lazy Training in Differentiable Programming](https://mlsanity.com/paper/1812.07956/) (2018)
- [Mixture-of-Experts with Expert Choice Routing](https://mlsanity.com/paper/2202.09368/) (2022)
- [Gradient Descent Finds Global Minima of Deep Neural Networks](https://mlsanity.com/paper/1811.03804/) (2018)
- [Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/1901.08584/) (2019)
- [Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers](https://mlsanity.com/paper/1811.04918/) (2018)
- [BASE Layers: Simplifying Training of Large, Sparse Models](https://mlsanity.com/paper/2103.16716/) (2021)
- [Towards Understanding Ensemble, Knowledge Distillation and Self-Distillation in Deep Learning](https://mlsanity.com/paper/2012.09816/) (2020)
- [Learning Factored Representations in a Deep Mixture of Experts](https://mlsanity.com/paper/1312.4314/) (2013)
- [CondConv: Conditionally Parameterized Convolutions for Efficient Inference](https://mlsanity.com/paper/1904.04971/) (2019)
- [Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data](https://mlsanity.com/paper/1808.01204/) (2018)
- [Linearized two-layers neural networks in high dimension](https://mlsanity.com/paper/1904.12191/) (2019)
- [When Do Neural Networks Outperform Kernel Methods?](https://mlsanity.com/paper/2006.13409/) (2020)
- [Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks](https://mlsanity.com/paper/1909.12292/) (2019)
- [Feature Purification: How Adversarial Training Performs Robust Deep Learning](https://mlsanity.com/paper/2005.10190/) (2020)
- [On the Power and Limitations of Random Features for Understanding Neural Networks](https://mlsanity.com/paper/1904.00687/) (2019)
- [Recovery Guarantees for One-hidden-layer Neural Networks](https://mlsanity.com/paper/1706.03175/) (2017)
- [What Can ResNet Learn Efficiently, Going Beyond Kernels?](https://mlsanity.com/paper/1905.10337/) (2019)
- [Limitations of Lazy Training of Two-layers Neural Networks](https://mlsanity.com/paper/1906.08899/) (2019)
- [SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Data](https://mlsanity.com/paper/1710.10174/) (2017)

## Built on by (most cited first, 30 of 35)

- [A Survey on Inference Optimization Techniques for Mixture of Experts Models](https://mlsanity.com/paper/2412.14219/) (2024)
- [How Do Nonlinear Transformers Learn and Generalize in In-Context Learning?](https://mlsanity.com/paper/2402.15607/) (2024)
- [FlyLoRA: Boosting Task Decoupling and Parameter Efficiency via Implicit Rank-Wise Mixture-of-Experts](https://mlsanity.com/paper/2510.08396/) (2025)
- [How Far Are We From AGI: Are LLMs All We Need?](https://mlsanity.com/paper/2405.10313/) (2024)
- [SPMTrack: Spatio-Temporal Parameter-Efficient Fine-Tuning with Mixture of Experts for Scalable Visual Tracking](https://mlsanity.com/paper/2503.18338/) (2025)
- [A Provably Effective Method for Pruning Experts in Fine-tuned Sparse Mixture-of-Experts](https://mlsanity.com/paper/2405.16646/) (2024)
- [LocMoE: A Low-Overhead MoE for Large Language Model Training](https://mlsanity.com/paper/2401.13920/) (2024)
- [LiMoE: Mixture of LiDAR Representation Learners from Automotive Scenes](https://mlsanity.com/paper/2501.04004/) (2025)
- [From Google Gemini to OpenAI Q* (Q-Star): A Survey of Reshaping the Generative Artificial Intelligence (AI) Research Landscape](https://mlsanity.com/paper/2312.10868/) (2023)
- [Mixture of Experts (MoE): A Big Data Perspective](https://mlsanity.com/paper/2501.16352/) (2025)
- [On the Convergence and Sample Complexity Analysis of Deep Q-Networks with ε-Greedy Exploration](https://mlsanity.com/paper/2310.16173/) (2023)
- [What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encoding](https://mlsanity.com/paper/2406.01977/) (2024)
- [eMoE: Task-aware Memory Efficient Mixture-of-Experts-Based (MoE) Model Inference](https://mlsanity.com/paper/2503.06823/) (2025)
- [Learning Soft Sparse Shapes for Efficient Time-Series Classification](https://mlsanity.com/paper/2505.06892/) (2025)
- [Sparse Models, Sparse Safety: Unsafe Routes in Mixture-of-Experts LLMs](https://mlsanity.com/paper/2602.08621/) (2026)
- [MoE3D: Mixture of Experts meets Multi-Modal 3D Understanding](https://mlsanity.com/paper/2511.22103/) (2025)
- [SF-DQN: Provable Knowledge Transfer using Successor Feature for Deep Reinforcement Learning](https://mlsanity.com/paper/2405.15920/) (2024)
- [Robust Experts: the Effect of Adversarial Training on CNNs with Sparse Mixture-of-Experts Layers](https://mlsanity.com/paper/2509.05086/) (2025)
- [Low-dimensional approximations of the conditional law of Volterra processes: a non-positive curvature approach](https://mlsanity.com/paper/2405.20094/) (2024)
- [Expert Merging in Sparse Mixture of Experts with Nash Bargaining](https://mlsanity.com/paper/2510.16138/) (2025)
- [How Can Mamba Learn In Context with Outliers and Generalize Provably?](https://mlsanity.com/paper/2510.00399/) (2025)
- [Guided by the Experts: Provable Feature Learning Dynamic of Soft-Routed Mixture-of-Experts](https://mlsanity.com/paper/2510.07205/) (2025)
- [Efficient Quantization of Mixture-of-Experts with Theoretical Generalization Guarantees](https://mlsanity.com/paper/2604.06515/) (2026)
- [ViMoE: An Empirical Study of Designing Vision Mixture-of-Experts](https://mlsanity.com/paper/2410.15732/) (2024)
- [Multi-Expert Learning Framework with the State Space Model for Optical and SAR Image Registration](https://mlsanity.com/paper/2507.04397/) (2025)
- [Robustness of Mixtures of Experts to Feature Noise](https://mlsanity.com/paper/2601.14792/) (2026)
- [View-Aware Semantic Alignment for Aerial-Ground Person Re-Identification](https://mlsanity.com/paper/2605.18192/) (2026)
- [Filtered not Mixed: Stochastic Filtering-Based Online Gating for Mixture of Large Language Models](https://mlsanity.com/paper/2406.02969/) (2024)
- [ISALux: Illumination and Segmentation Aware Transformer Employing Mixture of Experts for Low Light Image Enhancement](https://mlsanity.com/paper/2508.17885/) (2025)
- [SHMoAReg: Spark Deformable Image Registration via Spatial Heterogeneous Mixture of Experts and Attention Heads](https://mlsanity.com/paper/2509.20073/) (2025)

## Abstract (arXiv)

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 underlinepatch-level routing in underlineMoE (pMoE) divides each input into n patches (or tokens) and sends l patches (lll 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.