Demystifying Softmax Gating Function in Gaussian Mixture of Experts
Authors: Huy Nguyen
TrungTin Nguyen
Nhat Ho
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Mixture of Experts
Maximum Likelihood Estimation
Voronoi Loss Function
Algebraic Geometry.

Abstract: Understanding the parameter estimation of softmax gating Gaussian mixture of experts has remained a long-standing open problem in the literature. It is mainly due to three fundamental theoretical challenges associated with the softmax gating function: (i) the identifiability only up to the translation of parameters; (ii) the intrinsic interaction via partial differential equations between the softmax gating and the expert functions in the Gaussian density; (iii) the complex dependence between the numerator and denominator of the conditional density of softmax gating Gaussian mixture of experts. We resolve these challenges by proposing novel Voronoi loss functions among parameters and establishing the convergence rates of maximum likelihood estimator (MLE) for solving parameter estimation in these models. When the true number of experts is unknown and over-specified, our findings show a connection between the convergence rate of the MLE and a solvability problem of a system of polynomial equations.

Demystifying Softmax Gating Function in Gaussian Mixture of Experts
Huy Nguyen' TrungTin Nguyen Nhat Ho
Department of Statistics and Data Sciences, The University of Texas Austin
Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LJK
(huynm, minhnhat)@utexas..u edu, trung-tin. itt.--tii.ngyyeinniia.....
Abstract
Understanding the parameter estimation of softmax gating Gaussian mixture of experts has remained a long-stan oong-staning open problem the literature. It is mainly due to three fundamental theoretical challenges associated with the softmax gating function: (i) the identifiability only up to the translation of parameters; (ii) the intrinsic interaction via partial differential equations between the softmax gating and the expert functions the Gaussian density; (iii) the complex dependence between the numerator and denominator of the conditional density of softmax gating Gaussian mixture of experts. We resolve these challenges by proposing novel Voronoi loss functions among parameters and establishing the convergence rates maximum likelihood estimator (MLE) for solving parameter estimation in these models. When the true number of experts is unknown and over-specified, our findings show a connection between the convergence rate of the MLE and a solvability problem of system of polynomial equations.
Introduction
Softmax gating Gaussian mixture of experts 332 37 class of statistical machine learning models that combine multiple simpler models, known as expert functions the covariates, via softmax gating networks form more complex and accurate models, has found widespread
in various
applications, including speech recognition [51] 64 65]. natural language processing 14
20 17 [54]
211. computer vision [52] 3
[5] 44 and other applications 226 49 7
& 48
6 Regarding the 43 and physical sciences
applications of the softmax gating Gaussian mixture of experts in medicine
33), the parameters of each expert function play important role in capturing the heterogeneity of data. Thus, the main objective of these works is to conduct statistical inference for those parameters, which leads
need for convergence rates of parameter estimation in the softmax gating Gaussian mixture of experts. However, comprehensive theoretical understanding of parameter estimation in that model has still remained a long-standing open problem in the literature.
Parameter estimation has been studied quite extensively standard mixture models. his seminal work, Chen et al. [9] established the convergence rate univariate mixture models, namely, the settings when the number of true components is unknown and over-specified, and the family of distributions is strongly identifiable in the second order, c.g., location Gaussian distributions. That slow and non-standard rate is due to the collapse of some parameters into single pararameter or the convergence of weights to zero, which leads to the singularity Fisher information matrix around the true parameters. Then, Nguyen et al. [50] and Ho al. 22 utilized Wasserstein metrics to achieve this rate under the multivariate settings of second-o -ondrdderr strongly identifiable mixture models. Recently, Ho et al. (2 demonstrated that rates of the MLE strictly depend on the number of over-specified components when the mixture models are not strongly
of parameter estimation over-fitted
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

identifiable, such as location-scaa scale Gaussian mixtures. The minimax optimal behaviors of parameter estimation were studied in (27 46]. From the computational side, the statistical guarantee of the impecation-maximizaiio (EM), e.g., [12]. and moment methods had also been studied under both exact-fitted 2 I 25
and over-fitted settings [9 18
16 of mixture models.
Compared to mixture models, there has been less research on parameter estimation of mixture of experts. When the gating networks are independent of the covariates, Ho al. (30] employed the generalized Wasserstein loss function [59] to study the convergence rates of parameter estimation in Gaussian mixture of experts. They proved that these rates are determined by the algebraic inde- pendence of the expert functions and the partial differential equations with respect to the parameters. Later, Do et al. [13] extended these results general mixture of experts with covariate- gating network. Statistical guarantees of optimization methods for solving parameter estimation in Gaussian mixture of experts with covariate-free gating functions were studied in [1
63 When the
gating networks are softmax functions, parameter estimation becomes more challenging to understand due to the complex structures of the softmax gating function the Gaussian mixture of experts. Before describing these phenomena in further details, we begin by formally introducing the softmax gating Gaussian mixture of experts and related notions.
Problem setting: Assume that (X1, Y.)...., (Xn; Y,) E R x R are i.i.d. samples drawn from the softmax gating Gaussian mixture of experts of order it whose conditional density function gG. (Y]X) is given by:
exp(
T + (6))
9G. (Y|X)
S(YI(a)) X of
(I)
j=1 exp X + 3),))
where f(lu,, o) is a Gaussian density function with mean μ and variance a. Here, we define true but unknown mixing measure, that is, combination of Dirac measures 5 associated with true parameters f, == (Ph Si: ,b, of)) Notably, G. is not necessarily a probability measure as the summation of its weights can be different from one. For the purpose of the theory, assume that , E θ C R x Rd x R R x R4 where θ is compact set, and X E X' c. Rd where X is bounded set. Furthermore, we let (at, bj, oi),...... (a._, 62. ot.) be pairwise distinct and at least one among Si....., .........3. 37s, be non-zero to guarantee the dependence of softmax gating function the covariate X. Finally, we assume that the covariate X follows a continuous distribution to ensure that the softmax gating Gaussian mixture of experts is at least identifiable up to translations (see Proposition I.
G. = = exp((6))) (2
Maximum likelihood estimation. Since the value of true order k. is unknown in practice, to estimate the unknown parameters in the sofumax gating Gaussian mixture of experts (.. we consider using maximum likelihood estimation (MLE) within class of all mixing measures with at most components, which is defined as follows:
Gn E arg max- GEO,(0) n
1
Σ (X]]))(
(2)
where Ox(()) (G= E'' To guarantee that the MLE G. is a consistent estimator of G., we need k 2 k. In this paper, we study the convergence rate of the MLE G, to the true mixing measure G. under both the exact-fitted settings, namely when l: = k., and the over-fitted settings, namely when k > k., of the softmax gating Gaussian mixture of experts.
: 1 k S and (Boi, Bii, az b.) E O).
Fundamental challenges from the softmax gating function: There are three fundamental challenges arising from the softmax gating function that create various obstacles in our convergence analysis:
(i) Firstly, parameters Si., S of the softmax gating function are not identifiable as those of the covariate-indee indeeeddeni gating function in previous work. Instead, they are identifiable up to transla- tions, that is, the softmax gating value does not change when translate 8% to 1% + i and Si, to 3ig + to for any t IR and i2 E Rd. As consequence, we need to introduce infimum operator in the Voronoi loss functions (see equations (4) and (6)) to deal with this issue.
(ii) Secondly, a key step in our proof techniques is to decompose the density discrepancy 98, (YIX)- 9g. (Y) into linear combination of linearly independent elements using Taylor expansions.

---

However, since the numerators and denominators of softmax gating functions are dependent, we cannot apply the Taylor expansions directly that density discrepancy as in previous work [3] Moreover, there are two intrinsic interactions between parameters of the softmax gating's 's numerators and the Gaussian density function via the following partial differential equations (PDEs), which induce lot of linearly dependent derivative terms in the Taylor expansions:
Pu du
2u Iu
2
03,00
0a
062
0o
where xY 31. a, b, (3 X):
f(Y(a T + b. Therefore, it takes us great effort to group those linearly dependent terms together to obtain the desired linear combination of linearly independent terms.
(iii) Lastly, given the above linear combination of linearly independent elements, when the density estimation 9a., (YIX) converges the true density gc. (Y]X), the associated coefficients in that transformations, those limits lead system of polynomial equations introduced in equation ( This system admits a much more complex structure
combination also go zero. Then, via
than what considered in previous work [30 13
These fundamental challenges from the softmax gating function suggest that the previous loss functions, such as Wasserstein distance [50,
28 28 30), being employed to study parameter estimation in standard mixture models or mixture of experts with covariate free gating functions are no longer sufficient they heavily rely on the assumptions that the weights of these models independent of the covariates.
Main contributions: To tackle these challenges of the softmax gating function, we propose two novel Voronoi losses among parameters and establish the lower bounds of the Hellinger distance, denoted as -)..-), of the mixing densities of softmax gating Gaussian mixture of experts in terms of these Voronoi losses to capture the behaviors of the MLE. Our results can be summarized as follows (see also Table D
Exact-fitted settings: When k k. we demonstrate that the Hellinger lower bound Ex (xxh( (-1X) gG. (+X))] 2 C- Di G.) holds for any mixing measure G E (+)O), where C some universal constant and the Voronoi metric DG G.) defined as:
D1 = inf f1.
Σ EEA,
exp(3u)))(A Pry,, Aay Abiy, Aois))l
exp(3os) exp(36s + +nin+++i++ (4)
Σ EEA,
where Bij = B1: Bi 12, Daij a, a aj. Abi infimum over 41 E and l2 E Rdd is to account for the identifiability up to the translation of (Bi, 5- Furthermore, Ay is a Voronoi cell of mixing measure G generated by the true component w3- = ( aj. bj, 05) for all S k. 47), which is defined as follows:
by. Aoij == o; oj. The
= A,G)) := (i E (1,2,.... ... .. |lw w/ S ||w will VE + j},
(5)
where we denote w; == (B1, a, b,, o,). It is worth noting that the cardinality of each Voronoi cell Aj indicates the number of components of G approximating the true component wj of G.. As Ex [h(ga. (-IX)..c.(
= 1(2)) that lower bound of Hellinger distance indicates that Dj (G., G.) 0/21//)). Therefore, the rates of estimating exp(66)); Pī, (up translations) and aj. 33. of are of optimal order On
2. Over-fitted settings: When & k., the lower bound of Hellinger distance in terms of the Voronoi metric D, the exact-fitted settings is no longer sufficient due to the collapse softmax of vectors in possibly & dimensions to softmax of vectors in k. dimensions. Our approach is to define more

---

fine-grained Voronoi metric D2 (2, G.) to capture such collapse, which is given by:
D2(G, = inf
Σ Σ
exp(3o.) (1(4), Biyg. Aby, (11)))) + IIAaa,, A01))1
61.2 J:l 1
Σ E Σ exp exp((ex))l( Day, Abyj, AoGGil + H|Ay|=iiEA,
Σ
exp(Soi) - exp((6s + {1){ (6)
EEA,
for any mixing measure G E Ox()). Here, the values of function F(-) are determined by the solvability of a system of polynomial equations defined in equation ( We then show in Lemma that F(2) = 4, F(3) = 6, and we conjecture that F(m) 2m for any m 2 2.
In high level, the aforementioned system of polynomial equations arises from the PDEs in equa- tion (3) when establish the lower bound Ex (x( (x)00 (-x))) CCD, for any G E (+) for some universal constant C". Since Ex (h(oa, (-IX), ((xx)) O/n
also have D2 G.) 1122 under the over-fitted settings of the softmax gating Gaussian mixture of experts. As a consequence, the rates for estimating true parameters whose Voronoi cells have only one component of the MLE are order O(n (/2) On the other hand, for true parameters exp(36y): ), Piy aj, oj.0z whose Voronoi cells have more than one component of the MLE, the esti- mation rates are respectively ((11//2((A)))) for Si On-11/((AA)) D) for aj. oz. and On for )x This rich spectrum of parameter estimation rates is due to the complex interaction between the softmax gating and the expert functions.
Table I: Summary of density estimation and parameter estimation rates in the softmax gating Gaussian mixture of experts under both the exact-fitted and over-fitted settings. Recall that the cardinality of each Voronoi cell Aj gives the number of fitted components approximating true component w = =i aj. bb. az) (see equation (5). Furthermore, the notation F((A,)) stands for the solvability of the system of polynomial equations D). For instance, if wj is fitted by two components, then
have L,,- = 2 and F((A,)) 4. Please refer to Lemma for more details of the values of function F.
Setting
Loss Function
gG_ (YIx)
exp(%6,)
Bi, 03
07.03
Exact-fitted
D1
Onn-1/2)
O(n-1/2)
(n-1/22
O(n
Over-fitted
D2
((n-1/2)
O(n-1/2)
O (1-1/2M(AA))))
On-1//MAA))
Although the slow rates of the MLE under the over-fitted settings of the softmax gating Gaussian mixture of experts may seem discouraging, a practical implication of these results is that should not choose the number of experts le to be very large compared to the true number of experts ki Furthermore, the slow rates can also be useful for post-processing procedures, such merge-truncatt--merg procedure 24] with the MI_ reduce the number of experts as to consistently estimate k. when the number of data is sufficiently large. In particular, an important insight from the theoretical results that we can merge the MLE parameters that are close and within the range of their rates of convergence or truncate the parameters that lead to small weights of the experts. As the sample size becomes sufficiently large, the reduced number of experts may converge to the true number of experts. We leave an investigation of such model selection with the Gaussian mixture of experts via the rates of MLE for future work.
Practical implications:
The paper is organized as follows. In Section we first provide background on the identifiability and rate of conditional density estimation in the softmax gating Gaussian mixture of experts. Next, we proceed to establish the convergence rate of the MLE under both the exact-fitted and over-fitted settings of these models in Section 3] Then, conclude the paper with a few discussions in Section 4 Finally, full proofs of the results and a simulation study are provided in the Appendices.
Organization:
Notation: Firstly, we denote [rx] : 21, n for any positive integer Next, for any vector E Rdd and 2 : (z1, Z2..... 2a) E Nd. we denote u² = of u²² ... u²² |u| := + U2 + + ua and := 21 lzz!.... za!, while ||u||| represents for its 2-norm value. Additionally, the notation |A] indicates the cardinality of any set A. Given any two positive sequences (an)m21 and (b,, Jo we write a, = (b,,) or an S bn if an S Chn for all n E N, where C > 0 is some universal constant. Lastly, for any two probability density functions p, q dominated by the Lebesgue measure μ. we denote

---

()) [[vp- 2 du as the their squared Hellinger distance and V(p,g) = 2 gld as their Total Variation distance.
Background
In this section, we begin with the following result on the identifiability of the softmax gating Gaussian mixture of experts, which was previously studied in [36].
Proposition 1 (Identifiability of the softmax gating Gaussian mixture of experts). For any mixing measures G Σi= (B and G' E (xp(P% ( MM, af,
if we have (Y = 9G' (Y (X) for almost surely (X,Y) Y), then it follows that k = K' and G = G where G = Ei= exp(A%: + (1)0 (2,,,, for some 1 E IR and l2 E IR..
Proof of Proposition is issii Appendix B.T The identifiability of the softmax gating Gaussian mixture of experts guarantees that the MLE G₂
converges to the true mixing measure G. (up to the translation of the parameters in the softmax gating).
2
Given the consistency of the MLE, it is natural to ask about its convergence rate to the true parameters. Our next result establishes the convergence rate of conditional density estimation 9a. (YIX) to the true conditional density gG. (Y) which lays important foundation for the study of MLE's convergence rate.
Proposition (Density estimation rate). Given the MLE in equation estimation 96.. (X) has the following convergence rate:
2 the conditional density
P(Ex|h(sa, (-1X).9. (-1))] C(1o((n)/m)113) S exp((clogn),,
where and C are universal constants.
Proof of Proposition 2 is in Appendix B.2 The result Proposition 2 indicates that under either the exact-fitted or over-fitted settings of the softmax gating Gaussian mixture of experts, the rate of the conditional density function 98. (Y to the true one 9g. (Y under Hellinger distance is of order On 1/2) (up some logarithmic factors), which is parametric on the sample size.
estimation in Proposition 2 suggests that as long The parametric rate of the conditional density establish the Hellinger lower bound
From density estimation to parameter estimation:
Ex Ex(h(aa-1XX) SG. (+)))) Z D(G, G.) for any mixing measure G E (9) for some metric D among the parameters, then we obtain directly the parametric convergence rate of the MLE under the
metric D. Therefore, the main focus of the next section is to determine such metric D and to establish that lower bound under either exact-fitted or over-fitted settings of the Gaussian mixture of experts.
3 Convergence Rate of the Maximum Likelihood Estimation
In this section, we first study the convergence rate of the MLE under the exact- fitted settings of the softmax gating Gaussian mixture of experts in Section 3.1 Then, we move to the over-fitted settings in Section 3.2
Finally, we provide proof sketch of the theories in Section 3.3
3.1 Exact-fitted Settings
For the exact-fitted settings, namely, when the chosen number of experts k is equal the number of experts k., as we mentioned in the introduction, the proper metric between the MLE and the true mixing measure is the metric Dj defined in equation (4), which is given by:
(G, inf f1
Σ
Σ EA
exp(33:))l(A Puyj Daiy Abrj. Art))l
Σ iEA,
exp(Boc) - exp(66, +11)
5

---

Here, Aj is a Voronoi cell of G generated by ($i; oj, bj. 0). for all 1 S j S k, Furthermore, the infimum is taken with respect (21, E R x Ra such that P6y + 4 and Pi, l2 still lie inside the domain of the parameter space @.
where 16, == -B1--Bi -i; - t2, Aay := 0: oj. Ab, := b-bb, Ao := - o.. -
It is clear that D1 (G, 0 if and only if G = G. (up to translation). When DI G.) is sufficiently small, there cxist &1, t2 such that all of Biyj. Aay Abij, Aoig, and LIEA, exp(Sw)) exp(26y + t1) are sufficiently small as well. Therefore, the loss function D1 provides useful metric to measure the difference between the MLE and the true mixing measure. For any fixed 4, l2, the computation of the summations in Dj only has the complexity of the order (kk)). To solve the optimization with respect to (1, l2 in the metric D1, we can utilize the projected subgradient method with fixed step size [4], which has the complexity of the order OE=-2) as the functions of i and 2o are convex where E a desired tolerance. Therefore, the total computational complexity of approximating the value of the Voronoi loss function D is at the order of (
The following result establishes the lower bound of the Hellinger distance between the conditional densities in terms of the loss function D1 between corresponding mixing measures, which in turn leads to the convergence rate of the MLE.
Theorem 1. Given the exact-fitted settings of the softmax gating Gaussian mixture of experts i.e. = k. we find that
Ex (-X)) (1 (X))) G. D,,G,
\ (x.-1(0) Ox, for any G E Ex. (0)
where C1 is some universal constant depending only on G. and O As a consequence, there exist universal constants C₁ and ej such that the convergence rate of the MLF Gn under the exact-fitted settings satisfies:
P(Di(Gnn G.) > (1)g S exp(-
logn).
(8)
Proof of Theorem is in Appendix A. The parametric convergence rate of the MIE to G. under the metric DD suggests that the rates estimating the true parameters exp($t,). Pig (up to translation),
oj b3. 03 for j E [k.] are of order Onn (n-112), which are optimal up to logarithmic factors.
3.2 Over-fitted Settings
We now consider the over-fitted settings of the softmax gating Gaussian mixture of experts. Dif- ferent from the exact-fitted settings, the softmax weights associated with the MLE collapse to the softmax weights of the mixture of true experts as long as the MLE approaches the true mix- ing measure G.. More concretely, we can relabel the supports of the MLE G, with kn com- ponents (kn, I k) based on the Voronoi cells AT = A,(G,) such that we can rewrite as -n EiENy exp (xp()6)))
(8 ap (p. where Σ/= |Ag) ie,, (a. b2,0T) (az, 03)
exp x )
exp((3i,) ) X + Bby) j exp(( ) X + Bby.)
Σ ΣS iEA EP=1 E expl (3 T X )
A.
as approaches infinity for all < i S AB and j E [k.].
The collapse of the softmax weights along with the PDEs between the softmax gating and the expert functions in the Gaussian density create a complex interaction among the estimated parameters. To disentangle such interaction, we rely on the solvability of novel system of polynomial equations defined in equation (9). In particular, for any m 2 2, we define F(m) as the smallest natural number r such that the following system of polynomial equations:
Σ
Σ 1 (aimgn JET,
p p P2j
P3j Paj = O,
an al! 0z! aa!
for any (fi, f2) E Nd x N such that 0 < l Sr, 0 5 14 and f1 22122111 1, does not have
any non-trivial solution for the unknown variables {Pij P2j.Paj. P4j. P55 mm namely, all of ysy are non-zero and at least one among P3j is different from zero. The ranges of a 02 03 04 in the above

---

sum satisfy L2 = {a- = (a1. 02 03, Q4) E N X X a1 +1 E,, la + a3 + 20 =
f2). When d = and r 2. that system of equations becomes
m
Σ Pojpis 0,
Σ
0, Σ
Poj (P15P3j + +p2)) 0,
/=1
J=1
P3j
0,
P5j
2 Paj
2
+ Pas)
j=1
It is clear that we have non-trivial solutions P5j 1, Pij = 0 for all j E [ma], |p21| P31 1,
|pea| = P32 1, P41 = P42 1122, P2j - P3j paj = 0 for S S m.
When d = and r 3, the system of equations can be written as follows:
m
m
m
Σ
Po = 0,
Σ
Pry
=0
Σ
p
(p25 + +11Ppa)) = 0,
j=1
j=1
j=1
7
m
P53Pij = 0,
Σ P5
Pbg + pas)
=0, Σ
P5j
31 Paj + PssPNs = 0,
/=1
Ø=1
j=1
Σ
PojPis
=0,
Σ
P5j
2
1
PijP3j + +LIP22) = 0,
3=1
/=1
Σ j=1
2 P63
2
Pij
Paj
P1jP4j + P2)P83 = 0.
can be seen that the following is a non-trivial solution of the above system: Psj P1; P2j
for all E [m]] = v3 P32 v3 Pu1 P42 6 P3j Paj = 0 for 3 S S m. Therefore, we obtain that F(m) 2 A when m 3 and 1.
In general, when = 1, the system of equations has (r²2 + 3r2 equations. Intuitively, when m sufficiently larger than (r² + 3r)/2, the system may not have non-trivial solution. For general dimension d and parameter m 2 2, finding the exact value of F(m) is a non-trivial central problem in algebraic geometry (55). When m is small, the following lemma provides specific values for F(m).
Lemma 1. For any 2 1, when
2, F(m) 4. When 3, F(m) = 6.
Proof of Lemma D is in Appendix B.3 As m increases, so does the value of F(m). We conjecture that F(m) 2m and leave the proof of that conjecture future work.
By constructing the Voronoi loss function:
D2(G, = inf t1.82 >
Σ Σ
exp(3us) (I(A,,, Aby))) + II(Aai, (0s)))
+ Σ Σ
Aaij Abij, Ao +
exp(Box) exp( + (1)l PEA,,
the following result demonstrates that the convergence rates of the MLE under the over-fitted settings of the softmax gating Gaussian mixture of experts determined by F(-).
Theorem 2. Under the over-fitted settings of the softmax gating Gaussian mixture of experts 1 namely, when & > kio, we obtain that
Ex Ex(Mggo(-1X).cc ((X))] 2 C2 Gz)
(10)
for any G E (+) where C2 is some universal constant depending only on G. and θ. Therefore, that lower bound leads to the following convergence rate of the MLE:
P(Dz(GGn, G.) C,llo(nn//)) S exp(-o2 logn),
(11)
where C¹2 and Cg are some universal constants.
7

---

Proof of Theorem is in Appendix A.2 A few comments with the result of Theorem 2 are in order.
(i) Rates of individual parameters: The convergence rate On (12)) (up to some logarithmic term) of the MLE under the loss function D2 implies that for the true parameters exp(Bi,)) ) $i,, aj bj. 0j whose Voronoi cells have only one component of the MLE, the rates for estimating them are On 1/2) up some logarithmic factor. On the other hand, for true parameters with greater than one component (51)) while those for aj. oj are Onn (111//(())) (up to logarithmic factors). As the maximum value of |AA] is hn - hi + 1, indicates that these rates (up to logarithmic factors) can be as worse as O(n (//--1((knn-a - for estimating 0z. 03 and OO -k.ttt))...)))))))))) 11) for estimating Piz:
in their Voronoi cells, the rates for estimating Pig. bj are
(ii) Computation of Voronoi loss function Dz: Similar to the Voronoi loss function Dj in the exact-fitted setting, the loss function D2 is also computationally efficient. In particular, for any fixed 11, 12, the computation of the summations in the formulation of 'D2 is at the order O x k:),, which is linear on & when k, is fixed. Furthermore, we can solve the convex optimization problem with respect to 41, d2 with computational complexity at the order of O( via the projected gradient descent method with fixed step size where is the error. Therefore, the total computational complexity of approximating the Voronoi loss function D2 is at the order of O(k x k./e²).
(iii) Comparison with covariate-free gating network: We would like to remark that the results being established for parameter estimation under the softmax gating network settings of over-fitted Gaussian mixture of experts are in stark difference from those under the covariate-free gating network settings of these models (30, namely, when the gating function is independent of the covariates X. In particular, Theorem 2 in 30 shows that when the gating networks are independent of the covariates, the convergence rates of estimating oj are at the order of O(n -1/4) (up to some logarithmic factor), which are independent of the number of over-fitted components. It is different from the rates of a} whose Voronoi cells have more than one component in the softmax gating settings, which depends on the number of components that we over-fit the Gaussian mixture of experts (see discussion (i) after Theorem D. Furthermore, the rates of estimating bj.07 when the gating networks are independent of covariates are determined by a system of polynomial equations that is much simpler than the system of equations (9) when the gating networks are softmax function. These differences are mainly due to the intrinsic interaction characterized by partial differential equations with respect to the parameters between the softmax gating networks and the expert functions in Gaussian distribution.
3.3 Proof Sketch
In this section, we provide a proof sketch for Theorems and To simplify the ensuing discussion, the loss function DD in the proof sketch is implicitly understood as either Dj or DD2 depending on
the settings of the softmax gating Gaussian mixture of experts. Since the Hellinger distance / is lower bounded by the Total Variation distance V. to obtain the bounds in equations 7 and (I0). it is sufficient to show that Ex [V9 (ga (-IX), 9G. (-IX))] 2 D(G, G.). To establish this bound, we respectively prove its local and global versions by contradiction as follows:
Local version: In this part, we aim to show the following local inequality:
lim inf [x(V( (1X))) O. (E).
(12)
Assume that this claim does not hold true, that is, there exists sequence Gn Din exp ( af .oo))) (e) such that both [x[V (+IX), gG. (-IX)))/D((Gm G.) and D(G,, G.) approach zero as n tends to infinity. This implies that for any [kt],, we have EIEA, exp( + exp($ij) and (3), a. Dy of)) + (81, aj, 65. oz) and for all E Ay. For the sake of presentation, we simplify the loss function D by assuming that it is minimized when t 0 and 1/- = Og. Now, we decompose the quantity
Qn ) Tx + {6 (Y|X) 9a. (Y [X]
8

---

as follows:
h. On Σ
(xp(5p)))
uYY] S1: ag. - (i, uX|]x;
j=1 iEA;
k. j=1
o (1(1x:88)))
Σ TEA;
- -xx((((3)) [b); 05, - (V|x;; .
where we define u( u(Y)x; b, := exp(3]x))[VI)) X))(((aa + b, and x((
exp(3 X) X)ge, (X) Next, for each [k.] and i A,, we denote (i(X, bz. == (0j) "X+b3
and then apply the Taylor expansions to the functions u(Y|x; Sh, a. bf, o() and x up to orders rij and r2 (which we will choose later), respectively, as follows:
(( 8i af (2, - xX Big. 6,,000))
2n1
0 f
Σ
The (1)x exp(((t,)) T X) x + Rii
dh
|61++2==1
121
o( oY|| ,XIIx; = Σ (; exp(( T X)9a., (Y|X) + Rai (X, Y),
h=
where R1ss (X, Y) and R25 (X, Y)) are Taylor remainders such that Rpi (X, Y) (D G.) vanishes as n + co for p E (1,2). As a result, the limit of Q,/ (DG. G.) when n goes infinity can be seen as a linear combination of elements of the following set:
gda f (YI(a)) x + 17) : EE [k.). OS 2/6/ + 2nd }
w: = X exp((31,)) T X)
oh
U f exx)((())) X)g. (YIX): j E [k.]. 0 S 17 < r
which is shown to be linearly independent. By the Fatou's lemma, we demonstrate that Qn/D(G,,, G.) goes zero as of Qn/ (D,, G.), denoted by TV Th ())D(G,, G.) and (D) G-), vanish when n + co. Given that result, we aim to select the Taylor orders Vıy and r2j such that at least one among the limits of ())D((G G.) and 5T) (j) G.) is different from zero, which leads to contradiction. Hence, we obtain the local version of the desired inequality.
co, implying that all the coefficients in the representation
Below the details of choosing appropriate Taylor orders in each setting.
Exact-fitted settings: Under this setting, since ki is known, each of the Voronoi cells A, for j E [ki]] has only one element. Thus, for any i Aj. we have exp(A()) + exp( and (8T a. by o.) + a3 oj). Given that result, we will select Tı T2j 1 for all j E [k.]] as it suffices to show that at least one among the limits of T7 (i)/DG,, G.) and
ST () G.) is different from zero. In particular, if all of them vanished, would take the sum of all the limits of T7, 86 (i, G.) for (l,, (2) such that 2/6 + l2 < 2, which leads contradiction that 1 D(G,,, G.), G.) - 0.
Over-fitted settings: As k. becomes unknown in this scenario, we need higher Taylor orders to obtain the same result as in the exact-fitted setting. We will reuse the proof by contradiction method to find out those orders. More specifically, assume that all the limits of 17, (i)/D(G,, G.)) and ST (G,, G.) equal zero. After some steps of considering typical limits as in the previous setting which requires r25 = 2 for all j E [kt,], we encounter the following system of polynomial equations:
ph: P1s P2i Psi Pa
04 0,
Σ
Σ
an! az! az! as!
EE,Ay (01,02 a.).aa.....Iee...
for all (li, f2) E Nd x N such that S 16] S rıy, S l S nı - | |&1 + E2 2 for some j [k.]. Due to the construction of this system, it must have least one non-trivial

