Summary
Mixture-of-Experts (MoE) models use multiple specialized components called experts, guided by a router that decides which expert to use based on the input. The authors study how well these models learn from data, especially when the router chooses only a few experts (sparse routing) rather than many. They find that sparsity helps reduce computational costs but does not reduce the amount of data needed to learn well. Their mathematical bounds show that selecting experts adaptively adds a complexity cost that can't be ignored. They also prove these bounds are close to the best possible, making their results rigorous.
What this means in practice
- •For machine learning engineers: Design large models with sparse expert routing while understanding the precise data requirements for accurate learning.
- •For ai infrastructure teams: Optimize compute allocation by using sparse mixture of experts routing without expecting reductions in data needs for training.
A theory result. No direct application yet.
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\|_Δ$ 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.