Global analysis of Expectation Maximization for mixtures of two Gaussians

Introduction

Since Fisher’s 1922 paper (Fisher, 1922), maximum likelihood estimators (MLE) have become one of the most popular tools in many areas of science and engineering. The asymptotic consistency and optimality of MLEs have provided users with the confidence that, at least in some sense, there is no better way to estimate parameters for many standard statistical models. Despite its appealing properties, computing the MLE is often intractable. Indeed, this is the case for many latent variable models $\{f(\mathcal{Y},\boldsymbol{z};\boldsymbol{\eta})\}$, where the latent variables $\boldsymbol{z}$ are not observed. For each setting of the parameters $\boldsymbol{\eta}$, the marginal distribution of the observed data $\mathcal{Y}$ is (for discrete $\boldsymbol{z}$)

It is this marginalization over latent variables that typically causes the computational difficulty. Furthermore, many algorithms based on the MLE principle are only known to find stationary points of the likelihood objective (e.g., local maxima), and these points are not necessarily the MLE.

Among the algorithms mentioned above, Expectation Maximization (EM) has attracted more attention for the simplicity of its iterations, and its good performance in practice (Dempster et al., 1977; Redner and Walker, 1984). EM is an iterative algorithm for climbing the likelihood objective starting from an initial setting of the parameters $\hat{\boldsymbol{\eta}}^{\langle 0\rangle}$. In iteration $t$, EM performs the following steps:

In many applications, each step is intuitive and can be performed very efficiently.

Despite the popularity of EM, as well as the numerous theoretical studies of its behavior, many important questions about its performance—such as its convergence rate and accuracy—have remained unanswered. The goal of this paper is to address these questions for specific models (described in Section 1.2) in which the observation $\mathcal{Y}$ is an i.i.d. sample from a mixture of two Gaussians.

Towards this goal, we study an idealized execution of EM in the large sample limit, where the E-step is modified to be computed over an infinitely large i.i.d. sample from a Gaussian mixture distribution in the model. In effect, in the formula for $\hat{Q}(\boldsymbol{\eta}\mid\hat{\boldsymbol{\eta}}^{\langle t\rangle})$, we replace the observed data $\mathcal{Y}$ with a random variable $\boldsymbol{Y}\sim f(\boldsymbol{y};\boldsymbol{\eta}^{\star})$ for some Gaussian mixture parameters $\boldsymbol{\eta}^{\star}$ and then take its expectation. The resulting E- and M-steps in iteration $t$ are

This sequence of parameters $(\boldsymbol{\eta}^{\langle t\rangle})_{t\geq 0}$ is fully determined by the initial setting $\boldsymbol{\eta}^{\langle 0\rangle}$. We refer to this idealization as Population EM. Not only does Population EM shed light on the dynamics of EM in the large sample limit, but it can also reveal some of the fundamental limitations of EM. Indeed, if Population EM cannot provide an accurate estimate for the parameters $\boldsymbol{\eta}^{\star}$, then intuitively, one would not expect the EM algorithm with a finite sample size to do so either. (To avoid confusion, we refer the original EM algorithm run with a finite sample as Sample-based EM.)

2 Models and Main Contributions

In this paper, we study EM in the context of two simple yet popular and well-studied Gaussian mixture models. The two models, along with the corresponding Sample-based EM and Population EM updates, are as follows:

Sample-based EM iteratively updates its estimate of $\boldsymbol{\theta}^{\star}$ according to the following equation:

where $\boldsymbol{y}_{1},\dotsc,\boldsymbol{y}_{n}$ are the independent draws that comprise $\mathcal{Y}$,

and $\phi_{d}$ is the density of a Gaussian random vector with mean $\boldsymbol{0}$ and covariance $\boldsymbol{\Sigma}$.

Population EM iteratively updates its estimate according to the following equation:

where $\boldsymbol{Y}\sim 0.5N(-\boldsymbol{\theta}^{\star},\boldsymbol{\Sigma})+0.5N(\boldsymbol{\theta}^{\star},\boldsymbol{\Sigma})$.

The observation $\mathcal{Y}$ is an i.i.d. sample from the mixture distribution $0.5N(\boldsymbol{\mu}_{1}^{\star},\boldsymbol{\Sigma})+0.5N(\boldsymbol{\mu}_{2}^{\star},\boldsymbol{\Sigma})$. Again, $\boldsymbol{\Sigma}$ is known, and $(\boldsymbol{\mu}_{1}^{\star},\boldsymbol{\mu}_{2}^{\star})$ are the unknown parameters of interest.

Sample-based EM iteratively updates its estimate of $\boldsymbol{\mu}_{1}^{\star}$ and $\boldsymbol{\mu}_{2}^{\star}$ at every iteration according to the following equations:

where $\boldsymbol{y}_{1},\dotsc,\boldsymbol{y}_{n}$ are the independent draws that comprise $\mathcal{Y}$, and

Population EM iteratively updates its estimates according to the following equations:

where $\boldsymbol{Y}\sim 0.5N(\boldsymbol{\mu}_{1}^{\star},\boldsymbol{\Sigma})+0.5N(\boldsymbol{\mu}_{2}^{\star},\boldsymbol{\Sigma})$.

Our main contribution in this paper is a new characterization of the stationary points and dynamics of EM in both of the above models.

We prove convergence for the sequence of iterates for Population EM from each model: the sequence $(\boldsymbol{\theta}^{\langle t\rangle})_{t\geq 0}$ converges to either $\boldsymbol{\theta}^{\star}$, $-\boldsymbol{\theta}^{\star}$, or $\boldsymbol{0}$; the sequence $((\boldsymbol{\mu}_{1}^{\langle t\rangle},\boldsymbol{\mu}_{2}^{\langle t\rangle}))_{t\geq 0}$ converges to either $(\boldsymbol{\mu}_{1}^{\star},\boldsymbol{\mu}_{2}^{\star})$, $(\boldsymbol{\mu}_{2}^{\star},\boldsymbol{\mu}_{1}^{\star})$, or $((\boldsymbol{\mu}_{1}^{\star}+\boldsymbol{\mu}_{2}^{\star})/2,(\boldsymbol{\mu}_{1}^{\star}+\boldsymbol{\mu}_{2}^{\star})/2)$. We also fully characterize the initial parameter settings that lead to each limit point.

Using this convergence result for Population EM, we also prove that the limits of the Sample-based EM iterates converge in probability to the unknown parameters of interest, as long as Sample-based EM is initialized at points where Population EM would converge to these parameters as well.

Formal statements of our results are given in Section 2.

3 Background and Related Work

The EM algorithm was formally introduced by Dempster et al. (1977) as a general iterative method for computing parameter estimates from incomplete data. Although EM is billed as a procedure for maximum likelihood estimation, it is known that with certain initializations, the final parameters returned by EM may be far from the MLE, both in parameter distance and in log-likelihood value (Wu, 1983). Several works characterize local convergence of EM to stationary points of the log-likelihood objective under certain regularity conditions (Wu, 1983; Tseng, 2004; Chrétien and Hero, 2008). However, these analyses do not distinguish between global maximizers and other stationary points (except, e.g., when the likelihood function is unimodal). Thus, as an optimization algorithm for maximizing the log-likelihood objective, the “worst-case” performance of EM is somewhat discouraging.

For a more optimistic perspective on EM, one may consider a “best-case” analysis, where (i) the data are an iid sample from a distribution in the given model, (ii) the sample size is sufficiently large, and (iii) the starting point for EM is sufficiently close to the parameters of the data generating distribution. Conditions (i) and (ii) are ubiquitous in (asymptotic) statistical analyses, and (iii) is a generous assumption that may be satisfied in certain cases. Redner and Walker (1984) show that in such a favorable scenario, EM converges to the MLE almost surely for a broad class of mixture models. Moreover, recent work of Balakrishnan et al. (2014) gives non-asymptotic convergence guarantees in certain models; importantly, these results permit one to quantify the accuracy of a pilot estimator required to effectively initialize EM. Thus, EM may be used in a tractable two-stage estimation procedures given a first-stage pilot estimator that can be efficiently computed.

