arXiv preprint ·
Sparsity Saves Compute, Not Samples: Oracle Inequalities for Dense and Sparse Mixture of Experts
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Machine Learning
Prior-Informed Generalizable Low-Rank Representation Learning via Regularized Adversarial Reweighting
Imperfect Verifiers, Exact Targets: Inference-Time Scaling for Continuous Generation
ByteMark: A Unified Byte-Level Watermark for Detection Across Language Models
What a Data Release Must Preserve for Off-Policy Evaluation
Copula Active Subspaces II: Error Decomposition, A Posteriori Estimation, and Sharpness of the Bounds
Get the few papers worth your time in Machine Learning every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.