summaries: This work provides the novel approach for searching flow architectures. Compared to the standard approaches used to find the best deep architecture in standard network networks this problem is more challenging due to the need of invertible transform and requirement for determinant of the Jacobian to be easy to calculate. To solve the problem the authors propose to apply the weighting for candidate transformations. In order to enforce invertible properties of the model the authors suggest to use the mixing distribution approach instead of mixing the base transformations. They formulate the problem of learning best weights and show that optimal solution for soft weights is not optimal for binarised versions. Therefore they propose to optimize the upper bound of the proposed loss function instead. Further they show how to deal with the problem with larger number of layers. Some experiments are also performed to show the quality of the approach with respect to the baseline that is expert-based selection.  In this paper, the authors proposed to adapt a differentiable architecture search formulation (Liu et al., 2019) based on learned weighting of an ensemble of modules to automated search for Normalizing Flow architectures. The authors made several adaptations to the original approach for the normalizing flow problem, due to the invertibility constraints that prevent direct linear summation of different transform operations. Furthermore, the authors proposed to optimize the full network using an approximated upper bound of the KL divergence, instead of directly optimization. The authors proposed two methods to decompose the optimization problem: grow method, which is more straightforward and greedy, and block method, that alternatively adjusts each block. The authors experimentally compared their proposed method with manually specified architectures across various datasets, including POWER, GAS, HERMASS, MINIBOONE and BSDS300. The results seem mixed, as the searched model outperforms the manual model in some contexts but not others. This paper proposes a DARTS-like method for searching automated normalization flow models. Instead of directly using the output ensembles, which leads to infeasible flow models, this work proposed distribution mixture to guarantee that the supernet is always a valid flow model. The upper bound of the loss function is optimized jointly with resource constraints. Experiments on small-to-medium scale datasets valid the effectiveness of the proposed method. In this paper, the authors present an automated normalizing flow(NF) architecture search method. The method employs a mixture distribution formulation that can construct an optimal flow model with n layers of transformations from the transformation set. Besides, the authors introduce a block-wise optimization method to deal with exponentially growing optimization complexity. In the experiment, the authors proved the effectiveness of the optimization method which via approximate upper bound. And AutoNF has a better performance-cost trade-off than hand-tuned SOTA flow models. 
abstractText: Although various flow models based on different transformations have been proposed, there still lacks a quantitative analysis of performance-cost trade-offs between different flows as well as a systematic way of constructing the best flow architecture. To tackle this challenge, we present an automated normalizing flow (NF) architecture search method. Our method aims to find the optimal sequence of transformation layers from a given set of unique transformations with three folds. First, a mixed distribution is formulated to enable efficient architecture optimization originally on the discrete space without violating the invertibility of the resulting NF architecture. Second, the mixture NF is optimized with an approximate upper bound which has a more preferable global minimum. Third, a block-wise alternating optimization algorithm is proposed to ensure efficient architecture optimization of deep flow models.
references.authors: Jens Behrmann Will Grathwohl Ricky T.Q. Chen David Duvenaud Joern-Henrik Jacobsen
references.title: Invertible residual networks
references.venue: Proceedings of the 36th International Conference on Machine Learning,
references.authors: Laurent Dinh David Krueger Yoshua Bengio
references.title: Nice: Non-linear independent components estimation
references.venue: CoRR, abs/1410.8516,
references.authors: Laurent Dinh Jascha Sohl-Dickstein Samy Bengio
references.title: Density estimation using real NVP
references.venue: In 5th International Conference on Learning Representations,
references.authors: Dheeru Dua Casey Graff
references.title: UCI machine learning repository, 2017
references.venue: URL http://archive. ics.uci.edu/ml
references.authors: Conor Durkan Artur Bekasov Iain Murray George Papamakarios
references.title: Neural spline flows
references.venue: Advances in Neural Information Processing Systems,
references.authors: Will Grathwohl Ricky T.Q. Chen Jesse Bettencourt Ilya Sutskever David Duvenaud
references.title: FFJORD: free-form continuous dynamics for scalable reversible generative models
references.venue: In 7th International Conference on Learning Representations,
references.authors: Chin-Wei Huang David Krueger Alexandre Lacoste Aaron Courville
references.title: Neural autoregressive flows
references.venue: Proceedings of the 35th International Conference on Machine Learning,
references.authors: Kirthevasan Kandasamy Willie Neiswanger Jeff Schneider Barnabas Poczos Eric P Xing
references.title: Neural architecture search with bayesian optimisation and optimal transport
references.venue: Advances in Neural Information Processing Systems,
references.authors: Durk P Kingma Prafulla Dhariwal
references.title: Glow: Generative flow with invertible 1x1 convolutions
references.venue: Advances in Neural Information Processing Systems,
references.authors: Hanxiao Liu Karen Simonyan Oriol Vinyals Chrisantha Fernando Koray Kavukcuoglu
references.title: Hierarchical representations for efficient architecture search
references.venue: In International Conference on Learning Representations,
references.authors: Hanxiao Liu Karen Simonyan Yiming Yang
references.title: DARTS: Differentiable architecture search
references.venue: In International Conference on Learning Representations,
references.authors: D. Martin C. Fowlkes D. Tal J. Malik
references.title: A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics
references.venue: In Proceedings Eighth IEEE International Conference on Computer Vision. ICCV 2001,
references.authors: Bogdan Mazoure Thang Doan Audrey Durand Joelle Pineau R Devon Hjelm
references.title: Leveraging exploration in off-policy algorithms via normalizing flows
references.venue: Proceedings of the Conference on Robot Learning,
references.authors: Muhammad Ferjad Naeem Seong Joon Oh Youngjung Uh Yunjey Choi Jaejun Yoo
references.title: Reliable fidelity and diversity metrics for generative models
references.authors: Renato Negrinho Geoff Gordon
references.title: Deeparchitect: Automatically designing and training deep architectures, 2017
references.authors: Junier Oliva Avinava Dubey Manzil Zaheer Barnabas Poczos Ruslan Salakhutdinov Eric Xing Jeff Schneider
references.title: Transformation autoregressive networks
references.venue: Proceedings of the 35th International Conference on Machine Learning,
references.authors: George Papamakarios Theo Pavlakou Iain Murray
references.title: Masked autoregressive flow for density estimation
references.venue: Advances in Neural Information Processing Systems,
references.authors: George Papamakarios Eric Nalisnick Danilo Jimenez Rezende Shakir Mohamed Balaji Lakshminarayanan
references.title: Normalizing flows for probabilistic modeling and inference, 2021
references.authors: Esteban Real Sherry Moore Andrew Selle Saurabh Saxena Yutaka Leon Suematsu Jie Tan Quoc Le Alex Kurakin
references.title: Large-scale evolution of image classifiers, 2017
references.authors: Danilo Rezende Shakir Mohamed
references.title: Variational inference with normalizing flows
references.venue: In Francis Bach and David Blei (eds.), Proceedings of the 32nd International Conference on Machine Learning,
references.authors: Oren Rippel Ryan Prescott Adams
references.title: High-dimensional probability estimation with deep density
references.authors: Masanori Suganuma Mete Ozay Takayuki Okatani
references.title: Exploiting the potential of standard convolutional autoencoders for image restoration by evolutionary search, 2018
references.authors: E.G. Tabak Cristina V. Turner
references.title: A family of nonparametric density estimation algorithms
references.venue: Communications on Pure and Applied Mathematics,
references.authors: Barret Zoph Quoc V. Le
references.title: Neural architecture search with reinforcement learning
references.venue: In 5th International Conference on Learning Representations,
sections.text: Although various flow models based on different transformations have been proposed, there still lacks a quantitative analysis of performance-cost trade-offs between different flows as well as a systematic way of constructing the best flow architecture. To tackle this challenge, we present an automated normalizing flow (NF) architecture search method. Our method aims to find the optimal sequence of transformation layers from a given set of unique transformations with three folds. First, a mixed distribution is formulated to enable efficient architecture optimization originally on the discrete space without violating the invertibility of the resulting NF architecture. Second, the mixture NF is optimized with an approximate upper bound which has a more preferable global minimum. Third, a block-wise alternating optimization algorithm is proposed to ensure efficient architecture optimization of deep flow models.
sections.heading: 1 INTRODUCTION
sections.text: Normalizing flow (NF) is a probabilistic modeling tool that has been widely used in density estimation, generative models, and random sampling. Various flow models have been proposed in recent years to improve their expressive power. Discrete flow models are either built based on elementalwise monotonical functions, named autoregressive flow or coupling layers (Papamakarios et al., 2017), or built with transformations where the determinant of the flow can be easily calculated with matrix determinant lemma (Rezende & Mohamed, 2015). In the continuous flow family, the models are constructed by neural ODE (Grathwohl et al., 2019).
  Despite the variety of flow models, there’s yet no perfect flow concerning the expressive power and the computation cost. The flow models with higher expressive power usually have higher computational costs in either forward and inverse pass. In contrast, flows which are fast to compute are not able to model rich distributions and are limited to simple applications. For instance, autoregressive flows (Papamakarios et al., 2017) are universal probability approximators but are D times slower to invert than forward calculation, where D is the dimension of the modeled random variable x (Papamakarios et al., 2021). Flows based on coupling layers (Dinh et al., 2015; 2017; Kingma & Dhariwal, 2018) have an analytic one-pass inverse but are less expressive than their autoregressive counterparts. Other highly expressive NF models (Rezende & Mohamed, 2015; Behrmann et al., 2019) cannot provide an analytic inverses and relies on numerical optimizations.
  For different applications, the optimal flow model can be drastically different, especially if the computation cost is taken into consideration. For generative models (Dinh et al., 2015; Kingma & Dhariwal, 2018), flows with the fast forward pass are preferable since the forward transformations need to be applied to every sample from the base distribution. For density estimation (Papamakarios et al., 2017; Rippel & Adams, 2013), flows with cheap inverse will prevail. For applications where flow is utilized as a co-trained kernel (Mazoure et al., 2020), the computation cost and performance trade-off are more important, i.e., having a fast model with relatively good performance. However, in the current body of work, the architecture designs of the flow models are all based on manual configuration and tuning. To this date, there is a lack of a systematic way that could automatically construct an optimal flow architecture with a preferred cost.
  In this paper, we propose AutoNF, an automated method for normalizing flow architecture optimization. AutoNF has a better performance-cost trade-off than hand-tuned SOTA flow models based on a given set of transformations. Our approach employs a mixture distribution formulation that can search a large design space of different transformations while still satisfying the invertibility requirement of normalizing flow. The proposed mixture NF is optimized via approximate upper bound which provides a better optimization landscape for finding the desired flow architecture. Besides, to deal with exponentially growing optimization complexity, we introduce a block-wise optimization method to enable efficient optimization of deep flow models.