Most relevant to this paper are works that specifically analyze EM (or variants thereof) for Gaussian mixture models, especially when the mixture components are well-separated. Xu and Jordan (1996) show favorable convergence properties (akin to super-linear convergence near the MLE) for well-separated mixtures. In a related but different vein, Dasgupta and Schulman (2007) analyze a variant of EM with a particular initialization scheme, and proves fast convergence to the true parameters, again for well-separated mixtures in high-dimensions. For mixtures of two Gaussians, it is possible to exploit symmetries to get sharper analyses. Indeed, Chaudhuri et al. (2009b) uses these symmetries to prove that a variant of Lloyd’s algorithm (MacQueen, 1967; Lloyd, 1982) (which may be regarded as a hard-assignment version of EM) very quickly converges to the subspace spanned by the two mixture component means, without any separation assumption. Lastly, for the specific case of our Model 1, Balakrishnan et al. (2014) proves linear convergence of EM (as well as a gradient-based variant of EM) when started in a sufficiently small neighborhood around the true parameters; here, the size of the neighborhood grows with the separation between the two mixture components (which must be sufficiently large). Their analysis also proceeds by studying Population EM, and then relating Sample-based EM to it. Remarkably, by focusing attention on the local region around the true parameters, they obtain non-asymptotic bounds on the parameter estimation error. Our work is complementary to their result in that we focus on asymptotic limits rather than finite sample analysis. This allows us to provide a global analysis of EM, without any separation assumption; such an analysis cannot be deduced from the results of Balakrishnan et al. by taking limits.

Analysis of EM for Mixtures of Two Gaussians

In this section, we present our results for Population EM and Sample-based EM under both Model 1 and Model 2, and also discuss further implications about the expected log-likelihood function. Without loss of generality, we may assume that the known covariance matrix $\boldsymbol{\Sigma}$ is the identity matrix $\boldsymbol{I}_{d}$. Throughout, we denote the Euclidean norm by $\|\cdot\|$, and the signum function by $\operatorname{sgn}(\cdot)$ (where $\operatorname{sgn}(0)=0$, $\operatorname{sgn}(z)=1$ if $z>0$, and $\operatorname{sgn}(z)=-1$ if $z<0$).

We present results for Population EM for both models, starting with Model 1.

Our next result shows that if $\langle\boldsymbol{\theta}^{\langle 0\rangle},\boldsymbol{\theta}^{\star}\rangle=0$, then $(\boldsymbol{\theta}^{\langle t\rangle})_{t\geq 0}$ still converges, albeit to $\boldsymbol{0}$.

Let $(\boldsymbol{\theta}^{\langle t\rangle})_{t\geq 0}$ denote the Population EM iterates for Model 1. If $\langle\boldsymbol{\theta}^{\langle 0\rangle},\boldsymbol{\theta}^{\star}\rangle=0$, then

Theorems 1 and 2 together characterize the fixed points of Population EM for Model 1, and fully specify the conditions under which each fixed point is reached. The results are simply summarized in the following corollary.

If $(\boldsymbol{\theta}^{\langle t\rangle})_{t\geq 0}$ denote the Population EM iterates for Model 1, then

We now discuss Population EM with Model 2. To state our results more concisely, we use the following re-parameterization of the model parameters and Population EM iterates:

If the sequence of Population EM iterates $((\boldsymbol{\mu}_{1}^{\langle t\rangle},\boldsymbol{\mu}_{2}^{\langle t\rangle}))_{t\geq 0}$ converges to $(\boldsymbol{\mu}_{1}^{\star},\boldsymbol{\mu}_{2}^{\star})$, then we expect $\boldsymbol{b}^{\langle t\rangle}\rightarrow\boldsymbol{\theta}^{\star}$. Hence, we also define $\beta^{\langle t\rangle}$ as the angle between $\boldsymbol{b}^{\langle t\rangle}$ and $\boldsymbol{\theta}^{\star}$, i.e.,

(This is well-defined as long as $\boldsymbol{b}^{\langle t\rangle}\neq\boldsymbol{0}$ and $\boldsymbol{\theta}^{\star}\neq\boldsymbol{0}$.)

We first present results on Population EM with Model 2 under the initial condition $\langle\boldsymbol{b}^{\langle 0\rangle},\boldsymbol{\theta}^{\star}\rangle\neq 0$.

By combining the two inequalities from Theorem 3, we conclude

Theorem 3 shows that the re-parameterized Population EM iterates converge, at a linear rate, to the average of the two means $(\boldsymbol{\mu}_{1}^{\star}+\boldsymbol{\mu}_{2}^{\star})/2$, as well as the line spanned by $\boldsymbol{\theta}^{\star}$. The theorem, however, does not provide any information on the convergence of the magnitude of $\boldsymbol{b}^{\langle t\rangle}$ to the magnitude of $\boldsymbol{\theta}^{\star}$. This is given in the next theorem.

If $\langle\boldsymbol{b}^{\langle 0\rangle},\boldsymbol{\theta}^{\star}\rangle=0$, then we show convergence of the (re-parameterized) Population EM iterates to the degenerate solution $(\boldsymbol{0},\boldsymbol{0})$.

Let $(\boldsymbol{a}^{\langle t\rangle},\boldsymbol{b}^{\langle t\rangle})_{t\geq 0}$ denote the (re-parameterized) Population EM iterates for Model 2. If $\langle\boldsymbol{b}^{\langle 0\rangle},\boldsymbol{\theta}^{\star}\rangle=0$, then

Theorems 3, 4, and 5 together characterize the fixed points of Population EM for Model 2, and fully specify the conditions under which each fixed point is reached. The results are simply summarized in the following corollary.

If $(\boldsymbol{a}^{\langle t\rangle},\boldsymbol{b}^{\langle t\rangle})_{t\geq 0}$ denote the (re-parameterized) Population EM iterates for Model 2, then

2 Main Results for Sample-based EM

Using the results on Population EM presented in the above section, we can now establish consistency of (Sample-based) EM. We focus attention on Model 2, as the same results for Model 1 easily follow as a corollary. First, we state a simple connection between the Population EM and Sample-based EM iterates.

Suppose Population EM and Sample-based EM for Model 2 have the same initial parameters: $\hat{\boldsymbol{\mu}}_{1}^{\langle 0\rangle}=\boldsymbol{\mu}_{1}^{\langle 0\rangle}$ and $\hat{\boldsymbol{\mu}}_{2}^{\langle 0\rangle}=\boldsymbol{\mu}_{2}^{\langle 0\rangle}$. Then for each iteration $t\geq 0$,

Note that Theorem 6 does not necessarily imply that the fixed point of Sample-based EM (when initialized at $(\hat{\boldsymbol{\mu}}_{1}^{\langle 0\rangle},\hat{\boldsymbol{\mu}}_{2}^{\langle 0\rangle})=(\boldsymbol{\mu}_{1}^{\langle 0\rangle},\boldsymbol{\mu}_{2}^{\langle 0\rangle})$) is the same as that of Population EM. It is conceivable that as $t\to\infty$, the discrepancy between (the iterates of) Sample-based EM and Population EM increases. We show that this is not the case: the fixed points of Sample-based EM indeed converge to the fixed points of Population EM.

Suppose Population EM and Sample-based EM for Model 2 have the same initial parameters: $\hat{\boldsymbol{\mu}}_{1}^{\langle 0\rangle}=\boldsymbol{\mu}_{1}^{\langle 0\rangle}$ and $\hat{\boldsymbol{\mu}}_{2}^{\langle 0\rangle}=\boldsymbol{\mu}_{2}^{\langle 0\rangle}$. If $\langle\boldsymbol{\mu}_{2}^{\langle 0\rangle}-\boldsymbol{\mu}_{1}^{\langle 0\rangle},\boldsymbol{\theta}^{\star}\rangle\neq 0$, then

