On the Properties of Kullback-Leibler Divergence Between Multivariate Gaussian Distributions
Authors: Yufeng Zhang
Jialu Pan
Kenli Li
Wanwei Liu
Zhenbang Chen
Xinwang Liu
J Wang
Venue: NeurIPS 2023 poster (2023)
Keywords: Kullback-Leibler divergence
statistical divergence
multivariate Gaussian distribution
mathematical optimization
Lambert $W$ function
machine learning
flow-based model
reinforcement learning
TL;DR: We prove the approximate symmetry and relaxed triangle inequality of KL divergence between multivariate Gaussian distributions. We also demonstrate the applications of our theorems.

Abstract: Kullback-Leibler (KL) divergence is one of the most important measures to calculate the difference between probability distributions. In this paper, we theoretically study several properties of KL divergence between multivariate Gaussian distributions. Firstly, for any two $n$-dimensional Gaussian distributions $\mathcal{N}_1$ and $\mathcal{N}_2$, we prove that when $KL(\mathcal{N}_2||\mathcal{N}_1)\leq \varepsilon\ (\varepsilon>0)$ the supremum of $KL(\mathcal{N}_1||\mathcal{N}_2)$ is $(1/2)\left((-W_{0}(-e^{-(1+2\varepsilon)}))^{-1}+\log(-W_{0}(-e^{-(1+2\varepsilon)})) -1 \right)$, where $W_0$ is the principal branch of Lambert $W$ function.	For small $\varepsilon$, the supremum is $\varepsilon + 2\varepsilon^{1.5} + O(\varepsilon^2)$. This quantifies the approximate symmetry of small KL divergence between Gaussian distributions. We further derive the infimum of $KL(\mathcal{N}_1||\mathcal{N}_2)$ when $KL(\mathcal{N}_2||\mathcal{N}_1)\geq M\ (M>0)$. We give the conditions when the supremum and infimum can be attained. Secondly, for any three $n$-dimensional Gaussian distributions $\mathcal{N}_1$, $\mathcal{N}_2$, and $\mathcal{N}_3$, we theoretically show that an upper bound of $KL(\mathcal{N}_1||\mathcal{N}_3)$ is $3\varepsilon_1+3\varepsilon_2+2\sqrt{\varepsilon_1\varepsilon_2}+o(\varepsilon_1)+o(\varepsilon_2)$ when $KL(\mathcal{N}_1||\mathcal{N}_2)\leq \varepsilon_1$ and $KL(\mathcal{N}_2||\mathcal{N}_3)\leq \varepsilon_2$ ($\varepsilon_1,\varepsilon_2\ge 0$). This reveals that KL divergence between Gaussian distributions follows a relaxed triangle inequality. Note that, all these bounds in the theorems presented in this work are independent of the dimension $n$. Finally, we discuss several applications of our theories in deep learning, reinforcement learning, and sample complexity research.

