Analysis of Learning a Flow-based Generative Model from Limited Sample Complexity

We thank the reviewer for their comments and questions, which we address below.

lack of the correlation structure in the input data, which draws the conclusions to be less practical

We believe that ideas similar to the ones used in the present work could be leveraged to address mixtures with structured clusters, see also the answer to reviewer wFJz. Such an extension would allow to analyze more realistic data distributions, and potentially quantitatively capture the learning curves of some simple real datasets, like in (Cui & Zdeborová, 23). This constitutes an interesting research direction which we will further pursue in future work.

We thank the reviewer for their appreciation of our work, and address below their concerns.

Do you think this the same method could be used for more complex distributions, if yes what would be a concrete example?

While the method indeed makes use of the fact that the target density is a Gaussian mixture, we believe that very similar ideas can be employed to address Gaussian mixture densities with structured covariances. This would provide a gateway to modeling more realistic setups, since as shown in (Cui & Zdeborová, 23), at the level of the learning process, the performance of the DAE on MNIST is quantitatively captured when modeling the latter by the matching Gaussian mixture density. Another natural extension which could be addressed with similar methods is the case of more clusters, and using an autoencoder with more hidden units. We leave the exploration of these exciting questions to future work.

We thank the reviewer for their careful reading of our manuscript and the constructive comments. We address below their questions.

How many dimensions are needed to span $\hat{w}_t$ for all $t$ ? [...] I conjecture that two dimensions are enough[...]it would make clear that the model only has access to the empirical means

We thank the reviewer for this suggestion. The weight vectors can indeed be completely equivalently rewritten in terms of $\xi,\mu_{emp.}$ where $\mu_{emp.}$ is the empirical means

Note that this is just an equivalent way to present the equation, and that the underlying results remain totally unchanged. We chose the initial presentation in terms of $\xi, \eta, \mu$ to put further emphasis on the parameters of the target distribution. We however agree with the reviewer that using $\{\eta, \mu_{emp.}\}$, rather than $\{\eta,\mu,\xi\}$, constitutes a more concise rephrasing of the results, and have rewritten the manuscript in this way. We have updated the pdf of our paper to reflect this.

then the model actually does learn the training data by heart (i.e. it predicts the empirical means),

The reviewer is correct that the model overfits, as the trained weights bear explicit dependence on the training samples, and the Gaussian noises $x_0$ employed during training. By "not memorizing", we rather mean that the generated density is not the discrete empirical distribution supported on the training data, but instead a Gaussian mixture. In other words, the generative model allows to generate novel samples, distinct from the training data. We emphasized this distinction in updated manuscript.

On the other hand, it is not entirely correct that the generated density has the empirical mean of the training data as cluster mean. It is already not the case for the Bayes-optimal estimate, which is the empirical means rescaled by a $1/(\sigma^2+n)$ factor. For the generative model, the cluster mean is a linear combination of $\xi$ (subsuming the effect of the noises used during training) and the empirical means, rescaled by multiplicative factors whose expression depend non-trivially on the model parameters - notably the schedule functions $\alpha(t),\beta(t)$, and the regularization $\lambda$. We believe that this precise characterization of the cluster mean of the generated density as a function of the parameters of the learning model is a strength of our analysis.

Also, the rate $\Theta(1/n)$ is not affected by the regularization , and the network architecture is not varied so as to judge whether this particular setup has a particular convergence rate. [...]

The main focus of the paper is not to study the dependence of the convergence rate as a function of the model architecture and parameters, but rather show, in a particular setting, how a learning model can manage to learn the target density with a reasonably fast rate only from a few samples. This is allowed by the network architecture : indeed, had the minimization (5) been carried out over the space of denoising functions, instead of the parameter space of the considered learning model, the resulting generative model would memorize the training samples, and only allow to generate samples already present in the train set, instead of sampling the Gaussian mixture. Furthermore, a discussion for another architecture can already be found in Appendix D of the supplementary material, where we detail the case of an auto-encoder without skip connection. We completely agree with the reviewer that the study of a greater number of architectures is an important research direction to be explored in future works.

the rate to the true solution is essentially given how fast empirical means converge to the mean of the generative distribution.

This is indeed the correct intuition. We would however like to stress that the mean of the generated density is not equal to the empirical means, and that it is quite non-trivial that an auto-encoder can learn to generate a Gaussian mixture with such means just from a finite number of samples when trained on a denoising loss, and that the learning and transport processes can be sharply theoretically characterized.

I thank the authors for the extensive answers and update of the manuscript.

I appreciate that the authors undertook the effort to show that the main behavior of the flow can be described by the span of $\xi, \mu_\text{emp.}$. This makes clear that the model does not have implicit knowledge of the underlying distributions, but really the convergence is successfully borrowed from the convergence of the empiric mean (and not worse).

However, my concern remains that the research question is not really addressed.

Let us maybe approach this starting from my Q4: The characterization of the learned density in Corollary 3.3 describes the unspanned directions as Gaussian, and the distribution in the relevant subspace $\operatorname{span}(\xi, \mu_\text{emp.})$ is specified as time-recursive formulas of the components in $\xi$ and $\mu_\text{emp.}$ directions, influenced by the corresponding components of the weights. What does this tell me about the learned distribution at each of the mixtures? The authors say that the DAE with skip connections is superior over the DAE without skip connections. However, Appendix D shows the same scaling behavior with $n$ is observed in the metric of Corollary 3.3. Even the other end of the spectrum, a fully flexible function memorizing the training data, has this convergence behavior.

So under what metric should architectures be compared, how do the architectures differ in this metric, and what should we conclude from this on the inductive bias & sample complexity of models? In my view, this metric is a strong metric of convergence such as KL divergence or total variation, and the authors are able to show convergence as $\Theta(1/n)$ if this is indeed the dominant scaling behavior.

I am sceptical that the theoretical insight of this work is not large enough for being interesting to a broader audience. Due to the granularity of the scoring system, I think that the improvements are currently not enough to improve my rating. However, I am still happy to be convinced otherwise.