3 Population EM and Expected Log-likelihood

Do the results we derived in the last section regarding the performance of EM provide any information on the performance of other ascent algorithms, such as gradient ascent, that aim to maximize the log-likelihood function? To address this question, we show how our analysis can determine the stationary points of the expected log-likelihood and characterize the shape of the expected log-likelihood in a neighborhood of the stationary points. Let $G(\boldsymbol{\eta})$ denote the expected log-likelihood, i.e.,

where $\boldsymbol{\eta}^{*}$ denotes the true parameter value. Also consider the following standard regularity conditions:

The family of probability density functions $f(\boldsymbol{y};\boldsymbol{\eta})$ have common support.

$\nabla_{\boldsymbol{\eta}}\int f(\boldsymbol{y};\boldsymbol{\eta}^{*})\log f(\boldsymbol{y};\boldsymbol{\eta})\operatorname{d\!}\boldsymbol{y}=\int f(\boldsymbol{y};\boldsymbol{\eta}^{*})\nabla_{\boldsymbol{\eta}}\log f(\boldsymbol{y};\boldsymbol{\eta})\operatorname{d\!}\boldsymbol{y}$, where $\nabla_{\boldsymbol{\eta}}$ denotes the gradient with respect to $\boldsymbol{\eta}$.

These conditions can be easily confirmed for many models including the Gaussian mixture models. The following theorem connects the fixed points of the Population EM and the stationary points of the expected log-likelihood.

Let $\bar{\boldsymbol{\eta}}$ denote a stationary point of $G(\boldsymbol{\eta})$. We first prove that $\bar{\boldsymbol{\eta}}$ is a stationary point of $Q(\boldsymbol{\eta}\mid\bar{\boldsymbol{\eta}})$.

where the last equality is using the fact that $\bar{\boldsymbol{\eta}}$ is a stationary point of $G(\boldsymbol{\eta})$. Since $Q(\boldsymbol{\eta}\mid\bar{\boldsymbol{\eta}})$ has a unique stationary point, and we have assumed that the unique stationary point is its global maxima, then Population EM will stay at that point. The proof of the other direction is similar. ∎

The fact that $\boldsymbol{\eta}^{*}$ is the global maximizer of $G(\boldsymbol{\eta})$ is well-known in the statistics and machine learning literature (e.g., Conniffe, 1987). Furthermore, the fact that $\boldsymbol{\eta}^{*}$ is a global maximizer of $Q(\boldsymbol{\eta}\mid\boldsymbol{\eta}^{*})$ is known as the self-consistency property (Balakrishnan et al., 2014).

It is straightforward to confirm the conditions of Lemma 1 for mixtures of Gaussians. This lemma confirms that Population EM may be trapped in every local maxima. However, less intuitively it may get stuck at local minima or saddle points as well. Our next result characterizes the stationary points of $G(\boldsymbol{\theta})$ for Model 1.

The proof is a straightforward result of Lemma 1 and Corollary 1. The phenomenon that Population EM may stuck in local minima or saddle points also happens in Model 2. We can employ Corollary 2 and Lemma 1 to explain the shape of the expected log-likelihood function $G$. To simplify the notation, we consider the re-parametrization $\boldsymbol{a}\triangleq\frac{\boldsymbol{\mu}_{1}+\boldsymbol{\mu}_{2}}{2}$ and $\boldsymbol{b}\triangleq\frac{\boldsymbol{\mu}_{2}-\boldsymbol{\mu}_{1}}{2}$.

$G(\boldsymbol{a},\boldsymbol{b})$ has three stationary points:

The first two points are global maxima. The third point is a saddle point.

Concluding Remarks

Our analysis of Population EM and Sample-based EM shows that the EM algorithm can, at least for the Gaussian mixture models studied in this work, compute statistically consistent parameter estimates. Previous analyses of EM only established such results for specific methods of initializing EM (e.g., Dasgupta and Schulman, 2007; Balakrishnan et al., 2014); our results show that they are not really necessary in the large sample limit. However, in any real scenario, the large sample limit may not accurately characterize the behavior of EM. Therefore, these specific methods for initialization, as well as non-asymptotic analysis, are clearly still needed to understand and effectively apply EM.

There are several interesting directions concerning EM that we hope to pursue in follow-up work. The first considers the behavior of EM when the dimension $d=d_{n}$ may grow with the sample size $n$. Our proof of Theorem 7 reveals that the parameter error of the $t$-th iterate (in Euclidean norm) is of the order $\sqrt{d/n}$ as $t\to\infty$. Therefore, we conjecture that the theorem still holds as long as $d_{n}=o(n)$. This would be consistent with results from statistical physics on the MLE for Gaussian mixtures, which characterize the behavior when $d_{n}\propto n$ as $n\to\infty$ (Barkai and Sompolinsky, 1994).

Another natural direction is to extend these results to more general Gaussian mixture models (e.g., with unequal mixing weights or unequal covariances) and other latent variable models.

The second named author thanks Yash Deshpande and Sham Kakade for many helpful initial discussions. JX and AM were partially supported by NSF grant CCF-1420328. DH was partially supported by NSF grant DMREF-1534910 and a Sloan Fellowship.

References

Appendix A Proofs of the Main Results

This appendix is devoted to the proofs of our main results, and is organized as follows.

Section A.2 establishes a connection between Model 1 and Model 2 for Population EM. This connection enables us to use the analysis of Population EM for Model 2 for the analysis of Population EM for Model 1.

Section A.3 presents several structural properties of Population EM. These properties will be used in the proofs of our main results.

Section A.4 introduces several notations that will be used in the proofs of our main results.

Section A.5 presents the proof of Theorem 3.

Section A.6 presents the proof of Theorem 4.

Section A.7 presents the proof of Theorem 1.

Section A.8 presents the proof of Theorem 5, which also implies Theorem 2.

Section A.9 presents the proof of Theorem 6.

Section A.10 presents the proof of Theorem 7.

Appendix B includes a few auxiliary results that are used in the proofs of our main results.

A.2 Connection Between Models 1 and 2

In this section, we draw a connection between Model 1 and Model 2. This will enable us to conclude most of the results for Model 1 from the results we prove for Model 2. First, consider the re-parametrization introduced in (11). The iterations of Population EM can be written in terms of these new parameters $\boldsymbol{a}^{\langle t\rangle},\boldsymbol{b}^{\langle t\rangle}$ as

as shorthand for the Gaussian mixture density $0.5N(-\boldsymbol{\theta}^{\star},I_{d})+0.5N(\boldsymbol{\theta}^{\star},I_{d})$.

The following lemma establishes a connection between the iterations of Population EM for Model 1 and for Model 2.

If $\boldsymbol{a}^{\langle 0\rangle}=\boldsymbol{0}$, then $\boldsymbol{a}^{\langle t\rangle}=\boldsymbol{0}$ for every $t$. Furthermore,

Observe that the expression for $\boldsymbol{b}^{\langle t+1\rangle}$ in Lemma 2 is the same as the Population EM update under Model 1, given in (6).

Lemma 2 tells us that Model 1 is a special case of Model 2 if we know the mean $(\boldsymbol{\mu}_{1}^{\star}+\boldsymbol{\mu}_{2}^{\star})/2$ is known. In this case, $\boldsymbol{b}^{\langle t\rangle}$ is regarded as an estimate of $(\boldsymbol{\mu}_{2}^{\star}-\boldsymbol{\mu}_{1}^{\star})/2$, in the same way that $\boldsymbol{\theta}^{\langle t\rangle}$ is an estimate of $\boldsymbol{\theta}^{\star}$ in Model 1. (This explains our choice of the notation $\boldsymbol{\theta}^{\star}\triangleq(\boldsymbol{\mu}_{2}^{\star}-\boldsymbol{\mu}_{1}^{\star})/2$ in (11).)

