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 $\|\cdot\|_\Delta$ separates the contributions of routing and expert discrepancies. Using its empirical representation, we derive an oracle inequality with a fast rate of order $\tilde{\mathcal O}\big((Kd_{\mathrm{pr},e}+d_{\mathrm{pr},g})/n\big)$ 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_{\mathrm{pr},e}/n$, showing that the rates are optimal up to logarithmic factors.