Characterizing Evolution in Expectation-Maximization Estimates for  Overspecified Mixed Linear Regression
Authors: Zhankun Luo
Abolfazl Hashemi
Venue: Accepted by TMLR ()

Abstract: Estimating data distributions using parametric families is crucial in many learning setups, serving both as a standalone problem and an intermediate objective for downstream tasks. Mixture models, in particular, have attracted significant attention due to their practical effectiveness and comprehensive theoretical foundations. A persisting challenge is model misspecification, which occurs when the model to be fitted has more mixture components than those in the data distribution. In this paper, we develop a theoretical understanding of the Expectation-Maximization (EM) algorithm's behavior in the context of targeted model misspecification for overspecified two-component Mixed Linear Regression (2MLR) with unknown $d$-dimensional regression parameters and mixing weights. In Theorem 5.1 at the population level, with an unbalanced initial guess for mixing weights, we establish linear convergence of regression parameters in $\mathcal{O}(\log (1/\epsilon))$ steps. Conversely, with a balanced initial guess for mixing weights, we observe sublinear convergence in $\mathcal{O}(\epsilon^{-2})$ steps to achieve the $\epsilon$-accuracy at Euclidean distance. In Theorem 6.1 at the finite-sample level, for mixtures with sufficiently unbalanced fixed mixing weights, we demonstrate a statistical accuracy of $\mathcal{O}((d/n)^{1/2})$, whereas for those with sufficiently balanced fixed mixing weights, the accuracy is $\mathcal{O}((d/n)^{1/4})$ given $n$ data samples. Furthermore, we underscore the connection between our population level and finite-sample level results: by setting the desired final accuracy $\epsilon$ in Theorem 5.1 to match that in Theorem 6.1 at the finite-sample level, namely letting $\epsilon = \mathcal{O}((d/n)^{1/2})$ for sufficiently unbalanced fixed mixing weights and $\epsilon = \mathcal{O}((d/n)^{1/4})$ for sufficiently balanced fixed mixing weights, we intuitively derive iteration complexity bounds $\mathcal{O}(\log (1/\epsilon))=\mathcal{O}(\log (n/d))$ and $\mathcal{O}(\epsilon^{-2})=\mathcal{O}((n/d)^{1/2})$ at the finite-sample level for sufficiently unbalanced and balanced initial mixing weights, respectively. We further extend our analysis in the overspecified setting to the finite low SNR regime, providing approximate dynamic equations that characterize the EM algorithm's behavior in this challenging case. Our new findings not only expand the scope of theoretical convergence but also improve the bounds for statistical error, time complexity, and sample complexity, and rigorously characterize the evolution of EM estimates.