The proof of Lemma 2 is a simple induction that exploits the fact that $\mathsf{w}_{d}(\boldsymbol{Y},\boldsymbol{b}^{\langle t\rangle})+\mathsf{w}_{d}(-\boldsymbol{Y},\boldsymbol{b}^{\langle t\rangle})=1$: if $\boldsymbol{a}^{\langle t\rangle}=\boldsymbol{0}$, then

A.3 Some Structural Properties of Population EM

An important structural property of Population EM is that the updates are orthogonally invariant. This means that our analysis of Population EM can make use of any orthogonal basis as the coordinate system without affecting the conclusions. This is spelled out in the following lemma.

Using the Lemma 3, we can establish some simple invariances about Population EM, which we state in the following lemmas.

The following holds for any two settings of $(\boldsymbol{a}^{\langle 0\rangle}_{(1)},\boldsymbol{b}^{\langle 0\rangle}_{(1)})$ and $(\boldsymbol{a}^{\langle 0\rangle}_{(2)},\boldsymbol{b}^{\langle 0\rangle}_{(2)})$.

If $\boldsymbol{a}^{\langle 0\rangle}_{(1)}=-\boldsymbol{a}^{\langle 0\rangle}_{(2)}$ and $\boldsymbol{b}^{\langle 0\rangle}_{(1)}=\boldsymbol{b}^{\langle 0\rangle}_{(2)}$, then

If $\boldsymbol{b}^{\langle 0\rangle}_{(1)}=-\boldsymbol{b}^{\langle 0\rangle}_{(2)}$ and $\boldsymbol{a}^{\langle 0\rangle}_{(1)}=\boldsymbol{a}^{\langle 0\rangle}_{(2)}$, then

The proof of Lemma 4 is in Appendix B.1, and the proof of Lemma 5 is in Appendix B.2. These two lemmas imply that in our analysis of Population EM, we may assume without loss of generality that

Next, we show that effectively all of the action of Population EM takes place in a two-dimensional subspace.

where $\boldsymbol{Y}\sim 0.5N(-\boldsymbol{\theta}^{\star},\boldsymbol{I}_{d})+0.5N(\boldsymbol{\theta}^{\star},\boldsymbol{I}_{d})$.

where the last equality follows because $\boldsymbol{Y}$ has mean zero. ∎

Let $M_{0}$ denote the span of $\boldsymbol{b}^{\langle 0\rangle}\neq\boldsymbol{0}$ and $\boldsymbol{\theta}^{\star}\neq\boldsymbol{0}$ for the model $\boldsymbol{Y}\sim 0.5N(-\boldsymbol{\theta}^{\star},\boldsymbol{I}_{d})+0.5N(\boldsymbol{\theta}^{\star},\boldsymbol{I}_{d})$. Then $\boldsymbol{b}^{\langle t\rangle}\in M_{0}$ for all $t\geq 0$.

This follows from Lemma 6 and induction, by letting the columns of $\boldsymbol{U}$ be an orthonormal basis for $M_{0}$, and letting the columns of $\boldsymbol{V}$ to be a basis for the orthogonal complement of $M_{0}$. ∎

Recall that in Section 2.1, we defined the angle between $\boldsymbol{b}^{\langle t\rangle}$ and $\boldsymbol{\theta}^{\star}$ as $\beta^{\langle t\rangle}$. For our analysis, it will turn out to be useful to consistently refer to the cosine and sine of this angle, and hence we should regard the angle as possibly being any value between and $2\pi$. To do this, we fix an orthogonal basis $\{\boldsymbol{e}_{1}^{\langle t\rangle},\cdots,\boldsymbol{e}_{d}^{\langle t\rangle}\}$ such that

and define $\beta^{\langle t\rangle}\in[0,2\pi]$ be the angle such that

Using this definition of the angle $\beta^{\langle t\rangle}$, we can establish the following monotonicity property.

If $0\leq\beta^{\langle 0\rangle}<\pi/2$, then $\beta^{\langle 0\rangle}\geq\beta^{\langle 1\rangle}\geq\ldots\beta^{\langle t\rangle}\geq\ldots\geq 0$.

We assume $\beta^{\langle 0\rangle}>0$, the extension to $\beta^{\langle 0\rangle}=0$ is straightforward. Define $\alpha^{\langle t\rangle}$ as the angle between $\boldsymbol{b}^{\langle t\rangle}$ and $\boldsymbol{b}^{\langle t+1\rangle}$ such that

The strategy of the proof is to use induction to prove that the following three statements hold for $\forall t\geq 0$:

$\beta^{\langle t\rangle}\in(0,\frac{\pi}{2})$.

$\alpha^{\langle t\rangle}\in(0,\beta^{\langle t\rangle})$.

$\beta^{\langle t+1\rangle}=\beta^{\langle t\rangle}-\alpha^{\langle t\rangle}\in(0,\beta^{\langle t\rangle})$.

It is clear that the claim of the lemma holds if (iii) holds for all $t\geq 0$. The inductive argument uses the following chain of arguments for step $t$:

If (i) holds for $t$, then (ii) holds for $t$.

If (i) and (ii) hold for $t$, then (iii) holds for $t$.

If (i), (ii), and (iii) hold for $t$, then (i) holds for $t+1$.

Since (i) holds for $t=0$ by assumption, it suffices to prove Claims 1–3.

Claim 3 is trivially true, and Claim 2 follows from the fact that $\boldsymbol{\theta}^{\star}$ and all $\boldsymbol{b}^{\langle t\rangle}$ lie in a the same two-dimensional subspace. So we just have to prove Claim 1. For sake of clarity, we choose the orthogonal basis $\boldsymbol{e}_{1}^{\langle t\rangle},\boldsymbol{e}_{2}^{\langle t\rangle},\dotsc,\boldsymbol{e}_{d}^{\langle t\rangle}$ satisfying (17) to simplify the calculation. Let $\boldsymbol{U}_{t}$ be the orthogonal matrix whose rows are $\boldsymbol{e}_{1}^{\langle t\rangle},\boldsymbol{e}_{2}^{\langle t\rangle},\dotsc,\boldsymbol{e}_{d}^{\langle t\rangle}$, so

Hence it is clear that $\theta^{\star}_{\langle t\rangle,2}>0$ implies $\alpha^{\langle t\rangle}>0$ since $S(x_{a},x_{b},x_{\theta})>0$ for all $x_{b}>0$ and $x_{\theta}>0$.

where the last inequality is due to the fact that $R(x_{b},x)>0$ for all $x_{b}>0$.

A.4 Notations for the Remaining Proofs

In this section we collect the main notations that will be used in the proofs of our results. For the basic notation, we let $\phi_{d}(\boldsymbol{x})$ and $\Phi_{d}(\boldsymbol{x})$ denote the pdf and CDF for $d$-dimension standard Gaussian distribution respectively. We use $\phi(x)$ and $\Phi(x)$ as shorthand for one-dimension case. Let $\phi^{+}_{d}(x,x_{\theta})$ denote the pdf for $\boldsymbol{X}\sim 0.5N(-\boldsymbol{x}_{\theta},I)+0.5N(\boldsymbol{x}_{\theta},I)$, i.e.,

The importance of this function is clarified in the following calculations:

Note that according to (LABEL:equ:iteq21), we have

To understand where this function may appear, note that

A.5 Proof of Theorem 3

where Equality (a) is the result of (35) and (34). Hence it is straightforward to check that

where $c_{U,2}=\frac{1}{4}(1-\Phi(c_{U,1}+\|\boldsymbol{\theta}^{\star}\|))$. Hence, $\{\|\boldsymbol{a}^{\langle t\rangle}\|,\|\boldsymbol{b}^{\langle t\rangle}\|\}_{t}$ belong to a compact set.

We postpone the proof of this lemma until Appendix A.5.1, but the fact that the estimates remain bounded should not be surprising for the reader.