On the Properties of Kullback-Leibler Divergence Between Multivariate Gaussian Distributions
Yufeng Zhang, Jialu Pan Kenli Li
College of Computer Science and Electronic Engineering Hunan University, Changsha, China
tyufengzhang jialupan, 1kljahhu. edu. cn
Wanwei Liu, Zhenbang Chen, Xinwang Liu College of Computer
Key Laboratory of Software Engineering for Complex Systems National University of Defense Technology, Changsha, China {wwliu, zbchen, xinwangliu, wj enuddt eemuut.eduu.cm cn
Ji Wang
College of Computer
State Key Laboratory for High Performance Computing Key laboratory of Software Engineering for Complex Systems National University of Defense Technology, Changsha, China wj wj@nudt.eet edu. cn
Abstract
Kullback-Leibler (KL) divergence is one of the most important measures to cal- culate the difference between probability distributions. In this paper, we theo- retically study several properties of KL divergence between multivariate Gaus- sian distributions. Firstly. for any two n-dimensional Gaussian distributions Ni and N2, we prove that when K KI.(N2llA1) I (8 > 0) the supremum of (L(N)]|N)) is (1/2) (-
(og(-Wo(---1122) -)), where 1), Wo is the principal branch of Lambert W function. For small s, the supremum is & + 2...5 + O(*²). This quantifies the approximate symmetry of small KL divergence between Gaussian distributions. We further derive the infimum of KL(NNllN2) when (L(NeI 2 M (M >). O). We give the conditions when the supremum and infimum can attained. Secondly, for any three n-dimensional Gaussian distributions Nr. N2, and N₁, we theoretically show that upper bound of KL.(N [[N3) is 38 + 382 2 (L((N2IWg)) & 82 (E1, 2 0). This reveals that KI. divergence between Gaussian distributions follows relaxed triangle inequality. Note that, all these bounds the theorems presented in this work are independent of the dimension n. Finally, we discuss several applications of our theories in deep learning, reinforcement learning, and sample complexity research.
+0(82) when K (.(N)]|N)) 81 and
Introduction
statistical divergence measures the "distance" between probability distributions. Let X a space of probability distributions with the same support. A statistical divergence D X x X B$ (R*
JJalu Pan is the corresponding author.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

is the set of non-neen non-negative real numbers) should satisfy (a) non-negativity: D(p.9) 9) 2 0 and (b) identity of indiscemibles: ((p. p) = O, where p. q are probability densities, Another stricter concept. statistical distance, also measures the distance between probability distributions. A statistical distance should satisfy two additional properties, including (e) symmetry: D(p. q) = D(q. p) and (d) triangle inequality: [pp q) & D(p.g) Dgg. 4), where p, 9 and g are probability densities.
Kullback-Leible (KL) divergence, also referred to as relative entropy 33 is applied broadly in many fields, such as machine learning [T0] 23 information theory 15] and statistics E The KL divergence between two continuous probability densities pxx) and (xx) is defined as {L(p())llq(x)) = pxx) log p(x) dx. KL divergence is not a proper distance [3I. First, KL
q(x)
divergence is not symmetrie. It might happen that the forward KL. divergence K (((ll9)) is very small but the reverse KI. divergence K KI." (pllq) = (l((llp) is very large. Second, KI. divergence does not satisfy the triangle inequality. This hinders the application of KL divergence in many contexts.
KL divergence also has connections with other information measures. For example, by taking the second-order Taylor expansion, KL divergence can be approximated with fisher information matrix BI. Therefore, KL divergence is locally approximately symmetric when two distributions are close to each other.
Meanwhile, Gaussian distribution is one of the most important distributions and is central to statistics. also pervasive in many fields. The probability density function of an n-dimensional Gaussian Σ-'(x - -w)). Here μ E R" is the
distribution is ( Σ)- = (22))=//=])1/2)- exp (-(1/2) mean and Σ E S is the covariance matrix, where S is the space of symmetric positive definite n XXM n matrices. Gaussian distribution is the basis for more complicated distributions such as Gaussian Mixture Model [10]. In this paper, we refer to Gaussian distribution as Gaussian for brevity.
n1) -x)
The KL divergence between two n-dimensional Gaussians N1, N22 has the following closed form 45
|ا E1
KI.(N EN) E2)) = log
+ +Tr(E 21) (12 - 11)2-1) T1, (12 - 11)- -1
where the logarithm is taken to base e and Tr is the trace of matrix. Like many other distributions,
KL divergence between Gaussians is neither symmetric nor satisfies the triangle inequality.
In this work, we investigate the following two research problems, which are motivated by our research on diittf-disti detection with flow-based model [57].
1. How to quantify the relation between forward and reverse KL divergences between Gaussian distributions?
2. Does the KL. divergence between Gaussian distributions satisfy some property similar to triangle inequality?
Contributions. The contributions of this work are as follows. Let Ni(p,, E,) & (1,2.3)) be any three n-dimensional Gaussians.
1. We prove that when KL(N))IN2) I E (8 2 0) the supremum of (L(N2||N)) is + log(- woo(-Wol-e- (1+261)) 1), where Wo is the principal branch of Lambert W function. We give the conditions when the supremum can be attained. For small &, the supremum is e 2.. O(s)). This quantifies the approximate symmetry of small KL divergence between Gaussians.
(1/2) (-WW(--ee1+25)))
2. We find the infimum of KL(N1 if KL(NSINN)) 2 M (M > 0). We also give the conditions when the infimum can be attained.
3. We find an upper bound of (L I1Ng) if KL(N) E1 and KL(N)))N) 82 for E1, 62 2 O. For small E and E2, the upper bound is 3εl + 362 + 2 + o( + o(
This indicates that KL divergence between Gaussians follows relaxed triangle inequality.
4. All the bounds in our theorems are independent of the dimension n. This a critical property in contexts where dimensionality has fundamental impact.
5. The theorems proved in this paper can extend the applications of KL divergence in many contexts. We discuss the motivation application in out-of-distribution detection with flow- based model and multiple applications in reinforcement learning and sample complexity research.
We can choose to call (p(l)) or KL(gllp) as forward KL divergence.

---

The rest part of this paper is organized as follows. In Section we prepare lemmas and notations. Section 4 we investigate the supremum (infimum) reverse KL divergence between Gaussians when forward KI. divergence is bounded. In Section 5 we investigate the relaxed triangle inequality KI. divergence between Gaussians. Section applications. Finally, we conclude in Section 7 We put long proofs in Appendix.
2 we discuss related work. In Section 3
6 we discuss
2
Related work
KL divergence has a wide range of applications [15 10 23 45 20
25 3). Researchers have
investigated KL divergence between many distributions, including Markov sources [47]. GMM
models 18 27 multivariate generalized Gaussians [ discrete normal distributions [2]. etc. In
bound of KI. divergence between Gaussians given. far as we know, no related work focuses on the similar properties of KI. divergence between Gaussians as in this paper.
45
KL divergence one member of more general divergences such as Bregman divergence 12
Rényi divergence 48 45 [4], and (f. divvveergee (9]. Bregman divergence defines class of divergences 7 in vector space. KL divergence between multinomial distributions is special form of Bregman divergence when the convex function for Bregman divergence chosen as Σ/= Pi log Pt. where pı define multinomial distribution. Frigyik et. al. [21] extends vector Bregman divergence to functional Bregman divergence in L". Similarly, KL divergence is special form of functional Bregman divergene. (Functional) Bregman divergence also satisfies generalized Pythagoras theorem 21.
53. f-divergence
5 45
The asymmetry of KL divergence has restricted the application of KL divergence in practical applications. Many other divergences have been investigated [46] 16 43 226 17
22
56 55
Pardo gives a comprehensive survey wide range of statistical divergences in his book 45
3 Lemmas and Notations
Table 1: Notations.
f(x)
x logx R++)
W(x)
the Lambert W function
Wo()
the principal branch (branch 0) of W(x) the branch -1 of W(x)
W W_1(x)
(I())
the smaller solution f(x) (1
w2(1)
the larger solution f(x)
f(x....,xx))
Σ f(x)
the eigenvalue of matrix
N(O.
standard Gaussian distribution, dimension n climinated for brevity
We introduce the following Lambert W function before our theoretical results.
Definition 1 Lambert W Function 14). The inverse function of function xee is called Lambert function y (xx).
When x R, W is multivalued function with two branches Wo. W-1, where Wo the principal branch (also called branch 0) and W-1 is the branch -1. Figure A. in Appendix A shows the graph of Wo and W.1.
Lemmas. Function f(x) = x- log (x E R++) (R+ is the set of positive real numbers) lies in the core
of our problems. In Lemma B.I Appendix
B we prove several properties of f(x). We show that
the inverse function of f is (x) ):)====))) W
(x 2 1). Equation f(x) x log 1+ z (t 2 0) [1,+ We
has two solutions w; (f) = - (- - (1+r) E (0, 1] and wz(1) = -W -W-1(---1HH
treat wi (4), (2(1) as functions of 1.
Table I summmrizzes some notations used in this paper. Please see Table A.I list of notations.
Appendix for full

---

Bounds of Forward and Reverse KL Divergence Between Gaussians
In this section, investigate the relation between forward and reverse KL. divergences between Gaussians. These conclusions quantify the approximate symmetry of small KL divergence between Gaussians.
4.1 Supremum of Reverse KL Divergence Between Gaussians
The following Theorem gives the supremum reverse KL divergence when forward KL divergence is bounded by a number
Theorem For any two n-dimensional Gaussian distributions N(m, and N(12, E2), if E,) E2))
0), then
(L( EM) En)) S -Wo(-e-(1-2s1) log -Wo(-e-(142e) -11
The supremum is atlained when the following two conditions hold.
(1) There exists only eigenvalue 2 of (B)')
Bi BT equal to -Wo(-e-(1+Ze) and all other eigenvalues d (i # j) are equal to 1, where B₁ = P,D Pt is an orthogonal matrix whose columns are the eigenvectors of Σt, D1 = diag(d)...... dn) whose diagonal elements are the corresponding eigenvalues, B2 is defined in the similar way as B₁ except on Σz.
(2) 122-
Overview of Proof of Theorem Please see Appendix for the full proof. Here we give the overview of the proof. Theorem can be proved by solving the following optimization problem Pi analytically.
Pi maximize (L( E2) E1) KL(N(M E Σx)) SE
(2)
The proof consists of the following several steps.
1. Invertible linear transformation. We apply a linear transformation to N( Ei) and N(uz, Σn) such that one of them transformed
standard Gaussian. In this way, we can simplify the objective function and the constraint in Pt. Note that diffeomorphism preserves KL divergence inverse linear transformation to transform N (11, I) and N N( Σn) back.
4]] (see Proposition D.I in Appendix D). In the end, we use the
2. Reducing new optimization problem. We reduce P1 to the following core optimization problem Pz.
P2 maximize f( _(..... 1
(4)
X1
Xn
s.t. f(xi...... x,) S n 6
(5)
where xn)) =t) [>)
log (xi E (0,
3. Investigating f(x). f(x) lies in the core of the problem. We have proven several properties fx) in Section 3 A fundamental property fxx (stated in Lemma B.I. is that f(x) is strictly convex and takes its minimum value at x 1. These lemmas allow to conduct further analysis in other parts of this paper.
4. Allocating s'. problem Pz, the supremum of f( J(,...... X is affected by the domain of each dimension, which is in turn determined by how s' allocated to these dimensions. We call (E), ...) where Σ & = e' as an allocation. We prove that f( + takes maximum when e' is allocated to only one dimension (i.e., an "extreme" allocation). In other words, there exists one Ej s and 8; 0 for all # The key is to prove the convexity of function A(e) f( ) f( (E)), where wi(E) -Wo(-e-((tz))
In summary, we use linear transformation to simplify problem P; into standard Gaussian case. Then we deal with the simplified problem in the following Lemma] [ which accomplishes the above steps 2 Theorem can be seen as the generalization of Lemma

---

Lemma 1 Let (O. be n-dimennsonal standard Gaussian distribution, & be a positive number. For any n-dimensional Gaussian distribution (1, )),
(a) (KLAN(,E)))NCC) 1)) S.E. then
1
KL(N(O, (I. E))
loog -Wo( Wo(-e-(1t2e)) -1)
-Wo(-e-(1+2e))
(b) If KIAN(O, (H, 2)) & E, then
(L(N( E)IIN(O.)))
-Wo(-e- - log -Wo( -Wo(-e-(1421))
Proof 1 Please Section
C in the Appendix for details.
To further investigate the bound in Theorem [] we expand the Lambert function using the series
presented in [19 [4] for small &. This result is stated in the following Theorem 2 which can help users to apply our theorem conveniently.
Theorem For any two n-dimensional Gaussian distributions N(4, 21), N(22, E2), and a small positive number &, if KL((( En)l[N Σ2)) S E, then
KL(N( E2) E1)) s 8 + (
Proof 2 Please see Appendix Dfor details.
Theorem 1 holds for any two Gaussians N( Σ1) and N(2,, Σ2). According to the proof of Theorem (Lemma D. one of ((, Σn) and ( Σ2) can be fixed. Thus, it not hard to extend Lemmal to the case where the fixed Gaussian is not standard. We can apply linear transformation the fixed Gaussian (see Equation (D.46) as what we have done in the main proof of Theorem | (see Appendix D). Other parts of the proof are the same. Therefore, we obtain the following corollary.
Corollary Theorem 7 and Theorem 2 hold when one of ((,,E and N(p,, Σn) is fixed.
Remark The supremum in Theorem iis small (zero) when is small (zero). Figure A.2 in Appendix shows the graph of the supremum of KL divergence. Due to the strict conditions, it is hard to reach the supremum rypical applications (e.g. in machine learning). Notably, the bound is independent This is critical in high-dimensional problems (see motivation application in
of the dimension Section 6y. We also note that the condition KL(N( E1)))/( Σ2)) S e Theorem Tis is strict in high -igeesinnsi problems.
Remark 2 Theorem D gives the strict conditions when the supremmum can be attained. We can benefit from these strict conditions in applications. When the forward KL divergence is small, we want a guarantee that the reverse KI. divergence is also small such that bounding forward KL. divergence also bounds the reverse KL. divergence. Theorem / has the following two meanings.
1. The supremum of reverse KL divergence & + 2 + O(2)) is small, implying that the worst case is acceptable.
2. The strict conditions for reaching the supremum imply that the worst case barely happens in practice When these strict conditions not hold, the reverse KL divergence is smaller than the supremum, which is what want in practice.
Toy Examples.
Figure I shows some toy examples one dimensional case. The black line represents stan- dard Gaussian distribution No,0, 1). All other four Gaussian distributions N; (1 s s 4, in colored lines) have the same forward KL divergence K KL(N:]|No) = 0.01. The second distribution has the maximized reverse KL divergence KL(NollNi (0. 0.90173?)) x 0.01148,
which is equal to the supremum 1 (-wor- -Wal-e -Wa(-e--nesooo - log Wol -a220.00 -1). Other reverse
KL divergences KL(NolIN5,0, 1.101112)) 0.00879, (L(06)/N5,0014144... 0.01,
11.1, x 0.00892.
5

---

H 0,001
0.4
1=0.0=1.01661
p=0.14143.0-1
p=0.1.- 1.0755
0.3
0.1
0.0
Figure 1: One dimensional toy examples.
4.2 Infimum of Reverse KL Divergence Between Gaussians
In this subsection, we give the infimum of KL(Na)IN)) when KL(NiIIN 2 M (M > 0). The result presented in Theorem
Theorem 3 For any two n-dimensional Gaussian distributionss N(p1E and N(u2, E2). if
(L.N( E2)) M (M > 0), then
KL(N(P2, (2) 2,)) -W-1(e--142MM)
loog (1+2M1)(1+
The infirum is attained when the following two conditions hold.
(1) There exists only one eigenvalue Aj of Br (B,)) or BT' equal to
-W -W-1(-e-(1-MM) and all other eigenvalues h, (i # j) are equal to 1, where B 1/ P1 orthogonal matrix whose columns the eigenvectors of Σ,, Di diag(d),.....al whose diagonal elements are the corresponding eigenvalues, B2 defined in the similar way Bi except Σz.
(2) 142-
Proof Theorem Aand Theorem 3 form a duality, These theorems can be proved independently
in similar way and also be derived from each other. We give two proofs of Theorem 3 in Appendix
F The first proof presented in Appendix F.1 has the similar structure as that of Theorem except
that Theorem 3 uses W-1. The second proof shown in Appendix E2 derives Theorem 3 from Theorem
7 These two proofs can verify each other.
Relaxed Triangle Inequality
In this section, we give a dimension-free bound of KL [[N] when KL(N)][N5) and KL(Nal|N))
are bounded for any three Gaussians Ni, N2, and Ns. Proving the relaxed triangle inequality is much more difficult. The main result presented Theorem 3 We use two key Lemmas G.5 and to accomplish the key steps of the proof.

---

Theorem 4 For any three n-dimensioonl Gaussians N(u Ei) {1,2,3)) such that
(L(N(HI,Z)))))( E2)) E and ( (2),, Es)) S for E1, 82 2 0,
KL(N(, E)) Es)) 81 + 82 + 2
W W- 1 (1+20z)) + W-I(-e" (14261))
+W +W-1(-e +W-1(-e-(t2es)) +1 -W ---1(---
(22e++
282
Wol - (14282))
Overview of Proof of Theorem
The proof of Theorem 4 is the most technical part of this paper. Please see Appendix for details. Here we give the overview of the proof.
We want solve the following optimization problem P3 analytically.
P3 maximize KL(N(M (E) Σs))
S.L. KLIN E.) (122 Σ2)) s 61
KL(N( En) Σa)) 82
Unfortunately, it is hard to find the supremum due to the complexity caused by Lambert W function. So we relax the constraints to simplify the problem. The proof mainly consists of the following four steps.
1. Invertible linear transformation. The first step is similar to that of Theorem [ We apply linear transformation on NI, N2. and N3 simultaneously such that N2 is converted to standard Gaussian. The transformed problem will be proved Lemma (ammaa((sowy) (shown below). In the end, these three Gaussians are transformed back to general case.
2. Relaxing constraints. In the proof of Lemma we relax the constraints and finally reduce to the following core problem P4.
Σ An 211 - log d1, 2,22,,,1 2,1il
Pa maximize
(6)
s.t. 1 log 11/11 = 1 &1,1 (1 n)
61, 2 A
Σ
81.[i] 281
i=1
A' 2'2,111 log l' 2'2.11
= 82, (Isism)
82 2 A Σ E2,11] 282
where d1.1(] and X2,10 are the eigenvalues of Σ1 and ΣS¹ arranged in decreasing order, respectively. 61,11] and 62,11] are arranged in decreasing order too.
3. Allocating 28, and 282. The value of objective function in P4 is determined by 11, and 22 2ap which are in turn determined by how 28 and 22₂ are allocated to (81,11)--.. .,, (m,(m)) and (82.11)- ... {2][n]), respectively. We prove that an "extreme allocation" can maximize the objective function. In other words, the objective function in Equation (6) takes its maximum when ε1,[1] 28,, [, 282, and &1.[r] &2,[i] for 1 < n. In the proof, we use key Lemma G.3 to deal with the 2-dimensional case (n 2). Finally, extend to arbitrary dimensional cases.
4. Dealing with 2-dimensional case. The proof of Lemma G.3 is the most technical part in this work. In the proof, concentrating ε and is much harder than that in the last section for Theorem I. f(x) x - log x transcendental function whose inverse function is expressed by Lambert W function. This makes even a 2-dimensional case of problem Pa hard to solve. Our proof Lemma is like coordinate descent but much difficult. We show that, for any fixed "non- exon-mxtemme allocation" of 28l (i.e., (#1,11) E1,(2)) where 81,[2] 0), there exists
7

---

a "more extreme" allocation of 20² (d.e,, (62, (212)) where 62,[2] > 0) that maximizes the objective function. Note that is hard state that (22,1))))2122)) is "more extreme" than [E1,[1].&] (11_(2)) because # 82. Then we fix (62,(1))621(2)) and find a "more extreme" (,12)) lift the objective function further. Using these iterations, allocation of 28 ( "1111"
we can construct an infinite sequence of allocations whose limitation is an "extreme" one make the objective function reach its supremum. In Appendix [ we present the key Lemma G.5 and its proof. We also give its proof sketch before the long proof. Essentially, Lemma G.5 plays the most vital role in eliminating the dimension n in case n = 2 from the bound in 2-dimensional case. Finally, we will make the bound in high-dimensional problem dimension-free as well.
(i.e., 81,[1] 28,, (1 282). Then prove the extreme allocation
In summary, we apply linear transformation to simplify the problem. Then solve the simplified problem in the following Lemma 2 accomplishing the above steps 2 Theorem can be seen as the generalization of Lemma 2
Lemma For any two n-dimensional Gaussian distributions ( Σ1) and ( Σ2) such that (L(N()),Z)))IN((0 S E,, KL(N(O, ()LLOOOO)))NNE (11, S E2 (E), 82 2 0),
W- W- (-1 (1+202)) (12( W w-1(-e 1-1(-e-(1-2e))) <8 <
+W (W- (-e + - (--,(( (Vz8i + -Wol -1122r2)
282
Proof 4 Please see Appendix for details.
Remark 3 The bound in Lemma dimension-free and becomes when 81 822
Similarly, we expand Lambert W function by series 19 14 and simplify the bound in Theorem as follows (36]
Theorem For any three n-dimensional Gaussian distributionns N Ei e (1,2,3)) such that (L(N(H,,))))NN Σ2)) 81 and KL(N E2) (x) Es)) S for small 81, 82 0.
KL(N(U) (H3, E3) 381 + 382 2V o (82)
Proof 5 Please Appendix for details.
Finally, in the proof of Theorem we use invertible linear transformation to convert No to standard Gaussian while preserving KL divergence. This proof also applies to the case when N N Σz) is fixed. Therefore, we obtain the following corollary.
Corollary Theorem lndd hold when N(p,, Σn) is fixed.
Remark 4 Our theorem is different from existing generalized Pythagoras inequalities satisfied by KL divergence. Please see Appendix K. for more discussion.
Discussion and Applications
In our theorems, we allow all parameters are unknown or one Gaussian is fixed. Therefore, our theorems are suitable for problems where the parameters can vary. This is common in deep learning where the parameters are learned from data. In this section, we discuss motivation application and other applications ranging from anomaly detection to reinforcement learning to sample complexity research.

---

6.1 Motivation Application: Anomaly Detection with Flow-based Model
The research problems in this paper are motivated by our research on deep anomaly detection using bow-based model [37 Flow-based model assigns higher likelihoods to Out-of- Distriibbbbttio (OOD)
data than In-Distribution (ID) data (i.e., training data) [39 51 13 52 40, 30 For example, Glow
[29] assigns higher likelihoods for SVHN when trained on CIFAR-10 10. Furthermore, we cannot
sample OOD data from the model. Existing explanation is based on the discrepancy of typical set and high probability density regions of model distribution [40]. Such typicality-basee explanation and OOD detection method fail when OOD data has coinciding likelihoods with ID data [40].
We focus on two research problems in this context. (I) why we cannot sample OOD data from flow- based model with prior regardless of when OOD data have higher, lower, or coinciding likelihoods? (2) How to detect OOD data using flow-based model? We investigate these problems from a statistical divergence perspective. Let 2 f(x be the flow-based model mapping data in data space to representation Z in latent space. Suppose the prior distribution pzz is the most commonly used Gaussian distribution. Let X1 px(xx)),x) X2 ~ qx(xx) be the distributions of ID and OOD datasets, respectively. Z1 f(1)) pz)(), Z2 f(x2) qz(z) be the distributions of representations of ID and OOD datasets, respectively. Let P'x be the model induced distribution such that Z, ~ P'z and X, f ~ P'x- Flow-basee model is usually trained by maximum likelihood estimation, which is equal to minimizing forward KI. divergence K (Ixplll [44 23). We conduct generalized Shapiro-Wilt test for multivariate normality on representations. As shown in the original Table C.3 in (57) (also in supplementary material), pz is -aussian-like for all datasets. qz is also Gaussian-like for OOD datasets with higher or coinciding likelihoods except for just one case. These results allow us approximate pz and qz with Gaussians when possible.
The theorems proved in this paper provide solid theoretical guarantee for our analysis and algorithm. On one hand, flow-based model preserves KL divergence (see Proposition D.I in Appendix (D), so (L(p2llD>) which equals (L(pxllp') is minimized. According to the approximate symmetry of small KL divergence (Theorem D. we can know KL(pzzIlpz) is small too. So can assume P'z pz when K (.zllpps'>) is sufficienlly small. On the other hand, we can also assume that the distributions of ID and OOD data are far from each other. This implies that K KLL (I(xxll9xx equaling K (l.(pzlqqz) can be any large. This implies K (l.(p22l922) = K kl((p2lqzz) is large too. Specially, when qz is -aussian-like, we can apply the relaxed triangle inequality (Theorem 4 and infer that KL(pzllqz) must be large. Note that, when qz is not Gaussian-like, we can still apply the theorems presented in this paper to perform analysis on the lower bound of KL divergence (see original Theorem 5 in (57). Overall, the large KL divergence between p5 and qz reveals why we cannot sample OOD data from flow-based model with prior. It is also notable that flow-based model constructs diffeomorphism between data and latent space with thousands of dimensions. Thus, it is critical that the bounds found in this paper are dimension-fit free. Furthermore, we decompose the KL divergence further into group-wis wise KI. divergence and mutual information. Based on these analysis, we propose an unified OOD detection algorithm KLODS both for group (GAD) and point-wise (PAD) anomaly detection. We conduct extensive experiments to compare our method with 13 baseline methods including f-test, KS-test, MMD (24, KSD (35). Annulus Method [13], typicality test [40], the state-of-the-art (SOTA) GAD method GOD2KS 28 input complexity compensated likelihood [50, last-scale likelihood (49, ODIN 3. Joint confidence loss 333, and DoSE (37] Experimental results demonstrate the superiority of our method. For example, as shown in Table 2 our method outperforms the SOTA group-wist wise anomaly detection method GOD2KS on flow-based model by 9.1% AUROC. Our method also outperforms the SOTA point-wiss anomaly detection method DoSE with Glow by 5.2% AUROC. More details of the algorithm and experimental results on both group and point-wise anomaly detection can be refered to [57].
6.2 Applications of Approximate Symmetry of Small KL divergence
Theorem can be also applied widely in deep reinforcement learning and sample complexity research. In many contexts, researchers are hindered by the asymmetry of KL divergence. Theorem I on the approximate symmetry of KI. divergence between Gaussians brings the following convenience to us.
1. Minimizing one of forward and reverse KL divergences also bounds another.
2. We can exchange forward and reverse KL divergences for small g.
We
Meeeala append anonymous version of our work [57 in the supplementary material for convinience.

---

Table 2: Group- anomaly detection Results (AUROC and AUPR in percentage) of method KLODS and the SOTA method GOD2KS on Glow with batch sizes and 10. We run our method for 5 times. Results of GOD2KS are referred from 28
The higher the better.
batch size=
batch size==
0OD
KT.DSS
GODZKS
GODEKS
AUROC
AUPR
AUROC
AUPR
AUROC
AUPR
AUROC
AUPR
MNNSTT
99.820.0
99.820.0
98
98
100.020.0
100,020,0
100
100
FisHioMMNIST
KMNIST
99,9+0.0
99,9=0.0
100
Omniglot
100.0+0.0
100.0+0.0
100
100
100.0+0.0
100.0+0.0
100
100
CelebA
100.0:0.0
100.0:0.00
100
100.0:0.00
100.0=0.0
100
100
CIFAR-10
100.010.0
100.0:00.0
100.0:0.00
100.0:0.0
SVHN
100
100.0:0.0
100.0:0.0
93
86
100.0=0.0
100.0=0.0
99
98
100.0+0.0
100.0+0.0
100.0=0.0
100.0-0.0
100.0
100.0
CelebA
99.210.1
99.410.1
86
100.0:0.0
100.010.0
98
CIFAR 10
SVIIN
97.6++0.2
97.8+0.22
96
99 8+0
99 99.0+
100
100
LSUN
100.0+0.00
100.0+0.0
60
100.0+0.0
100.0+0.0
56
CIFAR-I0
99.6+0..
99.6:0.00
84
73
100.0=0.00
100.0:0.0
94
91
CIFAR-I00
99.810.0
99,810..0
82
100.0:00.0
100.0:0.0
90
CelebA
SVHN
100.0:10.0
100.0::0.0
97
100.0:0.0
100.0:0.0
100
100
LSUN
100.0+0.00
100.0+0.0
85
100.0=0.0
100.0=0.0
96
92
average
99.7
100.0
We summarize the applications Theorem Saarreemmbrieee brieffy in the following. The details of these applications are discussed in Appendix L..
Providing Theoretical Guarantee for Continuous Gaussian Policy in Reinforcement Learning. In [38], Nair er al. propose AWAC method to accelerate online reinforcement learning with offline datasets. They obtain theoretical guarantee in offline reinforcement learning for discrete policies. Theorem can extend their guarantee to continuous Gaussian policy.
Bringing New Insights to Existing Reinforcement Learning Algorithm. In [1. Abdolmaleki er al. propose the MPO algorithm for reinforcement learning. They use Expectation- Maximization (EM) to solve control problems and constraints on KL terms in both E and M-steps. Theorem can eliminate such a difference for continuous Gaussian policies.
Bridging Research on Sample Complexity of Learning Gaussian Distribution. Theorem 1 can bridge existing research on sample complexity of Gaussian distribution. Researchers have proposed algorithms for learning multivariate Gaussian distribution with error bounds in forward and reverse KL divergence separately so far 66 () Theorem can climinate the difference between forward and reverse KL divergence in this scenario.
6.3 Application of Relaxed Triangle Inequality
Extending One-step Safety Guarantee to Multiple Steps in Reinforcement Learning. The relaxed
triangle inequality (Theorem 5 has been applied in safe reinforcement learning. Liu et al. propose an Sispecaation-Maximizatin
style approach for learning safe policy in reinforcement learning [36]. They utilize our relaxed triangle inequality to extend one-step robustness guarantee to multiple steps. In the original Proposition 4 in (36), they simplify the bound in Theorem 4 in case Ej 82. Please see Appendix L.2 for details.
7 Conclusion
In this paper, we research the properties of KL divergence between Gaussians. First, we find the supremum of reverse KL divergence KL if the forward KL divergence (L(N]]|N)) (8 0). This conclusion quantifies the approximate symmetry of small KL divergence between Gaussians. We also find the infimum of (L(N2))N)) if KL(NN)IAg) 2 M (M 0). We give the conditions when the supremum and infimum can be attained. Second, we find bound for KL [[]]) when (L(NNl(AA) and KL(N2llNg)) are bounded. This indicates that KL. divergence between Gaussians follows relaxed triangle inequality. All the bounds in this paper are independent of the dimension of distributions. Finally, we discuss the applications our theorems in deep anomaly detection, reinforcement learning, and sample complexity research.
10

---

Acknowledgments and Disclosure of Funding
This work is supported by the National Natural Science Foundation China (Grant No. 62002107, 62372162, 62032024, 62172429, 61872371, 62202150, 62102442) and National Key Research and Development Program of China (Grant No. 2021ZD40300).
References
[1] Abbas Abdolmaleki, Jost Tobias Springenberg, Yuval Tassa, Rémi Munos, Nicolas Heess, and Martin A. Riedmiller. Maximum posteriori policy optimisation. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018.
[2] Karim T Abou-Mousterr and Frank P Ferrie. A note on metric properties for some divergence measures: The gaussian case. In Asian Conference on Machine Learning, pages 1-15. PMLR, 2012.
[3] Rohit Agrawal, Yi-Hsiu Chen, Thibaut Horel, and Salil Vadhan. Unifying Computational Entropies via Kullback-Leibler Divergence. In Alexandra Boldyreva and Daniele Micciancio, editors, Advances Cryptology- CRYPTO 2019, pages 831-858, Cham, 2019. Springer International Publishing.
[4] Rohit Agrawal and Thibaut Horel. Optimal bounds between f-divergences and integral proba- bility metries. Journal of Machine Learning Research, 22(128): 1-59, 2021.
[5] Syed Mumtaz Ali and Samuel D Silvey. A general class of coefficients of divergence one distribution from another. Journal of the Royal Statistical Society: Series B (Methodological), 2811)113 1966.
[6] Hassan Ashtiani, Shai Ben-David, Nicholas J. A. Harvey, Christopher Liaw, Abbas Mehrabian, and Yaniv Plan. Near-optimal sample complexity bounds for robust learning of gaussian mixtures via compression schemes. J. ACM, 67(6), oct 2020.
[7] Arindam Banerjee, Srujana Merugu, Inderjit S. Dhillon, and Joydeep Ghosh. Clustering with Bregman divergences. Journal of Machine Learning Research, (585):1705-1499 2005.
[8] Arnab Bhattacharyya, Davin Choo, Rishikesh Gajjala, Sutanu Gayen, and Yuhao Wang. Learn- ing sparse fixed-structure gaussian bayesian networks. In Gustau Camps-Vall Francisco J. R. Ruiz, and Isabel Valera, editors, Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pages 9400-9429. PMLR, 28-30 Mar 2022.
[9] Jeremiah Birrell, Paul Dupuis, Markos A. Katsoulakis, Yannis Pantazis, and Luc Rey-Bellet. (f, --vieerge:cee: Interpolating between f-divergences and integral probability metrics. Journal of Machine Learning Research, 23(39):1-70, 2022.
[10] Christopher M. Bishop. Pattern Recognition and Machine Learning (Information Science and Statistics). Brringer-Verlage Berlin, Heidelberg. 2006.
[11] N. Bouhlel and A. Dziri. Kullback- divergence between multivariate generalized gaussian distributions. IEEE Signal Processing Letters, 1617)10211111 2019.
[12] Lev M Bregman. The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming. USSR computational mathematics and mathematical physics, 733):200-217, 1967.
[13] Hyunsun Choi and Eric Jang. WAIC, but why?: Generative ensembles for robust anomaly detection. arXiv preprint arXiv: 1810.0139, 2018.
[14] Robert M Corless, Gaston H Gonnet, David EG Hare, David Jeffrey, and Donald E Knuth. the Lambert W function. Advances in Computational mathematics, 5(1):329-359) 1996.

---

[15] Thomas M Cover and Joy A Thomas. Elements of information theory. John Wiley & Sons, 2012.
[16] Jason V Davis, Brian Kulis, Prateek Jain, Suvrit Sra, and Inderjit S Dhillon. Information- theoretic metrie learning. In Proceedings of the 24th international conference on Machine learning, pages 209-216, 2007.
[17] Philippe Donnat, Gautier Marti, and Philippe Very. Toward generic representation of random variables for machine learning. Pattern Recogn. Lett., 70(C):24-31 January 2016.
[18] J. Durrieu, J. Thiran, and F. Kelly. Lower and upper bounds for approximation of the Luibback-Leibler divergence between gaussian mixture models. In 2012 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 4833-4836, 2012.
[19] Lsj Farmer. The princeton companion applied mathematics. Reference Reviews, 30(5):34-35, 2016.
[20] Sarah Filippi, Olivier Cappé, and Aurélien Garivier. Optimism in reinforcement learning and kullback-leibler divergence. In 2010 48th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 1 115-122, 2010.
[21] Bela A. Frigyik, Santosh Srivastava, and Maya R. Gupta. Functional Bregman divergence. In 2008 IEEE International Symposium on Information Theory, pages 1681-1685, 2008.
[22] Abhik Ghosh and Ayanendranath Basu. A new family of divergences originating from model adequacy tests and application robust statistical inference. IEEE Transactions on Information Theory, (5(8):55815559) 2018.
[23] Ian Goodfellow, Yoshua Bengio, Aaron Courville, and Yoshua Bengio. Deep learning, volume 1. MIT press Cambridge, 2016.
[24] Arthur Gretton, Karsten M. Borgwardt, Malte Rasch, Bernhard Schölkopf, and Alexander Smola. A kernel two-sample test. Journal of Machine Learning Research, 13(25):723-773, 2012.
[25] Peng Guan, Maxim Raginsky, and Rebecca M. Willett. Online Markov decision processes with Kullback-Leibler control cost. IEEE Transactions on Automatic Control, 59(6):1433-1433 2014.
[26] Ishaan Gulrajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron Courville. Improved training of Wasserstein GANs. In Proceedings of the 31 International Conference on Neural Information Processing Systems, NIPS' 17, page 5769 -7799, Red Hook, NY, USA, 2017. Curran Associates Inc.
[27] John R Hershey and Peder Olsen. Approximating the Kullback-Leibler divergence between gaussian mixture models. In 2007 IEEE International Conference Acoustics, Speech and Signal Processing-ICASSPPU
volume 4, pages IV-317. IEEF, 2007.
[28] Dihong Jiang, Sun Sun, and Yaoliang Yu. Revisiting flow generative models for out-of- distribution detection. In International Conference on Learning Representations, 2022.
[29] Durk Kingma and Prafulla Dhariwal. Glow: Generative flow with invertible 1x1 convolutions. In Advances in Neural Information Processing Systems, pages 10215-10224, 2018
[30] Polina Kirichenko, Pavel Izmailov, and Andrew Gordon Wilson. Why normalizing flows fail to detect
data. ICMI. workshop on Invertible Neural Networks and Normalizing Flows, 2020 (NeurIPS 2020), 2020.
[31] Solomon Kullback. Information theory and statistics. Courier Corporation, 1997.
[32] Johann Heinrich Lambert. Observationes variae mathesin puram. Acta Helveticue physico- watheenatioonnnttiii---oooinncno Band III, pages 128-168, 1758.
12

---

[33] Kimin Lee, Honglak Lee, Kibok Lee, and Jinwoo Shin. Training confidence-cally callbrated clas- sifters for detecting out-of-distribution samples. In International Conference on Learning Representations, 2018.
[34] Shiyu Liang, Yixuan Li, and R. Srikant. Enhancing the reliability of out-of-distribution image detection in neural networks. In International Conference on Learning Representations, 2018.
[35] Qiang Liu, Jason D. Lee, and Michael Jordan. A kernelized stein discrepancy for goodness-of-fi tests. In Proceedings of the 33rd International Conference on International Conference on Machine Learning- Volume 48, ICML' 16, page 276-284, JMLR.org, 2016.
[36] Zuxin Liu, Zhepeng Cen, Vladislav Isenbaev, Wei Liu, Steven Wu, Bo Li, and Ding Zhao. Constrained variational policy optimization for safe reinforcement learning. In International Conference Machine Learning, pages 13644-13668. PMLR, 2022.
[37] Warren Momiingsta, Cusuh Ham, Andrew Gallagher, Balaji Lakshminarayanan, Alex Alemi, and Joshua Dillon. Density of States Estimation for Out of Distribution Detection. In Proceed- ings of The 24th International Conference Artificial Intelligence and Statistics, volume 130, pages 3232-3240. PMLR, 2021.
[38] Ashvin Nair, Abhishek Gupta, Murtaza Dalal, and Sergey Levine. AWAC: Accelerating online reinforcement learning with offline datasets. arXiv preprint arXiv:2006. 09359, 2021.
[39] Eric Nalisnick, Akihiro Matsukawa, Yee Whye Teh, Dilan Gorur, and Balaji Lakshminarayanan. Do deep generative models know what they don't know? International Conference on Learning Representations (ICLR), 2019.
[40] Eric Nalisnick, Akihiro Matsukawa, Yee Whye Tch, and Balaji Lakshminarayanan. Detecting out-of-distribution inputs to deep generative models using typicality. 4th workshop on Bayesian Deep Learning (NeurIPS 2019), 2019.
[41] Frank Nielsen. An elementary introduction to information geometry. Entropy, 22(10), 2020.
[42] Frank Nielsen. On the Kullback-L divergence between discrete normal distributions. arXiv preprint arXiv:2109. /4920, 2021.
[43] Sebastian Nowozin, Botond Cseke, and Ryota Tomioka. f-GAN: Training generative neural sam- plers using variational divergence minimization. In D. Lee, M. Sugiyama, U. Luxburg, Guyon, and R. Garnett, editors, Advances Neural Information Processing Systems, volume 29. Curran Associates, Inc., 2016.
[44] George Papamakarios, Eric Nalisnick, Danilo Jimenez Rezende, Shakir Mohamed, and Balaji Lakshminarayanan. Normalizing flows for probabilistic modeling and inference. Journal of Machine Learning Research, 22(57):1-64, 2021.
[45] Leandro Pardo. Statistical inference based on divergence measures. CRC press, 2018
[46] Ziad Rached, Fady Alajaji. and L Lorne Campbell. Rényi's divergence and entropy rates for finite alphabet markov sources. IEEE Transactions Information theory, 47(4):1553-1561, 2001.
[47] Ziad Rached, Fady Alajaji, and L Lome Campbell. The Bellback-Leiblee divergence rate between markov sources. IEEE Transactions on Information Theory, 50(5):917-9))) 921, 2004.
[48] Alfréd Rényi. On measures of entropy and information. In Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Contributions the Theory of Statistics, pages 547-561. University of California Press, 1961.
[49] Robin Tibor Schirrmeister, Yuxuan Zhou, Tonio Ball, and Dan Zhang. Understanding Anomaly Detection with DeepInvertible Networks through Hierarchies of Distributions and Features In Advances in Neural Information Processing Systems 33. Curran Associates, Inc., 2020.
[50] Joan Serrà, David Álvarez, Vicenç Gómez, Olga Slizovskaia, José F. Núñez, and Jordi Luque. Input complexity and oui-s--dist detection with likelihood- generative models, In International Conference on Learning Representations, 2020.
13

