Provably Learning Mixtures of Linear Experts
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 , 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 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
| Figure 1 | Figure 2 | Figures 3 , 4 | |
|---|---|---|---|
| true experts | |||
| fitted experts | |||
| separation | minimum (scale ) | , (exact) | (exact) |
| expert scale | |||
| mixing weights | uniform | uniform; skewed | |
| expert initialization | local least squares | local least squares; | local least squares |
Mixture-of-Experts Models
Mixture-of-experts models use input-dependent routing to activate specialized subnetworks, increasing model capacity without running every parameter for each input.
See all 489 papers