sections.heading: 2 RELATED WORK
sections.text: Normalizing Flows: Various normalizing flow models have been proposed since the first concept in (Tabak & Turner, 2013). Current flow models can be classified into two categories: finite flows based on layer structure, and continuous flow based on neural ODE (Grathwohl et al., 2019). The finite flow family includes flows based on elemental-wise transformation (Papamakarios et al., 2017; Kingma & Dhariwal, 2018) and flows whose transformations are restricted to be contractive (Behrmann et al., 2019). In elemental-wise transformation flows, autoregressive flow and coupling layers are two major flavors and extensive work has been proposed to improve the expressive power of both flow models. In Huang et al. (2018), the dimension-wise scalar transformation is implemented by a sigmoid neural network, which increases the expressive power at the cost of being not analytically invertible. In Durkan et al. (2019), piecewise splines are used as drop-in replacement of affine or additive transformations (Dinh et al., 2015; 2017) and is the current SOTA flow model. Consequently many recent research efforts have been devoted to closing the gap of expressive power, albeit at the cost of more complex and expensive transformations. Moreover, there has been no quantitative trade-off analysis between the performance and cost among different flows.
  Neural Architecture Search: Many algorithms have been proposed or applied for neural architecture search. For instance, reinforcement learning (Zoph & Le, 2017), genetic algorithm (Real et al., 2017; Suganuma et al., 2018; Liu et al., 2018), Monte Carlo tree search (Negrinho & Gordon, 2017) or Bayesian optimization (Kandasamy et al., 2018). However, these methods all face the challenge of optimizing on a large discrete space and can take thousand of GPU days to find a good architecture. To address this issue, DARTS (Liu et al., 2019) proposes to relax the search space from discrete to continuous and allows efficient differentiable architecture search with gradient method which could reduce the search time to a single GPU day while still producing the SOTA architecture. However, all current NAS methods focus on optimizing traditional neural network structures (CNN, RNN) and there has yet been any implementation on normalizing flow.
  Necessity for the Trade-off Between Performance and Cost: Despite various transformations proposed in the literature, there is no perfect transformation with strong expressive power and low computational cost. Autoregressive flows have better expressive power, but the inverse computation cost grows linearly with data dimension. Coupling layers’ inverse calculation is as fast as the forward pass, but their expressive power is generally worse than autoregressive flow with the same element-wise transformation. Even in the same autoregressive flow or coupling layer family, flows with different element-wise transformations have different performance and computation costs. For instance, additive or affine coupling layers (Dinh et al., 2017; 2015) have very fast forward and inverse calculation with limited expressive power while the flow in (Durkan et al., 2019) are highly expressive but are more demanding on computation. In most applications, it is necessary to find the best performance while minimizing at least one specific component of the cost. Unfortunately, the current design of flow models is empirical and therefore cannot ensure the optimal trade-offs.