Let $\boldsymbol{b}^{\langle t\rangle}$ and $\boldsymbol{a}^{\langle t\rangle}$ denote the estimates of Population EM. There exists a value $c_{l}>0$ depending on $\|\boldsymbol{\theta}^{\star}\|$, $\langle\boldsymbol{b}^{\langle 0\rangle},\boldsymbol{\theta}^{\star}\rangle$, $\|\boldsymbol{a}^{\langle 0\rangle}\|$, and $\|\boldsymbol{b}^{\langle 0\rangle}\|$ such that

We postpone the proof of this claim to Appendix A.5.2. Note that according to Lemma 9 we know that $\sup_{t}\|\boldsymbol{a}^{\langle t\rangle}\|\leq c_{U,1}$ and $\sup_{t}\|\boldsymbol{b}^{\langle t\rangle}\|\leq c_{U,3}$. Hence, we define

This proves the first claim in Theorem 3. Our next goal is to prove the second claim, i.e.,

where Inequality $(\star)$ is due to the following lemma:

For any $\theta\geq 0$, there exists a constant $\kappa_{a}\in(0,1)$ only depending on $\theta$ and continuous for $\theta>0$ such that

Combining (39) and (41) establishes the second part of our main Theorem.

In this section we use the notations and equations that are summarize in Appendix A.4. Without loss of generality, we assume that $\langle\boldsymbol{b}^{\langle 0\rangle},\boldsymbol{\theta}^{\star}\rangle>0$ and $\langle\boldsymbol{a}^{\langle 0\rangle},\boldsymbol{b}^{\langle 0\rangle}\rangle\geq 0$ and it is straightforward to show that if $\|\boldsymbol{b}^{\langle 0\rangle}\|=0$, then

where Equalities (b) and (d) are due to (34). To obtain Inequality (c) we used the following chain of arguments: According to Lemma 4, $\mathsf{p}^{\langle t\rangle}\leq 0.5$ for every $t$. Hence, $2(1-\mathsf{p}^{\langle t+1\rangle})\geq 1$.

With exactly same calculation showed in (40), we have

If $x_{a}\geq x_{\theta}\geq 0,x_{b}\geq 0$, we have

We prove this lemma in the Appendix B.4. Combining (44) and Lemma 12 proves

We know from Lemma 4 that $\mathsf{p}^{\langle t+1\rangle}\leq 0.5$. In the range $0<\mathsf{p}^{\langle t+1\rangle}\leq 0.5$,

If $x_{a}\geq x_{\theta}\geq 0,x_{b}\geq 0$, we have

If $0\leq x_{a}<x_{\theta},x_{b}\geq 0$, we have

where $\Phi(x)$ is the CDF for a standard Gaussian distribution.

Therefore combining (45) and (47), we have

Hence, we have to find an upper bound for $\Gamma$ and a lower bound for $P$. Note that

A.5.2 Proof of Lemma 10

Without loss of generality we only consider the case $\langle\boldsymbol{b}^{\langle t\rangle},\boldsymbol{\theta}^{\star}\rangle>0$ and $\langle\boldsymbol{a}^{\langle t\rangle},\boldsymbol{b}^{\langle t\rangle}\rangle\geq 0$. Before we start the proof we remind the reader a couple of facts that we have proved in Lemma 8 and Lemma 9.

$\sup_{t}\|\boldsymbol{a}^{\langle t\rangle}\|\leq c_{U,1}$ and $\sup_{t}\|\boldsymbol{b}^{\langle t\rangle}\|\leq c_{U,3}$.

$\boldsymbol{b}^{\langle 1\rangle},\boldsymbol{b}^{\langle 2\rangle},\ldots,\boldsymbol{b}^{\langle t\rangle},\ldots$ and $\boldsymbol{\theta}^{\star}$ are all on the same two-dimensional plane:

The angle $\beta^{\langle t\rangle}\triangleq\arccos\left(\frac{\langle\boldsymbol{b}^{\langle t\rangle},\boldsymbol{\theta}^{\star}\rangle}{\|\boldsymbol{b}^{\langle t\rangle}\|\|\boldsymbol{\theta}^{\star}\|}\right)$ is non-increasing in terms of $t$.

$\boldsymbol{a}^{\langle t\rangle}$ is in the same direction as $\boldsymbol{b}^{\langle t\rangle}$ for all $t\geq 1$.

where $\Gamma$ and $P$ are defined in (33) and (31). Hence, the goal of the rest of the proof is to show that:

The main idea of this part is as follows. First note that

Hence, intuitively speaking we can argue that there exists a neighborhood of $x_{b}=0$ on which the derivative is always larger than $0.5$. Hence, when $\|\boldsymbol{b}^{\langle t\rangle}\|$ belongs to this neighborhood, $\|\boldsymbol{b}^{\langle t+1\rangle}\|$ is larger than $\|\boldsymbol{b}^{\langle t\rangle}\|$ and cannot go to zero. Next lemma justifies this claim.

For $\theta^{\star}_{\langle 0\rangle,1}>0$ there exists a value $\delta_{b}$ only depending on $c_{U,1}$, $\theta^{\star}_{\langle 0\rangle,1}$ and $\|\boldsymbol{\theta}^{\star}\|$ such that

where $\xi\in[0,\|\boldsymbol{b}^{\langle t\rangle}\|]$ and to obtain the last inequality we used Lemma 14 and the fact that $\|\boldsymbol{b}^{\langle t\rangle}\|\leq\delta_{b}$.

So far we have proved that if $\|\boldsymbol{b}^{\langle t\rangle}\|\leq\delta_{b}$, then $\|\boldsymbol{b}^{\langle t+1\rangle}\|\geq\|\boldsymbol{b}^{\langle t\rangle}\|$. But, we have not ruled out the possibility of the situation in which $\|\boldsymbol{b}^{\langle t\rangle}\|\geq\delta_{b}$, but $\|\boldsymbol{b}^{\langle t+1\rangle}\|$ is close to zero. That requires a simple continuity argument. Note that since $\Gamma$ is a continuous function of all its variables, its infimum over a compact set is achieved at certain point. Since, the value of $\Gamma(x_{1},x_{b},x_{\theta})$ is only zero when $x_{b}=0$, we conclude that the infimum is not zero. Hence, we conclude that

Hence, we have if $\|\boldsymbol{b}^{\langle t\rangle}\|\geq\delta_{b}$, then

Therefore combining the result of $\|\boldsymbol{b}^{\langle t\rangle}\|\leq\delta_{b}$ and $\|\boldsymbol{b}^{\langle t\rangle}\|\geq\delta_{b}$, we know Lemma 10 holds.

A.5.3 Proof of Lemma 11

We consider three cases and deal with them separately: (i) $0<x_{a}<\theta$, (ii) $x_{a}\geq\theta$, (iii) $x_{a}=0$.

$0<x_{a}<\theta$: Let $x_{1}\triangleq\theta+x_{a}>\theta-x_{a}\triangleq x_{2}>0$. We first simplify the left hand side of the inequality. Our main goal in this section is to derive sharp upper bounds for $\Gamma(x_{a},x_{b},\theta)$ and $1-2P(x_{a},x_{b},\theta)$. We start with $\Gamma(x_{a},x_{b},\theta)$. Note that

where $F$ is defined in (36). Next, we find an upper bound for $\frac{1}{2}(F(x_{b},x_{1})+F(x_{b},x_{2}))$. Note that $\forall x_{b}\geq 0,x_{\theta}\geq 0$, we have

Therefore, if we plug in $x_{\theta}=x_{1}$ and $x_{\theta}=x_{2}$, we have

where the last inequality holds since $l(x)$ is an increasing function. This can be proved by taking the derivative of $l(x)$:

Now we obtain an upper bound for $1-2P(x_{a},x_{b},\theta)$. Note that,

