mlsanityData to 7 Oct 2026

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

arXiv 2306.04073 ↗First posted 7 Jun 2023cs.LGcited by 35

On the map: Mixture-of-experts → Expert routing strategies

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.

Key facts. Cited by 35 papers in the map (data through 7 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.

Builds on

45 of 64 references.

Closest ancestors · 2

Same direction, newest first

  1. 2022Mixture-of-Experts with Expert Choice Routing18 Feb
  2. 2021Switch Transformers: Scaling to Trillion Parameter Models with Simple and Efficient Sparsity11 Jan

Other references · 43

  1. 2017Attention Is All You Needcited by 59,932
  2. 2014Deep Learning Face Attributes in the Wildcited by 3,679
  3. 2017Outrageously Large Neural Networks: The Sparsely-Gated Mixture-of-Experts Layercited by 3,413
  4. 2016Wide Residual Networkscited by 3,057
  5. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  6. 2013Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computationcited by 2,031
  7. 2020GShard: Scaling Giant Models with Conditional Computation and Automatic Shardingcited by 1,601
  8. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 784
  9. 2021Scaling Vision with Sparse Mixture of Expertscited by 740
  10. 2019Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descentcited by 732
  11. 2018On Lazy Training in Differentiable Programmingcited by 671
  12. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 572
31 more
  1. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 562
  2. 2018Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layerscited by 340
  3. 2021BASE Layers: Simplifying Training of Large, Sparse Modelscited by 315
  4. 2020Towards Understanding Ensemble, Knowledge Distillation and Self-Distillation in Deep Learningcited by 292
  5. 2013Learning Factored Representations in a Deep Mixture of Expertscited by 275
  6. 2019CondConv: Conditionally Parameterized Convolutions for Efficient Inferencecited by 273
  7. 2018Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Datacited by 260
  8. 2019Linearized two-layers neural networks in high dimensioncited by 155
  9. 2020When Do Neural Networks Outperform Kernel Methods?cited by 150
  10. 2019Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networkscited by 120
  11. 2020Feature Purification: How Adversarial Training Performs Robust Deep Learningcited by 107
  12. 2019On the Power and Limitations of Random Features for Understanding Neural Networkscited by 103
  13. 2017Recovery Guarantees for One-hidden-layer Neural Networkscited by 94
  14. 2019What Can ResNet Learn Efficiently, Going Beyond Kernels?cited by 91
  15. 2019Limitations of Lazy Training of Two-layers Neural Networkscited by 87
  16. 2017SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Datacited by 79
  17. 2019Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networkscited by 79
  18. 2020Learning Parities with Neural Networkscited by 77
  19. 2023A Theoretical Understanding of Shallow Vision Transformers: Learning, Generalization, and Sample Complexitycited by 77
  20. 2017Hard Mixtures of Experts for Large Scale Weakly Supervised Visioncited by 67
  21. 2016Network of Experts for Large-Scale Image Categorizationcited by 54
  22. 2022Towards Understanding Mixture of Experts in Deep Learningcited by 52
  23. 2022A Theoretical Analysis on Feature Learning in Neural Networks: Emergence from Inputs and Advantage over Fixed Featurescited by 49
  24. 2021Quantifying the Benefit of Using Differentiable Learning over Tangent Kernelscited by 41
  25. 2020Fast Learning of Graph Neural Networks with Guaranteed Generalizability: One-hidden-layer Casecited by 24
  26. 2022Generalization Guarantee of Training Graph Convolutional Networks with Graph Topology Samplingcited by 23
  27. 2018Guaranteed Recovery of One-Hidden-Layer Neural Networks via Cross Entropycited by 22
  28. 2020Computational Separation Between Convolutional and Fully-Connected Networkscited by 19
  29. 2017Learning Non-overlapping Convolutional Neural Networks with Multiple Kernelscited by 14
  30. 2022Learning and generalization of one-hidden-layer neural networks, going beyond standard Gaussian datacited by 8
  31. 2019On the Learning Dynamics of Two-layer Nonlinear Convolutional Neural Networkscited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 2; 2024: 10; 2025: 16; 2026: 7.

35 papers.

Sort:

By area:

  1. 2024A Survey on Inference Optimization Techniques for Mixture of Experts Modelscited by 46
  2. 2024How Do Nonlinear Transformers Learn and Generalize in In-Context Learning?cited by 35
  3. 2025FlyLoRA: Boosting Task Decoupling and Parameter Efficiency via Implicit Rank-Wise Mixture-of-Expertscited by 34
  4. 2024How Far Are We From AGI: Are LLMs All We Need?cited by 31
  5. 2025SPMTrack: Spatio-Temporal Parameter-Efficient Fine-Tuning with Mixture of Experts for Scalable Visual Trackingcited by 23
  6. 2024A Provably Effective Method for Pruning Experts in Fine-tuned Sparse Mixture-of-Expertscited by 21
  7. 2025LiMoE: Mixture of LiDAR Representation Learners from Automotive Scenescited by 19
  8. 2023From Google Gemini to OpenAI Q* (Q-Star): A Survey of Reshaping the Generative Artificial Intelligence (AI) Research Landscapecited by 18
  9. 2024LocMoE: A Low-Overhead MoE for Large Language Model Trainingcited by 18
  10. 2023On the Convergence and Sample Complexity Analysis of Deep Q-Networks with ε-Greedy Explorationcited by 17
  11. 2025Mixture of Experts (MoE): A Big Data Perspectivecited by 17
  12. 2024What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encodingcited by 14
23 more
  1. 2025eMoE: Task-aware Memory Efficient Mixture-of-Experts-Based (MoE) Model Inferencecited by 11
  2. 2025Learning Soft Sparse Shapes for Efficient Time-Series Classificationcited by 10
  3. 2025MoE3D: Mixture of Experts meets Multi-Modal 3D Understandingcited by 6
  4. 2026Sparse Models, Sparse Safety: Unsafe Routes in Mixture-of-Experts LLMscited by 6
  5. 2024SF-DQN: Provable Knowledge Transfer using Successor Feature for Deep Reinforcement Learningcited by 5
  6. 2025Robust Experts: the Effect of Adversarial Training on CNNs with Sparse Mixture-of-Experts Layerscited by 4
  7. 2024Low-dimensional approximations of the conditional law of Volterra processes: a non-positive curvature approachcited by 3
  8. 2025How Can Mamba Learn In Context with Outliers and Generalize Provably?cited by 2
  9. 2025Expert Merging in Sparse Mixture of Experts with Nash Bargainingcited by 2
  10. 2024ViMoE: An Empirical Study of Designing Vision Mixture-of-Expertscited by 1
  11. 2025Multi-Expert Learning Framework with the State Space Model for Optical and SAR Image Registrationcited by 1
  12. 2025Guided by the Experts: Provable Feature Learning Dynamic of Soft-Routed Mixture-of-Expertscited by 1
  13. 2026Robustness of Mixtures of Experts to Feature Noisecited by 1
  14. 2026Efficient Quantization of Mixture-of-Experts with Theoretical Generalization Guaranteescited by 1
  15. 2026View-Aware Semantic Alignment for Aerial-Ground Person Re-Identificationcited by 1
  16. 2024Filtered not Mixed: Stochastic Filtering-Based Online Gating for Mixture of Large Language Modelscited by 0
  17. 2025ISALux: Illumination and Segmentation Aware Transformer Employing Mixture of Experts for Low Light Image Enhancementcited by 0
  18. 2025SHMoAReg: Spark Deformable Image Registration via Spatial Heterogeneous Mixture of Experts and Attention Headscited by 0
  19. 2025MoME: Mixture of Visual Language Medical Experts for Medical Imaging Segmentationcited by 0
  20. 2025Life-IQA: Boosting Blind Image Quality Assessment through GCN-enhanced Layer Interaction and MoE-based Feature Decouplingcited by 0
  21. 2026Robust Heterogeneous Analog-Digital Computing for Mixture-of-Experts Models with Theoretical Generalization Guaranteescited by 0
  22. 2026Improving Ensemble Forecasts of Abnormally Deflecting Tropical Cyclones with Fused Atmosphere-Ocean-Terrain Datacited by 0
  23. 2026WILD-SAM: Phase-Aware Expert Adaptation of SAM for Landslide Detection in Wrapped InSAR Interferogramscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Improving Routing in Sparse Mixture of Experts with Graph of Tokens
  2. 2026Dense Mixture-of-Experts as a Reparameterized Wide FFN: A Granularity Sweep at Fixed Compute
  3. 2026Towards a Statistical Understanding of Mixture-of-Experts
  4. 2023Merge, Then Compress: Demystify Efficient SMoE with Hints from Its Routing Policy
  5. 2026L2R: Low-Rank and Lipschitz-Controlled Routing for Mixture-of-Experts
  6. 2025Input Domain Aware MoE: Decoupling Routing Decisions from Task Optimization in Mixture of Experts
  7. 2026Distribution-Consistent Inference for Dynamic Sparse Mixture-of-Experts
  8. 2026Generalization and Scaling Laws for Mixture-of-Experts Transformers