sections.heading: 3 METHOD
sections.text: In this work, we aim to tackle the challenge of finding an optimal flow model for a given task via an automated architecture search algorithm.
  Assumptions: In the remaining part of this paper, without losing generality, we assume that the transformation is properly modeled such that during the training process, only forward computation is needed. Under this assumption, when the flow model is used for density modeling (Durkan
  et al., 2019), the forward calculation is the dominant computation. When the flow model is used for random sampling (Kingma & Dhariwal, 2018), the inverse calculation is computationally intensive. When the flow model is utilized as a module and trained together with other components, e.g., policy network in maximum entropy learning (Mazoure et al., 2020), the training cost of the flow model is an important consideration.
  Problem Definition: Given a transformation set with m options {T 1, T 2, ...Tm}, the goal is to construct an optimal flow model with n layers of transformations from the set. The flow model pNF (x;θ) = pT1T2...Tn(x;θ) should minimize the KL divergence between the target distribution p∗(x) and itself while minimizing its computational cost CNF . Here, θ are the parameters of the transformation in the flow model. In this paper, we use the forward KL divergence as our target loss function (Papamakarios et al., 2021):
  θ∗ =argmin θ {DKL[p∗(x) || pT1T2...Tn(x;θ)] + λ · CNF }
  s.t. Ti ∈ {T 1, T 2, ...Tm} (1)
  While λ is a tuning factor capturing the relative importance of the performance-cost trade-off. Finding this optimal flow model is a discrete optimization problem with exponential complexity. To enable efficient architecture optimization, we use proposed method of relaxing the discrete search space to continuous space as suggested in Liu et al. (2019).