---

solution. Therefore, if we choose Fij = F([AA,) for all j [k,], then the above system does not admit any non-trivial solutions, which leads a contradiction. Hence, we obtain the lo-
cal inequality in equation (22), which suggests that we can find positive constant e such that inf infGEO,()):D(GG...)) Ex V (Vlo(-)XX) (1X/)//GGG..))))//)GGGG...
Global version: Therefore, it is sufficient to demonstrate the following global inequality:
inf (()
Ex [V
G.) 0.
(13)
Assume that this claim not true, then we can find a mixing measure G' E (+) such that 9c ()) 9G. (YIX) for almost surely (X, Y). According to Proposition
| we get that D(G", G.) = O, which contradicts the hypothesis D(G", GG) > E'. These arguments hold for both exact-fitted and over-fitted settings up some changes of notations.
Hence, the proof sketch is completed.
Discussion
In the paper, study the convergence rates of parameter estimation under both the exact-fitted and over-fitted settings of the softmax gating Gaussian mixture of experts. We introduce novel Voronoi loss functions among parameters resolve fundamental theoretical challenges posed by the softmax gating function, including identifiability up to the translation of parameters, the interaction between softmax weights and expert functions, and the dependence between the numerator and denominator of the conditional density function. When the true number of experts is known, we demonstrate that the rates for estimating true parameters when the true number of experts is unknown and over-specified, these estimation rates turn out to be determined by the solvability of a system of polynomial equations.
parametric on the sample size. On the other hand,
There are a few natural directions arising from the paper that we leave for furture work:
First, work does consider the top-K sparse softmax gating function, which has been widely used to scale up massive deep learning architectures (68 54 21]. It is practically important to extend the current theories establish the convergence rates of parameter estimation in the Gaussian mixture of experts with that gating function.
Second, the paper only takes into account the regression settings, namely when the dis- tribution of Y is assumed to be continuous. Given that mixture of experts has also been used in classification settings 22 31
53 34 35| 60), namely when Y is a discrete response variable, it is desirable to establish comprehensive theory for parameter estimation under these settings mixtures of experts.
Third, the theories developed the paper lay an important foundation for understanding parameter estimation in more complex models, including hierarchical mixture of experts [33
$1.37 (6)] and multigate mixture experts 44 26 45
Finally, the convergence rates of the MLE in this work are established under the well- specified settings, namely when the data are drawn from the softmax gating Gaussian mixture of experts. Nevertheless, the convergence analysis of the MLE under the misspec- ified settings, namely when the data are not necessarily generated from that model, has remained poorly understood. Under those settings, the MLE G. converges to the mixing measures G E arg min (9) (L()) p(Y[X) where p(Y|X) is the true condi- tional density function of Y given X, and it is not softmax gating Gaussian mixture of experts. Additionally, the notation KL stands for the Kullback-Leibler divergence. The insights from our thcories under the well-specified setting indicate that the Voronoi loss functions can be used to obtain the precise rates of individual parameters of the MLE G, to those of the mixing measure G.
Acknowledgements
NH acknowledges support from the NSF IFMI. 2019844 and the NSF Institute for Foundations of Machine Learning.
10

---

References
[1] A. Anandkumar, D. Hsu, and S. M. Kakade. A method moments for mixture models and hidden markov models. In COLT, 2012.
[2] S. Balakrishnan, M. J. Wainwright, and B. Yu. Statistical guarantees for the EM algorithm: From population to sample-based analysis. Annals of Statistics, 45:77-120, 2017.
[3] H. Bao, W. Wang, L. Dong. Q. Liu, O.-K. Mohammed, K. Aggarwal. S. Som, S. Piao, and
In F. Wei. VLMo: Unified iision-languae pre-training with ofoxtur--o-modlllyy--pppop Advances in Neural Information Processing Systems, 2022.
[4] S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
[5] Chamroukhi and B. T. Huynh. Regularized
Estimation of Mixture- of-Experts for Regression and Clustering. In 2018 International Joint Conference on Neural Networks (IJCNN), pages 1-8, 2018.
[6] F. Chamroukhi and B.-T. Huynh. Regularized Maximum Likelihood Estimation and Feature Selection in Mixtures-of-Expeee Models. Journal de la Société Française de Statistique, 160(1):57-85, 2019.
[7] F. Chamroukhi, A. Samé, G. Govaert, and P. Aknin. Time series modeling by a regression approach based on latent process. Neural Networks, 22(5-6):593-602, 2009. Publisher: Elsevier.
[8] F. Chamroukhi, A. Samé, G. Govaert, and P. Aknin. A hidden process regression model for functional data description. Application to curve discrimination. Neurocomputing, 73(7-9):1210- 1221, 2010.
[9] J. H. Chen. Optimal rate of convergence for finite mixture models. Annals of Statistics, 23(1):221-233 1995.
[10] K. Chen, I.. Xu, and H. Chi. Improved learning algorithms for mixture of experts in multiclass classification. Neural Networks, 12(9): 122-51222-1,2,,, 1999.
[11) Y. Chen, X. Yi, and C. Caramanis. A convex formulation for mixed regression with two components: Minimax optimal rates. COLT, 2014.
[12] A. P. Dempster, N. M. Laird, and D. B. Rubin. Maximum Likelihood from Incomplete Data Via the EM Algorithm. Journal of the Royal Statistical Society: Series B (Methodological), 39(1):1-22, Sept. 1977.
[13] D. Do, L. Do, and X. Nguyen. Strong identifiability and parameter learning regression with heterogeneous response. arXiv preprint arXiv:2212.0444 2022.
[14] G. Do, H. K. Le, T. Nguyen, Q. Pham, B. T. Nguyen, T.-N. Doan, C. Liu, S. Ramasamy, X. Li, and S. HOL HyperRouter: Towards Efficient Training and Inference of Sparse Mixture of Experts. In Proceedings of the 2023 Conference Empirical Methods in Natural Language Processing, Singapore, Dec. 2023. Association for Computational Linguistics.
[15] A. Dosovitskiy, I.. Beyer, A. Kolesnikov, D. Weissenborn, X. Zhai, T. Unterthiner, M. Dehghani, M. Minderer, G. Heigold, S. Gelly, J. Uszkoreit, and N. Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale. In International Conference on Learning Representations, 2021.
[16] N. Doss, Y. Wu, Yang, and H. H. Zhou. Optimal estimation of high-dimensional Gaussian location mixtures. The Annals of Statistics, 51(1):62 - 95, 2023. Publisher: Institute of Mathematical Statistics.
[17] N. Du, Y. Huang, A. M. Dai, S. Tong, D. Lepikhin, Xu, M. Krikun, Y. Zhou, A. Yu, O. Firat, B. Zoph, L. Fedus. M. Bosma, Z. Zhou, T. Wang, E. Wang, K. Webster, M. Pellat, K. Robinson, K. Meisr--elllseem, T. Duke, L. Dixon, K. Zhang, Q. Le. Y. Wu, Z. Chen, and Cui. Glam: Efficient scaling of language models with mixture-of-experts, In ICML,, 2022.
[18] R. Dwivedi, N. Ho, K. Khamaru, M. Wainwright, M. I. Jordan, and B. Yu. Sharp analysis of pnnectaaionmmaximizaaii for weakly identifiable models. AISTATS, 2020.
[19] R. Dwivedi, N. Ho, Khamaru, M. J. Wainwright, M. Jordan, and Yu. Singularity, misspecification, and the convergence rate of EM. Annals of Statistics, 44:2726-2755 2020.
11

---

[20] D. Eigen. M. Ranzato, and I. Sutskever. Learning factored representations in deep mixture of experts. In ICLR Workshops, 2014.
[21] W. Fedus, B. Zoph, and N. Shazeer. Switch transformers: Scaling to trillion parameter models with simple and efficient sparsity. Journal of Machine Learning Research, 23:1-39, 2022.
[22] I. C. Gormley and T. B. Murphy. A mixture of experts model for rank data with applications in
election studies. The Annals of Applied Statistics, 2(4): 1477, 2008. Publisher: Institute of Mathematical Statistics.
[23] J. Green. Iteratively Reweighted Least Squares for Maximum Likelihood Estimation, and some Robust and Resistant Alternatives. Journal of the Royal Statistical Society. Series B (Methodological), 46(2))149-199) 1984, Publisher: [Royal Statistical Society, Wiley].
[24] A. Guha, N. Ho, and X. Nguyen. On posterior contraction of parameters and interpretability in Bayesian mixture modeling. Bernoulli, (((4):2159-2188) 2021.
[25] M. Hardt and E. Price. Tight bounds for learning a mixture of two gaussians. In STOC, 2015.
[26] H. Hazimeh, Z. Zhao, A. Chowdhery, M. Sathiamoorthy, Y. Chen, R. Mazumder, L. Hong, and E. Chi. DSelect-k: Differentiable Selection in the Mixture of Experts with Applications to Multi-Task Learning. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P. S. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 29335-29347. Curran Associates, Inc., 2021.
[27] P. Heinrich and J. Kahn. Strong identifiability and optimal minimax rates for finite mixture estimation. The Annals of Statistics, 46(6):2844-2870, 2018.
[28] N. Ho and X. Nguyen. Convergence rates of parameter estimation for some weakly identifiable finite mixtures. Annals of Statistics, 44:2726 2016.
[29] N. Ho and X. Nguyen. On strong identifiability and convergence rates of parameter estimation in finite mixtures. Electronic Journal of Statistics, 10:271-307, 2016.
[30] N. Ho, C.-Y. Yang, and M. I. Jordan. Convergence rates for Gaussian mixtures of experts. Journal of Machine Learning Research, 23(323):1 81, 2022.
[31] B. T. Huynh and F. Chamroukhi. Estimation and feature selection in mixtures of generalized linear experts models. arXiv preprint arXiv: 1907,06994, 2019.
[32] R. A. Jacobs, M. Jordan, S. J. Nowlan, and G. E. Hinton. Adaptive mixtures of local experts. Neural Computation, 3, 1991.
[33] R. A. Jacobs, F, Peng, and M. A. Tanner. A Bayesian Approach to Model Selection in Hierarchical Mfxtures-of-Experts Architectures. Neural Networks, 10(2), 1997.
[34] W. Jiang and M. A. Tanner. Hierarchical Mixtures-of- for Generalized Linear Models: Some Results on Denseness and Consistency. In D. Heckerman and J. Whittaker, editors, Proceedings of the Seventh International Workshop Artificial Intelligence and Statistics, volume R2 of Proceedings of Machine Learning Research. PMLR, Jan. 1999.
[35] W. Jiang and M. A. Tanner. On the Approximation Rate of Hierarchical Mixtures-of--Eperrss for Generalized Linear Models. Neural Computation, (((5):1133111)) July 1999.
[36] W. Jiang and M. A. Tanner. On the identifiability of offeuees.. Neural Networks, 9:1253-1253 1258, 1999.
[37] M. I. Jordan and R. A. Jacobs. Hierarchical mixtures of experts and the EM algorithm. Neural Computation, 6: 181-214, 1994.
[38] B. Krishnapuram, L. Carin, M. Figueiredo, and A. Hartemink. Sparse multinomial logistic regression: fast algorithms and generalization bounds. IEEE Transactions on Pattern Analysis and Machine Intelligence, (76655777 2005.
[39] M. Kuusela, T. Vatanen, E. Malmi, T. Raiko, T. Aaltonen, and Y. Nagai. Semi-supervised anomaly detection towards model indee-indeeendent searches of new physics. Journal of Physics: Conference Series, 368:012032, 2011.
[40] J. Kwon and C. Caramanis. EM Converges for a Mixture of Many Linear Regressions. In
S. Chiappa and R. Calandra, editors, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 1727-1736. PMLR, Aug, 2020.
12

---

[41] J. Kwon, N. Ho, and C. Caramanis. On the minimax optimality of the EM algorithm for learning two-component mixed linear regression. In AISTATS. 2021.
[42] Kwon, W. Qian, C. Caramanis, Y. Chen, and D. Davis. Global Convergence of the EM Algorithm for Mixtures of Two Component Linear Regression. In A. Beygelzimer and D. Hsu, editors, Proceedings of the Thirly-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 2055-2110 10. PMLR, June 2019.
[43] Q. Li, R. Shi, and F. Liang. Drug sensitivity prediction with nigh-dimensional mixture regression. PLoS ONE, 2019.
[44] H. Liang, Z. Fan, R. Sarkar. Z. Jiang, T. Chen, K. Zou, Y. Cheng, C. Hao, and Z. Wang. V'T: Mixture-of- -f-Extsrts Vision Transformer for Efficient Multi-task Learning with Model- Accelerator Co-design. In NeurIPS, 2022.
[45] J. Ma, Z. Zhao, X. Yi, J. Chen, L. Hong, and E. H. Chi. Modeling Task Relationships in Multi-Task Learning with Multi-Gate ofxture-of-Fxperts In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD '18, pages 1930-1939, New York, NY, USA, 2018. Association for Computing Machinery. event-place: London, United Kingdom.
[46] T. Manole and N. Ho. Uniform convergence rates for maximum likelihood estimation under two-component gaussian mixture models. arXiv preprint arXiv:20066 200.000000,, 2020.
[47] T. Manole and N. Ho. Refined convergence rates for maximum likelihood estimation under finite mixture models. In Proceedings of the 39th International Conference on Machine Learning. volume 162 of Proceedings of Machine Learning Research, pages 14979-15006, PMLR, 17-23 Jul 2022.
[48] L. Montuelle and E. Le Pennec. Mixture of Gaussian regressions model with logistic weights, a penalized maximum likelihood approach. Electronic Journal of Statistics, 8():16661-195, 2014.
[49] B. Mustafa, C. Ruiz, J. Puigcerver, R. Jenatton, and N. Houlsby, Multimodal contrastive learning with limoe: the language-image mixture of experts. In NeurlPS, 2022.
[50] X. Nguyen. Convergence of latent mixing measures in finite and infinite mixture models. Annals of Statistics, 4(1):370 400, 2013.
[51] F. Peng, R. A. Jacobs, and M. A. Tanner. Bayesian Inference in Mixtures-of-Eaie offexxetts and Hierarchical Mixtures-of-Experts Models With Application to Speech Recognition. Journal of the American Statistical Association, 91435))9533-96, 1996.
[52] C. Ruiz, J. Puigcerver, B. Mustafa, M. Neumann, R. Jenatton, A. Pinto, D. Keysers, and N. Houlsby. Scaling vision with sparse mixture of experts. In NeurIPS, 2021.
[53] M. E. Ruiz and P. Srinivasan. Hicrarchical Text Categorization Using Neural Networks. Infor- mation Retrieval, 5(1):87-118, Jan. 2002.
[54] N. Shazeer, A. Mirhoseini, K. Maziarz, A. Davis, Q. Le, G. Hinton, and J. Dean. Outrageously large neural networks: The sparsely-gate -ated mixture-of-expeen layer. In International Conference on Learning Representations (ICLR), 2017.
[55] B. Sturmfels. Solving Systems of Polynomial Equations. Providence, R.I, 2002.
[56] H. Teicher. On the mixture of distributions. Annals of Statistics, 31:55-73, 1960.
[57] H. Teicher. Identifiability of mixtures. Annals of Statistics, 32:244 248,, 1961.
[58] S. van de Geer. Empirical processes in M-estimation. Cambridge University Press, 2000.
[59] C. Villani. Optimal transport: Old and New. Springer, 2008
[60] S. Waterhouse and A. Robinson. Classification using hierarchical mixtures of experts. In Proceedings of IEEE Workshop on Neural Networks for Signal Processing, pages 177-186. 1994.
[61] Y. Wu and P. Yang. Optimal estimation of Gaussian mixtures via denoised method of moments. The Annals of Statisties, 18:1987-2007, 2020.
[62] Y. Wu and H. H. Zhou. Randomly initialized EM algorithm for two-component Gaussian mixture achieves near optimality in (()n) iterations. Mathematical Statistics and Learning,
4:143-220, 2021.
13

