Risk Bounds for Mixture Density Estimation on Compact Domains via the h-Lifted Kullback–Leibler Divergence
Authors: Mark Chiu Chong
Hien Duy Nguyen
TrungTin Nguyen
Venue: Accepted by TMLR ()

Abstract: We consider the problem of estimating probability density functions based on sample data, using a finite mixture of densities from some component class. To this end, we introduce the $h$-lifted Kullback--Leibler~(KL) divergence as a generalization of the standard KL divergence and a criterion for conducting risk minimization. Under a compact support assumption, we prove an $\mathcal{O}(1/{\sqrt{n}})$ bound on the expected estimation error when using the $h$-lifted KL divergence, which extends the  results of Rakhlin et al. (2005, ESAIM: Probability and Statistics, Vol. 9) and Li & Barron (1999, Advances in Neural Information Processing Systems, Vol. 12) to permit the risk bounding of density functions that are not strictly positive. We develop a procedure for the computation of the corresponding maximum $h$-lifted likelihood estimators ($h$-MLLEs) using the Majorization-Maximization framework and provide experimental results in support of our theoretical bounds.

Published in Transactions on Machine Learning Research (11/2024)
Risk Bounds for Mixture Density Estimation on Compact Domains via the h-Lifted Kullback-Leibler Divergence
Mark Chiu Chong
mark. hwnn.chhiuchhng@@@ma.ccc com
School of Mathematics and Physics
The University of Queensland St Lucia, QLD 4072, Australia
Hien Duy Nguyen
hrien &hiii www.rni.kkkuhhuuu.uaa.....
Institute of Mathematics for Industry Kyushu University
Nishi Word, Fukuoka 819-0395, Japan;
School of Compuling, Engineering, and Mathemalivd Sciences Trobe University Bundoom,, VIC 3086, Australia;
TrungTin Nguyen
frungtin, www.eennnnnnnnnnnnunouoo wew.eeu...au...........o.o edu.ar
School of Mathematics and Plysics
The University of Queensland St Lucia, QLD 4072, Australia
Reviewed on OpenReview: fttp::///operevicee net/ formformm id= uHK
Abstract
We consider the problem of estimating probability density functions based on sample data, using a finite mixture densities from some component class. To this end, we introduce the h-lifted Kullback-Leibler (KI) divergence as a gencralization of the standard KL divergence and criterion for conducting risk minimization. Under compact support assumption, we prove ((1/vn) bound on the expected estimation error when using the h-lifted KL divergence, which extends the results of Rakhlin et al. (2005) ESAIM: Probability and Statistics, Vol. 9) and Li & Barron (1999 Advances in Neural Information Processing Systems, Vol. 12) to permit. the risk bounding of density functions that are not strictly positive. We develop a procedure for the computation of the corresponding maximum h- lifted likelihood estimators (h-MLLEs) using the Majorization- Maximization Miariiatioo-MMaiiiittiooon framework and provide experimental results in support of our theoretical bounds.
1 Introduction
Let (2, (P) P) be an rastract probability space and let. : Ω + X' a random variable laking values in the measurable space (,, where X' is compact metric space equipped with its Borel o-algebra F. Suppose that we observe an independent and identically distributed (i.i.d.) sample of random variables X, = (Xx))ej)) where [n] = (1)...,)), n), and that each X, arises from the same data generating process X, characterizod by the probability measure F & μ on (X, 8), with density function f = dF/du, for some o-ninit u. In this work, we concerned with the estimating I via data dependent double-index sequence of estimators (fr,n) where
k fk.n E Cp co (P) = fk (:ab)) = Σ (: |((:0) E 20 K ==1
k
1=1

---

Published in Transactions on Machine Learning Research (11/2024)
for each k, n E N, and where
P
- 1 CR),
(1)
the = (#1,...., Tk, 01,.. "t.....0,,, 0k), and d N. To ensure the measurability and existence of various optima, we shall assume that sp is Carathéodory in the sense that & (1;0) is (X.3)-measurable for each O and op (X;-) is continuous for each X E X.
In the definition above, written as convex combination of l elements of P. where P is often called the space of component density functions. We then interpret Ck as the class of k-component finite mixtures of densities class P, as studied,
identify the set C2 Co2 (P) the set of density functions that can be
for example, by McLachlan Peel (2004); Nguyen et al. 2020 2022b
1.1 Risk bounds for mixture density estimation
We are particularly interested in oracle bounds of the form
E (fe ((
(2)
where (p.4) + (p, Rzz is loss function on pairs of density functions. We define the density-to-class loss
e(f.c = inf e (f.g), C = (Ucox(1)) DEC
KEN
where cl(.) is the closure. Here, we identify (k, + p (ki, n) as characterization of the rate at which the left-hand side of (2) converges to zero as is and increase. Our present work follows the research of
Li & Barron (1999), Rakhlin et al. (2005) and Klemelä (2007) (see also Klemelä 2009. Ch. 19). Tn Li & Barron (1999) and Rakhlin et al. (2005). the authors consider the case where e ((p q) is taken to be the
Kullback Leibler (KL) divergence
KT. (1)))1) = f
ff plog "dy q
and fk.n = f&r (: (h,) a maximum likelihood estimator (MLE), where
h E arg max x
log fo (k))
is function of X,, with S₁ denoting the probability simplex in R*
Under the assumption that f. fv 2 for some a > and each k E [m]] (i.e., strict positivity), Li & Barron 1999) obtained the bound
h log (cyn)
E (fIl (L <1 k
+ C2
n
for constants C1, C22 03 > O, which was then improved by Rakhlin et al. 2005 who obtained the bound
E (KL (KT. - (IC() s a + 02 Vn"
for constants C1, 02 > (constants (cy)jEN are typically different between expressions).
Alternatively, Klemelä (2007) loss):
takes (p) to be the squared La (44 norm distance (i.e., the least-squares
e (p. 4) lp 4122,m.
where 11p12, fxle|?du, for each p E Le (w), and choose Jn,n as minimizers of the La (n) empirical risk, i.e. fk.n fk (: ())),,), where
n
Vkn E arg min
Σ 1=1
fie (:: wh) + IIfe (: (h:))) 1
(3)
2

---

Published in Transactions on Machine Learning Research (11/2024)
Here, Klemelä 2007
establish the bound
E | - Sk 2,0 - inf IlS
=1li, S Sa k + c Vn''
qEC
C1, 02 > O, without the lower bound assumption on f. f& above, even permitting to be unbounded. Via the main results of Naito & Eguchi (2013), the bound above can be gencralized the U-divergenoes, which includes the special (z( norm distance a special case.
On the one hand, the sequence of MLEs required for the results of Li & Barron 1999 and Rakhlin et al. (2005) are typically computable, for example, via the usual expectation-maxiiiaae
approach (cf. McLach- lan & Peel 2004] Ch. 2). This contrasts with the computation of least-squares density estimators of form (3 which requires evaluations of the typically intractable integral expressions I| (-: t However, the least-squares approach of [Klemelä (2007) permits the analysis using families P of usual interest, such normal distributions and beta distributtinn, the latter of which being compactly supported but having den- sities that cannot be bounded away from zero without restrictions, and thus do not satisfy the regularity conditions
Li & Barron
1999 and Rakhlin et al. (2005).
1.2 Main contributions
We propose the following h-lifted KL divergence, as generalization of the standard KL divergence to address the computationally tractable estimation of density functions which do not satisfy the regularity conditions of Li & Barron (1999) and Rakhlin et al. (2005). The use the h-lifted KL divergence has the possibility to advance theories based on the standard KL divergence statistical machine learning. To this end, let R2o be function in La (n), and define the h-lifted KT, divergence by:
h X
KL (p (p = f (p (p+h) log
p + h
q+ du.
In the sequel, shall show that KL. is a Bregman divergence on the space of probability density functions, as per Csiszár 1995).
Assume that a probability density function, and let Y, = (Yi) be a an i.i.d. sample, independent of X,, where each Y; Ω + X' is random variable with probability measure on (X' characterized by the density h with respect to μ.. Then, for each k and let fkim be defined via the maximum h-lifted likelihood estimator (h-MLLE; see Appendix for further discussion) fu.n = fx (: tk,,), where
1 Σ (log Us (Xi + h (X.)) + log (fe (Ya (Y:))).
tknn arg max
(5)
Vr, ES, x n
The primary aim of this work is show that
E (KLA (f KL, (fIIC) S a +
+ Vn
(6)
for some constants C1, 02 > 0, without requiring the strict positivity assumption that S3 2 > 0.
This result is a compromise between the works of Li & Barron (1999) and Rakhlin et al. 2005 and Klemelä (2007), as applics broader space of component densitics P, and because the required h- h-MLLES (5) can
be efliciently computed via minorization maximization minnizaiioonmaaiiiaaaio (MM) algorithms (see e.g., Lange 2016 We shall
discuss this assertion in Section 4
1.3 Relevant literature
Our work largely follows the approach of Li Barron (1999). which was extended upon by Rakhlin et al. (2005) and Klemelä (2007). All three texts use approaches based on the availability of greedy algorithms for maximizing convex functions with convex functional domains. In this work, shall make use of the
3

---

Published in Transactions on Machine Learning Research (11/2024)
proof techniques of Zhang (2003). Related results in this direction be found in DeVore & Temlyakov
(2016) and Temlyakov (2016). Making the same boundedness assumption as Rakhlin et al. (2005) Dalalyan
& Sebbar 20188) obtain refined oracle inequalities under the additional assumption that the class P is finite.
Numerical implementations of greody algorithms for estimating finite mixtures of Gaussian densities were
studied by Vlassis Likas
2002) and Verbeek et al. (2003).
The h-MLLE as an optimization objective can be compared other similar modified likelihood estimators, such as the L, likelihood of Ferrari & Yang (2010) and Qin & Priebe (2013), the 3-likelihood of Basu et al. (9988) and Fujisawa & Eguchi (2006), penalized likelihood estimators, such maximum posteriori estimators of Bayesian models, or f-soparable Bregman distortion mcasures of Kobayashi & Watanabo 20224 2021).
5 is made possible via the MM algorithm framework of Lange (2016), see also Hunter & Lange (2004). Wu Lange (2010), and Nguyen (2017) for further details. Such algorithms have well-studied global convergence properties and can be modified for mini-batch and stochastic settings (see, e.g.. RRaavvyayn et al. 2013 and Nguyen et al. 2022a).
The practical computation of the h- h-MLLEs,
A related and popular sctting of investigations is that of model selection, where the objects of interest are single single-index index sequences (ffn.,)) neN: and where the aim is to obtain finite-sample bounds for losses of the form (f,,.,,;)), I), where each kn E N is a data dependent function, often obtained by optimizing some penalized loss criterion, as described in Massart (2007), Koltchinskil [201] Ch. 6), and Giraud| (2021) Ch. 2). In the context of finite mixtures, examples of such analyses can be found in the works of Maugis Michel (2011) and Rabusseun & Michel 2013). A comprehensive bibliography of model selection results for finite mixtures and related statistical models can be found in Nguyen et al. (002cc).
1.4 Organization of paper
The manuscript is organized as follows. In Section 2 we formally define the h-lifted KL divergence as a Bregman divergence and establish several of its properties. In Section 3 we present new risk bounds for the h-lifted KL divergence of the form (2). In Section 4 we discuss the computation of the h-lifted likelihood estimator in the form of (5). followed by empirical results illustrating the convergence of (2) with respect to both k and n. Additional insights and technical results are provided in the Appendices at the end of the manuscript.
2 The hilifted KL divergence and its properties
In this section we formally define the h-lifted KT. divergence on the space of density functions and establish some of its properties.
Definition 1 (h-lifted KL divergence). Let f.g, and h be probability density functions on the space X, where > O. The h-lifted KL divergence from to f is defined as follows:
KL, (f)l))= / ( ( h1+ log /+ dp E,
{ log [+h + E, log f+ h + h
+
g ++ h
2.1 KL, Bregman divergence
Let Φ I + divergence between scalars dø I x I + Rzo generated by the function & is given by:
- I= 00) be strictly convex function that is continuously disferentiable. The Bregman
ds(p.9) = x(p) x(g) - d'(g)(p 9).
where d'(4) denotes the derivative of Φ at g.
Bregman divergences possess several useful properties, including the following list:
1. Non-negativity: do(p. 9) 2 for all p.g E I with equality if and only if p q;
4

---

Published in Transactions on Machine Learning Research (11/2024)
2. Asymmetry: dp(p.9) # p)) in general;
3. Convexity: de(p, q) is convex in p for every fixed g I.
4. Linearity: de q) cıds, (p,9) cadøz (p. q) for c2, 0.
The properties for Bregman divergences between scalars can be extended to density functions and other functional spaces, as established in Frigyik al. (2008) and Stummer & Vajda (2012) for example. We also direct the interosted reader to the works of Pardo 2006). Basu et al. (2011). and Amari (0166).
The class of h-lifted KT. divergences constitute generalization of the usual KT. divergence and are subset of the Bregman divergences over the space of density functions that are considered by Csiszár (1995). Namely, let P be a convex set of probability densities with respect to the measure on X. The Bregman divergence D& : P x P + o0) between densities p. E P can be constructed as follows:
Do(plla)= = (
-fx ds (p(x), (())) du(x).
The h-lifted KL divergence KL2 Bregman divergence is generated by the function 6(u) (u+ h) log(u+ h) - (u h)) + This assertion is demonstrated in Appendix C.1
2.2
Advantages of the h-lifted KL divergence
When the standard KL divergence is employed in the density estimation problem, it is common to restrict consideration of density functions to those bounded away from zero by some positive constant. That is, one typically considers the smaller class of so-called admissible target densities Pa C P (cf. Meir & Zeevi 1997)
where
Pa = (v(::) E P ((:0) 2 a >>0.
Without this restriction, the standard KL divergence can be unbounded, even for functions with bounded Li norms. For example, let and be densities of beta distributions on the support X' = [0, 1]. That is, suppose that p, Potta, respectively characterized by parameters 6, = (ap. bp) and 0g = (ag. bg), where
(a + (a) 20 (1- 1 0 ba, R30
Pbeta = x 3 (z; 0)
x0
(7)
Then, from Gil et al. 2013), the KL divergence between and is given by:
T (T (by) ) log
T (a,) [bpp)
KL (p q) log
I' (a + bn)
r (a + bb)
+ (ap - ag) {1b (ap) - v (ap + bp)) + (bp - by) (v (bp) - 10 (ap + bp)}
where v RR - R is the digamma function. Next, suppose that ap by and ag = bp = 1, which leads to (11)
the simplification
KL (pllg) = (ap
Since v is strictly increasing, observe that the right-hand side diverges ap + Thus, the KL divergence between beta distributions is unbounded. The h-lifted KL divergence in contrast does not suffer from this problem, and does not require the restriction to Pa. This allows us to consider cases where p.q E P are not bounded away from 0, as per the following result.
Proposition 2. Let P be defined as in KL, (f g) is bounded for all continnous densities f.g E P.
Proof. See Appendix C.2
Let (f. denote the standard no-norm, (z((t))= (Jx ffx) g(x)l² dp(x)) As remarked previously, Klemelä (2007) established empirical risk bounds in terms of the Lg-norm distance. Following results from
Meir & Zeevi 1997) characterizing the relationship between the KI. divergence in terms of the Tg-norm
5

---

Published in Transactions on Machine Learning Research (11/2024)
distance, in Proposition 8 establish the corresponding relationship between the h-lifted KL divergence and the I2-norm distance, along with relationship between the h-lifted KL. divergence and the Iy-norm distance.
Proposition 3. For probability density functions f, 9: and h, where h is such that h(x) 7 0 for all X, the following inequalilies hold:
1 $ KL, (fll)) (3(().))
Proof. See Appendix C.3
Remark 4. Proposition & highlights the benefit of the h-lifted KL divergence being bounded. for all continuous densities, unlike the standard KL divergence, while satisfying a relationship similar to that between the KL divergence and the L2 norm distance. Moreover, the first inequality of Proposition S is a Pinsker-like relalionship between the h-lifted KL divergence and the total variation dislance TVJ. = (l,
3 Main results
Here we provide explicit statements regarding the convergence rates claimed in 6 via Theorem and Corollary G which proved in Appendix A.2 We assume that bounded above by some constant and that the lifting function h is bounded above and below by constants and 6, respectively.
Thcorem 5. Let h be a positive density satisfying a a h(x)) S b, for all X. For any target density f satisfying S f(x) S c, for all X and where fumn is the minimizer of KL, over k-component mintures, the sollowing inequalily holds:
(KLa ((,))) KLn (fllc)
U3 ++ vn [ log 1/2 N(P.e/2.11 Ide +
81
+
U2
Vn where U1, U2, and Ug are positive constants that depend on some or all of a, b, and c.
Corollary 6. Let X and θ be compact and assume the following Lipschitz condition holds: for each E X, and for each 7 E O,
xp (2; 0) 4p (z; +) 15 (x) +11 for some function & X' + Ezo, where ||0|| = sup (uPrex/(((x)) < <c.
Then the bound in Theorem becomes
E [KL, (fIl KL. (1IIC) S
k+2 + C2 Vn'
C1
where 61 and 02 are positive constants.
Remark 7. Our results are applicuble to any compact melric space. X. with [0, 1] used in the experimental setup in Section 4.2 as a simple and tractable example to illustrate key aspects of our theory. There is no issue in generulizing to X' = [-m,, m]" for m > O and d E N, or more abstractly, to any compact subset X C. Rd. Additionally, X could even be taken as functional compact space, though establishing compactness and constructing appropriate component classes P over such spaces achieve small approzimation ervors KL (fI is an approximation theoretic task that falls outside the scope of our work.
From the proof of Theorem in Appendix A.2, it is clear that the dimensionality of X only influences our bound through the complexity of the class P, specifically, the constant Se log (P,, e/2, || lo dde, which remains independent of both n and k. Here, N(P, & II) is the s-covering number of P. In fact, the constant with respect to (un in Theorem 5) is entirely unaffected by the dimensionality of X. Thus, the dimensioon-iddependdee independent and hold even when is infinite-dimensional as long as there erists class P such that Jo 1/2 N(P, e/2, -1le is finâte.
rates of our bound on the expected h h-lifted KL divergence are dimension
Corollary 0 provides method for oblaining such bound when the elements ofP satisfy Lipschitz condition.

---

Published in Transactions on Machine Learning Research (11/2024)
4 Numerical experiments
Here we discuss the computability and computation of KLA estimation problems and provide empirical evidence towards the rates obtained in Theorem 5 Specifically, seek to develop methodology for computing h-MLLEs, and to numerical experiments to demonstrate that the sequence of expected h- lifted KL divergences between some density f and sequence of k-component mixture densities from a suitable class P, estimated using n observations does indeed decrease at rates proportional to 1/k and 1/vn, as and n increase.
The code for all simulations and analyscs in Experiments and is available in both the R and Python programming languages. The code repository is available here: httpps//gitthb: www.coom///..... hht//iiend///// Iooood
4.1 Minoriztionn-Mxiiiiatti algorithm
One solution for computing 5 is employ MM algorithm. To do so, we first write the objective of 5
} {
Ihh (1bx)
1
Σ i=1
log Σ Jop +
+ log Σ T (Y:0)) (x0
where Sh E 1 = Sb x Ok. We then require the definition of minorizer Qn for Ln. on the space Vs where Qn : Ux x 1x + R is a function with the properties:
(i) On (Wh. thx) Lnn (the), and
(ii) On (Wh: Xhx) Ln, (shk):
for each sha, X VR. In this context, given a fixed Xs, the minorizer Qn (*.x)) should possess properties that simplify it compared to the original objective La.- These properties should make the minorizer more tractable and might include features such as paramctric scparability, diffcrentiability, convexity, among others.
In order to build an appropriate minorizer for Li, we make use of the so-called Jensen's inequality minorizer, detailed in Lange (0066) Sec. 4.3), applicd to the logarithm function. This construction results in minorizer of the form
(V4.
fo (Xx: log T, +ry (Xi log (X)),))
TTy (Y::)) log + (Y: log o (Y;;,))
( (ogh (X.) 7 (Yrxx) (Y:))
(ry (X (Xxx)) + (Y:s xxx log T, xx))
( (xgx (Xxx))))og((Xxx))) (Xxx)) (Ysx)) log (Vxx)))
m
where
7 (X.:ba) = (x))
Σ Typ (X1;0,) + (x.)
7

---

Published in Transactions on Machine Learning Research (11/2024)
and
Tj (Xz = Typ (X:00) (X:(0))
T (Xx; (x (
Observe that Qn (-s X&) now takes the form of a loun-of-oggarthhms, as opposed to the more challenging lfg-of-sum form Ln,- This change produces functional separation of the elements of th..
Using On we then define the MM algorithm via the parameter sequence
(v%)
where
sEN
4 = arg max On (w' w/ 1)
(9)
V.EW,
for each s > O, and where u is user chosen and is typically referred to as the initialization of the algorithm. Notice that for each s, 9 is simpler optimization problem than (5) Writing vi
(x) (4) of+) ...., Olf"). we observe that (9) simplifies to the separated expressions:
11 ....,,. Th
Σ Ty
Xx: Xi ((:))(11))
11 + Ys: 1 (b:
(1)
]
Σ Ei=1 { (X + n Y2:1 (6116--11)
and
8)9) = arg max
(Xri (xriv(e-1) logop (X1:0,) + Ty (Y:: log (Y:00)),
T3
8
for each [R:].
A noteworthy property of the MM sequence values, due to the chain of inequalities
is that it generates increasing sequence of objective
sEN
Li 1 1)=-1)== = Qn (w/--1) vel w s Qn (1/"",(0-1)) < Li. (16)
where the equality is due to property (i) of Qn the first in equality is due to the definition of v/.)) and the second inequality is due to property (ii) of Qn This provides kind of stability and regularity to the sequence (Lm.n (v())) SEN
Of course,
provide stronger guarantees under additional assumptions. Namely, assume that (ii) VA C CEE, where Vr is open set in finite dinensional Euclidean space on which Lr... and Qn ( Xx) is differentiable, for each Xk E Vr Then, under assumptions (i)- regarding Iha and Qn, and due to the compactness of Mt and the continuity of Qn on Mp x Mx Razaviyayn et al. (2013 Cor. 1) implies that converges to the set stationary points of La, in the sense that
((())
SEN
1b =0, where V = lim inf (((()) STEV;
={ v/ E U/
=
OLnn Dykk
0
((((1))
More conciscly, say that the sequence
globally converges to the set of stationary points VT
SEN
4.2 Experimental setup
Towards the task of demonstrating empirical evidence of the rates in Theorem we consider the family of beta distributions on the unit interval X' [0, 1] as our base class (i.e., 7 to estimate pair of target densities
f1 (x) = X (x) + Xla/5.11 (x),
8

---

Published in Transactions on Machine Learning Research (11/2024)
and
2 - 4r
if x S 1/2,
f2 (x) X(0,1] (x)
-2 + 4x
if 1/2,
where XA the characteristic function that takes value 1 if x E and 0, otherwise. Note that neither fi when - 1/2, and hence neither densities are bounded away from 0, on X. Thus, the theory of Rakhlin et al. (2005) cannot be applied to provide bounds for the expected KL divergence between MLEs of beta mixtures and the pair of targets. We visualize fi and f2 in Figure 1
nor f2 are in C. In particular, Ji (xx when E (3 3), and f2(x)
2.0
1.5
demsity
1.0
0.5
0.0
0.0
0.2
0.4
0.6
0.8
1.0
Figure Simulation larget densities (solid line) and f2 (dashed line).
To observe the rate of decrease of the h-lifted KL divergence between the targets and respective sequences of h-MLLEs, conduct two experiments E1 and E2. In E1, our target density is set to Si and h (= 1/11/2,1// 1/2). For each E . 21 cach X, and Y; (i E [m]), i.i.d., from the distributions characterized by fi and h1, respectively. In E2, we larget f2 with h-MLLEs over the same ranges of & and n, but with he = 3 1, the density the uniform distribution. For each k and n, we simulate X,, and Y,, respectively, from distributions characterized by fz and f22
and k E (2.....8,, we independently simulate X,, and Y, with
In both experiments, simulate 50 replicates of each (k, n)scenarii and compute the corresponding h-MLLEs, (fkm)))et)) using the previously described MM algorithm. For each 1 E [r], we compute the corresponding negative log h-lifted likelihood between the target f and fk,,
KR,n,1- = f (ʃ ++ log (Jr,, + h) du
assess the rates, and note that
KL, (J (k.mm)) = / (ʃ + bi) log (S h)) dp + Kkmnt
where the prior term is constant with respect to l and n.

---

Published in Transactions on Machine Learning Research (11/2024)
To analyze the sample of 7 50 2100 observations of relationship between the values (Ke,n and the corresponding values of & and n, we use non-linear least squares (Amemiya regression relationship
1985
Sec. 4.3) fit the
22
E [K = do + (A: + 2)
(10)
n
We obtain 95% asymptotic confidence intervals for the estimates of the regression parameters do, d1, 02 bi: be E R, under the assumption of potential missspecification of (10), by using the sandwich estimator for the asymptotic covariance matrix (cf. White 1982).
4.3 Results
We report the estimates along with 95% asymptotic confidence intervals for the parameters of (10) for E1 and E2 in Table D
Plots of the average negative log h-lifted likelihood values by sample sizes n and numbers of components k are provided in Figure 2
Table 1: Estimates of parameters for fitted relationships (with 95% confidence intervals) between negative log h-lifted likelihood values, sample size and number of mixture components for experiments E1 and E2.
E1
ag
a1
a2
b1
62
Est.
-.66
0.73
6.80
1.87
0.99
95% CI
(-1.68, -1.67)
(0.68, 0.78)
(1.24, 12.36)
(1.81, 1.93)
(0.87, 1.11)
E2
ag
a1
02
bj
b2
Est.
-1.47
1.49
6.75
4.36
1.07
95% CT
(-1.48, 1.447 (0.58, 2.41)
(2.17, 11.32)
(3.91, 4.81)
(0.97, 1.16)
From Table ! we observe that E n. decreases with both n and both simulations, and that the rates at which the averages decrease are faster than anticipated by Theorem 5 with respect both n and k. We can visually confirm the decreases in the estimate of E [K.,..l via Figure In both E1 and E2, the rate of decrease over the assessed range of n is approximately proportional to 1/n, as opposed to the anticipated rate of 1/ Tz, whereas the rate of decrease in k is far larger, at approximately 1/k for E1 and 1/24.36 for E2.
These observations provide empirical evidence towards the fact that the rate of decrease of E Kg,,)] is at least 1/k and 1/V respectively, for & and n, at least over the simulation scenarios. These fast rates of over small values and & may be indicative of a diminishing returns of fit phenomenon, as discussed Cadez & Smyth (2000) or the so-called elbow phenomenon (see, e.g., Ritter ( 2014 Sec. 4.2), whereupon the rate of decrease in average loss for small values of k is fast and becomes slower as increases, converging to some asymptotic rate. This is also the reason why we do not include the outcomes when k 1, as the drop in E [KK,n between k = 1 and k = 2 is so dramatic that it makes our simulated data ill-fitted by any model of form (10) As such, we do not view Theorem as being pessimistic in light of these phenomena, as it applics uniformly over all values of & and n.
10

---

Published in Transactions on Machine Learning Research (11/2024)
E1
average
-1.658
-1.664
-1.666
-1.667
-1.668
-1.668
-1.62
7
-1.658
-1.662
-1.664
-1.665
-1.666
-1.666
-1.63
-1.656
-1.660
-1.662
-1.663
-1.664
-1.664
-1.64
5
-1.652
-1.656
-1.658
-1.659
-1.659
-1.659
-1.65
-1.648
-1.651
-1.653
-1.653
-1.654
-1.654
3
-1.633
-1.636
-1.637
-1.638
-1.639
-1.639
-1.66
Num. components k
-1.620
11.621
-1.622
11.222
-1.623
-1.623
1024
2048
4096
8192
16384
32768
E2
average
8
-1.466
-1.469
-1.470
11.471
11.77
-1.471
-1.465
-1.466
-1.469
-1.470
11471
-1.471
-1.41
-1.466
6
-1.466
-1.469
-1.470
-1.471
-1.471
-1.471
-1.467
-1.468
-1.466
-1.469
-1.470
-1.70
-1.471
-1.411
-1.469
4
-1.466
-1.469
-1.470
-1.470
-1.471
-1.471
-1.470
-1.467
-1.468
-1.469
-1.469
-1.469
-1.469
-1.471
2
-1.465
11.466
11.466
-1.467
-1.467
-1.467
1024
2048
4096
8192
16384
32768
Sample size n
Figure 2: Average negative log h-lifted likelihood values by sample sizes n and numbers components for experiments E1 and E2.
11

---

Published in Transactions on Machine Learning Research (11/2024)
5 Conclusion
The estimation of probability densities using finite mixtures from some base class P appears often in machine learning and statistical inference as natural method for modelling underlying data generating processes. In this work, we pursue novel generalization bounds for such mixture estimators. To this end, we introduce the family of h-lifted KL divergences for densities on compact supports, within the family of Brogman divergences, which correspond to risk functions that can be bounded, even when densities in the class are not bounded away from zero, unlike the standard KL divergence.
Unlike the least-squares loss, the corresponding maximum h-likelihood estimation problem can be computed via an MM algorithm,, mirroring the availability of EM algorithms for the maximum likelihood problem corresponding to the KL divergence. Along with our derivations of generalization bounds that achieve the same rates as the best-known bounds for the KL divergence and least square loss, we also provide numerical evidence towards the correctness of these bounds in the case when P corresponds to beta densities.
Aside from beta distributions, mixture densities on compact supports that can be analysed under our frame- work appear frequently in the literature. For supports on compact Euclidean subset, examples include mixtures of Dirichlet distributions (Fan et al. 2012) and bivariate binomial distributions (Papageorgion & compact Fuclidean manifolds, such as mix- tures of Kent Peel et al.) (0001) distributions and von Mises Fisher distributions (Banerjee et al.) 2005
David 1994). Alternatively, one can consider distributions
Ng & Kwong 2022). We defer investigating the practical performance of the maximum h-lifted likelihood
estimators and accompanying theory for such models to future work.
Acknowledgments
We express sincere gratitude to the Reviewers and Action Editor for their valuable feedback, which has helped to improve the quality of this paper. Hien Day Nguyen and TrungTin Nguyen acknowledge funding from the Australian Research Council grant DP230100905.
References
Shun-ichi Amari. Information Geometry and Its Applications, volume 194. Springer, New York, 2016.
Takeshi Amemiya. Advaneed econometrics. Harvard University Press, 1985.
Arindam Banerjee, Inderjit Dhillon, Joydeep Ghosh, Suvrit Sra, and Greg Ridgeway. Clustering on the unit hypersphere using von Mises- Fisher distributions. Journal of Machine Learning Research, 6(9), 2005.
Peter L Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, (BNNov):66344:: 2002.
Ayanendranath Basu, lan Harris, Nils L Hjort, and MC Jones. Robust and efficient estimation by min- imising a density power divergence. Biometrika, 85(3):549 559, 1998.
Ayanendranath Basu, Hiroyuki Shioya, and Chanscok Park. Statistical Inference: The Minároum Distance Ayproach. CRC press, Boca Raton, 2011.
Igor Cadez and Padhraic Smyth. Model complexity, goodness of fit. and diminishing returns. Advances in Newral Information Processing Systems, 13, 2000.
Imre Csiszár. Generalized projections for non-negative functions. In Proceedings of 1995 IEFE International Symposium on Information Theory, pp. 6. IEEE, 1995.
Arnak S Dalalyan and Mehdi Sebbar. Optimal kullback leibler aggregation in mixture density estimation by maximum likelihood. Mathematical Statistics and Learning, 1(1):1-35, 2018
Ronald A DeVore and Vladimir N Temlyakov. Convex optimization on banach spaces. Foundations of Compulational Mathematics, 16(2):369 394, 2016.
12

---

Published in Transactions on Machine Learning Research (11/2024)
Luc Devroye and László Györfi. Nonparometric Density Estimation: The L1 View. Wiley Interscience Series in Discrete Mathematics. Wiley, 1985.
Luc Devroye and Gabor Lugosi. Combinatorial Methods in Density Estimation. Springer Science & Business Media, 2001.
Wentao Fan, Nizar Bouguila, and Djemel Ziou. Variational learning for finite dirichlet mixture models and applications. IEEE transactions on neural networks and learning systems, 23:762 774, 2012.
Davide Ferrari and Yuhong Yang. Maximum lq-likelihood method. Annals of Statistics, 38:573 583, 2010.
Béla A Frigyik, Santosh Srivastava, and Maya Gupta. Functional bregman divergence and bayesian estimation of distributions. JEEE Transactions Information Theory, 54(11):5130 5139, 2008.
Hironori Fujisawa and Shinto Eguchi. Robust estimation in the normal mixture model. Journal of Statistical Planning and Inference, 136(11):3989 4011, 2006.
Subhashis Ghosal. Convergence rates for density estimation with Bernstein polynomials. The Annals of Statisties, 29(5):1264 1280, 2001. Publisher: Institute of Mathematical Statistics.
Manuel Gil, Fady Alajaji, and Tamas Linder. Rényi divergence measures for commonly used univariate continuous distributions. Information Sciences, 249:124-133 2013.
Christophe Giraud. Introduction to high-dimensional statistics. CRC Press, 2021.
Uffe Haagerup. The best constants in the Khintchine inequality. Studia Mathematica, 70(3):231-26) -23, 1981.
David R Hunter and Kenneth Lange. A tutorial on mm algorithms. The American Stalistician, 58(1):30 37, 2004.
Jussi Klemelä. Density estimation with stagewise optimization of the empirical risk. 67:169-195, 2007.
Machine Learning,
Jussi S Klemelä. Smoothing of multivariate data: density estimation and visualization. John Wiley & Sons, New York, 2009.
Masahiro Kobayashi and Kazuho Watanabe. Generalized shichlet-process-meent for f-separable distortion
measures. Neurocomputing 458:667-658 2021.
Masahiro Kobayashi and Kazuho Watanabe. Unbiased Estimating Equation and Latent Bias under f- Separable Bregman Distortion Measures. IEEE Transactions on Information Theory, 2024.
Vladimir Koltchinskii. Oracle Inequalities in Empirical Risk Minimization and Sparse Recovery Problems: École D'Êté de Probabilités de Saint-Flour XXXVIII-0008. Lecture Notes in Mathematics. Springer, 2011.
Vladimir Koltchinskii and Dmitry Panchenko. Rademacher processes and bounding the risk of function learning. arXiv: Probability, pp- 443-457 2004.
Michael R. Kosorok. Introduction to Empirical Processes and Semiparumetric Inference. Springer Series in Statistics. Springer New York, 2007.
Kenneth Lange. Optimization, volume 95. Springer Science & Business Media, New York, 2013.
Kenneth Lange. MM optimization algorithms. SIAM, Philadelphia, 2016.
Jonathan Li and Andrew Barron. Mixture Density Estimation. In S. Solla, T. Leen, and K. Müller (eds.), Advances in Newral Information Processing Systems, volume 12. MIT Press, 1999.
Pascal Massart. Concentration inequalities and model selection: Ecole Eté de Probabilités de Saint-Flour XXXIII-2003. Springer, 2007.
13

---

Published in Transactions on Machine Learning Research (11/2024)
Cathy Maugis and Bertrand Michel. A non asymptotic penalized criterion for gaussian mixture model selection. ESATM: Probabilily and Stalistics, 15:41-68, 2011.
Cathy Maugis-Rabussens and Bertrand Michel. Adaptive density estimation for clustering with gaussian mixtures. ESAIM: Probability and Statistics, 17:698 724, 2013.
Colin McDiarmid. On the method of bounded differences. In J.Editor Siemons (ed.), Surveys in Combi- natorics, 1989: Invited Papers at the Twelfth British Combinatorial Conference, London Mathematical Society Lecture Note Series, pp. 148 188. Cambridge University Press, 1989.
Colin McDiarmid. Concentration. In Michel Habib, Colin McDiarmid, Jorge Ramirez-Alfonsi. and Bruce Reed (eds.), Probabiisticc Methods for Algorillumic Discrele. Mathemalics, pp- Heidelberg, Berlin, Heidelberg, 1998.
Springer Berlin
Geoffrey McLachlan and David Peel. Finite Mixture Models. John Wiley & Sons, 2004.
Ronny Meir and Assaf Zeevi. Density estimation through convex combinations of densities: Approximation and estimation bounds. Neural Networks, 10:99-109, 02 1997.
Kanta Naito and Shinto Eguchi. Density estimation with minimization of U-divergence. Machine Learning. 90(1):29 57, January 2013.
Tin Lok James Ng and Kwok-Kun Kwong. Universal approximation on the hypersphere. Communicattinns Statislics- Theerry and Melhods, 51:8694 8704, 2022.
Hien D Nguyen. An introduction to majorizaalion-miiniize algorithuns for machine learning and statistical estimation. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, ((2):e1188, 2017.
Hien D Nguyen, TrungTin Nguyen, Faicel Chamroukhi, and Geoffrey McLachlan. Approximations of
conditional probability density functions in Lebesgue spaces via mixture of experts models. Journal of Statistical Distributions and Applications, 8(1):13, August 2021.
Hien D Nguyen, Florence Forbes, Gersende Fort, and Olivier Cappé. An online minorization intorizztioo-mmaimiiattoo algorithm. In Proceedings of the 17th Conference of the International Fedeeration of Classification Socielies, 2022a.
TrungTin Nguyen, Hien D Nguyen, Faicel Chamroukhi, and Geoffrey J McLachlan. Approximation by finite mixtures of continuous density functions that vanish at infinity. Cogent Mathematics & Statistics, 7: 1750861, 2020.
TrungTin Nguyen, Faicel Chamroukhi, Hien D Nguyen, and Geoffrey J McLachlan. Approximation of probability density functions via location-scale finite mixtures in Lebesgue spaces. Communications in Statistics Theory and Methods, pp. 1-12, 2022b.
TrungTin Nguyen, Hien D Nguyen, Faicel Chamroukhi, and Florence Forbes. A non-asymptotic approach for model selection via penalization in high-dimensional mixture of experts models. Electronic Journal of Statistics, 16(2):4742 4822, 2022c.
Haris Papageorgiou and Katerina M David. On countable mixtures of bivariate binomial distributions. Biometrical journal, 36(5):581-60) 1994.
Leandro Pardo. Statistical Inference Based on Divergence Measures. CRC Press, Boca Raton, 2006.
David Pool, William Whiten, and Gcoffrey J McLachlan. Fitting mixtures of kent distributions aid joint identification. Journal of the American Statistical Association, 96:56-63, 2001.
Sonia Petrone. Random Bernstein Polynomials. Scandinavian Journal of Statistics, 26(3):373-38) 393, 1999.
Sonia Petrone and Larry Wasserman. Consistency of Bernstein Polynomial Posteriors. Jourmal of the Royal Statistical Sociely Series B: Statistical Methodology, 64(1):79-100) 1000, March 2002.
14

---

Published in Transactions on Machine Learning Research (11/2024)
Yichen Qin and Carey E Priebe. Maximum Lg-likelihodd estimation via the expectation-mxxiiizatiie maximization algorithm: a robust estimation of mixture models. Journal of the American Stalistionl Associalion, 108 (503):914 928, 2013.
Alexander Rakhlin, Dmitry Panchenko, and Sayan Mukherjee. Risk bounds for mixture density estimation. ESAIM: PS, 9:220-229) 229, 2005.
Meisam Razaviyayn, Mingyi Hong, and Zhi- QuanQuan Luo. Unified Convergence Analysis Block Successive Minimization Methods for Nonsmooth Optimization. SIAM Journal on Optimization, 23(2):1126-1153, 2013.
Gunter Ritter. Robust cluster analysis and variable selection. CRC Press, Boca Raton, 2014.
Ralph Tyrrell Rockafellar. Conver analysis, volume 11. Princeton University Press, Princeton, 1997.
Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: from Theory to Algorithms. Cambridge University Press, Cambridge, 2014.
Alexander Shapiro, Darinka Dentcheva, and Andrzej Ruszczynski. Lectures on Stochastic Progrumming: Modeling and Theory, Third Edition. Society for Industrial and Applied Mathematios, Philadelphia, PA, July 2021.
Wolfgang Stummer and Igor Vajda. On bregman distances and divergences of probability measures. 1EEE Transactions on Information Theory, 58(3):1277-1288, 2012.
Rolf Sundberg. Statistical Modelling by Erponential Families. Cambridge University Press, Cambridge, 2019.
Vladimir N Temlyakov. Convergence and rate of convergence of some greedy algorithms in convex optimiza- tion. Proceedings of the Steklov Institute of Mathematics, 293:325-337, 2016.
Sara van de Geer. Estimation and Testing Under Sporsity: École d d'Été de Probobilités de Soint-Flor XLV 2015. Springer, 2016.
Aad W van der Vaart and Jon A Wellner. Weak Convergence and Empirical Processes: With Applications Slatistics. Springer, 1996.
Jakob J Verboek, Nikos Vlassis, and Ben Krösc. Efficiont greedy learning of Gaussian mixture models. Neural compulation, 15(2):469 485, 2003.
Nikos Vlassis and Aristidis Likas. A greedy EM algorithm for gaussian mixture learning. Neural Processing Letters, 15:77-87 87, 2002.
Halbert White. Maximum likelihood estimation of misspecified models. Econometrica, 50(1):1 22, 1982.
Tong Tong Wu and Kenneth Lange. The MM alternative to EM. Stalistical Science, 25(4):492 505, 2010.
Tong Zhang. Sequential greedy approximation for certain convex optimization problems. JEEE Transactions on Information Theory, 49(3):682 691, 2003.
15

---

Published in Transactions on Machine Learning Research (11/2024)
A Proofs of main results
The following section is devoted to establishing some technical definitions and instrumental results which are used to prove Theorem and Corollary 66 and also includes the proofs of these results themselves.
A.1 Preliminaries
Recall that we are interested in bounds of the form Note that P is a subset of the linear space
U
U KEN
k
[A] 1)
=
and hence we can apply the following result, paraphrased from Zhang 2003 Thm. II.1).
Lemma 8. Let be differentiable and concex function on V, and let (Jk) KEN be sequence of functions obtoined by Algorithm 7 If
d² d ((1 1T) p )q) S 21 oo,
sup (00.))
then, for each le E N,
2001 inf (p) < PEC
(fa)
+ 2
Algorithm Algorithm for computing greedy approximation sequence.
Require: So P for k N do Compute (mx, 0k) arg min x ((1- ((1 Ja-1 + (.1Ix0 3: Define fo = (1 Tx) fa- + T&P (-:8%)
4: end for
We interested in two choices for
(p) KL. (fllp)
(11)
and its sample counterpart,
fXx)+ (XX)) + h (X.)
1 n
log f())+ (YY)) +Y)))
Kn (p)
log
(12)
n
where (Xi)ie(n) and (Yi)se(m) are realisations of X and Y, respectively. We obtain the following important results.
Proposition Let denote either K, the KL divergence and assume that h 2 a and up (: c, for each 0 E O. Then,
or Kn, the sample KL2 divergence 12
4a - 2
x (fx)
inf x (p) PEC
-
k ++2 2
for each & E N, where (fx) is obtained per Algorithm
Proof. See Appendix C.4
Notice that sequences (fi) BEN obtained via Algorithm are greedy approximation sequences, and that Ts E Ce. for each & E N. Let (Jk) be the sequence of minimizers defined by
fk arg min KL, (f Il (1)bh))
(13)
X
16

---

Published in Transactions on Machine Learning Research (11/2024)
and let (fEN)LEN be the sequence of h-MLLEs, as per 5 Then, by definition, we have the fact that k (fx) S (fx) and K (fr.n) & (fk), for x set as or 12 respectively. Thus, we have the following result.
Proposition 10. For the KL, divergence 11 under the assumption that h 2 and 4 (::0) S c, for each
0 E O we have
4a 2c
K (fx) inf K (p) - PEC
(14)
+
for each k E N, where (ft)KeN is the sequence of minimizers defined via KLn diveryence 12 under the same assumptions as abovee we have
13
Furthermore, for the sample
4a 22
Ren (fx.n) - inf Knn (p)
S
(15)
PEC
k +
for each &s E N, where (fR are h-MLEEs defined via 5
As is common in many statistical Cearning/unffrrs convergence results (c.g., Bartlett & Mendelson 2002 Koltchinskii & Panchenko 2004); we employ the use of Rademacher processes and associated bounds. Let (E))ie[n) be ii.d. Rademacher random variables, that is P(s; -1) = P(, = 1) = 1/2, that are independent of (X)))ejm] The Rademacher process, indexed by a class of real measurable functions S, is defined as the quantity
1 Σ (XX));
(s)
==1
for E S. The Rademacher complexity of the class S is given by (.) E supses Rn (s)l.
In the subsequent section, we make use of the following result regarding the supremum of convex functions:
Lemma 11 (Rockafellar 1997. Thm. 32.2). Let n be a conver function on a linear space T, and let S T be an arbilrary subsel. Then,
sup (p) sup 17 (p). PES
PEco(S)
In particular, we use the fact that since a linear functional of convex combinations achieves its maximum value at vertices, the Rademacher complexity of S is equal to the Rademacher complexity of co(S) (see Lemma 21p. We consequently obtain the following result.
Lemma 12. Let (Es)se(n) be i.idd. Rademacher random variables, independent of (X,))e(n) and P defined as above. The sets and P will have equal complerity, (C) Rn(P), and the supremum of the Rodemacher process indezed by C is equal to the supremum the basís functions of P:
Eg sup gEC
Σ g(x))e; = E. sup
(Xx;; Y=1
DEG
Proof. Follows immodiately from Lemma
A.2 Proofs
We first present a result establishing a uniform concentration bound for the h-lifted log-likelihood ratios, which is instrumental in the proof of Theorem Our proofs broadly follow the structure of Rakhlin et al. 2005), modified as needed for the use of KT.
Assume that 0): e for some E Ryo. For brevity, we adopt the notation: Theorem 13. Let XI....,X. Xn be i.i.d. sample of size drawn from fixed density f such that 0 < fxx) S for all x E X, and let h be positive density with 0 < a S h(xx) < for all x E X. Then, for each t> >>0 0, with probability al least - e
[[(())lcc = supgec (T)))
" Σ log ((X.) + M(X.) E, log
9(X,) + h(X,)
g + h f+1
Wi
W2 log 1/2 N(P, e, de
<
w3
h
Vn
c
17

---

Published in Transactions on Machine Learning Research (11/2024)
where w1, W2, and wa are constants that each depend some all of a, b, and c, and N(P, dn,x) is the e-covering number of P with respect to the following empirical La metric
1 Σ (F)(X,) - -x2(x)))
(21,
n2
Remark 14. The bound on the term
n
log 9(1)) + h(Y)) f(X) + hY.))
9 + h f h
E, log
is the same as the above, except where the empirical distance dn,x replaced by dn.y, defined in the same way as dn,x but with Y, replacing X;.
Proof of Theorem
13
Fix h and define the following quantities: 9 - g=gth, f h1 C C h,
((x))
m4 = log ((X)
g(X;) f(X.)
m, = log
Z(I Fn)) =
log
E log
f(X.)'
f(x))*
n
We first apply McDiarmid's incquality (Lemma 23 to the random variable Z. The bound on the martingale difference is given by
1
[( X Xn) Z(X,.... X X,)
Elog
(m1 +... m. +... + mpn
f
E log 9
(m) +... m4 +...+ mn)
f
n
log g(X{)
g ((Xi)
log
f(x))
f(X.) c
1
c b log
c b
log
2log
c..
c c+b)
n a
The chain of inequalities holds because of the triangle inequality and the properties of the supremum. By
Lemma 23 we have
ns²
P(Z - E2-EZ>I PIZ-EZ>e] exp
(V2 stby
ne²
P 2 exp
(V2log ctb y
where it follows from == ne? ne2/(v2 ///2/112lgg ctb}a that 8 = V2 (ctb) V Thorefore with probability at least
et
log
((x)) f(X,)
E, log
E
log
g(X,) f(X))
Ey log g
+ V2llo
c+b
F2 im1
Let (es)ie(n) be i.i.d. Rademacher random variables, independent of (Xi))e(n)- By Lemma 24
log (X.) E, log á
log g(X,)
E
2
f(X.)
f(X))
By combining the results above, the following inequality holds with probability at least -
n
((x,)
E, log g 22E
((X.) log
c t
log
E; f(x,))
+ V2llog
V
f(x.)
c
18

---

Published in Transactions on Machine Learning Research (11/2024)
a(Xx) Now let p: f(X.) 1, such that 4t S P: + 1 etè holds for all e [n]. Additionally, let ny(p) log(p + 1)
that (7) 0 and note that for p E o+b 1, ctb 1] the derivative of n(p)) is maximal at p" o+h
an 1,
a and equal to 7) (p*) = b)/a. Therefore, bFc log(p + 1) is I-Lipschitz. By Lemma
22 applied to ry(p);
((x)) log
4(c +(c+b) b)
(X;)
2 E
= 2
E
8
8 c
11
f(x.)
c
1=1
c
71 i=1
(X.)
4(c +
b]
x(X,)
4(c + b) E
E
+
f(x,)
a
a
1=1
4(c+b) + b)
g(Xi)
4(c + b)
1
E
a
f(xi)
a
Vn'
where the final inequality follows from the following result, proved in Haagerup
1981
1/2
E
E S
E
72
Vn
Now, let ((())) a- ((x.)/ and note that
(k((u)) - Ev(()) If(x,))
[u(x)) o(X,)) S |u(X,) o(X,)).
By again applying Lemma 22 we have
4(c b)
n g
g(x))
8(c 8(c+b) E
E
Es
g(X))&,
a
f(X.)
a²
72
c
1=1
8(c 8(c+b) + b)
8(c + 6)
E
(X,)e
+
E
h h(X:)s;
a²
72
a²
1=1
c
i=1
+ 8(c
b)
8(c + b)
E
(x,))c,
+ a²
Vn"
Applying Lemmas 12 and 25
the following inequality holds for some constant K > 0:
E, sup
Σ
((x));
= E sup oe
Σ ((x;0)e
K E
f log!
1/2 N(P,e,
(16)
gEC
n
and combining the results together, the following inequality holds with probability at least 1 e
log ((X,) f(X,) f
g 8(c+ 6)
L log 1/2 L//=N(P,E,, E, e( +
(8b 44) + b)
(ctb) 6
E, log
<
E
+ v2log
a² f
V²vn
n
a
n
E
log 1/2 N(P, e, )n
W2 + W3
(17)
n
where Wi, W2, and Wa are constants that each depend on some or all of a, b and c.
Remark 15. From Lemma 25 we have that O = supjeæ po. To make explicit why 2an
(supgec Png2) = 2c, let F = C and observe
0 = sup
P.g = sup
1
Σ
g(x,)²
< 1 Σ = 2
GEC gEC n
1=1 n 1=1
19

---

Published in Transactions on Machine Learning Research (11/2024)
Since our basis functions (p(,0)) are bounded by c, everything greater than will have value O and hence the change from 2c to is inconsequential. However, it can also be motivated by the fact that sp(;0) are positive functions.
As highlighted in Remark 14 the full result of Theorem 13 relies on the empirical Lg distances a and da.y. In the result of Theorem 3 we make use of the following result to bound d, and dn.y.
Proposition 16. By combining Lemmas 18 and 19 the following inequalities holds:
log NogN((,, 11-1 S log (P(P:e e, I11 S log N(P, E.P,e//,,11 11
where &1 is the e-bracketing number of P. Therefore, we have that log N(P, xn s log (P,, and log ((,, dn.)) s log N(P.e2 1l.))
With this result, we can now prove Theorem
Proof (of Theorem 5). The notation is the same as in the proof of Theorem may change from line to line.
13 The values of the constants
+ En log f E, log
f
KLA ffll - KL (fll = Ey log
En log
Jk,
fk.
fk:
fk
= Ey log
f
1
log
i(X.)
log
f(X.)
+ En log
j
log
j(Y))
Σ
log j(Y))
fk.n
Ti
fkmm (X,)
fanm (X.)
fr.n(Y)
fk.n(Y))
1=1
t=1
i=1
j
n
log f(Xi)
1
f(X.)
f
f(Y.)
1 n
f(Y.)
E,
log
log
En, log
+
log
log
fk
(X,)
n
(X.)
fk
fi((Y))
n
(Y,)
i=1
i=1
i=1
f
n
f(X.)
((3))
ES
log
log
E₁ log
log
fR,
(x,n(Xi)
fk
f
i=1
f(X.)
f fkk
log j(Y:)
+
log
Ey log
+
En log
fx().)
fx,))
fk
f(X.)
F(X.)
log f(X.)
log f(X))
+
log
log
(X.)
(x.)
Jn,n(Yi)
fa,)))
i=1
((X.)
log g(Y))
sup
log
E log
+ 2sup
En log
f(X.)
f(Y.)
aEč
1
F(X.)
f(X,)
f(Y.)
log F(Y))
+
log
log
+
log
(Xi)
Fx(),))
(Y.)
Fa()))
i=1
1=1
w
log 1/2 N(P, E, dn, de }
w
t
fx())))
< 2 E
+
+
wg
V
log
vn
n
12.
(x,n(X))
W ( log 1/2 1/2 N(P, e, dn
wy
log Fo(Y))
+ 2 E
}
+
w
Vn
72
(k,
< W1 V
log N(P, [
W2 + w3
t
(x))
log (x,) Jr.n (Y,)*
1 / lle +
log
(X.)
with probability at least 1 - et, by Theorem target density fe, obtaining the following:
13 Now, we can use
15 from Proposition 10 applied to the
KL, (f& fk.n) =
fu())) n i=1 (xi)
1 Σ log
+ Σ
log
(x))))
4a -222
+ inf KL, (frs llp)
k +
Dec
i=1
20

