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

arXiv:2610.15039v1 Announce Type: new 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 |dot|Delta separates the contributions of routing and expert discrepancies. Using its empirical representation, we derive an oracle inequality with a fast rate of order ilde{mathcal O}ig((Kd{pr,e}+d_{pr,g})/nig) 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.

Related

• Towards a Statistical Understanding of Mixture-of-Experts
• Redundancy Meets Synergy: Dependency-aware Expert Selection for MoE via Submodular Optimization
• Boundary Mass and the Soft-to-Hard Limit in Mixture-of-Experts
• Dense Mixture-of-Experts as a Reparameterized Wide FFN: A Granularity Sweep at Fixed Compute

Source: arXiv cs.LG | 2026-10-14