where $K(x,b)\triangleq\int\frac{e^{yb}-e^{-yb}}{2(e^{yb}+e^{-yb})}\frac{1}{\sqrt{2\pi}}e^{-(y-x)^{2}/2}\operatorname{d\!}y$. The following lemma proved in the Appendix B.7 summarizes some of the nice properties of this function, which will be used later in our proof.

$K(x,b)$ is a concave, strictly increasing function of $x$. Furthermore, $K(0,x_{b})=0$.

Given (51) and (52) we can now prove the claimed upper bound in Lemma 11. We have

It is straightforward to use the concavity of $K(x,x_{b})$ in terms of $x$ and prove that the function $\frac{K(x_{1},x_{b})-K(x_{2},x_{b})}{x_{1}-x_{2}}$ is a decreasing function of $x_{2}$. Hence, it is maximized at $x_{2}=0$. Since $K(0,x_{b})=0$, proved in Lemma 15, we have

Our next step is to find an upper bound for $(l(x_{1})\frac{K(x_{1},x_{b})}{x_{1}}-\frac{1}{2})$. Note that

Finally to obtain an upper bound for $\frac{1}{x}l(x)(\frac{1}{2}-\Phi(-x))$ we use the following lemma:

Define $l(x)\triangleq x(1-2\Phi(-x))+2\phi(x)$, then for all $x>0$, we have

The proof of this lemma is presented in Appendix B.8. Using this lemma, we have

By continuity of the function $\frac{l(x)(\frac{1}{2}-\Phi(-x))}{x}$, we have

It is straightforward to prove that $\bar{\kappa}_{a}(\theta)$ is a continuous function of $\theta\in(0,\infty)$. Since $4P(x_{a},x_{b},\theta)(1-P(x_{a},x_{b},\theta))\leq 1$, we can bound (55) in the following way:

$x_{a}\geq\theta$: According to Lemma 4, $1-2P(x_{a},x_{b},\theta)\geq 0$. Together with Lemma 12 we have

Therefore, from (58) and mean value theorem, we have

Together with (57) and $P(x_{a},x_{b},\theta))\leq\frac{1}{2}$, we have

$x_{a}=0$: It is straightforward to prove that $P(0,x_{b},\theta)=\frac{1}{2}$. Hence,

Combining Case (i), (ii), (iii), we conclude that if we define

A.6 Proof of Theorem 4

It is straightforward to use Theorem 3 and show that for every $\delta_{a}>0$, there exists a value of $T_{\delta_{a}}$ such that for every $t>T_{\delta_{a}}$, $\|\boldsymbol{a}^{\langle t\rangle}\|\leq\delta_{a}$. For the moment suppose that the following claim is true: there exists $\delta_{a}>0,\kappa_{b},c_{b}$ only depending on $\|\boldsymbol{\theta}^{\star}\|$, $|\theta^{\star}_{\langle 0\rangle,1}|$ and the initialization $\{\|\boldsymbol{a}^{\langle 0\rangle}\|,\|\boldsymbol{b}^{\langle 0\rangle}\|\}$, such that if $\|\boldsymbol{a}^{\langle t\rangle}\|\leq\delta_{a}$ for some $t$, then the next iteration $\boldsymbol{b}^{\langle t+1\rangle}$ satisfies the following equation:

If we combine this claim with the result of Theorem 3, we obtain Theorem 4. Hence, the problem reduces to proving the above claim.

Note that in Lemma 9, Lemma 10 and Lemma 8, we have

Therefore, it is again straightforward to see that the following lemma implies our claim:

where $\delta_{a},\kappa_{b}$ and $c_{b}$ are functions of only $U_{a},L_{b},U_{b},L_{\theta},\|\boldsymbol{\theta}^{\star}\|$.

Our strategy of proving this lemma is to prove the following two claims for the first two coordinates:

There exists $\kappa^{\prime}_{b}\in(0,1)$ and $\delta_{a}>0$ such that if $\|\boldsymbol{a}^{\langle t\rangle}\|\leq\delta_{a}$, then

We will then combine the above two claims to obtain Lemma 17.

where $\kappa_{s}$ only depends on $U_{a},L_{b},U_{b},L_{\theta}$ and $\|\boldsymbol{\theta}^{\star}\|$. Hence,

To see the definitions of $P,\Gamma,$ and $F$ you may refer to Appendix A.4. Hence, we have

Obtain an upper bound for $|F(\|\boldsymbol{b}^{\langle t\rangle}\|,x_{\theta})-F(\|\boldsymbol{b}^{\langle t\rangle}\|,\theta^{\star}_{\langle t\rangle,1})|$ for all $\theta^{\star}_{\langle t\rangle,1}\in[L_{\theta},\|\boldsymbol{\theta}^{\star}\|]$ and $|x_{\theta}-\theta^{\star}_{\langle t\rangle,1}|\leq L_{\theta}$.

Obtain an upper bound for $|F(\|\boldsymbol{b}^{\langle t\rangle}\|,\theta^{\star}_{\langle t\rangle,1})-\theta^{\star}_{\langle t\rangle,1}|$ for all $\theta^{\star}_{\langle t\rangle,1}\in[L_{\theta},\|\boldsymbol{\theta}^{\star}\|]$ and $\|\boldsymbol{b}^{\langle t\rangle}\|\in[L_{b},U_{b}]$

We summarize our strategy for bounding each of these terms below:

Next we show that $\left|\frac{\partial P(x_{a},\|\boldsymbol{b}^{\langle t\rangle}\|,\theta^{\star}_{\langle t\rangle,1}))}{\partial x_{a}}|_{x_{a}=0}\right|$ is a decreasing function of $\theta^{\star}_{\langle t\rangle,1}$ and hence can be upper bounded by $\left|\frac{\partial P(x_{a},\|\boldsymbol{b}^{\langle t\rangle}\|,0))}{\partial x_{a}}|_{x_{a}=0}\right|$:

Our next goal is to show that there exists $\delta_{1}>0$ is a function of only $L_{b},U_{b},L_{\theta},\|\boldsymbol{\theta}^{\star}\|$ such that

This is a simple proof by contradiction. Since we have already done similar arguments in the proof of Lemma 14, for the sake of brevity we skip this argument. By combining (64) and (67) we conclude:

Upper bound for $|F(\|\boldsymbol{b}^{\langle t\rangle}\|,x_{\theta})-F(\|\boldsymbol{b}^{\langle t\rangle}\|,\theta^{\star}_{\langle t\rangle,1})|$: Again by employing the mean value theorem, we conclude that we have to bound $\frac{\partial F(\|\boldsymbol{b}^{\langle t\rangle}\|,x_{\theta})}{\partial x_{\theta}}$ in a neighborhood of $x_{\theta}=\theta^{\star}_{\langle t\rangle,1}$ for all $\|\boldsymbol{b}^{\langle t\rangle}\|\in[L_{b},U_{b}],\theta^{\star}_{\langle t\rangle,1}\in[L_{\theta},\|\boldsymbol{\theta}^{\star}\|]$. Note that, $\forall x_{\theta}\geq 0$

where to obtain Inequality (a) we used integration by parts and also the fact that $\frac{e^{y\|\boldsymbol{b}^{\langle t\rangle}\|}-e^{-y\|\boldsymbol{b}^{\langle t\rangle}\|}}{e^{y\|\boldsymbol{b}^{\langle t\rangle}\|}+e^{-y\|\boldsymbol{b}^{\langle t\rangle}\|}}<1$. To see why (b) holds, one may check (65). By employing (66), we then conclude that

Therefore, using mean value theorem, we have $\forall|x_{\theta}-\theta^{\star}_{\langle t\rangle,1}|\leq L_{\theta},\theta^{\star}_{\langle t\rangle,1}\in[L_{\theta},\|\boldsymbol{\theta}^{\star}\|]$,

Upper bound for $|F(\|\boldsymbol{b}^{\langle t\rangle}\|,\theta^{\star}_{\langle t\rangle,1})-\theta^{\star}_{\langle t\rangle,1}|$:

