Sparsity Saves Compute, Not Samples: Oracle Inequalities for Dense and Sparse Mixture of Experts
Abstract
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 |·|Δ separates the contributions of routing and expert discrepancies. Using its empirical representation, we derive an oracle inequality with a fast rate of order 𝒪̃((Kdpr,e+dpr,g)/n) 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.
Related
- Non-asymptotic oracle inequalities for the Lasso in high-dimensional mixture of experts
- Mixture of Censored Partially Linear Experts Models for Symmetric or Asymmetric Data with or without Outlying Observations: A novel approach with two-piece scale-mixture of normal distributions
- The Limits of Speculation: Bounding Speculative Decoding in Mixture-of-Experts
- A Mixture-of-Experts Framework for Multi-Stream Quickest Change Detection
- When Does Sparse Routing Help? The Geometry of Expert Separation in Mixture of Experts
BibTeX
@misc{ghosh2026sparsity,
title = {{Sparsity Saves Compute, Not Samples: Oracle Inequalities for Dense and Sparse Mixture of Experts}},
author = {Sagar Ghosh and Huy Nguyen and Alessandro Rinaldo},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.15039},
eprint = {2610.15039},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.15039},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Sparsity Saves Compute, Not Samples: Oracle Inequalities for Dense and Sparse Mixture of Experts
AU - Sagar Ghosh
AU - Huy Nguyen
AU - Alessandro Rinaldo
PY - 2026
DA - 2026/10/10
PB - arXiv
DO - 10.48550/arxiv.2610.15039
UR - https://arxiv.org/abs/2610.15039
AB - 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 |·|_Δ separates the contributions of routing and expert discrepancies. Using its empirical representation, we derive an oracle inequality with a fast rate of order 𝒪̃((Kd_pr,e+d_pr,g)/n) 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 Kd_pr,e/n, showing that the rates are optimal up to logarithmic factors.
ER -