Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The proposed paper presents a method for optimizing discrete structured VAEs using Natural Evolution Strategies (NES). The authors present a theoretical conclusion regarding algorithm convergence and extensive empirical results demonstrating that NES performs comparably to gradient-based methods, while being more computationally efficient.
main_review: **Strengths:**
* The paper addresses an open problem in the space of discrete VAEs.
* The paper is very well written, easy to follow, and compelling.
* The presentation of the background material logically leads the reader into the proposed methodology, and the math is included as a meaningful and coherent addition to the story.
* The experiments are extensive and convincing, demonstrating advantages over a wide range of baselines.

**Weaknesses and suggestions for improvement:**
* Some relevant works are missing from the literature review [1-6]. Contextualizing the proposed method in these works would make the overall paper stronger.
* Since Eq. (2) is critical to the proposed method and the presented theoretical results, it would be helpful to highlight its importance when it is first defined. I recommend you clearly state that Eq. (2) is the objective function you will consider for the remainder of the paper, and elaborate on why it is non-negative (i.e., is it because of a ReLU at the end of the $f_{\theta}$ network?). Additionally, please highlight in the proof of Lemma 1 where the non-negativity comes in.
* I would appreciate the inclusion of a discussion of the bias introduced by the NES algorithm in Eq. (4). Further discussion on why $N$ forward passes in NES are more desirable than a sampling-based technique with $N$ samples would also be helpful. The experiments and the parallelization arguments contribute to this discussion, but a bit more emphasis and detail in the methods section would aid the reader to better understand the advantages of the proposed method.
* I recommend the authors spend a bit more time explaining what $w_{1}$ and $w_{2}$ correspond to, i.e., the encoder and decoder parameters, respectively? At first read, I thought you were setting $N = 2$.
* The statement on pages 4 and 5 that for any $T$, there exists a $t \in \{1, ..., T\}$ for which the magnitude of the gradient is arbitrarily small needs to be corrected. Specifically, it should say something like for *T sufficiently large* the magnitude of the gradient is arbitrarily small.
* In the experiments, additional discussion would be helpful for why SST might be expected to do better than NES in Table 1, and the disadvantages of SparseMap compared to NES.
* Lastly, the paper needs to be proofread for typos, as I found a number of them while reviewing. Some examples include: 'over exponentially large latent space', missing period after Eq. (3), 'using NES algorithm' (missing 'the'), incorrect quotation marks for 'parameters' and "Growth in N", 'in contrast to contemporary trend' (missing 'the'), 'which must carefully designs', 'being simpler and robust' (missing 'more'), 'generic, flexible, and simpler to implement' (missing 'more'). The references need to be proofread for consistency, as well: some venues are missing, some venues are only presented as acronyms, while others are presented in full, incorrect capitalization ('Ai'), etc. If possible, avoid splitting equations across multiple lines in the text and capitalize 'Section' when referencing section numbers.

[1] A. van den Oord, O. Vinyals, and K. Kavukcuoglu, "Neural discrete representation learning," in NeurIPS, 2017.

[2] A. Razavi, A. van den Oord, and O. Vinyals, "Generating diverse high-fidelity images with VQ-VAE-2," in NeurIPS, 2019.

[3] G. Correia, V. Niculae, W. Aziz, and A. Martins, "Efficient marginalization of discrete and structured latent variables via sparsity," in NeurIPS, 2020.

[4] M. Itkina, B. Ivanovic, R. Senanayake, M. J. Kochenderfer, and M. Pavone, “Evidential sparsification of multimodal latent spaces in conditional variational autoencoders,”in NeurIPS, 2020.

[5] P. Chen, M. Itkina, R. Senanayake, and M. J. Kochenderfer, "Evidential softmax forsparse multimodal distributions in deep generative models," in NeurIPS, 2021.
summary_of_the_review: Overall, the authors present an interesting method for optimizing discrete VAEs with compelling theoretical and experimental results. The paper is well written and the story is coherent. My recommendation is to accept.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In this paper, the authors use Natural Evolution Strategies (NES) to learn discrete structured VAE. They empirically show that optimizing discrete structured VAEs using NES is as effective as gradient-based approximations. And they also prove that NES converges for non-Lipschitz functions in discrete structured VAEs.
main_review: Strengths.

1. The paper is well-organized. 

2. In this work, a gradient-free black-box optimization algorithm is explored for discrete structured VAEs. 
They also experimentally show gradient-free methods are as effective as sophisticated gradient-based methods.

