Efficient CDF Approximations for Normalizing Flows
Authors: Chandramouli Shama Sastry
Andreas Lehrmann
Marcus A Brubaker
Alexander Radovic
Venue: Accepted by TMLR ()

Abstract: Normalizing flows model a complex target distribution in terms of a bijective transform operating on a simple base distribution. As such, they enable tractable computation of a number of important statistical quantities, particularly likelihoods and samples. Despite these appealing properties, the computation of more complex inference tasks, such as the cumulative distribution function (CDF) over a complex region (e.g., a polytope) remains challenging. Traditional CDF approximations using Monte-Carlo techniques are unbiased but have unbounded variance and low sample efficiency. Instead, we build upon the diffeomorphic properties of normalizing flows and leverage the divergence theorem to estimate the CDF over a closed region in target space in terms of the flux across its \emph{boundary}, as induced by the normalizing flow. We describe both deterministic and stochastic instances of this estimator: while the deterministic variant iteratively improves the estimate by strategically subdividing the boundary, the stochastic variant provides unbiased estimates. Our experiments on popular flow architectures and UCI benchmark datasets show a marked improvement in sample efficiency as compared to traditional estimators.

Published in Transactions on Machine Learning Research (08/2022)
Efficient CDF Approximations for Normalizing Flows
Chandramouli Sastry
chandrramoul..sslryygmmaaaa
Dalhousie University
Vector Institute
Borealis AT
Andreas M. Lehrmann
andrras.eehrmarrn@@maaal
Borealis AI
Marcus Brubaker
mbrabake@yorkk..om
York University
Vector Institute
Borealis Al
Alexander Radovic
w.rddoic@gmmailcoommmm com
Borealis AI
Reviewed on OpenReview: https: // openreview. net/ ht///forur forum? id= LnjicgggB8
Abstract
Normalizing flows model complex target distribution in terms of bijective transform operating simple base distribution. As such, they enable tractable computation of number of important statistical quantities, particularly likelihoods and samples. Despite these appealing properties, the computation of more complex inference tasks, such as the cumulative distribution function (CDF) over a complex region (c.g., polytope) remains challenging. Traditional CDF approximations using Monte-Carlo techniques are unbiased but have unbounded variance and low sample efficiency. Instead, we build upon the diffeomorphic properties of normalizing flows and leverage the divergence theorem to estimate the CDF over closed region in target space in terms of the flux across its boundary, induced by the normalizing flow. We describe both deterministic and stochastic instances of this estimator: while the deterministic variant iteratively improves the estimate by strategically subdividing the boundary, the stochastic variant provides unbiased estimates. Our experiments on popular flow architectures and UCI benchmark datasets show a marked improvement in sample efficiency as compared to traditional estimators.
1 Introduction
Normalizing Flows Kobyzev et al., 2020 Papamakarios et al., 2021 are a form of generative model which constructs tractable probability distributions through invertible, differentiable transformations,, í.e., diffeomorphisms. They admit both efficient and exact density evaluation and sampling and, valid probability distributions, thcoretically support range of other probabilistic inference tasks. However, some inference tasks remain computationally challenging. Here we consider the task of computing cumulative densities over arbitrary closed regions of distributions represented by normalizing flows. Cumulative densities are a fundamental statistical measure that answer the question: what is the probability of a sample in this range of values? There are number of different extensions of the traditional one-dimensional definition of CDF higher dimensions. Here follow conventions in related works (Botev (2017); which define the CDF in higher dimensions particularly common in the domain of uncertainty estimation (Liu et al.
Cunningham et. al. (2013)
integral over closed region. Example applications
2019
Mazaheri et al.
2020 Abdar
et al. 2021 the evaluation of risk in financial settings (Richardson et al.
1997
Mehta et al.
2012 and

---

Published in Transactions on Machine Learning Research (08/2022)
actuarial analysis in general (Meneguzzo & Vecchiato 2004).
Other recent. examples include distributional reinforcement
learning (Sun et al. 2021), few-shot learning (Ridgeway &
Mozer 2018), and alternative methods for training normalizing
llows
Dai Seljak
2021
Despite the importance of cumulative densities, current tech- niques for computing them with normalizing flows restricted to traditional Monte-Carla based estimators which, while un- biased, can have unbounded variance and poor computational efficiency. Further, such approaches fail to exploit the inherent structure of normalizing flows, namely their construction as a diffeomorphic transformation.
target
normalizing flow
In this paper we describe novel estimator that exploits the unique characteristies of normalizing flows to efficiently estimate the cumulative density in closed regions. To do this we exploit the homeomorphic property of normalizing flow transforms to relate the cumulative density in the target space to volume in the base space. We then adapt the divergence theorem to show that we only need to consider the boundary of the region the target space.
base space
Figure 1: Overview, We propose an efficient
We analyze the resulting thooretical estimator to identify best- case performance scenarios and use this analysis to motivate an adaptive, approximate estimator. To practically realize this estimator and evaluate its performance, we explore its application to the computation of cumulative densities over convex regions.
estimator to compute the cumulative density P induced by a normalizing flow f over a complex region V. We show that P corresponds in- legrating over the boundary dW = g(VV in a uniform base space w.r.t. a vector field F with constant divergence 1, which can be expressed as an integration over the boundary @V the target space w.r.t. an equivalent vector field G.
Contributions.
The contributions of this paper are as follows:
first, we derive a novel formulation the cumulative density a normalizing flow by relating it to the volume a (uniform) base space and the boundary integrals both base and data space based on the divergence theorem. Second, based on these relations, we describe an unbiased, stochastic estimator for cumulative densities over closed region. Next, analyze this estimator to build adaptive, deterministic approximation for cumulative densities over a closed region by strategically adding points along the boundary of the region. Finally, we describe a comprehensive evaluation protocol to evaluate CDF estimators for normalizing flows as a function of region sizes, architecture families, and capacities. The code to reproduce our results, including training popular normalizing flow architectures, approximating cunulative densities with the proposed adaptive boundary estimator, and other bascline methods is publicly available
2 Related Work
Our proposed method is principally related to two bodics of existing work: (1) algorithms for efficient. estimation of cumulative densities for popular distribution functions; and (2) modifications of popular normalizing flows architectures to allow for more efficient cumulative density estimation.
Classic Algorithms. Computing cumulative densitics is not tractable in higher dimensions even for distributions such as the multivariate Gaussian which have closed-form density functions. Consequently, approximations to volume Integrals/cummultive cumulative density functions have been an important research problem: for example, Genz & Bretz (2009) discuss methods for approximating integrals over multivariate Gaussian and t-distributions. [Botev & l'Ecuyer (2015) and Bottvv (2017) propose tilting method for i.i.d. sampling and approximating cumulative densities over convex polytopes in multivariate Gaussian and l-distributions respectively. Approximating integrals over 1D) distributions is also challenging for certain distributions;
https://github. http:://gghubb.cc//brresssss//// http:/hhww....ee/eeeeeaaaaaatooa ott.raaaantttttooodaaaaaarrrnaaa approxinations
2

---

Published in Transactions on Machine Learning Research (08/2022)
see Lange 1999 for discussion on quadrature methods and chapters 4-6 of Press et al. 1988) for
discussion on numerical methods for estimating 1D integrals. Cunningham et al. (2013) extensively study (Minka 2001) as an approximate integration method for computing cumulative densitics over polyhedral or hyperroetangular regions in Gaussian space. In cases where the base space of a normalizing flow Gaussian, one could consider applying this method to the region Gaussian space corresponding the region V in the target space; however, it is not easy to ensure that polyhodral regions target space remain polyhedral in base space without restricting the expressive power of the flow transform.
Normalizing Flows. Cundy & Ermon 2020) consider the general problem of estimating integrals and propose approximate inference procedure that allows explicit control of the bias-variance tradcoff. The method involves first creating partitions of the base uniform space of the normalizing flow and then training a separate variational approximator for each partition. When one partition used for the entire region, the algorithm reduces to the standard variational approximation resulting in a biased low-variance estimate however, for good estimate, the number of partitions have to be increased and the algorithm reduces to Monte-Carlo sampling. Furthermore, it is not. easy to determine the partitioning stralegy to arrive at good estimate with few samples possible. Similar to problem setting, Liang et al. (2020) consider the problem of approximating range densities in a tabular database using auto-regressive models. In order to efficiently marginalize over data dimensions, they train the model by randomly masking some data dimensions, which is referred to as variable-skipping At inference time, they only need to sample the variables whose ranges are specified to form the estimate. Even though the training objective is indeed the mexcimum-lkkelihod objective, the estimate obtained from the model trained with sariable-skippng is only approximate value of the range densities.
Copulas. Introduced in Sklar 1959), copulas are multivariate cumulative density functions which can be used to define multivariate distributions in terms of their univariate marginals. The univariate marginals and the dependence between the variables are defined separately, allowing one to tractably compute multivariate axis-aligned CDFs, For example, Chilinski & Silva (2020) suggest an alternative to normalizing flows based on copula theory wherein CDF estimales are available through a simple forward pass; nonetheless, this approach has some limitations most notably, sampling from the learned distribution is not tractable. In contrast, we focus computing CDFs over flexibly shaped regions with normalizing flows, broad and flexible class of distributions.
3 Background
Before we describe our approach we provide a brief review of normalizing flows and traditional sampling- based methods of estimating their cumulative densities.
3.1 Normalizing Flows
Normalizing flows transform a random variable Y with simple base distribution py into a random variable X with complex target distribution (x( using bijective mapping f f: Rd - Rd. Base and target space are connected by the change-of-variables formula
dg do)
px(x) = (y) abs
(1)
dx
where | the determinant, abs(-) denotes absolute value, 9 is the inverse of f, and dg is the (d x d) Jacobian J of g. We set. Y Y Mo,ja, which has the important property P(y E W) = vol(W) for any compact set W C [0, 1]4, i.e., the cunulative density equals the enclosed volume For pre-existing flows f' with non-uniform (e.g., Gaussian) base distribution (y'),,) we can simply set f = f' (v)) to align them with the case above. Sampling from normalizing flow involves first sampling y and then applying the flow transform f to obtain x = f(y).
dx
We Ug to denote the uniform distribution with support S.
3

---

Published in Transactions on Machine Learning Research (08/2022)
Objective. Given compact set of interest V C Idd in target space, goal will be the efficient computation of
P(xEV) = =/, -xxxxx)) dx.
(2)
3.2
Monte- Estimation
If the volume V admits a tractable membershhp function, one could estimate P(x V) from N random samples from the model as the fraction of points falling into V; we refer to this method as the Monte-Cario (MC) estimate. Similarly, if the volume V admits a uniformly distributed random variable U ~ ll, one could estimate P(x E V) as
Px(x) dx Pu(xx px(x) dx Exxpu (x(x
px(x) (x)
(x)
which we refer to the Imporlance Sumpling (IS) estimate. While both of the described estimators are unbiased, they have unbounded variances for smaller sample sizes and may require several runs to obtain accurate results (Cunningham et al. 2013
4 Efficient Estimation of Cumulative Densities
Equipped with these tools, we will now describe our technique to efficiently compute the cumulative density of Eq. 2. We proceed in three steps: first, we leverage the divergence theorem to relate P(x E V) to a flux mathematically expressed as the surface integral of a given vector field and a measure how much of the vector field passes through a closed surface through the transformed boundary g(VV) of V base space (Section 4.1p. Then, we introduce an equivalent flux through the untransformed boundary 8V of V enable direct integration in target space (Section 4.2). Finally, we propose an iterative protocol that enables fine-grained control over the quality of the approximation (Section 4.3
4.1 Cumulative Density Boundary Flux
We will first show that computing the cumulative density over V in target space is equivalent computing the volume of W g(V) in base space.
Lemma 1. Let V C Rd be compact and W == g(V). Then P(x E vol(W.
Proof. Noting that p(x) = p(y) abs
dg dx
and dy = abs
dg dx
dx, we have
P(xEV) = / p(x) dx= I p(y) abs
dg
dx
dx
(3)
JN p(y) dy S dy vol(W)
We can control the properties of W through f:
Definition 1 (Diffeomorphism). A differentiable bijection f on Rd is called a diffeomorphism, if it has differentiable inverse f-1.
Importantly, diffeomorphisms map points on the boundary to points on the boundary and points in the interior to points in the interior (Armstrong) 2013), implying dw = gQV) ) for any diffeomorphic flow f. This includes popular flow architectures like Glow Kingma Dhariwal (2018), MAF Papamakarios al. (2017), and FFJORD Grathwohl et al. (2019) and ensures that W meets the requirements for the following theorem relating volume integrals surface integrals.
4

---

Published in Transactions on Machine Learning Research (08/2022)
((22)
A = g())
A 1
n1)
A2
P(y W)
P(x V)
1
(0)
A1
W = g(v)
(P3)
base space
target space
g
vol(W)
F
A3
A4
F(x)
FdA
G
9 (P4)
8
8
dA
Figure 2: Estimation in Base Space. A piecewise linear boundary defined by points {pr): in target space has complex shape A in base space. The cumulative density en- closed by is equivalent to boundary flux through A (Bq.5)) As am approximation, we can instead com-- pute the boundary flux of F through the piecewise linear boundary {A:]: defined by (g(p:)); (Eq.6))
Figure 3: Equivalencies. We show equivalent expres- sions for the cumulative density of interest P(x E V) and their associated spaces. The proposed estimator motivated by counter-clockwise chain of arguments, ultimately leveraging Js G dS.
Theorem 1 (Divergence Theorem). Let T C. Idd be compact with piecewise smooth boundary ØT. Given a vector field B, the volume integral of the divergence V B over T and the surface integral of B over öT are related by
/ (V-B)) dT=
B.n d(T))
(4)
Jor
where n is the outward-facing unit normal.
Proof. Wade 2017
Setting A = aw, an application of the divergence theorem using the vector field F(x) x yields V F and thus
vol(W) = dw = / v FW = F. dA,
(5)
d.e., we can compute the volume of W in terms of flux through the boundary of W Now, consider that the closed region V is given by a simplicial polytope and note that simplicial polytope can be constructed with arbitrary accuracy for any closed region of d-dimensional space whose boundary is defined by a c << dddimensional manifold. The boundary of such a polytope is defined by a set of (d-1)-simplices; for example, the boundary a simplicial polytope in 2D is a set of 1-simplices (i.e., line segments). We can approximate the boundary A by flowing the vertices of the (dmiicsim defining the boundary of V through g. Denoting the resulting set of simplices by {A,}i, have
vol(W) ~ F((A)) (n)
(6)
where A; is the i-th simplex, A. (c) its centroid, and A(")) its outward-facing normal. The approximation error is rooted in the assumption that the true boundary patch in A corresponding to transformed simplex A, is linear. The larger the set of simplices approximating the boundary A the better the estimate; Fig, 2 for summary of this section.
4.2 Stochastic Estimation in Target Space
One drawback of the method described in Eq. 0 is that it requires first constructing the set of simplices {At] in base space before we can apply the divergence theorem. In particular, we would need to recompute
We note that unique and other choices possible.
5

---

Published in Transactions on Machine Learning Research (08/2022)
the centroids A;
every time {A,): changes. Preferable is direct integration over the boundary S = ØV in target space using appropriate transformation of F.
(0) and normals A
Lemma 2. Let dA and dS be the area vectors in base space and target space, respectively. Then we have SA F. dA = [g G dS, with = J and J == Vg-
Proof. Consider simplex with vertices p: (i 2.... ..... d) in target space and its corresponding points (p:)) defining simplex AA (Ai) in base space. 9 can be approximated with Taylor expansion
g(x+ = g(x) + Je + ((1)()))
(7)
where J is the (d d) Jacobian the centroid of the simplex (as the transformation 9 preserves imput size). With F (o)) E Rd denoting the field at the centroid, we can write out F AA() as
J [(2 pı) (0( (ps pı) (
F AA 1
(d (d-1)) 1)!
J (pa P1) + 20(1<(13)
See Appendix A for general discussion on computing surface normals. In the limit AA - O, we have Am + dA and ||d||2 + 0:
F P2 p
1
dA
P3 P1
dS
(9)
[d - 1)!
Pa Pl
where G = |J|J D
For notational convenience we assume |J] > 0 so that outward-facing surface normals in base space remain outward-facing larget space; the general case requires st straight/orward tracking of their signs. Interestingly, G has tractable divergence, paving the way for an application of the divergence theorem in target space.
Lemma 3. With G defined as in Lemma 2, we have V.G |
Proof.
V. G v (adi(J)F)
(V (radi))))+
d d='tr(adj(])J) (V. (V-adj(J)) F
(10)
= [V F
[J]
because tr(adi(J)J) = J]... Furthermore,
Evans
2010
shows adj(J) for any C²-map
Lemma 3 allows close the loop and tie the field G back our original objective of computing P(x V). [ and Eq.(1) shows
Indeed, application of Eq.44]
- p(xx)xvV - P(x
[ G. faoss=[(u00 / ujlll
(11)
Fig. shows how the flux learned vector field G across the boundary 8V is related vol(W), which can be expressed the flux of a vector field with V F across the boundary aw -W--btalee obtained by applying a learned transformation g. See Fig. 3 for overview of all equivalencies derived.

---

Published in Transactions on Machine Learning Research (08/2022)
4.2.1 Stochastic Boundary Flux Estimator
For a simplicial polytope with boundary S given by non-overlapping simplices {S:)., we can leverage to define a slochastic boundary flur (BF-S) estimator of the cumulative density P(x E V) using points sampled from the boundary:
/ G G. ...d==/ Σ//, G(x)- s.T)
S dx xx=Es, /
G(x) s. dx =x=xx=x> siai
-s! / (x) G(x)
- ss"") dx
(12)
= - (4) Ex-us [G(x) s/m
where S; is the i-th boundary simplex, s(A) its area, and S its outward-facing unit normal. Alternalively, multiplying and dividing the surface integral Is G ds with the total surface area (E:)
/ G ds = -S Exxills [G(x) n(x),, s
(13)
where n(x) the outward-facing unit normal at x. Note that Us can be decomposed in terms categorical distribution 6; A /, E (A) over the simplices S; and the uniform distributions Us. More specifically, we have Us(x) = E, Us, (x), wherein all but one of the terms are zero for a point x on the surface S because the simplices are non-overlapping and the point x belongs to exactly one of them.
4.3 Adaptive Estimation in Target Space
While the stochastic boundary flux estimator introduced in Section 4.2.1 is unbiased, it does not allow for a strategic placement of evaluation points in an iterative fashion. We can turn Eq. into a sequential process by first approximating Ex-u4s, (G(x) s(") with deterministic estimate and then performing prioritized
iterative refinements.
4.3.1 Deterministic Boundary Flux Estimator
Given a set of boundary simplices {Si),, we can approximate the expected dot-product in (q.(12 by the average dot-product over the vertices of S,. Formally, this adaptive boundory flur (BF-A) estimator of P(x V) is given by
I G
G-dS dS 2e Es! () G(S.). s.M))
(14)
where G(S.) the average G-field over all vertices of S, While Eq. (14 is a biased estimate of the cumulative density P(x E V), its deterministic nature and inherent structure increase sample effi- ciency (e.g., prudent placement, reuseable computations) and enable strategic refinements to arbitrary precision.
4.3.2 Iterative Refinement
The quality of the approximation in Eq.014 14) can be controlled via iterative refinement of the initial set of boundary simplices {S.)-
Figure 4: Splitting Criterion (Total Edge Length). For two simplices (c.g., triangles ABC and ABD) with equal area, the uncertainty about the dot dot-product within simplex grows with point's dis- tance to its closest vertex, motivating the use of total edge length splitting cri- terion.
Each refinement, step consists of a splitting operation that first intro- duces one new vertex at the midpoint of a boundary line segment" and then splits all simplices sharing that edge. The key component of this splitting process a priority queue Q managing the next boundary line segment: I to split, where the longest edge of the simplex with highest priority according a priority function Pr.
4Th (d 1)-simplices (S.): forming the boundary each consist. of (5) line segments.
7

---

Published in Transactions on Machine Learning Research (08/2022)
Pr is designed such that it gives high priority to simplices which probably have high error. As general rule, the larger the simplex the larger the variation in the dot-products, and hence the larger the estimation bias. Although the area S/ of a simplex squarely fits the definition of size, it can be a misleading measure that should not be used in isolation see Fig. 4 for an illustrated explanation. Therefore, total edge length as measure of size. While this approach works well in lower dimensions, we saw marked improvements in terms of sample efficiency in higher dimensions after complementing these two criteria with the standard deviation of the dot-products al the vertices. Taken logether, we define the priority of the i-th simplex S as
also use the
Pr(S.) = - (oa(Si)
Σ 1 e;ES,
(15)
where Ej is the j-th edge (1-simplex) constituting the simplex S,, (a(SS) is the standard deviation of the dot-products computed with the unit surface normal across the simplex S, and is a small number guard against assigning zero priority to large simplices whose dot-products at the vertices are all zero. See Appendix B for summary of the entire splitting process in pseudo code.
4.4 Analysis
4.4.1
Best Case Scenarios
The integral of G over a simplex S, can be computed exactly if the flow transformation g is: (a) linear over the simplex S or (b) G. GS("") is constant for all x E S. The latter is equivalent to F dA being constant, such for hyperspheres. In both cases, we have G(S,) Ex-Uis [G(x)] In practice, it is rarcly possible to realize these best cases, however, if the dol-product is locally-linear over the simplex, our biased estimate is good approximation to the exact integral. For example, observe that the field lines of G vary across the boundary @v in Fig. The true value of Exx-Us, [G()] thus differs from its approximation G(S,) a gap we aim to minimize with the adaptive splitting protocol described above.
4.4.2 Runtime Complexity & Implementation Considerations
For given simplicial polytope, the algorithm first computes the surface normals for each of the boundary simplices, which requires computing d determinants of (d [ 1) x (d (6-11 1) matrices for each boundary simplex. The total complexity of this inilializalion step is thus Okd")), where k is the number of boundary simplices. Note that the surface normals do not need to be recomputed after splitting edges. Furthermore, if regions are defined as a set of half-spaces (i.e., linear inequalities), the surface normals are immediately available and do not require the quartic initialization step. Following this initialization, the manipulation of the priority queue with every split is logarithmic in the number of boundary simplices.
When computing G, one has to first flow the input to the uniform distribution and then compute the Jacobian vector product of the backward-pass; in order to avoid computing the Jacobian-vectan product, we can first compute the vector-Jacobian product T(("T J-1 of the backward-pass followed by a dot-product with F to obtain s(()T |J|s-2F. This avoids an extra backward-pass in PyTfrrch, which does not support moreard-mode auto-differnntiatin of aecobian-vector-pae products. In fact, the derivative of S(")T |J|J-'F with respect to s (( yields exactly G.
5 Experiments
We will now evaluate the proposed adaptive boundary flux (BF-A) estimator against traditional sampling- based estimators like Monte-Carlo (MC) and Importance Sampling (IS). As the accuracies of the CDF estimates of the baseline estimators are mainly a function of sample size (Cunningham et al. 2013 we compare all methods based on sample budgets.
For the purpose of evaluation, we train normalizing flows on d-dimensional (d (2, 4, 5)) data derived from 4 tabular datasets open sourced as part of the UCI Machine Learning Repository (Dua & Graff 2017 and preprocessed as in Papamakarios et al. (2077): Power, Gas, Hepmass, and Miniboone. We construct.
8

---

Published in Transactions on Machine Learning Research (08/2022)
0.22
0.30
0.08
6.08
0.00
0:00
0.04
0.24
0.02
0.09
0.00
3000
202
302
200
200
420
520
:00
200
202
Sumplic Sarglebbulgg.
Semphobuudga
(a) Glow
Kingmaa& & Dhariwal 2018 (b) MAF
Papamakarios et al.
2017 (c) FFJORD Grathwohl et al.
2019
Figure 5: Sample Efficiency. We highlight the sample efficiency of the proposed adaptive boundary flux (BF-A) estimator as compared to Monte-Carlo (MC) and Importance Sampling (TS) estimators. We show absolute estimation errors for 3 flow architectures: two discrete normalizing flows (Glow and MAF) composed of 7 flow-layers with 64 hidden units in their coupling nets and one continuous normalizing flow (FFJORD) parameterized by 2-layer MLP with 64 hidden units in each layer. All models were trained on a 2D slice of the Power datasct, with volumes V given by convex hulls constructed from points sampled on the surface of spheres with radius 1.0, centered at points sampled from the flow.
normalizing flows from the following three architecture families: Glow (Kingma & Dhariwal 2018 Masked Autoregressive Flow (MAF) (Papamakarios et al. 2017), and FFJORD (Grathwohl et al. 2019). For every pair (dataset, d), we obtain random d-dimensional slices of the dataset over which we train the normalizing flows. Additionally, we also consider how the capacities of these models affect the performance: for the two discrete flows (Glow and MAF), we vary the number of hidden dimensions in the coupling networks and the number of flow transforms stacked together; for FFJORD, we instead vary the number of hidden dimensions in each layer of the MLP parameterizing the ODE. For constructing discrete flows, we choose 3, 5 or 7 flow layers and construct coupling layers with 16, 32 or 64 hidden units. While one Glow layer corresponds to a sequence of (ActNorm)- - (Glow Coupling) (Invertible 1 x 1) transformations, one MAF layer corresponds to a sequence of (ActNorm) - (MAF Coupling) transformations. For continuous flows, we parameterize the neural ODE with hidden layers, each consisting of 16, 32 or 64 hidden units. In summary, we obtain a total of 168 flow models for every d (2, 4, 5): each from the 2 discrete flow families and 3 from the continuous flow, trained on 2 slices derived from each of the 4 datasets. We refer to Appendix C for additional training details and box-plots of training log- ligllikeiihoods..
Generating Simplicial Polytopes. The crucial component in ensuring fair and unbiased evaluation of the estimators is in uniformly sampling simplicial polytopes V in target space such that they not biased towards any specific regions or cumulative densities. In order to actually sample simplicial polytope, we construct a convex hull around a fixed number of points in target space. To ensure that convex hulls of varying sizes are equally explored, we sample these points from the boundary of a sphere centered at a flow sample and control the size of the convex hull by controlling the radius of the sphere. We observed that the inclusion of very small convex hulls can lead to inconsistent results across runs due to large relative crrors of the sampling-basee based estimators (MC, IS). Thus we only accepted convex hulls with CDFs larger than 0.01 for fairness and to improve stability and reproducibility between runs. While the number of hull points affects the average size and cumulative density of the enclosed volume, it does not markedly change the average size of the simplices as defined in Section 4.3.2 and we therefore do not consider the number of hull points as an evaluation axis.
In our evaluation we consider 20 points to construct the hull, trading off lower cumulative densities against 5 Furthermore, we consider spheres with radius 0.5, 0.75, and 1.0, amounting to coverage radius of up to standard deviation for our normalized data. Finally, in order
linear approximation of the spherical boundary!"
Note that all points lie on the boundary of the hull and count against. the sample budget of the BF-A algorithm.
9

---

Published in Transactions on Machine Learning Research (08/2022)
Estimator
Absolute Error
Relative Error
IS
0,00572:10. 01585
0.03000-00006322
MC
0.00381+0000380
0.04864+0.05177
BF-S
0.01705+0.04178
0.19032+
BF-A (ours)
0.00152=+0000564
0.01822::0.06622
Table 1: Quantitative Evaluation (Aggregate). We show the absolute and relative errors of each estimator for sample budget of 4,000 points, averaged across all evaluation axes. The proposed BF-A algorithm outperforms the IS and MC estimators in terms of both absolute and relative errors (p < 0.001 in a one-sided U-Test).
to evaluate a normalizing flow model, we construct convex hulls for each choice of the radius. Overall, we evaluate each CDF estimator over total of 10,080 hulls [
Evaluation. For each convex hull we compute a reference cumulative density using 2M importance samples and evaluate all estimators against this gold standard based on their predicted cumulative density using a fixed sample budget K. Unlike our proposed adaptive boundary flux (BF-A) estimator, which is deterministic, the Monte-Carlo (MC) and Importance Sampling (IS) estimators are stochastic. Thus, in order to accurately capture the variance of these estimators, we collect results across 5 runs for each hull. We then evaluate the estimators in terms of both relative and absolute errors. Table ! shows the aggregate results across all 10,080 configurations with a sample budget of 4,000 points. In the remainder of this section, we will unroll these results and analyze our estimator along individual evaluation axes.
Discussion. On average, our BF-A estimator obtains approximately 3.8x and 2.5x lower absolute errors than IS and MC, respectively, for a sample budget of 4,000 points (Table [ likeeise, we obtain 1.7x and 2.7x lower relative errors than IS and MC, respectively. For the specific case of 2D flows, report relative crrors that are better than IS by 11.1x and MC by 21.2x (Table 2al; also see Fig. 5 for a qualitative comparison of the estimators in 2D in terms of the absolute deviation from the true cumulative density. We note that in all 3 cases the proposed algorithm converges to the true estimate well within 500 samples, while the stochastic estimates of the MC and IS estimators exhibit high variance. This pattern is consistent across our experiments with 2D flows and we find that our algorithm outperforms IS and MC by 30x and 55x, respectively, for a sample budget of just 500 points. Conversely, the MC and IS algorithms would require ~50k samples on average lo match the relative errors of BF-A with just 4,000 samples in 2D. Averaged across all flows and dimensions (2D- 5D), we find that the baseline estimators would require 9.6x as many samples to match the relative error rates of BF-A. If we also account for per-sample rumning time (Appendix D Table 5), we find that the baseline estimators can process slightly more samples in the same time that would be needed by BF-A to form an estimate with 4,000 samples. However, they would still require 6.4x more time on average to match the relative error rates of BF-A. Nevertheless, absolute runtime depends on a number of confounding factors such as programming language, dodicated data structures, compute device, and low-level optimizations making fair comparison difficult. We view runtime optimization as an orthogonal research direction that can further capitalize on faster convergence rates and better sample efficiencies of CDF estimators.
A comparison across different hull radii is shown in Table 25 We note that, while the absolute errors of all estimators increase with increasing hull-sizes, the relative crrors of MC decrease with inereasing hull sizes, while those of IS and BF-A increase with increasing hull sizes; nonetheless, BF-A outperforms IS and MC in terms of both absolute and relative errors for the explored hull sizes. Additional quantitative evaluations can be found in the Appendix: in terms of different capacities (Appendix D Tables 4b.. the observed trends are in line with the analysis above, both for discrete and continuous flows. We also note that varying the width of the coupling transform (in discrete flows) does not affect the observed trends as much as the depth of the flow transform. Finally, we observe similar trends across varying flow architectures as well (Appendix D Table 4ah; also see Fig. g in Appendix for a visual summary of all quantitative evaluations.
6 10,080 hulls- 168 models dim
bulls models-radi radii
dim
10

---

Published in Transactions on Machine Learning Research (08/2022)
Dim Estimator
Absolute Error
Relative Error
Radius
Estimator
Absolute Erzor
Relative Errue
0.00737+0.01981 0.00:8240.0043//
0.01 0.00444
18
0.00338+ 000033++0.0100 066
0.01865++0022331
MC
0.03101+0.03366
0.5
MC
0.00336:0000083 00333
0.05670+0.05612
BF-A (ours)
0.00071=0.00281
0.001446:0000300
BF-A (ours)
0.00073:10.0220
0. 0.01016::.041500
0.00528+0001564
0.02543++0.06115
IS
0.00480=+0.1 027
0.02771+00.00661
3
MC
0.00363++0.00381
0.05247+0.05202
0.75
MC
0.00363:+00.003500
0.04896+0.05205
BF-A (ours)
0.001344+0000844
0.00710=+0.03222
BF-A (ours)
0.00126::0.00:100
0.01666:0.004129
IS
0.00808:10.01 998
0.03941=0000871
IS
0.00405:10.008L
0.04495:10.05404
1.0
MC
0.00425++0000425
0.04292++0004661
MC
0.00274++000057
0.06576:00.0612
BF-A (ours)
0.00229:00000728
0.02500:0.064150
BF-A (ours)
0.00237==0000700
0.03:299=00004445
IS
0.00376:10.00410
0.07233:10.08153
(b) Size- wise
MC
0.0024411.002118
0.07340:100064833
BF-A (ours)
0.00380:10.00658
0.07796100.1114/
(a) Dimension-wise
Quantitative Evaluation. We show the absolute and relative errors of each of the methods for a sample budget of 4,000 points, averaged across all configurations separately for (a) each dimensionality and (b) each radius of the hull. BF-A outperforms both IS and MC on average for flows < 5D and the explored hull sizes (p < 0.001 in a one-sided U-Test for each evaluation block).
Table 2:
Our qualitative and quantitative evaluations show a marked improvement of the proposed method over traditional sampling- based estimators. BF-A benefits from our novel formulation of cumulative densities as boundary fluxes as well from the sample efficiency enabled by the priority function Pr. We note that BF-S, the stochastic realization of the boundary flux estimator (Eq. (13) uscs random samples the boundary to form a Monte-Carke estimate of the CDF and accrues higher relative error of 0.19 on average compared to the other Monte-Carte estimators (Table D: nonetheless, its formulation readily extends itself to an adaptive refinement in (d-1) dimensional space, which we use in developing the BF-A estimator. Although the BF-S estimator cannot be directly applied to obtain sample-effccient and accurate CDF estimates, it could form the basis of stochastic-adaplive estimators in the future. Intuitively, the estimation error of the BF-A estimator can be traced back to how much the dot-product G n can change for small changes in the input x; in fact, our motivation behind evaluating the estimators a function of growing dimensions, growing hull-sizes, and growing model capacities is largeted towards testing how well our estimator can adapl to increasing complexity. We observe that while our method continues to outperform the sampling- based estimators with growing hull sizes (Table 2bb, model capacities (Appendix D Table 3 and Table 4b), varying flow architectures (Appendix D Table Aaj, and data dimensions up to and including 4D, BF-A only performs comparably to the sampling-based based estimators for a sample budget of 4,000 points with 5D) flows (Table 2a)).
Limitations & Future Work. A limitation of the proposed estimator is that the structural advantages and improvements over sampling-basee based estimators are likely to be less pronounced in higher dimensions: the CDF over compact region is defined by computationally challenging integration over d-dimensional volume, which inherently scales poorly with dimension. Here we describe how to exploit the diffeomorphic structure of distributions defined by normalizing flows to produce more efficient CDF estimation method and validate our approach on problems between 2D and 5D. While dimeesodimensional CDFs are certainly of interest, our evaluation of equivalent sample sizes shows that even oiw-dineniional CDFs can be computationally demanding. Additional challenges in high-dimensional spaces, such as floating point precision, cannot be ruled out and may require dedicated solutions not covered in this work.
Future extensions of the proposed estimator could consider using higher-order information of the model, such curvature, in defining the priority function in order to improve the scaling of the method; this may also enable the definition of a more natural stopping critcrion than sample budget. Another interesting extension to the adaptive estimator would be to split a batch of edges logether as opposed to splitting a single edge al a time. Additionally, it remains to be explored how different choices of field F could be used in minimizing the estimation error for a given simplicial polytope. Finally, noting that our method works better with FFJORD than MAF and Glow on average (Appendix D Table daj. one could also explore regularization methods that encourage smoother transformations between the target and base spaces.
11

---

Published in Transactions on Machine Learning Research (08/2022)
Conclusion
Cumulative density functions are fundamentally important probability density functions but camnot always be estimated efficiently and exactly. In this work, we propose new type of CDF estimator, derived as an adaptation of the divergence theorem, by exploiting the diffeomorphic properties of normalizing flows. Furthermore, we demonstrate how this CDF estimator can be made more samplo-effiiint by reusing computations and stralegically acquiring new points such that the estimale obtains a precise CDF estimate with few points as possible. In our evaluation of this new adaptive estimator, we find that it outperforms traditional sampling-bane based estimators in terms of sample-efficiencie and accuracies. We believe that proposed efficient CDF estimator will help open up new application arcas with normalizing flows.
Ackuowledgements.
This work was supported by Borealis Al Graduate Fellowship. The authors also thank Vector Institute and Sageev Oore for supporting the project with computational resources.
References
Molond Abdar, Farhad Pourpanah, Sadiq Hussain, Dana Rezazadegan, Ti Liu, Mohammad Ghavamzadeh, Paul W. Fieguth, Xiaochun Cao, Abbas Khosravi, U. Rajendra Acharya, Vladimir Makarenkov, and Saeid Nahavandi. A Review of Uncertainty Quantification in Deep Learning: Techniques, Applications and Challenges. Inf. Pusion, 2021.
Mark Anthony Armstrong. Basic Topology- Springer Science & Business Media, 2013.
7dravko Botev. The Normal Law Under Linear Restrictions: Simulation and Estimation via Minimax Tilting. Journal of the Royal Statistical Society, 2017.
7dravko I Botev and Pierre l'Eeuyer. Efficient Probability Estimation and Simulation of the Truncated Multivariate Student-t Distribution. Winter Simalation Conference (WSC), 2015.
Pawel M. Chilinski and Ricardo Silva. Neural Likelihoods via Cumulative Distribution Functions. UAI, 2020.
Chris Cundy and Stefano Ermon. Flexible Approximate Inference via Stratified Normalizing Flows. UAI, 2020.
John P. Cunningham, Philipp Hennig, and Simon Lacoste-Julien. Gaussian Probabilities and Expectation Propagation. JMLR, 2013.
Biwei Dai and Uros Seljak. Sliced Iterative Normalizing Flows. ICML Workshop on Invertible Newral Networks, Normalizing Flows, and Explicit Likelihood Models, 2021.
Dheeru Dua and Casey Graff. UCI Machine Learning Repository, 2017. URL http::/archiie..ittt uci. edu/ml
Lawrence C Evans. Partial Differential Equations. Craduate Studies Mathematics, 2010.
Alan Genz and Frank Bretz. Computation of Multivariate Normal and T Probabilities. Springer Science & Business Media, 2009.
Will Grathwohl, Ricky T. Q. Chen, Jesse Bettencourt, 1lya Sutskever, and David Duvenaud. FFJORD: Free-Form Continuous Dynamics for Scalable Reversible Generative Models. ICLR, 2019.
Diederik P. Kingma and Prafulla Dhariwal. Glow: Generative Flow with Invertible ixl Convolutions. NewrIPS, 2018.
Tvan Kobyzev, Simon Prince, and Marcus Brubaker. Normalizing Flows: An Introduction and Review of Current. Methods. PAMI, 2020.
Kenneth Lange Quadrature Methods. Numerical Analysis for Statisticians, 1999.
Fric Liang, Zongheng Yang, Ton Stoica, Pieter Abbeel, Yan Duan, and Xi Chen. Variable Skipping for Autoregressive Range Density Estimation. ICML, 2020.
Jeremiah Z. Liu, John W. Paisley Marianthi-AN Ainna Kioumourtzoglou, and Brent A. Coull. Accurate Uncertainly Estimation and Decompasition Ensemble Learning. NeurIPS, 2019.
12

---

Published in Transactions on Machine Learning Research (08/2022)
Bijan Mazaheri, Siddharth Jain, and Jehoshua Bruck. Robust Correction of Sampling Bias using Cumulative Distribution Functions. NewrIPS, 2020.
Amit Mehta, Max Neukirchen, Sonja Pfetsch, and Thomas Poppensieker. Managing Market Risk: Today and Tomorrow, 2012.
Davide Meneguzzo and Walter Vecchiato. Copula Sensitivity Collateralized Debt. Obligations and Basket Defanlt. Swaps. Journal of Futures Markets: Futures, Options, and Other Derivative Products, 2004.
Thomas P. Minka. Expectation Propagation for Approximate Bayesian Inference. VAL, 2001.
George Papamakarios, lain Murray, and Theo Pavlakou. Masked Autoregressive Flow for Density Estimation. NewrIPS, 2017.
George Papamakarios, Eric Nalisnick, Danilo Jimenez Rezende, Shakir Mohamed, and Balaji Lakshminarayanan. Normalizing Flows for Probabilistic Modeling and Inference. JMLR, 2021.
William H Press, Saul A Teukolsky, William Vetterling, and Brian P Flannery. Numerical Recipes in Cambridge University Press, 1988.
Matthew Richardson, Jacob Boudoukh, and Robert F. Whitelaw. The Best of Both Worlds: A Hybrid Approach to Calculating Value at Risk, 1997.
Karl Ridgeway and Michael C. Mozer. Learning Deep Disentangled Embeddings With the F-Statistic Loss. NeurIPS, 2018.
Sklar. Fonctions Répartition Dimensions Leurs Marges. Publications l'Institul Statistique de l'Unéversité de Paris, 1959.
Wei-Fang Sun, Cheng-Kuand Lee, and Chun- Yi Lee, DFAC Framework: Factorizing the Value Function via Quantile Mixture for Multi-Agent Distributional Q-Learning. ICML, 2021.
William Wade. An Introduction to Analysis. Pearson, 2017.
13

---

Published in Transactions on Machine Learning Research (08/2022)
A Computing Surface Normals
applying the divergence theorem, one would need to compute the surface normal vector. In the context of this paper, compute surface normals to the (d 1)-dimensional simplices constituting the boundary: for example, would need to compute the surface normal to iine-segments in 2D, triangles in 3D, tetrahedrons in 4D and so on. By definition of (d dimmensiional simplices, they lie in plane defined by (d- linearly independent vectors; since are computing normals to (d 1)-dimensional simplices lying in IR, the vectors spanning the plane containing the simplex and the normal vector this plane form full basis of R In general, simultaneous equalions in order to determine a vector normal to a given set of veclors. However, in this specific case, since know that we are computing normal vector (d 1) linearly independent vectors, can just define the normal vector to a simplex z defined by the vertex set } in terms of the determinant:
could imagine solving system of
22 21
23
(16)
3d 21
where, is the orthonormal unit basis in R*. Since the determinant of matrix containing two identical evaluates to O, we can easily confirm that the dot product Vi [2, d], v (+4 21) = 0. Also note that at high level, this cross-product operation. In fact, similar vector cross products, the vector norm of
construction resembles the the v is equal to the volume of the parallelotope spanned by the set of (d - 1) linearly independeut vectors {z+ 21 ). Therefore, order derive the surface normal vector whose magnitude equal the volume of the simplex z, we would need to divide v with (d 1)!:
(n)
2g 21
(17)
(d
1
21
Accordingly, for vector w, the dot-product w. (z) be written as:
W
21
(N)
1
23 21
(18)
(d - 1)!
21
14

---

Published in Transactions on Machine Learning Research (08/2022)
B
Pseudo-codes
Algorithm
Split edges and update the volume
Objects and Attributes:
edge:
simplex object in R having the following attributes:
endPoints: the endPoints of the edge
simplices: set 1-dimensional simplices that contains this edge
simplex: d simplex object æ having the following attributes:
edges: the set of edges contained in the simplex
unttSufaceNormall: the unit surface normal of the simplex, adjusted so that points outwards (or inwards) of the hull.
volume: the volume of the simplex
Eellleeetln method that will loop through the points and computes the mean dot-product
Input:
eogeloSplit: The selected edge split according to the priority function described in Eq
edges: Hashmap of Edges
Allows ((1) retrieval of edge objects from the endpoints. If object does not exist in the queue, one created and returned.
volume: The current estimated volume
Output:
Veluml
1: new Volume + volume
b Initialize the newVolume to be equal to the current volume
2:
for simplex in rdge'ToSplit.simpllee do simplex1 + new Simplex()
3:
simplex2 + new Simplex()
5:
simplexx..nittSufaeeeornnall simplex. unttiuresnntSrffaeNNNnnnd
6:
simplex unitSuufacceeeraaall
7:
simplexl.volume +
8:
simplex2.volume + simplex.volumee/
for Edge in caimplex.edgee (odge'ToSplit] do
10:
newEdgel + edges.ee getuessgee((ue (other wew.eerrreeee.oooiiiii endPoint((] edge.midPPoie
newEdge2 edges.getootherF.ieee (otherEdge.edd endeeint(1 edge.midPoint if other
12:
Point (edge (SSplit.endPPonttt then
otherEdge.ade satigeedddddsmmpeeee
14:
simplex1.ese Ledges add(otherEdeee newEdgel newEdge2)
else EtherEdge. haw.nndoinnteeeeeemm PonnteeeeTTTTT (ndooiit))d))))(1()) then
16:
otherEdge..o add add(simplex)
simplex2.edger hawpplls22dggges..ddoooeeeee newEdgel, newe2)
18:
else
19:
other (dgeaaddsiimplex simplex2)
NowE'del.add add(simppex)) simplex2)
21:
new new SowEEde22.dl addisiplexxl simplex2)
22:
simplexLeedge add(otherEdge. newEdgel, Edge)))2)
23:
Simplexx.edges..aie add EdtherEgee, newEdgel, newEdge2)
24:
reherFodge.emoove(simppee..
new Volume Veluml simplex.get VolumeElement(
26:
new + newVolume + simplexl .get Velumeeeeeet) newVolume newVolume sumplex2.geVolumeeeeeeee
28:
return new Volume
15

---

Published in Transactions on Machine Learning Research (08/2022)
Algorithm get VellumeeBleee of Simplex Object
Objects and Attributes:
edge: A 1 simplex object in Ie having the following attributes:
endPoints: the endPoints of the edge
simplices: set of d simplices that contains this edge
simplex: d simplex object in R4 having the following attributes:
edges: the set of edges contained in the simplex
unitSuffaceNormal:: the unit surface normal of the simplex, adjusted so that it points outwards (or inwards) of the hull.
volume: the volume of the simplex
get Eleueett a method that will loop through the points and computes the mean dol-product.
Input:
simplex: simplex object
flow: The normalizing flow
D: Number of dimensions
Output:
volume
volumeFlement
2: for point in simplex.points() do
3: volumeElement + volumebllemen + ooluuee/oo.doo///oottttooii.aae siiple oogomntiinpleemuiittuuaaeeoeeooe
4: return volumeElement
16

---

Published in Transactions on Machine Learning Research (08/2022)
C
Training Details and Log- likelihoods
For all normalizing flows, train the models with batch size of 10k and slop when the log-likelihoods do not improve over epochs. For the continuous flows, we used the exact divergence for computing the log-determinant. We used exp-scaling in the affine coupling layer of both MAF and Glow models and, in order to prevent numerical overflows, we applied a tanh nonlinearity before the exp-scaling. Finally, we used softplus as our activation function for both the Neural ODE and coupling networks. From Fig. and Fig, 7 observe both the Continuous and Discrete flows obtain similar log-iikelihoods and are able to fit the training data well.
(a) 2D
(b) 3D
(c)
(d) 5D
Figure 6: Log-Likelihoods (Discrete Flows).
17

---

Published in Transactions on Machine Learning Research (08/2022)
Log Loptroene
(a) 2D
(b) 3D
(c) 4D
(d) 5D
Figure 7: Log-Liicli (Continuous Flows).
18

---

Published in Transactions on Machine Learning Research (08/2022)
D Extended Results
In this section, we include results that evaluate our algorithm as a function of flow-architectures and their capacities. We also include plots to visually summarize our quantitative results.
Depth
Estimator
Absolute Error
Relative Error
Width Estimator
Absolute Error
Relative Error
IS
0.00449+0.01018 0.00359+0.00033.
0.02683+0.04063
IS MC
0.00552+0.01400
0.03095+0.04500
MC
0.04844+0.05345
0.00368+0000338
0.0485
BF-A (ours)
0.00115:10.004799
0.01719#0.07366
BF-A (ours)
0.00195100000677
0.0229010.00088
IS
0.00562++001335)
0.03167++0.04787
IS
0.00544:20.01577
0.02940=00004310
MC
0.00372110.00336
0.04833110.02216
32
MC
0.00365110.0032.
0.04782.10.05533
BP-A (ours)
0.00142:10.00555
0.0222110.00773
BF-A (ours)
0.00130=+0.00010
0.01944=0.07800
TS
0.00585+0.01499
0.0$113++000583
0.00501++0.01200
0.02932+0.04666
MC
0.00375+0.00342
0.04776+00005166
64
MC
0.008744:00000322 0.04520:00002117
BF-A (ours)
0.00192:+0.00775
0.02470=0.08552
BF-A (ours)
0.00125 1.00155:0000396
0.02184
Table 3: Quantitative Evaluation (Capacity Glow and MAF). We show the absolute and relative errors of
each of the methods with a sample budget of 4,000 points as a function of the depth and width of discrete flows as explained; see that BF-A outperforms both IS and MC.
Flow
Method
Absolute Error
Relative Earor
Width
Estimator
Absolute Error
Relative Error
IS
0.0099510.01133
0.0052410.038188
0.00631=0.02022
0.02975110.08816
Glow
MC
0.00357:0.003222
0.0507240.05421
16
MC
0.00383-0.00472
BF-A (ours)
0.00155::0.0072 00726
0.01963:10.07250
BF-A (ours)
0.00171=00.00004
0.01430=0.0332
0.00667=0.011900
0.03-115::00000022
IS
0.00614-0..1180
LL03005++0004960
MAF
MC
0.00379::0000336
0.01568:10.000002
32
MC
0.00400-0.004200
0.04991++0.05094
BF-A (ours)
0.001-15::00001177
0.02311=00.8501
BF-A (ours)
0.00131=00.00443
0.0103420.02098
IS
0.00640+0.02000
0.09021+0.04500
IS
0.00701=0.021332
0.09080+0004866
FFJORD
0.00-155+0.00155
0.01955:0000003
64
MC
0.00132-00004700
0.04914+10.0012
BF-A [ours)
0.00157#0.00417
0.01199::0.02529
BF-A (ours)
0.00170:10.00391
0.0113210.02083
(a) Flow-Architecturr
(b) Capacity FFJORD
Table 4: Quantitative Evaluation. (a) shows the absolute and relative errors of each of the methods for sample budget of 4,000 points function of the flow-architecture; we that BF-A outperforms both IS and MC. Most interestingly, we find that our method is more efficient with Neural ODEs than with Glow or MAF - our analyses show that this can be attributed the fact that Neural ODEs have much smoother diffeomorphic transformations than Glow and MAF. Perhaps more importantly, the Neural ODEs also oblain similar belter training log- ligllikes than Glow and MAF (Appendix C. (b) contains the absolute and relative errors of each of the methods with a sample budget of 4,000 points function of the number of hidden units of two-layer ML.ss parameterizing FFJORD; we see that. BF-A outperforms both and MC.
1im Method
Time (snc)
IS
0.00616:2000220
0.0061420.001118
BF-A (ours)
0.0096610.00575
3
MC
0.00908:0000771
BF-A (ours)
0.01390=:0.02337
IS
0.0106620002400
MC
8.01183=0.022288
BF-A (ours)
0.01794=0000012
IS
8.01708::0004119
MC
0.01730::0.02851
BF-A (ours)
8.025033::00400/
Table 5: Runtime Evaluation. We show the per-sample running times of all the estimators, averaged across all configurations, separately for each dimensionality. In order to obtain a fair evaluation, we ran all of the timing experiments in single non-preemptible job having access to 8 CPUs, 61GB RAM and Tesla T4 CPU (16GB).
19

---

Published in Transactions on Machine Learning Research (08/2022)
NE bre.
0.15
0.02
15
VVC Nerted
BFA
(a) Aggregate Evaluation of Estimators
0.4
2.5
2.2
Mathed
(b) Evaluation of Estimators with Growing Dimensions
0.32
0.25
0.15
0.15
0.75
1.0
BPAA
16
MK.
BFA
Saskus & Mebhol
(c) Evaluation of Estimators with Growing Hull Sizes.
0.15
0.02
Glox
Glox
Gibw
MAF
MiF
FFIRRO
F30R3
Rlw Mathas
(d) Evaluation of Estimators as function of Flow Architectures.
Figure 8: Visualizations of Quantitative Results.
20


Reviews:
[{"review_id": "iYUmzDEBVy", "reviewer": "Reviewer_RYPp", "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": "**Strenghts.**\n\n- The paper is well motivated and the problem being addressed is relevant.\n\n- The application of the divergence theorem for normalizing flows is not straightforward, yet the paper finds a way to form a practical estimator using it.\n\n- The ideas are nicely presented following a natural ordering.\n\n- The experimental analysis includes a large number of settings.\n\n- The paper promises to release code.\n\n\n**Weaknesses.**\n\n- The estimator BF-S is not included in the experimental analysis of Section 5, leaving the open question of how it performs in practice. If it does not perform well in practice, consider removing it from the paper (or relegating to an Appendix). If it does perform well, it'd be interesting (and useful to the community) to know about it.\n\n- The comparison to previous estimators is based on keeping the sample budget fixed. However, my understanding is that MC and IS are both faster than BF-A given the same sample budge, since BF-A requires additional computations and an iterative refinement procedure. Therefore, I think it would be fairer to compare estimators under the same computation budget, as opposed to sample budget.\n\n- It is unclear why convex hulls with CDF smaller than 0.01 are rejected in the experiments. Could the authors clarify this?\n\n- The experiments consider a low-dimensional setting ($k=2, 5$) (minor side note: why is this a change of notation from $d$ to $k$?). My understanding is that any CDF estimator operating in higher dimensions would inevitably fail due to floating point precision, raising the question of how to obtain a reliable estimator of log CDF. At the very least, a discussion about this point should be included under \"Limitations\", ideally mentioning the maximum dimensionality that the estimator can handle.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "**Note.** This review is being provided by the Action Editor.\n\nThis paper tackles the problem of estimating the CDF of a density described through a normalizing flow. To do so, the paper uses the divergence theorem to turn the integral over a volume into a surface integral. This theorem can be applied on either the untrasformed domain or the transformed domain; the paper argues why it is preferable to focus on the latter. The paper goes on and proposes two methods to approximate the surface integral on the transformed domain: BF-S (a stochastic unbiased approximation) and BF-A (a deterministic but biased approximation). The paper compares BF-A empirically on a number of flows and dataset against two methods: direct Monte Carlo estimator of the CDF and importance sampling, reporting smaller errors for BF-A.\n", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "Overall, the paper is already in good shape, although there is some room for improvement. I would appreciate if the authors could answer and/or discuss on the weaknesses listed above.\n\nBesides that, it can be useful to add some discussion on the following points:\n\n- Although the estimator presents lower error than MC and IS, these results are aggregated over a bunch of scenarios. It can be useful to know in which settings the estimator exhibits worse performance than the baselines, and in which settings the estimator is particularly effective.\n\n- How sensitive are the results to the particular way in which the regions are chosen in the experiments? (i.e., starting from a sample from the model and growing a ball of a fixed radius around it, then form a hull using all samples within that ball). For example, would it be different if we started from a data sample instead?\n\n**Minor comments.**\n\n- I initially got a bit confused by the expression in Eqs. (8) and (9) (and Appendix A overall), as it looks like a determinant over a non-square matrix. It would help to add a comment about the size of each component in the matrix being formed.\n\n- The notation on Section 4 and 5 becomes a bit cumbersome at times, although I don't have good suggestions on how to improve it. As a couple of minor comments, I would suggest introducing the definition of J earlier on (e.g., on Section 3), as well as using only one symbol to denote the divergence (currently the paper uses either $\\nabla \\cdot F$ or $\\text{div}(F)$ interchangeably). That said, the Figures help a lot to keep in mind the notation that has been adopted.\n\n- There are a few typos that need to be fixed. For example, there are a few \\citet that should be \\citep and vice-versa: page 2 (Genz & Bretz), page 3 (Cunningham et al.), page 8 (the tree references in the caption of Fig. 5), page 9 (Dua & Graff).\n\n- There is a missing period (.) after \"Copulas\" in the paragrah in page 3.\n\n- In Fig. 4, it would help to clarify that the two simplices are the triangles ABC and ABD.\n", "broader_impact_concerns": "No concerns.\n", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "ed7276fF0F", "reviewer": "Reviewer_Suvx", "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**:\n- The problem of using diffeomorphic push-forward transformations to estimate quantities like the CDF is a nice step in exploring the utility of such probabilistic models considering their already demonstrated utility in representing conditional/ marginal distributions as well as MCMC augmented sampling from multi-modal distributions.\n- The authors also did a terrific job in establishing how the CDF can be computed by relating it to the volume of the region in the base space and subsequently building the arguments to finally arrive at the chain of equivalences as shown in Fig.3 (which is very good to communicate the whole chain of arguments).\n\n**Weakness**:\nThe major weaknesses of the paper are its writing (which lacks clear introduction of mathematical concepts before delving into the details) and empirical analysis to evaluate the estimator as well as comparison to baselines. I'll detail these below:\n\n- *Empirical Analysis* : \n1) Similar to Monte Carlo methods or IS, I feel the performance of the proposed estimator is dependent on how well the simplex is constructed, specifically the samples $\\boldsymbol{x} \\sim \\mathcal{U}_{S_i}$. I wonder how the scaling here works in higher dimension since the experiments presented are on very low dimensions.  \n2) I also find the Monte Carlo baseline to be a weak baseline considering that in this regime a Quasi Monte Carlo baseline will be more appropriate and stronger. \n3) Also, for comparison with IS and MC estimators, the authors fix a budget of samples used. However, I believe a fair comparison might be of fixing computational time and then evaluating the methods' performance when run for this fixed amount of time. Given the computational cost of constructing & refining the simplices iteratively, I am curious of its effect on run-times. \n4) I also find the experiments presented to be restricted to fairly low dimensions (2-5); however, the main challenge in this space will arise in really high dimensions. I wonder how well the method would scale to high dimensions compared to classical alternatives.\n\n- *Writing*: While, overall, the paper is well written, I believe the exposition needs to be made more accessible. For example, at the beginning of section 4, I really appreciated the authors effort to explain their potential solution in simple words (I wish more ML papers would follow this). However, I felt the effort gor diluted by the fact that the authors used quite a bit of technical jargon (that is also non-standard in ML) that was not introduced or defined before which made it hard to follow e.g. *flux* is not defined. This persists in many areas of the paper where the appropriate terms have not be introduced or defined (even though they might be standard terms in say a Physics based paper) e.g. given the plethora of mathematical terms used, it is not easily clear how Eq. 4 and Eq.5 are related. This is made more difficult by the fact that accompanying terms have not been properly defined leaving it for the reader to figure out the intuition as well as the definitions. As another example, In Lemma 4.2, how should one interpret G? The original problem was stated in terms of V. How should one connect that to the formulation here intuitively?\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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 paper considers the problem of building efficient estimators for CDFs using push-forward transformations, specifically normalizing flows. Towards this end, they formulate the problem of estimating a CDF over a region $\\boldsymbol{V}$ in a target space as estimating the corresponding volume $\\boldsymbol{W}$ in the base space. Subsequently, they take this idea to build adaptive , stochastic and unbiased estimators defining the boundary of the region in the base space more faithfully by iteratively adding points.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "- *Writing* : I believe the paper will benefit from a notations and setup section wherein all the mathematical notations are established and the technical terms used are properly defined beforehand. Furthermore, I think the paper will also benefit from having more layman explanations accompanying useful technical derivations.\n\n- *Empirical Analysis*: I think the empirical analysis needs to strengthen more to be able to demonstrate the utility of the proposed estimator in higher dimensions which is where I'd say the problem is harder for classical alternatives. ", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "SnNtCQHQtT", "reviewer": "Reviewer_Vy3B", "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 paper nicely reframes the statistical estimation problem in terms of the divergence theorem and replaces an integration over a d-dimensional volume with a (d-1)-dimensional integration problem. This could lead to big improvements in performance of the estimator in low dimensional settings, but I am skeptical that it will help much in higher dimensions.\n\nThe exposition throughout is clear, and the main ideas are explained well. That said, the details of the problem could be stated more clearly. \n\nWeaknesses:\n\nThroughout, the paper supposes that a representation of the probability distribution of interest is given via a normalizing flow. In practice, a complex distribution coming from data will never be exactly represented in this way; training will lead to errors on the distribution that will certainly propagate to errors on the CDF. \n\nThe authors propose a stochastic algorithm, but seem only to use the deterministic one. Why is BF-S never evaluated experimentally?\n\nThe experiments go only to $d=5$.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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 manuscript proposes a strategy for computing cumulative distribution functions (CDFs) of complex and potentially high-dimensional probability distributions over complicated regions. The main technical innovation is found in section 4, the development of an estimator that uses samples from the base measure of a normalizing flow and propagates them through the boundary of the region of interest. The authors test their approach numerically and compare to Monte Carlo estimates and importance sampled estimates. ", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "I would say that the most pressing change is that the authors must provide a clearer articulation of how one would construct the representation of the polytope of interest. For a domain with nontrivial geometry, building the set of simplices $S_i$ seems quite complicated. \n\nAnother point the authors must address is the role of training and inaccuracy in the representation of the target distribution due to approximation by a normalizing flow. \n\nI think it is imperative that the authors consider a domain that is not simply an arbitrarily chosen convex region around a point, but rather one that is motivated by some problem of interest. \n\nIt would be nice to see experiments on the BF-S algorithm.\n\n", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Thank you for your submission. The paper proposes a novel way to estimate the CDF of a distribution modeled by a normalizing flow. The main technical contribution is a clever application of the divergence theorem. Although the paper has some limitations, the paper is technically correct and all three reviewers lean towards acceptance. Moreover, the main limitation (lack of scalability with dimensionality) has been properly discussed in the paper. Thus, my final recommendation is "Accept with minor revision".

As for the final version, I expect the authors to include some discussion about the absolute runtime, the approximation errors, and the error intervals in Tables 1 and 2.

Decision: Accept (poster)