---

[51] Alireza Shafaei, Mark Schmidt, and James J Little. Does your model know the digit is not cat? less biased evaluation of" outlier" detectors. arXiv preprint arXiv: 1et9.049999999 2018.
[52] Vit Skvára, Tomáš Pevný, and Václav Smídl. Are generative deep models for novelty detection truly better? KDD Workshop on Outlier Detection De-Constructed (ODD v5.0), 2018.
[53] W. Stummer and Vajda. On Bregman distances and divergences of probability measures. IEEE Transactions on Information Theory, 58(3):1277-12888 mar 2012.
[54] Tim van Erven and Peter Harremos. Rényi divergence and Kullback-Leibler divergence. IEEE Transactions on Information Theory, 60(7):3797-3820, 2014.
[55] Rui F. Vigelis, Luiza H. F. De Andrade, and Charles C. Cavalcante. Properties a generalized divergence related Tsallis generalized divergence. IEEE Transactions Information Theory, -665)22891-2897, 2020.
[56] Pengfei Yang and Biao Chen. Robust Kullback-Leibe divergence and universal hypothesis testing for continuous distributions. IEEE Transactions on Information Theory, 65(4):2360- 2373, 2019.
[57] Yufeng Zhang, Jialu Pan, Wanwei Liu, Zhenbang Chen, Kenli Li, Ji Wang. Zhiming Liu, and Hongmei Wei. Kullback-leibler divergence- based out-o--diitributtin detection with flow-based generative models. IEEE Transactions Knowledge and Data Engineering, pages 1-14, 2023.
14


