{'fraction_non_alphanumeric': 0.05158221302998966, 'fraction_numerical': 0.01956566701137539, 'mean_word_length': 3.8342331533693264, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 24, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Lower Bounds on the Total Variation Distance Between Mixtures of Two Gaussians

Mixtures of high dimensional Gaussian distributions have been studied extensively in statistics and learning theory. While the total variation distance appears naturally in the sample complexity of distribution learning, it is analytically difficult to obtain tight lower bounds for mixtures. Exploiting a connection between total variation distance and the characteristic function of the mixture, we provide fairly tight functional approximations. This enables us to derive new lower bounds on the total variation distance between pairs of two-component Gaussian mixtures that have a shared covariance matrix.


Introduction
Let N (µ, Σ) denote the d-dimensional Gaussian distribution with mean µ ∈ R d and positive definite covariance matrix Σ ∈ R d×d . A k-component mixture of d-dimensional Gaussian distributions is a distribution of the form f = k i=1 w i · N (µ i , Σ i ). Such a mixture is defined by k triples where w i ∈ R + with k i=1 w i = 1 are the mixing weights, µ i ∈ R d are the means, and Σ i ∈ R d×d are the covariance matrices. Mixtures of Gaussian distributions have been studied intensively due to their broad applicability to statistical problems [2,10,11,21,22,28,29,31,32].
The variational distance (a.k.a., the total variation (TV) distance) between two distributions f, f with same sample space Ω and sigma algebra S is defined as follows: The minimum pairwise TV distance of a class of distributions appears naturally in the expressions of statistical error rates related to the class, most notably in the Neyman-Pearson approach to hypothesis testing [25,30], as well as in the sample complexity results in density estimation [13]. In particular, in these applications, a lower bound on the total variation distance between two candidate distributions is an essential part of the algorithm design and analysis.
Tight bounds are known for the total variation distance between single Gaussians; however, they have only recently been derived as closed form functions of the distribution parameters [5,14]. The functional form of the TV distance bound is often much more useful in practice because it can be directly evaluated based on only the means and covariances of the distribution. This has opened up the door for new applications to a variety of areas, such as analyzing ReLU networks [34], distribution learning [3,4], private distribution testing [7,8], and average-case reductions [6].
Inspired by the wealth of applications for single Gaussian total variation bounds, we investigate deriving analogous results for mixtures with two components. As our main contribution, we complement the single Gaussian results and derive tight lower bounds for pairs of mixtures containing two equally weighted Gaussians with shared variance. We also present our results in a closed form in terms of the gap between the component means and certain statistics of the covariance matrix. The total variation distance between two distributions can be upper bounded by other distances/divergences (e.g., KL divergence, Hellinger distance) that are easier to analyze. In contrast, it is a key challenge to develop ways to lower bound the total variation distance. The shared variance case is important because it presents some of the key difficulties in parameter estimation and is widely studied [12,35]. For example, mean estimation with shared variance serves as a model for the sensor location estimation problem in wireless or physical networks [23,26,33].
The lower bound on total variation distance can be applicable in several contexts. In binary hypothesis testing, it gives a sufficient condition to bound from above the total probability of error of the best test [28]. Hypothesis testing in Gaussian mixture models has been of interest, cf. [1,9]. Furthermore, parameter learning in Gaussian mixture models is a core topic in density estimation [13]. Our bound can provide a sufficient condition on the learnability of the class of two component Gaussian mixtures in terms of the precision of parameter recovery and gap between the component of mixtures. Indeed, performance of various density estimation techniques, such as the Scheffé estimator or the minimum distance estimator, depends crucially on a computable lower bound in total variation distance between candidate distributions [13]. Furthermore, our lower bound implies that, for the class of distributions we consider, if a pair of distributions is close in variational distance, then the distributions have close parameters. This type of implication is integral to arguments in outlier-robust moment estimation algorithms and clustering [4,20].
We obtain lower bounds on the total variation distance by examining the characteristic function of the mixture. This connection has been previously used in [24] in the context of mixture learning, but it required strict assumptions on the mixtures having discrete parameter values, i.e., Gaussians with means that belong to a scaled integer lattice. It is not clear how to generalize their techniques to noninteger means. As a first step towards that generalization, we analyze unrestricted two-component one-dimensional mixtures by applying a novel and more direct analysis of the characteristic function. Then, in the high-dimensional setting, we obtain a new TV distance lower bound by projecting and then using our one-dimensional result. By carefully choosing and analyzing the one-dimensional projection (which depends on the mixtures), we exhibit nearly-tight bounds on the TV distance of d-dimensional mixtures for any d ≥ 1.

Results
Let F be the set of all d-dimensional, two-component, equally weighted mixtures where Σ ∈ R d×d is a positive definite matrix. When d = 1, we use the notation f µ 0 ,µ 1 ∈ F and simply denote the variance as σ 2 ∈ R. Our main result is the following nearly-tight lower bound on the TV distance between pairs of d-dimensional two-component mixtures with shared covariance.
If v 1 2 ≥ min( v 2 2 , v 3 2 )/2 and λ Σ,U = Ω(||v 1 || 2 ), then and otherwise, we have that Notice from the definitions of v 1 , v 2 , v 3 that U is contained within the subspace spanned by the unknown mean vectors µ 0 , µ 1 , µ 0 , µ 1 . Furthermore, λ Σ,U as defined in Theorem 1 can always be bounded from above by the largest eigenvalue of the matrix Σ, and as we will show in Section 1.3, this upper bound characterizes the TV distance between mixtures in several instances.

Related Work
Let I denote the d-dimensional identity matrix. Statistical distances between a pair of k-component with shared, known component covariance I have been studied in [15,35]. For a k-component Gaussian mixture We denote the Kullback-Leibler divergence, Squared Hellinger divergence, and χ 2 -divergence of f, f by ||f − f || KL , ||f − f || H 2 , and ||f − f || χ 2 respectively. We write ||M || F to denote the Frobenius norm of the matrix M . Prior work shows the following.
This bound alone does not give a guarantee for the TV distance. However it is well-known that, We can use this in conjunction with Theorem 3 to get a lower bound on TV distance, but it is suboptimal for many canonical instances. For example, consider one-dimensional Gaussian mixtures Using Eq. (1) and Theorem 3, we have that ||f − f || TV = Ω(u 4 ). On the other hand, by using our result (Theorem 2), we obtain the improved bound ||f − f || TV = Ω(u 2 ). The improvement becomes more significant as u becomes smaller. Also, the prior result in Theorem 3 assumes that the means of the two mixtures f, f are contained in a ball of constant radius, limiting its applicability. The TV distance between Gaussian mixtures with two components when d = 1 has been recently studied in the context of parameter estimation [16,19,27,18]. The TV distance guarantees in these papers are more general, as they do not need the component covariances to be same. However, the results and their proofs are tailored towards the case when both the mixtures have zero mean. They do not apply when considering the TV distance between two mixtures with distinct means. Theorems 1 and 2 hold for all mixtures with shared component variances, without assumptions on the means.
Further, our bound can be tighter than these prior results, even in the case when the mixtures have zero mean. Consider again the pair of mixtures f, f defined in Eq. (2) above. In [27,19], the authors show that ||f − f || TV = Ω(u 4 ); see, e.g., Eq. (2.7) in [27]. Notice that this is the same bound that can be recovered from Theorem 3, and as we mentioned before, this bound is loose. By using Theorem 2, we obtain the improved bound ||f − f || TV = Ω(u 2 ). Now consider a more general pair of mixtures, where for u, v ≥ 0, we define In [16] (see the proof of Lemma G.1 part (b)), the authors show that ||f − f || TV = Ω((u − v) 2 ). Notice that for the previous example in Eq. (2) with v = 2u, the result in [16] leads to the bound ||f − f || TV = Ω(u 2 ), which is the same bound that can be obtained from Theorem 2. However, for any small ε > 0, by setting v = u + ε, we see that the bound in [16] reduces to ||f − f || TV = Ω(ε 2 ).
On the other hand, by using Theorem 2, we obtain ||f − f || TV = Ω(u · ε + ε 2 ). Whenever u ε, our result provides a much larger and tighter lower bound. On the other hand, whenever u < ε, our bound coincides with that of [16].

Tightness of the TV distance bound
Our bounds on the TV distance are tight up to constant factors. For example, let u ∈ R d be a d-dimensional vector satisfying ||u|| 2 < 1. Consider the mixtures f = 0.5N (u, I) + 0.5N (−u, I) and f = 0.5N (2u, I) + 0.5N (−2u, I). Considering the notation of Theorem 1, we have v 1 = 2u and v 2 = u, and the first bound in the theorem implies that ||f − f || TV ≥ Ω(||u|| 2 2 ). On the other hand, we use the inequality ||f − f || TV ≤ 2 ||f − f || H 2 in conjunction with Theorem 3. In the notation of Theorem 3, note that M 1 (f ) − M 1 (f ) = 0, and we can upper bound the max over ∈ {2, 3} by the sum of the two terms to say that Since ||u|| 2 < 1, we see that ||u|| 2 2 is the dominating term on the RHS, and ||f − f || TV = Θ(||u|| 2 2 ). As a result, our TV distance bound in Theorem 1 is tight as a function of the means for this example.
Our bounds are tight in other instances too. Consider the second parts of Theorems 1 and 2 when samples are pre-multiplied with Σ −1/2 . Here, we can use the triangle inequality to derive a simple upper bound on the TV distance, Then, we can use tight bounds on the TV distance between single Gaussians. In the one-dimensional setting, Theorem 1.3 in [14] shows that In the high dimensional setting, Theorem 1.2 in [14] shows that recalling v 2 and v 3 from the definitions in Theorem 1 and letting λ min (Σ) be the minimum eigenvalue of Σ. Again by the invariance property, TV distance remains the same if the samples are premultiplied by Σ −1/2 . With this transformation, the component co-variance matrix is I and It follows that the second parts of Theorems 1 and 2 are tight up to constants when samples are pre-multiplied with Σ −1/2 . On the other hand, when comparing with the Hellinger distance upper bound of [15], our lower bound on the TV distance is not tight in the following case.
In contrast, Theorem 1 only gives a lower bound of Ω( u 2 2 ), which can be much smaller than u 2 . It would be an interesting open direction to derive tight bounds on this instance. We do not know if this is an inherent limitation of either of the bounds, and it may be possible to extend our results to capture the u 2 term, or tighten the upper bound.

Preliminaries
We use Ω(·), O(·), and Θ(·) to hide absolute constants. For vectors u, v ∈ R d , we let u, v denote the Euclidean inner product. We use the characteristic function of a distribution, defined below.
. The characteristic function can be used to bound the TV distance with the following lemma.

Lemma 2 ([24]
). For distributions f, f on a shared sample space Ω ⊆ R, Organization. The rest of the paper is organized as follows. In Section 2, we give a brief high level overview of our results. In Section 3, we provide the main parts of the proof of our TV distance result for one dimensional mixtures, which is based on elementary complex analysis. Subsequently, in Section 4, we provide the proof of the TV distance lower bound in the high dimensional case.

Technical Overview
In one dimension, we lower bound the TV distance as follows. For . The latter case corresponds to when either both means from one mixture are smaller than another, i.e., µ 0 ≤ µ 1 ≤ µ 0 , µ 1 , or the mixtures' means are interlaced, i.e., We use Lemma 2 to lower bound the TV distance between mixtures f µ 0 ,µ 1 , f µ 0 ,µ 1 ∈ F by the modulus of a complex analytic function: Let is not too small. Then, it remains to bound |h(t)| at the chosen value of t. In some cases, we will have to choose the constant c very carefully, as terms in h(t) can cancel out due to the periodicity of the complex exponential function. For instance, if It is reasonable to wonder whether there is a simple, global way to lower bound Eq. (4). We could reparameterize the function h(t) as the complex function g(z) = z µ 0 + z µ 1 − z µ 0 − z µ 1 , where z = e it , then study |g(z)|, for z in the disc with center 0 and radius 1 in the complex plane. However, we are unaware of a global way to bound |g(z)| here due to the fact that (i) g(z) is not analytic at 0 when the means are non-integral and (ii) there is not a clear, large lower bound for g(z) anywhere inside the unit disc. These two facts obstruct the use of either the Maximum Modulus Principle or tools from harmonic measure to obtain lower bounds. Instead, we use a series of lemmas to handle the different ways that |h(t)| can behave. The techniques include basic complex analysis and Taylor series approximations of order at most three.
Let f t µ 0 ,µ 1 be the distribution of the samples obtained according to f µ 0 ,µ 1 and projected onto the direction t ∈ R d . We have (see Lemma 6 for a proof) By the data processing inequality for f -divergences (see Theorem 5.2 in [13]), we have TV . Using our lower bound on the TV distance between onedimensional mixtures (Theorem 2), we obtain a lower bound on f µ 0 ,µ 1 − f µ 0 ,µ 1 TV by choosing t ∈ R d carefully. This leads to Theorem 1.

Lower Bound on TV Distance of 1-Dimensional Mixtures
Consider distinct Gaussian mixtures f µ 0 ,µ 1 , f µ 0 ,µ 1 ∈ F. Without loss of generality we will also let µ 0 ≤ min(µ 1 , µ 0 , µ 1 ) be the smallest unknown parameter, and let µ 1 ≥ µ 0 . We maintain these assumptions throughout this section, and we will prove Theorem 2. Figure 1: Layout of the means for Theorem 2. The means can be ordered in different ways, which affects the analysis of lower bounding |e itµ 0 + e itµ 1 − e itµ 0 − e itµ 1 | in Lemma 3. For a fixed t, the order affects (i) whether the real or imaginary part of e itµ 0 + e itµ 1 − e itµ 0 − e itµ 1 has large modulus and (ii) whether the terms from µ 0 and µ 1 or µ 0 and µ 1 dominate.
Eq. (4) implies that we can lower bound ||f µ 0 ,µ 1 − f µ 0 ,µ 1 || TV by the modulus of a complex analytic function with parameter t. Then, we can optimize the bound by choosing t = Θ(1/σ) and lower bounding the term in the absolute value signs.
See Figure 1 for an illustration of the different ways that the means can be ordered. The lemma follows from straightforward calculations that only use Taylor series approximations, trigonometric identities, and basic facts about complex numbers. We include the proof in Appendix A.
Recall that we will choose t = Θ(1/σ) to cancel the exponential term in Eq. (4). Therefore, Lemma 3 handles the case when all the means are within some interval of size Θ(σ).
Next, we prove that when the separation between the mixtures is substantially fair apart-when either |µ 0 − µ 0 | or |µ 1 − µ 1 | is at least 2σ-we have a constant lower bound on the TV distance. Recall that it is without loss of generality to assume that µ 0 is the smallest parameter and µ 1 > µ 0 . A similar result as the following two lemmas has been observed previously (e.g., [17]) but we provide a simple and self-contained proof.
Proof. Assume that |µ 0 − µ 0 | ≥ 2σ, where the case |µ 1 − µ 1 | ≥ 2σ is analogous. Recall from the definition of TV distance that For a random variable X ∼ f µ 0 ,µ 1 , let E denote the event that we choose the component with mean µ 0 , i.e., if X denotes X conditioned on E, then we have X ∼ N (µ 0 , σ 2 ). Since the mixing weights are equal, we have Pr(E) = Pr(E c ) = 1/2, where E c is the complement of E. Therefore, Recall that µ 0 ≤ µ 0 , µ 0 ≤ µ 1 and |µ 0 − µ 0 | ≥ 2σ. Again, for a random variable Y ∼ f µ 0 ,µ 1 , let E denote the event that the component with mean µ 0 is chosen (and E c denotes µ 1 is chosen). Then, where in step (a), we used the fact that µ 0 − σ ≥ µ 0 + σ and µ 1 − σ ≥ µ 0 + σ; in step (b), we used the symmetry of Gaussian distributions; in step (c), we used the same analysis as in (5). By plugging this in the definition of TV distance, we have ≥ 0.137.
We defer the proof of Lemma 5 to Appendix A. Using Lemmas 3, 4, and 5, we prove Theorem 2.

Lower Bound on TV Distance of d -Dimensional Mixtures
We lower bound the TV distance of high-dimensional mixtures in F and prove Theorem 1. For any direction t ∈ R d , we denote the projection of the distributions f µ 0 ,µ 1 and f µ 0 ,µ 1 on t by f t µ 0 ,µ 1 and f t µ 0 ,µ 1 , respectively. The next lemma allows us to precisely define the projected mixtures.
Proof. A linear transformation of a multivariate Gaussian is also a Gaussian. For x ∼ N (µ 0 , Σ), we see that t, x ∼ N ( µ 0 , t , t T Σt) by a computation of the mean and variance. Similarly, for x ∼ N (µ 1 , Σ), we have t, x ∼ N ( µ 1 , t , t T Σt). Putting these together, the claim follows.
From Lemma 6, we can exactly define the one-dimensional mixtures By using the data processing inequality, or the fact that variational distance is non-increasing under all mappings (see, for instance, Theorem 5.2 in [13]), it follows that Let H be the set of permutations on {0, 1}. The following lemma has two cases based on whether the interval defined by one pair of mean's projections is contained in the interval defined by the other pair's projections.
Proof. The proof follows directly from Theorem 2. Note that in Theorem 2, we assumed the ordering of the means without loss of generality, i.e., µ 0 ≤ min(µ 1 , µ 0 , µ 1 ) and µ 0 < µ 1 . However, taking a minimum over the set of permutations in H allows us to restate the theorem in its full generality. Now we are ready to provide the proof of Theorem 1.

Proof of Theorem 1
Let We consider two cases below. Depending on the norm of v 1 , we modify our choice of projection direction. In the first case, we do not have a guarantee on the ordering of the means, so we use the first part of Lemma 7. In the second case, we can use the better bound in the second part of the lemma after arguing about the arrangement of the means.

Lemma 8.
For v 1 , v 2 , v 3 defined above, there exists a vector z ∈ R d such that ||z|| 2 ≤ 10, z belongs to the subspace spanned by v 1 , v 2 , v 3 , and | z, v | ≥ ||v|| 2 Proof. We use the probabilistic method. Let u 1 , u 2 , u 3 be orthonormal vectors forming a basis of the subspace spanned by v 1 , v 2 and v 3 ; hence, we can write the vectors v 1 , v 2 and v 3 as a linear combination of u 1 , u 2 , u 3 . Let us define a vector z randomly generated from the subspace spanned by v 1 , v 2 , v 3 as follows. Let p, q, r be independently sampled according to N (0, 1). Then, define z = pu 1 + qu 2 + ru 3 . By this construction, we have that z, v ∼ N (0, ||v|| 2 2 ) for all vectors v ∈ {v 1 , v 2 , v 3 }, and further, ||z|| 2 2 = p 2 + q 2 + r 2 . Hence, for any v ∈ {v 1 , v 2 , v 3 }, we have Also, we can bound the norm of z by bounding p, q, r. We see that Similarly, Pr(p < −5) ≤ e −12.5 /5. Applying the same calculations to q and r and taking a union bound, we must have that with positive probability ||z|| 2 ≤ p 2 + q 2 + r 2 ≤ √ 75 ≤ 10 and | z, v | ≥ ||v|| 2 /6 for all v ∈ {v 1 , v 2 , v 3 }, implying there exists a vector z that satisfies the claim.
For this case, we will use the first part of Lemma 7. Let z be the vector guaranteed by Lemma 8.
Recall that we defined λ Σ,U max u T Σu to be the maximum amount a unit norm vector u belonging to the span of the vectors v 1 , v 2 , v 3 is stretched by the matrix Σ. Note that λ Σ,U is also upper bounded by the maximum eigenvalue of Σ. Now, using the fact that ||z|| 2 ≤ 10 and √ z T Σz ≤ λ Σ,U ||z|| 2 ≤ 10 λ Σ,U , we obtain The part of Lemma 7 that we use depends on whether √ t T Σt = Ω max (| t, v 1 |) or not. However, the second part of the lemma is stronger and implies the first part. Therefore, we simply use the lower bound in the first part of the lemma, and we see that wherein step (a), we used the following facts (from definitions): and in step (b), we used Eq. (7) for each v ∈ {v 1 , v 2 , v 3 }.
Notice that we must have s v 2 , v 3 > 0 from the definition of s. Then we see that The first inequality follows the norm bound on v 1 for this case, the second inequality uses that the definition of v and s imply that the second term in the sum is non-negative, and the third inequality uses the same logic and the fact that s ∈ {−1, 1}.
We just showed that . This implies that the interval defined by one pair of projected means is not contained within the interval defined by the other pair of projected means. This means we can use the second part of Lemma 7. Furthermore, we also have t T Σt = 1. Finally, since ||v|| 2 ≤ 2, note that √ v T Σv ≤ 2 λ Σ,U . Using Lemma 7 with our choice of t, we see that = Ω min 1, min(||v 2 || 2 , ||v 3 || 2 ) λ Σ,U .

Conclusion and Open Questions
We demonstrated the use of complex analytic tools to prove new lower bounds on the total variation distance between any two Gaussian mixtures with two equally weighted components and shared component variance. For a pair of mixtures with shared component variance, we provide guarantees on the total variation distance as a function of the largest gap (among the two mixtures) between the component means. Although intuitive, such a characterization was missing despite a vast literature on the total variation distance between mixtures of Gaussians with two components. We also extended our results to high dimensions and showed an elegant way via characteristic functions to reduce the problem to the one-dimensional setting. Finally, we should also point out that our lower bounds hold for all pairs of Gaussian mixtures with shared component covariance matrix without any assumptions on the component means; this was not the case in the prior results, which either needed the means to be bounded or the means of both mixtures to be zero. The complex analytic tools in this work are elementary, and there is room for development. These tools may be helpful in proving bounds on statistical distance between more diverse distributions. For example, our analytic techniques do extend to mixtures of two Gaussians with shared covariance and certain non-equal mixing weights. To give a specific instance, for a mixture with weights c 0 and c 1 , we could replace Lemma 3 so the lower bound only gains an additional multiplicative factor of min{c 0 , c 1 } when µ 1 > µ 1 . We avoided stating our results in full generality of the mixing weights to not complicate our techniques and results. It would be useful and interesting to provide matching upper bounds on the total variation distance of two-component mixtures for all instances as a function of the means and covariance (generalizing the results for single Gaussians [14]). Extending our results to more general mixtures with k components and unknown component variances/weights (e.g., for Gaussian or even other families of distributions, such as those studied in [24]) will be of significant interest to both the statistics and machine learning communities.
From the choice of c and the fact that x ≤ x and x/2 ≤ x for x ≥ 1, we see 40/π 2 ≤ c ≤ 80/π 2 .