Direct Evolutionary Optimization of Variational Autoencoders With Binary Latents
Authors: Enrico Guiraud
Jakob Drefs
Filippos S Panagiotou
Jorg Lucke
Venue: ICLR 2022 Submitted (2022)
Keywords: variational optimization
variational autoencoders
denoising
inpainting
evolutionary algorithms

Abstract: Many types of data are generated at least partly by discrete causes that are sparsely
active. To model such data, we here investigate a deep generative model in the
form of a variational autoencoder (VAE) which can learn a sparse, binary code
for its latents. Because of the latents’ discrete nature, standard VAE training is
not possible. The goal of previous approaches has therefore been to amend (i.e.,
typically anneal) discrete priors in order to train discrete VAEs analogously to
conventional ones. Here, we divert much more strongly from conventional VAE
training: We ask if it is also possible to keep the discrete nature of the latents
fully intact by applying a direct, discrete optimization for the encoding model. In
doing so, we (1) sidestep standard VAE mechanisms such as sampling approximation, reparameterization trick and amortization, and (2) observe a much sparser
encoding compared to autoencoders that use annealed discrete latents. Direct optimization of VAEs is enabled by an evolutionary algorithm in conjunction with
truncated posteriors as variational distributions, i.e. by a combination of methods
which is here for the first time applied to a deep model. We first show how the discrete variational method (A) ties into gradient ascent for network weights, and how
it (B) uses the decoder network to select binary latent states for training. Sparse
codes have prominently been applied to image patches, where latents encode edge-like structure. For our VAEs, we maintain this prototypical application domain
and observe the emergence of much sparser codes compared to more conventional
VAEs. To allow for a broad comparison to other approaches, the emerging encoding was then evaluated on denoising and inpainting tasks, which are canonically
benchmarks for image patch models. For datasets with many, large images of single objects (ImageNet, CIFAR etc) deep generative models with dense codes seem
preferable. For image patches, however, we observed advantages of sparse codes
that give rise to state-of-the-art performance in ‘zero-shot’ denoising and inpainting benchmarks. Sparse codes can consequently make VAEs competitive on tasks
where they have previously been outperformed by non-generative approaches.

