mlsanityData to 7 Oct 2026

Approximation Rates and VC-Dimension Bounds for (P)ReLU MLP Mixture of Experts

arXiv 2402.03460 ↗First posted 5 Feb 2024stat.ML cs.LG cs.NAcited by 2

On the map: Mixture-of-experts → MoE theory and gating functions

Abstract (arXiv)

Mixture-of-Experts (MoEs) can scale up beyond traditional deep learning models by employing a routing strategy in which each input is processed by a single "expert" deep learning model. This strategy allows us to scale up the number of parameters defining the MoE while maintaining sparse activation, i.e., MoEs only load a small number of their total parameters into GPU VRAM for the forward pass depending on the input. In this paper, we provide an approximation and learning-theoretic analysis of mixtures of expert MLPs with (P)ReLU activation functions. We first prove that for every error level varepsilon>0 and every Lipschitz function f:[0,1]n→ ℝ, one can construct a MoMLP model (a Mixture-of-Experts comprising of (P)ReLU MLPs) which uniformly approximates f to varepsilon accuracy over [0,1]n, while only requiring networks of O(varepsilon-1) parameters to be loaded in memory. Additionally, we show that MoMLPs can generalize since the entire MoMLP model has a (finite) VC dimension of tildeO(LmaxnL,JW), if there are L experts and each expert has a depth and width of J and W, respectively.

Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Placed in MoE theory and gating functions, one of 12 directions in Mixture-of-experts. Builds on 55 of its 99 references that are in the map. First posted on arXiv 5 Feb 2024.

Builds on

55 of 99 references.

Closest ancestors · 1

Same direction, newest first

  1. 2019Convergence Rates for Gaussian Mixtures of Experts9 Jul

Other references · 54

  1. 2020Language Models are Few-Shot Learnerscited by 32,199
  2. 2023DINOv2: Learning Robust Visual Features without Supervisioncited by 7,764
  3. 2017Outrageously Large Neural Networks: The Sparsely-Gated Mixture-of-Experts Layercited by 3,413
  4. 2021Switch Transformers: Scaling to Trillion Parameter Models with Simple and Efficient Sparsitycited by 3,014
  5. 2017Prototypical Networks for Few-shot Learningcited by 3,001
  6. 2021Convex optimizationcited by 2,479
  7. 2020REALM: Retrieval-Augmented Language Model Pre-Trainingcited by 2,126
  8. 2024Mixtral of Expertscited by 1,785
  9. 2020GShard: Scaling Giant Models with Conditional Computation and Automatic Shardingcited by 1,601
  10. 2016Error bounds for approximations with deep ReLU networkscited by 567
  11. 2019Are Transformers universal approximators of sequence-to-sequence functions?cited by 404
  12. 2014Breaking the Curse of Dimensionality with Convex Neural Networkscited by 329
38 more
  1. 2017SkipNet: Learning Dynamic Routing in Convolutional Networkscited by 328
  2. 2017The Expressive Power of Neural Networks: A View from the Widthcited by 318
  3. 2017Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networkscited by 304
  4. 2018Optimal approximation of continuous functions by very deep ReLU networkscited by 165
  5. 2020Deep Network Approximation for Smooth Functionscited by 163
  6. 2018Adaptivity of deep ReLU network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionalitycited by 160
  7. 2018Universal approximations of invariant maps by neural networkscited by 127
  8. 2019Error bounds for approximations with deep ReLU neural networks in Ws,p normscited by 95
  9. 2021Optimal Approximation Rate of ReLU Networks in terms of Width and Depthcited by 95
  10. 2017Optimal Approximation with Sparsely Connected Deep Neural Networkscited by 90
  11. 2019The phase diagram of approximation rates for deep neural networkscited by 86
  12. 2020O(n) Connections are Expressive Enough: Universal Approximability of Sparse Transformerscited by 82
  13. 2021On the approximation of functions by tanh neural networkscited by 81
  14. 2022Pathways: Asynchronous Distributed Dataflow for MLcited by 81
  15. 2015The Optimal Sample Complexity of PAC Learningcited by 72
  16. 2022A Characterization of Multiclass Learnabilitycited by 66
  17. 2020Approximation Bounds for Random Neural Networks and Reservoir Systemscited by 52
  18. 2021Universal Approximation Theorems for Differentiable Geometric Deep Learningcited by 41
  19. 2021Deep Network Approximation: Achieving Arbitrary Accuracy with Fixed Number of Neuronscited by 41
  20. 2021Hyperbolic Busemann Learning with Ideal Prototypescited by 40
  21. 2017Universal discrete-time reservoir computers with stochastic inputs and linear readouts using non-homogeneous state-affine systemscited by 39
  22. 2019A Theoretical Analysis of the Number of Shots in Few-Shot Learningcited by 39
  23. 2018Equivalence of approximation by convolutional neural networks and fully-connected networkscited by 38
  24. 2021Elementary superexpressive activationscited by 35
  25. 2020Fading memory echo state networks are universalcited by 31
  26. 2020The universal approximation theorem for complex-valued neural networkscited by 28
  27. 2022On the Adversarial Robustness of Mixture of Expertscited by 27
  28. 2022Designing Universal Causal Deep Learning Models: The Geometric (Hyper)Transformercited by 22
  29. 2022Designing Universal Causal Deep Learning Models: The Case of Infinite-Dimensional Dynamical Systems from Stochastic Analysiscited by 22
  30. 2023Alternating Gradient Descent and Mixture-of-Experts for Integrated Multimodal Perceptioncited by 19
  31. 2023Global universal approximation of functional input maps on weighted spacescited by 19
  32. 2020Universal Approximation Power of Deep Residual Neural Networks via Nonlinear Control Theorycited by 17
  33. 2023Optimal rates of approximation by shallow ReLUk neural networks and applications to nonparametric regressioncited by 15
  34. 2022Minimal Width for Universal Property of Deep RNNcited by 12
  35. 2023Rates of Approximation by ReLU Shallow Neural Networkscited by 12
  36. 2021Deep Neural Networks with ReLU-Sine-Exponential Activations Break Curse of Dimensionality in Approximation on H"older Classcited by 7
  37. 2020Approximation Theory of Tree Tensor Networks: Tensorized Univariate Functions -- Part Icited by 6
  38. 2022Do ReLU Networks Have An Edge When Approximating Compactly-Supported Functions?cited by 6

50 most cited of 54 All 54 (JSON)

Built on by

Cited by year

Citing papers per year: 2024: 1; 2025: 1.

2 papers.

  1. 2024Low-dimensional approximations of the conditional law of Volterra processes: a non-positive curvature approachcited by 3
  2. 2025Generative Market Equilibrium Models with Stable Adversarial Learning via Reinforcementcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025On the Expressive Power of Mixture-of-Experts for Structured Complex Tasks
  2. 2026Generalization and Scaling Laws for Mixture-of-Experts Transformers
  3. 2026The Rise of Sparse Mixture-of-Experts: A Survey from Algorithmic Foundations to Decentralized Architectures and Vertical Domain Applications
  4. 2022Towards Understanding Mixture of Experts in Deep Learning
  5. 2026∞-MoE: Generalizing Mixture of Experts to Infinite Experts
  6. 2024SEER-MoE: Sparse Expert Efficiency through Regularization for Mixture-of-Experts
  7. 2026DECO: Sparse Mixture-of-Experts with Dense-Comparable Performance on End-Side Devices
  8. 2025Joint MoE Scaling Laws: Mixture of Experts Can Be Memory Efficient