---

[63] X. Yi, C. Caramanis, and S. Sanghavi. Alternating minimization for mixed linear regression. In ICML, 2014.
[64] Z. You, S. Feng, D. Su, and D. Yu. Speechmoe: Scaling large acoustic models with dynamic routing mixture of experts. In Interspeech, 2021.
[65] Z. You, Feng, D. Su, and D. Yu. Speechmoe2: Mixture-of experts model with improved routing. In ICASSP 2022 2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 7217-7221, 2022.
[66] Y. Zhao, Schwartz, J. Sroka, and Makhoul. Hierarchical mixtures of experts methodology applied to continuous speech recognition. In Advances in Neural Information Processing Systems, volume 1994.
[67] K. Zhong, P. Jain, and I. S. Dhillon. Mixed linear regression with multiple components. In NeurlPS, 2016.
[68] Y. Zhou, T. Lei, H. Liu, N. Du, Y. Huang, Y. Zhao, A. M. Dai, Z. Chen, Q. V. Lc, and J. Laudon. Mixture-of-Expee Experrsss with Expert Choice Routing. In A. H. Oh, A. Agarwal, D. Belgrave, and K. Cho, editors, Advances in Neural Information Processing Systems, 2022.
14

---

Supplement to "Demystifynng Softmax Gating Function in Gaussian Mixture of Experts"
In this supplementary material, we present the proofs of Theorems | and 2 2 Appendix A] and then
provide proofs for the remaining results in Appendix B Finally, we carry out a simulation study to illustrate the various convergence rates that were derived in Theorems T and 2 in Appendix
A Proofs of Main Results
In this appendix, we provide proof for Theorem in Appendix A.1 while leave that for Theorem 2 in Appendix A.2 Prior to discussing more detail, let us recall some notations for high-dimensional settings that we will use in our proofs. Firstly, for any vector == (u1, "2, uaa E Rd and |u| := + + + ud and
== (21, 22. ..,) zd) E N we denote u² = uf ... u'd := := _1!22!... za!. Additionally, Og denotes the vector zero in R2, whereas the notation 1 stands for the indicator function. Finally, we denote h1 a, b)
X + b and h2(X, o) as mean and
variance expert functions in this work for any (a, b, or) E TR. RR x RR and X X.
A.1 Proof of Theorem 1
General Picture: this proof, we focus mainly on establishing the following bound:
Ex (x( gG. (-IX)) 2 21 DD(
(14)
Then, the above bound together with the result of Proposition leaad to the conclusion of Theorem
Local version: Firstly, we prove the local version of the inequality (4)
inf --50 GEE,, (C,
lim
Ex(V(ge((X)) ((l ((X))) 0.
(15)
Suppose that the inequality in equation 15 does not hold true, then we can find sequence G,
E exp( (1 (0 (7)77777 E Ek. (+) such that
sG. Ex (gc,, (o. (+X)))/Di(G, G.) + 0,
D (G G.) 0,
as OC. Next, we consider the Voronoi cells AB ;= (G for j [K..]. of the mixing measure Gn generated by the true components of G.. Since the argument in this proof is asymptotic, we assume without loss of generality (WLOG) that those Voronoi cells are independent of n for all n N. ie. A, = A Additionally, since k, is known under the exact-fitted settings and D2 (G,, Gz) + O. the Voronoi cell Aj has only one element for any j E [R:.]. WL.GG, we assume that Aj = {j} for - cc. Furthermore, there exist I E IR and /2 E Rdd independent of n such that (x) - exp( + 41) and 3i - Bi, + l2 as n approaches infinity for all j E [k.]. It indicates that we can upper bound the Voronoi loss function D as Di G-) < (G,,,, G.), where
all [k=.], which follows that (a), ,),0))
(aj, Dj. 03)
(G,, = Σ (exp((6)) (A,,,,,, DaG. A6C.Ab6..orjj.. Aoo))l (exp((()) exp( + +1]
in which
1 = 3 - 8ig l2,
Daj = a.) a): AM = D3 bj. Aaj = 03 oj.
(.IX) ( G.) - 0 when n + 00. we also obtain that
As Ex Ex(V (-1x), ga.
Ex [x (X
15

---

Step 1: Density Decomposition
Subsequently, we consider Qn := 1 +12)² X + S, +ti)l 19g. (Y pa. (x1)), which can decomposed as
(x Qn =
- uXX|x; + 03,
exp(((g) [((] u [, (2)
j=1
(exp((0)) exp(66 + +ii) [u(r]x:0t, 12 02,00,3)))) - +
j=1
A, + Bn En:
(16)
where we denote u(Y [X; 3 a, b) == ssp33)))f(Y(a' X + b, and v(Y]X;
exp(3] exp(3]X)gc, X)gG. (Y Next, by means of the first-order Taylor expansion, rewrite A, as exp(36))
An
a! (1)) an (A63))
alaa)t 20 of ah aallltaa
xa exp((3f) 12)
12) x)
+ b1, (Y)(a)) X
(X)
exp(
a0 (1,
(A))))
j=1 2/61 ++2=1
o (Y (aj)) T + o
x x exp((8t) +22 x) x))
(17)
an?
where R2(X, Y) is Taylor remainder such that R (X,
G.) + 0 a - oc. Here, the first equality is due to the following partial differential equation for the univariate Gaussian density:
f
82a. f
(Yla)) X 05) 2044
(Yl(a))
X + b,,0,))) oj),
ahg
while the second equality is obtained by defining l = a1 + a2 & = |a-| + ag + 2a and
Isy.22 = {a- = (as) E Nd No x N: on + 02 li, 03 + 204 l2 |aal] (18)
for all (E1, 62) E N such that S 2|61| + 82 S 2. Analogously, Bn can be rewritten as h-
exp(po;)
Bn ΣΣ j=1
7 (A,, 2 X exp((8i, + 12) X)9c. (Y R2 Y), (19)
where R2(XX, Y) is a Taylor remainder such that [2(XX, H) /DD (Gn, G.) + 0 as n - xc. From the formulations of An, Bn and En, we can represent Qn as the following linear combination
2
On
Σ
T th (J) x²1 exp(((i, +22) x)
x)
(Y1(a)) x 0))
a 12
j=1 2/6:0
(T X² cxxx((33t 12) X)96., Rg (X, + R (X,Y),
with coefficients being denoted by T (1) and (T) for all j E [kx]. 0 S 2/4 + l2 S 2 and
0 < hr < 1 where
exp(>%))
Encteris
(Ai, (At)) (61,6) # #02.
Th The (j)
2a
exp( - exp((ii + (1),
(21, = (0.s 0);
(20)
16

---

and
exp((it) 7!
hl + 0,
(21)
exp(5(i) + exp(96) + f2),
h|=00 0.
Step 2: Non-vanishing coefficients
Now, we will demonstrate by contradiction that at least one among terms of the forms T (i)DD) G.) and ( G.) does not approach zero. Indeed, assume that all of them vanish when n - 0c, then we get
&,
k.
o (G G.)
(xp( exp(965 + t1) = Σ
- 0.
(22)
(r, G.)
1=1
3=1
Similarly, by considering the limits of Th (J)/D/ G.) for all j E [k.] and 2/G l2 2, we obtain that
exp ( (At, Aalj Ab;, - 0.
(23)
Dj (nn G.)
Combine the results in equations and 23 we have 1 = (G, G.) G.) + 0. which contradiction. As result, not all the limits of T (i)/D/ G.) and S ()))))D G.)
equal to zero.
Step 3: Fatou's lemma involvement
Thus, let m. be the maximum of the absolute values of those terms, we have that 1/m, A oc. Then, the Fatou's 's lemma says that
Ex (ga., (-1X), 9G. (-1x))] 2/ f
I9a., (Y|X) - -G. (Y|x) d(X,Y). n- 2m, DD, G.)
lim 72000
lim inf
(24)
my D2(G,, G.)
By assumption, the left-hand side of the above equation equals to zero, therefore, the integrand in the right-hand side also equals to zero for almost surely (X, Y), which leads to the following limit: Qn/ [m,
(D/(/CCC (Gns G.)]
+
oo for almost surely Y). More specifically, we have
k-
gh f ah
Σ
mes ( exp(( + 122 x)
x x+b5 T bj.0))
/=1
2/=
wy( X exp + +2) T X)9.. (Y = 0,
h1==
for almost surely (X,Y) Y), where Me, (i) and w,y (j) are the limits of Th (i) [m, D' (G., G.)] and S ())lm// D (G., G.)], respectively, for all j E [k.] 0 S 2 + l2 S 2 and 0 S hl < 1. Here, at least one among 1/, (j) and w, (j) is different from zero. On the other hand, since the set
O [ : e [k.,, 0 2// 62 $6
W X exp(( + 12) T x)
oh
U
+ 12) x X)9c. (YIX) j E [k.,, 0 0= 1).
(25)
is linearly independent (see Lemma 2 at the end of this proof), we obtain that , (1) = (i) 0 for all j [k:.]. 2/41 + lg < and hy < 1, which a contradiction.
Thus, we reach the local inequality in 15 that is, there exists 5' > 0 that satisfies
inf GEC,, (D)
Ex VV (ga(())) ( 0.
17

---

Global version: Thus, it suffices to prove its following global inequality:
inf (x G.) (0)) Di (.GGG))>ee'
(26)
Assume by contrary that there exists a sequence G², E (x) (6) that satisfies
[imm- Ex(V(ga; (ooe,,(111,,,0)) (D, G.) >''
G.) = 0,
Therefore, we obtain that [x[V (c. we are able to replace the sequence G", by its subsequence which converges to some mixing measure G' E Ek. (9) such that D(G", G.) E'. Then, by the Fatou's lemma, we get
sG. (-Ix)
oo. Since the set θ is compact,
lim Ex[V(xa) (1x),, ga. (-XX) 1
lim so, (Y 9c. (Y]X) d(x, Y),
which implies that
/ 1 (Y X) 9G. (YIx))d(XXY)
Thus, we obtain that 9C (Y| 9c. (X) for almost surely (X,Y), Now that the softmax gating Gaussian mixture of experts is identifiable up translation (see Proposition [ the mixing measure G" admits the form G' Σ exp($0-() + t1 ) (t
for some t E R and Rdd where T is some permutation of the set (1,2..... ......,k..... .k.. This leads to the fact that (i G.) O, which contradicts the hypothesis (G" G.) > 5s > 0. Hence, we obtain the inequality in equation (14).
To complete the proof, we will show the previous claim regarding the independence of elements in W1 in the following lemma:
Lemma 2. The set W1 defined in equation 25 is linearly independent w.F.t X and Y.
Proof of Lemma
Assume that the following holds for almost surely (X,Y):
k.
2
8
me),,, X exp((8i, + t2) x) (Y((a)) Tx + bj.
ah
j=1
2 2
h,
Σ
()) X2 exp((3i + 12) ( X)9a. (Y = 0,
j=1 1-/=0
where ,,, E R. and w. (j) E R. Then, we need show that Te,, (f) = wr(() 0, for all
j [k,], 0 < 2/6,1 le 2 and 0 < hi s 1. The above equation is equivalent to
1 2-26
f (Ya(a)) T x + b3. + wee Wg9.). (Y exp((8i, + t2) Tx)
ΣΣ
Σ
(j)
ah
-=
0
for almost surely (X Since , Bis, are k. distinct values, we get that the set (exp((8t, + xx) [k.]] is linearly independent, which implics that
2-26
8- (M1(g)) x +bb.003) + wxlD).. (Vxx) =0, an
Σ
K.t. (i)
(
C=0
6==0
for all j [R:]] for almost surely (X, Y). Obviously, the above equation is a polynomial of X X,
where X' is compact subset of Rdd Then, achieve that
2-2
83 (r1(a)) X + 0;) + wc(()ga. = 0,
mc.e. ())
2=
18

---

for j E [k.] are k. distinct tuples, have that ((a)) X + 05) for [k,]] are also k. distinct tuples for almost surely X. Therefore, 0/2 an?a (M))) T X + o5) gG. (Y is a linearly independent set, As w. (i) for all j E [k.]. 0 2/61| + l2 S and hl S. 1.
for all j E [lx]] and Ç E 10, for almost surely (X,Y) Again, as
result, Me..
(i) (2
Hence, the proof is completed.
A.2 Proof of Theorem
In this proof, we adapt the framework in Appendix [A.1 to the setting of Theorem 2 However, since the arguments utilized for the global version part remain the same (up some changes of notations) for the over-fitted settings, they will not be presented here again. Thus, we focus only on proving the following local inequality:
lim inf (e): D=(G,G-)S=
O.
(27)
c-4
Assume that the above claim is not true, then there exists a sequence of mixing measures G, := DKn, exp( ar. E (O)))) such that
(xG, SG. 9o. (1X))i/ G.) + 0, D2(Gnn G.) + 0,
when n tends to infinity. Since the proof argument is asymptotic, we also assume that k, = k' for all n 2 1. Following the proof argument of Theorem Jin Appendix(A.] we also assume that the Voronoi cells Aj A, does not change with n for all j E [k:]] Additionally, since D2(G,, G.) + O, we have (a." 6i, ) (aj, bi, v3)) for any E A, as approaches infinity. Furthermore, there exist t E E and l2 E Id such that EiEA, exp(X%) + exp( + (1) and Si + Bi + t2 for any i A, and j E [k.]] Then, we can upper bound the Voronoi loss function D2 as D2 G.) S D2 G.). where
Di G.) ==
Σ Σ
exp((6i) (1(4,, A03)) + l[ Do A0t))) (10(/11112
;:1,,1>1 1 iEA
Σ exp (( Daij. Ab Ao || + AAEIEEE
exp( - exp(8ts + +t1)
j=1 EEA,
in which
A Bi. = S7. - -Bi, - 122
Aa == a - aj.
bbùj = 6.- - -b,, Ao = of¹ -oj.
Recall that Ex (9Ga. (-IX), 9a. (- XX)]]/2(Grr, (.). - 0 a + co, which leads to
Ex[V (- (c))
(C,,,, Gw) +0
Step 1: Density Decomposition
In this step, we decompose the quantity Qn = 1 : exp(( +12) T X Bog +t1]l (X
9G. (YIX)] with abuse of notations in Appendix A.] follows:
h.
Qn
exp( uY 87. 67, of - + t2 03.b),
j=1 AE
exp() on [o (1: - u + x
1
k.
exp(2%) exp(36; + +11)) ( [u Bi, + 12, 03, - - +12)
J=1
iEA,
= A, + B, + En:
19

---

where we denote u(Y $1. == exp(e X) x + b, and v( ==
exp(X] X)gG (Y Since each Voronoi cell Aj possibly has more than one element, we continue decompose An and B, as follows:
An = Σ
Σ
exp(
XX PI. a (,,,6,,00 - (Y pi 12, 03. 07)
3: 1
+ Σ
Σ
exp(P%i)
uY (8. -X 2,,
= An, + An,2s
and
Bn -
/= exp(
E
Σ
o( - u + +22
Σ
Σ
exp(3%))
- + +22
B,,1 + B,,2-
Now, we apply the first-order Taylor expansions to two terms A and Br. as in equations 17 and (9). while for An,2 and B,,2, we use the Taylor expansions of orders F(IAA) \) and 2, respectively, for each j |A, > 1 as follows:
exp(10)) 201a!
An, = Σ
Σ E
(Ar, (A (Abi)) jas (Do (a)))))
5/A, >1 iE 2/ + TETr
8zz
x x exp((3i) + +22 Tx)
(Y)())) ( bb + (X,,,,,,
OM
exp( (Atg x exp((3i, + 12) X)9G, (YIX) + RX,,
Bn, - Σ ;Ll,)>liEA 1-/=1
?!
Here, Iei = {a= (a:) E ENd, NO xNxN a1 + 02 L1, 03 + 2az lo |a2] } for any (2) N² such that < 2/61 + 6 < 2F(|A,)) )) while Ra and Rx(X,Y) are Taylor remainders such that (X, /)/D'(G,, G.) + when n + 0a for E {3,4].
As result, On can be represented as
k. (1
Hz
Qn Σ
Σ
The (1) X exp((Bi, + t2) x) (M((a)) x + ob
oh
24
16:00
87() X2 exp(( + T2) X) (YIX) + Σ R2 Y), (28)
with coefficients Th (j) and S (j) being defined for any j E [kx]], - 2/2 + 822 < and
(i)
0 < hrl S 1 as
exp(28)
Eies, Enetorer
204!! (Ai, )ar (AA))) (6, (2) # (Oa.
Th, T7)
EiEA, exp(36)) -xx((65 + t2),
(61, 62) = (0.,
and
exp(3()) (A,))
EiEs, 7l
hn| #1 0,
EiEa, exp(3(t) + exp( + f1);
h==
20

---

Step 2: Non-vanishing coefficients
Next, will show that not all the quantities ee ()/P2 G.) and (T) ( (Gn: G.) go to 0C. Assume that all of them vanish when tends to infinity. Then, by arguing similarly as in
equations (22 and 23
we obtain that
exp(36:) exp(665 + tt)
D2(G G.)
EEA
Σ Σ
Σ
exp exp (9t) (4))) Dati, Abyi Aot;)1 0.
j: A
Putting the above limit and the formulation of D2 G.) together, we deduce that
Σ> E exp(Sui)
( [1(4,, A (1AA,)) + II(Aa,)) 403)) A O.
D2 G.)
which indicates that there exists some index j E [k:] such that |Ay-1 1 and
Σ exp(Boi) YEA,-
(1 (I(As, Ab F[LAD + |1(aa'y ( A 0,
(G,, G.)
for all lo E RR. Without loss of generality, we may assume that j = 1. Recall that for (61, L2) No N such that 1 S [61++ + Eg S F((A1l), we have T (1) (G,, G.) + 0 as n - oc. Thus, obtain that
by dividing this ratio and the left hand side of the above equation and let l2
exp(3(t)
EiEr, EoEtgi
( 19 )a (Aa (Ab)) )as (Aoii)
20
0,
(29)
ΣiEA, exp((%: (1(A)1)T11
AbH A: + [[ Ao A0
for all (2) such that 141 + lg F(IAi))
Let us define Mn == maxieA; exp( Note that the sequence exp()%) is bounded, therefore, we replace it by its subsequence that has positive limit ph: == lim exp()).BBB, Thus, at least one among př,, for E Al, equals!
& I1. || 1 | 1/2 : EE A1} and 3,
In addition, we also define
(A,, ( //M Pie.
(Aa /M p2i
(AbR) ) M,, + P3is (Aa / m -> P4c-
Here, at least one of P1a. Pas, and Pı for E Ai equals either 1 or -1 Next, we divide both the numerator and the denominator of the ratio equation 29 by 3 té2 and then achieve the following system of polynomial equations:
Σ tE TE
1 a!!
PEP 12 P = 0,
for all (L1, E Nd x N such that 1 < |61++ lg < F(lAil). However, based on the definition of F(IA,)), the above system has no non-trivial solutions, which is a contradiction. Thus, not all the quantities T7 (i)/D G.) and (T)/P/ G.) go to 0 as
Step 3: Fatou's lemma involvement
Subsequently, we denote by m. be the maximum of the absolute values of those quantities. Based on the result Step 2, we know that 1/m, A oc. Then, by applying the Fatou's lemma as in equation (24). get that Qn/ (mm D' G+) + 0 as + co for almost surely (X,Y). It follows
21

---

from the decomposition of Qn in equation (2 that
(F(
X
exp((3i, +2) x) (Ml(a)) x + 0z,
0
2/0
H4 21)
Σ hn/=0
wy(i) X" exx + t2) X)gG. (Y|X)
for almost surely (X, Y), where me, (i) and (i) denote the limits of T2, f, D G.)] and ST (j) mm, D2 G.)) as + co, respectively, for all j E [k.], 0 S 2 + lg S 2;))
and 0 < hl & 1+ (1) By definition, at least one among 1),, Me, (5) and wy (j) is different from zero. Nevertheless, as the set
W2 X exp((Si, + +t2) X) O (a))) X + 6J 03) : [k,,, 0 2 + S 2F((AA))
Onf
U ( exp((( + t2) T (X)x) (Y : [k.]. hl S |||
(30)
linearly independent w.r.t X and Y (proof can be done similarly to Lemma 2). it follows that
(,,0a0 ()( 0,
for all j E 0 2|41+ + < (F(()))) and 0 S |1| < 1 (1A/111, which a contradiction. Hence, achieve the inequality in equation 27 and complete the proof.
B Proofs of Auxiliary Results
In this appendix, we provide proofs for the results of Proposition I and Proposition 2 in Appendix B. and Appendix B.2 respectively, while we leave that for Lemma in Appendix B.3
B.1 Proof of Proposition
Given the notations in Proposition assume that the equation (G = ga (Y|x) holds true, that is,
exp((321) TX + Bos)
f(Y((aa) X + +b,,
== exp((31)) X TX + +Bj)
exp((5(.)) X + 1b:)
[(Y((a)) + t1, (x) bby))
(31)
for almost surely (X, Y). Then, it follows from the identifiability of the location-scall Gaussian mixtures [56] (57) that the number of components and the weight set of the mixing measure G equal to those of its counterpart G", i.c. ks = and
exp((31.] T X Box)
exp((3(,) X + (b,)) Σ j=1 exp(((()) +B)
i [k]
:iE [K] 1k|].
j=1 exp((31)) Boj)
R
for almost surely X. For simplicity, we may assume that
exp(((1)))) + 8%xa) Σ exp(3,, + Boy) ΣS (xp T T + 8))))
exp((31.) x + Boi)
for all i E [k]. Since the softmax function is invariant to translation, we get that 3or = Ro: + ( and
31 = 31 + to for some t E R and to E IRd. Therefore, equation (3]) reduces to
&
exp(3u.) (Y 81 a, by o,) Σ
Σ
B1s. o6, 64, o)),
(32)
22

---

for almost surely (X,Y) Y), where u(Y Next, we will partition the index set [k] into subsets U1, U2......... Un such that for each & E [g). have exp(3oi) = exp(Sor) for any i, E Uz. As a result, equation (32) can be rewritten as
a, (1,a,,,.)) := exp( X)f(Y(a" x + b) for all i [k].
(xp(Bo))(((1x;))) 0.)
8=1 sEUe
(=liEUr
for almost surely (x, Y). Given the above equation, for each E [q]. we obtain that {((a.) X b, o.) i U2} {((a)) X + (1 de Ut). for almost surely X, which directly leads
{la by, 0.): Uz} = {(d of) : Ut).
WLOG, assume that (a;, oz) (0/, 1/ of) for all E Up. Consequently,
(xp(3)x)0(111101 E= LEU
exp( + t1)8 tb,
8= iEU2
or equivalently, G = G Hence, the proof is completed.
B.2 Proof of Proposition] 2
Our proof will be based on the convergence rates of density estimation from MLE in Theorem 7.4 in
[58] Before stating this result here, let us introduce some necessary notations. Firstly, let Pa (+) be
the set of conditional densities of all mixing measures in Ox(0), i.e., (+ = (ga G
O₂ (+)). Additionally, we define
(0) =
G :
(0) 1/2 ( e o
Next, for each 0 O, the Hellinger ball centered around the conditional density go. (Y)(Y and intersected with the set P/./2 (9) is denoted by
/1/²
= {0-0 0)
( {..
Finally, in order measure the size of the above set, 58 proposes using the following quantity:
JB(6,Pl/2 = [
822/20s H (t, P (t, (0,t). dt v
(33)
where (I, (1/1,,)///( (0, (0,1),11 11- -1) denotes the bracketing entropy
(0, u) under the 2-norm, and V = max (1, 03. Now, we are ready to recall the statement of Theorem 7.4 in 58):
of /1/2((
( Theorem 3 (Theorem 7.4, (58.. Take (6) > J8 /1/2 (O, 8)) that satisfies 4 (5) is non-
increasing function of Then, for some universal constant and for some sequence (8,) such that yno, 2 cll (8,), we achieve that
P P(xx (41 2) < cexp
nd²
for all 8 ' 8n-
The proof of this theorem can be seen in [58
Proof of Proposition
Back main proof, since
(t $1/2 (0, I)) <
23

---

for any & > 0, it follows from equation
33 that
6
JB(6,PH -
(L dt 8 /21/213
log(1/t)dt V V6,
62/223
where we apply the upper bound of bracketing entropy in Lemma 3 (cf. the end of this proof) in the second inequality. Let (6) = [log(1/6)) we have (6) is a non-increasing function of A. Moreover, the above equation deduces that (Ø) 2 Jo(ō, Pk 7 (O, 6)). Additionally, let 6n = /l, we have that vnd,, (V))))) for some universal constant c. As the assumptions are met, Theorem gives us
P(Ex [h(ga, (-IX), 9G. (-X))) C(log(n)/n) exp(-clog(m))
for some universal constant C' that depends only on θ.
For completion, will provide the result regarding the upper bound of bracketing entropy in the following lemma:
Lemma 3. Assume that O bounded set, then the following inequality holds true for any 0 S E $ 1/2:
Hn(s,Pa(90)) log(1/s).
Proof of Lemma 3
Firstly, we will establish an upper bound for the univariate Gaussian density f(Y X + b)) Since both X' and bounded sets, there exist positive constants K. u, é such that a X S K. and l I As result,
exp (- ( h1)²
x
22Th2
2h2
v
2
For any | 2x, we have that (
2
y²
which leads to
2h2
8u
Y2
f(Yla x xb)0) S exp
V2
8u
Putting the above results together, we obtain that S(Yla T + b, S K(Y[X), where we define y2
X(YIX) = V2रl
- exp
if Y 2 2x, and ((YIX) = V2sl otherwise.
Suz
Subsequently, let 17 S E, assume that the set (e) has 17-oovrr (under fn-nor denoted by
(TI...., nN), where N == (n, Px (+), || II1) is known as the -7covering number of (e))). Then, will build up the brackets of the form (1
for all i [N] follows:
XX) = (T. (Y - 77, 0},
M (Y max m (Y [X) + 17, (X))
Consequently, it can be checked that (O) U [ (Y u4: (Y|X)) with a note that yu: (Y]X)
4s (YIX) & min K(YIX)} Next, for each i E [N], we attempt to give an upper bound for
|| rill 1 |
(HI(IIX) (X d(x,Y)+ /
(mi(1)x) vx(Y d(X,Y)
1
R2
Rn exp
< R'n,
2u
where R : max{2k, v Vu) log (gg())) and R' is some positive constant. By definition of the bracket- ing entropy, since H (R'1,, Pa (+) -IIi) is the logarithm of the smallest number of brackets of size R'1 necessary to cover Pk (9), we achieve that
Hn(R'n, n, (x()), 11) S log = log (m Pa(O), II)))
Assume that the following upper bound for the covering number log (N, Px(O), [I1) log(1/n) holds true (proof is provided below), then the above result leads to
Hp(R'n Pa(O). |I Il)) S log(1/n).

---

By selecting e/ Hellinger distance is upper bounded by the L'-norm, we reach the desired conclusion:
e/R', R', we receive that Hø(e, (+), I1l x log((/E).. Furthermore, since the
(E(E, Px((), h) log(1/e).
Upper bound of the covering number. For completion, we will establish the following upper bound for the covering number, i.e.,
log (n, Px()), || 111) E log(1/n).
Let us denote A (3p. 31) E Rx (8o, 31, b, o) ) and {(a, (, R (Bo, B1, a, o) E }}. Since θ is a compact set, A and Ω are also compact. Thus, we can find g--oovers An and Q2 for and f2, respectively. It can be verified that A I On) (d+1)k) and [Syl S (1)-2k)))
For each mixing measure G = E ex E On(O), we consider another one denoted by G = Σ exp(Sui) ( (..,.. where (āz, b,, E Sy such that (ā,, b, T.) are the closest to (a;, bi, 0z) in that set for all i [k]. In addition, we also take into account the following mixing measure G Σ exp(3 )6 (B, (o,))") where (BocBBaa) An are the closest to (Bor, 31x) in that set. We can verify that the conditional density D0 belongs to the following set: R: (gG Px(()): (Bor, 31.) E A,; (a,, o;) E S2y Vi E [A:]
exp(STTX + Box) From the formulation of Ō Σラ exp + Baz)
Let us denote Softmax (3 + Bus)
get the following bounds:
llga -all1 Σ
/ Softmax(3].x Boi) (()((a)) bz) f(Y)(a)) x + b oz) dx
J [(Y((a))) [ (x, (a.) TX b bi
h Σ (1 - a.ll + 16: -bl +0, o.
Sn. where the second inequality follows from the facts that X is a bounded set. Note that Softmax is a Lipschitz function with Lipschitz constant L > 0. Additionally, since X' is a bounded set, there exists a constant > 0 such that || < B for any X E X. As a result, we get
(34)
Softmax(3TTxx Box) Softmax(B,,xx + Boo) ((M(()) x + b,, /
ll9a -tall Σ
/ (1811-B,e) - ||X|| 1,os Bosl) dx
Lkhn + 1),
(35)
where the second inequality follows from the fact that Softmax is Lipschitz function and the Gaussian density (T) X - by. σ.) is bounded. Putting the bounds in equations (34) and (35
together with the triangle inequality, we receive that
1|9. - g1l1 S | 9alli + l19a gell S 1) which means that R is an covvee (not necessarily smallest) the metric space (Pa(0), [1)). By definition of the covering number, we know that
.V (7) (e),,, ||- Il1) < | = |An x 10y1 < O(n (d+1)/) Ofr O(n (2d+3)k),
which implies that,
log (n, Px))), (l,o) S log(1/n).
Hence, the proof is completed.
25

---

B.3 Proof of Lemma 1
First of all, let us recall the system of polynomial equations of interest here:
Pij P2j P3j
P4j 0,
(36)
a1 a2 az! aq!
where In, far 02, 03, 04) E Nd x No x an + = L1, + 2014 l2 - -la2
for any (2) E No x N such that 0 & 14 S r. 0. rr 14 and L + f 2 1.
In this proof, we denote Pıj (piji, Ply2, Pijd) and p2j (p251, P252. ..... P2jd)-
When m 2: By observing a portion of the above system when & Oz, which given by
Paj
C2 P3i PA5
Σ
Σ ta
0,
82 1,
(37)
Org! or4!
follows from Proposition 2.1 in 28 that the smallest natural number such that the system 37 does not have any non-trivial solutions when = 2 is = 4. It is worth noting that solution of the [28] if all the values of ps; are different from zero, whereas least one among Paj is non-zero, which aligns with our definition of non-trivial solutions for the system 36.. Thus, we get F(m) < 4, and it suffices to demonstrate that F(m) > 3. Indeed, when
system 37 is considered non-trivial
r the system in equation (36) be written follows:
Σ 3=1
ph Pip = 1AA [d].
Σ J=1
Poj = 0,
2
Σ
Poy (P2ju + PijoPaj)
2
0 Vu, v E [d].
==1
1
1
PiJPiiuPijo = 0 vvu [d].
2
P5)
Píj 2
2
+ p4j)
0,
>
P5
P1 Paj
31
+ PsSPAN) 0.
j=1
m
Σ
p Pi Pl = Vu, u, [d],
Σ
Poj P +
2
0 Vu, E [d].
1=1
j=1
m
(prij pág + PijeP45 P2)(P3))
Vu, v. u, E [d].
j=1
(38)
can be seen that the following non-trivial solution of the above system: Psj = 1,,1 = P2j = 0.
for all j E [m], Ps1 = 1, P32 = 1, P41 = P42 = - Therefore, we obtain that F(m) > 3, which
leads to F(m) = 4.
When m 3: Note that F(m) a monotonically increasing function of m. Therefore, it follows
from the previous result that F(m) > F(2) = 4, or equivalently, F(m) > 5. Additionally, according to Proposition in (8), we deduce that F(m) S based on the reduced system equation (37).
Thus, we only need to show that F(m) 5. Indeed, the system (36) when 5 is combination of
26

---

the system in equation 38) and the following system:
m
P5 Pl Pll.uPPtoPPPPPPP 0 Vu 8, L, [d].
Σ 1=1
m
P5j P. +
2: P:Psiprs + 21) 0,
1
1=1
P5j 3 PijuP's + P1juPojp4s + 27 P2slss + p2j - 0 U,, [d],
j=1
Plju PhjuaPl + 21 Pijen =0 (0
(v:) [d]
Poj
3
j=1
1
P5j
Plju, Pljur
2! PlusPtjuu + Pijus = =0v(u)= [d].
2!2!
/=1
Σ
Piju, = OV(())= E {d]s
3=1
1=1
5
PajPaj + 21 psjpás) 0,
P5j
5!
P3)
+
31
==1
Σ 1=1
Pas [
PomPPs + Pinu
1
2!
Pijug
Paj
+ P2jusPsj 3
3.
1
+ Pejn,PasPij
Y(u)) E E(ds,
7
Σ
P&j 41
Piju, P3j
+
P2jus) Piju,,2jus)
Pija,
0 ((u)) E [d].
3!
j=1
1=
II
P2as +p4s) + II P2ju.
1
Pis
P Piju Paj +
P1ju.Ps54s + Pajus
213!
1=1
v(u)) ==1 [d]s
172
Piju. Paj + II
1 P4j 21 Pijur + 21 Pijup
P6a
P2ju:
3322
==10
((4)
11 E Id"
We can verify that the following is a non-trivial solution of this system:
Psy = 1,
Pıj = P2j = 0d
Vj E [m]]
v3
v3
P31 3
P32
P33 0,
P41 = 6'
0.
Hence, conclude that F(m) 6.
C Experiments
In this appendix, we conduct a simulation study to empirically validate our theoretical results on the convergence rates of maximum likelihood estimation (MLE) the softmax gating Gaussian mixture of experts established in Theorem [ and Theorem 2
C.1 Numerical Schemes
We illustrate the heterogeneity convergence rates the MLE under the softmax gating Gaussian mixture of experts via exact-fitted and over-fitted models, which correspond to the exact-fitted
27

---

respectively. For each case, we let X be uniformly distributed over [0, 1] and we generate observations Y from the conditional density ga. (Y] of softmax gating Gaussian mixture of experts model in equation ① Here, the true mixing measure G. Ei= (xp(( 07 where k. is specified as follows:
and over-fitted settings described in Sections 3.1 and 3.2
01 8, 81 = 25,
aj -02
bj 15, of ===0., 0.3,3
P6 0, i 0,
= 20, b -5, 5, 02 0.4.
Then, we compute the MLE G₁ w.r.t. number of components k for each sample. For both of these settings, we choose k E (k.,,, + 1.k, + +2 In order to perform the MLE, we use numerical scheme based on the EM algorithm [12] similar to the one used by Chamroukhi et al. 7 g. Note that the main difference with a classical EM is in the maximization step, as there are no closed formulas for updating the softmax gating parameters (5nr Bia), Vi E [k]. For this purpose, following the results Chamroukhi et al. 77 [ see also 38 10 23,, we use a multi-class iterative reweighted least-squares algorithm. All code for our simulation study below was written in Python 3.9.13 on
standard Unix machine.
We choose the convergence criteria e = 10-6 and 2000 maximum EM iterations, Our goal is to illustrate the theoretical properties of the estimator G., Therefore, we have initialized the EM algorithm in a favourable way. More specifically, we first randomly partitioned the set {l....,A k} into k. index sets JI,..., JR.. each containing at least one point, for any given k and k. and for each replication. Finally, we sampled 3i, (resp. aj, 65,66,.00 0)) from a unique Gaussian distribution centered on B (resp. at, 65, of), with vanishing covariance that j Jr.
C.2 Empirical Convergence Rates
The empirical mean of discrepancies D2 and D: between G₁ and G., and the choice of & for exact- fitted and over-fitted models are reported in Figures and 2 respectively. can be observed that the average discrepancies from G to Go vanish at a rate of (n (n-1/22 up to a logarithmic factor, as envisaged by Theorems | and 2 Although these empirical rates of convergence are similar for the two models, they imply that the convergence behaviour of the individual fitted parameters is very different in an over-fitted setting, which was already discussed in more detail in the Section 3.2
C.2.1 Exact-fitted Model
We generate 40 samples of size for each setting, given 200 different choices of sample size n between 102 and 10.. The empirical parametric convergence rate of the MLE to G- under the metric Di in Figure i consistent with the theoretical rates of estimating the true parameters exp( S1; (up to translation), a; 6j of for E [k.]], which are of order O(n -1/2) to logarithmic factors.
C.2.2 Over-fitted Model
In the over-fitted setting, we generate 40 samples of size for each setting, given 200 different
choices of sample size between Mmin R 14 * 10 for k = k, + 1. Remin ~ 27 10 for A = k. + 2 and mmax 10 To the best of our knowledge, there is still a lack of theoretical understanding of EM performance, in particular an established algorithm that enjoys global convergence for the parameter estimation of the over-fitted softmax gating Gaussian mixture of experts. The most related theoretical results are only for the mixture of expert with covariate-fres gating networks in [1 40 42 This explains why in F over-fitted setting, we have not plotted the error bar due to the instability of the EM algorithm for finding the global solution. Moreover, the sample size must be large enough so that the empirical behaviour of the MLE from the EM algorithm matches the theoretical rate of order O(n 1/2) up to a logarithmic term.
28

---

1.9n 0.50049
D1 Di(G G+)
0-
-1
log(loss)
-2
-3
-4
8
10
log(sample size)
Figure 1: Log-log scaled plots of the simulation results for exact-fitted setting. We compute the estimator G, on 40 independent samples of size n between 102 and 10 We plot its mean discrepancy from the true mixing measure in red, with error bars representing two empirical standard deviations. We also plot the least-squares fitted linear regression line of these points in black dash-dotted line.
4.9n -0.006
5.7m 0.40207
3-
Dy(G,, G.)
3-
Dy(G,n G.)
log(loss)
log (loss)
w t
0-
-1
10.0
10.5
11.0
11.5
10.25
10.50
10.75
11.00
11.25
11.50
(sgmsaee size)
log (sample size)
Over-fitted
Renin 14070
(b) Over-fitted, & Roin 26733
Figure 2: Log-log scaled plots of the empirical mean of the discrepancy D2 between G and G. (red curves) and least-squares fitted linear regression (black dash-dotted lines) are shown using 40 independent sample sizes n between Amin and 105.
29


Reviews:
[{"review_id": "18RhOgLcyh", "reviewer": "Reviewer_PaPA", "summary": "This work considers the problem of parameter estimation for the **softmax-gated mixture of Gaussian experts**. For simplicity, first consider the case in which the mixture weights do not depend on the covariates X. Then, this model can be seen as a mixture of linear regressions where each “regression component” is corrupted by Gaussian noise. The paper considers the much more challenging case where the mixture weights depend on the covariates. The mixing weights are modeled as linear functions which are normalized by applying softmax to the vector of mixing weights.\n\nThe paper proposes a novel \"Voronoi distance\" for the parameter space, which takes into account the invariances of the parametric model, and is used to determine convergence rates for the maximum likelihood estimator (MLE). In the well-specified case where $k$, the number of components of the model used, is equal to $k^*$, the true number of components, the MLE parameters converge at the parametric rate $n^{-1/2}$. In the overparametrized case where $k > k^*$, the rates of the component parameters are slower and depend on how many components of the overparametrized model fall inside the Voronoi cell of the true model’s components.", "questions": "- The authors mention in Section 1 that understanding the parameter estimation problem for mixture of experts models has been a long-standing open problem. Could the authors provide explanation for why this was the case? What were the technical barriers and what recent technical advances or breakthroughs have paved the way for the results established here?\n- Which aspects of the Voronoi distances are novel? Assigning the model’s components according to the Voronoi cells of true components seems like a natural thing to do for any mixture model. Is it the \\inf over translations of the mixing weights? Or the rate functions r(m) related to the system of polynomial equations?\n\n**Editorial comment**\n\n- In the introduction, it would motivate the paper’s result more if the authors provided simple and practical examples showing the importance of parameter estimation in this particular mixture of experts model rather than just estimating the density. Perhaps there are examples in which the parameters in the mixture of experts model are interpretable and have practical value?\n- Typo. First paragraph of Section 3.3. Total variation distance should be V not h.\n- It would be helpful to explain what mixing measures when they are first introduced in Section 1. Perhaps after Eq.(1) in the **Problem setting** paragraph.", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The paper overcomes significant technical challenges that come from using softmax gates for the mixing weights. The main contribution of the paper is showing that the expected total variation distance of the MLE’s conditional distribution $\\hat{p}(Y|X)$ from the true conditional distribution $p(Y|X)$ is *lower bounded* by the proposed Voronoi distance. The Voronoi distance takes care of the inherent symmetries of the parameter space. For example, the mixing weight parameters can only be identified up to global translations due to the softmax operation.\n- Since one can show that the expected TV distance of the MLE converges at the parametric rate $n^{-1/2}$ by computing the bracketing number of the parametric family [van de Geer, 2000; Theorem 7.2], this leads to an upper bound on the Voronoi distance and thus the $\\ell_2$ distance of the MLE parameters. \n- To be more precise, the paper proposes a family of Voronoi distances, for both the well-specified case and overparameterized case. The convergence rates for overparametrized cases are determined implicitly by a system of polynomial equations which in turn come from analyzing the Taylor expansion of the model’s conditional density w.r.t. the parameters.", "weaknesses": "**Exposition.** Though the technical contributions of this paper are solid, its exposition could be improved to make it more accessible to non-expert readers.\n\n- **System of polynomial equations (Section 1).** The full details of the system of polynomial equations in the introduction is difficult to follow and seems unnecessary since it is reproduced in Section 3. It would be easier and less intimidating for the readers if the authors omitted the full details and simply noted that $r(m)$ is related to whether some system of polynomial equations admits no non-trivial solutions. Then, one could end with “we conjecture r(m) = 2m, and establish this for the first few cases m=1,2,3, in Lemma 1.” It would also be great if the authors could provide more explanation for how one arrives at these polynomial equations.\n- **Computation of the Voronoi loss function (Section 3.2).** This would fit better in the experiment section. In typical estimation settings, we do not have access to the true parameters anyway. This quantity is only computable in synthetic settings where the experimenter knows the true parameters.\n- **Practical implication paragraphs.** These paragraphs in Section 1 and Section 3.2 are redundant.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1: The full details of the system of polynomial equations in the introduction are unnecessary and should be omitted. Instead, the authors should briefly introduce the quantity $r(m)$ and its properties. Additionally, how do the authors arrive at these polynomial equations?**\n\nThanks for your suggestion, we will consider it and edit our paper accordingly. Regarding the derivation of the system of polynomial equations, please refer to parts (ii) and (iii) of the Common Question 1 in the General Response section for brief explanation. For further details, ones can refer to Step 2 of the proof of Theorem 2 from line 629 -649 in the supplementary material for further details.\n\n**Q2: Regarding the computation of the Voronoi loss functions, since we do not have access to the true parameters in typical estimation settings, these functions are only computable in synthetic settings where we know true parameters.**\n\nWe agree with the reviewer that our proposed Voronoi loss functions are only computable when ones have access to true parameters. However, we would like to emphasize that the important feature of the proposed Voronoi losses is its ability to provide exact convergence rates of individual parameters of the MLE, i.e., we know the separation among the estimated parameters based on their distances to the true parameter or how small the weights of certain experts to 0 (see our response to Q5 for more details). From the practical perspective, these characterizations of separation among estimated parameters or the values of weights of experts give insight into the thresholds to merge these parameters when they become too close or truncate certain experts when their weights are too small. This procedure yields a useful method to reduce the complexity of the Gaussian mixture of experts and consistently determines the correct number of experts when the sample size is sufficiently large.\n\n**Q3: The practical implication paragraphs in Section 1 and Section 3.2 are redundant.**\n\nThanks for your comment, we will consider removing the practical implication paragraph in Section 3.2 in the revision of our paper. However, we may keep the one in Section 1 as it provides an insight of how to choose the number of experts to achieve the best possible convergence rates of parameter estimation and connection to the merge-truncate-merge procedure, which is used to estimate the true number of experts.\n\n**Q4: Could the authors explain why understanding the parameter estimation problem for mixture of experts models has been a long-standing open problem? What were the technical barriers and what recent technical advances or breakthroughs have paved the way for the results established here?**\n\nThanks for your questions. We would like to refer you to Common Question 1 in the General Response for further details.\n\n**Q5: Which aspects of the Voronoi distances are novel? Is it the $\\inf$ over translations of the mixing weights? Or the rate functions $r(m)$ related to the system of polynomial equations?**\n\nThanks for your question. Our proposed Voronoi loss functions are considered novel since they are able to characterize accurately the estimation rate for each parameter. In particular, from our Theorem 2, we know that the Voronoi loss $\\mathcal{D}_{2}(\\widehat{G}_n,G*)$ converges to zero at a rate of order $\\mathcal{O}(n^{-1/2})$ (up to some logarithmic term). \n\nThen, it follows from the formulation of this loss that for each $j=1,2,\\ldots,k_*$, \n\nall the resulting estimation rates for parameters $\\beta^*_{1j},a^*_{j},b^*_{j},\\sigma^*_{j}$ depend on the quantity $\\bar{r}(|\\mathcal{A}_j|)$, which possibly admits distinct values for different indices $j$. More specifically, if two Voronoi cells $\\mathcal{A}_1$ and $\\mathcal{A}_2$ does not share the same cardinality, i.e. $|\\mathcal{A}_1|\\neq|\\mathcal{A}_2|$, \n\nthen the estimation rates for $\\beta^*_{11},a^*_1,b^*_1,\\sigma^*_1$ are different from those of \n\n$\\beta^*_{12},a^*_2,b^*_2,\\sigma^*_2$, respectively. \n\nBy contrast, if we adopted the Wasserstein loss as in [1], the estimation rate for \n\n$\\beta^*_{1j}$ (resp. $a^*_j,b^*_j,\\sigma^*_j$) \n\nremains unchanged for any $j=1,2,\\ldots,k_*$, which is not accurate.\n\n**Q6: In the introduction, the authors should provide simple and practical examples showing the importance of parameter estimation in this particular mixture of experts model.**\n\nThanks for your suggestion. Mixture models and mixture of experts are well-known for modelling heterogeneous data, and they are commonly used in medicine [2] and physical sciences [3]. In these applications, mixture parameters play a vital role in capturing the heterogeneity of the data, thus, the main objective in [2, 3] is to conduct statistical inference for those parameters. This leads to a need for determining the convergence rates for parameter estimation in mixture models and mixture of experts. We will add this discussion to the revision of our paper. \n\n**Q7: Typo. First paragraph of Section 3.3. Total variation distance should be $V$ not $h$.**\n\nThanks for pointing out, we will correct it in the revision of our paper.\n\n**Q8: It would be helpful to explain what mixing measures are when they are first introduced in Section 1.**\n\nThanks for your suggestion, we will add the definition of a mixing measure to the revision of our paper. Basically, a mixing measure is referred to as a mixture of some measures. For instance, in line 53 of our work, since $G_*$ is defined as a mixture of Dirac measures, it is called a mixing measure.\n\n**References**\n\n[1] N. Ho, C.-Y. Yang, and M. I. Jordan. Convergence rates for Gaussian mixtures of experts. Journal of Machine Learning Research, 2022.\n\n[2] Q. Li, R. Shi, and F. Liang. Drug sensitivity prediction with high-dimensional mixture regression. PloS one, 2019. \n\n[3] Kuusela, M. Semi-supervised anomaly detection—towards model-independent searches of new physics. In Journal of Physics: Conference Series, volume 368, 2012."}, {"review_id": "ia6Bm4fMTM", "reviewer": "Reviewer_q5b3", "summary": "This paper studies convergence rate of Maximum Likelihood Estimate (MLE) of parameters of Gaussian mixture of experts with softmax gating. Unlike some of the previous papers, the authors allow for the gating probabilities to be input dependent. Convergence rate (upper bound) is provided for both the setting where the number of components is known, and when only a lower bound is known. For the latter case, the authors show connection between the MLE convergence rate and solvability of a central system of polynomial equations.", "questions": "* With the problem of identifiability, what happens if we introduce some penalty ($\\ell^1$, $\\ell^2$)? I was surprised that this (perhaps naive) solution was not discussed in the background section or anywhere else.\n\n* Could you make more explicit how the level of separation between individual components of the ground truth impacts the convergence rate? Intuitively, the more separated, the easier the estimation problem should be.\n\n* Potentially related question: What do you mean when you say that a particular Voronoi cell contains only one component of the MLE? Isn't the MLE a random variable? (Wouldn't that imply that the identity of cells which have only one component changes? Also what about the cells which have zero MLE components in them?)", "limitations": "N/A", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "* Makes progress on a difficult problem complicated by lack of identifiability and complex interactions between parameters of the gating mechanism and of the individual components. \n\n* Proposes a new \"Voronoi loss\", which lower bound the Hellinger distance, and is crafted to capture properties of the mixture of experts model (the involved Voronoi cells roughly correspond to the subsets of the input space dominated by a particular expert under the ground truth). \n\n* AFAICT provides the first MLE rates for models where the gating mixture is input dependent.", "weaknesses": "* As someone with only cursory understanding of the area (emergency reviewer), the paper was hard to follow and full of technical detail that to me felt like obfuscating rather than facilitating understanding.\n\n* Unclear what can a practitioner take away, except that they should set the number of components as low as possible. (This is a very minor weakness, as I don't think every paper needs to have direct application.)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1: As someone with only cursory understanding of the area, the paper was hard to follow and full of technical detail that to me felt like obfuscating rather than facilitating understanding.**\n\nThanks for your comment. We would like to refer you to Common Question 1 in the General Response to understand our paper better.\n\n**Q2: Minor issue: Unclear what can a practitioner take away, except that they should set the number of components as low as possible.**\n\nThank you for raising your concerns. In fact, there are two other important messages: (1) The slow convergence rates of the MLE may provide important thresholds for the merge-truncate-merge procedure, a procedure that has been used to estimate the true number of components in standard mixture models [1], to consistently estimate the true number of experts $k_*$ in our mixture of experts; (2) We also illustrate the heterogeneity convergence rates in the MLE for solving the parameter estimation of the softmax gating Gaussian mixture of experts via exact-fitted and over-fitted models. Although these empirical rates of convergence are similar for the two models, they imply that the convergence behaviour of the individual fitted parameters is very different in an over-fitted setting, which is already discussed in more detail in the Section 3.2 of our paper.\n\n**Q3: With the problem of identifiability, what happens if we introduce some penalty $(\\ell_1,\\ell_2)$?**\n\nThank you for your question. As far as we know, we are not sure if introducing a penalty $(\\ell_1,\\ell_2)$ will solve the identifiability problem. Furthermore, proof techniques should be further developed to extend our proposed approach to these settings in order to establish the convergence rates for the parameter estimation problem in penalized mixture of experts.\n\n**Q4: Could you make more explicit how the level of separation between individual components of the ground truth impacts the convergence rate? Intuitively, the more separated, the easier the estimation problem should be.**\n\nThanks for your question. In this work, we do not take into account any assumptions on the level of separation between ground-truth parameters. Moreover, it can be seen from Theorem 1 and Theorem 2 that the estimation rates for ground-truth parameters are independent of that separation level. Instead, under the over-fitted settings, those estimation rates depend on the solvability problem of a system of polynomial equations. For instance, Theorem 2 implies that a true parameter $a^*_j$ has an estimation rate of order \n\n$\\mathcal{O}(n^{-1/\\bar{r}(|\\mathcal{A}_j|)})$ (up to some logarithmic term) \n\nfor any $j\\in\\{1,2,\\ldots,k_*\\}$. \n\nSince $\\bar{r}$ is a monotonically increasing function of $|\\mathcal{A}_j|$, then the lower the cardinality of the Voronoi cell $\\mathcal{A}_j$ is, the better the previous estimation rate for $a^*_j$ becomes.  \n\n**Q5: What do you mean when you say that a particular Voronoi cell contains only one component of the MLE? Isn't the MLE a random variable? (Wouldn't that imply that the identity of cells which have only one component changes? Also what about the cells which have zero MLE components in them?)**\n\nThanks for your question. We would like to emphasize that as the MLE $\\widehat{G}_n$ is a random variable, \n\nthen the Voronoi cells $\\mathcal{A}^n_j$ for $j\\in\\{1,2,\\ldots,k_*\\}$ corresponding to the MLE are also random.\n\nUnder the over-fitted settings, the number of components of the MLE $\\widehat{G}_n$ \n\nis strictly larger than that of the true mixing measure $G_*$, i.e. $\\widehat{k}_{n}>k*$. \n\nThus, according to the pigeonhole principle, there must exist some Voronoi cell having at least two elements. Additionally, we could also find some Voronoi cell $\\mathcal{A}^n_j$ which has only one element $i$, and this element corresponds to the component $(\\widehat{\\beta}_{1i},\\widehat{a}_i,\\widehat{b}_i,\\widehat{\\sigma}_i)$ of the MLE. This is what we mean when we mention a Voronoi cell which contains only one component of the MLE.\n\nRegarding the question about Voronoi cells having zero MLE component, we get from Theorem 2 that the Voronoi loss $\\mathcal{D}_2(\\widehat{G}_n,G*)$ converges to zero as $n$ goes to infinity. \n\nThen, it follows from the definition of this Voronoi loss that $(\\widehat{\\beta}_{1i},\\widehat{a}_i,\\widehat{b}_i,\\widehat{\\sigma}_i)$ converges to\n\n$\\(\\beta^*_{1j},a^*_{j},b^*_{j},\\sigma^*_{j})$ for any $i\\in\\mathcal{A}^n_j$ and $j\\in\\{1,2,\\ldots,k_*\\}$. This result implies that each Voronoi cell $\\mathcal{A}^n_j$ must have at least one element.\n\n**References**\n\n[1] A. Guha, N. Ho, and X. Nguyen. On posterior contraction of parameters and interpretability in Bayesian mixture modeling. Bernoulli, 27(4):2159–2188, 2021.  "}, {"review_id": "j7yhHqEUPm", "reviewer": "Reviewer_txMC", "summary": "This paper establishes convergence rates for parameters (Gaussian mean / variance and expert weight) for softmax Gaussian mixture of experts. The rates depend on the setting: exact-fitted vs. over-fitted. The solutions are in terms of Voronoi losses and Hellinger distances.", "questions": "My main question is regarding the significance of the result and connecting the result to practical empirical settings — what can be done to make this connection clearer?", "limitations": "The authors have adequately addressed the main limitations of their work in the Discussion section of the paper.", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "**Originality**\n\nTo the best of my knowledge, this paper is the first to provide convergence rates for softmax Gaussian mixture of experts, making it an original paper. Likewise, the methodology for obtaining this result involves a rather involved setup, which struck me as highly non-trivial, again, supporting claims of originality. Of course, this is not my area of expertise, so it is difficult for me to accurately assess these points.\n\n**Quality**\n\nI believe the quality of the paper is strong. The authors provide a thorough description of the setup for softmax Gaussian mixture of experts, with rigorous proofs for the cases of exact-fitted and over-fitted number of experts. I have not assessed the quality of the proofs in the appendix.\n\n\n**Clarity**\n\nDespite tackling a complex theoretical problem and proposing a fairly involved solution, I found the paper was presented well. Terms are defined clearly, and the authors walk the reader through the main results before diving in to more detail.\n\n**Significance**\n\nThe results seem marginally significant, as the authors claim that they have some practical implications for setting the number of experts and post-processing techniques, like merge-truncate-merge. However, fully demonstrating these practical insights, as well as empirical verification of the convergence rates, are not included in the paper, somewhat limiting their significance.", "weaknesses": "I have several concerns regarding the **significance** of the results.\n\nFirst, these results target the convergence of the softmax mixture of expert parameters, however, in practical settings, I would imagine that these parameters are the outputs of deep networks, which may complicate the convergence picture.\n\nSecond, the convergence results are derived by considering the number of “true” experts, however, it’s unclear to me whether there is a notion of a “true” expert, particularly if the parameterization is used inside of a neural network / model to model a latent variable.\n\nFinally, while I understand that this is an entirely theoretical paper, connecting it more closely to the practical settings in which softmax mixture of experts are used would help to more clearly demonstrate the significance of the paper. For instance, even if it’s in a toy setting, is there any way to empirically verify the convergence rates for exact-fitted vs. over-fitted setups?\n\nRegarding **presentation**, I found the paper overall quite clear given the complexity of the result. However, some diagrams (there are none in the main paper) could possibly fill in any gaps in the reader’s understanding. For instance, diagrams showing the softmax Gaussian mixture of experts setting, as well as other concepts, like Voronoi cells, Hellinger distance, etc., would be useful additions to the paper. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1: The paper targets the convergence of the softmax mixture of expert parameters, however, in practical settings, I would imagine that these parameters are the outputs of deep networks, which may complicate the convergence picture.**\n\nThanks for your question. Regarding the softmax gating Gaussian mixture of experts with general expert functions (including deep neural networks), the conditional density of $Y$ given $X$ is given by\n$$g_{G_*}(Y|X):=\\sum_{i=1}^{k_*}\\dfrac{\\exp((\\beta^*_{1i})^{\\top}X+\\beta^*_{0i})}{\\sum_{j=1}^{k_*}\\exp((\\beta^*_{1j})^{\\top}X+\\beta^*_{0j})}f(Y|h_1(X,\\theta^*_{1i}),h_2(X,\\theta^*_{2i})),$$ where $f(\\cdot|\\mu,\\sigma)$ denotes a Gaussian density with mean $\\mu$ and variance $\\sigma$, while $h_1:\\mathcal{X}\\times\\Theta_1\\to\\Omega_1\\subset\\mathbb{R}$ and $h_2:\\mathcal{X}\\times\\Theta_2\\to\\Omega_2\\subset\\mathbb{R}^+$ are referred to as expert functions which can be chosen as deep neural networks.\n\nWe call that $h_1$ and $h_2$ are algebraically independent if they are twice differentiable w.r.t their parameters $\\theta_1\\in\\Theta_1\\subset\\mathbb{R}^{q_1}$ and $\\theta_2\\in\\Theta_2\\subset\\mathbb{R}^{q_2}$, and all the following sets are linearly independent w.r.t $X$:\n\n(S.1) $\\{\\dfrac{\\partial h_1}{\\partial\\theta_1^{(u)}}(X,\\theta_1)\\dfrac{\\partial h_1}{\\partial\\theta_1^{(v)}}(X,\\theta_1), X^{w}\\dfrac{\\partial h_2}{\\partial\\theta_2^{(z)}}:1\\leq u\\leq v\\leq q_1, 1\\leq z\\leq q_2,0\\leq |w|\\leq 1\\}$,\n\n(S.2) $\\{\\dfrac{\\partial h_2}{\\partial\\theta_2^{(u)}}(X,\\theta_2)\\dfrac{\\partial h_2}{\\partial\\theta_2^{(v)}}(X,\\theta_2):1\\leq u\\leq v\\leq q_2\\}$,\n\n(S.3) $\\{\\dfrac{\\partial h_1}{\\partial\\theta_1^{(u)}}(X,\\theta_1)\\dfrac{\\partial h_2}{\\partial \\theta_2^{(v)}}(X,\\theta_2):1\\leq u\\leq q_1, 1\\leq v\\leq q_2\\}$,\n\n(S.4) $\\{X^{w}\\dfrac{\\partial h_1}{\\partial\\theta_1^{(u)}}(X,\\theta_1):1\\leq u\\leq q_1,0\\leq|w|\\leq 1\\}$,\n\nwhere $\\theta_1^{(u)}$ are the $u$-th entry of $\\theta_1$.\n\nFor example, if $h_1(X,\\theta_1)=\\theta_1^{\\top}X$ and $h_2(X,\\theta_2)=\\theta_2$, then $h_1$ and $h_2$ are algebraically independent.\n\nUnder over-fitted settings, if $h_1$ and $h_2$ are algebraically independent expert functions, we propose using the follwoing Voronoi loss for the convergence analysis: \n\n$\\mathcal{D}(G,G*):=\\inf_{t_1,t_2}(\\sum_{j:|\\mathcal{A}_j|>1,i\\in\\mathcal{A}_j}[$ \n\n$\\exp(\\beta_{0i})||(\\Delta_{t_2}\\beta_{1ij},\\Delta\\theta_{1ij},\\Delta\\theta_{2ij})||^2]$\n\n$+\\sum_{j:|\\mathcal{A}_j|=1,i\\in\\mathcal{A}_j}[$\n\n$\\exp(\\beta_{0i})||(\\Delta_{t_2}\\beta_{1ij},\\Delta\\theta_{1ij},\\Delta\\theta_{2ij})||]$\n\n$+\\sum_{1\\leq j\\leq k_*}[$\n\n$|\\sum_{i\\in\\mathcal{A}_j}[$\n\n$\\exp(\\beta_{0i})]-\\exp(\\beta^*_{0i}+t_1)|])$,\n\nwhere $\\Delta_{t_2}\\beta_{1ij}:=\\beta_{1i}-(\\beta^*_{1j}+t_2)$, $\\Delta\\theta_{1ij}=\\theta_{1i}-\\theta^*_{1j}$, $\\Delta\\theta_{2ij}=\\theta_{2i}-\\theta_{2j}$.\n\n**(we apologize for the typing of the loss function as it is too complex to compile in one line)**\n\nIn particular, we find out that the MLE $\\widehat{G}_n$ defined as in our work still converges to \n\nthe true mixing measure $G_*$ under the above loss at a rate of $\\mathcal{O}(n^{-1/2})$ (up to some logarithmic term). \nConsequently, the estimation rates for over-fitted parameters $\\beta^*_{1j},\\theta^*_{1j},\\theta^*_{2j}$ are $\\mathcal{O}(n^{-1/4})$, while those for exact-fitted parameters are $\\mathcal{O}(n^{-1/2})$.  \n\nHowever, when $h_1$ and $h_2$ are not algebraically independent, then the estimation rates for true parameters will vary with the choices of expert functions. For instance, in our work, $h_1(X,(a,b))=a^{\\top}X+b$ and $h_2(X,\\sigma)=\\sigma$ are not algebraically independent since the corresponding set (S.4) is linearly dependent.\n\n**Q2: The convergence results are derived by considering the number of “true” experts, however, it’s unclear to me whether there is a notion of a “true” expert.**\n\nThanks for your question. We would like to clarify that we did not use the term ``the number of true experts'' in our paper. However, we used two other terms which possibly related to that term:\n\n1) ``the true number of experts'' (line 118), which was denoted by $k_*$;\n\n2) ``true experts'' (first line on page 6), which indicates the experts with true parameters, e.g. $f(Y|(a^*_i)^{\\top}X+b^*_i,\\sigma^*_i)$.\n\n**Q3: Is there any way to empirically verify the convergence rates for exact-fitted vs. over-fitted setups?**\n\nThanks for your question. Ones can refer to Appendix C in the supplementary material where we conducted several experiments to empirically justify the theoretical convergence rates for both exact-fitted and over-fitted settings.\n\n**Q4: Some diagrams could possibly fill in any gaps in the reader’s understanding. For instance, diagrams showing the softmax Gaussian mixture of experts setting, as well as other concepts, like Voronoi cells, Hellinger distance, etc.**\n\nThanks for your suggestion, we will add the illustration of Voronoi cells in the PDF file (attached at the end of the General Response section) to the revision of our paper. \n\nImage Caption: Illustration of Voronoi cells under the over-fitted settings. Blue triangles represent true components while red rounds indicates fitted components. By definition, each Voronoi cell corresponds to only one true component, i.e. one blue triangle, and its cardinality is the number of corresponding fitted components, i.e. the number of red rounds. For instance, in cell 1, the blue triangle is approximated by two rounds, implying that the cardinality of cell 1 is two. Then, from the comments on Theorem 2 (line 237-244), since $\\bar{r}(2)=4$, the estimation rates for $\\beta^*_{11},b^*_1$ are $\\mathcal{O}(n^{-1/8})$, while those for $a^*_1,\\sigma^*_1$ are $\\mathcal{O}(n^{-1/4})$ (up to some logarithmic term).\n\n**Q5: Regarding the significance of the result and connecting the result to practical empirical settings — what can be done to make this connection clearer?**\n\nThanks for your question. Please refer to the Common Question 2 in the General Response section for our response."}, {"review_id": "UXoQk04Uxb", "reviewer": "Reviewer_sK4C", "summary": "The authors explore the theoretical complexity of standard Gaussian Mixture of Experts and propose a Vononoi loss which estimates different components of the MLE using different Voronoi cells. \n\nUpdate: I have read the rebuttal and the other reviewers' responses, and will keep the score at 7 (accept).", "questions": "Minor notes: there seems to be a switching between Vononoi vs Voronoi in the paper. Make sure to standardize them!", "limitations": "Yes.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The authors establish versions of the Voronoi loss in multiple scenarios, both in fixed settings and over-fitted settings. \n\nThe Voronoi loss function in both settings is computationally efficient up to a linear order of the number of experts, assuming that the true number of experts is fixed.", "weaknesses": "Unfortunately, there does not seem to be any practical exploration of the Voronoi loss in the real world setting to verify the theoretical findings, that should be fine due to the posit of the paper as a more theoretical work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1: Unfortunately, there does not seem to be any practical exploration of the Voronoi loss in the real world setting to verify the theoretical findings, that should be fine due to the posit of the paper as a more theoretical work.**\n\nThanks for your comment. We would like to refer the reviewer to Appendix C in the supplementary material where we run several experiments under synthetic settings to empirically validate our theoretical results. For the connection of our theoretical results to real-world settings, please refer to the Common Question 2 in the General Response section.\n\n\n**Q2: Minor notes: there seems to be a switching between Vononoi vs Voronoi in the paper.**\n\nThanks for pointing out, we will correct it in the revision of our paper."}, {"review_id": "mxlseCL3Ig", "reviewer": "Reviewer_8L63", "summary": "This paper addresses the long-standing challenge of parameter estimation in softmax gating Gaussian mixture of experts. The authors identify three theoretical challenges related to softmax gating: (i) the non-uniqueness of parameter estimation, (ii) the interaction between softmax gating and expert functions, and (iii) the complex dependence in the conditional density. They propose Vononoi loss functions to overcome these challenges and establish convergence rates for the maximum likelihood estimator (MLE). Additionally, they discover a connection between the MLE rate and a polynomial equation solvability problem when the number of experts is unknown or over-specified.", "questions": "No", "limitations": "No", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper proposes a novel solution to a long-standing problem in the literature, addressing three fundamental challenges associated with softmax gating. By introducing Vononoi loss functions and establishing convergence rates for the maximum likelihood estimator, the authors offer a fresh perspective on parameter estimation in these models. The paper contributes to the theoretical understanding of softmax gating Gaussian mixture of experts. It tackles the issues of non-uniqueness, interaction between gating and expert functions, and complex dependence in the conditional density. By resolving these challenges, the authors enhance our knowledge of the underlying principles and dynamics of these models. The paper establishes a connection between the MLE rate and a solvability problem of a system of polynomial equations. This connection adds an interesting aspect to the study, highlighting the potential relationships between statistical estimation and mathematical problem-solving.", "weaknesses": "Firstly, the absence of a comparison or discussion of popular techniques such as Gumbel-softmax [1] and max-propagate [2] raises concerns. These techniques are widely used in probabilistic MOE methods, and their exclusion from the paper may limit its completeness and applicability.\n\nSecondly, the lack of experimental validation is another potential issue. The practical relevance of the proposed methods is claimed by the authors, but without empirical evidence or experiments, it is challenging to assess the true impact and effectiveness of the proposed approach in real-world scenarios.\n\n[1] E. Jang, et al. \"Categorical Reparameterization with Gumbel-Softmax.\" International Conference on Learning Representations (2017).\n\n[2] J. Ren, et al. \"Probabilistic mixture-of-experts for efficient deep reinforcement learning.\" arXiv preprint arXiv:2104.09122 (2021).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1: The absence of a comparison or discussion of popular techniques such as Gumbel-softmax and max-propagate raises concerns. These techniques are widely used in probabilistic MOE methods, and their exclusion from the paper may limit its completeness and applicability.**\n\nThanks for your suggestion, we will consider adding discussion about the Gumbel-Softmax and max propagation to the revision of our paper. However, we would like to emphasize that the main objective of this work is to study the convergence rates for parameter estimation in the Gaussian mixture of experts with softmax gating, which is commonly used in many machine learning and deep learning applications [1, 2] but remains missing theoretical understanding for long time. Therefore, the Gumbel-Softmax and max propagation techniques go beyond the scope of our paper, and we believe that proof techniques need to be further developed to handle these settings.\n\n**Q2: The lack of experimental validation is another potential issue, which makes it challenging to assess the true impact and effectiveness of the proposed approach in real-world scenarios.**\n\nThanks for raising your concerns. Actually, in Appendix C of the supplementary material, we already carried out several experiments to empirically verify our theoretical results. Therefore, you can refer to that appendix for further details of experimental validation. Regarding the implication of theoretical results to real-world scenarios, please refer to the Common Question 2 in the General Response section.\n\n**References**\n\n[1] Hussein Hazimeh, Zhe Zhao, Aakanksha Chowdhery, Maheswaran Sathiamoorthy, Yihua Chen, Rahul Mazumder, Lichan Hong, and Ed H. Chi. Dselect-k: Differentiable selection in the mixture of experts with applications to multi-task learning. In Advances in Neural Information Processing Systems 34, 2021.\n\n[2] Noam Shazeer, Azalia Mirhoseini, Krzysztof Maziarz, Andy Davis, Quoc Le, Geoffrey Hinton, and Jeff Dean. 2017. Outrageously large neural networks: The sparsely-gated mixture-of-experts layer. In International Conference on Learning Representations 2017."}]

Author rebuttal:
**General Response**

Dear AC and reviewers,

Thanks for your thoughtful reviews and valuable comments, which have helped us enhance our paper substantially. In this section, we will address some common concerns from the reviewers, and then include these changes to the revision of our paper.

**CQ1: Main challenges in the paper?**

To the best of our knowledge, previous work on comprehending the convergence rates for parameter estimation problem in mixture of experts or mixture models [1] all assume that the corresponding gating or mixing proportion is independent of the covariates $X$. This assumption is limited and far from recent applications of mixture of experts in machine learning and deep learning [2], which leverage covariate-dependent gating such as softmax gating and its variants. For those reasons, understanding parameter estimation of softmax gating Gaussian mixture of experts has remained a long-standing open problem in the literature.

There are three main challenges in our work: 

**(i)** Firstly, parameters $\beta^*_{1i}, \beta^*_{0i}$ of the softmax gating are not identifiable as those of the covariate-independent gating in previous work. Instead, they are identifiable up to translation, that is, the softmax gating does not change when we translate the parameters as follows: $\beta^*_{1i}+t_1$ and $\beta^*_{0i}+t_2$. As a consequence, we need to introduce an infimum operator in the Voronoi loss function to deal with this issue.  

**(ii)** Secondly, it is clear that the numerators and denominators of softmax gating are dependent. Thus, in Step 1 of our proofs, if we applied the Taylor expansion directly to the conditional density difference $g_{G_n}(Y|X)-g_{G_*}(Y|X)$ as in previous work [1], we were unable to represent the conditional density difference as a linear combination of elements belonging to some linearly independent set, which is a key step in the proof techniques. To this end, we consider the product of the softmax gating's denominator and the conditional density difference, which is denoted by $Q_n$. Subsequently, we decompose the product $Q_n$ such that the decomposition includes two functions $\exp(\beta_{1i}^{\top}X)f(Y|a_i^{\top}X+b_i,\sigma_i)$ and $\exp(\beta_{1i}^{\top}X)g_{G_n}(Y|X)$ as in line 291. Then, we have to apply two Taylor expansions of different orders to these functions, respectively, rather than only one Taylor expansion as in [1]. Now, $Q_n$ is written as a linear combination but there are some linearly dependent terms due to the intrinsic interaction between the softmax gating's numerator $\exp(\beta_{1i}^{\top}X+\beta_{0i})$ and the Gaussian density function $f(Y|a_i^{\top}X+b_i,\sigma_i)$ via the partial differential equation in Eq.(3): $$\frac{\partial u(X,Y)}{\partial\beta_1}\cdot\frac{\partial u(X,Y)}{\partial b}=\frac{\partial u(X,Y)}{\partial\beta_0}\cdot\frac{\partial u(X,Y)}{\partial a},$$ where $u(X,Y):=\exp(\beta_1^{\top}X+\beta_0)f(Y|a^{\top}X+b,\sigma)$. Therefore, it takes us much effort to group these linearly dependent terms together as in Eq.(25) to formulate $Q_n$ as a linear combination of linearly independent terms. 

**(iii)** Finally, in Step 2 of our proofs, we assume that all the ratios of coefficients in the above linear combination to the Voronoi loss converge to zero. Then, via some transformations, those limits lead to the system of polynomial equations in Eq.(6). Compared to the system in previous work [Eq.(6), 1], our system is much more complex and challenging due to the interaction between the softmax gating's numerator and the Gaussian density. As a result, it takes us greater effort to comprehend our system in Lemma 1.  

**CQ2: Connection between theoretical results and real-world settings?**

There are two different real-world settings that the current theoretical results will yield important insights into:

(i) Well-specified setting: In this setting, we assume that the data are generated from Gaussian mixture of experts with softmax gating. It is the setting that we mainly study in the current work. Our results in the paper suggest that when we overspecify the number of experts in the well-specified setting, the convergence rates of some parameters can be very slow and depend on the amount of components that we overspecify the model while those of the remaining parameters can be very fast. These rates can be captured precisely by the novel Voronoi losses. The precise rates are important for developing model selection to choose the correct number of experts in the well-specified settings, which is important to improve the complexity of using Gaussian mixture of experts in practice (Please refer to the Practical Implication paragraph in the Introduction).

(ii) Misspecified setting: In this setting, the data are not generated from Gaussian mixture of experts with softmax gating while we fit the data by Gaussian mixture of experts. Different from the well-specified setting, the MLE $\widehat{G}_{n}$ converges to the mixing measures $\bar{G}$ which is an optimal solution for the problem of minimizing the following Kullback-Leibler divergence:

$KL(g_{G}(Y|X), P(Y|X))$, 

where $P(Y|X)$ is the true conditional density function of $Y|X$, which is not a Gaussian mixture of experts, $g_{G}(Y|X)$ is Gaussian mixture of experts with mixing measure $G$. The insights from our theories in the well-specified setting indicate that the Voronoi losses can be used to obtain the precise rates of individual parameters of the MLE $\widehat{G}_{n}$ to those of $\bar{G}$. The detailed theoretical development of parameter estimation under the misspecified setting is beyond the current scope of the paper and left for future work.

**References**

[1] N. Ho, C.-Y. Yang, M. I. Jordan. Convergence rates for Gaussian mixtures of experts. Journal of Machine Learning Research, 2022.

[2] H. Hazimeh. Dselect-k: Differentiable selection in the mixture of experts with applications to multi-task learning. In NeurIPS, 2021.

Meta-review: The paper studies statistical rates for maximum likelihood estimation in softmax-gated Gaussian mixture of experts, with gating probabilities that are allowed to depend on inputs. Reviewers were happy with the paper's contributions as well as the author response. Some concerns were raised regarding accessibility of presentation and relevance to practice, and I encourage the authors to clarify these points in the final version.
Decision: Accept (spotlight)