# Sparsity Saves Compute, Not Samples: Oracle Inequalities for Dense and Sparse Mixture of Experts

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in MoE theory and gating functions, one of 12 directions in Mixture-of-experts.
- Builds on 10 of its 48 references that are in the map.
- First posted on arXiv 10 Oct 2026.

## Placed in

- Mixture-of-experts / [MoE theory and gating functions](https://mlsanity.com/moe/moe-theory-and-gating-functions/)

## Builds on (most cited first, 10 of 10)

- [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)
- [GShard: Scaling Giant Models with Conditional Computation and Automatic Sharding](https://mlsanity.com/paper/2006.16668/) (2020)
- [Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks](https://mlsanity.com/paper/1703.02930/) (2017)
- [Learning with Square Loss: Localization through Offset Rademacher Complexity](https://mlsanity.com/paper/1502.06134/) (2015)
- [Statistical Perspective of Top-K Sparse Softmax Gating Mixture of Experts](https://mlsanity.com/paper/2309.13850/) (2023)
- [Sigmoid Gating is More Sample Efficient than Softmax Gating in Mixture of Experts](https://mlsanity.com/paper/2405.13997/) (2024)
- [A Universal Approximation Theorem for Mixture of Experts Models](https://mlsanity.com/paper/1602.03683/) (2016)
- [Generalization Error Analysis for Sparse Mixture-of-Experts: A Preliminary Study](https://mlsanity.com/paper/2403.17404/) (2024)
- [Convergence Rates for Softmax Gating Mixture of Experts](https://mlsanity.com/paper/2503.03213/) (2025)

## Abstract (arXiv)

Mixture-of-Experts (MoE) models combine specialized experts through an input-dependent routing mechanism, and their sparse variants underpin many modern large-scale systems. Yet the statistical cost of adaptive routing remains only partially understood. We study the estimation error of least-squares MoE estimators when both the experts and the gating network are Lipschitz in their parameters. We represent each MoE as a gate--expert pair in a Gated Hilbert Space, whose norm |·|_Delta separates the contributions of routing and expert discrepancies. Using its empirical representation, we derive an oracle inequality with a fast rate of order tildemathcal Obig((Kdpr,e+dpr,g)/nbig) for dense MoEs with K experts. For sparse Top-k and Top-p routing, the selection map is discontinuous in the gating parameters. We handle this by partitioning the gating class according to the selection patterns it induces on the sample. The resulting bounds match the dense rate up to an additive routing cost governed by the Natarajan dimension of the selector. We show that such a routing-complexity condition cannot be dropped: Lipschitz continuity in the parameters alone does not suffice. For linear softmax gating, the routing cost is of the same order as the gating term. Finally, for linear experts, we establish a matching minimax lower bound of order Kdpr,e/n, showing that the rates are optimal up to logarithmic factors.