Because the proof of this part has many algebraic steps we postpone it to the Appendix B.10.

Given $x_{b}\in[L_{b},U_{b}],x_{\theta}\in[L_{\theta},\|\boldsymbol{\theta}^{\star}\|]$ where $0<L_{b}\leq L_{\theta}\leq\|\boldsymbol{\theta}^{\star}\|\leq U_{b}<\infty$, there exists $\kappa_{b}^{\prime\prime}\in(0,1)$ is a function of only $L_{b},U_{b},L_{\theta},\|\boldsymbol{\theta}^{\star}\|$ such that

Let $\epsilon_{p}=\min\{\frac{1-\kappa_{b}^{\prime\prime}}{2\kappa_{b}^{\prime\prime}},1\}$ (This choice will become clear later in the proof). Using contradiction arguments similar to the ones employed in the proof of Lemma 14, it is straight forward to see that there exists $\delta_{2}>0$ only depending on $L_{b},U_{b},L_{\theta},\|\boldsymbol{\theta}^{\star}\|$ such that

So far we have proved in (61) and (2) and the following bounds:

Let $\kappa_{b}=\max\{\kappa_{s},\kappa_{b}^{\prime}\}\in(0,1)$ and $c_{b}^{\prime}=16\|\boldsymbol{\theta}^{\star}\|+6$. Then, we conclude that

Setting $c_{b}=(c_{b}^{\prime})^{2}+2c_{b}^{\prime}U_{b}+2c_{b}^{\prime}\|\boldsymbol{\theta}^{\star}\|$ completes the proof of Lemma 17.

A.7 Proof of Theorem 1

To prove this result we will use some of the results we have proved in the last few sections. We summarize them here.

In Section 1.2 we showed that to study the dynamics of Population EM for Model 1, it is sufficient to study

where $\mathsf{w}_{d}(\boldsymbol{y},\boldsymbol{\theta}^{\langle t\rangle})=\frac{\phi(\boldsymbol{y}-\boldsymbol{\theta}^{\langle t\rangle};I)}{\phi(\boldsymbol{y}-\boldsymbol{\theta}^{\langle t\rangle};I)+\phi(\boldsymbol{y}+\boldsymbol{\theta}^{\langle t\rangle};I)}$ and $\boldsymbol{Y}\sim\frac{1}{2}N(-\boldsymbol{\theta}^{\star},\boldsymbol{I}_{d})+\frac{1}{2}N(\boldsymbol{\theta}^{\star},\boldsymbol{I}_{d})$.

In Section 1.2 and A.2 we showed that to study the dynamics of Population EM for Model 2, it is sufficient to study

where $Y\sim\frac{1}{2}N(-\boldsymbol{\theta}^{\star},\boldsymbol{I}_{d})+\frac{1}{2}N(\boldsymbol{\theta}^{\star},\boldsymbol{I}_{d})$.

According to Lemma 2, (72) reduces to (71), if $\boldsymbol{a}^{\langle 0\rangle}=\boldsymbol{0}$. In other words, if we set $\boldsymbol{a}^{\langle 0\rangle}=\boldsymbol{0}$, then $\boldsymbol{a}^{\langle t\rangle}=\boldsymbol{0}$ and $\boldsymbol{b}^{\langle t\rangle}=\boldsymbol{\theta}^{\langle t\rangle}$. This in turn implies that if we analyze the convergence dynamics of (72), we immediately obtain the convergence of (71) by setting $\boldsymbol{a}^{\langle 0\rangle}=\boldsymbol{0}$.

If $\beta^{\langle t\rangle}$ denotes the angle between $\boldsymbol{\theta}^{\star}$ and $\boldsymbol{b}^{\langle t\rangle}$, then we proved in Appendix A.5 that for (72) we have

The same is true for $\boldsymbol{a}^{\langle 0\rangle}=\boldsymbol{0}$ initialization.

According to Lemma 9 and Lemma 10, we have $\|\boldsymbol{b}^{\langle t\rangle}\|\in[c_{L,1},c_{U,3}]$. According to Lemma 8, we have $\theta^{\star}_{\langle t\rangle,1}\in[\theta^{\star}_{\langle 0\rangle,1},\|\boldsymbol{\theta}^{\star}\|]$. The same is true for $\boldsymbol{a}^{\langle 0\rangle}=\boldsymbol{0}$ initialization.

Note that we can employ Theorem 4 to claim that (by setting $\boldsymbol{a}^{\langle t\rangle}=\boldsymbol{0}$) if $\langle\boldsymbol{b}^{\langle t\rangle},\boldsymbol{\theta}^{\star}\rangle>0$, then for the symmetric case, there exists $T_{0}$ such that for every $t>T_{0}$,

where the last equality is due to the fact that $P(0,\|\boldsymbol{b}^{\langle t\rangle}\|,\theta^{\star}_{\langle t\rangle,1})=\frac{1}{2}$. Also, according to (60) we have

Hence, let $U_{a}=0,L_{b}=c_{L,1},U_{b}=c_{L,3}$ and $L_{\theta}=\theta^{\star}_{\langle 0\rangle,1}$, we conclude that

Similarly, employing (A.4) for the first coordinate and using the fact that $P(0,\|\boldsymbol{b}^{\langle t\rangle}\|,\theta^{\star}_{\langle t\rangle,1})=\frac{1}{2}$, we obtain

Note that the last equality is due to (37). According to Lemma 18, we know that there exists $\kappa_{b}^{\prime\prime}\in(0,1)$ which is a function of only $L_{b},U_{b},L_{\theta},\|\boldsymbol{\theta}^{\star}\|$ such that

Let $L_{b}=c_{L,1},U_{b}=c_{L,3}$ and $L_{\theta}=\theta^{\star}_{\langle 0\rangle,1}$. Combining (74), (75) and (76) completes the proof.

A.8 Proof of Theorem 5

The proof for the case $\langle\boldsymbol{b}^{\langle 0\rangle},\boldsymbol{\theta}^{\star}\rangle=0$ is very different from the proof of the case $\langle\boldsymbol{b}^{\langle 0\rangle},\boldsymbol{\theta}^{\star}\rangle\neq 0$. It seems that the convergence of the algorithm to its stationary point may not be geometric and hence proof ideas we developed for the case $\langle\boldsymbol{b}^{\langle 0\rangle},\boldsymbol{\theta}^{\star}\rangle\neq 0$ are not applicable here. Hence, we prove Theorem 4 using the following strategy:

We first characterize all the stationary points of Population EM. Let $(\boldsymbol{a},\boldsymbol{b})$ denote the stationary points and we show that $\boldsymbol{a}=\boldsymbol{0}$ and $\boldsymbol{b}\in\{-\boldsymbol{\theta}^{\star},\boldsymbol{0},\boldsymbol{\theta}^{\star}\}$. This is discussed in Appendix A.8.2.

We then show that any accumulation point of $\{(\boldsymbol{a}^{\langle t\rangle},\boldsymbol{b}^{\langle t\rangle})\}$ is one of the stationary points. Let $(\boldsymbol{a}^{\infty},\boldsymbol{b}^{\infty})$ denote any accumulation point. This is discussed in (i) in Appendix A.8.3.

We show that if $\langle\boldsymbol{b}^{\langle 0\rangle},\boldsymbol{\theta}^{\star}\rangle=0$, $\boldsymbol{b}^{\infty}$ can not converge to $-\boldsymbol{\theta}^{\star}$ or $\boldsymbol{\theta}^{\star}$. Hence, the algorithm has to converge to $\boldsymbol{0}$. Since $\boldsymbol{a}^{\infty}=\boldsymbol{0}$ for all stationary points, we have $\{\boldsymbol{a}^{\langle t\rangle},\boldsymbol{b}^{\langle t\rangle}\}$ converges to $(\boldsymbol{0},\boldsymbol{0})$. This is discussed in (ii) in Appendix A.8.3