---

Published in Transactions on Machine Learning Research (11/2024)
Since by definition we have that für E C, inf pec KL (fr lI)) and with probability at least 1 - e we have:
KT (f.1) KT. (f
Vn [
W1
N(P, ll +
vn w0
t
W4
(18)
+
We can write the overall error as the sum of the approximation and estimation errors as follows. The former is bounded by [4), and the latter is bounded as above in (8). Therefore, with probability at least 1 e
KL (f |l fk,m) KLn (f
[KLa (fl - KL, (fllC) + [KLn (f - KL. (f])
W4
W1
[ log N(P, Ilw + 02 + uis way F. n
(19)
k +2
As in Rakhlin et al. (2005), rewrite the above probabilistic statement statement in terms of expec- tations. To this end, let
A W4
+
log' 12 N(P,E/2.11 -1loo) +
W2 Vn'
k+2
Vn
J
and 2 = KL,, (f11)K,)) - KTn (S|IC). We have shown P (E way 1. S See Since 2 0,
P(2 A s)ds. E(2) = // P(z s)ds / P(2 s)ds S A+
Setting wyy / 4, we have t w and E[2) S A+ 5
winss ds S A vu
Hence,
E (KLx [x,)) KL. (/11C)
C1
02
c log
1/2 N (P,e/2, || 1lo de + 43
k +
Jo
where C1, C2 and are constants that depend on some or all of b, and c.
Remark 17. The approzimation error characterises the suitability of the class C, i.e., how well functions in C are able to estimate a target f which does not necessarily lie in C. The estimation error characterises the ervor arising from the eslimalion of the largel J on the basis of the fovile sample of size n.
Proof of Corollary 0 Let X' and θ be compact and assume the Lipshitz condition given in continuously differentiable, then
If (px;;) is
Op (x; a0,
Oyp (a; 00
(z; 1 (x:TT]
Σ Am
(0%)
10, Tal
sup e"
(0r)
110 7111
Setting
O.p (z; -)
+ (x) sup
(0-)
0" 0-
00
we have ||0 < co. From Lemma 20 we obtain the fact that
log Ni (P, 21 11x6) S log (0, ll 1l,o),
which by the change of variable d = 2=| = = == 6//2||1 implies
log N1 (P,e/2,11 II S log (8, 0
41|001100 -
-,
|l- (11111)) ll.)
Since θ C Rd, using the fact that Euclidean set of radius has covering number N (r, S (2r) we have
log
(, 11 111) < d dlog
E
12 ( diam (9)
4 +
E
21

---

Published in Transactions on Machine Learning Research (11/2024)
So
So Vlog (o, s and since c < oo, the integral is finito, as required.
11 11 ds S /-¹ /alog 12 diam (0)
de,
B Discussions and remarks regarding h1-MLLS
In this section, we share some commentary on the derivation of the h-lifted KL divergence, its advantages and drawbacks, and some thoughts on the selection of the lifting function h. We also discuss the suitability of the MM algorithms in contrast to other approaches (e.g., EM algorithms).
B.1 Elementary derivation
From Equation 4 we observe that if X arises from a measure with density f, and if we aim to approximate f with a density E co2(P) that minimizes the h-lifted KL divergence KL, with respect to f. then we can define an approximator (referred to as the minimum h-lifted KT, approximator) as
U/ (f + loghf hhdd / (s + hi logig h)dp
fu = arg min gEcos (P)
/ (ʃ + h) logig + h2dd = arg max
/ [s + h3 log + h3du,
arg min (P)
g (P)
noting that fxi h3 logif + h3du is constant that does not depend on the argument g. Now, observe that
/ logig + h hddp = Ey logig + h} and / f flogig + h)dp = E, logig + h)
since both f and & are densities on X with respect to the dominating measure μ. If sample X,, = (Xi)selmi is available, we can estimate the expectation E, logig + h} by the sample average functional
log(o(X,) +(X.)),
resulting in the sample estimator for fs:
fk.n = arg max gEens(P)
log ( (XX) + +(X))) + E, logig + h}
which serves an alternative to Equation 5 However, the expectation E, logig + h} is intractable, making the optimization problem computationally infeasible, especially when X' is multivariate (i.e., X C Rd for d > 1); as integral evaluations may be challenging to compute accurately. Thus, we approximate the intractable integral E, log(g g + h} using the sample average approximation (SAA) from stochastic programming (cf. Shapiro et al. 2021 Chapter 5), yiclding the Monte Carlo approximation
log(g(Y)) A(Y))
n1
for sufficiently large nı E N, where each Y, is independent and identically distributed random variable from the measure on X' with density h. This approach provides an estimator for fo of the form
fknm, = arg max gEco
Σ n
log(g(X.) +(X.)) + log(g(Y)) + +n(Y))
1=1
22

---

Published in Transactions on Machine Learning Research (11/2024)
which is exactly the h-MLLE defined by Equation 5 when take nı n. Notably, the additional samples Y, (K))e())) provide no information regarding E, log + h), which is the component. of the objective function coupling the estimator with the target f. However, it offers a feasible mechanism for approximating the otherwise intractable integral E,, log(g + ht..
By setting n = n for the SAA approximation of En log + h}, the convergence rate Theorem remains unaffected. Specifically, for any >> 0,
g(x)) + +(X.) E log + h f(X,) h(X,)
wi E Elgg 1/2 N(P, dn.adde W3
W2 vn
log
+
h
Vn
and
log g(Y.) + l(Y))
f(Y,) + h(Y)) E, log g+1 h f h
1
W1
E Elog 1/ N(P,,, dn +
W2
+
Way
t n
Vn
1=1
with probability at least - e as noted in Remark ([l/vn)+O(v(p))) the combined bound in the proof of Theorem in Appendix A.2 is also of this order, as required.
14
Given that both upper bounds are of order
Finally, to obtain the additional samples Y,, = (Y)), simply simulate Y, from the data-generating process defined by h. Since can choose h freely, selecting an h that facilitates easy simulation (e.g., h uniform over X, which remains bounded away from zero on compact set) is advisable for satisfying the requirements of our theorems.
B.2 Advantages and limitations
As discussed extensively in Sections and 2 our two primary benchmarks are the MLE and the least Ta estimator. Indeed, the MLE is simpler than the h-MLLE estimator, as it takes the reduced form
1 n
fu.n arg max gEco,(P)
log (X,),
and does not require a sample average approximation for intractable integrals. It is well established that the MLE estimates the minimum KL divergence approximation to the target f
/ f log
[ap KT. (fllg).
Sa arg min (P)
g
However, as highlighted in the foundational works of Li Barron 1999) and Rakhlin et al. 2005). controlling the expected risk
E { KL (fll - (LIIC))
requires that f 2 y for some strictly positive constant y > O. This requirement excludes many interesting density functions targets, including those that vanish at the boundaries of X, such as the 1/2 distribution, those that vanish in the interior of X, such examples fi and fz in Section 4.2 Consequently, the condition is restrictive and often impractical in many data analysis settings.
Alternatively, one could consider targeting the minimum L2 estimator:
fk arg min / (s - dd arg min / 1²- 2fg + - (P)
-2 / fgdu+ + / grdu)
gd arg min
gEcox(P)
(Ecox(P)
Using a sample X, generated from the distribution given by S, the first term of the objective can be approximated by - integral that cannot be approximated by Monte Carlo sampling from a fixed generative distribution, as it depends on the optimization argument g. Thus, unlike the h-MLLE, is feasible to reduce this intractable integral to sample average, which implies the need for numerical approximation in practice. This can be
which is relatively simple. However, the second term involves an intractable
23

---

Published in Transactions on Machine Learning Research (11/2024)
computationally complex, particularly when g is intricate and X' is highh-dimensional. Hence, the minimum I2-norm estimator of the form
_ n - i=1
fk.m = aagaagmn min gEco.(P)
g(Xi) + g g2du
is often computationally infeasible, though its risk
E | fk.mll
inf II g|12 gEC
can be bounded, as shown in the works of Klemelä (0007) and Klemelä 20099), even when minx f 0. In comparison with the minimum L2 estimator and the MLE, we observe that the h-MLLE allows risk bounding for Largels not bounded from below (i.e., minx f = 0), without requiring intractable integral expressions. The h-MLLE achieves the beneficial properties of both the MLE and minimum L2 estimators, which is the focus of our work.
Other divergences and risk minimization schemes for estimating f, such as 3-likelihoods and Lg likelihood, could also be considered. The by likelihood, for instance, provides maximizing estimator with a simple sample average expression, similar to the MLE and h-MLLE. However, lacks a characterization in terms of proper divergence function, such as the KL divergence, h-lifted KL divergence, or L2 norm. Consequently, this estimator is often inconsistent, as observed in Ferrari & Yang (2010) and Qin & Priebe (2013) These studies show that the Lg likelihood estimator may not converge meaningfully to f, even when f E co2 (P)) for any fixed E Rso (1), unless a sequence of maximum Lg likelihood estimators is constructed with depending on n and approaching to approximate the MLE. Thus, the maximum Lg likelihood estimator does not yield the type of risk bound we require.
Similarly, with the 3-likelihood (or density power divergence), the situation is comparable to that of the minimum Le norm estimator, where the sample-based estimator involves intractable integral that cannot be approximated through SAA. Specifically, the minimum S-likelihood estimator is defined as (cf. Basu ct al. 1998):
[ -
[+
n2
fu.n = arg min (Ecoy(P)
1
Σ i=1
g
(x.) +
B
for B 0, which closely resembles the form of the minimum La estimator. Hence, the limitations of the minimum Le estimator apply here as well, although risk bound with respect to the B-likelihood divergence could thcoretically be obtained if the computational challenges are disregarded. In Section L3 we cite
additional estimators based on various divergences and modified likelihoods. Nevertheless, in each case, one of the limitations discussed here will apply.
B.3 Selection of the lifting density function h
The choice of h is entirely independent of the data. In fact, h can be any density with respect to satisfying < a < h(x) < b < oc for every x E X. Beyond this requirement, our thcoretical framowork remains unaffected by the specific choice of h. In Section 4 we explore cases where h is uniform and non-uniform, demonstrating convergence
both Is and n that aligns with the predictions of Theorem 5 For practical implementation, as discussed in Appendix [..] h serves as the sampling distribution for the sample average approximation (SAA) of the intractable integral E, logig h]. Given its role a sampling distribution, it is advantageous to select a form for h that is easy to sample from. In many applications, we find that the uniform distribution over X is an optimal choice for h, as it meets the bounding conditions.
We observe that although calibrating h does not improve the rate, it does influence the constants in the upper bound of the final equation of Equation 19 Specifically, for each t > 0, with probability at least ct
11 Vπ
[ log 1/2 (P,,e/2,1 11.0 11. +
W2 + w3
E -
W1
KL. (f fn. - KL. (f(C)
+
k 2'
24

---

Published in Transactions on Machine Learning Research (11/2024)
which contributes to the constants in Theorem 5 Letting denote the upper bound of the target (i.e. (xx S ce< oo for every E x), make the following observations regarding the constants:
c + 1 x
W2 & (8b+ + 4a)(c +
(
c (c+
Wig x log
Wig & a²
a
a²
Here, Wh, W2, and Wa are per the final bound in Equation 17 in the proof of Theorem from the bound in Equation 15
13 while wy arises
When h is uniform, it takes the form h(z) 2, where == 1/ fx du, making = === b. If h is non-uniform, then necessarily a < 2 < b, as there would exist a region 2 of positive measure where h(x) > 2, which implies that h(x) < z for some x E \ otherwise,
J hdp | hdpp + /x/ hdp
m(2) x(X)
u(x 2) x(x)
1,
contradicting h being density function. Although Sctting h = 2 minimizes the numerators in w1, as deviations from uniformity increase the numerators of wi and w4 while decreasing the denominators. The same reasoning applies to W2:
cannot control can choose h to control and b.
(8b (c)(c+ U2 x
8be a
4c
862
4b .af
a²
a
Since с O, any deviation from uniformity in h either increases maintains the numerators while decreasing the denominators, minimizing w2 when h is uniform. The same logic applies to W3, as the logarithmic function is increasing, so Wy is minimized when h is uniform.
Consoquently, we conclude that the smallest constants Theorem are achieved when is chosen as the uniform distribution X. This suggests that a uniform optimal from both practical and theoretical perspectives.
B.4 Discussions regarding the sharpness of the obtained risk bound
Similar to the role of Gaussian mixtures as the archetypal class of mixture models for Euclidean spaces, beta mixtures represent the archetypal class of mixture models the compact interval [0, 1], as established in the studies by Ghosal b: Petrone (1999). Just as Gaussian mixtures approximate any continuous
density on X' = Rdd to an arbitrary level of accuracy in the Lp-norm (Nguyen et al. 2020 2021 2022b).
mixtures of beta distributions can similarly approximate any continuous density on X [0. 1 with respect
to the supremum norm [Ghosal 2001 Petrone 1999 Petrone Wasserman 2002).
We will leverage this
property in the following discussion.
Assuming the target. f is within the closure of our mixture class C (ie., KL, (fIIC) 0). setting k, (vv)) achieves convergence rate in expected KL, of O(I/VR) for the mixture maximum h-lifted likelihood estimator (A-MLLE) fk,, An interesting question is whether this rate is tight and not overly conservative, given the observed rates in Table [ We aim to investigate this question by discussing a lower bound for the estimation problem.
To approach this, we use Proposition 3 observe that KL, satisfies a Pinsker-like inequality:
KL (1ll)) 2 TV(,g),
where TV(J,) = 1/2 fx g/du. Using this inequality along with Corollary and the convexity of - ʃ2 we find that the h-MLLE satisfies the following total variation bound:
E (T.
Vkn
V
Wi.f kn
W2.5
WI.f
W2,f
< Wf
Vn
1/2
n1/4
n//4
for some positive constants wi,f, W2,,, wy depending on f. by taking kn = Vn. Now, consider the specific case when X' [0, 1), and the component class P consists of beta distributions. In this case, we have (ef.
25

---

Published in Transactions on Machine Learning Research (11/2024)
Petrone & Wasserman 2002
Eq. 5), for any continuous density function 10, 1] + Rgo:
inf sup [f(x) g(x)l 0, which implies that inf KL (f 0, gec
gEC [E(1.
since
sup -f())- L2(f.9) 2 VRLI, (f
zE[0.1]
for any 0 < 7 S h, with the second inequality due to Proposition 3 Thus, for a compact parameter space e defining P. we assume KL, (f = 0. Consequently, the rate of O(n-1/4) for expected total variation
distance achievable in the beta mixture model setting. This convergence is uniform in the sense that
E
S 1/1
where w depends only on the maximum 2 f, the diameter of O, and the condition KLs (flIC) = 0, with component distributions in P restricted to parameter values in O.
In the context of minimum total variation density estimation on [0, IJ, Exercise 15.14 of Devroye & Lugosi 2001h states that for every estimator f and every Lipschitz continuous density (with sufficiently large Lipschitz constant),
sup Ey {TV(
W n3/3'
SELip
for some universal constant W depending only on the Lipschitz constant. This lower bound is faster than our achieved rate of Onn-1/4), but it applies only to the smaller class of Lipschitz targets, a subset of the continuous targets satisfying KL2 (flIC) 0.
The target f2 from our simulations in Section belongs to the class of Lipschitz targets, and thus the improved lower bound rate of O(n-1/3) from Devroye & Lugosi (2001) applies. We can compare this with vn for Experiment 2 in Table yielding an empirical rate in n of O( (0nn-103), with an exponent between -1.07 and 0099 (95% confidence), over the range n E {2 21 Clcarly, this obscrved rate is faster than the lower bound rate of O(n On-1/3), indicating that the faster rates observed in Table are due to small values of n and k. As n increases, the rate must eventually decelerate to at least O(n 1/5 when the target f is Lipschitz on X, which is only marginally faster than our guaranteed rate of (0(n1/4). Demonstrating that O(n 0/411/4) is minimax optimal for certain target classes f is a complex task, left for future exploration.
Lastly, we note that our discussions in this section implies that the h-MLLE provides an effective and genetic method for obtaining estimators with total variation guarantees, which complements the comprehensive studies on the topic presented in Devroye Györfi (1985) and Devroye & Lugosi (001).
B.5 The KL divergence and the MLE
For any probability densities and g with respect dominant measure μ on X, the h-lifted KL divergence is defined
KL, (f -
f [(++)) log (1+ (g
dp,
which we establish Bregman divergence the space of probability densities dominated by μ X' in Appendix C.1
We previously demonstrated a relationship between KT, and the Lz distance (Proposition 3 showing that if h(x)) 2 0 for all x E X, then
f (
KL, ( l1 < 12(S.)), where 13(S.g) - 212
is the square of the L2 distance between the densitics. Given that always select h(x)) 2 7, this bound is always enforceable. This relationship is stronger than that between the standard KL divergence and the Le distance, which similarly satisfies
KL (1 S 12(f.9).
26

---

Published in Transactions on Machine Learning Research (11/2024)
but with the more restrictive requirement that f(z) 2 7 0 for every X, limiting its applicability to
densities that do not vanish. In the proof of Proposition 3 in Appendix
C.2
we show that one can write
h 9 ++
KL (f = 2KLL
2
2
which allows the application of the theory from Rakhlin al. (2005) by considering the mixture density (f + 222 as the target and using g + h as the approximand, where g coε (P). Under this framework, the maximum likelihood estimator can be formulated as
-
- log 71
g(Z,) + h(Z.)
fkin E arg min gEooy (P)
2
1=1
where (Zm) are independent and identically distributed samples from a distribution with density (22 This sampling can be performed by choosing X; with probability 1/2 or Y with probability 1/2 for cach E [n], where X, is an observation from the generative model f and Y; an independent sample from the auxiliary density Although the modified estimator, based on the bound from Rakhlin et al. (2005). attains equivalent convergence rates, inefficiently utilizes observed data, as 50% of the data is replaced by simulated samples Y,. In contrast, h-MLLE estimator maximally utilizes all available data while achieving the same bound.
B.6 Comparison of the MM algorithm and the EM algorithm
Since the risk functional is not log-likelihodd, straightforward EM approach cannot be used to compute the M-LE However, by interpreting KL, as a loss between the target mixture hf+ and the estimator (fk. + h)/2, an EM algorithm can be constructed using the standard admixture framework (see Lange 2013 Section 9.5). Remarkably, the FM algorithm for estimating (fk,n + h)/2, has the same form as our MM algorithm, which leverages Jensen's inequality (cf. Lange 2013 Section 8.3). fact, the majorizer in
any EM algorithun results directly from Jensen's 's inequality (see Lange 2013 Section 9.2), making our MM algorithm in Section 1.1 no more complex than an EM approach for mixture models.
Beyond the EM and MM methods, other standard algorithms typically address the generic estimation of k-component mixture model in coą(P) for a given parametric class P. Since our MM algorithm follows structure nearly identical to the EM algorithm for the MLE of this problem, it has comparable iterative complexity. Notably, per iteration, the MM approach requires additional evaluations for both X,, and Y,. and for g(X)) and h(X,), so it requires a constant multiple of evaluations compared to EM, depending on whether h a uniform distribution or otherwise (typically by a factor of or 4).
B.7 Non-convex optimization
We note that the 4-MLLE problem (and the corresponding MLE) are non-convex optimization problems. This implics that, aside from global optimization mothods, no itcrative algorithm-whether gradicnt- basod methods like gradient descent, coordinate descent, mirror descent, or momentum-based variants can be guaranteed to find global optimum. Likewise, second-order techniques such as Newton and quasi-Newton methods also cannot be expected to locate the global solution. In non-convex scenarios, the primary assurance that can be offered is convergence to a critical point of the objective function. In our case, this assurance is achieved by applying Corollary 1 from Razaviyayn et. al. (2013), as discussed in Section 4.1 Notably, this convergence guarantee consistent with that provided by other iterative approaches, such as EM, gradient descent, or Newton's method.
Additionally, it may be valuable to examine whether specific convergence rates can be ensured when the algorithm's 's iterates approach a neighborhood around a critical value. In the context of the MM algorithm, we can affirmatively answer this question: since the h-MLLE objective is twice continuously differentiable with respect to the parameter th, it satisfies the local convergence conditions outlined in Lange (2016) Proposition 7.2.2). This result implics that if w lies within a sufficiently close neighborhood of local minimizer vig. the MM algorithm converges linearly to vt. This behavior aligns with the convergence guarantees offered
27

---

Published in Transactions on Machine Learning Research (11/2024)
by other iterative methods, such gradient descent line-search based quasi-Newton methods. Quadratic convergence rates near 2 can be achieved with a Newton method, though this forfeits the monotonicity (or stability) of the MM algorithm, as it is well-known that even in convex settings, Newton's method can diverge if the initialization is not properly handled.
An additional advantage of the MM algorithm over Newton's method is its capacity to decompose the original objective into sum of functions where each component of t/s (M...... Thy . 0x) ) is separable within the summation. In other words, can independently optimize functions that depend only subsets of parameters, either ( TT) each 8, for computation. This characteristic is noted after Equation g in the main text. Such decomposition can lead to computational efficiency by avoiding the need to compute the Hessian matrix for Newton's method or approximations required by quasi-Newton methods. Specifically, in cases involving mixtures exponential family distributions such as the beta distributions discussed in Section 4.2 each parameter-separated problem becomes strictly concave maximization problem, which can be efficiently solved (sce Proposition 3.10 in Sundberg 2019
I....,k, thereby simplifying the iterative
C Auxiliary proofs
In this section, we include other proofs of claims made in the main text that are not included in Appendix A
C.1 The h-lifted KL divergence as Bregman divergence
Let + h, so that Φ(u) log(ū) ū Then ('(u) = log(ū), and
/ (flog(f) - -- 1) (ğlog(0) 9 1} log(0)(f g)dp f ílog(") Glog(ā) - f log(ā) + log(
D&(f gl
/ If + -b)log(F) - (g + h1 (og(ū) of flg(() + lo
f ( 113 log x
f f+ h+hdp= du KL. lfllg).
g+h
C.2 Proof of Proposition 2
Let f f+h and = -gght, h. Since is positive, there exists some ÿ. such that ÿ. infzex (g(x) M(x)) > 0. Similarly, since X is compact, there exists some positive f such that 0 < f supaex (f(x) + h(x)) <0.. Define M = sup log(f(=)/0(z)). Then M < co, and
f KL. (f = f flog _du s sup log
I _ fdp = 2M < xo.
sex
C.3 Proof of Proposition 3
Defining f and ğ as above, we have
/ flog
i Ap < [ j (g (1-1) dy [ (f ()-
KL (f
ğ dp S ---51-11000 -I
g
The first inequality comes from the fundamental inequalities on logarithm log(z) < x for all x 2 Indood, let f(z) log(x) x + 1. We obtain f'(x) = - I=z, Then f'(x) 0 and f'(x) 2 0 if s 1. Therefore, f is strictly decreasing on (1, o0) and strictly increasing on (0, 1]. This leads to the desired inequality (() < f(1) for all 0.
28

---

Published in Transactions on Machine Learning Research (11/2024)
The next equality comes from the following identities:
fi ljdk
/ p- 1-110 du
/
p fg
5g
du /
(f
g
/
(J g)²
du
du.
9
x
9
x 9
The last equality is followed from
fg f 09 du
+)ja+ Sx fdut / zdpt - - ( h)du+ Sx (a + h)du - - hdp +
S hdy O.
9
In fact, the proof of Proposition 3 follows the standard technique in the derivation of the estimation error, see for example Meir & Zeevi 1997..
Additionally, we can show that the h-lifted KL divergence satisfies a Pinsker-like inequality, in the sense that
VKL (f 2 TV(f.g),
where TV represents the total variation distance between the densities S and g. Indeed, this easy observe since
f+h 2KL
KL (fllg) = / (f + 11 log
f+h h du = 2 { h
2
ff h g g+h
log
du
y +
2
g+hh
2
2
f+h 2
g g+h
f
+
h
9 h
(1 { If - slldu (V))).)).
15-
2 4
de
du
x'
x
2
2
2 x
where the inequality due Pinsker's inequality:
(T
C.4 Proof of Proposition
For choice
11 by the dominated convergence thcorem, we observe that
d²
d2
f+h
d2
f + h
K ((1 p + πq) = E
log
E
log
d
d
[1 T)P + TQ +
d
(1 π + Tq +h
(p 4)
(p 9)²
= E
+ E₁
[[1 ((1-T) T)p + nq + h13
[(1 π) p xq hi
Suppose that each (::0) E bounded from above by < co. Then, since p.g E C are non-
negative functions, we have the fact that (p 2)= s c². If we further have a S h for some a > 0, then
[11 x)ppppp + + n1² 2 a², which implies that
d
((1 - TT) πq) 2 a
2
for every q E C and क E (0, 1), and thus
d ki ((1 - T) mq) - 26
d²
sup
a² x0.
EE(
Similarly, for case
12 have
d²
d²
f(x:) + ((x;)
d (6 - T)p + nq)= =
Σ
log
?
(1 pz) कe (x.) + (x,))
29

---

Published in Transactions on Machine Learning Research (11/2024)
d²
(yi) + h (yii
log
d (1 (1=x)p (We) + uq (1i) + h (11)
(xi) - q (xi))²
(x - 9 (v:))
+
1=1 [[1 - (z,) + лh (x,) + h (x:)]
==1 - x) (3r) + xq (vs) + h (y)))²
By the same argument, as for K, have the fact that (x) q (x))) 2, for every p.q C and every
x X, and furthermore [[1 π) p (z) uq (x) + h (x))² 2 a² for any π E (0, 1). Thus,
d²
2c
sup (0,,) d ((1 - π) + mq) S a²
< 00, as required.
D Technical results
Here collect some technical results that required in proofs but appear elsewhere in the literature. In some places, notation may be modified from the original text to keep with the established conventions herein.
Lemma 18 Kosorok 2007 Lem 9.18). Let N( e, II) denote the e-covering number of f, ( the bbbackktingg number of F,, and || be any norm on F. Then, for all >>
N( 11 11 II) = Ni(5 e, II)
Lemma 19 Kosorook 2007 F,
Lem 9.22). For any norm ||||| dominated by || 1lo and any class of functions
11,11.11 log (1 2s, ||. (1) S log N( e, ll llo)): for all e >
Lemma 20 (Kosrook
2007
Thm 9.23). For some metric d on T, let & = (f:: :t: be a function class:
[fa(x) f((x) s d(s, ().)).
some fixed function F on X, and for all X' and s, t T. Then, for any norm |I-
( 26 F
II) S N(T,s,
Lemma 21 (Shalev-Shwartz & Ben- David
2014), Lem 26.7). Let A be subset of Th and let
Σ ojaz N,N, E A, 2 0, 11/la//1= =1 }
= Rr, (A)) i.e., both A and A' have the same Rademacher complerity. Lemma 22 (van de Geer 2016 Thm. 16.2). Let (Xi)ieti be non-random elements of X and let F be class of real-valued functions on X. If pi : R + R, i E [n], are functions vanishing at zero that satisfy for all u, U. E R, (p:(4)) (v)) < |u vl, then we have
Then,
1 2E
E Σ (x(((X
Σ s(X))e:
Lemma 23 MMDiaariid 1998 Thm. 3.1 or McDiarmid 1989 Suppose (Xi) are independent random variables and let Z = g(x1....,X, Xn), for some function 9- If satisfies the bounded difference condition, that is there exists constant ej such that for all j E [n) and all æı,... ai,...,,,j,t, J'y Enz
1g(01 19( - 111
g(
g( ..........
.......,JJ-J IJ- o/g, x ... fnll $ cj.
then
2t
P(Z - EZ 2 2) < exp
Σイ=
30

---

Published in Transactions on Machine Learning Research (11/2024)
Lemma 24 van der Vaart & Wellner 1996. Lem. 2.3.1). Let Rif) = Ef and Eia If
Φ Rs0 - Ryo is convec function, then the following inequality holds for any class of measurable functions ;;
Ed (I)S(()) - Hr (f)lg) - EΦ (f)l
where (f) is the Rademacher process indened by $ In particular, since the identity map connex,
E ([( Rn (f) - 2E (()))
Lemma 25
Koltchinskii 2011 Thm. 3.11). Let dn be the empirical distance
f2), E -
and denote by E( da) the e-covering remmber of F. Let o = supfes Paf. inequality holds
Then the following
K
20n
(f]lb(())sss
E
log
log
1/2 1/ N(F e,
vn
for some constant K > 0.
31


Reviews:
[{"review_id": "17nWTSHC0L", "reviewer": "Reviewer_gqi7", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: Adding a lower bounded density function to a given model is interesting. In addition, the paper is well written.\n\nWeakness\n(1) My main concern is that all the theoretical results are derived in terms of the excess risk of the h-lifted KL diverges. It is not clear what are the relations between the h-lifted KL divergence and the original KL divergence (or the original L2 distance). To me, all of the results are about the $f+h$ instead of $f.$ Since $f+h$ is lower bounded, I think that existing results can be applied. \n\n(2) I could not find discussions about the choice of $h$ in practice.  \n\n(3) Computation is another concern. A standard EM may not be easily applicable and so the authors developed an MM algorithm. I wonder how efficient is the proposed MM algorithm compared to the computation algorithm for the minimum L2 distance estimator.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors proposed a special divergence so called the h-lifted KL divergence and proved the convergence rate\nof the excess risk of the MLE corresponding to the h-lifted KL divergence. The advantage the authors claim is that their theoretical\nresults are valid for densities not lower bounded.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "(1) There must be results about the convergence rate of the density estimation of $f$ rather than $f+h.$\n(2) I want to hear why existing theoretical results for lower bounded density and KL divergence cannot be applied for the estimation\nof $f+h$ that is lower bounded.\n(3) Discussions about the choice of $h$ must be given for practical applicability of the proposed algorithm.\n(4) Some analysis for the efficiency of the MM algorithm compared with existing algorithms should be done.", "broader_impact_concerns": "I do not think any ethical concerns exist.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "YxqEMOoE3F", "reviewer": "Reviewer_Wawz", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:** The strength of this paper is the theoretical result on the risk bound, which complements previous results known in the literature.\nWe like the link with the more general class of Bregman divergences.\n\n**Weaknesses:** Even if the main contribution is theoretical, we find that the computational tests rather weak.\nWe would have expected some empirical studies on mixtures of known densities (e.g., a mixture of 3,4,5 Gaussians) with an increasing number of sample points and then empirical studies of how this theoretical bound meets practice.\nThis type of test (by considering a mixture of other known probability densities) could help establish whether the risk bound is tight or not.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents a new (theoretical) risk bound for risk density estimation using a so-called $h$-lifted Kullback-Leibler divergence. \nThe main contribution is the proof that the new bound based on this divergence is correct.\nThe literature on previous bounds, using different divergences, seems complete and updated.\nThe authors present some computational results to show that the proposed $h$-lifted Kullback-Leibler divergence can be computed in practice and used to estimate the density of function given a finite sample of observed data.\n\n**Disclaimer:** This paper falls out of my main research interests. Hence, I might have misunderstood some points.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Since this paper is out of my main research competences, I rely on the requests of the other reviews.\n\nIn the previous paragraphs, I have suggested some possible computational test, but they are not mandatory for acceptance.", "broader_impact_concerns": "This is mainly a theoretical result without any direct ethical implications.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "w3KtjUfowZ", "reviewer": "Reviewer_u7g9", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The authors propose a new extension of KL divergence to obtain a more sample-efficient estimator and provide a theoretical analysis of this divergence. \nThe paper is a bit hard to read through as there are many mathematical proofs included in the formal contents and there are no clear connections between those propositions, lemmas, and theorems. It is also not clear how those theoretical results can bring some benefits in practical scenarios. The experiments are too simplified to demonstrate any realistic applications.  \nAs I'm not an expert in measure theory or a closely related field, I can not make a judgment about the novelty of this work. I'm not able to verify all the proofs either. \nIn my understanding, this work is more about statistics than machine learning and its contribution to the community of machine learning is dubious. Detailed questions are below.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors introduce the h-lifted Kullback–Leibler (KL) divergence as a criterion for conducting risk minimization and prove an $O(1/\\sqrt{n})$ bound on the expected estimation error under a compact support assumption when using this divergence.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. In Eq.(4), why this $Y_i$ variable is needed in the estimator? If it's just a random noise independent of $X_i$, it can't bring any extra information.  In a practical scenario, how to define it or obtain it? \n2. In Sec. 1.3, the authors mentioned some other likelihood estimators, what are the pros and cons of the proposed estimator compared to those existing ones?\n3. How to define the density function $h$ for a given dataset? Is it data-independent?\n4. Proposition 3. The proof doesn't look correct. How was the first inequality obtained? And $\\tilde{f}(\\frac{\\tilde{f}}{\\tilde{g}}-1) = (f+h)\\frac{f-g}{\\tilde{g}}$, so where is the $(f-g)^2$ from? \n5. What's $t$ in Theorem 11?\n6. Are those theoretical results also valid in multivariate cases, such as $X_i$ is multidimensional? If yes, how does the data dimension affect the error rate?\n7. A few practical experiments would be more convincing.\n8. It could be helpful to explain how each theoretical result (e.g. a proposition, lemma, or remark) contributes to the main findings or why such a result is attractive.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: When preparing the camera ready revision, please reorganize the paper as suggested by Reivewer gqi7.
Decision: Accept (poster)