Published in Transactions on Machine Learning Research (01/2026)
Characterizing Evolution in Expectation- -ixiitation-aaiiiizaaiinn Esti- mates for Overspecified Mixed Linear Regression
Zhankun Luo
huo3338purdue.co edu abolfazl@puurdue.cm edu
Abolfazl Hashemi
School of Electrical and Computer Engineering Purdue University, West Lafayelte, IN, USA
Reviewed on OpenReview: https: // openreview. net/ formm? id= #F
Abstract
Estimating data distributions using parametric families is crucial in many learning setups, serving both as a standalone problem and an intermediate objective for downstream tasks. Mixture models, in particular, have attracted significant attention due to their practical effectiveness and comprchensive thcorctical foundations. A persisting challenge model misspecification, which occurs when the model to be fitted has more mixture components than those in the data distribution. In this paper, develop theoretical understanding of the Expectation-Vaxinizatio (EM) algorithm's 's behavior in the context of targeted model misspecification for overspecified two-component Mixed Linear Regression (2MLR) with unknown d-dimensional regression parameters and mixing weights. In Theorem 5.1 at the population level, with an unbalanced initial guess for mixing weights, we establish linear convergence of regression paramcters in (log(1//c) steps. Conversely, with a balancod initial guess for mixing weights, we observe sublinear convergence in O(e-2) steps to achieve the 6-acouracy at Euclidean distance. In Theorem 6.1 at the finite-sample level, for mixtures with sufficiently unbalanced fixed mixing weights, demonstrate statistical accuracy of ((d/n)) 1/2), whereas for those with sufficiently balanced fixed mixing weights, the accuracy is ((d/n))1/) given n data samples. Furthermore, we underscore the connection between our population level and finite-sample level results: by sctting the desired final accuracy e in Theorem 5.1 to match that Theorem 6.1 at the finite-sample level, namely let letting e ((dd/))//2 for sufficiently unbalanced fixed mixing weights and ((d/n)) for sufficiently balanced fixed mixing weights, intuitively derive iteration complexity bounds (log(1/e)) = Olog(nn/d) and sufficiently unbalanced and balanced initial mixing weights, respectively. We further extend our analysis in the overspecified setting to the finite low SNR regime, providing approximate dynamic equations that characterize the EM algorithm's behavior in this challonging case. Our new findings not. only expand the scope of theoretical convergence but also improve the bounds for statistical error, time complexity, and sample complexity, and rigorously characterize the evolution of EM estimates.
(((//))/33 at the finite-sample level for
1 Introduction
Mixtures of parameterized models powerful tools to model intricate relationships in practical scenarios, such Mixed Linear Regression (MLR) and Gaussian Mixture Models (GMM) (Beale & Little, 1975). It is common for the number of mixture components in the fitted model to differ from that of the data distribution, which can substantially slow down parameter estimation convergence rates. We specifically focus on the overspecified setting, where the number of mixture components in the fitted model exceeds that of the data distribution. Expectation Maximization (EM) algorithm (Dempster et al., 1977; Wu, 1983; De Vcaux, 1989; Jordan & Xu, 1995; Wedel & DeSarbo, 1995) is notable for its computational efficiency and case of practical implementation, overcoming the intractable problem of non-convexity and the presence of numerous spurious

---

Published in Transactions on Machine Learning Research (01/2026)
local maxima in Maximum Likelihood Estimation (MLE) (Qian et al., 2022). It proceeds through two steps: in the E-step, it computes the expected log-likelihood using the current parameter estimate; subsequently, the M-step updates the parameters to maximize the expected log-likelihood computed in the E-step. These iterative steps serve to maximize the lower bound on MLE until convergence. The goal of this paper is to gain a comprehensive understanding of EM updates for overspecified mixture models.
1.1 Related Work
Ti has been shown that EM achieves global convergence for GMM with k = 2 components (2GMM) (Klusowski & Brinda, 2016; Xu al., 2016; Daskalakis et al., 2017; Ndaoud, 2018; Zhao et al., 2020; Wu & Zhou, 2021). Studies (Balakrishnan et al., 2017; Klusowski & Brinda, 2016; Kwon et al., 2019; 2022) have confirmed that EM for two-component mixed linear regression (2MLR) converges from random initialization with high probability. GMMs with k 2 3 components frequently lead to EM with random initialization being trapped in local minima with high probability, while local maxima can demonstrate notably inferior likelihood than any global maximum (Jin et al., 2016). For mixture models with multiple components, such as Gaussian Mixture Models (GMM), it is well known that the negative log-likelihood in the EM algorithm cant can exhibit several spurious local minima that are not globally optimal, even when the mixture components are well separated (Chen et al., 2024b). Consequently, proper initialization of the parameters is crucial, as assumed in the analysis of mixtures of many linear regressions (Kwon & Caramanis, 2020). A convergence analysis for EM in MLR with multiple components has been presented (Kwon & Caramanis, 2020), but it requires careful initialization and strong separation for regression parameters. Even for the case of 2GMM, most work requires good initialization and strong separation for regression parameters. For instance, Wu & Zhou (2021) analyzed the convergence rates of 2GMM with fixed balanced mixing weights given a specific initialization and strong scparation for location paramcters. Alternatively, specific initialization needs to trend loward the ground truth in cases of weak separation or no separation (Weinberger & Bresler, 2022). There is lack of understanding of the EM update rules in mixture models given weak separation or no separation of the ground truth parameters.
as the objective function
When ground truth parameters of some components in mixture models have no separation, this means we are using a model with more components to fit a ground truth data distribution with fewer components, which is called the overspecified setting. In particular, the 2GMM/2MLB model is considered overspecified when there is no separation between the true regression parameters or location parameters of its two components. Moreover, it has been observed that the convergence of EM can be prohibitively slow when dealing with poorly separated mixtures (Redner & Walker, 1984), while achieving rapid linear convergence superlincar convergence in cases with strong separalion (Kwon el al., 2021; Ghosh & Kannan, 2020). The convergence rate of regression parameters using EM for 2GMM in the overspecified setting, assuming known mixing weights, is analyzed in Dwivedi et al. (2020b); Dhawan et al. (2023). Kwon et al. (2019; 2021) derived iteration complexity and statistical accuracy for the weight case across all SNR regimes but their results in the low-SNR setting apply only when mixing weights are known to be balanced. Kwon & Caramanis (2020) analyzed EM for MLR with more than two components under restrictive conditions such as requiring initializations very near the ground truth and well-separated regression parameters- cases of overspecification where the ground truth parameters coincide. Nevertheless, there is a lack of prior research formally analyzing the evolution of EM updates for 2MLR with unknown regression parameters and mixing weights in the overspecified setting, with most prior research primarily concentrating on scenarios with known mixing weights. The behavior of EM updates in overspecified settings is not fully understood when dealing with unknown mixing weights, whether they are balanced or unbalanced. In this paper, we address this gap by conducting a detailed analysis of the EM updates for overspecified 2MLR, based on the expressions of integrals with Bessel functions given in (Luo & Hashemi, 2024). Even though Luo & Hashemi (2024) provided closed-form EM update rules (using Bessel functions) for 2MLR across all SNR regimes, but they focus primarily on the high-SNR case and do not discuss convergence guarantees or the dynamics in the overspecifted setting and the low-SNR regime. The statistical rates for parameter estimation of a class of overspecified finite mixture models have been studied in several studies (Chen, 1995; Ho & Nguyen, 2016; Heinrich & Kahn, 2018; Doss et al., 2020; Manole & Ho, 2020; 2022; Ho et al., 2022b; Nguyen et al., 2023a). The optimal minimax rates for 2MLR with known balanced mixing weights have been determined in Kwon et al. (2021), while those for 2GMM with known mixing weights have been established in Dwivedi et al.
do not cover
2

---

Published in Transactions on Machine Learning Research (01/2026)
(2020b) using the scheme outlined by Balakrishnan et al. (2017). However, the statistical error for 2MLR with unknown mixing weights remains unclear. We develop new techniques to sharpen the analysis for this statistical error.
1.2 Technical Overview
In this paper, we present comprchensive study of overspecified mixture models. The paper is organized as follows. In section 2, we state the setting of two-component mixed linear regression (2MLR), overspecification, and the EM update rules, and introduce Bessel functions for the analysis of EM updates. In section 3, we provide two motivating examples (haplotype assembly and phase retrieval) of the 2MLR model to justify the practical implications. In section 4, we characterize the population EM update rules with expectations under the density involving Bessel functions (equalion 10), show their nonincreasing property and boundedness (Facts 4.2, 4.3), and provide their approximate dynamic equations (Proposition 4.4) for the evolution of regression parameters and mixing weights. In section 5, we establish the guarantees of convergence rate for population EM (Theorem 5.1) with balanced and unbalanced initial guesses for mixing weights, and establish theoretical bounds for sublinear convergence (Proposition 5.3) with balanced initial guesses and the contraction factor of linear convergence (Proposition 5.4) with unbalanced initial guesses. In section 6, we present the tight bounds for sample complexity, time complexity, and final accuracy for finite-sampl sample EM (Theorem 6.1) by coupling the analysis of population EM and finite-sample FM and establishing statistical errors (Propositions 6.3, 6.4) in the overspecified setting. In scction we discuss the differences between results of 2MLR and 2GMM, extend our analysis from the overspecified setting to the low-SNR regime, and examine the challenges of analyzing overspecified mixture models with multiple components. In section 8, we validate our theoretical findings with numerical experiments. Detailed derivations and proof techniques are provided in the Appendices. In summary, our contributions include:
We derive the approximate dynamic equations for the regression parameters and mixing weights in Proposition 4.4 based on the population EM update rules to disentangle the relationships between regression parameters and mixing weights by establishing novel inequalities and identities for EM update rules (sce equation 10 and Appendices A, H), aiding in the investigation of EM evolution in the overspecified setting and the low-SNR regime.
Linear convergence of regression parameters with a rate of (log([/)e) is achieved with an unbalanced initial guess for mixing weights. In contrast, sublinear convergence at rate of O(e=?) is confirmed with a balanced initial guess by replacing annulus-based localization in Dwivedi et al. (2020b) with "variable separation" method upon the discretized differential inequality (see the proofs of Proposition 5.3 and Theorem 6.1 in Appendices D, G respectively), ensuring c-accuracy in Euclidean distance, as shown in Theorem 5.1 and Proposition 5.3.
We address the gap for sufficiently balanced mixtures, where the imbalance of the initial guess for mixing weights is less than or of the same order of magnitude as (d/n)1/4 in Theorem 6.1, improving bounds on statistical error, time complexity, and sample complexity in 2MLR by establishing the concentration incquality based on modified log-Sobolev incquality (sce Section 5.3 modified logarithmic Sobolev inequalities in Ledoux (2001)) and bounds for the statistics (see Appendices E, F). Our new techniques advance the results beyond those for 2GMM (Dwivedi et al., 2020b).
By adopting the above novel techniques, we rigorously characterize the evolution of EM estimates for both regression parameters and mixing weights of overspecified MLR models by providing approximate dynamic equations (Proposition 4.4) for EM update rules and establishing convergence guarantees (Theorems 5.1, 6.1) for final accuracy, time complexity, and sample complexity at population and finite-sample levels, respectively.
2 Problem Setup
In this paper, we investigate the symmetric two-component mixed linear regression (2MLR) model given by:
y = (-1) (0" +
(1)
3

---

Published in Transactions on Machine Learning Research (01/2026)
where denotes the additive Gaussian noise, (xx y) E Rd x represents the covariate-responss observation, E (1,2) is the latent variable, i.e., the label of the data, with probabilities P(= = 1| x =1) and (2). The ground truth values for the regression parameters and the mixing weights are expressed P[zz = = = x"
by 8* and x² = (1), x (2)), respectively. 9 and π = (I(1), x()) denote the cstimated values for the regression parameters and mixing weights in the fitted 2MLR model, respectively.
Consider the 2MLR model in equation 1. Let n denote the number of samples s ((1,, (((,,,,))+ y:) used for each EM update, and let {=] be the values of the latent variable for these samples. Furthermore, o² denotes the noise variance, 9 == 8/o and 0 := 0" /or are the normalized parameters, and 7 := ||0*|//r is the signal-to-noise ratio (SNR), while p = (6", (] [[@]]) is the cosine angle between the ground truth and the estimated regression parameters. In this paper, we focus on the case of overspecification, namely 0- = 0 = (0, 0, , 0) E IR, where the ground truth regression parameters are zero, and there is no separation between two mixtures. We note that the 2MLR and 2GMM models are standard models for establishing theoretical undorstanding of methods for mixture models, see, c.g., the recent works (Dwivedi al., 2020b; Weinberger & Bresler, 2022; Dhawan el al., 2023; Luo & Hashemi, 2024; Reisizadeh el al., 2024). Thus, we adopt the 2MLR model and its standard assumptions in this paper to develop finer understanding of the misspecification phenomenon (sec also Section 2.2.2, page 6 of Balakrishnan et al. (2017); page 1 of Klusowski & Brinda (2016); page 4 of Reisizadeh et al. (2024); and page 3 of Luo & Hashemi (2024)).
Bessel Function. Ko(æ), for all x > 0, is the modified Bessel function the second kind with parameter 0, defined by the integral representation Ko(x) == .o exp(-x cosh t) di which also the solution f Ko(x) to the modified Bessel equation 2dd + + x² = The approximations for Ku(æ)) arc: Ko(x) In 2 n - for x - 0+, where y = 0.577 is Euler's constant, and Ko(x)= x V exp(-x) for x + too. (see equation 10.32.9 for the integral representation, equation 10.25.1 for the modified Bessel equation, and equations 10.25 10.25.2, 10.25.3, and 10.31.2 for approximations in Chapter 10 of Olver et al. (2010)). An important fact is that for the product of two independent standard Gaussian random variables Z1 10, and Z2 ~ ~V,00, 1), it has the probability density fx involving the Bessel function Ko, X == Z1 x Z2 ~ fx(x) = Ko(læl) (see page 50, Section 4.4 Bessel Function Distributions, Chapter 12 Continuous Distributions (General) of Johnson et al. (1970)).
Notations. The notations I(-), O() and ((-) share the standard definitions of asymptotic notations:
f == ((g) means g = =O(f) for f.g. 9. namely If(x)] 2 C' x [g(x)) for some constant C. > 0 and all æ sufficiently large (see page 528 of Lehman (2017)). f= O(g) means f = O(g) and g = O()). We also write f S g if f= -g), and f> g if f = M(g), and f= g if f = O(g). a V b and a A refer to the least upper bound max (a, b) and the greatest lower bound min(a, b) of a, b, respectively.
2.1 EM Updates
The EM algorithm estimates the regression parameters and the mixing weights from observations. Balakrishnan et al. (2017) gave the population EM update rule of regression parameters for 2MLR given the known balanced mixing weights π nT" (2 as follows:
(()) = Ey-p(s (*) tanh yyz, 8)
yr.
g2
For the more general case of unknown mixing weights we introduce the variable v to characterize the imbalance tanh v = x11 - (2) of the mixing weights π = (m(1),((2)) namely
In T (1) In i())
v
(2)
and the population EM update rule for regression parameters becomes
M(0, v) = Ea-p(eler x tanh u(x,0)) 0)
σ² + v) yx,
(3)
while the population EM update rule for the imbalance tanh(v) is given by
N N(0, v) = Ea-pcele xx)) tanh y(z, 0² + v) v)
(4)
4

---

Published in Transactions on Machine Learning Research (01/2026)
The corresponding finite-sample EM update rules with n observations are given by
1
Yi 3i(22, 8) W.t)): Nn( = tanh
Yo yo 8)
()) =
tanh
o² +
+
72
0²
(5)
To further simplify the analysis of the finite-sample EM update rules, we introduce the following easy EM update rule for regression parameters:
ye (1 o²
M v) tanh
+ + y.s.s
(6)
The derivation of the EM updale rules for the 2GMM model is on pages 4 of Weinberger & Bresler (2022), and the rigorous derivation 2MLR for the population and finite-sample EM update rules (equations 3, 4, 5) can be found Appendix B of Luo Hashemi (2024).
2.2 Auxiliary Quantities
The superscript stands for the 6-th EM iteration. For instance, 0c and x' denote the t-th iteration of regression parameters and mixing weights. For the ease theoretical analysis, we denote
a² 0'=11001
110'1 8² :=
= :a==tan((')== - x2),
(7)
be the lz norm of the normalized regression parameters 8 /o, and |81 = || - - 1T( 1/2| | (2) - 1/2| represents the & distance between the mixing weight x' and the balanced mixing weights (1/2, 1/2), namely the imbalance in mixtures, to further simplify the discussions on the convergence of FM iterations. Here, 1 = 1) is the vector of all ones. To further simplify the amalysis, we introduce these two functions m(a, v) and nıa, v) of a = ||0l/a and v = (In π (1) - In /2 by defining them as the expectations under the density X fx(x)= Ko([=)) involving the Bessel function Ko.
m(a, v) E[taan(aoX + +)x), n(a, v) = E[tanh(oxX + v)].
(8)
In particular, we write mo(a) (a) m(a, 0) E E[tanh(aXX)X] for the case of tanh ((1) -2( 0.
3 Motivating Examples
As motivating examples, we highlight the tasks of haplotype assembly in bioinformatics and genomics (Cai et al., 2016) and phase retricval, which arises in numerous fields including acoustics, optics, and quantum information (Candes et al., 2015), and also learning overparameteriiatioo models and Mixture of Experts (MoE) models, to justify the practical implications of our work.
3.1 Haplotype Assembly
Haplotypes are sequences of chromosomal variations an individual's genome that are crucial for determining the individual's disease susceptibility. Haplotype assembly involves reconstructing these sequences from a mixture of sequenced chromosome fragments. Notably, humans have two haplotypes, i.e., they are diploid organisms (see Cai et al. (2016) for clear mathematical formulation of the problem). For diploids, the primary challenge is to reconstruct two distinct haplotypes (binary sequences of single mucleotide polymorphisms- SNPs) from short, noisy sequencing reads. Each read corresponds to a local window of the genome but originates from one of the two chromosomes. The ambiguity in the haplotype origin of each read can be modeled as mixture of two linear regression models with symmetric parameters, aligning with the model discussed in our work. Following Cai et al. (2016), let 0* E f[1,++1) represent one haplotype, and the other haplotype is its negative, -0* The binary variable z +1) indicates the haplotype origin of the i-th
5

---

Published in Transactions on Machine Learning Research (01/2026)
read, where the probability of the read originating from H* is P(z; +1] x1),,, and the probability of it originating from -0" is PP(z; = -1] = x x2)).. Furthermore, the j-th entry, Ed]i] for j E [d], of the noise vector E, follows a distribution defined by a fixed error probability pe: specifically, the noise causes an error (a flip) with probability Pe, meaning [[] = (2, = Pe, and the noise is zero (correct reading) with probability 1 1 Pe: meaning P(e.[j] = 0) = 1 - -Pe- Given this framework, the read signal y/ can be modeled by the following two-mixture model: y4 = 2,0" + E.- The primary goal is to estimate the unknown ground truth parameters, which are the mixing probabilities xt = (=* (1), T (2)) and the haplotype 0*, using the dataset of read signals {y: } It should be noted that while this is also two-mixture model, it features distinct formulation and noise structure.
3.2 Phase Retrieval
Regarding the application of the phase retricval problem, as noted in Scction 3 of Klusowski et al. (2019) and discussed in Section 3.5 of Chen et al. (2015), there is an established connection between the symmetric 2MLR and the phase retrieval problem. Specifically, by squaring the response variable yt and subtracting the variance o², we obtain:
v/ :- 3/ oz 1(2,, 0-
(9)
This formulation is esscntially the phase retrieval model with hetcroskedastic error term & 2(-1)=** 0"); (E3 - of), which has zero mean, i.e., E[g.] = 0. Therefore, by leveraging our re- sults on symmetric 2MLR, we can directly establish convergence guarantees for the corresponding phase retrieval problem. For phase retrieval problems, several theoretical guarantees for the parameter estimate Ó have been established. Regarding the convex formulation (Chen et al., 2015), for n Σ d samples, the relative error bound is 110 | 0'11/o S vd/n log" + min( /d/n/// /n, (d/n) 1/4) log" n, where 17 = =|00-1/o represents the signal-to-noise ratio, as shown on page 10 of Chen et al. (2015). In the case of agnostic estimation (Neykov et al., 2016), for 2 d2 log d samples, the error bound of the estimate @ satisfies ||0-011/1001] X v (dd d))gg))/// under the constraint ||0| = ||0'1, as established on pages 3 and 9 of Neykov et al. (2016). For the EM algorithm when the sample size n is sufficiently greater than the dimension (n 2 d), the relative error bound for the estimated vector ô depends on the initialization of the mixing weight n² With unbalanced initialization of mixing weights ||70- 2111 2 (d/n)1/4, the relative error is bounded by | 10-00 S vd/n. Conversely, with balanced initialization of mixing weights || - -lli 2 (d/n))/4, the relative error bound is less favorable, given by 0" S (d/n)//4 (see Theorem 6.1). Regarding sample complexity, our results require Z d samples, matching the sample complexity requirement established in Chen et al. (2015) and improving upon the 2 dL log d requirement in Neykov et al. (2016). In terms of error rates, with balanced initialization, our rate (d/n))/4 matches the second term in Chen et al. (2015), demonstrating that the EM algorithm achieves a better rate when SNR rj is sufficiently small. With unbalanced initialization, our rate vd/n matches the leading term vd/n log* n in Chen et al. (2015) and improves upon the Vdlog d//n rate in Neykov et al. (2016) by removing the logarithmic factor when SNR rj = 1. These theoretical comparisons demonstrate that our EM-based approach achieves competitive or improved error rates compared to existing phase retrieval methods, while providing explicit characterization of the intiialization-deeeddde convergence behavior.
3.3 Overparametrizatioo Models
For the general setting of overparameterization models, our theoretical results provide one of the fundamental examples. In our theoretical results of the EM algorithm for the 2MLR model, we exhibit linear convergence with an unbalanced guess of mixing weights, while showing sublinear convergence (a* x 1/vl) with balanced guess of mixing weights (see Theorems 5.1, 6.1), which is consistent with the convergence rate of O /t) for the overparameterized Gaussian mixture model (Xu et al., 2024). Interestingly, for the problem of low-rank mairix factorization (Xiong et al., 2023) in the overparanneterization regime, an exponentially faster linear convergence rate is achieved using gradient descent with an asymmetric parameterization, while gradient descent with symmetric parameterization exhibits a sublincar rate of 1/t². This suggests that imbalance accelerates the convergence rate. Overparameterization also has an impact on the convergence rate of gradient descent for learning a single neuron in neural networks (Xu & Du, 2023). The method exhibits linear
6

---

Published in Transactions on Machine Learning Research (01/2026)
convergence in the exact-parameteriiatonn regime, but shows sublinear convergence rate of 1/t in the overparamelerization regime. Therefore, overparaneelerization can exponentially slow down the convergence rate of Gradient Descent (GD).
3.4 Mixture of Experts
While the EM algorithm has been shown to be powerful tool for learning Mixture of Experts (MoE) models (Fruytier et al., 2025), establishing the convergence rates of the Maximum Likelihood Estimator (MLE) for these complex mixture models under exact-specified and over-specified settings remains a significant open challenge (Ho et al., 2022a; Nguyen et al., 2023b; 2024). In this context, our theoretical analysis of the EM algorithm for the 2MLR model serves as a fundamental example. By establishing rigorous guarantoes in this setting, our work provides the necessary theoretical groundwork to deepen the understanding of convergence behaviors in more complex architectures, such as MoE and deep mixture models.
4 Population EM Updates
In this section, we characterize the population EM update rules by using expectations (equation 10) under the density involving Bessel function Ku- We show alternative approach to derive Identity 4.1 (Corollary 3.2 of Luo & Hashemi (2024)) that leverages the key fact that the product X = 7, of two independent standard Gaussians follows X Ko(le)), from which we can derive the expectatioos (equation 10). We further show the nonincreasing property and boundedness (Facts 4.2, 4.3) of the expectations of FM update rules and provide approximate dynamic equations (Proposition 4.4) for the evolution of regression parameters and mixing weights.
Identity 4.1. (Corollary 3.2 in Luo & Hashemi (2024): EM Updates for Overspecified 2MLR) Suppose 2MLR model is fitted to the overspecified model with no seporation, where 0- = Ō. The EM update rules at the population level for f : 6t/ /a- = M(6-11 ( 3/o and tanh(v²) == (1) - (2) = N N(00-1, are then as follows.
0¹ =
8" 1 S
-² -x- )x
Tooli tanh(v') & fr tanh(u ||0-~ (
where 00 :- //.
Remark. Identity 4.1 (see our derivation in Appendix B, Subsection B.1) completely characterizes the evolution of EM updates by using Bessel functions. Note that the proposition unveils that the EM update for regression parameters at the population level must be in the same direction as the previous EM iteration (as further corroborated numerically in Fig. 1a). The numerical experiments in Fig. 1a of EM updates validate the theoretical results. Hence, we only need to focus on the reduction of length in terms of the regression parameters; therefore, we introduce the la norm of the normalized regression parameters a := ||0*|// and the imbalance of mixing weights 8 == tanh(v") to facilitate the analysis in the following context. Furthermore, the population EM update rules for a 8t can be expressed as expectations with respect to a symmetric random variable X, whose probability density involves the Bessel function Ko: namely X ~ Ko(lal) given by
a = ==mma Etttan(a' + +')),, g++1= = v²) = Ejtanh(aa'X +z0]
(10)
Fact 4.2. (Monotonicity of Expectations) Let m(a, v) == Eltanh(ax + v) and n(a,v) = E[tanh (aX +v) be the expectations with respect to X ~ Ko(lul) Then they satisfy the monolonicity properlies:
(monotonicity of mía, v)j: m(a, v) is a nonincreasing function of v 2 0 for fixed a 2 0, and a nondecreasing function of a 2 for fized v 2 0, namely:
m(a, 20) S m(a, v/) S m(a, v) S m(a, 0) S a for 0 0
2
0 =m00 v) < m(a, v) S miaa, v) S m v) for 2
7

---

Published in Transactions on Machine Learning Research (01/2026)
Trajectories of and e*
Initialization a' with n² a),
empirical trajectory theoretical trajectory
0.637 -
initial value 8
0.305.0.31
oertical component of
1.0
ground buuth
Estimated Lower/Upper Bounds
0.5
0.0
0.31
-05
-1.5
20
36
horizontal component of
tarations
(a) Trajectories of EM iterations for regression pa- rameters in the overspecified setting given different imitial values. d = 2, trajectories of 0' for trials with 8 and x" uniformly sampled from [-2, 2] and [0, 1}, respectively in the overspecified setting 0"
(b) Initialization phase of a² == 110 II in the worst- case scenario with balanced initial guess =0 () and a := ||00 + oc. Even in the worst case, the initialization phase of a' bounded by a² I _, a < 0.31, and a < 0.1 after 1, 3, and 20 EM iterations.
Figure 1: Left: EM trajectories are nearly perfect rays from the origin to the initial point, which aligns with the theoretical results in Identity 4.1. Right: In the worst case, we show that a' 2 0.1 for all L < 9 (see remark on the proof Fact 5.2 in Appendix D, Subsection D.2) by using the theoretical matching lower bound for the worst case in Proposition 5.3. Also, we demonstrate that a' < 0.1 for all t 2 36 (Fact 5.2) by applying the theoretical upper bound in Proposition 5.3. As a² x 0.1 by numerical evaluations, and 20 > 9 and 20 36, the theoretical results consistent with the numerical results shown in the figure.
(monotonicity of n(a,, v)): n(a, v) is a nonincreasing function of a 2 0 for fixed v 2 O, and a nondecreasing function of v 2 0 for fized a 2 0, namely:
n) S n(a v) S n(a,v) S n(0,v) = tanh(v) for 0 aasa 0 n( 0) S n(a, v) S n(a,v') I n(a, o0) 1 for 0 // 2.0
Remark. m(a,v) is an even function of v and n(a, v) is an odd function of v. Moreover, by using the Fact 4.2 together with equation 10, we can establish the bounded and nonincreasing properties of (a' [ (1
Fact. 4.3. (Nonincreasing and Bounded) Let a² == 110' = ( and B = tanh(v") = N(O0-1,ut (,-i)) for all t E Z+ be the t-th iteration of the EM update rules [[M v)ll/a and N v) at the population level, then 3² 30 2 0, at S 2/T,, and {a and {139))62 are non-increasing.
Remark. Fact 4.3 (see proof in Appendix B, Subsection B.2), the nonincreasing property of ||0'] and - at the population level indicates that the estimates of regression parameters gradually approach the ground truth 0* = Ö, while the estimates for mixing weights shift from "unbalanced" to "balanced". For the case of T = (1/2, 1/2), we always have 3 = 3 = || 11l1 = by using the nonincreasing property of (1 Additionally, the bounded ||0]]/a ensures that EM iterations remain within a bounded region, regardless of the initial distance from the ground truth 0" - Ō.
Proposition 4.4. (Approrimate Dynamic Equations) Let a² == 110' ||M (1 and 3r == tanh(u") 1000-1,00 (11) for all & E 24 be the 1-th ileration of the EM update rules (0, v)ll/a and N(0, v) at the population level, then the series approrimations for EM update rules are
t+ = + g++1 = +
Remark. Proposition 4.4 (sce proof in Appendix B, Subsection B.3) characterizes the evolution of EM updates by introducing approximate dynamic equations when the regression parameters are small enough. When o is
8

---

Published in Transactions on Machine Learning Research (01/2026)
(0')'
18--8" Wy-""+1W8" afa!*1
1.0
0.0.0
approsimate tynamis updates
approcmate dynamics updatiss
0.000
04
0.004
0.
0.002
0.
02
0.4 0.5
0.001
0.002
0.003
0.004
0.005
0.005
0.007
0.008
0.009
0.010
1817
Figure 2: Top: Relation of the (a'-att))/a and _ given a' = 0.1 and 8 E (0.1,0.2. 0.9, Bottom: Relation of the (3t - 1/3*) and a'a given a' = 0.1 and 5 E {0.1,0.2.-.. 0.9, The difference between (a' - -of=-)/+/aa and [89] is bounded by (1 - (((a)))) and the difference between (8' (8+=-/+1)/8*
and a is bounded by (1- -1- (1=(8)))0((aa14)) (see remark on the proof of Proposition 4.4 in Appendix B, Subsection B.3).
sufficiently small, the higher order terms for a and 3e+1 are (1- ((a))) and (111- ((a)))))
respectively (see the remark on the proof of Proposition 4.4 in Appendix B, Subsection B.3). We illustrate our findings by comparing the EM updates at the population level with our approximate dynamics, as shown in Fig. 2.
Further, we preciscly outline the evolution of EM estimates for both regression parameters and mixing weights as opposed to just the former as done in Dwivedi et al. (2020b). Using the techniques from pages 30-33 of Dwivedi et al. (2020a), we can only establish a rough upper bound for the update | := (1)-
which represents the imbalance mixing weights. However, to fully understand the evolution of EM itcrations, it is crucial to establish lower bound for 130+1 We achieve this by bounding expectalions involving the Bessel function K2 (see Lemma A.7 and Lemma C.2). By applying this lower bound for the imbalance [33), we further establish Theorem 5.1, which characterizes the convergence rate at the population level.
In the special case of balanced mixing weights, namely 3 = tanh v' = 0 then -- = 1, we have ge+1 8 by using Fact 4.3, the lower/ anper/uppt /uper bounds for a+1 when at is sufficiently small by introducing [a']3 term:
3[a'|s
a' - 3(a < a S
(11)
1 8(o
where the upper bound a' a3a33aa1%/LL4Sjoo still holds when 3r + (see remark the proof of Proposition 4.4 in Appendix B, Subsection B.3), and further establish Proposition 5.3 by using the above bounds for *++
5 Population Level Analysis
In this section, we give an analysis of population EM and establish convergence rate guarantees for population EM (Thcorem 5.1) with balanced and unbalanced initial guesses for mixing weights. We show theoretical bounds for sublinear convergence (Proposition 5.3) with balanced initial guesses and the contraction factor of linear convergence (Proposition 5.4) with unbalanced initial guesses, by bounding the expectations (equation 10) under the density involving Bessel functions for EM updates in the overspecified setting,
Main theorem 5.1. (Convergence Rate at Population Level) Suppose 2MLR model is fitted to the overspecified model with no separation 0" == then for any E (0,2/m):
(unbalanced) if n # ( 1), population EM lakes at most T = O (log !) ileralions to achieve 10911/0 S e,
(balanced) if x = (2. 1), population EM takes at most T = O iterations to achieve ||0 1//0
$ Sc.
Remark. In Theorem 5.1 (see proof in Appendix D, Subsection D.4), with an unbalanced initial guess for mixing weights, that is 800 * O, we further show the linear convergence and the upper bound for the contraction factor a aa*, therefore EM updates achieve the e-aceuracy in (log(1/e)) steps. Even in the worst case (the initial guess for mixing weights is balanced, f = 0), we still show that a O(1 ( holds
9

---

Published in Transactions on Machine Learning Research (01/2026)
relations of converged B and g
a' with varying initial values P = ||00 1/21h
1.0
110"//0
1.0
iterations of a'te" (6"-0)
110%//
Iterations of o'te" (62-
0.8
118"//0
Iterations afta -0
0.8
-1le" -11s
0.6
0.4
0.2
0.0
0.0
0.2
0.4
0.6
0.8
1.0
0
25
75
100
125
150
175
200
(a) Interpolation across initial mixing weight regimes
(b) Relation of the converged value g Rs 33 = 1|
0 = (, 2), (0.6, 0.4), 0.3,, showing sublinear conver-
I|1 and the initial value 800 || - 1 llI when 3
gence for x² (2 2) and linear convergence for x"
" (1) x (2) 2 O where 8 takes ten evenly spaced
(0.6, 0.4). (0.7, 0.3), with the normalized regression parame- ter a |10" 0.1.
values between 0.01 and 0.99, given different initial a | 0.1, 0..,
Figure 3: Comparison of convergence behavior and EM trajectories at population level.
(Proposition 5.3), and it takes at most ((--2) iterations to achieve e-acouracy in &g norm. We validate the sublinear convergence rate with numerical results, see Fig. 4a. Compared to (ff==1og((///) steps taken to achieve the e-accuracy for 2GMM with known balanced mixing weights n' (1. 3 (Equation (15), page 16 in Dwivedi al. (2020b)), we give better estimation (Ee-?) for steps in 2MLR.
Intuitive Explanation of Theorem 5.1. For GMM/MLR models, rumning the EM algorithm is equivalent to performing a step of Gradient Descent on the negative log-likelihood (Kwon et al., 2024). When an unbalanced estimate of mixing weights is given, the negative log-likelihood retains its dominant quadratic term, [a]2. This quadratic form ensures that the EM algorithm behaves like a Gradient Descent step on a strongly convex function, suggesting a fast, linear convergence rate for a'. In contrast, when a balanced estimate of mixing weights given, the [a]² term in the negative population log-likelihood cancels out (page 22 of Luo & Hashemi (2024) and Lemma. A.3). Specifically, the likelihood term can be expanded [e[n (a)) = [a] [((xX22/2 (aX)*/12 + +...] = 3/a]4//4 The EM algorithm, being equivalent to Gradient Descent, then follows path approximated by a R a² V(3)a")4/4) a' - =3 leading to much slower, sublinear convergence rate where a' is proportional to 1/vī.
[a=] /22
Proof Sketch. of Theorem 5.1. By invoking Fact 5.2 of initialization at population level, it is guaranteed that a To = | < 0.1 after running population EM for at most To = O(1) iterations. By applying the nonincreasing property of (a')re we show that a' S To < 0.1 for t 2 Tb
For the case of n. 1/2), by applying the sublinear convergence guarantee in Proposition 5.3 and selecting t = O(c-)) the normalized regression parameters T O(t ATo) 0(2-1/2) s achieve + e-accuracy within + To = - 0(1 = (2) iterations.
For the case of の * (1/2, 1/2), namely g0 + 0, by using the bound for the contraction factor a++1+ fa in Proposition 5.4 repeatedly, then a To /a & a / I 10(1 - c[30003) for some > 0. Then by selecting = ((log((/e)((( log(11loooo111-1
c) 10lo://////1-1((010000900 = (log((//e), is sufficient to show that a S
Fact 5.2. (Initialization at Population Level) Let a' = |001 N(00-1,,' for all t. E Z4 be the t-th iteration of the EM update rules (00,)))l/o and N v) at the population level. If we run EM at the population level for at most To = 36 iterations, then TTo < 0.1.
( and B := tanh((')=
Remark. By using such nonincreasing and bounded property Fact 4.3 and applying the EM update rules in Identity 4.1, we show that the regression parameters will converge to small region ||0*1//a < 0.31 within
10

---

Published in Transactions on Machine Learning Research (01/2026)
only three iterations of EM updates. Then by invoking the following upper bound in Proposition 3.3, it takes at most 33 iterations for the value to drop below 0.1. Thus, Fact 5.2 is established (see proof in Appendix D, Subsection D.2). Similarly, we can show that in the worst case of sublinear convergence with balanced initial guess x² = (2: 2) and a = ||00 - oo, we have a = ||@8 = 0.31 and a' 2 0.1 for all t I 9 by using the matching lower bound in Proposition 5.3, which also matches the numerical results in Fig. 1b.
Proposition 5.3. (Sublinear Convergence Rate) Let a' == | = ,|M/('->_\\//o and B == tanh(v")
(100-1,,'-1 for all t E Z+ be the t-th iteration of the EM update rules (MM().))l/ and N(0, v) at the population level. Suppose that a" E0,00.30 (0,0.31), then
1
a' Vot 18 au 112
1I Zz0;
when the initial guess of mising weights is balanced TO (2: 2), namely 80 tanh vO == -|/=0 311 0, then
1
a² 2
Vt E Zzo-
6t 22 2t + 1) + )2
upper bounds
of vs. lower bounds
2263) U
1.0
1.0
0.9
0.9
0.8
0.6
terations of -0.00.05
terations -i""00""0000
0.5
Iterations o'ts" (a"=0.05)
Iterations of to (2.02
a'lu" (1]-0.1)
Ierations of d'ta" (d9=0.1)
upper bounds for afte" io"" 0.002
0.4
bounds aije* (sf -0.02)
upowr bounds e'tr" 0.055
lower bounds for o'je" (e 0.05)
0.3
bounds etaa" =011
0.3
30
100
harations
terations
(a) Upper bound illustration for sublinear convergence with balanced initial mixing weights.
(b) Lower bound illustration for sublinear convergence with balanced initial mixing weights.
Figure Sublinear convergence rate bounds for a == 10/1/// as shown in Proposition 5.3, with different. initial values a 0.02, 0.05, 0.1 and balanced initial guess 30 = T 1 over 200 EM iterations.
Remark. The above Proposition 5.3 (see proof in Appendix D, Subsection D.1) highlights that the population level, when the initial guess of the mixing weights is balanced, the EM updates exhibit an excessively slow convergence rate. To establish the above tight bounds, present much tighter lower and upper bounds for a+1 with the same coefficients of [a=13 in equation 11 (see remark Proposition 4.4)). Furthermore, we developed a technique of "variable separation" by interpreting the upper bound a f+1 < a - "3/""1//00 /01]/////11// +1++0 8a*) in equation 11 as the discretized version of a differential inequality da < - Consequently, we derived the simple upper bound for a' in Proposition 5.3 by solving the discretized version the differential inequality. For sufficiently small a', we could further establish a tighter upper bound a < a² 3[a" 10ja²"3), and the "variable separation" technique could be applied to derive the other upper bound for a' by introducing Lambert W function (see Section 4.13 Lambert W-Function in Olver et al. (2010)), namely a' < 1/1 (2) (2))2 10
In(0(aa)]]) 1) (see remark the proof of Proposition 5.3 in Appendix D, Subsection D.1). As a approaches the logarithmic term in the above upper bound for a' becomes negligible, and the upper bound be approximated by 1/ 6t + (2)).. Our lower/upper bounds for at are tight given the balanced initial guess x (b) 1), since 1 In(et + c') for some constants c, > 0.
11

---

Published in Transactions on Machine Learning Research (01/2026)
Proposition 5.4. (Contraction Factor for Linear Convergence) Let at = 1001//0 || "1"1"/////0 1 and 8 == tanh((')= NN00-1, ,i=1) for all I. E 244 be the t-th iteration of the EM update rules (M(O0,)ll/ and () v) at the population level. Then 3 == lim 3r erists and
(1) if 5 = 0, then g = 0,
(0) if 5 > 0, then < 1000 S fr s 30
(ti) if 8 < 0, then 0 8 2 gt 2 80.
Suppose that a' E (0,0.1), then
a+1 18
a²
Remark. Proposition 5.4 (see proof in Appendix D, Subsection D.3) provides the upper bound for the contraction factor a*+1/</ of linear convergence when a² -|@0 1l/ is small enough, which is strictly less than when the initial guess of mixing weights T0 * ( f). This upper bound for contraction factor is obtained by establishing the bounds (sec Subsection A.3 and Appendix C) for expectations in Identity 4.1, thereby a/t2/a" < 1 (5/3))aaaa (3 11 (4 Furthermore, we can provide the lower/upe S In | - In | < -[a0|3/4 when a < 0.1, < v2/5 (see proof of Proposition 5.4 and its remark in Appendix D, Subsection D.3). Also, we can show the lower bound for the contraction factor a²+1/a² 2 1 - -3/aa - [39? 2 - ) - [ by using Proposition 5.3 and Fact 4.3 when a < 0.1 sulficiently small (see Appendix C for the derivation of the first inequality). Since a+*1 /a" is lower bounded and upper bounded by some constants which are in the range of (0, 1) when t is sufficiently large, a" converges linearly when the initial guess Tº * (2 2) is unbalanced (namely go +).
bounds
for 8 by showing that (300
6 Sinite-Sample Level Analysis
In this section, we give a finite-sample analysis and present light bounds for sample complexity, time complexity, and final accuracy (Theorem 6.1) by coupling the analysis of population EM and finite-sample EM and establishing statistical errors (Propositions 6.3, 6.4) in the overspecified setting.
Main theorem 6.1. (Convergence Rate at Finite- SSmite Level for Fized Mixing Weights)
Suppose 2MLR model is fitted to the overspecified model with no seporation 0 = ō, given miring weights n' T and Ω (d log 1 log }) samples:
(sufficiently unbalanced) if -
Advlog&1= n
finite-sample EM takes at most T
n (1 - - 1 aviog
iterations to achieve 1/00= (110-- 111 dvvls [ )))
(sufficiently balanced) if 1| 2111 S ddvlog _
fimite-sample EM takes at most T = = (1 avving 1 )t)
(I
(1 [dvlog + [[ :). with probability at least 1 - T(ō + 8¹).
iterations to achieve 10/1//0
10/==O0 = 0
Remark. Theorem 6.1 (see proof in Appendix G, Subsection G.2) provides the final statistical errors, time complexity, and sample complexity the specific setting of fixed mixing weights. There is a tight connection between Theorem 6.1 at the finite-sample level and Theorem 5.1 the population level. In particular, by setting the final accuracy in Theorem 5.1 for regression parameters to be ((d/n)) for the "sufficiently unbalanced" case, we intuitively obtain the required iteration complexity T O(log 4) Oloo 3) for the "sufficiently unbalanced" case, which is consistent with the iteration complexity Ollog h) in Theorem 6.1 at the fiiieesampll level. Moreover, by setting the final accuracy in Theorem 5.1 for regression parameters to be ((d/n))1/4 for the "sufficiently balanced" case, we intuitively obtain the required iteration complexity T 2 (((/d))/2) for the "sufficiently balanced" case, which is consistent with the time complexity (((/))//2 in Theorem 6.1 at the finito-sample level. This main theorem addresses all regimes where the mixing weights remain fixed, x' n. In contrast, Theorems 1 and 3 in Dwivedi et al. (2020b) cover only
12

---

Published in Transactions on Machine Learning Research (01/2026)
boundd for
bound 11/
log
v log
/|pr
log
log
11t 2
V
Vog
(a) Bounds of the time complexity T in both sufficiently unbalanced and balanced cases.
(b) Bounds of the statistical accuracy 110 0- 1'/1/a in both sufficiently unbalanced and balanced cases.
Figure 5: Theorem 6.1 provides bounds on time complexity and statistical accuracy for fixed mixing weights x² = n in both sufficiently unbalanced and balanced cases.
the cases of sufficiently unbalanced Gaussian mixtures, where | 2 (((d/))//4 and the special case T0 (2) )); while our main theorem covers all regimes of mixing weights, including the "sufficiently balanced" case ||7" I11 x (((d/))//)) which is handled by introducing our proof technique of "variable separation". In addition developing new proof techniques, we improve the bounds in Theorem 3 of Dwivedi al. (2020b)
for statistical accuracy O ( [[<vlos:
1 Vlog log 3 -ce)
time complexity O ((3)² log á log + and sample 1
n complexity (d log & log log 4) for e' E (0, 1/4) the case of balanced mixing weights T" = ( 4) The previous bounds diverged as e' whereas our time and sample complexity remain stable.
Intuitive Explanation of Theorem 6.1. The final statistical accuracy of the MLE estimate is governed by the invertibility of the Fisher Information matrix, which is the second-order derivative of the negative population log-likel With an unbalanced estimate of mixing weights, the negative log-likelihood maintains the [a]² = |/2 lerm, which ensures the Fisher Information matrix (w.r.t. the regression parameters) is invertible. As a well-established result (Van der Vaart, 2000), this invertibility guarantees that the MLE estimate achieves the standard parametric rate of order n 1/2 and therefore the final accuracy of the EM algorithın is also proportional to n -1/2. However, when a balanced estimate is given, the critical term [a]2 vanishes, causing the Fisher Information matrix to be singular. This singularity slows down the standard parametric rate of final accuracy (Dwivedi et al., 2020b), resulting in converged a" that exhibits rate proportional to n 11/4
Proof Sketch. of Theorem 6.1. Initially, Fact 6.2 ensures that after at most To 0(1) finite-sample EM iterations, we have To = ||@ < 0.1 with high probability. Therefore, without loss of generality, we assume a < 0 0. For simplicity, we denote finite-sample and population updates for the norm of normalized regression parameters as a a², respectively.
We upper bound the (t + 1)-th finite-sample EM iteration "+1 using the triangle inequality at+1 < +5++1 The first term represents the statistical error |a - (0 ((d/((()))11) (see Proposition 6.4), while the second term a' is the population EM update, which is bounded by the upper bounds provided Appendix C.
For the case where 3r = 5 ((d/n))/44 by selecting sufficiently large sample size and simplifying the expression, we derive the recurrence relation ++1 ((dd/))) ((d//))/+//8)) /89) I (1 c(3")3) ((d/n))/*//)) for some 0. Using the approximation 1 - 2f & xxp(-c((0]2), express the above relation
13

---

Published in Transactions on Machine Learning Research (01/2026)
By choosing T 0 (log(n (n we achieve 6-accuracy for the normalized regression parameters, yielding: a² I (((d/n))/1//)
recursively, leading to: - -
In the case where 8 = < (((d/n)²/") we similarly derive a recurrence relation by selecting sufficiently large sample size n and simplifying the expression, a+11 S a -daa"3 for some c <> when a' 2 ((d/n)) (/4)
This relation can be viewed as the discretized version of the ordinary differential inequality: da dt. By applying the method of "variable separation" this discretized version, we obtain a² (t(-1122 when select T ((dd/n))/a)- = (((n/d)))) (/2) Fact 6.2. (Ivitialization at Finile-Sample Level) Let at == ||0'1|/o tanh(v") = NN,(0'1,,'* ,,²=)) for all t E Z+ be the t-th iteration of the EM update rules M| (0, v)ll/a and (0, v) at the finite-sample level. If we run EM at the finite-sample level for at most To = ( iterations with n = 2 (n V log 1)) samples, then To < 0.1 with probability at least 1
a' 2 @((d/n))/4). To achieve a I {((d/))))),
,0-000 and 8 =-
Remark. Fact 6.2 (see proof Appendix G, Subsection G.1) is established a similar way as Fact 5.2 at the population level, but requires selecting a sufficiently large number of samples n Odd V log })) guarantee that the statistical error is small enough.
Proposition 6.3. (Statistical Error of Mixing Weights) Let (0, and N,, (0, be the EM update rules for mixing weights tanh(u) == x (11) (2) at the population level and finite-sample level with n samples, and n Z log 3, 8 (0, 1), then
1101/a 1+ |l
1100
log 1 n1
(N)(0,)) N(O, -= min
with probability least. 6-
Remark. Proposition 6.3 (see proof in Appendix F, Subsection F.1) proved by applying the elementary inequality for tanh and the concentration inequality, which is based modified log-Sobolev inequality in Ledoux (2001) (sce Appendix E, Subsection E.1 and Subsection E.2).
Proposition 6.4. (Statistical Error of Regression Porumeters) Let (0, and Mn(0, v) be the EM update rules for regression parameters 9 at the population and finite-sample levels with samples, and if n 2 d dVVlog ; E (0, 1), then with probability at least 1 1-
(0, - -MO = (
V log 1
n
and i 2 v log v log" J, 8' E (0, then with probability at least 1 - (6 - 8'),
[0, (000 (tanh |o| 1001///0)) d v log
n
Remark. Proposition 6.4 (see proof in Appendix F, Subsection F.4) demonstrates our sample complexity n = 2(d Vlo }), whereas Lemma of Dwivedi et al. (2020b) presents sample complexity 2( }). The difference lies in the techniques used: their multiplicative log factor is derived through the standard symmetrization technique with Rademacher variables and the application of the Redoux-Tallgrann contraction inequality (see the proof of Lemma 1 on page 44 of Dwivedi et al. (2020b) and Appendix E of Kwon et al. (2021) for Lemma 11). In contrast, we obtain our additive log factor by applying the rotational invariance of Gaussians and expressing the & norm of the orthogonal error as the geometric mean of two Chi-square distributions (sce Appendix E, Subsection E.3).
7 Discussions on Extensions
In this section, we discuss the differences between results of 2MLR and 2GMM, extend our analysis from the overspecified setting the low-SNR regime, and examine the challenges of analyzing overspecified mixture models with multiple components.
14

---

Published in Transactions on Machine Learning Research (01/2026)
7.1 Convergence and Sample Complexity: 2MLR vs 2GMM
In the overspecified setting (signal-t-nnois--aatte (SNR) 17 ||0 - 0), the population EM update rules for 2MLR are as follows (see equation 10) for the normalized regression parameters a² = |10'11/o and imbalance of mixing weights 3² = tann(v²) = (1) (2):
a+tl |+] E[tanh(a' X + ge+l BB[tan(aa'XX + v²) where X Ko([æ))
π
In contrast, for 2GMM, the population EM update rules are (see page 6 of Weinberger & Bresler (2022)):
a - Eljanh(a' Z + v')Z], = Bltanh(a' + v²]] where Z ~ 1),
Here, Ko denotes the modified Bessel function of the second kind, the density function of X has exponential tail since Kg(æ)) x V 2n exp(-xx) for - 00, and Z follows standard normal distribution, which is sub- Gaussian (Wainwright, 2019). At the population level, we still can establish the sublinear convergence rates of a' = 0(1/V)) with balanced initial mixing weights (.30 = 0), and linear convergence rates with unbalanced initial mixing weights (3" # 0) for both 2MLR and 2GMM by bounding the above expectations.
However, at the finite-sample level, convergence guarantees differ between 2MLR and 2GMM. For 2MLR, Theorem 6.1 indicates that a sample size n = Q2 V log }) is sufficient to ensure convergence. In contrast, for 2GMM, we can show that a smaller sample size n = D2 V log 4) is required to achieve the same probability 1 1 T5 over T iterations. Intuitively, the difference arises because, for finite n, the sample averages 1 E tan, + Z2 Σx= tanh(aZZ + +)) converge to their expectation more rapidly when {Z,]== are sub- Gaussan (in 2GMM) compared to when they have an exponential tail in probability (in 2MLR). This faster convergence in the sub-Gaussian case allows for reliable parameter estimation with fewer samples.
7.2 Extended Analysis in Low SNR Regime
To further exlend our analysis from the limiting case of n= ||0*1//a = 0 to the case of finite low SNR (n S 1) of Mixed Linear Regressions (MLR), we can still obtain the recurrence relations of a', 8 follows:
a a=1 = Eltanh(a'X x + x')x] + n d'E[tanh(a'' X + x²)*++++(11
(12)
g--1 = E[lanh(a'X + D²)] + n18" p' BB[laahhaa' + + + O(r²),
where =tan(("") is the imbalance of mixing weights of the ground truth, and p² = (0", (0,00)))/ / [10*1) is the cosine angle between the ground truth and the estimated regression paramcters at t-th iteration.
While equation 10 gives the EM update rules of a in the overspecified setting of 1 = O, we can also obtain the EM update rules of a², 88 in the low SNR regime (equation 12) with the help of introducing n, pf by using the perturbation method as discussed in Appendix H. The differences between the EM update rules of a g in the finite low SNR regime S 1 and the EM update rules of a', 33 in the overspecified setting = 0 come from the presence of 17, pf in the EM update rulcs. In the overspecified setting, the EM update rules of , are given by equation 10 with 7 = 0 and are independent of p', where the cosine angle p² = p" remains the same as the initial value p as shown in Identity 4.1 and Figure 1a. But in the finite low SNR regime 17 7 1, the EM update rules of a², 8 are given by equation 12 with v and p²: where the cosine angle p is updated by the EM update rules of pt as follows when ny is sufficiently small (see details in Appendix H, Subsection H.3):
1+ p'= + (1-111 (tt)) (B[tanh(a' X + +1)) - a a'E(tannh 2 (a X + + x1)x))/
X))p))))))RRR//il R[tanh(a' X v') x (13)
The equation 12 and equation 13 (sce proof in Appendix H, Subsoction H.3) are proved by using the perturbation method as discussed in Appendix H, Subsection H.2. Moreover, the expectations E/tanh(aa X + " X + El,anhh (amaah(a'xxx""" + +z')] and E[tanh? (a'x) X + x² in equation 12 and equation 13 can be approximated by scries expansions of a² around af as in Appendix H, Subscction H.1. The remainder terms of O(7²) in equation 12 and equation 13 hide the effect of a', 1,, in the EM update rules. Consequently, by substituting the series expansions of the expectations into equation 12 and equation 13,
Remark.
15

---

Published in Transactions on Machine Learning Research (01/2026)
can obtain the following approximate dynamic equations of a', , p² in the finite low SNR regime:
(a+1))
a1 [ 81(1 (1 (B999) + n88 x
(1 - [ (893))
ge+1
p'a'(1 18
+ +0(1a99)+067) (14)
p²+1
(1-) (1-00 189))
In particular, when 17 = O, we have p²+ = p' by Identity 4.1, and the above approximate dynamic equations reduce to the approximate dynamic equations of Bt in the overspecified setting, which aligns with our previous results obtained in Proposition 4.4. Also, finer analysis shows that |p'| = 1 implies |p'+ = even when 17 # 0 (see the remark of Appendix H, Subsection H.3), therefore the EM iterations of regression paramcters have the same direction as the ground truth if the initial value of the regression parameters is in the same direction as the ground truth.
7.3 Generalizing Multiple Components
As shown in the numerical experiments of Dwivedi et al. (2020b), the EM algorithm for overspecified Gaussian mixtures with multiple components can also exhibit the slow convergence of final accuracy in terms of sample size The order of the final accuracy O((d/n)1/4) demonstrales slower convergence in the sulficiently balanced case compared to the final accuracy ((d//))//) in the sufficiently unbalanced case for 2MLR and 2GMM in the overspecified setting, which is not merely coincidence, but a general phenomenon. However, it remains an open problem to establish the convergence guarantees for the final accuracy, time complexity and sample complexity for overspecified mixture models with multiple components. model with multiple components, is necessary carefully examine the many-to-one correspondence between the components of the fitted model and those of the ground truth (sce page of Qian et al. (2022)). Therefore, the assumption of well-separated regression parameters and the requirement for good initialization of the mixing weights, as in existing works such as Kwon & Caramanis (2020), no longer hold. This requires a more careful analysis and development of more advanced techniques for the analysis of overspecified mixture models with multiple components.
for a general overspecified
8 Experiments
In this section, validate our theoretical findings in the previous sections with numerical experiments. The code for our numerical experiments is available at attps://githuu:
_mlr. Trajectory of EM Iterations. We sample 2,000 independent and identically distributed (i.i.d)) two- dimensional covariates and additive noises from Gaussian distributions and set the true regression parameters 0* -. 0. Fig. la, all the iterations are nearly perfect rays from the origin to the initial point, which aligns with Identity 4.1.
Dynamics of the EM iteration. In the overspecified setting, we show that the approximate dynamic equations (a' a/'''///'' ze [8'] and (8* -/+ zs a'attl when the regression parameters are small enough in Proposition 4.4. We demonstrate the linear correlations in Fig. 2, therefore, our experiments validate Proposition 4.4. For the experimental settings, we specify a = 0.1 and consider different values of St E (0.1, ... ..., 13.
Convergence Rate in Regression Parameters. Fig. 3a presents the fast convergence with unbalancod initial guess and the slow convergence with balanced initial guess, which in agreement with our theoretical results in Theorem 5.1.
Sublinear Convergence Rate with Balanced Initial Guess. Fig. 4a and Fig. 4b exhibit the slow sublinear convergence rate given the balanced initial guess, which aligns with our sublinear theoretical bounds. Hence, our experimental results validate our analysis in Proposition 5.3.
Initialization Phase in the Worst Casc. In Fig. 1b, we show the iterations of a² the worst case with balanced initial mixing weights ~0 2), i.c., 5 tanh nd - O, and infinite initial regression parameters a² = |0011/a -> oo. In the worst case, show that at 2 0.1 for all t & 9 by using the theoretical
16

---

Published in Transactions on Machine Learning Research (01/2026)
matching lower bound for the worst case in Proposition 5.3. Also, we demonstrate that a' < 0.1 for all t 2 36 (Fact 5.2) by applying the theoretical upper bound in Proposition 5.3. As a R 0.1 by numerical evaluations, and 20 > 9 and 20 < 36, the theoretical results from Proposition 5.3 and Fact 5.2 are consistent with the numerical results shown in Fig. 1b.
Converged Mixing Weights and Initial Guesses. In Proposition 5.4, we prove that converged mixing weights 3 are nonzero for a nonzero initial guess 8 + 0, and provide lower bound for 3 We observe the correlation between the converged 3" and varying 8 uniformly sampled from [0.01, 0.99], with a e {0.1, 0.3, 0.5}. These theoretical findings are supported by numerical results in Fig. 3b.
9 Conclusions
In this paper, we thoroughly investigated the EM's behavior in overspecified two-component Mixed Linear Regression (2MLR) models. We rigorously characterized the FM estimates for both regression parameters and mixing weights by providing the approximate dynamic equations (Proposition 4.4) for the evolution of EM estimates and establishing the convergence guarantees (Theorems 5.1, 6.1) for the final accuracy, time complexity, and sample complexity at population and finite-sample levels, respectively. Notably, with unbalanced initial guess for mixing weights, showed linear convergence of regression parameters in (log((/)e) steps. Conversely, with a balanced initial guess, sublinear convergence occurs in O(--2) steps to achieve e-accuracy. For mixtures with sufficiently imbalanced fixed mixing weights || - 1l ((d/n))1/) we establish statistical accuracy ((d/n))/)2) whereas for those with sufficiently balanced fixed mixing weights || - 2 1l1 & O((d/n)'/4) the accuracy is O(d//)))/4). Additionally, our novel analysis sharpens bounds for statistical error, time complexity, and sample complexity needed to achieve final statistical accuracy of ((dff))//) with fixed sufficiently balanced mixing weights. Furthermore, we discussed the differences between results of 2MLR and 2GMM, and extended our analysis from the overspecified setting to the finite low SNR regime.
Building upon the analysis and established connections between the diffusion model objective and the classic EM algorithm in GMM (Shah al., 2023), we foresee exlending this analysis from GMM to MLR and establishing the time and sample complexities involved in learning the diffusion model objective, as discussed in recent works (Chen et al., 2024a; Gatmiry et al., 2024). The practical applications (haplotype assembly (Cai et al., 2016; Sankararaman et al., 2020) and phase retrieval (Klusowski et al., 2019; Chen et al., 2015)) of mixture models such as MLR and GMM can spur significant interest within the statistics community toward establishing rigorous theoretical foundations for generative diffusion models.
References
Thomas D. Ahle, Michael Kapralov, Jakob T. Knudsen, Rasmus Pagh, Ameya Velingker, David WoodrufT, and Amir Zandieh. Oblivious sketching of high-degree polynomial kernels, 2020.
Sivaraman Balakrishnan, Martin Wainwright, and Bin Yu. Statistical guarantees for the EM algorithm: From population to sample-based analysis. The Annals of Slatislies, 45(1):77-122) 120, 2017. doi: 10.1214/ 16- A6-A051435.
Evelyn ML Beale and Roderick JA Little. Missing values in multivariate analysis. Journal of the Royal Statistical Society Series B: Statisticol Methodology, 37(1):129- 114,, 1975.
Changxiao Cai, Sujay Sanghavi, and Haris Vikalo. Structured low-rank matrix factorization for haplotype assembly. IEEE Journal of Selected Topics in Signal Processing, 10(4):647 657, 2016.
Emmanuel J Candes, Xiaodong Li, and Mahdi Soltanolkotabi. Phase retrieval via wirtinger flow: Theory and algorithms. IEEE Transactions Information Theory, 61(():1985 2007, 2015.
Jiahua Chen. Optimal rate of convergence for finite mixture models. The Annals of Statistics, pp. 221-233 1995.
17

---

Published in Transactions on Machine Learning Research (01/2026)
Sitan Chen, Vasilis Kontonis, and Kulin Shah. Learning general gaussian mixtures with efficient score matching. arXiv preprint arXin:2404.18880 2024a.
Yudong Chen, Xinyang Yi, and Constantine Caramanis. A convex lormulation for mixed regression with two components: Minimax optimal rates. arXiv preprint arxi::1312. 7006, 2015.
Yudong Chen, Dogyoon Song, Xumei Xi, and Yuqian Zhang. Local minima structures in gaussian mixture models. IEEE Transactions on Information Theory, 2024b.
Elliott Ward Cheney. Introduction to approzimation theory. McGraw-Hin 1966.
Constantinos Daskalakis, Christos Tzamos, and Manolis Zampotakis. Ten steps of EM suffice for mixtures of two Gaussians. In Conference on Learning Theory, pp. 704-710. PMLR, 2017.
Richard D De Veaux. Mixtures of lincar regressions. Computational Statistics & Data Analysis, 8(3):227-245, 1989.
Arthur P Dempster, Nan M Laird, and Donald B Rubin. Maximum likelihood from incomplete data via the EM algorithm. Journal of the royal statistical society: series B (methodological)) 39(1):1 1977.
Abhishek Dhawan, Cheng Mao, and Ashwin Pananjady. Sharp analysis of EM for learning mixtures of pairwisc differences. arXiv preprint arXiv:2302.1000 2023.
Natalie Doss, Yihong Wu, Pengkun Yang, and Harrison H Zhou. Optimal estimation of high-dimensional location gaussian mixtures. arXiv preprint arXic:2002.05818 2020.
Rick Durrett. Probubility: theory and eramples. Cambridge university press, 2019.
Raaz Dwivedi, Nhat Ho, Koulik Khamaru, Martin Wainwright, Michael Jordan, and Bin Yu. Sharp analysis for weakly identifiable models. In International Conference on Artificial Intelligence and Statistics, pp. 1876. PMLR, 2020a.
pnpeectationmmxiininn
Raaz Dwivedi, Nhat Ho, Koulik Khamaru, Martin J. Wainwright, Michael I. Jordan, and Bin Yu. Singularity, misspccification and the convergence rate of EM. The Annals of Statistics, 48(6):3161 3182, 2020b. doi: 10.1214/19-0011924
Quentin Fruytier, Aryan Mokhtari, and Sujay Sanghavi. Learning mixtures of experts with EM: A mirror descent perspective. In Forly-second International Conference Machine Learning, 2025.
Khashayar Gatmiry, Jonathan Kelner, and Holden Lee. Learning mixtures of gaussians using diffusion models. arXiv preprint 2rxiv:2404.18880 2024.
Avishek Ghosh and Ramchandran Kannan. Alternating minimization converges super-linearly for mixed linear regression. In International Conference Artificial Intelligence and Statistics, pp. 1093-1103. PMLR, 2020.
Izrail Solomonovich Gradshteyn and Iosif Moiseevich Ryzhik. Table of integrals, series, and products. Academic press, 2014.
Philippe Heinrich and Jonas Kahn. Strong identifiability and optimal minimax rates for finite mixture estimation. The Annals of Statistics, 46(6A):2844 - 2870, 2018. doi: 10.1214/17-A0S164.
Nhat Ho and XuanLong Nguyen. Convergence rates of parameter estimation for some weakly identifiable finite mixtures. The Annols of Statistics, 44(6):2726 2755, 2016. doi: 10.1214/16-A0S1444
Nhat Ho, Chiao- Yu Yang, and Michael I Jordan. Convergence rates for gaussian mixtures of experts. Journal of Machine Learning Research, 23 2333)): 81, 2022a.
Nhat Ho, Chiao- Yu Yang, and Michael I Jordan. Convergence rates for gaussian mixtures of experts. Journal of Machine Learning Research, 23(323):1-88 2022b.
18

---

Published in Transactions on Machine Learning Research (01/2026)
Chi Jin, Yuchen Zhang, Sivaraman Balakrishnan, Martin J Wainwright, and Michael Jordan. Local maxima in the likelihood of Gaussian mixture models: Structural results and algorithmic consequences. Advances in neural information processing systems, 29, 2016.
Normal L. Johnson, Samuel Kotz, and N. Balakrishnan. Distributions in Statistics: Continuous Univariate Distributions, Volume 1, Second Edition. Houghton-Mifflin, 1970.
Michael Jordan and Lei Xu. Convergence results for the EM approach mixtures of experts architectures. Newral networks, 8(9):1409-1453 1995.
Jason M Klusowski and WD Brinda. Statistical guarantees for estimating the centers of two-component Gaussian mixture by EM. arxiv preprint or Xiv: 02280, 2016.
Jason M. Klusowski, Dana Yang, and W. D. Brinda. Estimating the coefficients of a mixture of two linear regressions by expectation maximization. IEEE Transuctions on Information Theory, 65(6):3515 3524, 2019. doi: (0.1109/TII) 201.T.....29916222
Jeongyeol Kwon and Constantine Caramanis. EM converges for a mixture of many linear regressions. International Conference on Artificial Intelligence and Stalistics, pp. 1727-1736. PMTRR, 2020.
Jeongyeol Kwon, Wei Qian, Constantine Caramanis, Yudong Chen, and Damek Davis. Global convergence of the EM algorithm for mixtures of two component linear regression. In Conference on Learning Theory, pp- 2055 2110. PMLR, 2019.
Jeongveol Kwon, Nhat Ho, and Constantine Caramanis. On the minimax optimality of the EM algorithm for learning two-component mixed lincar regression. In International Conference on Artificial Intelligence and Slatislics, pp. 1405 1413. PMLR, 2021.
Jeongyeol Kwon, Wei Qian, Yudong Chen, Constantine Caramanis, Damek Davis, and Nhat Ho. Global optimality of the em algorithm for mixtures of two-component linear regressions. IEEE Transactions on Information Theory, 2024.
Jeongyeol Kwon et al. Statistical learning with latent variables: mirture models and reinforcement learning. PhD thesis, The University of Texas at Austin, 2022.
Beatrice Laurent and Pascal Massart. Adaptive estimation of quadratic functional by model selection. Annals of statistics, pp. 1302-1338, 2000.
Michel Ledoux. The concentration of measure phenomenon. Number 89 in Mathematical Surveys and Monographs. American Mathematical Soc., 2001.
Eric Lehman. Mathematics for computer science. Samurai Media Limited, 2017.
Zhankun Luo and Abolfazl Hashemi. Unveiling the cycloid trajectory of EM iterations in mixed linear regression. In International Conference on Machine Learning, pp. 33329 33382. PMLR, 2024.
Tudor Manole and Nhat Ho. Uniform convergence rates for maximum likelihood estimation under two- component gaussian mixture models. arXiv preprint arXiv:2006. Xix::2006000744 2020.
Tudor Manole and Nhat Ho. Refined convergence rates for maximum likelihood estimation under finite mixture models. In International Conference on Machine Learning, pp. 14979-15006. PMLR, 2022.
Mohamed Ndaoud. Sharp optimal recovery in the two-component Gaussian mixture model. orXi preprint arXiv:1812.08078 2018.
Matey Neykov, Zhaoran Wang, and Han Liu. Agnostic estimation for misspecified phase retrieval models. Advances in Neural Information Processing Systems, 29, 2016.
Huy Nguyen, TrungTin Nguyen, and Nhat Ho. Demystifying softmax gating function gaussian mixture of experts. In A. Oh, T. Neumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.). Advances in Neural Information Processing Systems, volume 36, pp. 4624-4652. Curran Associates, Inc., 2023a.
19

---

Published in Transactions on Machine Learning Research (01/2026)
Huy Nguyen, TrungTin Nguyen, and Nhat Ho. Demystifying softmax gating function in gaussian mixture of experts. Advances in Neural Information Processing Systems, 36:4624-4652, 2023b.
Huy Nguyen, Pedram Akbarian, Panqi Yan, and Nhat Ho. Statistical perspective of top-K sparse softmax gating mixture of experts. In The Twelfth International Conference on Learning Representations, 2024.
Frank W Olver, Daniel W Lozier, Ronald Boisvert, and Charles W Clark. NIST handbook of mathematical functions. Cambridge university press, 2010.
Andrei D Polyanin and Alexander V Manzhirov. Handbook of integral equations. CRC press, 2008
Wei Qian, Yuqian Zhang, and Yudong Chen. Structures of spurious local minima in k-means. IEEE Transactions Information Theory, (8(1))395-422) 422,, 2022. doi: 10.1109/TIT TT1/0///TT..21.1111111 3024.31
Richard A Redner and Homer F Walker. Mixture densities, maximum likelihood and the EM algorithm.
SIAM review, 26(2):195-22 239, 1984.
Amirhossein Reisizadeh, Khashayar Gatmiry, and Asuman Ozdaglar. Em for mixture linear regression with clustered data. In International Conference on Artificial Intelligence and Statistics, pp. 2341-2349.
PMLR, 2024.
Nathan Ross. Fundamentals of Stein's method. Probability Surveys, 8(nonc):210 293, 2011. doi: 10.1214/ 11-PS182.
Walter Rudin. Principles of Mathematical Analysis. McGraw-Hill, New York, 3rd edition, 1976.
Abishek Sankararaman, Haris Vikalo, and François Baccelli. Comhapdet: a spatial community delection algorithm for haplotype assembly. BMC genomics, 21:1 14, 2020.
Alcksci Shadrin. Twelve proofs of the markov inoquality. Approzimation theory: volume dedicated to Borislav Bojanor, pp. 233 298, 2004.
Kulin Shah, Sitan Chen, and Adam Klivans. Learning mixtures of gaussians using the ddpm objective. Advances in Neural Information Processing Systems, 36:19636 19649, 2023.
Aad W Van der Vaart. Asymptotic statistics, volume 3. Cambridge university press, 2000.
Martin J Wainwright. High-dimenssioal statistics: A non-osymplolic viewpoint, volume 48. Cambridge university press, 2019.
Michel Wedel and Wayne DeSarbo. A mixture likelihood approach for generalized lincar models. Journal of classification, 12:21 55, 1995.
Nir Weinberger and Guy Bresler. The EM algorithm is adaptively-optimal for unbalanced symmetric gaussian mixtures. Journal of Machine Learning Research, 23(103):1 79, 2022.
CF Jeff Wu. On the convergence properties of the EM algorithm. The Annals of statistics, pp. 95- 15-1,,, 1983.
Yihong Wu and Harrison H Zhou. Randomly initialized EM algorithm for two-component Gaussian mixture achieves near optimality in O(yn) iterations. Mathematical Statistics and Learning, 4(3), 2021.
Nuoya Xiong, Lijun Ding, and Simon Du. How ovarpaarameterizaiion slows down gradient descent matrix sensing: The curses of symmetry and initialization. orXiv preprint arX1o:2310.01169, 2023.
Ji Xu, Daniel J Hsu, and Arian Maleki. Global analysis of expectation maximization for mixtures of two Gaussians. Advances in Neural Information Processing Systems, 29, 2016.
Weihang Xu and Simon Du. over-parameeteriaation exponentially slows down gradient descent for learning a single neuron. In The Thirty Sizth Annual Conference on Learning Theory, pp. 1155 1198. PMLR, 2023.
Weihang Xu, Maryam Fazel, and Simon Du. Toward global convergence of gradient EM for parrttaranterized gaussian mixture models. Advances in Neural Information Processing Systems, 37:10770- 2024.
Ruofei Zhao, Yuanzhi Li, and Yuekai Sun. Statistical convergence of the EM algorithm on Gaussian mixture models. Flectronic Journal of Statistics, 14:632- 660, 2020.
20

---

Published in Transactions on Machine Learning Research (01/2026)
Appendices
A Lemmas in Proofs for Results of Population EM Updates
22
B Proofs for Results of Population EM Updates
C Lemmas in Proofs for Results of Population Level Analysis
28
D Proofs for Results Population Level Analysis
E Lemmas in Proofs for Results of Finite-Sample Level Analysis
34
Bounds for Statistical Errors of Finite-Sample Level Analysis
G Proofs for Results of Finite-Sample Level Analysis
47
H Extension to Finite Low SNR Regime
We organize the Appendices as follows:
Appendix A, we prepare lemmas for identities of hyperbolic functions, inequalities of tanh and simple expectations under the density involving Ko, and lower/upper bounds for expectations with tanh under the density involving Kg.
Appendix B, provide proofs for EM update rules M(0, NN, v) at the population level, the nonincreasing property of ||@*]]
[]. || - Ill and boundness of ||0' and the approximate dynamic equations of (MM ,")l//,, v²) when |0]]/a is small.
Appendix C, present lemmas on the evolution of a² = 1000 8r = =1((1== 72() in population EM, providing lower/un /upper bounds for a++1/(a((t (1))))1111)))))))))0)))))))))()) a +1 / and
Appendix D. provide proofs for convergence rates of regression parameters ||0]| at the population level. For T0 = (3) )), show sublinear convergence rate with time complexity O(e-2) to achieve e-accuracy. while for TO * (1, }), we demonstrate linear convergence rate with time complexity Ollog )). We also establish the existence of 8 = lim 3 and give an upper bound with g for the contraction factor of linear convergence.
Appendix E, we develop lemmas to bound errors at the finite-sample level by establishing tighter concentration inequalities using the modified log- Sobolev inequality, bounding statistics, and deriving inequalities for tanh.
Appendix F, we establish bounds for the projected error and statistical error in regression parameters for both easy EM and standard finite-sample EM, as well as for the statistical error in mixing weights.
Appendix G, we provide proofs for convergence rates at finite-sample level. For mixtures with sufficiently imbalanced fixed mixing weights || - Il 2 ((d/n))//4) the statistical accuracy is ((d/n))/2) whereas for those with sufficiently balanced fixed mixing weights || - 1 |l S ((d/)))/)), the accuracy is ((d/n)//4)
Appendix H, we extend our analysis to the finite low SNR regime (n 110~11/0 S 1), and provide the approximate dynamic equations for EM iterations a², 8 and the cosine angle p² == "'M,0'//100 |1|0011 in low SNR regime.
21