A.8.2 Characterizing the Fixed Points of Population EM

First note that if we write the iterations of Population EM in terms of $\boldsymbol{a}^{\langle t\rangle}$ and $\boldsymbol{b}^{\langle t\rangle}$ we obtain

If $(\boldsymbol{\gamma}^{\langle t\rangle},\mathsf{p}^{\langle t\rangle},\boldsymbol{a}^{\langle t\rangle},\boldsymbol{b}^{\langle t\rangle})$ converges to $(\boldsymbol{\gamma},\mathsf{p},\boldsymbol{a},\boldsymbol{b})$, then it is straightforward to show that

The only feasible solution for $a$ is zero.

We then set $a=0$ and show that the only possible solutions for $b$ are $-\theta^{*},0,\theta^{*}$.

We should prove the above two by considering the following four different cases: (1) $a\geq 0,b\geq 0$, (2) $a\geq 0,b\leq 0$, (3) $a\leq 0,b\geq 0$, (4) $a\leq 0,b\leq 0$. Since the four cases are similar we focus on the first case only, i.e., $a\geq 0,b\geq 0$. To prove that the only possible solution of $a$ is zero, note that (77) can be written as

where $\kappa_{a}<1$. Note that Inequality (1) is a result of Lemma 11. Note that (81) implies that $a$ must be zero.

The only remaining step is to examine the solutions for $b$. It is straightforward to prove that $P(0,b,\theta^{*})=\frac{1}{2}$. Hence, we can simplify (78) to

where the last equality is due to (37). The following lemma enables us to characterize the solutions of (82).

$F(x_{b},x_{\theta})$ is a concave function of $x_{b}\geq 0$. Furthermore, we have the following: (i) $F(0,x_{\theta})=0$, (ii) $F(x_{\theta},x_{\theta})=x_{\theta}$.

The proof of this lemma is presented in the Appendix B.9. It is straightforward to use the above properties and show that $F(x_{b},x_{\theta})$ has in fact the shape that is exhibited in Figure 1, which proves our claim in the one dimensional setting.

First, it is straightforward to employ (83) and (84) and confirm that $\forall i\geq 2$ we have

where the last inequality is due to Lemma 11. We know that $\kappa_{a}<1$. Therefore we have $\boldsymbol{a}=\boldsymbol{0}$ and

A.8.3 Proof of Convergence for Population EM

We can break the proof into the following steps. Let $\{\boldsymbol{a}^{\langle t\rangle},\boldsymbol{b}^{\langle t\rangle}\}_{t=1}^{\infty}$ denote all the estimates of the Population EM algorithm.

We first prove that every accumulation point of $\{\boldsymbol{a}^{\langle t\rangle},\boldsymbol{b}^{\langle t\rangle}\}_{t=1}^{\infty}$ satisfies the fixed point equations:

where $\boldsymbol{Y}\sim\frac{1}{2}N(-\boldsymbol{\theta}^{\star},I)+\frac{1}{2}N(\boldsymbol{\theta}^{\star},I)$. This proof is presented in Appendix B.11.

We have already proved that these fixed point equations only have the following solutions : $\boldsymbol{a}=\boldsymbol{0}$ and $\boldsymbol{b}\in\{-\boldsymbol{\theta}^{\star},\boldsymbol{0},\boldsymbol{\theta}^{\star}\}$. We proved in Lemma 4 that $\operatorname{sgn}(\langle\boldsymbol{b}^{\langle t\rangle},\boldsymbol{\theta}^{\star}\rangle)=\operatorname{sgn}(\langle\boldsymbol{b}^{\langle t+1\rangle},\boldsymbol{\theta}^{\star}\rangle)$. Hence, we conclude that $\langle\boldsymbol{b}^{\langle t\rangle},\boldsymbol{\theta}^{\star}\rangle=0$ for every $t$. The only possible fixed point is hence $(\boldsymbol{0},\boldsymbol{0})$. In summary, in the first step we prove that it only has one accumulation point, that is $(\boldsymbol{0},\boldsymbol{0})$.

Next we prove that $\{\boldsymbol{a}^{\langle t\rangle},\boldsymbol{b}^{\langle t\rangle}\}_{t=1}^{\infty}$ is a convergent sequence. Suppose that the sequence does not converge to $(\boldsymbol{0},\boldsymbol{0})$, then there exists an $\epsilon$ such that for every $T$, there exists a $t>T$ such that

We construct a subsequence of our sequence in the following way: Set $T=1$ and pick $t_{1}>T$ such that $\|(\boldsymbol{a}^{\langle t_{1}\rangle},\boldsymbol{b}^{\langle t_{1}\rangle})\|_{2}>\epsilon$. Now, set $T=t_{1}+1$, and pick $t_{2}>T$ such that $\|(\boldsymbol{a}^{\langle t_{2}\rangle},\boldsymbol{b}^{\langle t_{2}\rangle})\|_{2}>\epsilon$. Continue the process until we construct a sequence $\{(\boldsymbol{a}^{\langle t_{n}\rangle},\boldsymbol{b}^{\langle t_{n}\rangle})\}_{n=1}^{\infty}$. According to Lemma 9 $\{(\boldsymbol{a}^{\langle t_{n}\rangle},\boldsymbol{b}^{\langle t_{n}\rangle})\}_{n=1}^{\infty}$ is in a compact set and has a convergent subsequence. But according to part (i) the converging subsequence of this sequence must converge to $(\boldsymbol{0},\boldsymbol{0})$ which is in contradiction with the construction of the sequence $\{(\boldsymbol{a}^{\langle t_{n}\rangle},\boldsymbol{b}^{\langle t_{n}\rangle})\}_{n=1}^{\infty}$. Hence $\{\boldsymbol{a}^{\langle t\rangle},\boldsymbol{b}^{\langle t\rangle}\}_{t=1}^{\infty}$ must be a convergent sequence and converges to $(\boldsymbol{0},\boldsymbol{0})$

A.9 Proof of Theorem 6

Let $\hat{\boldsymbol{a}}^{\langle t\rangle}=\frac{\hat{\boldsymbol{\mu}}_{1}^{\langle t\rangle}+\hat{\boldsymbol{\mu}}_{2}^{\langle t\rangle}}{2}$ and $\hat{\boldsymbol{b}}^{\langle t\rangle}=\frac{\hat{\boldsymbol{\mu}}_{2}^{\langle t\rangle}-\hat{\boldsymbol{\mu}}_{1}^{\langle t\rangle}}{2}$. Then the iteration functions based on $(\hat{\boldsymbol{a}}^{\langle t\rangle},\hat{\boldsymbol{b}}^{\langle t\rangle})$ are the following:

Therefore $\hat{\boldsymbol{q}}^{\langle t\rangle}$ and $\hat{\mathsf{p}}^{\langle t\rangle}$ are the empirical versions of $\boldsymbol{\gamma}^{\langle t\rangle}$ and $\mathsf{p}^{\langle t\rangle}$ respectively. Our first goal is, for each $i\in\{1,2\}$, to compare the Population EM sequence $(\boldsymbol{\mu}_{i}^{\langle t\rangle})_{t\geq 0}$ to the Sample-based EM sequence $(\hat{\boldsymbol{\mu}}_{i}^{\langle t\rangle})_{t\geq 0}$, provided that the initial values $\boldsymbol{\mu}_{i}^{\langle 0\rangle}$ and $\hat{\boldsymbol{\mu}}_{i}^{\langle 0\rangle}$ are the same. We prove that

We prove by induction. For $t=0$, it is clear that (91) holds because both Population EM and Sample-based EM start with the same initialization. For $t=1$, by Weak Large Law Numbers (WLLN), we have

Since $\mathsf{p}^{\langle 1\rangle}\in(0,1)$, by employing the continuous mapping theorem, we have

Therefore (91) holds for $t=1$. Now we assume that (91) holds for $t\geq 1$, and our goal is to prove it for $t+1$. Note that