Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.
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.

The 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.

As 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].

Minor things:

-abstract: "canonically" -> "canonical"

-change "a.k.a." to something more formal, e.g. "i.e."

-page 3, second paragraph: "Gumble" -> "Gumbel"



[1] Estimating Gradients for Discrete Random Variables by Sampling Without Replacement, Kool et al., ICLR 2020

[2] Invertible Gaussian Reparameterization: Revisiting the Gumbel-Softmax, Potapczyski et al., NeurIPS 2020

[3] Rao-Blackwellizing the Straight-Through Gumbel-Softmax Gradient Estimator, Paulus et al., ICLR 2021

========================================================================================================

UPDATE 1 AFTER REBUTTAL

========================================================================================================

I 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_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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.

main_review: Pros: The theoretical derivation of this article is very clear
Cons:
(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;
(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.

summary_of_the_review: This article is written clearly, but the experimental part is a bit lacking in persuasiveness.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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. 

The 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. 
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. 

A 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_review: The proposed method is novel and well-presented. I would recommend accept this paper.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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.

main_review: **Strenghts**

I 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.

Discrete 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).

**Weaknesses**

The 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.

The 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:
1. How good and robust is the approximation obtained by evolutionary strategies?
    1. How would a random sample selection perform?
    2. Have you experimented with different EAs?
    3. How does the quality of this approximation varies if we change the number of latent dimensions?
2. 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).
    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.
    2. How diverse are the states at the end of the evolutionary loop?

Due 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. 

Minor comment: figures in main text are way too small to appreciate the differences, which are key in denoising/inpanting tasks.

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. 
While 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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.
main_review: Strengths:
- 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.
- The experiments are promising. However, I miss a deeper comparison with existing methods (e.g., RELAX, Gumbel-softmax).

Weaknesses:
- 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.
- 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.
- 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.
- What is the rationale for picking the very particular mutation operator? What about other possible perturbations?
- I miss a deeper comparison and discussion with other approaches, namely:
    - MCMC techniques for binary variables:
        * 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).
        *Auzina, I. A., & Tomczak, J. M. (2021). Approximate bayesian computation for discrete spaces. Entropy, 23(3), 312.
    - Stochastic differentiation libraries that allow differentiation through discrete random variables:
        * 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.
        * van Krieken, E., Tomczak, J. M., & Teije, A. T. (2021). Storchastic: A Framework for General Stochastic Automatic Differentiation. arXiv preprint arXiv:2104.00428.
    - Or methods for differentiating black-box models:
        * 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.
- 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.

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.
review_title: null

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