---

Published in Transactions on Machine Learning Research (01/2026)
A Lemmas in Proofs for Results of Population EM Updates
A.1 Identities of hyperbolic functions and expectations under the density involving Ko
Lemma A.1. (Identities of Hyperbolic Functions in Polyanin & Manzhirov (2008))
tanh(a b) tanh(-on b) [1 (bnh tanh(a) tanh(a + b) + tanh( b) tanh(b)[1- tann" tanh (b) tanh
+ Lanh"(b (a)
Proof. The first identity is proved by using the identities of Hyperbolic Functions in Supplement 1, Page 698 of Polyanin & Manzhirov (2008). The second one is proved by letting +- b, b in the first onc. ]
Eltanh(a +2)] be the expectations with respect to X (z) Ku([=)//x, random variable with probability density involving the Bessel function Ko, and B = tunh(u), then m(a,v) (a(a.v) and
Lemma A.2. Let m(a, 1/) == (x)
n(,
da
tanb(ax)X 32 Kann"(aX)
tanh t (aX) 3 tanh (aX)
m(a, (1 - B²
n(a, v) BE
Proof. By applying Leibniz integral rule or invoking the dominated convergence theorem to exchange the order of taking limit and taking the expectations (see Theorem 1.5.8, page 24 of Durrett (2019)), obtain the relation m(a, v) @n(a.v) Since X [x(x) Ka([=)) is symmetric random variable, we have:
Ba
1 Elf(X) B[f(- E[f(() + f( (-x]]xxxoll - [[f(( f(-X)]l
By substituting ((X) with tanh(a:X + v), tanh(a + x)X, and applying the above proven identities of hyperbolic functions, these two identities are proved.
Lemma A.3. (Expectations Gradshteyn & Ryzhik (2014)) For a E [0, 1), n E Z4, and random variable
X Ko([=)) then we have:
eexp( a o. X = arccos a
[()osh(ax)] = VI- a² B[X
E[X (2n - 1)!!²,
a²
where (2n - 1)!! = 3 x (2n- 1).
Proof. We prove the first and second identities by taking the limit v -+0 in the third formula in table 6.611 with modified Bessel function K,, Section 6.61 Combinations of Bessel functions and exponentials, Page 703 of Gradshteyn & Ryzhik (2014), and invoking cosh(az) = (exp(ax) cxp(=ax))/2.
We prove the third and fourth identities by letting in the 16th formula in table 6.561, Section 6.56-6.58 Combinations of Bessel functions and powers, Page 685 of Gradshteyn & Ryzhik (2014), and invoking T(n + +) 172-"(2m 1)!!.
22

---

Published in Transactions on Machine Learning Research (01/2026)
A.2 Inequalities of tanh and simple expectations under the density involving Ko Lemma A.4. For & E Rgo, we have:
tanh(t)
S t
cxp(-t)
3
2
t² - rt S
(tnh?(t)
S f
= t exp( --t)
3
3
6² 1 S
tanb
< ( 1s exp(-11
1 1 (anh"(1)
S 1 1 exp(( (-1)
Proof. By using Taylor expansion with remainder (see 5.15 Theorem, pages 110-111 of Rudin (1976))
for tanh(t), tanh (t), tanh (t), (t) and dropping out the non-negative remainder, we obtain the lower bounds for tanh(!), (t), tanh (4), (I). The upper bounds for tanh((), (t),) (anh((),)n))(()) (anh" tanh"(()
are established by introducing the exponential decay in the terms of ts, ,,,,,, respectively, where the analysis on the monotonicity of the gaps between the upper bounds and tanh(t), tanh"(t), ttnh tanh (t) ensures the correctness of the upper bounds when t is small, and the fact that tanh(t) is bounded but the upper bounds are unbounded as & increases ensures the correctness when t is large.
Lemma A.5. For any v, 2, E IR, we have:
+ (v) tanh² S (v) tanh?(t) S 1 + tanh? sinh
Proof. By substituting tanli (v) (t)))(() + x into 1 ++x S I-z: we otain the lower bound for i- (I) By substituting tanh?(v) + r,, sinh (t) + x into 1 < 1+ (+(((-1)))) (r- Itx (1 Vr e [0, 1], E Rg0, we establish the upper bound for (-tanh" (a)
]
Lemma A.6. For a E [0, 0.31), and a random variable X
Ka([zl)
we have:
9
d [eep((-a( = E[x exp(-a|X(]
I 1+ Sox
da
225
de da [llexp(-a = exp((xxxxxx(()(
+ 16k
18a²
d²
d(2a)2 B/cosh(2aX)) - E[X E[X 1)]
25 02
3
Proof. By Leibniz integral rule or the dominated convergence theorem to exchange the order of taking limit and taking expectations (see Theorem 1.5.8, page 24 of Durrett (2019)), we obtain the relations between the right-hand side expectations and the simple expectations shown above. Therefore, we obtain the closed form expressions for expectations on the right-hand side by taking derivatives of the closed-form expressions of simple expectations, which are given in Lemma of Subsection A.1. Consequently, we directly give the lower/ tower/upper bounds of rational functions on the left-hand side for these closed form expressions based on their Padé approximants, verified by analyzing the monotonicity, convexity of the gaps between the rational functions and the closed form expressions, and evaluating values at the boundaries of the interval of ]
A.3 Lower/Upper bounds for expectations with tanh under the density involving Ko
Lemma A.7. Let n(a, v)= := E[tanh(aXX + v)] be the expectation with respect to random variable with density X ~ (o((=))/T,, suppose a E [0, 0.31) and / = tanh(v) 2 0, then
n(a,v) 2 3 { 1 a²((1111 - ) + a (1 B²2 x
6
8² x 9
a
300
1 1+ 8a
1 16a
m(a,v) < 3. {1 a²(1 B²2 a1 B²) 6}
23

---

Published in Transactions on Machine Learning Research (01/2026)
Proof. We obtain the following lower/upper bounds for n(a,v) by applying the Lemmas of indentities in Subsection A.1 and invoking the Lemmas of inequalities in Subsection A.2.
tanh (aX)
n(a,v)
3E
3 tanh (a:)]
[ - (ax)((()))( 3 tanh (aX)) 9B - (1 B²) ttan - - (aX))
8 1 (1 ) (ax)² 3
(ax) exp(-a|X1)
-39 (ax)* (ax) exp( exp(-a|x1)
8 { 1 (1 83) a² a²
6
300
}
- B2
a+ x 9-a" -aa x + 16a
8a
n(a,v)
s BR [1 tanli (x) + sinhh? (ax)}} (ax]] [E1[ (1 - B²) tanh" (aX) (aX]]
2 [(ax)]
$ 3 ( 1 - (1 E (ax)²
= 3 {I - (1- 3²) aa² - a x 66
Lemma A.8. Let m(a, v) := E[tanh(axX X] be the expecatation with respect random variable with density X ~ /o((=))/T,, suppose a E [0, 0.31) and | = tanh(v) 0, then
m(a,v) a(1 88) { - a² 3 3-80 8 x
a2 225]
m(a,v) & a(1 - 39) { 1 {1- 2
225
- 3 x
a 32
1 +
1
25 a2
1 + 16a
Proof. We obtain the following lower/upper bounds for m(a,v) by applying Lemmas of indentities in Subsection A.1, invoking Lemmas of inequalities in Subsection A.2 and noting that sinh?(() cosh(2t)
2 > 82.
tanh(aX)X
m(a,v)
(1 )²)E
1 32 (ax)]
2 (1 B)E [lanh(aX)x(] + 8² tanh" = (1- B²) [|x Lanh(a] + 8² 12 (anh
2 (1 8²) {
[
E | (a|x)) - [(ax)))))) }
+ & [I ((ala)))
= (1 8 a x x (a 9 ---a a 225)}
m(a,v)
s (1 8º)E [tanh(a|x])|x]]] 32 sinh (ax))
(aa/x)) - 3 (a exp(axxp(aaa11] |x[(1 + B sinh((()))
S (1 B
S (1 83)
| (a|x]) - - (a/x))) exp(- esp(-a/\1i)]
(cosh (2a|X() 1)
+ (1- - 33
|X[(||X))
X|(a||X) exp((a(()))))
= (1 - 82) {a
3
225
a²
+
a x 32
3
1 8a
1
2
1 + 16a
Lemma A.9. Let ma(a) [[lanh(aXXX) be the expectation with respect to random variable with density X ~ Ko([x))/T, suppose a E [0, 0.31), then
3
a - 3 < mp(a) Sa
+ 8a
Proof. By letting 3 tanh(v) = 0 in the previous Lemma, the lower/upper bounds for mo(a:) obtained.
24

---

Published in Transactions on Machine Learning Research (01/2026)
B Proofs for Results of Population EM Updates
B.1 Proof for EM Update Rules
Theorem B.1. (Identity 4.1 in Section 4: EM Updates for Overspecified 2MLR) Suppose 2MLR model is fitted to the overspecified model with separation, where H = Ô. The EM update rules at the population level for = ja/o M ( w/ and lanh(v") = x1) - (2) = N(O0-1 1l=1) are then as follows.
00
Hr
tanh([10'~1111 o' Ja (o((l/))
|00|| B
1 110
lanh(v')
where 0 = 08 /a.
Proof. In the overspecified setting, namely 0* Ö, the expectation in the EM update rules (equation 3, equation 4) becomes
Ee xx) = ( (1
We decompose x x gl T x-, and (O span((*-1)z with B[x+] O. Since x,
y/a = e/o are independent each other, we obtain
(
g¹ (.- tanh
+
x--1
o²
001 ||--|| Eg Bo tanh
1|0-111
tanh
JE
+ v--1
||0-|1|
tanh(v")
1 tanh yr
+ +
It is well known that the Normal Product Distribution is == ge Kn((=)) see also Page 50, Section 4.4 Bessel Function Distributions, Chapter 12 Continuous Distributions (General) of Johnson et al. (1970) for more information.
g¹
||0t-1||
+ +x+t))=
|000
E
Kdan
tanh
||0--||| + t(-))
tanh(v')
E Aqea tanh
The above two equations immediately give the EM update rules and equation 10 is proved. Let x =
K([=() consider the direction 6f note that tanh (---1 + ||0-~1| tanh (2--1- - 0 x)) 0 for ll
| 00 0.
/ tanh (110-1112 1111) x. Ko(l=/)dx = [/m0 + +/"" tanh (110-11| v1-1)= x. Ko(lz))dr
00
= -1/00 (tanh (v--1 + ||0--11 ||| x))
tanh (1-
- 110 (10r-11 =)) Ko(lx|)dx > 0
Hence, we conclude that T
g
g0 T
thereby the proof is complete.
25

---

Published in Transactions on Machine Learning Research (01/2026)
B.2 Proof for Nonincreasing Property
Theorem B.2. (Fact 4.2 in Section 4: Monotonicity of Expectations) Let m(a, B|tanh(axX + []
and n(a, /) == E|tanb(a.X + v)] be the expectations with respect to X Kolla]) Then they satisfy the monotonicity properties:
(monotonicity of m((a, v)): m(a, v) is a nonincreasing function of 2 0 for fixed a 2 0, and a nondecreasing
function of for fixed v 2 0, namely:
m(a, 0o) I m(a, I m(a, v) S m(a, for 0 0
2
0 m(0,v) S m(aa v) S m(a' v) S ml for 0 0sa 0.
(monotonicity of n(a, v)]: n(a, v/ is nonincreasing function of for fixed 2 0, and nondecreasing function of v 2 0 for fixed 2 0, namely:
0 n(,o, v) na v) n(a,v) n0, = tanh(v) for 0 a aa 0,
0 0)a.0) & n(a,v) S n(a,v') S n(a, 00) = for 0 - <vS'',a>0
Proof. By using the identitics hyperbolic functions and expoctations in Subsection A.1, and noting that 1-1²
I-p2p 1-r27 are nonincreasing and nondecreasing respectively in E [0, 1] for r E [0. and rt * 1, we have
m(a,v) S m(d'vv) m(a, v) 2 m(a, n(a,v)_n(a'' v)) n(a,v) 2 n(a,1/)
for 0 < a a
S
for a'
Moreover, can invoke the dominated convergence theorem to exchange the order of taking limit and taking the expectations (see Theorem 1.5.8, page 24 of Durrett (2019)), since I-raz 1 I- S I-p- are bounded in [0, 1] and therefore integrable. Note that E[[X]] #
I-z²
X Ko([=)) in Subsection A.1, we have
x
m( m(oo, v)
lim E[tanh(oxX + x]) = E lim tanh(o + v) | = B[|]]]
000
0-000
n(a, 00) = lim E[tanh(aX + v)] = E lim tanh(aX + v)] = E[[] =
+0000
0+000
Similarly, we have
m(a, oc) = lim E[tanh(aX + +) E[ lim tanh(aX v) = [[ =
7000
n(
lim E[Lanh(aX + +z] = E lim tanh(a + v)] = E[sgn(X] 00000
a
Also, have m(0,v) tanh(v)E[[] = 0, n00, v) = [[(ann(vv)] tanh(v), na, 0) = [[ttnn(axX)) = 0 and
m(a, 0) = E (at)ah(aaX)x < E E = aE Ya 2 0.
Therefore, have completed the proof by combining the above results.
Theorem B.3. (Fact 4.3 in Scction 4: Nonincrcasing and Bounded)
Let a² = | | - |>/// and 3 == tanh(u*) = N(00-1, ((1)) for all / E Z, be the 1-th
iteration of the EM update rules [0, v) and N N v) at the population level, then 3 3000 > 0, a² < 2/T, and 00 and fe are non-increasing.
26

---

Published in Transactions on Machine Learning Research (01/2026)
Proof. Note that X ~ Koll<) is symmetric random variable, we have that m(a, v) m(a, -v) m(a, (n]) x
is even function of y and n(ax v) = -n(a, -v) sgn(v)n(a, (u]) is an odd function of v. By the recurrence relation of EM updates equation 10, we have a²+1 = m(aa, v²), g = n(a",v with 3 tanh(v").
By applying the previous proved monotonicity of m(a, v), n( v/ (Fact 4.2 in Section 4), we have
gt+1 8 (en(v")] (vn)) tanh | 2 0, | n(a' 10 S n0,0| tanh |n'| 1 Therefore, by induction, we have 3..3 .3 2 0 and { is mon-increasing, By the monotonicity of m((a, v),
2
0 f a =m(aa ,²) m(a' |0 v m(a' 0) S a', a'+ 1111) mla', oo) x Therefore, we have a' 2// for all i E z and (a {a') is non-increasing.
7
B.3 Proof for Approximate Dynamic Equations
Theorem B.4. (Proposition 4.4 in Section 4: Approximate Dynamic Equations)
Let a' := |001//o 10* and 8 tanh(v") ((0-),,"") for all Z+ be the t- th iteration of the EM update rules 20, and N (0, at the population level, then the series approximations for EM update rules are
1+ = 1893)) g++1 = 3²(1 - +'aa't''++(0
Proof. By applying the recurrence relation equation 10, namely at m(a', v²), = ni(a'v1) and
invoking the tower/upper bounds for m(a, v) and n(a, v) in Subsection A.3, we show that.
at =a'(1 - ($9]² + ([a9)3
Bt -8811 1- [o-]3 ( o((a)))
181-1197 (899)) = a'0((a913) O((a'1*), and Therefore, a'(a" - a1-1-11111)1
ge+1 B²(1 a +1a + +((a')))
Remark. When a' is sufficiently small, by the proven Lemma of series approximations of m(a, v) and nıa, v)
in Subsection H.1, we have
a+1 m(a", v²) = E[tanh(a'X + vz
= = -1 (1'1) + (1 (1-133))((('1)))
gh+1 n(a',v²) = E[tanh(a'X + = 81 -
+ 3 -
8¹(1 +
Hence, we have these approximations when a² * 0 and 3r + respectively (see Lemnas Appendix C):
1+1
a - at
1+ 1+0((a))),
a = -193 (1 - (1-131))(((aA}))
a¹11 (3022
g1+1_ 3r aa'a + (1 13))0(((0)1 -1 -11-1993) +(((')))
g
In the special case of balanced mixing weights, namely 3² tanh v² = 0, then by using the bounds for a 1+1 = =m(a', = mla', 0) mola') in Subsubsection A.3, for sufficiently small a', we have
3/
a' 3[a s 2+1 < az
1 8[o']
The above upper bound still holds when 3e + 0, since a+1 m(a', v²) = m(a', 11/1 S m(a', .0) mo(a') a' a3-3/oa)3/CC 8[a(]) by using the monotonicity of m(avv) (Fact 4.2 in Section 4).
27

---

Published in Transactions on Machine Learning Research (01/2026)
C Lemmas in Proofs for Results of Population Level Analysis
Lemma C.1. Let a' == |/00 ||M (0,0.1),3* == tanh( = N(00-1, 1,-1,,, vt E Z+ be
the 1-th iteration of the EM update rules
at population level, then
5 0.97 S a'(1 [893) S - 3 3 + 9.53(a -3 - -1892
a +11
a²+1 a' a' S
5 1892. 5
- 3
Proof. By applying equation 10 a+ = m(a', 1²), g = n(a', v"), invoking the lower / /upper bounds for the
expectation of m, n in Subsection A.3, and noting that max 9[a²) [ [398] + 225(a "2)5(a")'(3') [39[3 = 0.03, 05a"g0.100$=11
1200(1- "1
1200(1+ 32 0.100.1
I
0.52972 < 0.53, we obtain the following lower /upper bounds.
(1+16(a')(1-38 (()))))))))
(1+16-01) (1-10)
411
2 1 1- 9-/aa9
[872
2251a"1"1312
2 1 0.03 0.97
a1 [09|2)
3
a1+1
1200(1 + 25 (a9)
< 1 - 9|aa
189}
+ 13'1
18
a²(1 - (89
+ 8(a4]
+ 16(a))) (1- ((
[91?
+ 0.53 "1[8"// = 1 3
1a0-22 + 9.53
5
1+ 1.88-00 0.1
By dropping out the term of [04))(89)] and using a² < 0.1, the upper bound for a²+1 /at is established.
a+1 S (1- (1 (1- 5
+ + 9.53[a < 1 - 5 -la01 0. <
-1-31000
3 gla'12 - 4 118
5
at
By applying the lower bound for a m(a', v4) in Subsection A.3, when a² E (0.0.1).
a++1
at 2 (1- (1-19)3) (1 +| - 2 1 1 1- 2 1
Lemma C.2. Let at = 10011/0 || (0,0.1),
tanh(v') NNO0-1, 1 e
(0, Vil. e 2, be the t-th iteration of EM update rules [0, ()llo,,, (00, at population level, then
-aa' S -a0) [39p)) gr < 0.944 - (373) - - - la9p.
g++1 g0
S
Proof. By applying equation 10 a++1 m(a', 1²), ge+1 - = n v²), invoking the lower /upper bounds for the
expectation of n in Subsection A.3, and noting that 41-1 - 9[33 + [ I+16 2 0 holds by using
300
[811
<
128 2 +6 for at 2 O, we have
428(n'] 2488 +15
ge+1
6 [893)
300
2 1-la9 (1PP111133--1 + 1a91
1+ 8[a'] 9/39/
+ 1307
21
I+ 16
ge+1
S 1 - 6/o (3(13) 0.94[4"'(( -39(2)
B
By applying (1 (1- (1-181?3) < and 0.94(1 - [3 2 2 for 8e E (0, / we obtain the following bounds.
-1a012 < -1a')2(1 1333) < g++1 3r
$ - - (891)) < 1 la'p
gt
2
28

---

Published in Transactions on Machine Learning Research (01/2026)
D Proofs for Results of Population Level Analysis
D.1 Proof for Sublinear Convergence Rate
Theorem D.1. (Proposition 5.3 in Section 5: Sublinear Convergence Rate)
Let a' := 11/o || the EM update rules [|M v) N(0, v) at population level. Suppose that a 00,0.3), then
3 == tanh(r') = _N ,,_ Vt E Σ+ be the t-th iteration of
1
at
Vi E Zzoi
V6l + (8+ + 2 } -
when the initial guess of mixing weights is balanced TO (2 2), namely = then
= tanh v0 || 2 0,
1
VL E Zz0-
6t + 22 + 1) + )2
Proof. By invoking the bound for expectation ma(a) = m 0) = X]xanhaaX) under the density function X ~ Ko([=))/T T in Subsection A.3, the EM update rule a ++1 m(a', 1²) = E[tanh(a'X+ + in equation 10,
and the monotonicity of m(a, v) in Fact 4.2 in Section 4, we have
3/a²}
++ m(a', v²) = =m/",, (v')) s m(a', S a' 1+ 8(a*]
Saa < 0.31
Regarding the upper bound on the right side, we view it as the discretized version of differential inequality da I ddt. By the method of 'variable separation", we conclude the following upper bound. Hence, by
using 0 < a+ S a', we obtain 1 is
1
+ atf and 1 15
a²
a+II
a
T- T=
+1
T
Σ
1
'a"1
+ 1aa9-2 { fat - aa
1=0
1+8
t=0
at
2
1
at
8 la'l
(att } fat aatty
a²
atty
a++T
2
++
T-1
(1a 1a 12
+
(1a
6 1=
1=0
+
3
[a
{ la 0 2
3
8
[19--1]
By substituting 1 + T, namely |a'] + 1 > 6t + |a-| + 16 -1 and solving for a', the upper bound for a' is established.
Let's provide a matching lower bound to justify the sublinear convergence rate for the worst case of a balancod initial guess T (2, 1), namely 8o tanh ~ (1) - (2) 0. By applying Fact 4.3 in Section 4, 11 (tanh | 1' is nonincreasing, therefore, v = 0, At E Z2o given the initial guess is balanced.
Again, by invoking the bounds for expectations in Subscction A.3, and the EM update rulc a++ = =maa,, ,²) E/tanh(a' x + x')x] in equation 10, we obtain the following lower bounds for a' == ||0'1//r E (0, 0.31).
at - 3[ao < mala') = maa, .0) = mía', "²)=='')
= a
Regarding the lower bound on the left- hand side, multiplying by 12x' on both sides and defining A' := 6|a-|² < 6/a < for ease of analysis, and applying the AM-GM inequality A < (A' + /22))/2 then
A
2 [A-2 A & A' 4
29

---

Published in Transactions on Machine Learning Research (01/2026)
Hence, A I [AT and dividing by A on both sides,
1
1
A'
A
A++1
A
(A AL+1)
A' A [49]
A
To obtain the lower bound for At
1 [a
use the upper bound for a' which has been obtained:
[a-)-2 + 16/681111 2 6t + [a-]-2 - + 16(a") also apply the AM-GM inequality [a") + 9 2 6(a and
+ 16|aa))-1 3 + 16 x x3= 57.
11
16 (1a")
a
2 + 24 = (a")
+ 6
2 + 9) 2 6l 57
3
Therefore, we have shown the lower bound for
L Λ7.
1 - A
1
3
3 2
- +
11
Hence, the use of telescoping summations and bounding a summation by an integral Σ In = l1 + 1) gives the following upper bound for
+ dr
r+
?
1 1 A0.
1 1 A
1
11
A
-
A
A
st+ In(1.2t 1) Σ
1 ==
3
T=U
Consequently, we obtain the following lower bound for at by substituting = 6|a²|2, 10 =6[a9/3
1
a'
V 61 + 2212n(11111 21 + 1) + (+)))
By combining the upper/lower bounds for a² = 1001//0 in the worst case of balanced initial guess n¹ =(2 2)
1
Sa aa
6t + 22 (1.2t + 1) (2))²
6et + (8 + 2 8
which justifies the sublinear convergence rate, as t 2 In (1.2t + 1).
Remark. For a finer analysis, we can establish a tighter upper bound for a" ++1 by starting from the series expansion of tanh(a'X) X) and using the fact that _[ = [(2n - 1)!!}² for X Kolla))
a+1 E[tanh(a' X + x' < E[tanh (ax))
I a a'E[X²] - | -
+ [a [a''=[[']]
17
|a']'[[X*|
62
(a [a']E[[x]]
15
315
2835
= a' - 3 + - (17 x 35)[a') + (62 x 315) 1 < 3[a'1//(111 10(a²1²)
where the last line holds for a' E 00.0.13) is sufficiently small, which is tighter than the upper bound a+ <a - 3/12)3/(11 + 8(a'1) (since 8[a'] > 10/at]2 for a' E [0,0.13)). By applying the same method of "variable separation", and noting that (a* - a ++1 1/a* < II(aa//a")) (-1) (since z/(1 + x) I In(1 + x), Vz 2 0), we can establish the following relation for a::
a' 1+1 6T K 31a-13/(1 10(a
1 a
( a
2
1 a
+ 20
+
20
a
By solving the above inequality and introducing Lambert W function (see Section 4.13 Lambert W-Function
of Olver et al. (2010)) and noting In x - In S W(x), Vo 2 e, we obtain the following upper bound for a when a E 0.13.:
a'
10w (Totzao अंंंगर exp(0.6t))
/ 6t + 22) 10 -
+
30

---

Published in Transactions on Machine Learning Research (01/2026)
D.2 Proof for Initialization at Population Level
Theorem D.2. (Fact 5.2 in Section 5: Initialization at Population Level)
Let a' | , and 3 lanh((") and (00 v) at the population level. If we run EM at the population level for at most To 36 iterations, then To < 0.1.
-00--,,0-) for all I E 2+ be the 1-th
iteration of the EM update rules
Proof. By the recurrence relation of EM updates equation 10, we have a mmaaa v.). Futhermore, by applying the monotonicity of m(a, (Fact 4.2 in Section 4), we have
a ++ = m(a', v²) = m(a", ,,01) & mla", 0) mmaaa")
In three iterations of EM updates, by numerical evaluations of mo(-) and noting that mo(oo) = 2, applying the monotonicity of mu(-) (Fact 4.2 in Section 4), we have
π )
a S mol(?? S mo(mo(a*)) S mo (moom(m S mo(mo((ma(<s))) mg
mg
0.305 < 0.31
Note that a+1 S a' and a' is nonincreasing (Fact 4.3 Soction 4), we justify that a² S a < 0.31, V 2 By
applying the sublinear convergence rate guarantee in Proposition 5.3, selecting To 36 and using a < 0.31,
1
To
<.1
V6x (To 3)+ + 18+
2 23 1
Therefore, we have completed the proof.
Remark. the worst case of balanced initial guess n² mo(mo(ma(Do))) 0.305 > 0.3, the matching lower bound in Proposition 5.3, then for any Zzo, S 9,
1) and a + oo, then by applying a
a² 2
2 0.103 > 0.1
6(t - 3) 22 21.2 3) + +1
6x6+ 22.n x + 1) (0.3
Therefore, in the above worst case, a' 0.1, Zzo, 9 shown. By numerical evaluations in the worst. case, we have 20 mo (mo R 0.1 as shown in Fig. 1b. As 9 < 20 < 36, our theoretical
times
conclusions based on the matching lower bound and the upper bound for at Proposition 5.3 are verified.
D.3 Proof for Contraction Factor of Linear Convergence
Theorem D.3. (Proposition 5.4 in Section 5: Contraction Factor for Linear Convergence)
Let a' := ||0|||/a | (0-00~1,"~~~Il1 >/>'////o and Be := tanh(v") = "(0--1,~(11) for all t E 2+ be the t-th iteration of the EM update rules |M, l/ and N(0, at the population level. Then 8o0 == lim g exists and
(i) if 8 0, then 8 0,
(ii) if 00 0, then 0 < 800 3r $ g0,
(ii) if 30 < 0, then 0 8 2 3¹ 2 80.
Suppose that a' E (0, 0.1), then
a++1
4
at 1 5 18002
Proof. Using Fact 4.3, we have shown that g 30 2 and {1 non-increasing, namely | | Z4. By the monotone convergence theorem of sequence Rudin (1976), 8 == lime 8* exists. Hence, if 80 > 0, then 0 < g00 3r < g0-1 S 30 for any VI Z_.. Conversely, if
31

---

Published in Transactions on Machine Learning Research (01/2026)
80 < 0, then 02 2 gt-1 = ................................ 8 0 for any VI E Z... Furthermore, we will show g o 0 when 8 + 0 in the proof of this proposition 5.4, thereby the results in Proposition 5.4 (i) (iii) hold for all t E Σ+.
80 for any Vt E 24. And if 300 =0 then f =.... 3
For brevity, we show that g > 0 when 30 > 0 in the following steps; similarly, we can validate that 8 <0 when 3 < by following the same procedure. If all 3e 2 2 for 1I 2 0, we must have 8
Otherwise, we have 3r < starting from t 2 to for some to. Without loss of generality, we may assumm
to = 0, 3
V 5 a 0.1 and continue our discussion below. We begin with the proven Lemmas in Appendix C, which impplies the following inequalities:
ha ++ -Ina'
a++1 - a²
S --3aa²²
5
4 -
1899
- 189
at
3
5
g++1
Bt
In 1 Be
1.006
-1.006[ay1
B
where the first inequality is from In(1 + +) I x, Vr 2 0, In z) 2 1.006x, Vz E [0, 0.01] and the second inequality is from Lemma C. We first give rough upper bound for [a-]3; E Z, by applying the upper bound of Proposition 5.3 in Subsection D.I, namely I+16a
61+
(8+
20
1 + 16a
16
2.6 11)
[a']2 S
(1 (
61 + {8+ = 82
6(t
6
Based on that rough upper bound, we have the following inequality to establish the lower bound for 8
In In In 8r 2 -1.006[a"1 2
1.006
2.6
6 (t
(t+1)-1
20 -::0222-0000 (++)) Vt E Zz0
9
By taking the telescoping sum of the above inequality and taking the exponential, we have
8e 2 80 exp
(-20
9 20
9
Σ T=0
4-1
(r+2))-
2 80 exp
(-2) (-
20 J T - dr) = exp
cxp (-20 9 In(t (n((++)) 1)) = (t) 1
where the first inequality is from the telescoping sum of the above inequality and the second inequality is from the fact that (T= 2)-1 < f(+ - = In(t + 1).
By the above rough lower bound for st, we can establish the other upper bound for a' via using the proven incquality In a+ anaa < 1.
a' aa exp 1-11p r-1 Σ (T + ( 1)-
s a exp (-2109p 1+ 1(t) T -t = a exp (-8139p (1+1)++-1) -1)
where the first inequality is from the telescoping sum of the above inequality and the second inequality is from the fact that S (T) < r++ -- u 10[(t + 1) -].
By applying the above upper bound for a", telescoping the inequality of In ge, - In > -1.006(a taking the limit of t - do and noting that Ei exp(-16] + 1) ) I f exp(-16] )dt (हहागर.ा and 1.006 ex < 1.006 exp(16 { I 10², we have
10t
> Ja > - 1a 10 (10!)
1
[a
In 8 - In 3D > -1.00
(16 30)(002))00
300
[00200
-00
0=0
Therefore, we have shown that 800 when 8 > By the same procodure, we have g00 < 0 when 130 < 0. Consequently, when 8 o O, the contraction factor for linear convergence of a is bounded by
a+1 $ -1-3107 1072 <1 5
13002
at
32

---

Published in Transactions on Machine Learning Research (01/2026)
where the first incquality is from the above upper bound for (a*+1 - -aa//a and the second inequality is from the fact of | S 1,89 which is shown earlier.
Remark. By applying the upper bound for the contraction factor, we have at I a (1 ( To estimate the upper bound for go0 we start with the following proven inequalities from Appendix C:
In - -Ina' 2 1.006 a+t1 aa
1 (27 +
2 -1.00 (3(a')2 + (399)) 2
(27 +2) + (1))
at
20
-1 - < Betl- - B² In
S 2 1a'l² v 1a112)((++11 t0 exp (-10 18912)
(1)
Br
where bounds for (a'+1 - /a' -3////3 are from lemmas in Appendix C, and the first inequality leads to lower bound for a², aka a' 2 a exp
(- &
20 (27 + 2) + 21{5913) 2 at 1) 20 exp exp ()))..
By applying the above lower bound for a', then for given go / we have
In 800 In 30 - Ilao 1-- (t (0+1)-RB exp (-10
21 [89/tt dt S - /0 (++ e #t - [a91
10
where the first inequality is from the telescoping sum of the above inequality.
D.4 Proof for Convergence Rate at Population Level
Theorem D.4. (Theorem 5.1 Section 5: Convergence Rate at Population Level)
Suppose a 2MLR model is fitted to the overspecified model with no separation 0* o, then for any (0, 21:
(unbalanced) if n² + (2) 2), population EM takes at most T= = O (log)) !) iterations to achieve |00 S c,
(balanced) T 2 2), population EM takes at most T O(E ?) iterations to achieve | Se
Proof. If 0" = 0, then 0'= 0 S e, VI E Zzo; otherwise, by invoking the fact for initialization at population level in Subsection D.2, then To = ||0 1/0 < 0.1 after running population EM for at most To = (1) iterations.
Without loss of generality, we may assume a 11091// (0,0.1) in the following discussions.
Let's prove the cases of (i) T" ()) and (ii) σ0 # (2. }),, separately.
Proof for Unbalanced Case ~0 # ())
Note that |,81| = ||=00 11l1 * 0, then by using the proposition for contraction factor in Subsection D.3, the
limit 8o0 = 100 8e * O, and for a e (0,0.1),0 < a+1 < a'
a+1
4 13002
S 1
5
at
Therefore, by taking T = [[- log log
+ θ (log )), then for at a= 1/0 we have
log(1
$ [3
T S (1 - (3 00.
Proof for Balanced Case n = (2 2)
1
By applying the proposition for sublinear convergence in Subsection D.1, for a E (0,0.1) and L E Zzo
1 61 + (8+1 1/ -
a²
Hence, by taking T [2 + 16e - 1 16 - we have a= 1001/// Se. 0
33

---

Published in Transactions on Machine Learning Research (01/2026)
E Lemmas in Proofs for Results of Finite- Finite-Sample Level Analysis
E.1 Modified Sog-eeoolev Inequality
The following definition and logarithmic Sobolev inequality are on Page 91, Chapter 5 Entropy and Concen- tration, (Ledoux, 2001) by Michel Ledoux.
Definition E.1. Entropy of non-negative measurable function given a probability measure μ defined
En {
du J f log fdv (J fdj) log (J fdn) =f flog 1 san
if f flog(1 + fdd < xc
x
otherwise
Remark. Since f log J f llog(1 + f) + f log f and 0 S f fllo(1 + f), su = 1, then
-1 -1 -15 -1+ / flog(1 + f)dp $ f flog fdu / flog(1 + f)d
If f + f)du < 00, then -1 S S log fdp < oc; note / (2- S f 1( (2- =²4) = ( s
f flog(1 f)
0. / fdp $ 2
1 { {++ / flog(1 + fydu 00
Hence, [f is bounded if f log(1 f)du 00.
Definition E.2 (Equation (5.1) in Ledoux (2001): Logarithmic Sobolev Inequality). A probability measure μ Rd is said to satisfy logarithmic Sobolev inequality if for some constant 0 and all smooth enough functions f on Rd,
Remark. Let f² = exp(t) and v0 : R + IR be a Lipschitz function such that (ı(x)) (x')) s A/2 x'), then the "modified logarithmic Sobolev incquality" bocomes
Ent. (exp(())(())] - cE,,, [[+ (x)) s ex (expx((
Lemma E.3. (Bounds for Bessel Function, see Chapter 10 Bessel Function of Olver et al. (2010))
Let Kp be the modified Bessel function with parameter 0, then for x >
exp((=x) x) Ko(x)
1
exp(=x)
S
2T Vx +1
2T
Vx
Proof. By invoking the monotonicity proporty of K,, namely
(x) I [x)) for 0 S VvvivVa > 0,
in Section 10.37 Inequalities; Monotonicity, and K (4(x) /
expl (x) in Section 10.39 Relation to Other vz
Functions, Chapter Bessel Function of Olver et al. (2010).
Ko(w)
K (x)
exp(-x) Vx
2m
For the lower bound of Kofz) confirmed through numerical validation that
noting that Ka(x) and /
T exp(=x) Va+I
monotonically decreasing, it can be
*
exp( V
1.26 1.54 Ko (1) Ko(x)
for (0, 1). Hence, focus the case of in the following discussion.
34

---

Published in Transactions on Machine Learning Research (01/2026)
By applying (1 - \/2 x 21) + 1 for 1 (0, hence VIFI (1 - )x 3, invoking v
2x JR. exp(-2y), / VJdy Jz_- exp(-zz)) Vidy, and using 1 1-y/4- < 1/ /1 + y/2 for y
Texp(-2) x)
exp(-0)
1 Viu-+ exp(-2) x)
/ (1 (1-4) 5) exp ry) dt
exp( exp(-2(1 + vl)
V 2 V
V2
1
x
2σ
V2 R
4
JR V2 + v)
dy
Namely, noting that SR, exp( exp(-of dy = Ja, exp( cosh t)dt by substituting y cosh t 1, and invoking vu(2+y)
JR. exp(-z cosh cosh fjdt = (o(x) (Equation 10.32.8) in Section 10.32 Integral Representations, Chapter 10 Bessel Function of Olver et al. (2010).
exp( Ko(x)
V +1
Lemma E.4. (Modified Logarithmic Sobolev Inequality) Let eb R R be function such that for Va R, and 0 & À 1/2 < 1; the probability measusre μ is induced by a density function then for any c 2 7,
[=(())
S A|z
du Koll
di
(exp(1) cd2 / /exp(((x)dd..
(exp([)) I
Proof. Step 1. Upper-bound for [exp(())
Note that á flog - t + 1 2 O, and let t + En [exp(())]] = exp(e)ddu.
Then, we apply vé - + expl +b < 2 21 du = Ko(lal) do and Ko(w)
S
exp(=x)
proved in previous Lemma.
25
Finally, we adopt the assumpton 0 I x S 1
[exp(v]] < ex - exp(1) +1] = Eplt& - + exp(- exp(())
12
2 Buly exp(x)] S Ex,12eexp(\(x1))
exp(A\x))]
2
x2 /
x² exp((-1 - \//dd== = 4v2 (1 2)
3 X2
31
V 2x
Step&
Lower-bound for EE [exp(v)]
We apply Ko(#) " 2 V 2n Va+I
exp(-r) in previous Lemma, and use the assumption S A <1
2
exp( + \)r)
[exp((()]]
E2 (epppppp---p (-\/x|>1 2
dr
π
JR+
+I
exp
(-)x))
20
3
dr
erfc
B+ Vx +1
v3
Step 3. Estimate for c
Entz X [exp(1)]
3X2
3/3e
6.9622594 < 7
2c v3
erfe
(v²) X2
2erfc (v22
By choosing c 2 7, the proof is complete.
(xxp)(oxp(+)] = cd² S (op(((()))
[oxp(()) -
35

---

Published in Transactions on Machine Learning Research (01/2026)
We could derive the concentration inequality based on the previous Lemma (modified log-Sobolev inequality). see also section 5.3 modified logarithmic Sobolev inequalities in Ledoux (2001).
Theorem E.5. (Concentration Inequality with Exponential Tail)
Let F: R + R be a function such that [F(x)) & |x| for Vo E I;; the probability measusre μ induced by a density function {0i) Fz)), then for any t and 2 7,
iid de da
Ko[la]) let F3 = F(xi), F
{
t2 :
P
( FF(F 2 nt s exp
PP
min
4
Proof. Step 1. Estimate the Chernoff bound for F for t 2 O, and by the independence of F;
Σ P. E, 2 ml) = P
exp((A P. E,(Fil) 2 exp(nd()
E, [exp(A|>>
F; (FiI))))
<
inf A=0
exp(nit)
log Ep [exp(AF)] - E114 -
= exp
ninf A A=0
Step 2. Upper-bound for ((A) log B, (exp((A)) for 0 << 1 <1
We study the evolution of <(A) by taking the derivative of (()).
[exx(FF) log E (cxp(()FF))
d ((A)
[x([xp(AF]]
Ent [exp(AF))
ax
X2
x²E expl [AF)
Ent, (exp(AF) X=E, (xx)(FF) I for 0 < A 2 < and c 277
By using the previous Lemma,
(F(eN))(AF))
ds ((>) ((2)
d c
<(0)
lim A-0
log E (cxp(AF)
lim x-0
E, (exp(XF)
[..[F]
A
Hence, we show the following upper-bound for C(A),VX (0,
<(>) =<(0) J' C(X))X s [c(
Step 3. Obtain the concentration inequality for F when 2 0
Note that log B (exp(AF))
En[F] - 1 ((A) EE,14
< cd L, and - + 4.4 -2,
E2 -E,111+ +0} log E, (exp(AF))
IP Σ (E [x) 2 nt
exp
inf nd AE(
exp
A(e1 - 01 = exp (ni(es- +) (2:dt) AE +
inf
=exp
1 1ize + { 12
Toskcaa exp { min 1, 12
(1)))
exp
Let F P the above expression, we obtain the upper-bound for the probablity measure
nt s exp {-" min t, 12 c
Σ FF - E,( < -nt)
36

---

Published in Transactions on Machine Learning Research (01/2026)
Combine the above two cases, conclude the following for Vt 2 0 and c <2 7,
P E (P) - Bx(Ai) 2 nt S exxp
{-
{-
n
min t 1.
E.2 Azuma-Hoeffding Inequality and Elementary Inequality of tanh
Lemma E.6. (Azuma-Hoeffding Incquality, Corollary 2.20 page 36 in Wainwright (2019))
Let Fc) be martingale difference sequence for which there are constants {(ux, ba) such that D3 E [ak: bu] almost surely for all A = I.....n. n. Then, for all t 0,
21
P
DE
2
2exp
k= (bx - ax)²
Lemma E.7. (Upper Bound for tanh) For Vt, R, have
ttanh(t + tanh w/ s 1 tanh |p| S
and
1 1 tanh |y|
2/
tanh(t + +v) - tanh S
x |8| S
14 + |p
1 |M]
Proof. The first inequality is proved by applying la + bj < |a| + |6| and lanh |r| < 1.
Let's prove the second inequality by discussing these two cases S and t > 0. Without loss of generality, we assume
in following discussions, since we can always let -v + v, - t for 0.
(i) I 0, then by noting that g(l) min (t) (+++ is concave function of the straight line which connects these two points g(t) (==-(++)) and g(t) le=o must be not greater than g(t) for Vt (1(1+)
s(l) 2 g() la-0 + g(t) Ii=0 - g(t) 1t=-01+) x WE
+
Namely,
1 1+ tanh
tanh(t + gt) min min(tanh(t + v)) +) 2 tanh v +
W -
1
Note that
tanh(t +v) 2 -1 tanh 1 + tanh
Vt < -(1+v)
1+v
By applying tanh(t + +v tanh v 0 and 1 + tanh 2, validate the second inequality for the case of
t < 0.
(ii) t 0, by applying the identity tanh(() = (tanh(t + v) (anhe)/( - tanh(t + v) tanh v) and tanh /. <
f,0 < tanh < tanh(t+ + v)
tanh? tanh(t + v) tanh v S (1-1anni v)
xt Vt
Then, by invoking 1 < tanh v $ we have
1 + tanh v
2t
tanh(t + +D) tanh s
t
Vt
1+v
++ V
37

---

Published in Transactions on Machine Learning Research (01/2026)
E.3 Bounds for Statstics
Lemma E.8. (Operator Norm Bounds for Gaussian Ensemble, see Example 6.2 of Wainwright (2019))
Let [Te J ~ (0, Ia) and d S n, then for the minimal eigenvalue 7min and maximal eigenvalue 7max
üd
[
[
<
1 I
d
Σ
Ymax
n
Amiu
21-t
V
1=1
and the oz-optrao norm
l22
1
d
d
la
2 2
+
+ t
+
1=1
with probability greater than 2exp(-nt**
Lemma E.9. (Upper Bound for Chi-square r.v., see Lemma 1, page 1325 in Laurent & Massart (2000))
Let Z ~ (n), then for 120 0
P 22 2 2 nt 2V2n+2vnt+22 28) S exp(-t)
Lemma E.10. (Upper-Bound for Weighted Sum of Gaussian Vectors)
iid ~ (O 1) and { Let {=
lid ~ (0 then
Σ
2 + 2( + valy log 2vnd nd - 2log 8
2
with probability at least 1 1-6 8, namely, if 2 d
V d
log
log
O
Proof. By using the rotational invariance of Gaussians, we can rewrite the la norm as the geometrical mean of two Chi-square random variables Z (n), Zo ~ (d).
Σ
V 222
By using the concentration incquality for Chi-square distribution (see Lemma 1, page 1325 in Laurent & Massart (2000)), then with at least probability at least 1 6- 6,
2
2 2
21 s ( y
2 x log
2 g. + log
Zz s
Vd+ log
2 g + log
Therefore
VZ,2252 22 |/+ v 2
2 = 22 + 2log x
2 8 2 + 2(Vn= + vay log
Vd++ + / log 8
If n 2 d, we have
(V
Σ
d
log
log
o
n
11
n
38

---

(ns)# Published in Transactions on Machine Learning Research (01/2026)
Lemma E.11. (Upper Bound for Norm of Sum of r.v., Corollary 38 page 55 of (Ahle et al., 2020)) Let 2 C 0 and a 2 1. Let (Xi))e(m) be iid. mean 0 random variables such that | (Cp)*, then | C max {2 vpn, (npp)
li Lemma E.12. (Upper-Bound for Cubic of Exp S.v.JSuppose (Zi ~ exp(-=))le20 then we have
log
b V
3 1 d' log"
7 O
V
i=1
with probability at least 1 - (6 8').
2 p2 and B|z 6, 11 -E|zill 6+ z pd for 2 2, applying Corollary 38 on page 55 of Ahle et al. (2020) in the second step.
Proof. Noting Khintchinc's incquality || lp -(3p+
P
Σ 
2
E|Z
+8
inf (ne) PE
Σ ( - -[(21)
inf (nE)
Σ 2 RT
ps0
i=1
inf (NE) "P max
(vm, (n/p) /mp?}
Vne
D
inf P22
inf p22 p
VP
pr
exp
ne²
1
(ne)$)
2
exp
1
2e
$
e
The last step is achieved by taking p ne²
.
(nc)
for these two above terms respectively, and 2
max (V
2e
22))
Note that inequality =2 V then 1 <2e)) x nn and ne 2 (2en) à therefore _ (n=) $ > _ (2en)) 2 log n, namely /nexp(- (ne))) +) 1 for Vn 2
P
7
E|Z + $ exp
ns²
+
1e)
(lne)t)²
exp
(ne)*
S exp
ns²
+exp
(ns)
n
2c
2c
2c
4c
(vong)
log
log" y1
By letting E ==6 O
then with probability at least - (6 8')
log
3 5 log
2 - +
V1
39

---

Published in Transactions on Machine Learning Research (01/2026)
E.4 Bounds for Sum of Functions with tanh
Lemma E.13. (Upper-Bound for [Lanh(ax + v) tanh v/æ) Suppose (ai) iid Ko((=r)/a a 2 0, then we
have
(" (
log 1 V
log" 8 n
-
[tanh(axx + v) tanh 1/2= =
a
θ
1+ |
==1
with probability at least 1 (ō 8').
Proof. By invoking the upper bound for tanh in proven Lemma in Subsoction E.2,
2a
[[tanh(ax; + v) tanh v/ S
1 | x7
T+pp ) with
If a = 0, then Lemma is valid, let's assume a > 0 and define Z == [tan + v) JanhvJaj
[2,1 S x².
By using the expectation with 2h and Ko(x) in Lemma of Subsection A.1, we obtain Khintchine's inequality
||2 S ||>ح S 22p / (b) 1/p (b)-"/p 2 p² and [E|Z]]| s E S E[=]] = 1, || E[Z,]lpp 2 p² 1 2 p²
for p 2, applying Corollary 38 page 55 of (Ahle et al., 2020) int the second step.
a 24 z E te}
n
n Σ i=1
(nE) FE PE
Σ (Z: - (2-))22))
inf inf (ns) pso
P
Z, E[Z,]
ps0
inf (nE) P max p22
Vpn, (n/p) 1/pp?
VTE
-P
Y2
ne
p
inf p22
+ inf p22
vP
p
y2
ns²
(ne)* $ exp
1- 2 (nE)
exp
2e
The last step is achieved by taking p
n=
(nc)
for these two above terms respectively, and >
max {v2z 20 nn
(20)²)
(vviss
log L log? + n
By letting 8 =
laking the bounds for two sides, then with probability at least - (6 +
n2
- EE
[tanh(ax; + +v) - -tanh w/2;
2a
1
Σ
E
Z
S
+
log
log 2 1 V
37
1+ |pl
1 |M|
1=1
1=1
Lemma E.14. Let {adli D NO (4,2, I N/ 1), {
id NN(O, and a 2 0,
then for n 2 d' v log J, with probability least 6,
tanh(oz;4 + v)zif = o (
log
!
V
and for n 2 dV log 1 v loga gr. with probability at least 1 (6 ( 8')
log 1
a
tanh(ax,a + 2) =
- tanh |a| + 1 |
v
2
40

---

Published in Transactions on Machine Learning Research (01/2026)
Proof. We decompose the sum of vectors into two parts.
a
tanh(acraay u) tanh(v)
taanb + v) tanh(v)
By the previous Lemma of bound for weighted Gaussian vectors in Subsection E.3, we upper-bound the & norm of first term by
tanh |p|-
x - tanh |u|.
V
log
V
log
1=1
with probability at least 1 1 -/22.
d-1
4
Let (5 ,.n) = (F) Lt x2-1) == [[aan((araaa + v) tanh(v)]=:: then
NN Ia-1)
1771
j=1
TTa
d-1
tanh + +D) - tanh (anh(u)]2,,, = 17
117//2
j=1
d 2
TT Tillz
Hence,
(d), and by applying the upper bound for Chi-square r.v.
j=1
0 (vvv tion E.2.
log
with probability 1 - 6/4, and invoking the bound for tanh in proven Lemma in Subsec-
[anh((ocra + v) tanh(v)]as;ā)
1 -17l2 0
Vd
log 1
d
log 1 8
tanh(on,a + v) tanh 0
n
n
x² (n), then by applying the upper bound for Chi-square again, and using 2 log J we have 1==1 x O()) with probability at least - 5/4, and
Note that >"
2 i=
log
ttan + v) - tanh(v)) =0
n
Let Z: (a!( lid
exp( ( 2) 1
20:
then x? s 2Z, and [2;a|| < Z?
2
a
[
< 2 a
z
|
x
-
1=1
By invoking the upper-bound for cubic of Exp r.v. in Lemma of Subsection E.3 and n 2 ddvlog v Vlogg g then 1 - z (1) with probability at least (8/4 + 8') and
Σ
ttan ttanh + +) tanh(v))a,ū,
a
O
d
log
1
P
71
T
Combine the bound for two terms, we conclude that
log
tanh(az,a + v)
S 0
n
Lanh(ax,a)) + 2)
< tanh
|p||
+
a
0
d v
log -/4
1
41

---

Published in Transactions on Machine Learning Research (01/2026)
hold with probability at least 1 and (6 + 8") respectively.
Lemma E.15. Let {a iid Ko((=))/ and 0, then for log 2 with probability at least - 6,
log
tanh(ax; + +2) =
n
and
E Σ
tanh(ax, + +v) = + [el
a
log 71
d
n
Proof. Note that (an, + v) [-1,]] boundod, then by applying the Lemma of Azuma- Hauma-Hoofdding Inequality in Subsection E.2,
(v
log
E
tanh(ax, + +v)
=0
71
n
We can rewite
72 Σ
E tanh(ax, + v/)
E
[tanh(ax; + 1)) tanh v/]
71
By invoking the Upper Bound for tanh in proven Lemma in Subsection E.2, ttan((zz v/ applying Concentration Inequality with Exponential Tail in proven Lemma in Subsection E.1 and n Z log
1+|0] 1zg].
2a
1
log O
Σ
E
[tanh(ax, + v) tanh v)
+ |
n
Lemma E.16. Let {= nd /o((=))/ and 0,
then for n 2 log 3 with probability at least 1 - 8,
n
log $
Σ
E tanh(ax; + v)aa
o
m
and for 2 log | v log" 8 with probability at least 1 - (6 60),
tanh(ax; + v)æ; = tann |//
1 |pl } jo
log 1
E
11
Proof. We decompose the sum of vectors into two parts, and note that E[x,]
1
E tanh (ax; + v)2; = tanh(v) 1
x4 +
[tanh(ax; + v) - tanh(v)]æ;
n
The first term is bounded
with probability at least - 5/2, by invoking Concen- tration Inequality with Exponential Tail in proven Lemma in Subsection E.1 and n Z log :
Em 23
log
1
(vius)
(V
[1088
tanh(v)
Σ
< tanh |p| O
1=1
42

---

Published in Transactions on Machine Learning Research (01/2026)
By [tanh(ax; + v) tanh(v)]2; I 2/2;|, the second term is is bounded with probability at least 1 8/2
[tanh(ox; + +2) tanh(v)) O log 3/2
EB
By invoking the bound for [tanh(ac + v) tanh u/r in proven Lemma in this Subsection E.4 and n 2
log V log 1 3. with probability at least 1 - (6/2 8*)
log
Σ
E [tanh(oa, + +2 tanh
O
1 P
n
Combinc the bound for two terms, we conclude that
log
E
tanh (az; + v)ass
o
1=1
(v
log à
E
lanh(au + 1)ss
Lanh |0| +
0
1 vl
hold with probability at least 1 and (5 + 8') respectively.
43

---

Published in Transactions on Machine Learning Research (01/2026)
F Bounds for Statistical Errors of Finite- Finite-Sample Level Analysis
F.1 Proof for Statistical Error of Mixing Weights
Theorem F.1. (Proposition 6.3 in Section 6: Statistical Error of Mixing Weights)
Let (0, v) and (0, v) be the EM update rules for mixing weights tanh(v) == t (1)-x((2) at the population level and finite-sample level with n samples, and n 2 log J.8 (0. then
1011/0 1 1 |
log 3
(N,(0, - N(O, v) min
0
with probability at least 1 1-6 6.
Proof. Since (0, = t. E. tanh ( + and (O, =- Eowp(elo xxt) tanh (y/na)
+ v)) then let
|101//o, note that v:/o (0, (I,, 0//0)//// /|0| (0, 1), then Normal Product Distribution is
2 = y1 (r,, 0)
Ko([=))
|0
π
see also Page 50, Section 4.4 Bessel Function Distributions, Chapter 12 Continuous Distributions (General) of Johnson et al. (1970) for more information. Hence, rewrite the error as
N) - N(O,V) = - Σ E tanh(aZ: +v)
Σ
12 lid Ko((z))
~
By invoking upper bound for sum of tanh in Subsection E.4, using a = |101//o, n 2 log 3 the proof is complete.
F.2 Proof for Projected Error of Regression Parameters
Theorem F.2. (Projected Error of Regression Parameters)
Let v0, be the EM update rule for regression parameters 0 at population level, M, v) be the easy version of finite-sample EM update rule for 0 with n samples, and if n Z log J. E (0, 1), then with probability at least 1 - 8, the projection on span{0} for the statistical error satisfies
(V 1og (Voost
K
0 (1o1)
Mansy (0, ((0 10=
and if 2 log 1 v log² t, 8' (0, 1), then with probability at least 1 (6 + 8',
K K101 M - acc.n)) tann |p| + ||01/0 log
1 + |u]
71
Proof. Since M (0, = 1 n
Ei_ tanh (mitzn0) +D) year, (0, = Bamp(s x*) tanh (v(z.0)
+ +v) yz,
o²
then let |1011/o, note that v:/a N(O, (r, 0)/ 1|01 ~ NN0, 1), then Normal Product Distribution is
y x Z =
(x,, 0)
Ko((2|)
110
44

---

Published in Transactions on Machine Learning Research (01/2026)
see also Page 50, Section 4.4 Bessel Function Distributions, Chapter 12 Continuous Distributions (General) of for more information. Hence, we can rewrite the projected statistical error as
|00| |
Mn () (M(,)))((()))))
E lanh a (2 id Ko(I=I)
11
Apply the upper bound for sum of tanh(aZ, + Z in Subsection E.2, the proof is complete.
F.3 Proof for Statistical Error of Regression Parameters for Easy EM
Theorem F.3. (Statistical Error of Regression Parameters for Easy E.M)
Let (0, v) be the EM update rule for regression parameters 0 at population level, M (0, be the easy version of fimite-sample EM update rule for I with samples, and if 2 d V log 3. (0, 1), then with probability at least 1 6,
dv log (
Vdvlost
MM (0.v) - M(0, v01/0 11l00 0
and if 2 V Vog J V log J. 8' E (0, 1), then with probability least - (6 8))
1011/0 }
dvlogd log
v
| (0,v) - (00, = tanh |e| + 1+|ul |u|
Proof. Since M (0, = 1
n Ei= tanh 1iizg +w) yea,, (0, = Exup(s .r) tanh /2 + yz, 2,0 Pj Zi into two parts in two subspaces span and span {
then let : |101//, and decomposc where 74 ~ (0, 1), 7 N(O, Ta-1), and the orthogonal projection matrix Ps satisfies span (P+t) = span (0) The projection matrix has the following properties: Po O, (P Ps (P
(M M((,u)) = Kio Measy (0, - M(O,)) /0
+ P (M ((00N)))/
|0l
The l2 norm of the first term (projected statistical error) is bounded Proposition of of the projected statistical error, Let's focus on the second term, and use the notation == ||0|//, y/o = Z N(00 1), then
( 1 Σ 7
Pg (M (0, v) M(B.u))/o Pg
(2,
where (Z = N(O, 1), ~ (00, are independent of cach other.
By applying | 2 and the upper bound for sum of tanh(a + v) in proven Lemma in Subsection E.4, we complete the proof.
45

---

Published in Transactions on Machine Learning Research (01/2026)
F.4 Proof for Statistical Error of Regression Parameters
Theorem F.4. (Proposition 6.4 Section Stalistical Error Regression Parameters)
Let (0, v) and M,, (0, v) be the EM update rules for regression parameters 0 at the population level and finite-sample level with samples, and if n Z d v log 2 E (0, 1), then with probability at least 6,
d V log 8 (
[0, 1100 =0
n
and if n 2 d log v log" 3.0' 8' E (0, 1), then with probability at least 1 - (6 + 8))
d V log 1
[,, M(0, 111// {tanh (o| 1001/00
n
Proof. By using the connection between Mn and M and decomposing the error into two terms,
2i PAT
(Ma(0, (0,00))-M(00,))/ M(O,u))/o
(M (0, -0(0,))
n
E PATy
Σ RJJ -Ia) M(O.v)/o
n1
By using Operator norm bounds for the standard Gaussian ensemble in Lemma of Subsection E.3, and n 2 d V log !
=0(1
(1
a Ei=
Σ
d log 1 n
0(1)
Ta =0
By invoking the proven upper bound of Statistical Error of Regression Paramcters for Easy EM, and using the facts that [0, < ||||| is nonincreasing and bounded v)ll// = O(1) in iubsection B.2, the bounds in this proposition are established.
46

---

Published in Transactions on Machine Learning Research (01/2026)
G Proofs for Results of Finite-Sample Level Analysis
G.1 Proof for Initialization at Snite-Sample Level
Theorem G.1. (Fact 6.2 in Section 6: Initialization at Finite-Sample Level)
Let a' := | II (0" (0-,,," 1/// and 8 := tanh(v") = N, (0 "0--), for all Σ+ be the t-th itcration of the EM update rules (M, 2/)l/a and (0, at the finite-sample level. If we run EM at the finite-sample level for at most To (1) iterations with n = St (d v log })) samples, then a < 0.1 with probability at least 1 - 6.
Proof. For brevity, write a' = |M for the EM update rule at population level. By invoking the bound for the statistical error of regression parameters in Subsection F.4, and selecting n 2 (2000C)? [d v log !] for some constant. C
d log a
1 x 10
la' 35-aa"
a²l S
2
If <.11, then it satisfies the condition; otherwise, by invoking the population EM update rule a'+1_ mla', v²) = E[[tan(aa'X + xy in equation 10, and the monotonicity of mn(a v) in Fact 4.2 of Section 4,
a+ S ah + 10 - at+| 1===m(a''' v²) + 2 x 10-3 S mlaa ,0) + 10-3 =mo(a") + 2 10-3
Applying the monotonicity of m(a, v) in Fact 4.2 of Section 4, which is also applicable to mo(a) = m(a, 0)
a² s mo(a²)
1
x 10-3 S mo((c) + x 10 2 + 2
1 2
-
1
10 0.64
2
1
a² s mo((a)) ) +
x 10
- mo (0.64) + 2
x 10 < 0.4
2
1
a S mp(a?) + 2
x 10
3 S mo (0.4) + 10 < 0.31
Furthermore, by applying the upper bound for expectation mo(a) = m(a 0) = E[tanh(axXXX] under the density function X Ko([=l)/T in Subsection A.3 for 1 1
1 x 10 < 1+ 8(a + x 10-3
3/0-/
1
1+l S mola') +
2
By using a' 2 0.1, then p¹ = a²
1
2
and
20
20
173
3
1+1 < e
x
10
3
< rº_
1r < <r² - -1993
3
20
2
2
Hence, by using 0 < ,t1 S rt, we obtain <
FIFT
+
FTF
To pt ++
To
(
pd
2(Tb 3) By selecting To 196 (1) and using
[r] 3
fo
n(4 = To -1
1
r(+I
3=3
t=3
3
: 3
20
0.31
20
we
have
1
1
1
1
a
Tb +
0.1
20
/ 2( - 3)
13
2
20
20
20
By substituting 6/To - 6 in the above expressions, then To < 0.1 with probability at least 1 1-6 8.
47

---

Published in Transactions on Machine Learning Research (01/2026)
G.2 Proof for Convergence Rate at Finite- Sanite-Sample Level
Theorem G.2. (Theorem in Section Convergence Rate at Finite-Sample Level for Fixed Mixing Weights) Suppose 2MLR model is fitted the overspecified model with no separation 0" Ö, given mixing weights x' TO and ? (d V log à V log 3.) samples:
(sufficiently unbalanced) if ||70 1
ddvlog i n
finite-sample EM takes
most T
(1 2111 log avlog a iterations to achieve 110-1/00= - o (I 1 dv i $ )
(1
(sufficiently balanced) if ||
2111 2 dvlog 1
finite-sample EM takes at most T T=O O
n dvlog
iterations to achieve | 11/0
(1
[avlo with probability at least 1 T(á + 0').
Proof. By invoking the fact for initialization at finite-sample level in Subsection G.1, then a = || 11/o < 0.1 after running population EM for most. To = (11) iterations. Without loss of generality, we may assume a |001//o 0.1) in the following discussions.
For brevity, write the output of the EM update rule for regression parameters at Population level a'+1 [|M 1')l//a ||M I)/,,,, and output of the EM update rules for regression parameters at Finite-smaple level as a++1 = ||0 = ||,, ///o///==> [0 ,,")
Without the loss of generality, we assume 3e = x1 - (2) 2 0, then by invoking the inequality Appendix for a' s 0.1
a+1
S
3 - 9.53(a
a (3)22)
and the upper bound for statistical error in Subsection F.4, namely la - a4t1| S c2(B + +atly dving & for some univeral constant when n 2 v log 3 v log" 3r. we have
a+ s la a a
$ a'(1 - 2((1-19133 11 (1-
5 Ja'1 +9.53(a
d AVlogg 1
2 +a') 28088+a)))
3
n
d v log
d v log + g
5 (3 [13)]2)
a¹ 1- 1311 22
9953 13)3
n
n
3
with the probability least + 8').
48

---

Published in Transactions on Machine Learning Research (01/2026)
Proof for part a) (sufficiently unbalanced) ||T00 2112 2
dvlog
Consider the following two cases.
(i) if 8 = |,80 = | 2 2 2c
ddvlog #
13 > 0.4, by invoking - -(1-1393) -
< 131 S
d log
+ +2 d log
++ 1 a² 1 + 2v
+ 3
saa9
n
By selecting 2 (5c)4 d V log b11, then 1 - 0.4 c² / /dvlog t + 31aa1
< 0.9 for at s 0.1, therefore
d Volog
log d 2 0.9
d log 8
- 10c²
a' 10c² -102
n
n
Furthermore, by letting n 2 (10c)* [dv log $], then 10c²
v dvlloo :
S 0.1 and a S..,, hence
a" S 10c² dV Vog
log
V logg 1
0.9
a 10c2
S 10c2
+0.1 x 0.9
n
log avlug x
2 log e- log 10
1+ = 0 (log dvlog 1
Let's choose T
then
log a
A ( d log !
d log
d log H
d log
a" S 10o2
6²
11o21
n
n
1
(ii) 1881 = 1.80 = ||
1/11 2 2c
dvlog 1
184 S 0.4, by invoking -(1 13913) 9.53[
0.1, |89| S 0.4
1+1
S a' 1
4
3 (1892)
+ =
d dVlog 1
0.1(a"1
n
Hence,
r+1
4 c
d dV
(1 $
(18912)
c
V log
3 g0 V
3 30
Furthermore, by letting n 2 (30))
[d log 2] then
4 ?
dvlog
dvlog $
1/2
S 0.1
3 3o
2
d dV
+ +0.1 (1 -1-2 130 T
TT <
30
$/2 log aving イ
- log go +log zc
Lot's choose T= -=1
[
1+ θ (139--108 aviog
n
: for 1,30| 00.4, hore we use that fact
log(1 [20
log(1 - [[0012) (((39)2) for small 30 then
c²
d' log
(d log 1 2 c²
2c
d log
a=
3 g0 V
f0
n g0
To sum up, by combining case (i) and case (ii), we show that with Ω (d log | v log" f.) and
|0| ||-00 Ill 2 2c dvlog aa" 11001//0 s 0.1, if we run finite-sample EM for most T o (189) aviog : itcrations, then a ||0 11 o o dvlog : with probability least T(ō 8').
n
g0
49

---

Published in Transactions on Machine Learning Research (01/2026)
Proof for part b) (sufficiently balanced) ||=00 - x [dvlog $ 1
If 189| = 189 = || 111
S
2c
dvlog
2 (10c)* [dv log t]] then 3e S 5, + 4(1-18935 let
3 -.5.3
d V log
Ja'12
- (1999) + + d Voog
a S aa (
(1 (1-
4
then the goal a² =0 (( {1 i)
If a $ 2c
dvlog
is achieved; otherwise, we have a 2c
dvlog
d v log 8
a1 < (1-13313) (1-1111111))) + 2 )
n
(i) if a² >
2²²
dvlog i
note that a'(1 (11-(0 (a')3) 2 a' for a' S < 2
v2 2
then
a't1 v a' (1 - [a'1²)
(ii) if at <
20² 30
dvlog 1 then by invoking 1 1812 < 1 and at > 2c
dvlog 1
we have
2e d log 2/ S a (a933) 2
[d vdVlog' 17
s (1 (1- 2 (1a
3
at+l S a - (a9)))
at n
To sum up, by combining case (i) and case (ii), the following inequality holds for a² > 2c dvvlog h
11 11-
3 glan13
a ++ S a'
2
Hence, by using 0 < a++1 S aa, we obtain 1 15
a²
a'
and
a==1
a41
4
1
a² + a a+1
T = Σ
S
a 1++1 111 (a' a1)1
1=
0=
2
((a (1)22-2
1a
[a-))-2 (29-22
Namely,
1
a" <
5
/ + [a
T
([ ([aiie 11) then
Let's choose T=
1+ =
66 dvlog
V log 1
a" <
< 2c
3T
Therefore, we show that with = 2 (d log & v log )) and |:30| -|=0-
+ll, -
dvlog 1 2c
n
|100|1/0 I 0.1, if we run finito-sample EM for most T 0 (1 (Lavioes 1
1 iterations, then aT = =1100||/0
( [ + $J²) with probability at least - T66+ + 8').
50

---

Published in Transactions on Machine Learning Research (01/2026)
H Extension to Finite Low SNR Regime
H.1 Series Expansions for Expectations
In this section, we provide series expansions for several expectations involving the hyperbolic tangent function. These expansions crucial for analyzing the behavior of EM updates in the low SNR regime.
Lemma H.1 (Derivative Polynomials for tanh). Let (t) az (an for any E Zza and l == Lanh(Z),
d
then
Po(t) tanh(2) -t, (1) (1- Pn(1),
and (v,()= E Z[] are polynomials in for any n E Z2o, and we have:
(e)(P.(()) - = +
max
[P(()] S n!.
1E x
d" Proof. Let Pt(t) d2n tZnh(Z) for any n E Zzo and :: tanh ()), then by the chain rule:
dt d
(t( = t2) =t Z(t), Pu+i(t)= = dz dt
Pr((t) p,(t)= = (1- (t)..
dt
Thus, by the induction, we have Pt(()= E|| are polynomials in for any n E Zzo, and have:
deg( (eg(Po(1))= 1, deg( (1)) = 2 + (leg((aa(1) -1] = deg( Pn (z) = = +
By Bernstein's is inequality (see section 7, page 91 of Cheney (1966) and Shadrin (2004)), we have max4e[-1,]] V11 - (2 p())(t I deg(p(t)) max (p(t) for any polynomial p(t):
d
max (u++i(t) & max 4E[-1,1]
V1 ta Pa(t) dt
S deg(( max |P [t) (n + max PP((t)]- 66|-1,1
161-1,11
(E|-1.1]
Therefore, by the above recurrence relation, have:
(P((O) (n!) max rE[-1.1]
max
[Po(1]) = (n!) max
|1| = n!
rE[-1.1]
rE[-1,1]
Lemma H.2 (Reexpressions Expectations). Let ~ fx(x)= = Ko(l=)) be a random variable with probability
density involving the Bessel function Ko, and / tanh(v) Then for any Zzo: If 10se < 1/2, then:
E[tanh(ax + 2)
3E| 2* - 3(1 101--39)B B [tanh
+(1 ((a)),
Ettanb(aX+ +1)x2x+1
(1 - 8 (t(an
+(1 B (ax) (xx)x
+(1 - (3)))
10 < 1/4, then:
E[tanh? + 2
= 3 2m + (1 (00-33)(( (1 3,32) [tanh (aanh2(xX) (
+(1 - 1))3)((a+))
Eltanh?(a2) + 2
= 2(1 - (tans
+2(1 88) (111+ ) (Ethh X
+(1 33)3²0(a²)
51

---

Published in Transactions on Machine Learning Research (01/2026)
Proof. We have the following facts for tanh(aX + v) and 3 tanh(z):
tanh"(ax)
tanh(aX + +1) taaht-nnaaaa. + +v)
2 - 23(1 -8²)
1- 32 (anli((X)
= 23 - (²) (ax)
tanh (ax)
-23(1 - 8²) 8² 1- 32 tanh (ax)
tanh(aX)
tanh(ax + +v) tanh(-aX + = 2(1 21-B3) 3) 1- 3 tanh"(oX)
2(1 - B²) (aan((a
+2(1 8) B² (aX)"(aX)
lanh
+2(1 88) 8t 1 3 tanl (ax)²
tanh?(aX + +2) + tanh?(-aX (-aX++))
= 28 + - 8). (1 - (1-3,2) tanh (aX)
+2(1 - 37) 1 - 3,32) - 8 (ax))
tanh (ax)
+(1 + 8²)
[1 - f2- tanh taanh (aX))
48(1 82) (1- tanh
tanli(ax +2) tanh"(-aX +2)
[1- -1-3atmn taanh((a
48(1 - 8²) Lanh(ax))
+43(1 8²) (-1 + 2,32) (a
+48(1 8²) ( )2 8² tanh (aX)) (axh)
tanh 3 (aX)
32 [] 32 tanh? (aX))²
Since X ~ fx(x) Ko(w)) is symmetric random variable, have:
- - f(-X))
By substituting f(X) with tanh(o + taan(axX + x) tanh? + v) tax + x2*2+, n Zoo, we only have to consider the upper bounds for the absolute values of the remainder terms in the above equalities.
For the remainder terms of E[tanh(oX + 2*) and E[tanh(ax + v) X2++1, suppose that for fixed on and 0 < a < on < 1/2, we have:
tanh"
E
2
S
& (B X)X 2)x2++2)/20 O(a*).
32 tanh" (ax)
tanh" lanh"(a (ax)
2n++
< a E (aX) $ (a 1 = O(at).
f2 tanh" (a:X)
Note that the coefficients of the remainder for (aanh??axx*+a0 and (axanh"(axX+1)) 11 are bounded
by:
[(1 (1-333 (1-338)(2--) 32 tanh? + (1+ < 3,
[(-1 ((11233))2 3² tanh (aXn?(())))))))))))))))))))))))) 8 < 2.
52

---

Published in Transactions on Machine Learning Research (01/2026)
Suppose that for fixed do and S do 1/4, we have:
lanh (ax)
E
X2n
s R [iinh" x2m] I (ox =(aa),
1 32 tanh (ax)] tax)a
tanh (anh"(a.) (aX)
E
2
I aE (a|sinn((aXX))) 2m+ x f a (ax x = O(a").
[ B2 tanh (ax))
These remainder terms are bounded by O(a²) and O(a²) respectively, we have proved the lemma.
Lemma H.3 (Series Expansions for Expectations of tanh). Let X ~ fx(x) Ko(lul) be random variable with probability density involving the Bessel function Ko, and B = tanh(v). Then for 0 s a 1/2:
E[tanh(ax + x)
= - - 8²) + (1 -1- (3))0(aaa)))
E[tanh(axX + =)X]
a(L aLL- (1- 332) + -1 (2)(3))(a))
E[tanh(aX + v)]
=8- 03-02p(1 -8) + (1-
Proof. We start by defining these expectations w.r.t the distribution with a density fx = Ko([=))
l(a, v) = [atann((xX + =))x3, m(a, v) = E[tanh(ax + x)], ra(a, v) = Eat + 1)].
By Lemma H.1 and chain rule, and let Z = aX + u, tanh (Z) tanh(o v), then:
8m 0a
[tanh" (aX + vi] =
8"
tanh2(z)
x" IPx
| S n!|x).
azn
Since E|X|" 00, Vn E Zzo, can invoke the dominated convergence theorem to exchange the order of taking limit and taking the expectations (see Theorem 1.5.8, page 24 of Durrett (2019)):
v'l(a,v) v) [[]n(tt)x**) )mm(a,v) E[P,(t)x**1],, Dan
d"n(a,v) (t)x())XX). da
Da
By using the fact that (t) l==0= (B) with B == tanh(v), we have:
("I(a,v) da
m(m
( v)
(8)
(B)
dan
a=0
o=0
a=
Since v(a,v) and n(a, v) have infinitely many derivatives, can use the Taylor expansion at (sce 5.15 Theorem, pages 110-111 of Rudin (1976)) to approximate 1(x, v), m((x v), v)o,
3 (a,v) = Σ
E[Pa(() la=a' X a
n+ P.(3)E[X***
Pa(3)
n! + +O(a))
n!
n=0
m=D
m(a,v) = Σ (3)))
a n!
+ B[Ps(t)
la=a" X
5
Pa ( + +(03)
5!
n=0
n=0
3
a + E(Pa(t) 10 X4
PA(EE a 0=0
n((av)) = Σ
Σ
+0(a),
n!
n!
n=0
where a', a" " are some values between and a, and coefficients remainders are bounded by:
[t)) lama' X4+21/4!
E[x 411/4 = E[X* (ō!!)² = 225.
(t)s(t) laza"' X5521/51
|[x 51/5! -| (5!!)² 225.
[t) la=a" X-1/41
s
|||*1|
41/41 -[ (3!1)² 9.
By the recurrence relation Pt+ (1 - Pt) Po(t) = in Lemma H.1, we have
(3) 88, P2(9) (1 (1). (-28), P3(8) = -1- - 3,3²), Pa(9) (1- (1- -19-))8883 -388).
53

---

Published in Transactions on Machine Learning Research (01/2026)
Note that [[X2*] [[2k - 1)1l|, -[ for any k Z+, then:
9 I(a,v) Po(3) 3 P2(3)a²+ 3 3a² 3²) + O(a")
3
33) - 3a (1- - -1) m(a.v) = P1(8)a+ 2 (0(())a++((a)) a a
1
a(a,v) = + P2(8))²+ =
- a² - /²) + O(at)
2
By invoking Lemma H.2 for 0 S a < 1/2 and the fact that E|x²M] = [(2k - 1)!!7 for any k E 2+
([Pa(t) la X a
( (ax) [xx)))x) + B(1
([P la=a" X
5! (1
- (ax))/3))x
+(1 - +(1-89)88 / [[[[thh 3 (aX) (ax) (1-
(t) l= X
B(1 - 3 (tanh? - (ax)3) + +(1 - (()))
4!
=
By 1- e 3 S tanh(()) St- - 1
2t
12
2t
v tann?(()
S 12, 13
tanh (1)$$ 13, 14 2 0, have:
15
3
(1) la=or X a
$ (1 881
0²
2
F 1+2
+ + =(1 11)00(((²))
3
(t) la=a" X a
S BP) ( -a
2
B[x
8 1 1li + (910(a91)
5!
15
= -1-33 -(1-3)0(a)) (aa))
x1 at
+ +8810(())) (,xx,211x' (1 (1-88)1 (1--8))))((a)))
[(P((t) la=a""
<1 331181
Lemma H.4 (Series Expansions for Expectations of tanh Squared). Let X ~ fx (z) variable with probability density involving the Bessel function Ko, and B = tanh(v). Then for 0 S a 1/4:
Ka(=e) be random #
E/tanh? + x)x² = (+) (1-
Iitaan?((aX) + x)X] = 2a.(11 - 82) - 12a -200
3,8 - (1=)3)80(a").
Proof. We start by defining these expectations w.r.t the distribution with density fx fx) = Ko(l=)),
m(a, v) = E[tanh(axX + =])], n(a, v) = E[tanh(axX + +)].
As shown in the proof of Lemma H.3, we can invoke the dominated convergence theorem to exchange the order of taking limit and taking the expectations (sce Theorem 1.5.8, page 24 of Durrett (2019)):
8m
8"
m( v) E[Px(()X**1,,
Dan n(a v) B[Pa((X*).
nam
When n = 1, by Pt(t)= = 1 1 12 from Lemma H.1 and [[X*] 1, [| = 0, we have:
Blaanh"(a + x = [E(1 PI(1)) = = -(P:)))) Ōm((a v)
aa
Ejtanh + + = -X = on(a,v)
da
54

---

Published in Transactions on Machine Learning Research (01/2026)
Note that ] [(2k - 1)!!? B[ 0 for any k Z4, and since m(a, v) and n(a, v) have infinitely many derivatives, we can use the Taylor expansion at or 0 (see 5.15 Theorem, pages 110-111 of Rudin (1976)) to approximate @ 8n
mm(, v) and 8 än
n(a,
@m(a,y) da
E 1
a E()((t) la=a' X x a²
P((3)+ 2 (3())++))))))))
(B) (n 1)! E E[X"|
4!
n=1
@n(a.v)
(P)((()) l==a" X P2( + 3 +
a
Σ
(B)
da
1)!
5!
where a', a" are some values between 0 and a, and the coefficients of remainders are bounded by:
[[Ps(t) la=o' -x5+ 1/41 I [ la=a" -/1/
B[x*] (Xx4)!5/4! = 5 (5!!)?
B[xa] 661/5! 6 (6!!)².
By the recurrence relation Pa+ (1) = (1 - -1 (1) with Pa(l) = from Lemma H.l, we have
(1 =1 1- P2(3) - (1 (1- (-23), (B) = (1-
- 3²) 2 + 3,3), Pa(3) = (1 - (2) 88((2 - 3,32).
Hence, by substicuting the values of Pa (3), we have:
E[tanh (axX + x)x²] = 8 + (1 O((²))
E[tanh (a. + + = 2a,3(1 - (8) - 12a 120 (2) - (382) + 0(a²).
By invoking Lemma H.2 for 0 S a 1/4 and the fact that B[X2*] [[2k 1)!!7² for any k E E+
-E(P((() lama' X5+11 a
(1 (1-18 (1 383 (((anni((a)) (ax))) + (1 -3
4!
-B[Po(t) la=a" X
3TE (tanh 3 (aX ((a
= 2(1 -
- - /3)xx]
5!
+2(1 - 8²) (-1 2,3²)
)
(1)33))00000
By e S stanh()= St 5/
1
+
21
1
15
t²
2r
3
S tanh? (t) s , t - tanh (t) S t², Vt 2 0, we have:
E (t) Ja=a' x5+1 a=1
S (1 - pp
( 2 2 E
+ 3310(a0))) = -1 (())))))))
41
3
[(P((() Ia=a" X0 5
(10) 2 B[x
< - 3
+ 1000 2- 2| +|x0+))++810000)
5!
15
= -1- - (()))
Lemma H.5 (Expectations w.r.t Gaussian Distribution). Let X ~ fx( = Ka[l=ll be a random variable
with probability density involving the Bessel function Ko, and Z1 Zg i.d. N(O. 1). Then:
B[tanh(ax + x
E[tanh(o.]]22 + +) + (tanhh (a + v))
[ttan((xX+ + +
= +(an)((22/2++)))7))}} = E|ttanh Eltaab'(a27,2 + v/ E'tanh(ax +v] = Ettanh(aZZ +v]],
-aiBttanh r) Eltanh' Eltanh'(aZZ23 + 1)) Zz),
where tanh'(.) is the derivative of tanh(-).
Proof. For a = 0, We can justify the above identities by | 1, E[Z Z[] 0, therefore, we only need to prove the identities for + O. By applying Stein's 's lemma (see Lemma 2.1 of Ross (2011))
55

---

Published in Transactions on Machine Learning Research (01/2026)
with respect to Z and noting the fact that : 2,22 ~ fx(x)= = Ko(a)) for any Z1, Z2 1.d. N(O,,)) 1) (see
page 50, section 4.4 of chapter 12 in Johnson al. (1970)); we have:
In cosh(a2222 2)
2z
+1) x Zi).
a
0Z1
tanh 22
Citanh'(aZz1 +
E
E v) Z1).
001
Ejaanh(aX +v)X],
E[tanh (02)22+))02;33) = taanhaaZ + +v)
Lanh + v)23
07.
E[tanh(ax +2)x² E|Innoohíie + v)
By combining the above equations, the first two identities are proved. For the last two identities, we note that [[X]= 0, tanh'(-) tanh?(), then:
E[[ann'' (o 22 + +1)0
-aBBtaanh (aX v) E[tanh(ax + v)].
E[[anh +v]
56

---

Published in Transactions on Machine Learning Research (01/2026)
H.2 Approximations of EM Update Rules in Finite Low SNR Regime
Theorem H.6 (Approximations of EM Update Rules in Finite Low SNR Regime). In the finite low SNR regime where 1) = 1/6 x 1, the EM update rules are:
M(O.v)/o é B[tanh((x + v]x] + n pEjtanh((XX +) + E n VI x² (Eltanh(ax 2)] (elttannn((a + +)) + O(Paa)
N(0.v) E[tanh(axX v)] + n (tanh(ax +) 0(1²a²)
where X (x)x)= Ko(l=)) is random variable with probability densily involving the Bessel function (0.0") is the cosine of angle between and 0*, Ei - 0/||0|| and Ko, 8 = tanh y* = (1) - x2), p शলाा
82 8¹ 19'
form an orthonormal basis, and |001/a, 3 tanh =x(1)= (2). 1il
Proof. We start by viewing the response variable y + Ae as pure noise NN with some small perturbation Ae := (-1)==1(0*, æ), where x (O, Ia). To simplify our analysis, introduce several notations. First, let p = (0.0")
|||||-10-||| denote the cosine of angle between & and 0" Next, we define pair of 0--(0".E,)), orthonormal vectors: E = 0/||0|| and E2 == (0=-(0"E))E:l) For the noise terms, we introduce three independent
standard Gaussians: Z1 =/a NN 1) and Zg == (I, (z, 0] NO 1), Z3 (z, ε②) ~ ~N 1). Finally, for the low SNR regime where 1 == 10 ll// S 1, we define == |0]]/a and B == tanh x (2).
Then, we can express AZ1 == A as:
AZ Ae/o
2 (0 (-)= + V1 - ~ N(0.
mpZ2
Then, can define G the following functions:
F(Z) == (a u)2, G(Z) tanh(a v).
Consequently, we can express the EM update rules M(0, (00,v),N(0) (N, v)) at population level as:
y(x,0)
M(H.v)/o = E tanh
+v
y 10= E[F + 2Z)
σ²
y(x, 0)
σ² + )
N(O,v) = E tanh
= =E(G(Z + +Z)]]
By introducing the derivative of tanh in Lemma H.1 and invoking Taylor's theorem with remainder (sce 5.15 Theorem, pages 110-111 of Rudin (1976)), we have:
F(Z + AZ) = F(Z)+ + F'())ZZZZAZZ
F" (Z F ((+)))))))))
2 G(Z1 +Zz) G(Z)) (ZZ)))(ZZZZZ+ (Z ((ZZ)
where E (0,0)) 1), remainders bounded by (use max [P((1) max [P(()) s 1):
(AZI)) + 2(02)))(G((++ +EAZ))) [Z + +(AZI) = + -2 Zz),
S 2a²23(1Z])
(o + +(AZ)) 1(aZ)) (AZ))) S 2
57

---

Published in Transactions on Machine Learning Research (01/2026)
and by the orthogonality of é1 E2 and |Z1 47 | 27 + [Z,13):
( FM 22222 & ) 2
E|= (Z AZZ
E 2
2n/Bi(a² +1
2 (12) + +
8n/a(1+ 5 -=-aa
x
{ (Z1 +2 - 85 E
S 1 1 +(22)()))))
27 12a1
16 pa(1 )
5
2 GHh [21 < <4
< -
= 0n"aa= 0
Note E| = 0, [| = 1 and Z1, 22, 23 are independent and [[[-1)=+]|= 3 = tanh v² then:
M(0,u)/o 1 + +01aaa]
+F (0))a))
Ee [n8*v/ /108/1/1P))((())0+0))))
(0,v)) B[G(Z)) + + (2))))
Let X = 2122 ~ fx(x) = Ko(l=|) by invoking Lemma H.5 for expectations w.r.t Gaussians, then:
B[F(2)) =
= E[tanh(aX + x]],
(2))( =
E[tanhi(a2Z 22 + v)) 23 = B[tanh(aX + x)x,, E|||+nh(t//// 22 (at v) Z2]
([1)
B[G(Z)) = -ann (aX + +)X], (Z))2 = E[tanh' (aZ1 E[tanh'(aZ1Z: +/
-
+ E|tan(axxx + +v]],
= = Ettann(ax + +)
Substituting the above results into the EM update rules, we have:
M(O.v)/o á [[ttnn((aX+ + + n1* p/janaaan(aXXX +)xx
tg 11 1 x² (E(tanh(a w)] aiB(tan (o + D)X]) + 0
((.v)) E[tanh(axX v)] + n pE|tanh(a + + 0
Therefore, we have established exact expressions of the EM update rules M M(0, v) and N(O, v) for the regression parameters and the mixing weight imbalance tanh = T(1) (2) in the low SNR regime where 17 |001|// $ 1. These expressions involve expectations with respect to the random variable X ~ fx(x)= = Ko(lz)) where Ky is the modified Bessel function of the second kind.
Remark. When |p| = (AZ)))o= = (-1)++1 is independent of Zg, the remainder satisfies:
1 Fr (Z 2Z2))
E
E
(" + AZ))
E 0.
2
2
10=1
|p|=1
58

---

Published in Transactions on Machine Learning Research (01/2026)
H.3 Approximate Dynamic Equations in Finite Low SNR Regime
Theorem H.7. For the EM iterations of a' == ||0'1//a, 3 = tanh p² = (0', / |||0 given a' 1/4 and 1 = 110"1//0 x in low SNR regime, we have the approximate equations for a g+ Bett1
18191099/111191 v la??²)
g+ = Etaanh(a X + 1/) X + n/8 Bltanh(aaa + // x 020
at
8 = Ejtanh(o X + ) + n/ TR. (tanh(a' X + // x] + +
Furthermore, with the notations C = a² (1م1
|3 C. - |3 when S Cy ^ Cy we have:
(33((EE(a 0t+l = p² + +1 [p'13) n5 (E (aanthanaa + r1)] - a a'E[tanh" 2 (a X + x)) + x
+ o 11 2 + 000
)
11
(1 - (09)) +
)
"1 3)
(C
o
(G)))
where X is a random variable with the density function X fx(x)) Ko([=l)/+ involving the Bessel function Ko-
Proof. To simplify the notations, we let a', 8 p² e E2 denote a, S. E, E2 iteration t. We start by using
Lemma H.3 and Lemma H.4, we define sf = (o [89]2) then:
4 = [ - 3 O((a')))
8' (1-0)=(1)
I = -001 -lumflcx++x/xx===100001111111000
=
T Blaan((a'X+**) =
J (ttanh(a'X+v/)) a "a'tann"(a'X
= (1- -1 1=
In the low SNR regime where 17 |/0 / 1, by invoking the proven Theorem in Subsection H.2, we have:
M(O',u')/o = ह [ n3 p² + O(yaa')]
+ E f PAJ +O(Pa'))
N(0', = + + 011(('133)
For a²+1 = || (((01,')1// 1/0, N(0', (e), by applying the triangle inequality, we have:
a+1 = ( + 3 121322 + 120-099))3333111 O
ge+1
1 0
The cosine g²41 of angle between ac+1 and 0r is determined by the inner product of M (0' v/// and
8* |+ p²v + (ptPees
0 a 1+1 (M(0', w') 1/0,0'/10001) = 13 + n3 (1 -' +0()aa').
To derive the approximation for +1+1 when yj is small enough, we first note that following inequality:
é +ccos
+cos r2 + 2 2re 2recos cos + Ecosy 2r
n By letting r r= 8 p (13 J¹), = n1 S cos = = p¹, we have:
a ++ = 1 + n13 pz 1/ + -20 [8899199//1 - (1-13) v lat|2
at
where J -6,'' s0 + 0(oa and r O /a²) = (1- (313333)0(a)) when 17 S 0(1) S 11/("'(''p33)))
namely T, 2 n/3"/''' (1 J-)
59

---

Published in Transactions on Machine Learning Research (01/2026)
Furthurmore, when 2 x we have of 2 r/a'. Therefore, if 1 S min (at (1-1 1 n = = = -1-
--1893 we have 1f 2 p' / when 7 S V1 [3913 T3.0
|. 1..88.1111111 1- v1- [89T))
a (1-10
13.
3
^ / - [313, we have
a't a=t1= 0 - Os5 = - -1-
1= 3 Cy = v - 1393, then our assumptions on yi can be rewritten as 1 E C2 A C. By using such fact 1/(1 + x) = 1 + O(xx)) ve E 1-1/2.1/2] and If + n 1t = (1- (3)3) then:
For the simplicity of notations, we define C, == a
(4 n8+ 111)/a/++======= = 1+0 ((#)
(G)) v )
Similary, by letting x = (a'+1 - T1 and note that 1 = (1 - 18933) 12= 0(0), =0(19)) then:
1
1/a0t1
T
1 + p'O
C
+ 0
(
C2
J' J/ = n/3 J 11/1/+1'00 ((2)) + +o
v
(d,) 21
)
2
?
v
Ci
Note that a²+1 = O(I5) = -05 -1 (1- (1-181))0(aa) therefore we have:
0(r2at)/a (((
2
Note the following relation that we obtained earlier:
-++²= p¹ - (Ti + n3" of T2)//aat1
+1 + (1 - (093)) Jn + +
by combining the above results and invoking the assumption 7. Cy A C²₁, then we have:
( ((=) 2)
+ +0' ((2))
2)
+(1 (1 11-) 7 3
p' n J 1'
リ (C,)
(
In summary, with the notations C, = a² (1-18113 1335 C² = VI-189p given at < 1/4, S 1, we have:
a++1 1 n p' 12 a² 1393)0 ((c)) 2
)
7 2
ge1
To + n p 1 (112(a7)3)
with the assumption S C, A Cg. we also have
0 p² + (1-11''1 10133) n J /1 +0 (( 17
((=)) +0'0
((2)) 17 C,,) (2)) +(1 (1- +1 119) (11199)-00
((((())) 3)
((2)).
p'O
Remark. When Ip'| = 1, by noting the remark in Subscction H.2, the remainder term of the EM update rules in the direction of øt is exactly zero, namely 12)0 az) )|m = 0, thus we have:
|M (M((".>>)/// |-|== = [ + n p² 1 + 0()²a')
Therefore, we have |pt if |p'|= = since 8- 8/111011| = sgn(p') ot when Ip'l = 1 and
10+ - (M (OMM0 '') /|00 |I| = K sgu(p") = ((), - 1.
60

---

Published in Transactions on Machine Learning Research (01/2026)
Theorem H.8 (Dynamic Equations of EM Update Rules Low SNR Regime). For the EM iterations of a' : 1001// 3 == tanh p² == (0', /0] given a' 1/4 and 1 100 11/o S in low SNR regime, we have the approximate dynamic equations for a²+ ,
a+ a' - (39) + p' 9(1 (893))
(1 - (1-131))(((1)))) 1²0 - ( (a9)3)
a²
ge+1 (1-
n13" p'a'(1 11873) + (1 (8)))(((aTT)) + 1 (la1?)
Furthermore, with the notations Cy = a² 1-1
131.301 C = vI - 137 when S Cy A C²2, we have:
p 1T = p'+ (1 - [p'1) n99 8¹11 6/a 6/a-1313113
a'(1 - [34]2)
+ (1 (1-10'?3) 7735
+ +1)0(1093)
+ O'O ( (2,,) 2
3
o
+ (L- o
17
Cr
Proof. By using Lemma H.3 and Lemma H.4 and defining s² = [1-]2(1- - [39)), we have:
fg = (aoh(aaX++)))) = 8 s0(1 + (((a))))),
I = [ttan((a = -1 - -(['''))
I P ( -11-- J
ooooa//""=="]]ooododddddd""""""" 33 (1
=
By substituting the above results into the approximate dynamic equations in proven Theorem H.7, note that
(1 - ((a))) + n3 p' - -1- (1]30)) we have:
a ++| = ( -119111111011 911
+ (1 (1- (1=)))))0(((()))++++ + (1 - (399) V (a9)3)
[1999199/111
at
|| + n3 -1 (1- (
Note that 3²(1 - (00 "( we have: + (1
g = - (1 -
(1) + 17 (la*13).
Furthermore, with the notations C, at To. C₂ = v 1 1,7,, when 17 2 Cn A Cy we have:
1
J/H 3 /-((1 (3933)
1 (1
30' 8t 1 3-3/a9 - 3(0)2) + ((()71)
1 1- 1-3/a 1011-333333 31302) + (((9)))
831(11 (1112) + 1 1812 9 a² 13
a²
I - O((a)3)) 00 + 000(0()3))
at
1842
8² 6/a ([a4)218813)
+ (
a1 (3022
hence,
r² + (1 - (0-13) n133 8¹ - 6[a
1+
a²(1 - (89]2
+ (1 - -pplt)) n- 8² (1/(1 + +1)0((a(13
17 2
2) (/
17 3
+
+ Op4
(6)) + (1 11-1)))) o
C
C
E
61


Reviews:
[{"review_id": "0ejfJy5kGE", "reviewer": "Reviewer_wKF4", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper presents a theoretical analysis of the expectation–maximization (EM) algorithm for mixed linear regression when the fitted model has two components but the true data-generating process is single-component. It establishes, for instance, convergence rate results for both balanced and unbalanced cases and supports them with numerical experiments.\n\n*Remark*: I'm sorry about the delay. To avoid holding up the process further, I'll share my feedback without having checked all derivations in detail.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The theoretical claims are soundly developed and presented with mathematical rigor. The exposition is coherent, and the included numerical experiments are well structured and consistent with the stated results, providing credible support for the main theoretical arguments. The overview of related work is thorough and situates the contribution clearly within the existing literature.\n\nHowever, the presentation is dense, and several results would benefit from additional commentary explaining their intuition, scope, and implications. The paper currently provides limited discussion of how the theoretical insights relate to practical applications; the two motivating examples are illustrative but not empirically explored.", "audience_yn": "Yes", "audience_explanation": "The work is specialized and primarily of interest to researchers studying the theoretical underpinnings of EM-type algorithms or mixture models. While the scope is narrow, the results contribute to understanding failure modes and convergence guarantees in over-specified mixture models. Including a clearer discussion of the relevance and broader implications would increase accessibility to a wider segment of the audience. Clarifying the connections to broader themes such as overparameterization or robustness in iterative algorithms would further enhance its appeal to the TMLR audience.", "requested_changes": "- Add brief intuitive explanations after each main theorem to clarify its significance and relation to practical algorithmic behavior.\n- Include at least one applied or simulated example demonstrating how the derived convergence rates manifest in a more realistic setting, or explicitly clarify that the work is purely theoretical and adjust claims accordingly.\n\nOptional suggestions:\n- In eq. (1): for notational simplicity, consider defining $z\\in \\{-1, 1\\}$ instead of using $(-1)^{z+1}$.\n- Expand the discussion section to connect findings to current trends in overparameterized models and algorithmic stability.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "4eAdyi4wkp", "reviewer": "Reviewer_HWto", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper establishes theoretical guarantees for the Expectation–Maximization (EM) algorithm applied to two-component mixture of linear regression (2MLR) models. The main contributions are Theorem 5.1, which characterizes the convergence rate of the population-level EM algorithm, and Theorem 6.1, which provides finite-sample guarantees by quantifying the statistical accuracy as a function of sample size. Moreover, Theorem 6.1 can be linked to Theorem 5.1 to derive bounds on the iteration complexity. The paper also extends the analysis to the low–signal-to-noise ratio (SNR) regime. Technically, it derives approximate dynamic equations governing the evolution of the regression parameters and mixing weights under population-level EM updates, offering deeper insight into the algorithm’s convergence behavior.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The paper is clearly written, with a well-defined problem setup, explicit assumptions, and carefully stated theoretical guarantees. Although I did not examine all technical details, particularly the proofs, the authors effectively convey the key ideas and the overall proof strategy throughout the paper. The proposed theoretical analysis is further supported by empirical verification on synthetic data.", "audience_yn": "Yes", "audience_explanation": "Considering the broad readership of TMLR, I believe that some readers may find this work of interest. However, to be honest, the topic feels somewhat narrow, as it focuses on the theoretical properties of a very specific model applied to a particular setting with a specific learning algorithm—one among many possible alternatives.", "requested_changes": "If feasible, it would be valuable to include empirical demonstrations on real-world datasets. For example, as the authors mention in the main paper, applications such as haplotype assembly or phase retrieval could serve as compelling examples to illustrate the practical relevance of the theoretical findings. While the current synthetic experiments are informative for validating the analysis, experiments on real data would better highlight the algorithm’s strengths and potential limitations in realistic settings. Since I am not an expert on this particular algorithmic framework, it is somewhat difficult for me to fully assess its practical utility.", "broader_impact_concerns": "I don't find any broader impact concerns regarding the submission.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "gMnxfr4WXA", "reviewer": "Reviewer_8cnp", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper offers theoretical analysis of the Expectation-Maximization (EM) algorithm's performance in the context of overspecified two-component Mixed Linear Regression. The authors explore the complex situation where the model includes more components than the actual data-generating distribution. A significant contribution is the examination of how the initial estimate of the mixing weights critically influences the convergence rate of the regression parameters. The theoretical findings are corroborated by numerical experiments and linked to practical applications such as haplotype assembly and phase retrieval.\n\nStrengths:\n\n1. The paper delivers an overview of the evolution of EM for both regression parameters and mixing weights in the overspecified context.\n\n2. It establishes precise bounds for convergence rates and final statistical error, enhancing previous results for 2GMM.\n\n3. The analysis extends beyond the overspecified context to include the finite low SNR regime.\n\nWeaknesses:\n\n1. The theoretical guarantees are specifically derived for two-component mixtures with Gaussian covariates and noise.\n\n2. The paper lacks practical strategies for achieving a favorable unbalanced initialization in real-world situations where the true parameters are not known.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The paper's claims are supported by a novel theoretical framework that incorporates exact EM derivations using Bessel functions, along with numerical experiments that validate the theoretical findings.", "audience_yn": "Yes", "audience_explanation": "The paper's rigorous characterization of EM's convergence dichotomy in a fundamental model like mixed linear regression, along with its improved theoretical bounds, will be of great interest to TMLR's audience.", "requested_changes": "1. In practice, how would you suggest initializing $\\pi^0$? Would a strategy that intentionally unbalances the initial guess be advantageous, even if the true weights are balanced?\n\n2. Including simulations related to haplotype assembly or phase retrieval, along with an explanation of how your results contribute, would be beneficial.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)