📊 statistics

Revisiting Incremental Stochastic Majorization-Minimization Algorithms with Applications to Mixture of Experts

This paper introduces and theoretically validates an incremental stochastic Majorization-Minimization algorithm that generalizes stochastic EM to handle high-volume streaming data without explicit latent variables, demonstrating superior performance over standard optimizers on both synthetic and real-world mixture of experts regression tasks.

Original authors: TrungKhang Tran, TrungTin Nguyen, Gersende Fort, Tung Doan, Hien Duy Nguyen, Binh T. Nguyen, Florence Forbes, Christopher Drovandi

Published 2026-01-28

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: TrungKhang Tran, TrungTin Nguyen, Gersende Fort, Tung Doan, Hien Duy Nguyen, Binh T. Nguyen, Florence Forbes, Christopher Drovandi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a very smart, but slightly chaotic, robot to predict the future based on a massive stream of data. The data is so huge that you can't possibly look at it all at once; it's like trying to drink from a firehose. This is the world of streaming data, where information arrives one drop at a time, and traditional methods that require you to pause and review the entire ocean of data before making a decision are too slow or impossible.

This paper introduces a new, smarter way for the robot to learn, called the Incremental Stochastic Majorization-Minimization (MM) algorithm. Here is how it works, broken down into simple concepts:

1. The Problem: The "Mixture of Experts"

The paper focuses on a specific type of model called a Mixture of Experts (MoE).

The Analogy: Imagine a hospital with many different doctors (the "experts"). Some are great at treating heart issues, others at skin conditions, and others at bone fractures.
The Gatekeeper: There is also a triage nurse (the "gating network") who looks at a patient's symptoms and decides which doctor is the best fit for that specific person.
The Goal: The robot needs to learn two things simultaneously:
1. How to be the perfect triage nurse (knowing which expert to pick).
2. How to be the perfect expert (knowing how to treat the patient).

The challenge is that the data is messy, high-volume, and arrives in a stream. The robot can't wait to see all the patients before it starts learning; it must learn as it goes.

2. The Old Way vs. The New Way

The Old Way (Batch Learning): Imagine the robot waits until the end of the day, gathers every single patient record, and then tries to figure out the best rules. This is slow and requires a massive memory bank.
The "Stochastic" Way (The Standard): The robot looks at one patient, makes a guess, updates its brain slightly, and moves to the next. This is fast, but it's like a drunk person walking home; they might wobble a lot and take a very long, inefficient path to the destination.
The Paper's New Way (Incremental Stochastic MM): This is the paper's main contribution. It's like giving the robot a GPS with a "safety net."
- Majorization-Minimization (MM): Instead of trying to solve the hardest part of the puzzle directly (which is like trying to climb a jagged, slippery mountain), the robot builds a smooth, safe ramp (a "surrogate") that sits on top of the mountain. It knows that if it walks to the bottom of this smooth ramp, it will definitely be lower than where it started on the jagged mountain. It then slides down the ramp, updates its position, and builds a new, even better ramp for the next step.
- The "Stochastic" Twist: Because the data is streaming, the robot can't build the perfect ramp every time. Instead, it builds a "good enough" ramp based on the single patient it just saw, updates its position, and repeats.

3. Why This Paper is Special

The authors realized that for this specific type of "Mixture of Experts" model (specifically one that uses a "softmax" gate, which is like a very sophisticated voting system), the old "safety net" methods used by other algorithms (like standard Stochastic Gradient Descent or Adam) often fail. They break down because the mathematical landscape is too bumpy and unpredictable.

The Claim: The authors proved mathematically that their new "ramp-building" method is stable. Even though the data is messy and arrives one by one, the robot is guaranteed to eventually find a good stopping point (a stationary point) where it can't improve much further.
The "Relaxation": Unlike older methods that demanded the data fit into neat, perfect mathematical boxes (like "exponential families"), this new method is flexible. It relaxes those strict rules, allowing it to handle the messy, real-world complexity of the "Mixture of Experts" models that other algorithms struggle with.

4. The Results: Does it Work?

The authors tested their robot in two ways:

Synthetic Data: They created fake data where they knew the "true" answer. Their method found the correct answer faster and more accurately than popular competitors like SGD, Adam, RMSProp, and Sophia. It was like the robot with the GPS ramp reaching the destination in fewer steps than the others.
Real-World Data: They tested it on two real datasets:
- Corn Genetics: Analyzing drought-resistant corn varieties using protein data.
- Crime Statistics: Predicting crime rates based on community demographics.
  In both cases, their method produced more stable and accurate predictions than the standard tools used by data scientists today.

Summary

Think of this paper as a new, more robust training manual for a robot that learns from a never-ending stream of information.

The Problem: Old methods get confused by the complexity of "Mixture of Experts" models when data is streaming.
The Solution: A new algorithm that builds temporary, smooth "ramps" to guide the robot down the mountain of data, one step at a time.
The Benefit: It is mathematically proven to be stable and, in practice, learns faster and more accurately than the current top-tier tools, specifically for complex models that mix different types of experts together.

The paper does not claim this is a medical cure or a specific business tool yet; it simply proves that this new mathematical "engine" is superior for training these specific types of complex AI models on large, streaming datasets.

Technical Summary: Revisiting Incremental Stochastic Majorization-Minimization Algorithms with Applications to Mixture of Experts