Reviews:
[{"review_id": "fjZXyvNxvR", "reviewer": "Reviewer_azx2", "summary": "In this paper, the authors prove the following interesting mathematical properties of the Kullback-Leibler (KL) divergence between multivariate Gaussian distributions, while the KL divergence is not a proper distance (in sense that it is not symmetric) and does not satisfy the triangle inequality, but:\n1. if $KL(N_2||N_1) \\leq \\epsilon$ then it can be shown that the supremum of $KL(N_1||N_2) $  can be upper bounded by some explicit function of $\\epsilon$ that is of order $\\epsilon$ for $\\epsilon$ small, so that the KL is approximately symmetric in the Gaussian case when being close; and\n2. an infimum of $KL(N_1||N_2) $ is also derived for $KL(N_2||N_1) \\geq M$; and\n2. for three Gaussian $N_1, N_2, N_3$, one has an upper bound $KL(N_1||N_3) $ that verifies the triangle inequality up to a factor of three, again when the three Gaussians are close.\n\nThe authors discuss the basic proof ideas and some possibly applications in Section 5.\n", "questions": "1. The authors mention that they propose an unified OOD detection algorithm KLODS, but no detail about KLODS is given, it would be great if the authors could elaborate more on this.", "limitations": "This paper is primarily of theoretical nature, and I do not see any potential negative societal impact of this work.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "This paper focuses on the fundamental theoretical properties of Kullback-Leibler divergence between multivariate Gaussian distributions, that, to the best of my knowledge, are novel, and have wide applications in ML.\nI've not checked the detailed proofs, but the proof sketch looks compelling. The proof idea is very interesting and may be of independent interest.\n \n\n", "weaknesses": "The paper is in good shape, I do not have specific concern to raise.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your careful and valuable comments. We explain your concerns as follows.\n\n\nC1: The authors mention that they propose an unified OOD detection algorithm KLODS, but no detail about KLODS is given, it would be great if the authors could elaborate more on this.\n\nA1: We will add more details about the OOD detection algorithm in the revision.\n\nThe OOD detection work motivating the theoretical research in this submission is elaborated in our another manuscript named “Kullback-Leibler Divergence-Based Out-of-Distribution Detection  with Flow-Based Generative Models”. Currently, this manuscript is under review in another journal. We also append the anonymous version in the supplementary material. Please see the appended manuscript for details.\n \nThanks again for your valuable comments."}, {"review_id": "LvUkQDlFQA", "reviewer": "Reviewer_rMwu", "summary": "In this paper, the authors look at the KL divergence between two multivarite Gaussian distributions. The KL divergence is an important distance function between two distributions. However, it lacks certain nice properties that other metric distance functions such as variation distance satisfies: namely, symmetry and triangle inequality. This paper shows that, nevertheless, KL divergence satisfies an approximate version of these two important properties. Specifically, if one of the KL divergences is small then the reverse KL divergence will also be small. Similarly, if two pairs of distributions have small KL divergences between them, then the remaining pair will also have a small KL divergence in between.\n\nThe results are derived by posing this as an optimization problem that minimizes the unknown KL divergences subject to the constraint that the known KL divergences are small. Then certain relevant functions such as  and  are analyzed to derive an upper bound for the above optimization problems.\n\nFinally, the authors argue that such approximate symmetry and approximate triangle inequality appear in several important practical applications. In fact, they mention one such problem involving deep neural networks that led them to study this question.\n\nOne more application of this result is that learning a multivariate Gaussian in either KL gives a similar learning result for the reverse KL. So far algorithms have been derived separately for the two directions, see [arXiv:1710.05209] and [arXiv:2107.10450] for more.\n\nI have not carefully checked the mathematical details.", "questions": "None.", "limitations": "None.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper works on a fundamental mathematical problem of proving that KL divergence between multivariate Gaussians is almost a metric near 0. and gives a nice solution. This paper is very nicely written and a pleasure to read. This is really a beautiful paper.\n\n", "weaknesses": "None.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your careful and valuable comments, especially for suggesting one more application of our theorems. Please see the *common rebuttal for all reviewers* for discussion about this application.\n\nThere is no weakness, question, or limitation contained in the comments. Thanks again for your valuable comments!"}, {"review_id": "wSGz8fsgdh", "reviewer": "Reviewer_odZe", "summary": "This paper investigates the properties of KL divergence between Gaussian distributions. The main theoretical contributions include two main theorems. The first one gives the supremum of reverse KL divergence between Gaussians when the forward KL divergence is bounded. The conditions when the supremum is attained are also identified. The second theorem gives the relaxed triangle inequality of KL divergence between Gaussians. Based on these two main theorems, this paper also derives several corollaries, including the local approximations and a lower bound of reverse KL divergence. It is also notable that the bounds are dimension-free. Finally, this paper discusses several applications of the theoretical results in OOD detection with flow-based generative models and safe/robust reinforcement learning.\n\nOverall, the research questions studied in this paper have not been answered before. The theoretical contributions of this paper are novel and solid. The proofs are carefully written and correct. Notably, the proof of Theorem 4 is rather technical. The theorems presented in this paper can be applied in various contexts involving KL divergence and Gaussian distributions.\n", "questions": "See Weaknesses.", "limitations": "The authors have discussed social impacts and limitations.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.\tThe problems studied in this paper are novel and interesting. This paper answers these research problems for the first time.   \n2.\tThe proofs, which are based on the Lambert W function, are technical.  \n3.\tThe theoretical results can be applied to various problems, including anomaly detection and reinforcement learning. These results also have other potential applications.\n", "weaknesses": "1.\tIt is possible to make some equations tighter by introducing notations earlier. For example, notations in Equations (G.146)-(G.150) can be introduced earlier to make Equations (G.128)-(G.144) more concise. \n2.\tThe derivations in Equation (E.54) and (J.193) are over-detailed. These two equations can be shortened.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your careful and valuable comments. We explain your concerns as follows.\n\nC1: It is possible to make some equations tighter by introducing notations earlier. For example, notations in Equations (G.146)-(G.150) can be introduced earlier to make Equations (G.128)-(G.144) more concise.\n\nA1: We will introduce these notations earlier to make Equations (G.128)-(G.144) more concise in the revision. \nWe have two choices on where to introduce these notations (Equations (G.146)-(G.150)). The first choice is to introduce them earlier. This would make the proof more concise but harder to understand. The second choice is to retain the details of Equations (G.128)-(G.144) and introduce notations (i.e., Equations (G.146)-(G.150)) later. This would make the proof more detailed but a little longer. Note that these two choices do not affect the correctness of the proof.  \n\nC2: The derivations in Equation (E.54) and (J.193) are over-detailed. These two equations can be shortened.\n\nA2: Thanks for this suggestion. In the revision, we will make the derivations in Equation (E.54) and (J.193) more concise.\n\nThanks again for your valuable comments."}, {"review_id": "NyaBLZolK9", "reviewer": "Reviewer_ZfdJ", "summary": "Kullback-Leibler (KL) divergence is an important measure of distance between probability distributions with uses in statistics, information theory and many other fields. However, it is not a proper distance measure, since it is not symmetric and does not satisfy the triangle inequality in general. The authors consider the KL divergence between multivariate Gaussian distributions and show that a relaxed notion of symmetry and triangle inequality holds under certain conditions. Specifically, they formulate an upper bound on KL(N2,N1) when KL(N1,N2) < epsilon, and show that it cannot be much greater than epsilon. Similarly, they give a lower bound on KL(N2,N1) when KL(N1,N2)  > M. Finally, they upper bound KL(N1,N3) when KL(N1,N2) < epsilon1 and KL(N2,N3) < epsilon2. They conclude by discussing several applications of the results in deep learning and reinforcement learning.", "questions": "- Can you please rearrange the structure of the paper to be more in line with convention?\n- Can Lemma G.5 be made more edible, or could a more informative overview be given?\n\n-- The authors have thoroughly addressed these points in the rebuttal.", "limitations": "There is no potential negative societal impact of the work", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The disadvantages of KL divergence as far as symmetry and triangle inequality go are well known, so finding conditions in which even a relaxed version of these properties hold is interesting and potentially useful.", "weaknesses": "Firstly, due to the continuity of the KL divergence around epsilon=0 (N1=N2), the results are not too surprising. The proofs are technical, lengthy and somewhat repetitive. Lemma G.5 in particular is not so digestible for readers. Secondly, the structure of the paper is unorthodox: usually you would have the Related Work section right after the Introduction instead of before Conclusions; that would also be a better place to start mentioning the applications for which your results might be relevant. The section called Lemmas and Notations has no lemmas. The Applications section should be called Discussion.   ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your careful and valuable comments. We explain your concerns as follows.\n\n**C1**: due to the continuity of the KL divergence around epsilon=0, the results are not too surprising.\n\n**A1**: The task of this work is to (1) *quantify* the approximate symmetry and (2) *find* a relaxed triangle inequality. Such issues have hindered researchers for a long time. See the application section and *common rebuttal for all reviewers* for details.\n\n**C2**: Can you please rearrange the structure of the paper to be more in line with convention?\n\n**A2**: We will move the related work section after the Introduction.\n\n**C3**: Can Lemma G.5 be made more edible, or could a more informative overview be given?\n\n**A3**: Proving Lemma G.5 is hard. Appendix G gives a proof sketch. Here we give a more detailed proof sketch.\n\nIn the LHS (resp. RHS) of Inequality G.94, $\\varepsilon_{x,2}$ and $\\varepsilon_{y,2}$ lie in the second (resp. first) term. We will use Inequality G.94 to move $\\varepsilon_{x,2}, \\varepsilon_{y,2}$ to the first item such that $\\varepsilon_{x,1}, \\varepsilon_{x,2}$ and $\\varepsilon_{y,1},\\varepsilon_{y,2}$ are allocated in only one dimension (see Equation H.178).\n\nWe construct function\n$S(\\theta_x, \\theta_y)=f(w_2(\\varepsilon_{x,1}+\\theta_x\\varepsilon_{x,2})w_2(\\varepsilon_{y,1}+\\theta_y\\varepsilon_{y,2}))+f(w_2(\\varepsilon_{x,2}-\\theta_x\\varepsilon_{x,2})w_2(\\varepsilon_{y,2}-\\theta_y\\varepsilon_{y,2}))$ for $-\\frac{\\varepsilon_{x,1}}{\\varepsilon_{x,2}}\\leq \\theta_x\\leq 1,-\\frac{\\varepsilon_{y,1}}{\\varepsilon_{y,2}}\\leq \\theta_y\\leq 1 $ (see Equation G.112). When $\\theta_x=\\theta_y=0$, $S(\\theta_x, \\theta_y)=S(0,0)$ equals the LHS of Inequality G.94.\nRecall that $w_2(0)=1$ and $f(1)=1$. So when $\\theta_x=\\theta_y=1$, $S(\\theta_x, \\theta_y)=S(1,1)$ equals the RHS of Inequality G.94.\nWhen increasing $\\theta_x$ and $\\theta_y$ from 0 to 1, $\\varepsilon_{x,2}, \\varepsilon_{y,2}$ are moved to the first item gradually and\nthe LHS approaches the RHS of Inequality G.94 gradually.\n$\\theta_x$ and $\\theta_y$ control how $\\varepsilon_{x,2}$ and $\\varepsilon_{y,2}$ are allocated among the two terms. \nWe call $(\\theta_x, \\theta_y)$ and the corresponding pairs $(\\varepsilon_{x,1}+\\theta_x\\varepsilon_{x,2},\\ \\varepsilon_{x,2}-\\theta_x\\varepsilon_{x,2})$ and\n$(\\varepsilon_{y,1}+\\theta_y\\varepsilon_{y,2},\\ \\varepsilon_{y,2}-\\theta_y\\varepsilon_{y,2})$ \nindiscriminately as *allocations*. When $\\theta_x=\\theta_y=1$, we call it an *extreme allocation*.\nTo prove Inequality G.94, it suffices to show $S(0,0)\\leq S(1,1)$.\n\nHowever, it is hard to prove $S(0,0)\\leq S(1,1)$ directly due to the complexity brought by Lambert $W$ function. We treat the problem as an optimization problem where $S(\\theta_x, \\theta_y)$ is the objective function.\nWe use an analytical and variation version of coordinate ascent to solve the optimization problem. In the beginning, we start from a well-chosen point (see Equation G.113) arbitrarily close to point $(\\theta_x=0, \\theta_y=0)$. In each iteration, we fix one of $\\theta_x$ and $\\theta_y$ and make another vary. The goal is to maximize the objective function $S(\\theta_x, \\theta_y)$. In this way, we construct an infinite sequence of allocations and reach the supremum finally.\n\nThe proof mainly consists of the following four aspects, which are much harder than a simple coordinate ascent algorithm. \n\n**Aspect 1**: We start optimization from a well-chosen point close to $(\\theta_x=0, \\theta_y=0)$. In each iteration, once we fix one of $\\theta_x$ and $\\theta_y$ and make another one vary, we prove there exists one and only one supremum. For example, once we fix $\\theta_x=\\theta_{x,0}$ where $\\theta_{x,0}>0$ can be artitrarily small, we prove there exists one and only one $-\\frac{\\varepsilon_{y,1}}{\\varepsilon_{y,2}}< \\theta_{y,1}<1$ that maximizes $S(\\theta_{x,0},\\theta_y)$ (see Proposition G.2). In the next step, we fix $\\theta_y=\\theta_{y,1}$ and find $\\theta_{x,2}$ to lift $S(\\theta_x, \\theta_{y,1})$ further. In this way, we find an infinite sequence of allocations $(\\theta_{x,0}, \\theta_{y,0}), (\\theta_{x,0}, \\theta_{y,1}), (\\theta_{x,2}, \\theta_{y,1}), (\\theta_{x,2}, \\theta_{y,3}),\\dots$. \nIn the end, we will show that in these iterations, the allocations corresponding to these local maximums are more and more *extreme*. \n\n**Aspect 2**: However, the condition describing the local maximum (e.g., $\\theta_{y,1}$) is complicated. For example, Equation G.119 describes the condition that $\\theta_{y,1}$ should satisfy. We cannot solve the Equation analytically. So we turn to analyze the condition to study the property of these local maximums.\nWe use a crucial transformation (in Equations G.120~G.124) to obtain key Equations  G.124, G.138, G.142 which express the property of these local maximums (corresponding to allocations) implicitly.\nEquations  G.124, G.138, G.142 also characterize the relation between local maximums obtained in neighboring iterations.\n\n**Aspect 3**: Prove that the constructed sequential allocations in the above iterations are more and more *extreme*. There are two problems we need to tackle. First, how to measure the *extremeness* of one allocation. We find formulae (see Equations G.148 and G.149) to measure one allocation's extremeness indirectly. Second, how to compare the extremeness of two allocations. The Equations G.124, G.138, G.142 used to characterize the property of local maximums obtained in Aspect 2 are also used to prove these sequential allocations are more and more extreme.\n\n**Aspect 4**: Prove the limit of the allocation sequence is $(\\theta_x=1,\\theta_y=1)$ which can maximize the objective function. \n\nHope you enjoy our analysis.\n\n**Q4**:  The section called Lemmas and Notations has no lemmas. The Applications section should be called Discussion.\n\n**A4**: The section ‘Lemmas and Notations’ introduces notations and Lemmas B.1. We will add subcaption to improve consistency. We will add discussion and revise the Application section name.\n\nThanks."}, {"review_id": "fqZ493DGBm", "reviewer": "Reviewer_8dDm", "summary": "This paper explores and proves some properties of KL divergence between multivariate Gaussian distributions. One of the motivations is that as a statistical distance, KL divergence does not satisfy the properties of a metric, that is, symmetry and triangle inequality. In spite of these issues, this paper proposes the relaxed versions. To be specific, it proves the lower bound (resp. upper bound) for reverse KL divergence given the lower bound (resp. upper bound) of forward KL divergence, and the summation upper bound of two bounded KL divergences. Finally, the proposed techniques are applied to anomaly detection with flow based model and reinforcement learning. ", "questions": "The KL divergence is widely used in machine learning and statistics, etc. Can the theoretical results in this paper be used to some other tasks in machine learning?", "limitations": "See Weaknesses. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "(1) This paper proves the lower bound (resp. upper bound) for reverse KL divergence given the lower bound (resp. upper bound) of forward KL divergence, and the summation upper bound of two bounded KL divergences.  \n(2) The theoretical results can be applied to some applications in deep learning and reinforcement learning.  \n(3) This paper is well-written and easy to understand. \n", "weaknesses": "(1) Theorem 1 and Theorem 3 hold when two conditions are satisfied. For example, for the mean, it requires $\\mu_1 = \\mu_2$, which is too strong in practice.  \n(2) Since the KL divergence has a wide range of applications, the two applications shown in this paper are kind of limited and not convincing. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your careful and valuable comments. We explain your concerns as follows.\n\n**C1**: Theorem 1 and Theorem 3 hold when two conditions are satisfied. For example, for the mean, it requires $\\mu_1=\\mu_2$, which is too strong in practice.\n\n**A1**: **These strong conditions are advantages rather than disadvantages when applying our theorems**.\n\nIn Theorem 1 and Theorem 3, we give the strong conditions when the supremum/infimum can be attained. We can benefit from these strong conditions in applications. \n\nAs we discussed in Section 5.2, the approximate symmetry of KL divergence between Gaussians brings the following convenience to us.\n\n(1) Minimizing one of forward and reverse KL divergences also bounds another.\n(2) We can exchange forward and reverse KL divergences for small $\\epsilon$.\n\nFor example, when applying the approximate symmetry of KL divergence between Gaussians (Theorem 1), we know the forward KL divergence is small ($\\leq \\epsilon$). We want to guarantee that the reverse KL divergence is also small such that bounding forward KL divergence also bounds the reverse KL divergence. Theorem 1 states that the supremum of reverse KL divergence is $\\epsilon + 2\\epsilon^{1.5}+O(\\epsilon^2)$, which is a small bound. Since the conditions needed to attain the supremum are strong, it is hard to reach the supremum in practice. This implies that when these strong conditions do not hold, the reverse KL divergence is even smaller than the supremum. That is just what we want in applications. In other words, the supremum describes the *worst case* in application. The stronger these conditions are, the harder to meet the worst case.\n\nTo summarize, Theorem 1 has the following two meanings.\n\n(1) The supremum of reverse KL divergence $\\epsilon + 2\\epsilon^{1.5}+O(\\epsilon^2)$ is small. This tells us the worst case itself in application is acceptable.\n\n(2) The strong conditions tell us the worst case barely happens in practice, so the reverse KL divergence is usually smaller than the supremum. This is just what we want in applications. \n\nTherefore, the strong conditions to attain the supremum are our theorem's advantage rather than disadvantage. We will add more discussion to explain this point in the revision. \n\n**C2**: Since the KL divergence has a wide range of applications, the *two* applications shown in this paper are kind of limited and not convincing. Can the theoretical results in this paper be used to some other tasks in machine learning?\n\n**A2**: **Yes!** We have discussed **four** (not two) applications ranging from deep anomaly detection to reinforcement learning in our paper. In the *common rebuttal for all reviewers*, we summarize four existing applications and discuss one new important application in sample complexity research. Please see the *common rebuttal for details*. These five applications have demonstrated the usefulness of our theory. Our theory may have other potential applications.\n\nThanks again for your valuable comments."}]

