cs.LGNov 3, 2026

Provably Learning Mixtures of Linear Experts

Authors: Adrian Candocia, Aamod Varma, Mark Davenport

Organizations: School of Electrical and Computer Engineering, Georgia Institute of Technology, Atlanta, GA 30332, USA.

Abstract

Mixture-of-Experts (MoE) models are widely deployed in modern machine learning. However, few convergence guarantees exist for gradient-based training of MoEs: the objective is nonconvex, and even simple mixtures trap first-order methods in spurious local optima. We analyze a canonical gated mixture featuring linear experts and a gate induced by Gaussian clusters in the input space, and give, to our knowledge, the first global convergence guarantee for jointly training the gate and the experts of such a model by gradient EM on its likelihood. Given a logarithmic overparameterization relative to the true number of experts mm, gradient EM converges from randomly initialized gates and least-squares-initialized experts to any prescribed accuracy in polynomially many iterations, under a separation condition on the gate centers. Our analysis establishes a gradient-dominance inequality for the coupled dynamics by decoupling the loss into per-cluster subproblems. Empirical results validate the predicted mlog⁡mm\log m phase transition and suggest that the least-squares warm start required by our analysis is not needed in practice: randomly initialized experts perform nearly as well. We also find that leaving the mixing weights unconstrained concentrates routing onto the true number of experts, whereas load-balancing penalties spread it, so that the fitted model can be pruned to a fraction of its width without loss of accuracy.

Figures & tables

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

Oct 21, 2026

GaP-MoE : Explicit Expert Specialization in Mixture-of-Experts via Orthogonal Gradient Accumulation and Projection

Sparse Mixture-of-Experts (SMoE) models improve scalability by routing input tokens to only a subset of expert networks, but they often suffer from representation collapse, in which multiple experts converge toward similar functions and lose their intended diversity. Prior work has addressed this limitation either by improving router architectures or by introducing auxiliary loss terms that implicitly penalize similarity among experts. However, router-based approaches remain vulnerable to routing collapses, and loss-based approaches can conflict with the task's original objective during optimization. In this work, we propose GaP-MoE (Gradient Accumulation and Projection in MoE), which induces expert specialization by directly manipulating expert output gradients rather than modifying the loss function. At each training step, GaP-MoE stochastically selects one of the TopKTopK routed experts as a leader based on normalized routing scores, and projects the gradients of the remaining follower experts onto the orthogonal complement of the subspace spanned by the leader's recent gradients. This removes directional overlap between expert gradients without altering the task loss, allowing specialization to emerge as a direct consequence of the optimization dynamics rather than an externally imposed constraint. We evaluate GaP-MoE in both fine-tuning settings (BERT-based, on GLUE) and from-scratch pretraining settings (GPT-2-based, on WikiText-103, enwik8, and text8), and further confirm its compatibility as a drop-in module for existing SMoE architectures. Experimental results show that GaP-MoE achieves performance comparable to or better than standard SMoE.
Oct 10, 2026

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

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 O~((Kdpr,e+dpr,g)/n)\tilde{\mathcal O}\big((Kd_{\mathrm{pr},e}+d_{\mathrm{pr},g})/n\big) for dense MoEs with KK experts. For sparse Top-kk and Top-pp 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/nKd_{\mathrm{pr},e}/n, showing that the rates are optimal up to logarithmic factors.
Jul 14, 2019

Regularized Estimation and Feature Selection in Mixtures of Generalized Linear Experts

Mixtures of experts (MoE) are conditional mixture models in which both the mixing proportions and the component densities depend on the predictors, and are widely used for regression, classification and model-based clustering of heterogeneous data. Fitting MoE by maximum likelihood becomes unstable, and sometimes infeasible, when the predictors are numerous or correlated. We propose a regularized maximum likelihood framework for simultaneous parameter estimation and feature selection in MoE whose experts belong to the generalized linear model family, covering Gaussian, Poisson and multinomial responses within a single formulation. Sparsity is induced in both the gating network and the experts through ℓ1\ell_1 penalties, and the penalized log-likelihood is maximized by a proximal Newton-EM algorithm whose M-step reduces to weighted Lasso problems with closed-form coordinate-ascent updates. Unlike existing penalized MoE procedures, the algorithm requires neither a local quadratic approximation of the penalty nor any matrix inversion, it returns exactly sparse estimates without thresholding, and a proximal Newton-type variant guarantees a monotone increase of the penalized objective at every iteration. On simulated data and five real data sets, the method recovers the actual sparsity support and delivers prediction and clustering accuracy that is competitive with, and often better than, state-of-the-art regularized MoE. The source codes of our developed algorithms and their documentation are publicly available on Github at https://github.com/nv-thin/GLM-RMoE.