3. They prove that the NES algorithm converges for non-Lipschitz functions. This is different from the contemporary trend that relies on Lipschitz functions.

Weaknesses
1. In VAES, there are two terms for ELBO: one is sampled log-likelihood term, the other is the KL-divergence term that measures the similarity of the auxiliary distribution q and the unknown distribution p.  A lot of people notice the importance of the second term. In this paper, the authors use gradient-free methods for the first term. However, the second term is missing in the algorithm. Or do I miss something? 

2. The gradient-free black-box optimization algorithm is generally with high variance (for example, refinance force algorithm). Unfortunately, there are no clear discussions on this. And how is the effect of the proposed method? Mirrored sampling is used in the experimental setup. It is not clear whether this sampling method is used in other methods. This leads to a question: whether there is a fair comparison.

summary_of_the_review: It would be great to provide more details on how to get Equation (2). Especially, why an argmax operation is added.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: In this paper, the authors proposed to use the Natural Evolution Strategy (NES) algorithm for learning discrete structured VAEs. This algorithm estimate gradients with forwarding pass evaluations only and do not require propagating gradients through their discrete structures. Authors showed empirically that optimizing discrete structured VAEs using NES is as effective as gradient-based approximations.
main_review: The strengths of the paper:
- proposing another approach to optimization a neural network than through propagating gradients,
- proving that NES converges for non-Lipschitz functions such as the objective function of a discrete VAE,
- experimentally showing that gradient-free methods have similarly effective as perturb-and-parse gradient-based methods

The weaknesses of the paper:
- optimizing only the mean of the distribution of parameters, a covariance matrix of the distribution of parameters is imposed by the user. The classical model VAE optimizes both these parameters.
- too poor experiments, the authors showed experiments that presented effective optimization of the ELBO values and how the latent space size affects the method’s run-time. It could be possible to show how the model reconstructs the images or generates them (this can be troublesome due to the lack of optimization of the VAE model variance). The results of such experiments can be compared to the results of the VQ-VAE method (https://arxiv.org/pdf/1711.00937.pdf or VQ-VAE 2 - https://arxiv.org/pdf/1906.00446.pdf).
summary_of_the_review: The paper is well written, the authors clearly describe the problem and the proposed solution that is computationally appealing because does not require propagating gradients. It is theoretical work, the experiments only show the effectiveness of the ELBO function optimization. The authors consider only optimization of the mean distribution of parameters and do not show other experiments that confirm the effectiveness of such optimization in generative models (see the section of the weaknesses of the paper). Hense I rate the work good but not sufficient for the ICLR conference.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper proposes and analyses the use of Natural Evolutionary Strategies (NES) to train a VAE with a discrete latent space representation (Spanning Trees).  NES provides a smoothed approximation of the discrete function for which the gradient can be easily computed.  This approach can be seen as an example of the REINFORCE algorithm, although it clearly shows superior performance to traditional REINFORCE implementations.  The authors show that not only is it competitive and often marginally better than state-of-the-art techniques for this problem, it is also much more straightforward and easier to generalise.
main_review: This is an elegant paper.  Although, NES algorithms have been used elsewhere, this is the first application to VAE training.  By demonstrating its feasibility and effectiveness the authors highlight the usefulness of the approach.  The discussion and analysis is informative and of a high scientific standard.  The use is the approach in this contexts requires the use of a number of sampling tricks which makes the approach quite subtle.

One could argue that this is just an application of NES to yet another application, but I think this would be unfair.  The REINFORCE algorithm has become a important, goto, algorithm in deep-learning.  Showing that NES provides a simple and efficient algorithm for solving non-differentiable problems is an important contribution worth making.

The paper is well written, accurate and to the point.
summary_of_the_review: This is in my view a good paper that deserves a place in ICLR.
review_title: null

Meta-review: The authors propose to use genetic algorithms to learn variational autoencoders (VAEs) with discrete latent spaces. Specifically they employ natural evolution strategies (NES) to avoid backpropagating gradients through discrete variables. Experiments show how the proposed approach is competitive with the current state-of-the-art to train discrete VAEs.

Some concerns arose from the review and discussion phases, these included confusion around the justification and derivation of NES for VAEs in the presentation and the limitation of the experiments. Authors were responsive and provided the reviewers the needed clarifications, an updated presentation in the revised paper and additional experimental results which ultimately were successful in raising the reviewers' scores towards full acceptance.
Decision: Accept (Poster)