Author rebuttal:
Thanks for your valuable comments.

Here we address one concern from Reviewer (8dDm) on the applications of our theory. We think Reviewer (rMwu) may be also interested in this point. So we put the answer in the common rebuttal.

Reviewer (rMwu) proposes no weakness or question. We thank Reviewer rMwu for her/his suggestion of one more important application of Theorem 1 (approximate symmetry of KL divergence between Gaussians) on sample complexity research.
Reviewer (8dDm) proposes one problem as follows. 
“Since the KL divergence has a wide range of applications, the *two* applications shown in this paper are kind of limited and not convincing. Can the theoretical results in this paper be used to some other tasks in machine learning?”

**A**: As pointed out by reviewers, our theory can be applied to various problems ranging from deep learning to reinforcement learning to sample complexity research. 

**Firstly**, we have discussed **four** applications in Section 5 and Appendix L. They are:

(1) *The Motivation Application on OOD Detection Using Flow-Based Model*. Both the approximate symmetry (Theorem 1) and relaxed triangle inequality (Theorem 5) are applied in the motivation application. Please see Section 5.1 and the manuscript (anonymous version) “Kullback-Leibler Divergence-Based Out-of-Distribution Detection with Flow-Based Generative Models” in the supplementary materials. 

(2) *Providing Theoretical Guarantee for Continuous Gaussian policy in AWAC method [arXiv:2006.09359]*. Nair et al. provide a theoretical guarantee for discrete policy distributions. The approximate symmetry (Theorem 1) can extend their guarantee to continuous Gaussian policy. Please see Appendix L.1.