sections.heading: 3.1 MIXED FLOW ENSEMBLE
sections.text: For the ith transformation layer with m options, we introduce a corresponding weight w j i for each option T j which reflects how likely the transformation will be selected. The weight is parameterized by a vector α and made continuous via softmax:
  wji = exp(αji )∑m j=1 exp(α j i )
  (2)
  By applying this parameterization for each transformation layer, we can construct a mixed flow ensemble pMix(x;θ,α), where each layer in this mixed model reflects a weighted combination of the effect of all possible transformations. In this case, the architecture optimization problem is reduced to learning the weight vector for each layer and, at the end of the optimization process, weights will be binarized and the transformation with the highest weight in one layer will be selected as the final transformation. The mixed flow ensemble thus degrades to a normal flow model. The whole procedure is illustrated in Fig. 1 (left).
  As adopted in (Liu et al., 2019), training of the flow ensemble becomes joint optimization of the architecture parameterα and the model parameter θ over the training and validation datasets, which could be written as the following bi-level optimization problem:
  α∗ =argmin α DvalKL[p ∗(x) || pMix(x;θ∗,α)] + λ · CMix(α)
  s.t. θ∗ = argmin θ DtrainKL [p ∗(x) || pMix(x;θ,α)],
  ∀ T ∈ pMix, T ∈ {T 1, T 2, ...Tm},
  (3)
  While the optimization problem is well defined, the key challenge is to construct the flow ensemble within the normalizing flow framework. This is different from traditional neural architecture search, which can mix various operations with no additional issue. Normalizing flow has its unique requirement for the invertibility of transformations and a preferred simple Jacobian calculation, which requires careful handling.
  The mixed flow ensemble pMix(x;θ∗,α) must satisfy two requirements. First, it must be a legal density function such that it can be optimized by the KL divergence formulation. Second, each transformation layer in pMix(x;θ∗,α) should represent a weighted combination of all possible transformations. Consider the ith layer in the mixed flow ensemble with input random variable xin and output random variable xout, and pxin(xin) and pxout(xout) are their corresponding density functions. This layer has m transformation options in {T 1i , T 2i , ...Tmi } and w j i is the corresponding
  weight for each transformation. As discussed in Assumption, we assume all transformations directly model the inverse transformation, i.e. xin = T j i (xout). Two approaches can be used to construct the mixed flow ensemble.
  Construction by Mixed Transformations: The straight forward way of building the ith mix flow ensemble layer is to mix all transformations by weighted summation, as shown in Fig. 1 (right-top). The final weighted transformation for this layer can be thus represented as:
  Ti(xin) = m∑ j=1 wji · T j i (xout) (4)
  There are two drawbacks of this formulation despite its simplicity. First, definition of normalizing flow requires the mixed transformation Ti be invertible and differentiable in order to ensure pxout(xout) legal density function. However, this invertibility is not guaranteed even if all candidate transformations are invertible. Second, even if the mixed transformation is invertible, there is no easy way to calculate the Jacobian determinant of this weighted summation of transformations. Meeting the requirement of invertibility and ease of calculating Jacobian determinant brings strict restrictions on the candidate transformations and prevents the optimization of flow architectures on a wider search space. As a result, the construction of the mixed flow ensemble by weighted summation of transformations is not adopted in this paper.
  Construction by Mixed Distributions: An alternating way is to build the mixed flow ensemble by mixing distributions. For a given transformation T ji in this ith layer, applying the transformation to the input random variable will result in a new distribution:
  pT ji (xout) = pxin(T j i (xout)) · | detJT ji (xout)| (5)
  By applying this to every transformation option in {T 1i , T 2i , ...Tmi }, we can obtain k different distributions, and it is possible to mix all the density functions together by their weighted summation, to get a mixture model as shown in eq.(6).
  pTi(xout) = m∑ j=1 wji · pT ji (xout) (6)
  An illustration of this process is shown in Fig. 1 (right-bottom). Different from the previous approach, the mixture model has a legal density function as: pTi(xout). By the definition of normalizing flow, we can assume that there exists an invertible and differentiable transformation Ti, which transforms xin to xout, although the transformation itself can not be explicitly written out.
  For the next (i + 1)th layer, the density of the mixture model will be used as the input density function pxin(xin) as in the previous layer. By applying this formulation for n layers, the final mixed flow ensemble can be written as:
  pMix(x;θ,a) = mn∑ k=1 Wk · pT1T2...Tn(x,θ) = mn∑ k=1 Wk · pi(x;θi)
  where each Wk = n∏
  i=1 wi and mn∑ k Wk = 1
  (7)
  Each wi is defined in eq.(2) and we use pk(x;θk) to represent a “normal flow architecture” with n transformation layers. Clearly, the final mixed flow ensemble is a legal density function which is in fact, a weighted summation of all possible flow models built with n layers of transformations.
