In machine learning, a long-standing piece of conventional wisdom dictates that if you mix together enough simple models, you can approximate any complex distribution or function. While this intuition has driven the massive practical success of Mixture-of-Experts (MoE) architectures, transforming this intuition into rigorous mathematical proof requires navigating the complexities of functional analysis.
Why exactly do MoE models work as universal approximators, and what are the mathematical mechanics behind their expressivity? By looking at how these models behave across different functional spaces, we can understand the precise guarantees that underpin their success.
The Intuition of Localized Mixtures
At its core, an MoE model decomposes a complex global problem into simpler local sub-problems. It achieves this through two main components: a gating network and a set of expert networks. The gating network acts as a continuous router, assigning weights to each expert based on the current input, while the experts generate localized predictions.
To understand why this structure yields a universal approximator, imagine trying to paint a highly complex, non-linear landscape using only straight lines. A single straight line (a linear expert) fails globally. However, if you restrict each line to a tiny, localized patch of the canvas using the gating network, and then smoothly stitch those patches together, you can approximate any curve to arbitrary precision.
Approximating Continuous Functions via Stone-Weierstrass
To formalize this intuition for deterministic continuous functions, theoreticians frequently turn to the Stone-Weierstrass theorem. This theorem provides a checklist for universality: a family of functions is dense in the space of continuous functions on a compact domain if it forms an algebra (meaning it is closed under addition, scalar multiplication, and multiplication) and can separate distinct points.
In A Universal Approximation Theorem for Mixture-of-Experts Models, Hien Duy Nguyen et al. systematically demonstrated that the mean functions of MoE models satisfy these exact algebraic conditions. By proving that the mathematical formulation of MoEs allows for closure under basic algebraic operations, the authors established that MoEs can approximate any continuous function on any compact domain. This result was vital because it removed historical constraints requiring the target function to be differentiable or the domain to have a rigid geometric shape.
This foundational capability extends naturally to dynamic environments. For instance, in Time Series Prediction using Mixtures of Experts, Assaf J. Zeevi et al. extended this framework to stationary time series. They proved that a mixture of simple linear autoregressive models acts as a universal approximator for smooth functions within Sobolev spaces, showing that complex non-linear stochastic processes can be reliably modeled by aggregating mathematically tractable, localized components.
From Functions to Densities: The Convex Hull Framework
While approximating a deterministic function is powerful, many real-world tasks require modeling uncertainty. This means approximating probability density functions (PDFs) or conditional PDFs (the probability distribution of an output given an input).
To prove that mixtures can approximate any arbitrary PDF, the theoretical perspective shifts from algebraic closure to geometric spaces. In Approximation of probability density functions via location-scale finite mixtures in Lebesgue spaces, TrungTin Nguyen et al. treated the set of all possible mixtures as a convex hull within a normed vector space—specifically, Lebesgue ($L_p$) spaces.
By applying the Hahn-Banach theorem, the authors demonstrated a powerful geometric truth: by taking a single valid base density function and systematically shifting it (location) and scaling it (scale), the linear span of these transformed densities can fill the target space. This means that a finite mixture model can approximate almost any PDF under remarkably weak assumptions.
Target Density (Complex/Multimodal)
_ .---. _
_.' \/ \/ '._
/ \
Approximation via Location-Scale Mixture (Convex Hull)
/\ /\ /\
/ \ / \ / \ <-- Summing shifted and scaled base densities
___/____\/____\/____\____
When moving to conditional problems, the mixture weights and parameters depend directly on the input $x$. The model must capture not just a static density, but how that distribution changes shape as the input moves.
In Approximations of conditional probability density functions in Lebesgue spaces via mixture of experts models, Hien Duy Nguyen et al. extended these Lebesgue space proofs to conditional densities. They established that MoE models are dense in these spaces, ensuring the architecture is expressive enough to represent complex conditional distributions. For univariate inputs, the authors demonstrated almost uniform convergence, meaning the approximation remains highly accurate across nearly the entire input space, rather than just minimizing an average error.
Furthermore, this holds true even when the output is multidimensional. In Approximation results regarding the multiple-output Gaussian gated mixture of linear experts model, Hien D. Nguyen 0001 et al. proved that Gaussian-gated Mixture of Linear Experts (MoLE) models can arbitrarily well approximate multivariate conditional probability densities, providing a rigorous foundation for complex multi-variable regression and tracking tasks.
Escaping Compact Domains
Early approximation proofs often relied on the mathematically convenient assumption of a compact (bounded) domain. However, real-world data is frequently unbounded. How do mixture models perform when inputs or outputs can stretch to infinity?
The key lies in how the base densities behave at the boundaries of the space. In Approximation by finite mixtures of continuous density functions that vanish at infinity, Hien Duy Nguyen et al. showed that if the base density function vanishes at infinity, finite mixture models can achieve uniform approximation across the entire $\mathbb{R}^n$ space. This generalized framework provides a unified theoretical backing for the mixture "folk theorem," confirming that the approximation holds true uniformly, in $L_p$ norms, and almost everywhere.
Similarly, when analyzing neural network components designed to handle unbounded functions, such as the $k$-Rectified Linear Unit ($k$-ReLU), Naoya Hatano et al. in Global Universality of the Two-Layer Neural Network with the k-Rectified Linear Unit utilized inductive arguments to extend approximation capabilities. By first establishing density for continuous functions with compact support, they systematically extended global universality to broader, unbounded functional spaces.
Bridging Theory and Modern Scaling
While classical proofs focus on simple linear experts or fixed base densities, modern deep learning relies on scaling these architectures into massive deep MoE Transformers and complex scoring systems.
For example, in information retrieval, the LITE framework introduced by Himanshu Jain et al. in Efficient Document Ranking with Learnable Late Interactions leverages these universal approximation capabilities to learn arbitrary continuous relevance scoring functions between queries and documents, optimizing both accuracy and storage.
When scaling these systems, a constructive approximation theorem developed by Mansour MAYAKI in Generalization and Scaling Laws for Mixture-of-Experts Transformers demonstrates that MoE architectures have two distinct pathways for reducing approximation error:
- Increasing active capacity: Making the individual experts deeper or wider.
- Expanding the expert pool: Increasing the total number of available experts that the gating network can choose from.
This reveals why MoEs are uniquely suited for massive scaling: they allow a model to increase its total representational capacity by adding experts without necessarily increasing the computational cost per token.
The Frontier: Deep Experts
Despite these sweeping universality proofs, a significant theoretical gap remains. As noted by Huy Nguyen et al. in Is Temperature Sample Efficient for Softmax Gaussian Mixture of Experts?, many rigorous convergence and sample efficiency guarantees are still restricted to linear expert functions.
While we know that mixtures of linear experts can approximate any density or function in the limit, modern architectures use deep neural networks as the experts. Validating whether the sample efficiency gains and optimization landscapes observed in practice persist under formal proofs for complex, multi-layer expert architectures remains one of the most active and vital frontiers in machine learning theory.
Key Foundational Work
Hierarchical Mixtures-of-Experts for Exponential Family Regression Models with Generalized Linear Mean Functions: A Survey of Approximation and Consistency Results (1998) — contributed 4 concept elements to this direction.
Time Series Prediction using Mixtures of Experts (1996) — contributed 1 concept elements to this direction.