(3) *Bringing New Insights to Existing Reinforcement Learning Algorithm*. In [arXiv:1806.06920, ICLR 2018], Abdolmaleki et al. propose the MPO algorithm for reinforcement learning. They use Expectation-Maximization (EM) to solve control problems and use constraints on KL terms in both E and M-steps. Theorem 1 can eliminate such a difference for continuous Gaussian policies. Please see Appendix L.1.

(4) *Extending One-step Safety Guarantee to Multiple Steps in Reinforcement Learning*. In [arXiv:2201.11927, ICML 2022], Liu et al. propose an Expectation-Maximization style approach for learning safe policy in reinforcement learning. Our relaxed triangle inequality extends their one-step robustness guarantee to multiple steps. Please see Appendix L.2 and [arXiv:2201.11927, ICML 2022] for details.

**Secondly**, as Reviewer (rMwu) pointed out, Theorem 1 (approximate symmetry of KL divergence) has one more important application. Theorem 1 can be used to **extend existing theoretical results in sample complexity research**. In “Ashtiani, et al., Near-optimal Sample Complexity Bounds for Robust Learning of Gaussian Mixtures via Compression Schemes, Journal of the ACM, 2020. arXiv:1710.05209”, the authors propose a compression-based learning method and establish an optimal lower bound of sample complexity for learning Gaussian mixtures. For a fixed target Gaussian mixture distribution $P$, the learning method receives a sample set and outputs a distribution $Q$ satisfying $KL(Q||P)\leq \epsilon$. See page 26, the inequality below Equation (17) in [arXiv:1710.05209, JACM 2020], where KL divergence is used to bound Total Variation distance. Their conclusion applies to a single Gaussian when the number of mixture components is 1. One open problem proposed in their paper is: what is the sample complexity for learning Gaussian mixtures with guarantee using the reverse KL divergence $KL(P||Q)\leq \epsilon$ (see page 35, last paragraph, in [arXiv:1710.05209, JACM 2020]). Our Theorem 1 on the approximate symmetry can extend existing theory and answer this open problem in the single Gaussian case. According to Theorem 1, when $KL(Q||P)\leq \epsilon$, $KL(P||Q) \leq \epsilon+2\epsilon^{1.5}+O(\epsilon^2)$. The supremum equals $O(\epsilon)$ when $\epsilon<1$. This implies that the bounds of forward and reverse KL divergence have the same order. Therefore, the optimal sample complexity for learning single Gaussian is the same when using reverse KL divergence as a guarantee.