Under review as a conference paper at ICLR 2022
DIRECT EVOLUTIONARY OPTIMIZATION OF VARIA- TIONAL AUTOENCODERS WITH BINARY LATENTS
Anonymous authors
Paper under double-blind review
ABSTRACT
Many types of data are generated at least partly by discrete causes that are sparsely active. To model such data, we here investigate a deep generative model in the form of a variational autoencoder ( (VAE) which can learn a sparse, binary code for its latents. Because of the latents' discrete nature, standard VAE training is not possible. The goal of previous approaches has therefore been to amend (i.e., typi- cally anneal) discrete priors in order to train discrete VAEs analogously conven- tional ones. Here, we divert much more strongly from conventional VAE training: We ask if is also possible to keep the discrete nature of the latents fully intact by applying direct, discrete optimization for the encoding model. In doing so, we (1) sidestep standard VAE mechanisms such as sampling approximation, repa- rameterization trick and amortization, and (2) observe much sparser encoding compared to autoencoders that use annealed discrete latents. Direct optimization of VAEs is enabled by evolutionary algorithm in conjunction with truncated posteriors as variational distributions, i.e. by a combination of methods which is here for the first time applied to deep model. We first show how the discrete vari- ational method (A) ties into gradient ascent for network weights, and how it (B) uses the decoder network to select binary latent states for training. Sparse codes have prominently been applied to image patches, where latents encode edge-like structure. For our VAEs, we maintain this prototypical application domain and ob- serve the emergence of much sparser codes compared to more conventional VAEs. To allow for a broad comparison to other approaches, the emerging encoding was evaluated on denoising and inpainting tasks, which are canonical benchmarks for image patch models. For datasets with many, large images of single objects (Ima- geNet, CIFAR etc) deep generative models with dense codes image patches, however, we observed advantages of sparse codes that give rise to state-of-the-arr performance in 'zero-shot' denoising and inpainting benchmarks. Sparse codes can consequently make VAEs competitive on tasks where they have previously been outperformed by non-generative approaches.
preferable. For
INTRODUCTION & RELATED WORK
Objects or edges in images are either present or absent, which suggests the use of discrete latents for their representation. There are also typically only few objects per image (of all possible objects) or only few edges in any given image patch (of all possible edges), which suggests a sparse code (e.g. Olshausen & Field, 1996; Titsias & Lazaro-Gredilla 2011; Goodfellow et al. 2013 Sheikh et al.) 2014). In order to model such and similar data, we study a novel, direct optimization approach Tor variational autoencoders (VAEs), which can learn sparse, discrete encoding. VAEs (Kingma & WWellnn 2014 Rezende et al. 2014) in their many different variations, have successfully been applied to large number of tasks including semi-supervised learning (e.g. MMaloe et al.) 2016), anomaly detection (e.g. Kiran et al. 2018), sentence interpolation (Bowman et al. (016) or music interpolation (Roberts al. 2018) name few. The success of VAES, in these tasks, rests on a series of methods that enable the derivation of scalable training algorithms to optimize VAE pa- rameters. These methods were originally developed for Gaussian priors; account for VAEs with discrete latents, novel methodology had to be introduced (we elaborate below and later in App.
The training objective of VAEs derived from a likelihood objective, i.e., we seek model parameters θ of VAE that maximize the data likelioel,,oo,, T.(@)- Σn, log (pel (7 (n)),, where we denote

---

Under review as a conference paper at ICLR 2022
by (lNNN) set of N observed data points, and where pel (a) denotes the modeled data distribution. Like conventional autoencoders Bengio et al. 2007). VAEs use a deep neural network (DNN) to generate (or decode) observables from a latent code Unlike conventional autoencoders, how-
ever, the generation of data / is not deterministic but it takes the form of a probabilistic generative model. For VAEs with binary latents, we here consider the following generative model:
pe (2) = (e = II. (m th (1 T.) )))))))), pe (i) 2) = N (1
o), ())
(1)
with E' E =(0,1 1 being a binary code parameterized by priors म. I E RD, and the non-linear function (2) W) being a DNN that outputs the mean of the Gaussian distribution, pa () is commonly refemred to as decoder. The set of model parameters is θ { W. where W incorporates DNN weights and biases. We assume homoscedasticity of the Gaussian distribution, but note that there is no obstacle to generalizing the model by inserting DNN non-linearity that outputs a correlation matrix. Similarly, the algorithm could easily be generalized to different noise distributions should the task hand call for it. For the purpose of this work, however, we will focus on the elementary VAEs given by Eqn.
For conventional and discrete VAEs. essentially all optimization approaches seek to approximately maximize the log-likelihood using the following series of methods (we elaborate in App.(A):
(A) Instead of the log-likelihood, a variational lower-bound (a. ELBO) is optimized.
(B) VAE posteriors are approximated by an encoding model, i.c. by specific distribution (usu- ally Gaussian) parameterized by one or more DNNs.
(C) The variational parameters of the encoder are optimized using gradient ascent on the lower bound, where the gradient is evaluated based on sampling and the reparameterization trick to obtain sufficiently low-variance and yet efficiently computable estimates.
(D) Using samples from the encoder, the parameters of the decoder are optimized using gradient ascent the variational lower bound.
Optimization procedures for VAEs with discrete latents follow the same steps (Points A to D). How- ever, discrete or binary latents pose substantial further obstacles for learning, mainly due to the fact that backpropagation through discrete variables is generally not possible or biased (Rolfe, 2016 Bengio et al. 2013). Key elements of gradient estimators commonly applied for discrete latent VAÉS include, e.g., reparameterizations of continuous approximations to discrete latents (Jang al.) 2016) or score function based reformulations yielding a surrogate loss (Schulman et al.) 2015 also see Related Work and A.). While accomplishing, in different senses, the goal of maintaining standard VAE training as developed for continuous latents (i.c., learning procedures and/or learn- ing objectives that allow for gradient-based learning of the encoder and decoder DNNs), gradient estimation methods apply significant amounts of methodology additional to the learning methods conventionally applied for VAE optimization. These additional methods (compare Fig- their ac- companying design decisions and used hyper-parameters (e.g. parameters for annealing to 'soften' discrete distributions) do increase the complexity of the system that has to be optimized. Further- more, the additional methods usually impact the learned representations. For instance, softening of discrete distributions, c.g. by using 'Gumbel-softmax' (Jang et al. (016)) or 'tanh' approximations (Fajtl et al. (020) seems favor dense codes. While dense codes (as also used by conventional VAHS and GANs) can result in competitive performance for a subset of the above discussed tasks, other recent contributions point out advantages of sparse codes, e.g., in terms of disentanglement (Tonolini et al. 2020) or robustness (Sulam et al. 2020 Paiton et al. 2020).
In order avoid adding methods for discrete latents to those already in place of standard VAEs, it may be reasonable to investigate more direct optimization procedures that do not require, e.g., a softening of discrete distributions or other mechanisms. Such direct approach challenging, how- ever, because once DNNs are used to define the encoding model (as commonly done), we require methodologies for discrete latents to estimate gradients for the encoder (as done via sampling and reparameterization; see Points C and D). A direct optimization procedure, as we investigate here, consequently has to change VAE training substantially. For the data model (I). we will maintain the variational setting (Point A) and a decoding model with DNNs non-linearity. However, we will not use an encoder model parameterized by DNNs (Point B). Instead, the variational bound will be increased w.r.t. an implicitly defined encoder model which allows for efficient discrete optimiza- tion. The procedure does not require gradients to be computed for the encoder such that discrete latents are addressed without the of reparameterization trick and sampling approximations.
2

---

Under review as a conference paper at ICLR 2022
Related Work. In order to maintain the general VAE framework for encoder optimization in the case of discrete latents, different groups have suggested different possible solutions: work by |Rolfe (2016), for instance. extends VAEs with discrete latents by auxiliary continuous latents such that gra- dients can still be computed. Work on the concrete distribution (Maddison et al. 2016) or Gumbel- softmax distribution (Jang et 2016) proposes newly defined continuous distributions that contain discrete distributions as limit cases, Work by Lorberbom et al. (2019) merges the Gumbel-Max reparameterization with the use of direct loss minimization for gradient estimation, enabling effi- cient training on structured latent spaces (for further improved Gumbel-softmax versions also see Kool et al., 2020, Potapezynski et al. 2020 Paulus et al. (02I). Furthermore, work, e.g., by van den Oord et al. (2017), and Roy et al. (2018) combines VAES with vector quantization (VQ) stage in the latent layer. Latents become discrete through quantization but gradients for learning are adapted from latent values before they are processed by the VQ stage. Similarly, [Tomzakk & Welling (2018) use what they call (Icarnable) pseudo-inputs, which determine a mixture distribution as prior, and the ELBO then contains additional regularization for consistency between prior and average poste- rior. Tonolini et (2020) extend this work and introduce an additional DNN classifier. The classifier selects pseudo-inputs and the classifier weights are learned instead of the pseudo-inputs themselves. Using their approach, Tonolini et al. (2020) also argue for the benefits not only of discrete latents but of a sparse encoding in the latent layer in general. Fajtl al. (2200) base their approach on a deterministic autoencoder and use a tanh- -aarropppoxiitiionn of binary latents and projections to spheres in order to treat binary latents. Targeting not only discrete VAE optimization but more gen- eral approaches such as probabilistic programming or general stochastic automatic differentiation, Bingham et al. (2019); van Krieken et al. (202T) apply gradient estimators for discrete random vari- ables which optimize surrogate losses (Schulman et al., (215)) derived based on the score function (Forsteer et al.) 2018) or other methods (yan Kricken et al. (02I]. For the derivation of efficient, unbiased any-order derivatives, techniques for variance reduction of estimators are identified as key components. yan Krieken et al.] (2021) mention exponential scaling behavior which, however, can be addressed using efficient parallelized computations. Furthermore related are methodologies for gradient estimation for unknown ("black-box') functions of discrete or continuous random variables as studied by (Grathwohl et al. 2018), who optimize neural network-based surrogate losses.
In terms of numerical evaluation, the above discussed approaches demonstrate the benefits of the respective new methodology very different experiments. For instance, |van den Oord et al. (2017) focus on image, video and speech generation capabilities of their approach, and report concrete values e.g. for phoneme classification for their evaluation. Roy et al. (2018) show improved image generation capabilities, e.g., on CIFAR and report accuracy scores for machine translation similar to autoregressive baselines. TTomzaak & Welling (2018) show competitive likelihood results in the unsupervised permutation invariant setting for many data sets; and Fajtl et al. (2020) evaluate their approach based on accuracy/sensitivityy tradeoffs among other comparisons. Toooolii et al.) (2020) focus the competitive capabilities of their VAEs to learn meaningful (disentangled) features; and Lorberbom et al. (2099) focus on the benefits of structured priors. Numerical evaluations of their VAES and different numbers of categoric latents show better performance of their direct loss minimization than Gumbel-softmar VAEs, and the same applies for comparisons in terms of semi- supervised learning. Similarly to Tonolini et al.] (2020), disentanglement results for the relatively large CelebA dataset are also shown by Lorberbom et al. (2019). For this and many other datasets, large DNNs are required while the latent layers are often kept relatively small.
DIRECT VARIATIONAL OPTIMIZATION
Let us consider the variational lower bound of the likelihood. If we denote by (=)(2) the variational distributions with parameters Ø- (Φ(1) ..... ((N)), then the lower bound is:
F( θ) = Σ, E (m) log (Z 2) pe - Σn, E. go0 log (10 (n) (3)),
(2)
where we sum over all data points ((1) x(N), and where IE %6 value of a function M())) w.r.t. distribution to (E). The general challenge for the maximization of F(O, +) is the optimization of the encoding model o(")) VAEs with discrete latents add to this challenge the problem of taking gradients w.r.t. discrete latents. Seeking to avoid such derivatives, we, for our purposes, do not use DNN for the encoding model. Consequently, we need to define an
[h()) denotes the expectation
3

---

Under review as a conference paper at ICLR 2022
alternative encoding model (n) which has remain sufficiently efficient. Considering prior work on generative models with discrete latents, variational distributions based on truncated posteriors offer themselves as such an alternative (Lücke & Sahani 2008). Truncated posterior approxima- tions have been shown to be functionally competitive (e.g. Sheikh et al. 2014]] Hughes & Sudderth, 2016), and they are also able efficiently train large-scall models with hundreds or thousands of latents (e.g. (Sheikh & Lücke 2016; Forster & Lücke, (0118). In all these previous applications, optimization of truncated variational distributions relied on expectation maximization and closed- form or pseudo-closed form M-steps for shallow models. In the context of discrete latent VAßs, the important question arising is if or how the optimization of truncated variational distributions for the encoding model can be performed jointly with gradient-bace baased optimization of the decoding model (which uses a DNN).
Optimization of the Encoding Model. Encoder optimization is usually based a reformulation of the variational bound 2 given by:
F(2, θ) = En EE (m) [log (2(()
(n) (E): [2)]] - Σn DKL [
(3)
For discrete latent VAEs, the variational distributions in are commonly replaced by an amortized encoding model (2) with DNN-based parameterization. When expectations w.r.t go (#) ap- proximated (as usual) via sampling, the encoder optimization requires gradient estimation methods for discrete random variables (cf. Related Work and A.p. In contrast, our proposed approach uses truncated posteriors as variational distributions and hence deviates substantially from the afore- mentioned standard approach. Given a data point H (m), truncated posterior is simply the posterior
itself truncated to subset " (m) of the latent space, i.e., for 5 Φ (x) applies:
(m) d (2) = (= (=(=
pe |z) pe(
Σ
(= I(m)
Σ (o(ā(n) (z pe()))
frea(0)
while 46 (2) 0 for 2 4 (n) The subsets 4 {
|==1 the variational parameters. Cen- trally for this work, truncated posteriors allow for a specific alternative reformulaiion of the bound. The reformulation recombines the entropy term of the original form (2) with the first expectation
value into a single term, and is given by (see Lüicke Forster 2019
Lücke 2019 for details):
F( θ) Σ log ( Σ
(e (0) p)()))
(5)
())
Thanks to the simplified form of the bound, the variational parameters 4 (n) of the encoding model can now be sought using direct discrete optimization procedures. More concretely, because of the
specific form (5, pairwise comparisons of joint probabilities are sufficient to maximize the lower
bound: if we update the set +b" (*) for a given z (n) by replacing state gold Φ
(x)
with state
gnow & 4. (n) then F( θ) increases if and only if:
log (pe (n)x)) > log (po(7()), zold).
(6)
To obtain intuition for the pairwise comparison, consider its form when inserting the binary VAE (T) into the left- and right-hand sides. Eliding terms that do not depend on 2 we obtain:
log (7, - - W - 2 Σn TA 2h.
where मn =lg ((1 ((1-ma/TT) mM)/mM). The expression assumes an even more familiar form if we restrict ourselves for a moment to sparse priors with n. न < i.e., मF न > 0. Criterion (6) then becomes:
|| filzzew 2IIl + 20 nen
< || = w) + 20 |
(8)
where 12" = ー 2/. Such functions are routinely encountered in sparse coding or compressive sensing (Eldar & Kutyniok 2012;: for each set + (x) we seek those states 7 that are reconstructing I (n) well while being sparse (2 with few non-zero bits). For VAEs, μZ(z, W) is DNN and such much more flexible in matching the distribution of observables T than can be expected from linear mappings. Furthermore, criteria like ( usually emerge for maximum a-posteriori (MAP) training
4

---

Under review as a conference paper at ICLR 2022
Figure 1: The optimization process of the variational parameters ((n) using evolution- ary search. A. Some states are selected as parents. B. Each child undergoes mutation. C. Children are merged with the original population and the least fit are discarded.
A. Parent selection
B. Mutation
C. New population
@
Stowas
Etuess
0010
0010
1010
0010
0011
0OL
001
1010
2.5
0001)
000
2
0001
in sparse coding (Olshausen & Field 1996). In contrast to MAP, however, we here seek a population of states E in 4 (n) for each data point. It is consequence of the reformulated lower bound ( that remains optimal to evaluate joint probabilities (as for MAP) although the constructed population of states o" (*) can capture (unlike MAP training) rich posterior structure.
Evolutionary Search. But how can new states E geew that optimize & "²) be found efficiently in high- dimensional latent spaces? Random search and search by sampling has recently been explored for elementary generative models (Lücke al., 2018). Here we will follow another recent suggestion Guiraud et al. 2018) and make use of a search based on evolutionary algorithms (EAs). In this setting we interpret sets &- (m) as populations of binary genomes / and base the fitness function on
Eqn. Concretely, using (n) as initial parent pool, we apply the following genetic operators in
sequence to suggest new states to update the $ (*) based on 6q. (see Fig. for an illustration and A.I. for further details): firstly. parent selection stochastically picks states from the parent pool. Each of these states undergoes mutation: one offisping diversity. Crossover could also be employed to increase offisping diversity. We repeat the procedure using the children generated this way the parent pool, giving birth to multiple generations of candidate states. Finally, we update x (") by substituting individuals with low fitness with candidates with higher fitness. The whole procedure can be seen with perfect memory or very strong clitism (individuals with higher fitness never drop out of the gene pool). Note that the improvement of the variational lower bound depends generating as many as possible different children with high fitness over the course of training.
bits are flipped to further increase
evolutionary algorithm
We point out that the EAs optimize each + (m) s.t. the technique can be efficiently applied to large datasets conjunction with stochastic or batch gradient descent on the model parameters O. The approach is, at the same time, memory intensive,
independently, which allows for distributed execution
ie. all sets + (m) need to kept memory (see App A for details).
Optimization of the Decoding Model. Using the previously described encoding model (11) (=), can compute the gradient of (2) w.r.t. the decoder weights W which results in (see App. for
more details):
(=) V (1()) -
-
The -igt--hand-side has salient similarities to standard gradient ascent for VAE decoders. Especially the familiar gradient of the mean squared error (MSE) shows that, e.g., standard automatic differ- entiation tools can be applied. However, the decisive difference are the weighting factors g(() (2).
(m) Considering (4). in order to compute the weighting factors we require all E + to be passed through the decoder DNN. As all states of & (m) anyway have to be passed through the decoder for the MSE term of D the overall computational complexity not higher than an estimation of the gradient with samples instead of states in x
(n) (but we use many states per Φ compare Tab, [
To complete the decoder optimization, update equations for variance o² and prior parameters म can be computed in dosed-form (compare, e.g., Shelton et al. 2011) and are given by
2nnew
1 Σ DN
DEX
Σ
4
(n)
(2)
| (m) paZz 2) and znew
1
Σ ()
(n) d
(2) 2. (10)
(M)
The full training procedure for binary VAES is summarized in Algorithm [ We refer to the bi- nary VAE trained with this procedure as Truncated Variational Autoencoder (TVAE) because of the applied truncated posteriors.
5

---

Under review as a conference paper at ICLR 2022
Algorithm Training Truncated Variational Autoencoders
Initialize model parameters {W, म. x
Initialize each 4- (") with distinct latent states repeat
Zi Bern(2;;
for all batches in dataset de for sample in batch do &' = (n))
Non-linear layer(s)
Output layer plzz, W)
for all generations de 4new" mutation (sclection (0"ew)
~ N(d,
( (*) U new
end for
Truncate (x)
to S fittest elements based on
Figure 2: Graphical Representation of the Model Architecture Used in Nu- merical Experiments.
end for
Use Adam to update using
end for
Use [0] update म., a²
until parameters & have sufficiently converged
3 NUMERICAL EXPERIMENTS
TVAE can flexibly learn prior parameters T..-... TH and if low values for the Th are obtained (which will be the case) the code is sparse. The prototypical application domain to study sparse codes is image patch data (Olshausen & Field 1996] Goodfellow et al. (012). We consequently use such data to investigate sparsity, scalability and efficiency on benehmarks.
AB.. we furthermore report results for a benchmark with audio data. For all numerical experiments, we employ fully connected DNNs 77(;; W) for the decoder as illustrated Fig.2 2 the exact network architectures and activations used are listed in Tab. The DNN parameters are optimized based on ( using mini-batches and the Adam optimizer (details in App. B.T
Sparsity and scalability. After first verifying that the procedure can recover generating parameters using ground truth data (see A.p. pixels (van Hateren & van der Schaal 1998). We then applied TVAE with different settings. First, we used a model with H = 300 and a linear decoder; and, second, a TVAE with H = 300 and deep decoder with architecture (300-300-256), see App. [B.3] for details. Regarding sparsity, observed for linear and non-linear TVAES a sparse encoding. For the linear TVAE we observed on average 20.3 latents active across data points (i.e.. En nh / H 20.3 300), and for the non-linear TVAE we observed on average 28.5 latents to be active (x, sparse codes also when we changed parameter initialization, used other DNNs and when changing latent dimensions. Furthermore, we observed efficient scalability to large latent spaces (we went up to H 1000) as long as decoder DNNs were of small to intermediate size. Compared to linear decoders, the main additional computational cost is given by passing the latent states of tp (") through the decoder DNN. instead of just through a linear mapping. The sets of states (i.e., the bitvectors in (")) could be kept small, at size S = j (r) = 64, such that N x ( (*) o [" l) states had be evaluated for each epoch. This compares N M states that would be used for standard VAE training (given M samples are drawn per data point). Differently to standard VAE
B.2), we used = 100, 000 whitened image patches of 16 x 16
H 28.5 / 300). We observed
training the sets क (m) have to be remembered across iterations. For very large datasets, the additional O(Nx + (n)
x H) memory demand can be distributed over compute nodes, however.
Denoising and inpainting. The experiments above show a notable difference in scalability char- acteristics compared to other (including discrete) VAEs. Using a non-amortized approaches means that memory and computational load more strongly increase with data points than for amortized training. Above, we processed 100, 000 data points which is still feasible for DNNs of inter- mediate size. Large decoder DNNs increase the computational load significantly, however, as (n) N X (1 (m) + | newll) |) latent states have to be passed through the decoder. Furthermore, larger DNNs require more data points to not overfit which further increases computational load of our N- dependent method. Tasks such as disentanglement of features using high-dimensiioal input data, large DNNs, and small latent spaces (see introduction) are, therefore, not regime where the here studied approach can be applied efficiently. However, for tasks with relatively few data for which an as effective as possible optimization is required, advantages of direct optimization can be expected.

---

Under review as a conference paper at ICLR 2022
A Orgirall
Controlled candiorn
Denoising results for House. D compares PSNRs (in dB) obtained with different 'zero-shot' mod- els using a fixed patch size and number of latents (see text for details). E lists PSNRs for different algorithms with different optimized hyper-parameteet
Figure 3:
$1.00
3335
11:15
Mekay 10
12.22
26.00
31:00
The top category only requires the noisy image. The middle requires addi- tional information such as noise level (KSVD, WNNM, BM3D) or additional noisy images with matched noise level (n2v²). The bottom three algorithms use large clean datasets. depicts the denoised image obtained with TVAE for a 50 in the best run (PSNR=30.03 dB).
VI4A
$4.40
32:33
2016
USC
12:31
26.30
S30
$2.08
36.5
IYAD
34.27 4 22
13.65 L .06
29.66 =
22.01
32.10
BLN
KSVD
18:22
7016
7716
RESID
36.5
13.90
24.8
RPIL
2115
SOGAAX
3437
25.28
2001
For image patches, sparse codes are often preferred to dense encoding. A canonical benchmark to evaluate image patch models is 'zero-shot' denoising, which recently became popular also because conventional DNN denoising is not offering good solutions. 'Zero-shot' means that only the noisy image is used for training. If no clean data available, variations of feed-forward DNNs have been suggested whose training objectives have been altered to enable training on single (or few) noisy images (e.g. Lehtinenn et al. 2018 Krull et al. 2019b). However, deep generative models are (we would argue) more natural candidates to train on noisy data as their learning objective can be used directly. If few data is available for 'zero-shot' learning, large and very deep DNNs cannot be used. [Shocher et al.] (2018), for instance, also argue that smaller DNNs are sufficient for the "zero-shot" setting. The task is consequently natural and well suited to evaluate direct optimization, and it has the very significant additional benefit of allowing for comparison to large range of other approaches that have recently been suggested. Most notably, we can compare to other VAEs (Jang et al., 2016 Park et al., 2019a), to sparse coding, to large feed-forward DNNs (Zhu et al. [019|Dong et al. 2019), and to DNNs dedicated to learning from noisy data (Lehtinen et al. 2018 image inpainting. Like denoising, inpainting allows for comparison to other reported results on standard benchmarks. Additionally, inpainting highlights another advantage of the direct optimization approach we study: as no encoder DNNs are used, missing data can naturally and directly be treated probabilistically (see below).
Krull al. 2019b). Furthermore,
evaluate our approach
The one denoising benchmark that offers the broadest possible comparison to other methods the 'house" image (Fig.B)A) Standard benchmark settings for 'house" make use of additive Gaussian white noise with standard deviations a E (15, 25, 50]. First, consider the comparison in Fig. Fig.3 3D where all models used the same patch size of D = 8 x 8 pixels and H = 64 latent variables (App.[B.4ffor details). Fig. FDD lists the different approaches in terms of the standard measure of peak signal-to-noise ratio (PSNR). Values for MTMKL (Titsias & Lázaro-Gredill, [ GSC (Sheikh) ct al. 2014) and S5C (Sheikh & Lücke 2016) were taken from the respective original publications (which all established new state-of-ther art results when first published). As can be observed, TVAE significantly improves performance for high noise levels. The approach is able to learn the best data representation for denoising and represents the state-of-the-art in this controlled setting (i.e., fixed D and H). The decoder DNN of TVAE provides the decisive performance advantage: TVAE significantly improves performance compared to linear Binary Sparse Coding (var-BSC, [Hennies et al. 2010 Shelton et al., 2011), confirming that the high lower bounds of TVAE on natural images translate into improved performance on a concrete benchmark. For 25 and o 50, TVAE also significantly improves on MTMKL, GSC, and S5C. These three approaches are based on a spike- and-slab sparse coding model (also compare Goodfellow et al.) 2012). Despite the less flexible Bernoulli prior, the decoder DNN of TVAE provides the highest PSNR values for high noise levels.
To extend the comparison, we next considered the denoising task without controlling for equal conditions. Concretely, we allowed for any approach that performs denoising on the benchmark including approaches that are trained on large image datasets and/or use different patch sizes (in- cluding multi-scale and whole image processing). Note that different approaches may employ very different sets of ing approaches, hyper-parameters include patch and dictionary sizes; for DNN approaches they include all network and training scheme papperr-rraeterss.. By allowing for comparison in this less controlled setting, include number of recent approaches including large DNNs trained
that can be optimized for denoising performance: for sparse cod-
7

---

Under review as a conference paper at ICLR 2022
A
Noley
Denoised
B
GSVAE
VLAE
TYKE
Model
Spacsity
Lower Bound
PSNR
GIVAR (10-500-5m))
48.03
25.65
GSVAB (266-256-512)
46.18
26-13
VLAB (50-500-500)
a/a
45.98"
26.55
TVAE (50-500-500)
17.98
30.03
TVAE (356-250-513)
16. 16.86
29 96
C
Singleton
Figure 4: Comparison of data representations learned by denoising image patches (cf. App. B.6)
on clean data and training schemes specifically targeted to noisy training data. Fig. shows the denoising performance for the three noise levels we investigated, with results for other algorithms taken from their corresponding original publications unless specified otherwise. For WNNM and EPLL we cite values from Zhang et al. (201)). The results reported for noise2void (n2v, Krull et al., 2019b), Gumbel-softman VAE (GSVAE: Jang al. 2016). VLAE (Park et al. 2019a), we produced ourselves by applying publicly available source code (see App. B.4).
Note that the best performing approaches in 3 were trained on noiseless data: EPLL Zoran & Weiss 2011), BDGAN (Zhu et al., 2019) and DPDNN (Dong et al. 2019) all make use of clean training data (typically hundreds of thousands of data points or more). For denoising, EPLL also requires the ground-truth noise level of the test image. Ground-truth noise level information is also required by KSVD (Elad & Aharon 2006) and WNNM (Gu et al. (014). As noisy data very frequently occurring, lifting the requirement of clean data has been of considerable recent interest with, c.g., approaches like noise2noise (n2n Lehtinen et al. 2018 and noisc2void having received noisy training
considerable attention. The n2n approach can achieve denoising performance data which is almost as high as the performance of a given DNN when trained on clean data, would thus outperform all approaches in Fig except for the bottom three. However, n2n requires different noise realizations of the very same underlying image. The noise2void approach aims to remove this unrealistic, artificial assumption. Considering 3Eg PSNR values of TVAE were consistently higher than those of n2v even if n2v was trained on external data with matched noise level (n2vf in Fig. E). Performance of TVAE is 0.2dB lower than BM3D for 25 and 0. 0.6dB higher for a 50, which makes it, for larger noise levels, the state-of-the- on this benchmark in the 'hero-shot' setting (i.e., the setting n2n and n2v aim to address).
noise
Fig.3
Besides measuring PSNRs, we investigated the generative representation that TVAE used for de- noising. For TVAE, training and data reconstruction is performed based on patches taken from the noisy image, and reconstructed image patches are finally combined to generate the denoised image (see App. for details). Based on such image patches, TVAE learns a sparse encoding which, in terms of lower bounds, shows to be very competitive compared to other generative models (com- pare Fig. 4... For the House denoising benchmark (Fig (Fig,3 B), the sparsity, i.c., the average number of active latents Σn Wh H was 5.98 64 (a 15), 4.47 64 (a 25), 1.65/ (a 50).
Finally, TVAE can be applied to 'zero-shot' inpainting tasks using a procedure similar to the one employed for denoising. For TVAE, the treatment of missing data is directly available. Missing pixel values are simply treated as such using the probabilistic description of the model. Concretely, when evaluating log-joint probabilities of a data-point during training, missing values are treated as unknown observables AAp. In contrast, amortized approaches will have to specify how the deterministic encoder DNNs should treat missing values. compares PSNRs obtained with TVAE to other methods: the left table shows results for 'House" where we separate BPFA and TVAE, which are permutation-invarice not cormutaaioo-invariii
approaches, from DIP and Papyan et al. (2017), which are (right) shows results for "Castle', where we separate 'zero-shot' ap- proaches (top section) from non- zero-shoo'' approaches (bottom section; PLE refers to the approach from Yu et al.) (2012), IRCNN refers to Chaudhury & Roy (017 Fig 5 (right) shows the result of 'zoro-shot' inpainting on 'Castle' with 50% missing pixels (more details in A.5). As can be observed, TVAE is ofate-of-the-arr for 'House' and for the larger 'Castle' with 50% missing pixels. But if non- poon-eenuttaiinn invariant DNNs with specific, large U-nets are used (DIP for 'House"), or models are trained clean data, then higher PSNR values are achieved.
8

---

Under review as a conference paper at ICLR 2022
House 50%
Castle 50%
Castle 80%
Originol
50% maisingg
Restored
MTMKL BPEA
a//a
MTMKL
b/aa
94
38.02
BPFA
36-45
29.12
TVAE
TVAE
37.33
93
Papyan et al.
34.58
PLE
38.34
30.07
DIP
39.16
IRCNN
a/a
28.74
Figure 5: Inpainting results for House (50% missing pixels) and Castle (50% and 80% missing). Highest PSNR in the 'zero-shot' setting (top rows) marked bold; overall highest PSNRs are bold and underlined. PLE requires the noise level as additional information; IRCNN requires external clean training images; Papyan et al. and DIP are not permutation invariant. The rightmost image depicts TVAE's inpainting result for Castle (50% missing; sparsity Σn Thh H was 10.56 / 512).
4 DISCUSSION
We investigated VAEs with binary priors able to learn sparse latent codes. We were in general inter- ested in how such codes can efficiently be learned, and what advantages (and disadvantages) can be observed. Compared to all previous VAEs with discrete latents, the approach we followed differs the most substantially from conventional VAE learning. While all other VA maintain amortization and reparameterization as key elements, the TVAE approach instead uses direct discrete optimization of binary latent vectors. A conceptual advantage of the approach its concise formulation (compare Fig. 7 with fewer algorithmic elements, fewer hyperparameters and fewer model parameters (e.g., no parameters of encoder DNNs) Functional advantages of the approach are its avoidance of an amortization gap, its ability to learn sparse codes, and its generality (it does not use specific pos- terior model, and can be applied to other noise models, for instance). However, the disadvantage of non-amortized approach is a lower computational efficiency: we optimize variational parameters for each data point which is more costly. Conventional amortized approaches (for discrete or con- tinuous VAEs) are consequently preferable if one seeks to optimize large. intricate DNNs large data sets. There are, however, alternatives such as transformers (which can use > >150M parameters) or diffusion nets, which both are considered to perform more strongly than VAEs for large-scale settings and density modeling (Child et al. 2019 Kingma et al. 20221] for recent comparisons).
When no sufficiently large datasets are available, models incorporating large DNNs can not be op- timized. In such cases, we observe sparse codes obtained by direct discrete optimization to be advantageous. For image patch modeling. TVAE with intermediately large decoder DNNs outper- formed Gumbel-softmax VAEs (GSVAE) as well as, e.g., a recent continuous VAE baseline (VLAE; Park al. 2019a| Figs. The competitive performance presumably due to the approach not being subject to an amortization gap, due to it avoiding factored variational distributions, and more generally due to the emerging sparse codes being well suited model image patches. In com- parison, the additional methods to treat discrete latents in GSVAE seem to result in dense codes with significantly lower performance than TVAE. Performance of VLAE much more competitive. While VLAE uses vanilla non-sparse (i.e. Gaussian) prior, its continuous encoding is presumably a reason why its dense codes result in higher ELBO values than GSVAE (but in lower values than TVAE). Dense codes are notably not necessarily disadvantages for image data. For datasets with many images of single objects like CIFAR, the dense code of GSVAE and also of VLAE is similar or better in terms of ELBO values than TVAE (Fig. (5). The suitability of sparse vs. dense codes consequently seems to highly depend on the data, and here we confirm the suitability of sparse codes for image patches. Based on the high ELBO values of TVAE for patches (Figs 4122. we observed TVAE to result in state-of-te oftte-of-the-arr art performance on the recently popular task of 'eroo-hoo'' denoising (also see Fig. [6] for benchmarking results with audio data). Likewise, the approach is competitive for 'zero-shot" inpainting. Inpainting highlights another advantage of direct optimization: in con- trast to other (continuous or discrete) VAES, it is not required to additionally specify how missing data shall be treated by encoder DNN (see A.5.
Our conclusion is consequently that direct discrete optimization can, depending on the task, serve as alternative for training discrete VAEs. In a sense, the approach can be considered more brute- force than conventional amortized training: direct optimization is slower but at scales at which can be applied more effective. To our knowledge, the approach is also the first training method for discrete VAES not using gradient optimization of encoder models, and in general the first which makes discrete VAEs competitive, e.g., for 'zero-shot' denoising and inpainting.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Yoshua Bengio, Pascal Lamblin, Dan Popovici, and Hugo Larochelle. Greedy layer-wise training of deep networks. In NIPS, pp. 153-160, 2007.
Yoshua Bengio, Nicholas Léonard, and Aaron Courville. Estimating or propagating gradients through stochastic neurons for conditional computation, 2013.
Rahul Bhalley. Sc09 spoken numbers. https://wwws hwwp://p......./raaabbbbaalaaaaa
Bo09-apokest numbers/mmme////// 2018. Accessed: 2021-11-06.
André Biedenkapp and Frank Hutter. Hpbandster. github repository; 2018.
URL
https:
//github. com/ http:///uutmm/HHpaaaaae atttom///aaaaatttrrr [Accessed 05-October 2021].
Eli Bingham, Jonathan P Chen, Martin Jankowiak, Fritz Obermeyer, Neeraj Pradhan, Theofanis Karaletsos, Rohit Singh, Paul Szerlip, Paul Horsfall, and Noah D Goodman. Pyro: Deep Universal Probabilistic Programming. The Journal of Machine Learning Research, 20(1):973-978, 2019.
Manuel Blum, Robert W Floyd. Vaughan Pratt, Ronald L Rivest, and Robert E Tarjan. Time bounds for selection. Journal of computer and system sciences, 7(4):448-44) 1973.
Samuel Bowman, Luke Vilnis, Oriol Vinyals, Andrew M Dai, Rafal Jozefowicz, and Samy Bengio. Generating sentences from a continuous space. In CoNLL, 2016.
Harold Burger, Christian J Schuler, and Stefan Harmeling. Image denoising: Can plain neural networks compete with BM3D? In CVPR, pp.
IEEE, 2012.
Subhajit Chaudhury and Hiya Roy. Can fully convolutional networks perform well for general image restoration problems? In ICMVA, pp. 254-257, 2017.
Rewon Child, Scott Gray, Alec Radford, and Ilya Sutskever. Generating long sequences with sparse transformers. Preprint arXiv: /904. 10509, 2019.
Chris Cremer, Xuechen Li, and David Duvenaud. Inference suboptimality variational autoen- coders. In ICML, pp. 1078-1086, 2018.
B. Dai, Y. Wang. J. Aston, G. Hua, and D. Wipf. Connections with robust PCA and the role of emergent sparsity in variational autoencoder models. JMLR, 19(1)115331614, 2018.
Chris Donahue, Julian McAuley, and Miller Puckette. Adversarial audio synthesis. arXiv preprint arXiv:1802.04208 2018
W. Dong, Wang, W. Yin, G. Shi, F. Wu, and X. Lu. Denoising Prior Driven Deep Neural Network for Image Restoration. TPAMI, 2019.
M. Elad and M.I Aharon. Image Denoising Via Sparse and Redundant Representations Over Learned Dictionaries. IEEE Trans. on Image Processing, 15:3736-3745, 2006.
Yonina C Eldar and Gitta Kutyniok. Compressed sensing: theory and applications. university press, 2012.
Cambridge
Y. Ephraim and D. Malah. Speech enhancement using minimum-mean square error short-time spectral amplitude estimator. IEEE Transactions on Acoustics, Speech, and Signal Processing, 32 16):1109-1121, 1984. doi: 10.1
Jiri Fajtl, Vasileios Argyriou, Dorothy Monekosso, and Paolo Remagnino. Latent bernoulli autoen- coder. In Proc. ICML, pp. 2964-2974, 2020.
Stefan Falkner, Aaron Klein, and Frank Hutter. Bohb: Robust and efficient hyperparameter opti-
mization at scale. In International Conference on Machine Learning, pp. 1437-1446. PMLR, 2018.
Jakob Foerster, Gregory Farquhar, Maruan Al-Shedivat, Tim Rocktäschel, Eric Xing, and Shimon Whiteson. DiCE: The Infinitely Differentiable Monte Carlo Estimator, In International Confer- ence on Machine Learning, pp. 1529-1538. PMLR, 2018.
10

---

Under review as a conference paper at ICLR 2022
P. Földiák. Forming sparse representations by local anti- learning. Biological Cybernetics, 64:165-170, 1990.
Dennis Forster and Jörg Lücke. Can clustering scale sublinearly with its clusters? A variational EM acceleration of GMMs and k-means. In AISTATS, pp. 124 132, 2018.
Timo Gerkmann and Richard C. Hendriks. Unbiased MMSE-Base Noise Power Estimation With Low Complexity and Low Tracking Delay. IEEE Transactions on Audio, Speech, and Language 2012. doi: 10. 119/TTTL.2211.221151..
Processing, 20(4):1383-135
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In AISTATS, pp. 249-256, 2010.
J. Goodfellow, A. Courville, and Y. Bengio. Scaling up spike-and-slab models for unsupervised feature learning. TPAMI, 1528)11902-1114, 2013.
Ian Goodfellow, Aaron C. Courville, and Yoshua Bengio. Large-Scale Feature Learning With Spike- and-Slab Sparse Coding. In ICML, 2012.
Will Grathwohl, Dami Choi, Yuhuai Wu, Geoff Roeder, and David Duvenaud. Backpropagation through the Void: Optimizing control variates for black-box gradient estimation. In International Conference on Learning Representations, 2018.
Shuhang Gu, Lei Zhang, Wangmeng Zuo, and Xiangchu Feng. Weighted Nuclear Norm Minimiza- tion with Application to Image Denoising. In CVPR, pp. 2862-2869. IEEE, 2014.
E. Guiraud, J. Drefs, and J. Lücke. Evolutionary Expectation Maximization. In GECCO, 2018.
M. Haft, R. Hofman, and V. Tresp. Generative binary codes. Formal Pattern Analysis & Applica- lions, 6:269-84, 2004.
M. Henniges, G. Puertas, J. Bornschein, J. Eggert, and J. Lücke, Binary Sparse Coding. In LVA/ICA, pp. 450-57.00 Springer, 2010.
Patrik O. Hoyer. Modeling receptive fields with non-negative sparse coding, Neurocomputing, 52-54:547-52, 2003.
Michael C Hughes and Erik B Sudderth. Fast Learning of Clusters and Topics via Sparse Posteriors. arXiv preprint arXiv:1609.0752) 2016.
Ryuji Imamura, Tatsuki Itasaka, and Masahiro Okuda. Zero-Shot Hyperspectral Image Denoising With Separable Image Prior. In ICCV Workshop. 2019.
Keith Ito and Linda Johnson. The lj speech dataset.
bttps://eeitiito.co
LJ
Speech- 2021. Accessed: 2021-11-06.
Eric Jang. Gumbel-SSoftmxx Gitflub repository, 2016.
URL https://githui. com/
ericjang//umbbll softmax Accessed: 2021-08-03.
Eric Jang, Shixiang Gu, and Ben Poole. Categorical Reparameterization with Gumbel-Softmax, 2016.
Yoon Kim, Sam Wiseman, Andrew Miller, David Sontag, and Alexander Rush. Semi-amortized variational autoencoders. In ICML, pp. 2678-2687, 2018.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 1412.6980, 2014.
Diederik Kingma and Max Welling. Auto-Encoding Variational Bayes. In ICLR, 2014.
Diederík P Kingma, Tim Salimans, Ben Poole, and Jonathan Ho. Variational diffusion models. Preprint 1rXiv:2107.00632 2021.
B Kiran, Dilip Thomas, and Ranjith Parakkal. An overview of deep learning based methods for unsupervised and semi-supervised anomaly detection in videos. Journal of Imaging. 4(2):36, 2018.
11

---

Under review as a conference paper at ICLR 2022
Wouter Kool, Herke van Hoof, and Max Welling. Estimating Gradients for Discrete Random Vari- ables by Sampling without Replacement. In Interaatonaal Conference on Learning Representa- tions, 2020.
Alexander Krull, Tim-Oliver Buchholz, and Florian Jug. Noise2 Learning Denoising from Single Noisy Images. GitHub repository, 2019a. URL
n2v
Accessed: 2020-06-03.
Alexander Krull, Tim-Oliver Buchholz, and Florian Jug. Noise2Void Learning Denoising from Single Noisy Images. In CVPR, pp. 2129-2137, 2019b.
Jaakko Lehtinen, Jacob Munkberg, Jon Hasselgren, Samuli Laine, Tero Karras, Mika Aittala, and Timo Aila. Noise2Noise: Learning image restoration without clean data. In ICML, volume 80,
pp. 296222962722 2018.
Guy Lorberbom, Andreea Gane. Tommi Jaakkola. and Tamir Hazan. Direct optimization through arg max for discrete variational auto-encoder. In NeurIPS, pp. 6203-6214, 2019.
Yang Lu and Philipos C Loizou. A geometric approach to spectral subtraction. Speech Communi- cation, 50(6)4453-466 2008.
James Lucas, George Tucker, Roger B Grosse, and Mohammad Norouzi. Don't Blame the ELBO! A Linear VAE Perspective on Posterior Collapse. NeurIPS, pp. 9408-9418, 2019.
Lücke and M. Sahani. Maximal causes for non-linear component extraction. JMIR, 9:1227-67, 2008.
Jörg Llice.. Truncated Variational Expectation Maximization. arXiv preprint, arXiv: 1:10v:161..03113. 2019.
Jörg Lücke and Dennis Forster. k-means as a variational EM approximation of Gaussian mixture models. Pattern Recognition Letters, 15:339-3566 2019.
Jörg Lücke, Zhenwen Dai, and Georgios Exarchakis. Truncated Variational Sampling for "Black Box" Optimization of Generative Models. In LVA/ICA pp. 467-478, 2018
Lars Maalge, Casper Kaae Sønderby, Spren Kaae Sønderby, and Ole Winther. Auxiliary deep gen- erative models. In ICML. 2016, 2016
Chris Maddison, Andriy Mnih, and Yee Whye Teh. The concrete distribution: A continuous relaxation of discrete random variables. arXiv preprint 1eXiv:6611.007111 2016.
Xiaojiao Mao, Chunhua Shen, and Yu-Bin Yang. Image Restoration Using Very Deep Convolutional Encoder-Decoder Networks with Symmetric Skip Connections. In NIPS, pp. 2802-2810, 10, 2016.
D. Martin, C. Fowlkes, D. Tal, and Malik. A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics. In ICCV, volume 2, pp. 416-423, 2001.
Michael Michelashvili and Lior Wolf. Speech Denoising by Accumulating Ver-Frequency Modeling Fluctuations. arXiv preprint arXiv: /904.06/00077 2020.
Vivek Sivaraman Narayanaswamy, Jayaraman J. Thiagarajan, and Andreas Spanias. On the Design of Deep Priors for Unsupervised Audio Restoration GilHlub repository, 2021a. URL https:
7/github. www httttutb.ccm....ssssvvaaaaaaeeee
Accessed: 2021-10-27.
Vivek Sivaraman Narayanaswamy, Jayaraman J. Thiagarajan, and Andreas Spanias. On the Design of Deep Priors for Unsupervised Audio Restoration. In Proc. Interspeech 2021, pp. 2167-2171,
2021b. doi: 00214437/meexpeech222---- 1890.
Fernando M. F. Nogueira. Bayesian optimization package.
git com/ fmfn//
BayesianOpt imi zationn 2019.
B. Olshausen and D. Field. Emergence of simple-cell receptive field properties by learning a sparse code for natural images. Nature, 381:607-9, 1996.
12

---

Under review as a conference paper at ICLR 2022
Dylan M Paiton, Charles G Frye, Sheng Y Lundquist, Joel D Bowen, Ryan Zarcone, and Bruno A Olshausen. Selectivity and robustness of sparse coding networks. Journal of Vision, 20(12): 10-10, 2020.
Vardan Papyan, Yaniv Romano, Jeremias Sulam, and Michael Elad. Convolutional dictionary learn- ing via local processing. In ICCV, pp. 5296-5304, 2017.
Yookoon Park, Chris Kim, and Gunhee Kim. Variational Laplace autoencoders. In Proc. ICML, pp- 5032-5041, 2019a.
Yookoon Park, Chris Dongjoo Kim, and Gunhee Kim. Variational Laplace Autoencoders GitHub repository, 2019b. Utthttps: //tttppp:///thbb... http://ttttt.ooooaaaatoettteettt wwwm/yookoo///ooooooooooooooooot VLLAE Accessed: 2021-08-
Max Paulus, Chris Maddison, and Andreas Krause. Rao-Blackwellizing the Straght-Thhrough Gumbel-Softmar Gradient Estimator. In International Conference on Learning Representations, 2021.
Andres Potapczynski, Gabriel Loaiza-Ganem, and John P Cunningham. Invertible Gaussian Repa- rameterization: Revisiting the Summee-Softtax. In Advances in Neural Information Processing Systems, volume 33, pp. 12311-12321, 2020.
Mangal Prakash, Alexander Krull, and Florian Jug. Fully unsupervised diversity denoising with convolutional variational autoencoders. In 9th International Conference on Learning Repre- sentations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.ner, 2021. URL
https://cpenrevie/ net wwt./eeeeetteeeeeeeeeeeeeee
Danilo Jimenez Rezende, Shakir Mohamed, and Daan Wierstra. Stochastic backpropagation and approximate inference deep generative models. ICML proceedings, 2014.
Adam Roberts, Jesse Engel, Colin Raffel, Curtis Hawthorne, and Douglas Eck. A hierarchical latent vector model for learning long-term structure in music, 2018.
Jason Tyler Rolfe. Discrete variational autoencoders. arXiv preprint arXiv:1609.02200 2016.
Aurko Roy, Ashish Vaswani, Arvind Neelakantan, and Niki Parmar. Theory and experiments on vector quantized autoencoders. arXiv preprint arXiv: 1805. 1063,, 2018.
John Schulman, Nicolas Heess, Theophane Weber, and Pieter Abbeel. Gradient Estimation Using Stochastic Computation Graphs. In Proceedings of the 28th International Conference on Neural Information Processing Costems-Volumme pp. 3528 3536, 2015.
A.-S. Sheikh and J. Lücke. Select-and-Sample for Spike-and-Slab Sparse Coding. In NIPS, 2016.
Abdul-Saboor Sheikh, Jacquelyn A. Shelton, and Jörg Lücke.. A Truncated EM Approach for Spike- and-Slab Sparse Coding. JMLR, 15:2653-2687, 2014.
J. Shelton, J. Bornschein, A.-S. Sheikh, P. Berkes, and Lücke. Select and Sample A Model of Efficient Neural Inference and Learning. NIPS, pp. 2618-26, 2011.
Assaf Shocher, Nadav Cohen, and Michal Irani. "Zero-Shot" Super-Resolution using Deep Internal Learning. CVPR, pp. 18-331.. IEEE, 2018.
Leslie N Smith. Cyclical learning rates for training neural networks. In WACV 2017, pp. 464-472. IEEE, 2017.
Jeremias Sulam. Ramchandran Muthukumar, and Raman Arora. Adversarial robustness of super- vised sparse coding. Proc. NeurIPS, 2020.
Michalis K. Titsias and Miguel Lázaro-Gredilla. Spike and Slab Variational Inference for Multi-Task and Multiple Kernel Learning. In NIPS, 2011.
Jakub M. Tomczak and Max Welling. VAE with a VampPrior. arXiv preprint 1r05v:1705.07.0 2018.
13

---

Under review as a conference paper at ICLR 2022
Francesco Tonolini, Bjöm Sand Jensen, and Roderick Murray-Smith. Variational sparse coding. In Proc. UAI, pp. 690-700, 2020.
Dmitry Ulyanov, Andrea Vedaldi, and Victor Lempitsky. Deep image prior. In CVPR, pp. 9446- 9454, 2018.
Aaron van den Oord, Oriol Vinyals, et Neural discrete representation learning. In NeurlPS, pp- 6306-6315,20 2017.
J. H. van Hateren and A. van der Schaaf. Independent component filters of natural images compared with simple cells primary visual cortex. Proc. R. Soc. London. B, 265:359-666 1998.
Emile van Krieken, Jakub M Tomezak, and Annette ten Teije. Storchastic: A Framework for General Stochastic Automatic Differentiation. arXiv preprint arXiv:2104.00428, 2021.
Pete Warden. Speech commands: dataset for limited-vocabulary speech recognition. arXiv preprint arXiv: 2018.
Guoshen Yu, Guillermo Sapiro, and Stéphane Mallat. Solving Inverse Problems With Piecewise
Linear Estimators: From Gaussian Mixture Models to Structured Sparsity, IEEE Transactions on Image Processing, 21(5):2481-244 2012.
Kai Zhang, Wangmeng Zuo, Yunjin Chen, Deyu Meng, and Lei Zhang. Beyond Gaussian De- noiser: Residual Learning of Deep CNN for Image Denoising. IEEE Transactions on Image Processing, 2677):31 2017.
Kai Zhang, Wangmeng Zuo, and Lei Zhang. FFDNet: Toward a fast and flexible solution for CNN based image denoising. IEEE Transactions on Image Processing, 2018.
Zhoutong Zhang, Yunyun Wang, Chuang Gan, Jiajun Wu, Joshua B Tenenbaum, Antonio Torralba, and William T Freeman. Deep Audio Priors Emerge from Harmonic Convolutional Networks. In International Conference Learning Representations, 2020.
Dihan Zheng, Sia Huat Tan, Xiaowen Zhang, Zuoqiang Shi, Kaisheng Ma, and Chenglong Bao. An unsupervised deep learning approach for real-world image denoising. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. URLAttps://opeezeviee.
Mingyuan Zhou, Haojun Chen, John Paisley, Lu Ren, Lingbo Li, Zhengming Xing, David Dunson, Guillermo Sapiro, and Lawrence Carin. Nonparametrie Bayesian Dictionary Learning for Anal- ysis of Noisy and Incomplete Images. IEEE Transactions on Image Processing, 21(1):130-144, 2012.
Shipeng Zhu, Guili Xu, Yuehua Cheng, Xiaodong Han, and Zhengsheng Wang. BDGAN: Image Blind Denoising Using Generative Adversarial Networks. In PRCV, pp. 241-252, 2019.
Daniel Zoran and Yair Weiss. From Learning Models of Natural Image Patches Whole Image Restoration. In ICCV, pp. 479-486, 2011.
14

---

Under review as a conference paper at ICLR 2022
Supplementary Material
A DETAILS OF ENCODER AND DECODER OPTIMIZATION
General Decoding Model
Standard Decoding Model
Binary Docoding Model
f ~ pa (z)
I~N (20,1)
E Bern (2, at)
x
θ
W2
W.o²
I~ pe (I 2)
N~N (d)
H~ (2; o
N
N
N
Figure 6: Generic and general VAE decoding model (left), VAE model with standard continuous latents (center), and the VAE model with binary latents (right) of Eqn. ( (right).
See Fig. 6 for a graphical comparison between the decoding models of a vanilla VAE and the binary VAE considered here (I] Fig. 7 graphically illustrates different steps optimize standard VAEs, and additional steps suggested by different contributions in order to optimize discrete VAEs.
For the optimization of the binary VAE (T. consider the original form of the lower bound, Eqn. ( When taking derivatives of F(Ø, Q) w.r.t. θ we can ignore the entropy temm!" ! For the binary VAE
model of Eqn. ① the gradient of the lower bound w.r.t. W then given by:
F(2,0)
Σ
w
E (m)
log (pe (7)) (m) pe)
Σ
W
log (pes (o (M) |
(n)
Σ
V
E
log (N
;(, ofli]]
l (") |i(mm -A W)ll
20
W
(E
Σ
d
(n)
V
(m) (m)
مT wi1l
(11)
20
(e
where, by using and 11. the weighting factors ( (2) are given by:
pe(# (n) 2) pe (2)
(1)
[
Σ Egrepio) pe ( (n)
2') (e("")
exp (- 2 [[
M[ W TTz)
(12)
Σ exp
| (= W)ll TT
(N))(n)
for all & E o. (*) where म. = log (L=m)). Note that the q4 (2) are evaluated at the current values of the parameters O they are therefore treated as constant, e.g., for the gradient w.r.t. W.
It may be interesting to compare the gradient estimate (1]) the gradient estimate of conventional VAE training. For this consider a standard encoder given by an amortized variational distribution
For our choice of variational distributions. it is not trivial that the entropy term actually can be ignored because the encnding model qa 4') in 4 is defined in terms of the decoding model and its parameters. For truncated distributions, however, it can be shown that the entropy term still be ignored (Lācke 2019).
15

---

Under review as a conference paper at ICLR 2022
which we shall denote by lo (3). The distribution /6 (z) could be a Gaussian whose mean and
a(") variance are set by passing data point (x)) through encoder DNNs. For discrete VAEs, l4 (2) can be thought of as an analog discrete distribution. If we now take gradients of w.r.t. W and estimate
using samples from a(m)( (2), we obtain the familiar form:
Vw.F(O, 0)
Σ V W
(()) log 1 pe)
V W E (i))
log (N(T [i(2, W), o o
V - w)
20
m=1
where glm)
((n) 20 (2). We can slightly rewrite this expression to obtain:
- Σ3
VwIE
#(Z w)ll"
(13)
20
M
Em ())
If we now compare with the gradient using the truncated approximation (") (2),
1 Σ Σ W F(B.0) = 20
44 (2)
1
(14)
one can discuss analogous roles played by the subsets T (m) (the variational parameters of dΦ
(1))
(=))
and by a standard encoder %% The states in a subset & are used to estimate the gradient similar to the samples from a standard encoder of*) (z). The size of + (") can consequently be thought of as analog to the number of samples used in a conventional estimation of the gradient. Standard VAE training estimates the gradient by weighting all samples equally (with (1/M)) and the gradient di-
rection is approximated using sufficiently many samples drawn from the current (x) (E). In contrast,
truncated gradient estimation uses the states in t (") and the gradient is computed using a weighted summation with weights qi.
(n) (2). These weights are computed by passing the states E through the decoder network. The gradient is then, notably, not a stochastic estimation but exact: gradient ascent is guaranteed (for small steps) always monotonically increase the variational lower bound.
Computational Complexity. To add to the discussion of computational complexity of TVAE com- pared to standard VAE training, consider again Eqns. [ and [4] If as many samples M are used, per data point, as there are states in each & (n) then both sums have the same number of summands. The evaluation of the gradients of the mean square error (MSE) is consequently precisely the same for both approaches. The additional weighting factors 1o (")( (#) have to be computed for TVAE. However, the weighting factors just represent a small overhead because the evaluation of the decoder DNN for the states in 4" (n) is a computation that can be reused from the updates of 4" (n)
The main computational differences are in the updates of "") compared to the update of encoder DNNs for conventional VAEs. Once the parameters θ (W, .f) are updated using (14). new states for T (x) have to be sought based on criterion 7 In practice and for each n, we generate M' new states according the applied evolutionary procedure. To select the best states have to pass all these M' new states through the decoder DNN to evaluate (7). Furthermore, we have to pass all M states already in x (n) through the DNN to re-evaluate (7) because the parameters θ have changed. In summary, we do require O(N x (M + M')) passes through the decoder DNN. Selecting the M best states from the (M M') states does not add complexity this can be done in (M + M') for each (Blum et al. 1973). The EA does add to the computational load but parent selection and mutation only add a constant offset for each of the considered states.
For comparison with standard VAEs, if we use M samples of an encoder g((") (ž), we require O(M x N) passes through the decoder DNN to update the parameters θ according to (13). For the encoder update requires N M passes through encoder and decoder DNN estimate the gradient
16

---

Under review as a conference paper at ICLR 2022
Additional methods used for VAEs with discrete latents
Direct Discrete Optimization
Standard
Optimization lower bound Instead of liceihhood
Ostimization of Instean likellhood
Introduce smoothing continuous latents (Reife, 2017!
Use suitable posterior approximation
or
lske truncated posterie" approxumetion
Add vector oLantization stop, commitment loss Ray al., 2018)
Reparameterize
Use compact lower
posterior obtain low variance estimates for the gradier objectlve wit., postarior parameters
Use GMM--lke prior preudk-inpuuts TTemzzak Weiling, 2018: tonolini el., 2020)
Use effiient discrete optimization maximize olojective parameters
DNNs posterior nor nor-iieerities
Apply Gumbel Max reperameterizatioon and direct loss minimization (Lorterrbom (2019)
Lse stochastle gradient escent to sptimine objective posterior porameters
Soften discrete distributions, recover them annealing ng mit Ujnn al., 2017)
Figure 7: Typical collection of methods used to optimize the encoding model of VAEs. Left: Meth- ods of the standard procedure to optimize VAEs. Middle: Examples of additional methods applied to maintain the standard VAE procedure also for VAEs with discrete latent variables. Right: Alter- native direct discrete optimization of VAE encoding models.
w.r.t. the encoder weights (if we draw M samples for each data point from conventional encoder distribution (())) (z). The additional overhead to actually draw the samples is usually negligible.
Hence, the computational complexity of TVAE training is comparable if M = M' z M. However, conventional VAE training is amortized, i.e., the update of encoder weights uses information from all data points n. contrast, TVAE training is not amortized, i.e., the are updated per data point. The advantage of amortization is that in practice, weights of conventional encoder converge faster or (alternatively) less samples M are required. Considering the observed runtimes, more efficient conventional VAE training can presumably in large parts attributed to faster convergence using amortization. Furthermore, the used number of samples M for conventional VAE training is
(*)
usually smaller than best working sizes of (") (we used, e.g., |$ ["] E [20, 200] for denoising.
see Tab. and the required storage of &
(n) results in overhead computations. On the other hand, amortization also has disadvantages (e.g. Kim et al. 2018 Cremer et al. 2018). The competitive
performance for denoising may consequently be attributed at least in part to T not being subject to an amortization gap.
A.I EVOLUTIONARY ALGORITHMS
We base the fitness function on the joint (T Z) that follows from ( Concretely we employ the reformulation (7). which allows for robust computation, and we use an offset (constant w.r.t. ž) to ensure that fitness values strictly non-negative. We investigated different selection operators: (i) uniform random selection procedure that is independent of the parents' fitness, and (ii) a procedure in which parents selected with probability proportional to their fitness. After selection, the
17

---

Under review as a conference paper at ICLR 2022
children states of a new generation are manipulated through mutation (and possibly crossover). The mutation operator flips one bit per child; the index of the bit to flip is uniformly randomized. To apply crossover. children states are paired in any possible way, and the tails of the states in each pair are swapped; the single crossover point is uniformly randomized.
In large scale numerical experiments, we used cimmess-popoortional parent selection in combi- nation with uniformly random bitflips, as we found this operator combination to efficiently and
effectively suggest new states guew for the optimization of the subsets & (*) based on criterion (8) (cf. Fig. IT). We refer to this evolutionary operator design as imparents-randflinn designs we considered are termed accordingly (i.e., cates uniformly random parent selection, application of crossover and uniformly random bitflips; compare Fig. [T]. Hyperparameters of the evolutionary algorithms are N, (denoting the number of
other operator for instance, indi-
parental states selected per generation; N₂ S 1 (") D. Ne (denoting the number of children evolved per parent), and N2 (denoting the number of generations evolved). When erossover employed, the total number of new states evolved per data point per epoch is given by (Np 1).N otherwise it NoNg The concrete hyperparameters used in the numerical experiments are listed in Tab.[T
B DETAILS ON THE NUMERICAL EXPERIMENTS
B.1 HYPERPARAMETERS
For all numerical experiments, DNN training using 9 was performed with mini-batches, the Adam optimizer (Kingma & Ba 2014) and decaying cyclical learning rate scheduling (Smith) 2017).
Xavier/Glorot initialization (Glorot & Bengio 2010) was used for the DNN weights, while biases were always vero-initialized. Parameters म and o² were updated via Equ. 10).. म was initialized to ". o² was initialized to 0.01 with the exception of the Barbara, CIFAR- TO and Audio datasets
(Figs. 15 and 16) for which we initialized o² with the data variance. The s" (") were initialized by drawing- E from a Bernoulli distribution with p(=a. 1) 77 Hyperparameter optimization was conducted manually, and for the more complex datasets, it also made use of black box Bayesian optimization based on Gaussian Processes (Nogueira 2019) and BOHB (Falkner et al., 2018) us- ing the hphandster framework (Biedenkapp & Hutter 2018). Tab. provides an overview of the hyperparameters used in each of the reported experiments.
B.2 VERIFICATION EXPERIMENTS
We first evaluated T'AE training on artificial datasets with known ground-truth parameters and log- likelihood, in order verify the correct functioning of the algorithm and investigate possible local optima effects. The dataset consisted of 500 4x4 images generated by linear superposition of vertical and horizontal bars (compare, e.g. Földiák 1990 Hoyer 2003; Guiraud al. 2018), with small amount of Gaussian noise. The DNN's input and middle layers had 8 units each. The (()) variational sets consisted of 64 hidden states each. Fig. shows the evolution of the run that achieved the highest EL value out of ten. All parameters were correctly recovered, and the ELBO value was consistent with actual ground-truth log- likeeiiodoood
Such an elementary test, however, can also be solved by linear models. In order to demonstrate that TVAEs can solve non-linear problems, taking advantage of the neural network non-linearity embedded in the generative model, we introduced correlations between pairs of bars: the bars com- binations shown in the first two data points from the left in Fig. were discouraged from appearing together. Again we selected the run with highest peak ELBO value out of ten. The model correctly learns that certain combinations of bars are much more unlikely than others, and correctly estimates their likelihood.
Fig. 10 some more insight into the correlated bars test experiment described. The left section of the figure shows the generative parameters for the dataset used: W, is the 8x8 weight matrix the top-to-middle layer: this makes it so that the activation of the first latent variable inhibits activation of the second, and activation of the last latent variable inhibits activation of the last. Concretely, this results in a dataset where these specific bars combinations are discouraged from appearing. The weights Wi, visualized as 8 4x4 matrices, generate the actual bars. o² was set to 0.01 and the dataset contained average of two superimposing bars per data point (I 2/8 for each h). The middle
18

---

Under review as a conference paper at ICLR 2022
Table Hyperparameters used in the numerical experiments. The architecture the decoding DNN is listed as Ho-H1-...-D with Hy and D indicating the number of Bernoulli latents and Gaussian observables respectively, and Hı-... denoting the number of hidden layer units. By default, we used ReI.U activations in the hidden layers and a linear output layer. For Barbara and CIFAR-10, we used LeakyReI.U instead ReL.U; for CIFAR-10, we additionally used a Sigmoid the output layer. Min and max Lr. denote lower and upper learning rate boundaries and are, together with Epochs/Cycle, hyperparameters of the cyclical learning rate scheduler (cf. Smith 2017). [4(n) denotes the number of distinct latents per data point (referred as S Alg. I). and refer the parameters used for {15, ) and 50 in Fig. E respectively.
Decoding Model
Encoding Model
He Me-BBe...-D
Min
Epuchs/Cycll
Batch
[3
fi--andilip (N,
N,
Bars (Figs 9 110
8-8-16
0.0001
0.1
50
32
2/6
onnct E-step
Bus (1%g
6-8-9
0.0001
0.05
20
32
32
rasudom sumpling (N
R6
Bass
fitmandtiip
5.
N,
Bass (Fig
18
6-8-9
0,0001
0.05
20
32
32
rand rand-randfip L..
0,
Bass (Fig
11
6.8-9
0.0001
0.05
20
32
32
Et cross randhip
(N₂
= N. 1)
Bass (Fig
6-3-9
0,0001
0.05
20
32
32
rand-cross candisi p (A,
-i.
(Fig
samplling
Bass (Fig
18
8-8-16
0,0001
0.03
20
32
64
fit-andilip (N
5.
N.N.44 N,
Bass (Fig
8-8-16
0,0001
D.05
20
32
64
rand-ondttip (V
-
N. N. N, -1]
Bars (Fig
8-8-16
0,0001
0.05
20
32
64
fi-cmees-ramlling
(N,
55,
Bars
8-8-16
0.0001
32
64
radd-omss-nnttll
13
500-300-256
fi-mndilip
N. 7.
House (Figg
64-64-64
0,0001
0.01
20
32
200
lit-nddlipp (N, N.
House (Fig
512 512-512-144
0.0001
0.05
20
32
64
fit-zandlip (N, =S.N.
Barhara
50-500-500-64
0.0001
0.001
160
512
100
fit-andfiip
L.N.
House 50 (Figg)
512-512-144
0.0001
0,01
20
32
64
fitranddlip (22 L.
Casrle-50 (Fig
512-312-25
0.0001
0.00125
20
32
32
fi-nndflip (A -,
Castle 50 (Pig
512-512-144
0,0001
0.001
20
32
64
fitrandfiip CN, 2.N.
CIFAR- 10 (Pi
32-512-3072
0,0004
0.009
160
128
20
fitrandflip -15.N.-10.33
CIFAR-10
50-5001-500-900
0.004
0.009
20
fi--ndflip (A, N.
CIFAR-10 (Pig
1024-256-512-8077
0.009
(N,
CIARR 1b
1024-512-0072
0.0004
0.009
160
128
20
fitrandlip (N -.1.N N.- 1,
Audia (Fig
200-512-400
0.001
0.001
160
512
20
Mi-nndllp -18 N,
Epoch
One-hot
Jog (e)) (o
1.2
graadd truth
10
65
25
084
50
15
log
Ground truth
Figure 8: TVAE Training Simple Bars Data: Noiseless Output of the TVAE's DNN for the 8 Possible One-hot Input Vectors Over Several Training Epochs. Generating parameters are the last row.
Figure Correlated Bars Test. The plot shows the ratio between inferred and ground-truth log- likelihoods log (z)) of data points with inter- esting bar combinations. The inferred values are reported below the data points themselves.
19

---

Under review as a conference paper at ICLR 2022
section of the figure shows the ELBO values (averages over all batches for each epoch) as training progresses. The cyclic learning rate schedule is responsible for the oscillatory behavior. The right section shows some example data points together with samples from the trained TVAE model that reached the highest ELBO value out of the ten runs.
Groud-truth (8x8)
ELBO epochs
Excmmple datapolnts
Ground-truth (8x16 showed as 8odx44
Trained TVAE sumples
-15
55
15
Figure 10: Generative Parameters for the Correlated Bars Test (left); ELBO Values over Epochs for 10 runs (center); Example Datapoints and Samples from the Generative Model (right).
Using bars test data generated with linear model (no correlations between pairs of bars) as de- scribed above, Fig. depeppscs reliabilities of different evolutionary operator designs (also compare A.p.A..I.
B.3 SCALABILITY EXPERIMENTS
The N = 100, 000 image patches of size D 16 x 16 for the scalability experiments were ex- tracted from a standard image database (van Hateren van der Schaaf 1998) and pre-processed as in Guiraud et al. 2018). The most elementary VAEs use linear mapping for the decoder Øá(z, W). While being a natural baseline, such VAEs have also played a role in understanding important prop- erties of VAE learning (e.g. Dai et al. 2018 Lucas et al. 2019). For standard Gaussian latents, a linear VAE can be shown to recover probabilistic PCA solutions. For Bernoulli latents, we can recover binary sparse coding (Haft et al. 2004 (hhelton et al.] (011)) in case of linear decoders. 300 latents) with a linear VAE. After 100 epochs the weights of the linear mapping were used to initialize the bottom layer of deeper decoder network with three layers of 300, 300 and 16 x 16 = 256 units, respectively. The weights of the deeper layers were simply initialized to the identity matrix. Furthermore, prior and variance were optimized. The setup just described guarantees a common starting point for linear and non-linear VAEs such that the difference provided by deeper decoder DNNs can be highlighted. Fig. shows the variational bounds during learning of the linear VAE compared to the non-linear VAE for a typical experiment.
We therefore began our analysis (using
The non-linear VAE can be observed to quickly and significantly optimize the lower bound beyond a linear VAE. In proceeding experiments (when we are not concerned with comparisons to linear VAEs) we simply optimized the weights of the non- non-linear TVAE directly as we did not observe an advantage in first optimizing linear VAE.
Regarding scalability, we observed similar efficiency of non-lincar TVAE compared to linear mod- els described in the main text. To further investigate scalability, went to TVAEs with up H=1000 latent variables (while using 100 units in the DNN middle layer). TVAE training time remained in line with the theoretical linear scaling with H while the variational bound further in- creased.
B.4 IMAGE DENOISING
Data Estimator: Given a trained TVAE with parameters θ, we estimated the value of a pixel in
single patch ea (pa(E)))) [.a]. When using pe (xia z) E E(3) pe T)pe( (z T) obtain:
rdd = Eps (aul [ma] = Em [Ha(2]]
(15)
The expectation value on the right- -ind-- of Eqn. (15) is then approximated based on the encod- ing parameters t. (n)
using truncated posteriors. Finally, we took weighted average of the estimates
20

---

Under review as a conference paper at ICLR 2022
H = 6
H = 8
0
*FF(C, () - L((Rm)
-2
-5-
-4
-10
-15-
-8-
20
-10
random
ritparents-randffiis
randparents-randdiin
random
fitparents-randfiig
randparents-randfips
Figure 11: Reliability of different evolutionary operator combinations (cf. App on bars test (see B.2 for details). Reliability quantified in terms of the normalized difference between the lower bound at the last training epoch and the log-likelihood computed using the ground-truth generating parameters. For the strategy labeled as 'random', we randomly sampled states from Bernoulli distribution with p(zA- = 1) H
40
linear binary VAE
20
TVAE starting from linear mapping
20
-40
600
-80
175
epoch
Figure 12: ELBO Gain of TVAE Compared to Linear VAE with Binary Latents (on 16 16 image patches).
21

---

Under review as a conference paper at ICLR 2022
of a pixel value in different patches (see, e.g.. Burger et al. 2012) in order to generate the pixel values of the full denoised image.
Performance Comparison Under Controlled Conditions. To evaluate the performance on standard denoising benchmarks, we first compared TVAE to related probabilistic sparse coding approaches such as MTMKL,, GSC and var-BSC (Fig. D). MTMKL and GSC use the data model of spike- and-slab sparse coding and for training mean-field field and truncated posterior approximations with pre- selection are used, respectively. Compared to MTMKL and GSC, var-BSC uses a less complex data model and a training scheme also based on evolutionary optimization (Guiraud et al. 2018). The denoising performance observed in the scenario with controlled conditions (Fig. 3D shows that for high noise level (o = 50), var- BSC achieves higher PSNR values than MTMKL and GSC although the method uses simpler data model. This observation demonstrates the effectiveness of the evolu- tionary training method used by var-BSC. However, PSNR values for TVAE are significantly higher due to the higher flexibility in modeling the data distribution provided by the used DNN.
Performance Comparison Under Uncontrolled Conditions. In a second step, Fig.Bl compared the performance of TVAE with respect to different denoising approaches including deterministic sparse coding (KSVD), a mixture model approach (EPLL), a non-local image processing method (WNNM) and state-of-the-arr denoising methods based on deep neural networks (BDGAN and DPDNN). These approaches can be distinguished. e.g., by the amount of employed training data and by the requirement for clean data. TVAE as well as MTMKL,, GSC and var-BSC do not re- quire clean images for training. Furthermore, all these approaches noisy image is available ('zero-shot' learning; compare, e.g., SShocher et al.) 20188] Imamura et al.) 2019). Instead, EPLL, BDGAN and DPDNN use clean training data (typically tens or hundreds of thousands of data points are collected for training).
be trained if only the single
Approaches such as noise2noise (n2nnnehnnnen et al.) 2018 and noise2void (n2v Krull et al. 2019b) occupy middle ground: they can be trained on noisy data but they typically require much larger amounts of data than, e.g., TVAE or MTMKL. In the original n2v publication. for instance, 400 (noisy) 180 x 180 BSD (Martin et al., 2001) images were used to create training dataset (this procedure also involved data augmentation; compare Krull et al. 2019b). For our comparison with results of FE, we used the standard, publicly available code for n2v (Krull et al. 2019a) to- gether with the default training set (a = 25) employed in the original n2v publication (specifically, followed the 'denoising2D BSD668' example from the corresponding GitHub repository). We then applied the trained n2v network to denoise the 'house' image with o = 25. The resulting PSNR value was 32. B which is 0.76d lower than the PSNR value for BM3D (3..86d The difference is consistent with an on average 0 lower performance of n2v compared to BM3D) on the BSD68 test set (see Krull et al. 2019b). The same network can also be used to denoise an image with lower or higher noise level. The n2v network trained on = 25 does, for instance, re- sult in PSNR values of 32.93d. for the 'house' image with a 15 and in 20.96dI3 for the 'house' image with o = 50 (see n2ut in T)b.2). Especially for high noise levels performance can be much improved, however, if the n2v network trained using images with the same noise level as the test image. In order to do so, we followed the procedure described in the n2v publication while adapting the noise level of a = 15 one case and a = 50 for the other case (as described above, we used the "denoising2D_BSS _BSS668' example as reference implementation). Trained on a dataset with matched noise, we then denoised the 'house' image with a = 15 in the one, and a = 50 in the other case (results listed as n2v* in Tab The PSNR values obtained for 'house" in this matched-noise-leved scenario are much higher compared to the scenario with unmatched noise level (e.g., for o = 50 the PSNR improvement is approximately 8 dB). The much lower performance for mismatched noise for n2v is in this respect consistent with observations for standard DNN denoising for which training with the ground-truth noise level has been pointed out as important for performance (Chaudhury & Roy 2017: Zhang et al. 2018).
(n2v/Krull
The n2v approach can avoid having to know the exact noise level, e.g., e. it trained on just the single noisy image. In a last experiment, we hence investigated this 'zero-shot" denoising feature of n2v and applied the algorithm to denoise the 'house' image while using the same noisy image for training that we seek to denoise (again, our implementation was based on the n2v "denoising2D.BSSS BSD68 example, see above). The obtained PSNR values are listed as n2v" in Tab.
From Tab.Zii it can be observed, that for all considered training settings of n2v and all noise levels, PSNR values of TVAE are consistently higher than those of n2v even if n2v is trained on external
22

---

Under review as a conference paper at ICLR 2022
Table 2: Denoising Performance of n2v in PSNR (dB) for the 'House' Image. For comparison, additionally list the performance of TVAE (numbers copied from Fig. Fi.. PSNR values for n2v* are obtained by training only on the noisy image (i.e., in the same setting as used for MTMKL, GSC, var-BSC and TVAE in Fig. E). More training data improves performance for n2v. PSNR values for n2vf show performance if additional training data in the form of noisy images with AWG noise = 25 is used. Further improvements (especially for high noise) are obtained if the n2v network is trained on training data with a noise level that matches the noise of the test set (see n2v²). For instance, we used for n2v+ training data with values were computed using the model in its state at the training epoch with smallest validation loss; for n2v*, performed three independent runs of the algorithm and here report the results of the best run (in terms of validation loss). See text for further details.
50 to denoise the 'house' with
50. PSNR
o=15
o=25
o=50
n2v*
32.22
29.69
24.89
n2y!
32.93
32.10
20.96
n2vt
33.91
32.10
28.94
TVAE
34.27 + .02
32.65 + .06
29.98 + .05
data with matched-noise level. Additional parameter tuning may improve performance of n2v" to a certain extent but PSNRs are in general much lower than n2vf, While we followed for n2vF the standard hyperparameter setting of the original paper/code publication of n2v (Krull et al.] 2019b a), cannot exclude further improvements with parameter fine tuning for the "house' benchmark. However, we remark that the difference of n2vF and BM3D for the 'house' benchmark is on the very same range as the differences between n2v and BM3D as reported on the BSD data set in the original n2v publication. The stronger performing BM3D is according to denoising performance the preferable comparison and as such included in FIg. In terms of efficiency, the n2v approach is in general (once trained) faster than BM3D as well as TVAE, however.
PSNR values of noise2noise (n2n) are usually very closely aligned with PSNR values achievable by feed-forward DNNs. More concretely, n2n uses, for instance, RED30 network (Mao et al.) (016)) which achieves 31.07 dB PSNR on the BSD300 data set if trained on clean data. If directly trained on noisy data, RED30 achieves 31.06 dB (Lehtinen et al., 2018). n2n is thus strongly performing in terms of PSNR. The caveat of n2n compared to n2v is, however, that the noisy data n2n uses is rather artificial. The pairs of images n2n is trained consist of two different noise realization of the same underlying clean image. For real data, such a setting is only approximately occurring at most, which has motivated the n2v approach.
Like n2v, BDGAN and DPDNN are optimized for specific noise levels (specific standard deviations used to generate the noisy training examples). EPLL is trained exclusively clean image patches; for denoising, the algorithm requires the ground-truth noise level of the test image as input parameter. Ground-truth noise level information is also required by KSVD and WNNM.
Like all approaches in the top category of Fig. 3. TVAE does not require ground-truth noise level information, nor clean images, nor large amounts of training data. For the 'zero-shot' setting, TVAE is consequently the best performing system on the 'house" benchmark. Such a high performance is notably achieved using basic DNN and relatively small patch sizes of D = 8 (for a 15 and a = 25) or D = 12 x 12 (for o 50). All feed-forward DNNs for denoising use much larger patches (e.g., n2v use 64 64). That competitive denoising performance can be achieved for small patches, in general, argues in favor for VAE approaches to denoising. Indeed, TVAE even comes close to state-of-the-art approaches (BDGAN and DPDNN) that use very intricate DNN architectures and large amounts of clean training data. We believe that such results underline the potential of the here investigated approach although the novelty of the approach is the focus rather than extensive benchmarking.
Comparison to Deep Generative Models. While denoising is. in general, well suited for deep generative models, performance for standard image denoising is not common such results for standard DNNs (which may also be related to efficiency aspects). Exceptions include the recent BDGAN Zhhu et al. 2019) and the very recent DivNoising (Prakash al. 2021) and NN+X (Zheng
23

---

Under review as a conference paper at ICLR 2022
et al.
2021) approach. Regarding VAEs, we here compared TVAE to GSVAE (Jng et al. 2016
and
VLAE PPak et al. 2019a) using publicly available source code of these models (Jang 2016)
and
Park al. (2019b), respectively). For GSVAE, we implemented continuous latents, L..
used a Gaussian distribution over the observables (rather than a Bernoulli as implemented in the public source code). For both GSVAE and VLAE, used the same hyperparameters
in the respective publicly available implementations. To apply both models for denoising, we used the same patch-based processing as employed for TVAE (compare Data Estimator paragraph above). The PSNRs listed in Fig. [3] were obtained using patch sizes of 12 x 12 and 8 x 8 for GSVAE and VLAE, respectively, and they were measured at the training epoch with the highest lower bound.
Computational Demand. An important limitation of TVAE is its computational demand. For our experiments on the 'house' image with noise level / = in Fig. we used N 60025 patches of D = 12 x 12 pixels, which amounts to all possible non-overlapping square patches of that size that can be extracted from the image. For training and denoising we used a TVAE with H = 512
latent variables, sizes of [ " = 64, and 512 units in the DNN middle layer of the decoder. TVAE training required 49 seconds per training epoch when executing on single NVIDIA Titan Xp GPU and 2.5 GB of GPU memory. We ran for 500 epochs which required between seven and eight hours on the single GPU. We did not observe significant changes variational bound values or in denoising performance after 500 epochs in any of the experiments we conducted for Fig. 3 Runtime complexity increased linear with the number of data points N, with the dimensionality of the data D, with the number of the latents H, and with the size of the DNN used. Runtimes also increased approximately proportional w.r.t. the size of o (n) Empirically we observed sub-linear scaling with [ (m) presumably because of significant overhead computations: for example, increasing from 64 to | 1 I
128 (while keeping all other parameters as above) computational time increases from 49 seconds per training epoch to 75 seconds
x (")
25 in Fig. B used smaller patch sizes (D = 8 x 8) and (i.e., | ()) 200). In general, if the patch size D is increased, more structure has to be captured. This can be done either by increasing the size of the stochastic latents H or by using larger DNNs. Both, in turn, requires more training data in order to estimate the increased number of parameters. In the current setup, the sizes of D which are currently feasible are comparably small. The denoising performance based on small patches is, however, notably very high.
For noise levels
15 and
fewer stochastic latents (H = 64) but larger + (9)
For comparison, n2v uses up to D = 64 x 64 and also all other feod-forward DNN approaches use significantly larger patch sizes than TVAE (and the other approaches in category 1). Still, n2v can be trained efficiently on large patches requiring approximately 19 hours on a NVIDIA Tesla K80 GPU for training on approximately 3k noisy images of shape 180x 180 and seconds for the denoising of one 256x256 image. The higher computational demand of TVAE is also the reason why averaging across databases with many images (such as BSD68) or applications to large single images quickly becomes infeasible. As novel approach. TVAE is, however, far from being fully optimized algorithmically compared to large feed-forward approaches. and there is certainly further potential to improve training efficiency.
Tab. 3 furthermore, systematically compares runtimes of GSVAE, VLAE and TVAE for the Bar- bara denoising benchmark from Fig.
B.5 ZERO-SHIOT INPAINTING
Similarly to the use of TVAE for denoising (see B.4 single image with missing pixels (Fig 13 center) is divided into square patches to form the training set; during training, missing pixels can be treated observables with unknown values when evaluating log-joint probabilities of a data- data-point, which provides a grounded way to treat missing data. To estimate likely values of missing pixels, again use the estimator from (15) and only consider the observed entries of data point when evaluating posterior probabilities:
est E. (2) [Ma(=)]-
(16)
As for denoising (compare Eqn. 15). the expectation value can be approximated using truncated
posteriors with encoding parameters $ (*) Complete data points with 'inpainted" pixels then
24

---

Under review as a conference paper at ICLR 2022
Table 3: Runtimes required by GSVAE, VLAE and TVAE reach the lower bounds and PSNRs reported in Fig. 4 Total runtime of VLAE consists of 5.1 hrs for parameter optimization and 1.8hrs for importance sampling. The PyTorch implementations of the models were executed on single NVIDIA Tesla V100 NV-Link 32GB HBM2 on a server with Intel Xeon 4214 12-core 2.20
GHz CPUs.
GSVAE
VLAE
TVAE
50-500-500-66
--5000-500-64
50-500-500-64
256-256-512
epoch
total
epoch
total
epoch
total
epoch
total
epoch
total
10s
0.01hrs
11s
0.03hrs
468
6.9
213s
9.5hrs
234s
10.4hrs
Figure 13: Inpainting of the 'House" Image with TVAE.
be used for DNN backpropagation to optimize the decoder. The inpainting procedure consequently directly derives from the standard probabilistic treatment of missing values. In contrast, amortized approaches will have to specify how encoder network should treat missing values because encoder DNNs expect real values for all pixels as input.
When evaluating TVAE on standard inpainting benchmarks, we observe competitive performance compared to other approaches. Big.Bsshows a comparison of inpainting performance (in terms of PSNR) with previous state-of-ther oowttffthhatttte systems that like TVAE do not require large, clean training data nor information, e.g., on the noise level. As can be observed, TVAE outperforms approaches such BPFA (Zhou et al. 2012) Papyan al. (207)) in most settings. TVAE performance is lower than for DIP (Ulyanov et al., 2018). TVAE, like BPFA and Papyan et al. (2017). is a permutation- invariant approach, however. That is, the TVAE model itself does not leverage information about the 2D nature of images. In contrast, DIP results rely on a large dedicated DNN with LeakyReL as activation functions, U-net / hourglass architecture with skip connections, and convolutional units with reflection padding (see supplement Ulyanov et al. (2018)). The convolutional stages do explicitly assume the 2D image structure. We also remark that DIP uses in total 2 million parameters compared to about 0.5 million parameters of the standard multi-layer perceptron used in TVAE. Furthermore, and as a consequence of its more intricate architecture, DIP uses many more tunable hyper-parameters.
In the case of the 'House' image, training lasted 500 epochs taking around seconds/epoch on single NVIDIA Titan Xp GPU.
Tab. lists the hyper-parameters used for these experiments.
B.6 FURTHER COMPARISON TO MODELS WITH GRADIENT-BASED ENCODER OPTIMIZATION
Fig 4 provides comparison of the generative representations used by TVAE, GSVAE Jang al.
2016 and VLAE (Park et al. 2019a) for denoising D x 8 patches of the noisy Barbara image
(additive white Gaussian noise with 25; compare Sec. and BB4. We applied the models
using different decoder architectures including 50 500 500 D and 256 256 512 D
(denoted are the numbers of network units counted from decoder input layer (value referred as
25

---

Under review as a conference paper at ICLR 2022
Figure 14:
Inpainting of the 'Castle' Image with TVAE. Left Original image. Center Training image (top, 50% missing pixels, bottom, 80% missing pixels). Right Inpainting result with TVAE (top, 50% missing pixels, bottom, 80% missing pixels).
H), to decoder hidden layers, to decoder output layer (value referred to D): for GSVAE we used / 5 x 10 and И = 32 categorical latents). We observed the GSVAE and VLAE implementations to yield significantly better results when applying the algorithms after normalizing the image patches to the interval [0, 1]; to maintain comparability, we applied the same procedure for TVAE.
To investigate differences in the learned representation, we computed (i) the sparsity of the encoding En nh / H: i.e. the average number of active latents per data point), (ii) the best lower bound across training epochs (both depicted in BB) and (iii) the decoder output for singleton input (1l-dimnniional vector containing single *1" entry and 'O' entries otherwise; results visualized in Fig. 4C). For VLAE, Fig. 4B lists an importance sampling-bast -baed log-likelihood estimate instead of lower bound value. The results depicted in Fig. 4 and C were obtained using the 50 50-550-500-D decoder, and panel C illustrates a random selection of ten singleton means. As can be observed from Fig. 4 TVAE learns comparably very sparse encodings with generative fields capturing distinct patterns of the underlying image. Such encoding shows to result in comparably very high lower bounds which, in turn, result in comparably very high denoising PSNRs.
As another example of commonly used image patch dataset, we applied TVAE to CIFAR-10 and investigated the learned data encoding, also comparing with GSVAE and VLAE (Fig. While patches from the Barbara image (considered above) contain comparably little, elementary structure, CIFAR-10 10 images depict entire objects (cars, animals, etc.) and thus contain significantly more complex structure. Similarly the Barbara benchmark, TVAE learns sparse encoding CIFAR- 10 images; the performance in terms of lower bounds is, however, less competitive compared to GSVAE and VLAE (when controlling for comparable decoder network architectures).
26

---

Under review as a conference paper at ICLR 2022
A Log-likelihood estimates
GSVAE
VLAE
TVAE
1024-256-512
32-512
50-500-500
32-512
50-500-500
1024-256-512
1024-512
2559
2392*
2687*
1649
1831
2044
2893
B Sparsity
GSVAE
VLAE
TVAE
1024-256-512
32-512
50-500-500
32-512
50-500-500
1024-256-512
1024-512
512
n/a a
n/a
13
18
179 1024
135
1024
1024
C Samples (top) and TVAE reconstructions (bottom)
Figure 15: Log-likelihood estimates and sparsity obtained for CIFAR-IO. For comparison, we considered Gumbel-softmax VAE (GSVAE; Jang et al. 2016)) and VLAE (Park et al. 2019a). For VLAE, we cite the values reported in the original publication (these correspond importance sampling-based log- lieelkkoihood estimates). Values for GSVAE, computed ourselves using pub- liely available source code (Jang) 2016) together with the default parameter settings. For GSVAE and TVAE, the values listed in panel A denote lower bounds. The values in panel B depict sparsity measured in terms of average number of active latents per data point (Σ, Th H). The columns in panel A, B refer different decoder architectures: 1024-256-51 12, for instance, denotes H/ 1024 latents in the decoder input layer and two hidden layers with 256 and 512 hidden units, respectively.
The decoder output layer was the same all conditions (D 32 x 32 3). Panel C depicts reconstructed data points obtained with TVAE for the 1024-512 setting.
27

---

Under review as a conference paper at ICLR 2022
cie
cie
54 Trech
90% Steahen
Tork Prrfensnnos
sie
A35%:
3339:
OFF3C
A013
365
260
2016
1-21
F95e
1965
346
1911
33L
15.00
11.36
0:43
Figure 16: Results for 'Zero-Shot' Audio Denoising. Panel A depicts the dB-scaled amplitude spectrogram of an example from the LJ-Speech dataset. Panel was obtained after adding Gaussian noise (a 0.1). Panels C-F show the denoising results of GA (Lu & Loizou| 2008), MMSE-STSA (Ephraim & Malah 1984), DCDAP (Narayanaswamy et al. 2021b) and T TAE. Panel G reports SNR and PESQ improvements averaged over five examples per dataset (the improvement is computed by comparing the denoised waveform with the target waveform; see App. BB7 for details).
B.7 ZERO-SHOT AUDIO DENOISING
Learning-basedd 'zero-shot' data enhancement is subject of current research not only in the con- text of image but also audio processing (e.g.. Zhang al.) 2020 Narayanaswamy et al. 202 Michelashvili & Wolf 2020). Narayanaswamy et al. (2021b) b). for instance, discuss applications of U-Net-based networks with dilated convolutions the task of unsupervised Gaussian audio denois- ing. To address the question of the extent to which the strong 'zero-shot' denoising performance of TVAE on visual data (Figs. 3 carries over to audio data, we applied TVAE to the benehmark considered in Sec. 4.1 and Tab. in Narayanaswamy et al. (2021b). Concretely, we followed the experimental design described in Narayanaswamy et al. (2021b) and used the following datasets: LJ-Speech (Ito & Johnson| 22221) SC09 Spoken Numbers [Warden] 20188] Donahue et al. [2018; we used the version made available by [Bhally 2018), and Bach Performances (Donahue et al. 2018). From each of these three datasets, we randomly selected five examples after resampling the audio files to 16 kHz. Regarding the number of examples per dataset, our procedure slightly diverts from the one used by Narayanaswamy et al. (2021b) who collected 50 examples per dataset. The reason for limiting our evaluation to only five samples lies in avoiding long runtimes of TVAE (compare App-AA and B.4). For the I.-Speechh and Bach Performances datasets, cerpts of two seconds duration; for SC09, each example had a duration of one second. To each of the in total 15 collected snippets, we added Gaussian noise using a 0.1, We then normalized the noisy waveforms to fill the range [-1, 1]. Narayanaswamy et al. (2021b) do not report to have used such normalization; for TVAE, we observed data normalization to be beneficial to avoid numerical instabilities related to very small variances learned due to very small waveform amplitudes. Finally, we applied TVAE to the noisy waveform after extracting overlapping chunks of
randomly selected ex-
it helped
D 400 samples (similarly to the overlapping patches extracted from noisy images, ef. App. B.4
For the evaluation, we used two standard baselines, namely Geometric Approach (GA: Lu & Loizou 2008) and the Vinimum-Mean Square Error Short-Time Spectral Amplitude estimator (MMSE-STAA:) Ephraim Malah 1984) together with the noise power spectral density estimator of SSpsh--
Gerkmann & Hendriks 2012). Furthermore, compared to the approach of (arayanas (2021b) which we refer to as DCDAP (as an abbreviation for 'Deep Audio Prior with dilated convo- lutions "). We applied the publicly available source code of DCDAP (Narayanaswamy et al. 202 together with the default parameter settings; as 'dilation type', we chose the option 'exponential" For the LJ-Speech and the SC09 datasets, we quantified performance in terms of Signal-to-Norts Ratio (SNR) and Perceptual Evaluation of Speech Quality (PESQ); for the non-speech dataset (Bach Performances), we measured only SNRs. For all three benchmark datasets considered, TVAE can improve the performance of all compared methods in terms of both SNR and PESQ improvement (Fig. 16p.
al.
28


Reviews:
[{"review_id": "jLrUbCgDbjv", "reviewer": "Reviewer_ALx1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "main_review": "**Strenghts**\n\nI found the paper to be a very interesting read, since it presents a novel idea to train discrete VAEs, which is notoriously challenging. The idea is simple and theoretically grounded, as it is based on the truncated variational EM. Overall the paper is well written and clearly explains the presented method. The introduction is however too long and not to the point: most of it can be put in a \"related work\" section, and the introduction could be used instead to better introduce and justify TVAEs.\n\nDiscrete VAEs are commonly trained with continuous relaxations of latent variables such as using the Gumbel-Softmax distribution. This is however hard to train due to the needed annealing that is difficult to tune, and as discussed in this paper does not offer very sparse representations. The idea presented in this paper is quite different from standard VAE training, since it relies on non-amortized methods based on truncated approximations and evolutionary algorithms. This implies that this method is able to avoid the amortization gap (but also that its training will be slower and less scalable). TVAEs show SOTA/competitive performances in standard benchmarks for image inpainting and denoising, even in the one-shot setting (while other methods might require large amount of data to achieve similar results).\n\n**Weaknesses**\n\nThe paper offers many details on the proposed algorithm both in the main text and in the very extensive appendix. However, after reading both of them, I still had many open questions on why and how this method works, which require some more detailed analyses and ablation studies. Some of them might be at least inferred by reading the appendix in detail, but due to their importance this should not be required from the reader.\n\nThe core idea of the algorithm is based on a sample-based approximation of a high dimensional integral in the ELBO, where samples are obtained with evolutionary strategies. This raises several questions:\n1. How good and robust is the approximation obtained by evolutionary strategies?\n    1. How would a random sample selection perform?\n    2. Have you experimented with different EAs?\n    3. How does the quality of this approximation varies if we change the number of latent dimensions?\n2. How do you initialize the S latent states in algorithm 1? It is a bit unclear if you use the samples from the previous iteration by keeping population in memory (at the end of page 5 you say it's not required, but in page 6 you say they need to be remembered across iterations).\n    1. in case you re-use samples from the previous iterations, how do you ensure you do not get such in local optima? Especially at the beginning of training the latent space will be constantly changing.\n    2. How diverse are the states at the end of the evolutionary loop?\n\nDue to the non-amortization and the usage of EA, for scalability reasons this method can only be applied to a restricted task domain, that is however well defined and discussed in the paper. \n\nMinor comment: figures in main text are way too small to appreciate the differences, which are key in denoising/inpanting tasks.\n", "summary_of_the_paper": "This work focuses on VAE models with discrete latent variables, that are optimized with evolutionary algorithms using ideas from truncated Variational Expectation Maximization. This model is shown to learn a sparser representation than other methods for discrete VAEs. This allows TVAEs to be well suited for denoising and inpainting tasks.\n", "summary_of_the_review": "The presented idea is interesting and novel in the VAE setting, and could inspire new research in generative models with discrete latent variables. \nWhile the experiments show that the model performs well in inpainting and denoising tasks, I feel that to be more impactful this paper lacks a clearer analysis and discussion on what makes this model work. I'd be happy to increase my score if the authors improved the paper in this direction.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "YsbeIiUhQuX", "reviewer": "Reviewer_DBE8", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "main_review": "Strengths:\n- The proposed idea is rather straightforward but interesting. To my knowledge, it is the first time I see an application of an evolutionary algorithm to learn binary encoders in VAEs.\n- The experiments are promising. However, I miss a deeper comparison with existing methods (e.g., RELAX, Gumbel-softmax).\n\nWeaknesses:\n- It is quite unclear how the decoder is formulated. The Eq. 3 suggests we deal with the Gaussian distribution. However, the comment on the MSE is a bit misleading because it is a well-known fact that the likelihood function for the Gaussian distribution results in the MSE.\n- The notion of the subsets (\\Phi^{(i)}) that are variational parameters is a bit vague. The paper would highly benefit from presenting an example right after the Eq. 3. This is especially important in the discussion about passing all states of \\Phi^(n)} through the decoder and the complexity.\n- In the Eq. 5 (and before it), there is a new variable called “prior parameters” introduced. However, the authors did not introduce it earlier nor define the prior. From the equation it seems they are the expected values of z’s.\n- What is the rationale for picking the very particular mutation operator? What about other possible perturbations?\n- I miss a deeper comparison and discussion with other approaches, namely:\n    - MCMC techniques for binary variables:\n        * Strens, M. (2003). Evolutionary MCMC sampling and optimization in discrete spaces. In Proceedings of the 20th International Conference on Machine Learning (ICML-03) (pp. 736-743).\n        *Auzina, I. A., & Tomczak, J. M. (2021). Approximate bayesian computation for discrete spaces. Entropy, 23(3), 312.\n    - Stochastic differentiation libraries that allow differentiation through discrete random variables:\n        * Bingham, E., Chen, J. P., Jankowiak, M., Obermeyer, F., Pradhan, N., Karaletsos, T., ... & Goodman, N. D. (2019). Pyro: Deep universal probabilistic programming. The Journal of Machine Learning Research, 20(1), 973-978.\n        * van Krieken, E., Tomczak, J. M., & Teije, A. T. (2021). Storchastic: A Framework for General Stochastic Automatic Differentiation. arXiv preprint arXiv:2104.00428.\n    - Or methods for differentiating black-box models:\n        * Grathwohl, W., Choi, D., Wu, Y., Roeder, G., & Duvenaud, D. (2017). Backpropagation through the void: Optimizing control variates for black-box gradient estimation. arXiv preprint arXiv:1711.00123.\n- The structure of the network is very simplified. It is hard to predict how the proposed approach will behave in a more complex case (i.e., convolutional layers, recurrent layers, residual layers, etc.). I am aware that the proposed approach is generic, however, the learning dynamics is completely different for various layers.\n", "summary_of_the_paper": "The paper proposes to use evolutionary computing for optimizing binary encoders in the Variational Auto-Encoder framework. The authors present a specific evolutionary algorithm for learning encoders for binary latent variables. The experimental section outlines some applications to denoising and inpainting.", "summary_of_the_review": "The paper proposes an evolutionary algorithm for learning encoders for binary latent variables. The paper allows a reader to understand the main idea, however, it lacks a proper presentation of some details (e.g., the idea of using truncated distributions in the discussed context, presenting explicitly the forms of distributions used). Moreover, the experimental section is interesting, however, it misses a deeper comparison with other existing methods and an analysis of various architectures of neural networks. Overall, I find the paper interesting, however, it is not ready to be accepted to the conference.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "X3Gvk4-BNlM", "reviewer": "Reviewer_XRYc", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "main_review": "Pros: The theoretical derivation of this article is very clear\nCons:\n(1). This paper used discrete latents to solve present and absent problems of objects or edges. It would be better to prove the proposed method on a large scale dataset, such as ImageNet;\n(2). The advantages mentioned by this paper are: fewer algorithm elements, fewer hyperparameters and fewer model parameters. It would be better to carry out experiments to prove that images generated from this model has better performance while maintaining fewer model parameters.\n", "summary_of_the_paper": "This paper investigates VAEs with binary priors able to learn sparse latent code and studied how such codes can efficiently be learned. It also proposes a method that uses a direct discrete optimization of binary latent vectors.\n", "summary_of_the_review": "This article is written clearly, but the experimental part is a bit lacking in persuasiveness.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "WpNygmNoqsw", "reviewer": "Reviewer_TZnV", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "main_review": "This paper sheds light on a new direction of discrete latent distribution VAE models as it uses a direct model for the encoder part instead of DNN. The formula variational optimization for the direct model are novel and concrete. The criterion for encoder optimization (Eq. 10) encourages the latent code to be sparse. This is also validated in the experiments, which provides great advantages in some application scenarios. The experiment part of the paper is solid and the proposed method is consistently evaluated with previous methods. The discussion part also gives great insights into the advantages of the proposed method under different application settings. \n\nA minor concern is the scalability of the proposed method. As pointed out by the authors, for each epoch of N data points, we need to evaluate S*N states, where S scales w.r.t. the complexity of the encoder, compared to a O(N) complexity under traditional VAE settings. This should not be a problem for a small to medium dataset but might be a performance concern for a very large dataset.", "summary_of_the_paper": "In this paper, a novel variational autoencoder (VAE) model with binary latent distribution is proposed. Compared to traditional VAE models, aside from the latent distribution here is Bernoulli (instead of Gaussian), the encoder part is an explicitly expressed model (instead of a DNN) and can be optimized directly, which makes the model to have a simpler form compared to previous DNN-based sparse latent code learning methods. The model is numerically evaluated on (zero-shot) denoising and inpainting tasks, and shows comparable or better performance than competitive methods. \n\nThe main novelty of this paper comes from developing a direct VAE framework to handle discrete latent codes. Previous discrete latent code VAE models use DNN as encoders, and thus need methodologies, e.g., a softening of discrete distributions, for discrete latent to estimate gradients for the encoder. In this paper, the authors avoid using DNNs and directly model the encoder explicitly, whose optimization does not require gradients. ", "summary_of_the_review": "The proposed method is novel and well-presented. I would recommend accept this paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "4bCqixoHcnm", "reviewer": "Reviewer_hasK", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "main_review": "I am somewhat split on this paper. On the one hand, I found the paper to be well motivated at a high level as a way to avoid gradient bias and obtain sparsity; and the approach taken by the authors is quite original and deviates from most VAE works. On the other hand, the proposed method is much more computationally intensive than regular training of VAEs, and I also wonder if this might be a case of over-complicating things for the sake of the idea sounding interesting.\n\nThe paper is mostly well-written, although I would appreciate some additional background on genetic/evolutionary optimization algorithms in the appendix, as I do not believe these are often in the area of expertise of the intended machine learning audience of this paper.\n\nAs for the experiments, while the tasks selected by the authors do highlight some benefits of their proposed method; it does not seem like the proposed approach necessarily performs better (e.g. Figure 12 in the appendix shows the proposed method achieving worse ELBO than a Gumbel-Softmax VAE with a comparable architecture, although the proposed method recovers sparser latents). I believe there should be a discussion about these results in the main manuscript. Finally, the authors do discuss computational cost, but do not report running times. Given that the cost is highly increased over the baselines, I believe it's particularly important for the authors to report running times. Finally, the only continuous relaxation the authors compare against is the Gumbel-Softmax, and not further improved versions, e.g. [1,2,3].\n\nMinor things:\n\n-abstract: \"canonically\" -> \"canonical\"\n\n-change \"a.k.a.\" to something more formal, e.g. \"i.e.\"\n\n-page 3, second paragraph: \"Gumble\" -> \"Gumbel\"\n\n\n\n[1] Estimating Gradients for Discrete Random Variables by Sampling Without Replacement, Kool et al., ICLR 2020\n\n[2] Invertible Gaussian Reparameterization: Revisiting the Gumbel-Softmax, Potapczyski et al., NeurIPS 2020\n\n[3] Rao-Blackwellizing the Straight-Through Gumbel-Softmax Gradient Estimator, Paulus et al., ICLR 2021\n\n========================================================================================================\n\nUPDATE 1 AFTER REBUTTAL\n\n========================================================================================================\n\nI have read the other reviews, as well as the author's rebuttal, and unfortunately my concern that this paper is complicated for the sake of it remains. I will thus maintain my current score.", "summary_of_the_paper": "This paper proposes an approach to learn VAEs with binary latent variables. Rather than relying on commonly used continuous relaxation techniques, the authors completely forgo the encoder neural network and parameterize the approximate posterior using a subset of states, so that the approximate posterior is proportional to the true posterior but only supported in the corresponding subset of states. The authors then propose a training algorithm which involves doing gradient descent over the decoder and using a genetic algorithm to optimize over the (non-amortized) posterior distribution.", "summary_of_the_review": "This paper proposes an interesting and novel way of training VAEs with binary latents; although the method adds a lot of computational complexity for benefits which are not completely clear.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a new approach for learning binary latent variable models using evolutionary optimization.

Pros:
* A new perspective to learning binary latent variables is proposed using evolutionary algorithms.
* The proposed method works well on auxiliary tasks such as zero-shot denoising and inpainting. 

Cons:
* The proposed evolutionary optimization performs poorly on the binary VAE problem. 
* It has a high computational cost that will limit its application in real-world problems.
* An in-depth comparison with prior work on learning discrete latent variables is missing. This may include MCMC-based approaches, REINFORCE-based techniques, REBAR or RELAX. 

This paper presents an interesting direction for learning binary latent variables using evolutionary algorithms. However, the proposed method performs poorly on the binary VAE problem which is the core problem, targetted in this paper (See likelihood values for binary VAEs in Fig. 15). The reviewers have raised concerns regarding the computational complexity of the evolutionary method in practice. They have also criticized the missing baselines for the binary VAE experiments. 

The authors have argued that the proposed method excels at auxiliary problems such as zero-shot image denoising and inpainting. However, these problems are not the central problem of this submission, and naturally, they have not been discussed, reviewed, and evaluated thoroughly. They can be also addressed with non-binary VAEs and other forms of generative models which are not discussed in the paper. 

Given these concerns, we don't believe that this submission in its current form is ready for publication at ICLR.
Decision: Reject