Problem Statement
The processing of high-volume, streaming data has rendered traditional batch-mode algorithms impractical due to their requirement for repeated passes over full datasets. While incremental stochastic estimation methods, such as the incremental stochastic Expectation-Maximization (EM) algorithm, have been developed to address this, they often rely on restrictive assumptions, particularly the explicit representation of latent variables and the assumption that the target model belongs to the exponential family. These constraints limit their applicability to complex models like the Softmax-Gated Mixture of Experts (MoE), where the objective function (negative log predictive density) does not generally belong to an exponential family and lacks global regularity properties such as Lipschitz continuity, $L$ -smoothness, or convexity. Consequently, existing incremental stochastic EM and MM variants often fail to provide valid surrogates or convergence guarantees for softmax-gated MoE models.

Methodology
The authors revisit and analyze an incremental stochastic variant of the Majorization-Minimization (MM) algorithm, formulated within the Stochastic Approximation framework. The core methodology involves:

Generalized MM Framework: The approach relaxes the requirement for the target model to be in the exponential family. Instead, it requires that the majorizer surrogate function belongs to an exponential family. The algorithm constructs a sequence of majorizers defined by $g(\theta, z; \tau) = -\psi(\theta) + \langle \bar{S}(\tau; z), \phi(\theta) \rangle$ , where $\bar{S}$ is an auxiliary statistic updated via stochastic approximation.
Algorithmic Structure: The proposed Incremental Stochastic MM Algorithm (Algorithm 1) maintains an auxiliary statistic sequence $\{s_n\}$ updated by the recursion $s_{n+1} = s_n + \gamma_{n+1}(\bar{S}(\bar{\theta}(s_n); z_{n+1}) - s_n)$ . The parameter iterate $\theta_{n+1}$ is then deterministically obtained by minimizing the surrogate function with respect to the updated statistic: $\theta_{n+1} = \bar{\theta}(s_{n+1})$ .
Application to Softmax-Gated MoE: The method is specifically applied to two variants of softmax-gated MoE models:
- Continuous Output (SGMoE): Utilizing Gaussian experts with polynomial regression for gating and mean functions.
- Discrete Output: Utilizing multinomial logistic regression experts with polynomial gating.
  For these models, the authors derive specific exponential family majorizer surrogates that bypass the need for the original objective to be in the exponential family. They construct valid majorizers using quadratic bounds and specific matrix inequalities (e.g., involving the matrix $B_{n,K}$ ) to handle the non-convexity and lack of smoothness inherent in the softmax gating and Gaussian likelihood terms.
Theoretical Guarantees: Under a set of regularity assumptions (P1–P5) and stability conditions (Assumptions 1–8), the paper establishes that the algorithm generates a sequence that converges almost surely to a stationary point of the objective function (where the gradient vanishes). This consistency result relies on the existence of a Lyapunov function and the properties of stochastic approximation.

Key Contributions

Generalization of Incremental Stochastic MM: The work generalizes the incremental stochastic EM algorithm, allowing for broader applicability to models where explicit latent variable representations are difficult or where the model does not fit the exponential family structure.
Theoretical Consistency: The authors provide rigorous theoretical guarantees proving that the iterates converge to stationary points characterized by a vanishing gradient, a property often absent in widely used stochastic optimizers like SGD, RMSProp, Adam, and Sophia when applied to complex latent models.
Novel Application to Softmax-Gated MoE: The paper demonstrates that the proposed method is the first incremental stochastic algorithm capable of effectively fitting softmax-gated MoE models, a setting where existing incremental EM and MM variants fail due to restrictive regularity conditions (e.g., failure of Lipschitz continuity and convexity in the SGMoE objective).
Correction of Bounds: The authors revisit and correct a bound presented in Lemma 2 of a previous work [5], providing a more explicit and rigorous formulation used to construct valid majorizers for multinomial logistic regression contexts.

Experimental Results
The method was evaluated on synthetic and real-world datasets, comparing performance against state-of-the-art stochastic optimizers (SGD, RMSProp, Adam, AdamW, Sophia).

Synthetic Data: On both low-dimensional and high-dimensional synthetic datasets, the Incremental Stochastic MM algorithm consistently outperformed baseline methods in terms of estimation error (MSE, MAPE, NRMSE) and prediction error. It demonstrated faster convergence rates and greater stability, particularly when using Polyak averaging.
Real-World Data:
- Dent Maize Genotypes: In a bioinformatics study involving drought stress and proteomics data, the proposed method yielded stable gains in predictive performance compared to baselines.
- Communities and Crime: On socio-economic crime data, the method again showed superior or comparable performance with lower variance across cross-validation folds.
Initialization Robustness: The algorithm performed robustly under both perturbed ground-truth initialization and data-driven initialization (via K-means), successfully recovering true parameters and minimizing log-likelihood.

Significance and Claims
The paper claims that the proposed Incremental Stochastic MM framework offers a robust and theoretically grounded alternative for optimizing complex latent variable models in streaming data environments. By relaxing the stringent assumptions required by EM-based methods (such as convexity and explicit latent representations), the approach broadens the scope of incremental stochastic estimation. The authors highlight the central role of softmax-gated MoE architectures in contemporary deep learning for heterogeneous data modeling and argue that their method fills a critical gap by providing a viable optimization strategy where previous incremental stochastic approaches were inapplicable. The work suggests that this framework can serve as a foundational tool for future developments in statistical learning, particularly for models requiring flexible, non-Gaussian, or deep neural network-based expert components.