Similarly, in “Bhattacharyya et al., Learning Sparse Fixed-Structure Gaussian Bayesian Networks, AISTATS 2022, 
arXiv:2107.10450”, the authors propose a learning method for sparse fixed-structure Gaussian Bayesian network, which can be treated as a representation of multidimensional Gaussian distributions (see Koller's book: Probabilistic graphical models: principles and techniques). They prove the sample complexity of their method for learning Gaussian distribution with guarantee $KL(P||Q)\leq \epsilon$, where $P$ is the target Gaussian distribution from which samples are drawn, $Q$ is the learned Gaussian distribution. Specially, in page 9 of [arXiv:2107.10450, AISTATS 2022], the authors note that their theoretical result uses reverse KL divergence while the JACM paper discussed above uses forward KL divergence. Again, Theorem 1 can extend their conclusion to forward KL divergence and eliminate the difference between forward and reverse KL divergence. 

Just as Reviewer (rMwu) says, "Learning a multivariate Gaussian in either KL gives a similar learning result for the reverse KL. So far algorithms have been derived separately for the two directions". Theorem 1 can eliminate the difference between forward and reverse KL divergence in this scenario. In other words, we answer the open problem proposed in [arXiv:1710.05209, JACM 2020] in single Gaussian case. We can see that the asymmetry of KL divergence between Gaussians has hindered researchers for a long time. Note that Theorem 1 allows us to exchange forward and reverse KL divergence in the derivation on-demand, which would bring more convenience. We plan to explore this direction in the future.

Since KL divergence and Gaussian are widely applied, our theory may have more potential applications.  

Thanks.

Meta-review: The paper studies the properties of the KL divergence between multivariate Gaussian distributions and show various properties such as approximate symmetry in KL divergence, a relaxed triangle inequality. The paper is well written and all reviewers recommend acceptance. I  encourage authors incorporate reviewer comments. I also suggest that they add a few one dimensional toy examples in the paper.
Decision: Accept (poster)