# Breaking the gridlock in Mixture-of-Experts: Consistent and Efficient Algorithms

arXiv: https://arxiv.org/abs/1802.07417 · HTML: https://mlsanity.com/paper/1802.07417/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Placed in MoE theory and gating functions, one of 12 directions in Mixture-of-experts.
- Builds on 27 of its 55 references that are in the map.
- First posted on arXiv 21 Feb 2018.

## Placed in

- Mixture-of-experts / [MoE theory and gating functions](https://mlsanity.com/moe/moe-theory-and-gating-functions/)

## Builds on (most cited first, 27 of 27)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Neural Machine Translation by Jointly Learning to Align and Translate](https://mlsanity.com/paper/1409.0473/) (2014)
- [Outrageously Large Neural Networks: The Sparsely-Gated Mixture-of-Experts Layer](https://mlsanity.com/paper/1701.06538/) (2017)
- [Empirical Evaluation of Gated Recurrent Neural Networks on Sequence Modeling](https://mlsanity.com/paper/1412.3555/) (2014)
- [Effective Approaches to Attention-based Neural Machine Translation](https://mlsanity.com/paper/1508.04025/) (2015)
- [Convergence Analysis of Two-layer Neural Networks with ReLU Activation](https://mlsanity.com/paper/1705.09886/) (2017)
- [Statistical guarantees for the EM algorithm: From population to sample-based analysis](https://mlsanity.com/paper/1408.2156/) (2014)
- [Spurious Local Minima are Common in Two-Layer ReLU Neural Networks](https://mlsanity.com/paper/1712.08968/) (2017)
- [Recovery Guarantees for One-hidden-layer Neural Networks](https://mlsanity.com/paper/1706.03175/) (2017)
- [Learning One-hidden-layer Neural Networks with Landscape Design](https://mlsanity.com/paper/1711.00501/) (2017)
- [Hard Mixtures of Experts for Large Scale Weakly Supervised Vision](https://mlsanity.com/paper/1704.06363/) (2017)
- [Spectral Methods meet EM: A Provably Optimal Algorithm for Crowdsourcing](https://mlsanity.com/paper/1406.3824/) (2014)
- [Ten Steps of EM Suffice for Mixtures of Two Gaussians](https://mlsanity.com/paper/1609.00368/) (2016)
- [Gradient Descent Learns One-hidden-layer CNN: Don't be Afraid of Spurious Local Minima](https://mlsanity.com/paper/1712.00779/) (2017)
- [Generative Image Modeling Using Spatial LSTMs](https://mlsanity.com/paper/1506.03478/) (2015)
- [Local Maxima in the Likelihood of Gaussian Mixture Models: Structural Results and Algorithmic Consequences](https://mlsanity.com/paper/1609.00978/) (2016)
- [Global analysis of Expectation Maximization for mixtures of two Gaussians](https://mlsanity.com/paper/1608.07630/) (2016)
- [Solving a Mixture of Many Random Linear Equations by Tensor Decomposition and Alternating Minimization](https://mlsanity.com/paper/1608.05749/) (2016)
- [Spectral Experts for Estimating Mixtures of Linear Regressions](https://mlsanity.com/paper/1306.3729/) (2013)
- [Polynomial-time Tensor Decompositions with Sum-of-Squares](https://mlsanity.com/paper/1610.01980/) (2016)
- [Guaranteed Non-Orthogonal Tensor Decomposition via Alternating Rank-1 Updates](https://mlsanity.com/paper/1402.5180/) (2014)
- [Hierarchical Mixture-of-Experts Model for Large-Scale Gaussian Process Regression](https://mlsanity.com/paper/1412.3078/) (2014)
- [Learning Mixtures of Linear Classifiers](https://mlsanity.com/paper/1311.2547/) (2013)
- [Learning Mixtures of Discrete Product Distributions using Spectral Decompositions](https://mlsanity.com/paper/1311.2972/) (2013)
- [Score Function Features for Discriminative Learning: Matrix and Tensor Framework](https://mlsanity.com/paper/1412.2863/) (2014)
- [LSTM-based Mixture-of-Experts for Knowledge-Aware Dialogues](https://mlsanity.com/paper/1605.01652/) (2016)
- [Provable Tensor Methods for Learning Mixtures of Generalized Linear Models](https://mlsanity.com/paper/1412.3046/) (2014)

## Built on by (most cited first, 13 of 13)

- [Convergence Rates for Gaussian Mixtures of Experts](https://mlsanity.com/paper/1907.04377/) (2019)
- [Provably learning a multi-head attention layer](https://mlsanity.com/paper/2402.04084/) (2024)
- [Mixture of Experts (MoE): A Big Data Perspective](https://mlsanity.com/paper/2501.16352/) (2025)
- [On component interactions in two-stage recommender systems](https://mlsanity.com/paper/2106.14979/) (2021)
- [Statistical-Computational Tradeoffs in Mixed Sparse Linear Regression](https://mlsanity.com/paper/2303.02118/) (2023)
- [Uniform Consistency in Nonparametric Mixture Models](https://mlsanity.com/paper/2108.14003/) (2021)
- [SQ Lower Bounds for Learning Mixtures of Linear Classifiers](https://mlsanity.com/paper/2310.11876/) (2023)
- [Mixed Regression via Approximate Message Passing](https://mlsanity.com/paper/2304.02229/) (2023)
- [On Parameter Estimation in Deviated Gaussian Mixture of Experts](https://mlsanity.com/paper/2402.05220/) (2024)
- [Learning Mixtures of Experts with EM: A Mirror Descent Perspective](https://mlsanity.com/paper/2411.06056/) (2024)
- [Soft-to-Hard Routing in Sparse Mixture-of-Experts Models](https://mlsanity.com/paper/2605.02124/) (2026)
- [On the Adaptation to Concept Drift for CTR Prediction](https://mlsanity.com/paper/2204.05101/) (2022)
- [Computationally efficient reductions between some statistical models](https://mlsanity.com/paper/2402.07717/) (2024)

## Abstract (arXiv)

Mixture-of-Experts (MoE) is a widely popular model for ensemble learning and is a basic building block of highly successful modern neural networks as well as a component in Gated Recurrent Units (GRU) and Attention networks. However, present algorithms for learning MoE including the EM algorithm, and gradient descent are known to get stuck in local optima. From a theoretical viewpoint, finding an efficient and provably consistent algorithm to learn the parameters remains a long standing open problem for more than two decades. In this paper, we introduce the first algorithm that learns the true parameters of a MoE model for a wide class of non-linearities with global consistency guarantees. While existing algorithms jointly or iteratively estimate the expert parameters and the gating paramters in the MoE, we propose a novel algorithm that breaks the deadlock and can directly estimate the expert parameters by sensing its echo in a carefully designed cross-moment tensor between the inputs and the output. Once the experts are known, the recovery of gating parameters still requires an EM algorithm; however, we show that the EM algorithm for this simplified problem, unlike the joint EM algorithm, converges to the true parameters. We empirically validate our algorithm on both the synthetic and real data sets in a variety of settings, and show superior performance to standard baselines.