sections.heading: 3.2 OPTIMIZATION WITH APPROXIMATED UPPER BOUND
sections.text: Optimizing the forward KL divergence between the target distribution and the mixed flow ensemble can be written as:
  LOpMix = DKL [p ∗(x) || pMix(x;θ,α)]
  = −Ep∗(x)[log( mn∑ k=1 Wk · pk(x;θk))] (8)
  We will demonstrate that direct optimization of this original loss can lead to underside mixture models. In the whole search space of the flow ensemble, we are interested only in ”normal flow architectures” points, i.e. the points where the weight of one architecture is 1 and others are all 0. However, it can be easily proven that the global optimum of LOpMix may not be the desired normal flow architecture (the red points in Fig. 2). Instead, optimization is very likely to end up in a mixture model that is globally optimal with similar weight for each possible flow architecture (the green point in Fig. 2). In this case, we will encounter difficulty when extracting a normal flow architecture with the search result. A common practice in differentiable architecture search (Liu et al., 2019) is to binarize the weights and select corresponding transformations. However, there is no guarantee that the binarized architecture will have a lower loss, and finding this nearest binarization may lead to performance drop. As a result, optimization with the original loss function is not suitable, and could be risky.
  In this paper, we propose to optimize an upper bound of the original loss function to provide a better global optimum for the search of best normal flow architectures. Our method utilizes Jensen’s inequality log( ∑ W · x) ≥ ∑ W · log(x) as follows, since we have ∑ W = 1 and the log function is concave, we can obtain an upper bound of the KL divergence given as:
  LOpMix = −Ep∗(x)[log( mn∑ k Wk · pk(x;θk)] ≤ LUpMix = −Ep∗(x)[ mn∑ k Wk · log(pk(x;θk))] (9)
  The benefit of optimizing the upper bound can be summarized as follows:
  Proposition 1: The global minimum point of LUpMix is defined by a normal flow architecture.
  Proof: Suppose each flow model pk(x;θk) has an optimal parameter θ∗k that minimizes the KL divergence between p∗(x) and it: −Ep∗(x)[log(pk(x;θ∗k)] ≤ −Ep∗(x)[log(pk(x;θk)] (10) There also exists a flow architecture (pz(x;θ∗z)) that has the minimal KL divergence: −Ep∗(x)[log(pz(x;θ∗z)] ≤ −Ep∗(x)[log(pk(x;θ∗k)], ∀k ∈ mn (11) We can then prove the proposition by showing that:
  LUpMix = −Ep∗(x)[ mn∑ k Wk · log(pk(x;θk))] ≥ −Ep∗(x)[ mn∑ k Wk · log(pk(x;θ∗k))]
  ≥ −Ep∗(x)[ mn∑ k Wk · log(pz(x;θ∗z))] = −Ep∗(x)[log(pz(x;θ∗z)]
  (12)
  Proposition 2: At normal architecture points (Wk = 1,W−k = 0), LUpMix = L O pMix .
  The proof of proposition 2 is apparent.
  With the above propositions and under the assumption that the global optimum can be reached at the end of the optimization, we can show that the solution set, i.e. all possible normal flow architectures are the same in both LOpMix and L U pMix , and we can do optimization with proposed upper bound without violating the original definition. Furthermore, since the global optimum of the upper bound will always lead to a normal flow architecture, we will not end up in finding a mixture model with the need to do heuristic and risky binarization of weights W .
sections.heading: 3.3 EFFICIENT ARCHITECTURE OPTIMIZATION FOR DEEP FLOW MODELS
sections.text: While the flow ensemble by mixed density formulation could reflect the weighted effect of all possible transformation combinations, the architecture optimization complexity grows exponentially with respect to the number of considered transformation types and the number of transformation layers. In this scenario, efficient optimization of the whole flow architecture will not be possible. It is natural to decompose the original problem into sequential optimization of few different blocks, where each block could be optimized in one time with a limited number of layers. We propose two methods to decompose the problem.
  Grow Method: The first approach is a straightforward greedy method which we call ”Grow”. Each time, a block is optimized until convergence, and the weights of the transformation layer are binarized. The searched transformations in this block will be directly added to the searched layer in the previous block. The architecture optimization of later blocks will be based on the existing layers and, the growth of layers stops when reaching the total number of layers constraint. Despite its simplicity, the downside of the “Grow” method is that the optimization is short-sighted. The block being optimized has no information about the architectures which could be added later, and the whole architecture is more likely to be trapped in local minimum.
  Block Method: To avoid the issue of getting stuck in a local minimum, we propose another method named “Block” optimization. Blocks B in this approach are optimized alternatively to allow each block to adjust their architectures with respect to other blocks. In fact, the first “Grow” approach is a specific case of the “Block” method, where all the blocks are initialized as identity transformations and optimized only once.
  Algorithm 1 Algorithm flow for AutoNF Require: Transformations: {T 1, T 2, ...Tm}, Blocks: B = {B1, B2, ...Bl}, Cost: CMix Ensure: n-layer flow model:
  1: while not converged do 2: for each Bi ∈B do 3: while not convergence do 4: αBi = argminαBi D val KL[p
  ∗(x) || pMix(x;θ∗B,αBi)] + λ · CMix(αBi) 5: θB = argminθB D train KL [p
  ∗(x) || pMix(x;θB,αBi)] 6: end while 7: Fix architecture for Bi 8: end for 9: end while
sections.heading: 3.4 COST MODEL AND ALGORITHM FLOW
sections.text: As discussed in section II, we are interested in modeling the training cost (forward calculation cost) and the inverse calculation cost, since each of them plays a different role based on desired applications. We use an independent experiment to model the cost of different types of flows and summarized in a table which are included in Appendix B. With the cost model, the total cost of the mixed flow ensemble could be extracted based on emphasize on different costs, e.g. if training cost is the major concern, only training cost of different flows will be calculated. This total cost CMix is then added as an regularization term into the training loss function.
  In our paper, gradient based method is used for optimization which is efficient in this very high dimensional search space. The architecture parameter α and the flow model parameter θ are optimized alternatively with first order approximation in (Liu et al., 2019). The final algorithm flow of our proposed AutoNF method can be summarized in Algorithm 1.
sections.heading: 4 EXPERIMENTS
sections.heading: 4.1 EVALUATION OF PROPOSED UPPER BOUND
sections.text: Setup: We use a simple example to demonstrate the necessity of doing optimization with our proposed upper bound. We use AutoNF to build a 4 layer flow model with 2 transformation options including planar flow and radial flow from (Rezende & Mohamed, 2015). We use the POWER dataset as the target and optimize with original loss (name M1) and our proposed upper bound (named M2). We use Adam optimizer for both architecture parameter and model parameter with a learning rate of 0.002. The batch size is 512 and the training iteration is 10000.
  The results are shown in Fig.3. For both M1 and M2, we present the weight for planar and radial flow for each layer as well as the training and validation loss during the search process. The final weight for each layer, searched architectures after binarization and the test score are shown in the right-bottom table.
  Analysis: Optimization with our proposed upper bound (M2) shows a concrete convergence of weight to 0 or 1 for each layer, which leads to a desired normal flow architecture, while the optimization with the original loss function (M1) ends up in a mixture model instead of a normal flow architecture, as shown in Fig.3(left). This is within in our expectation as shown in Fig.2. Moreover, although the mixture model is mostly likely to be the optimal in the original loss, the normal flow architecture after binarization however, is not an optimal model. As shown in the right-bottom table, the architecture found by M2 has a significantly better test score than M1, and this clearly supports our statement of doing optimization with our proposed upper bound.
sections.heading: 4.2 SEARCH FOR FLOW MODELS WITH BEST PERFORMANCE COST TRADE-OFF
sections.text: Transformation Options and Reference Designs: To evaluate our AutoNF framework, we setup our experiments with four types of non-linear flows and one linear flow. In autoregressive family, we
  choose affine autoregressive flow (Papamakarios et al., 2017) and rational quadratic autoregressive flow (Durkan et al., 2019). Affine autoregressive flow has limited expressive power but the computation cost is lower, while the later has the state of art performance in autoregressive family with higher cost. Affine coupling layer (Dinh et al., 2015) and rational quadratic coupling layer (Durkan et al., 2019) are selected from coupling layer family. For linear transformation, we combine a reverse permutation and an LU linear layer together as a single layer. Random permutation (Durkan et al., 2019; Oliva et al., 2018) is not used since it is difficult to reproduce in architecture optimization. Every non-linear transformation layer is paired with a linear transformation layer suggested by Durkan et al. (2019) as a final transformation option, i.e., a layer in our experiment contains a reverse permutation, an LU-linear layer and one of the non-linear transformation layer listed above.
  We use the rational quadratic flows family, including rational quadratic autoregressive flow (RQ-AF) and Rational quadratic coupling layer (RQ-C) in (Durkan et al., 2019) which have top 2 performance as the baseline. For fair comparison, we use RQ-AF as the baseline when emphasizing forward cost since it has better performance and use RQ-C as the baseline when emphasizing inverse cost since RQ-C has significantly lower inverse cost.
  Evaluation Metric and Datasets: Evaluating the performance-cost trade-off is an open question in NF, we propose to use a new metric to address the difficulty of negative log-likelyhood (NLL). NLL is a common measurement for density estimation (lower, the better), however, the order of magnitude of NLL is different across different datasets and it is not suitable to use percentage difference to measure how a model is exactly better than another.
  In this paper, We proposed to utilize density and coverage (Naeem et al., 2020) to evaluate the performance of NF models. Density and coverage are recently proposed method to evaluate the sample quality of generative models. The density metric reflects the fidelity of the model and is consistent with NLL metric. Across different datasets, density and coverage are at the same order of magnitude and allows evaluation of architecture across datasets. In our experiments, 10000 samples are drawn from the trained flow models and compare with 10000 samples from the test data. The results of three independent runs are averaged as the final reported results.
  To evaluate the performance-cost trade-off, we define a figure of merit (FOM) as FOM = cost reduction% + density drop% compared to reference SOTA designs. In principle, the weight of the two terms can be manually adjusted to reflect the importance. For demonstration purpose, we use the equally weighted summation to report the results.
  The performance of the flow models are evaluated with density estimation for UCI (Dua & Graff, 2017) and BSDS300 (Martin et al., 2001) datasets.
  Analysis: The architecture search results are reported in Table.1 which includes the test NLL, density, coverage, cost and corresponding FOM. Table.1 shows that our AutoNF clearly helps to find architectures that have better performance-cost trade-off. out AutoNF can reach to up to 3.66X cost reduction and up to 75.2% improvement in FOM compared with SOTA literature results. Across all five different datasets, AutoNF demonstrates an average improvement of 58.67% on FOM with emphasis on forward cost and an average improvement of 52.57% on FOM with emphasis on inverse cost.
sections.heading: 5 DISCUSSION
sections.text: Normalizing flow is highly parameterized module and designing a flow model and use it for application requires a lot of hands-on experience and domain knowledge. In this paper, we show that the AutoNF framework is very effective in balancing performance-cost trade-offs when building complex flow models. Moreover, although not demonstrated in this paper, the framework could also be used to help decide hyper parameters in complex flow model, e.g. the hidden features and number of bins in the SOTA coupling layer (Durkan et al., 2019). In additional, the proposed optimization method with upper bound can be easily extended to other suitable probabilistic kernels. one example is to identify the best parameterized distribution(s) within a mixture model. We believe our framework will be very useful in many machine learning applications where normalizing flows are needed.
title: AUTONF: AUTOMATED ARCHITECTURE OPTIMIZA-