Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: Natural gradient has been proven effective in many statistical learning algorithms. A well-known difficulty in using natural gradient is that it is tedious to compute the Fisher matrix (if one is using Fisher-Rao metric) and the Wasserstein information matrix (if one is using Wasserstein metric). It's important to be able to estimate natural gradient in a practical way, and there have been a few papers looking at this problem but mostly for the case with a Fisher-Rao metric. This paper takes a different and general approach to approximate natural gradient by leveraging the dual formulation for the metric restricted to the Reproducing Kernel Hilbert Space. Some theoretical guarantees of the proposed method is established together to some experimental study.

I find this work interesting with some important merit, as it tackles an important problem in statistical learning. My main concern, however, is the problems related to RKHS from a practical point of view. For example, solving optimization problem (11) is difficult and the paper makes a range of further approximations to be able to arrive at an approximate solution. Also, selecting the kernel and its bandwidth is crucial in practice. From a practical point of view, I suspect that more evidence is needed to justify if the proposed method can really offer a method of choice.  

Having said that, I believe this paper provides an important first (and alternative) step towards an important problem. The paper is also well written and well structured. I have a few further comments below
1) In the abstract and introduction, the invariant property of natural gradient is mentioned several times without a detailed explanation why/what it is. Adding a brief explanation of this property is appreciated.
2) The sentence on line 8 in Introduction reads ".. It can be not alleviated by using adaptive step size...". This is when the authors are talking about the adaptive learning methods. Is this a too strong comment about the adaptive learning methods? Can the authors know for sure that these methods cannot be used here?
3) Equations (1) and (2): Are they correct? should the minus sign just be in front of the first term \mathcal{M}_t(u) only?
4) Page 4, first line after Def 3: "one covers the usual gradient \nabla\rho_\theta(x)". It is not very clear (to me) how to get this. Can the authors please elaborate more on this?

 
     

review_title: Official Blind Review #1

final_score: rating: 8: Accept
review_content: Thank you for your revision and for the rebuttal. This a  strong submission with insightful angle on natural gradients and with provable guarantees. The authors improved a lot the manuscript and incorporated reviewers feedback. I am increasing my score to 8. 
 
###
Summary of the paper: 

The paper provides a way to estimate the natural Wasserstein gradient using Kernel estimators. The idea is neat and novel. Natural Wasserstein Gradient similar to the so called natural fisher gradients preconditions the gradient using a matrix that uses the local curvature of the manifold of the parametric distribution. 

Authors give variational forms of the Fisher information matrix of an explicit model , using  the variational form of the chi squared or the Fisher Rao divergence. Similarly authors give a variational form of the wasserstein natural gradient . Let theta be the parameter of the parametric implicit model, theta in R^q.  For a descent direction $u$, the variational form is obtained via finding an objective S,  $\sup_{f\in C^c_{\infty}} S(f, u ) = u^{\top}G_{W}u$, where $G_{W}$ is a form of  "Wasserstein information matrix".

Authors then propose to learn the function f in an RKHS and propose to find the descent direction by solving
 $\min_{u} <u, \nabla_{\theta} Loss (p_{\theta})>  + \sup_{f\in RKHS}  S(f, u ) + r(u)- \lambda ||f||^2_{rkhs}$
where r(u) is a quadratic regularizer on u. 

The sup problem has a closed form solution and can be approximated  using Nystrom approximation and randomization on dimensions. The problem in u has also a closed form solution , and one used u as the proxy to the natural  descent. 

Authors under some assumption  show that the  estimated natural W gradient in RKHS  is concentrated around the true one. 

Experiments on synthetic data and in classification on CIFAR 10 and CIFAR 100 shows that the preconditioning of the gradients that the method offers allows faster convergence in both well conditioned and ill conditioned initialization of the weights of the neural network.
 
Review : 

The paper is not easy to follow and the high level intuition how the method works is not well explained. 

It would be easier for the reader, to motivate the natural wasserstein descent from how one defines natural Fisher descent , where one seeks a first order approximation of $KL(p_{\theta},p_{\theta+ \epsilon u})$ as we perturb in the parameter space and this well known that this epsilon $u^{\top}F u$. 
Hence natural Gradient descent is :
$\min _{u} <u, \nabla_{\theta}Loss(p_{\theta})> + KL(p_{\theta},p_{\theta+  u}) \approx min _{u} <u, \nabla_{\theta}Loss(p_{\theta})> + u^{\top}F u$  

Now for the wasserstein distance one has also similarly:
$\min _{u} <u, \nabla_{\theta}Loss(p_{\theta})> + W^2_2(p_{\theta},p_{\theta+  u})$

and it is known that as epsilon goes to zero we have: 

 $W^2_2(p_{\theta},p_{\theta+ \epsilon u})/\epsilon = ||p_{\theta} - p_{\theta+ \epsilon u}||^2_{H^{-1}(p_{\theta})}+o(\epsilon) = \sup_{f} \int f (p_{\theta} - p_{\theta+\epsilon u}) - \frac{1}{2} \mathbb{E}_{p_{\theta}}||\nabla_x f(x)||^2+o(\epsilon) $

Now replacing with the implicit model as epsilon goes to zero we get the expression given in the paper using a simple taylor expansion:
$=   \sup_{f} \int <\nabla_{\theta} h_{\theta}^{\top}\nabla_x f(h_{\theta}),u > d\nu - \frac{1}{2}\mathbb{E} _{p_{\theta}}||\nabla_x f(x)||^2$

in a sense the paper is proposing to linearize $W^2_2$ around the perturbation in the parameter space of the implicit model and this can be done using  $|| .||_{H^{-1}(q)}$ , as pointed and used in many recent works.  then the paper proposes to approximate $|| .||_{H^{-1}(q)}$ in RKHS which was already proposed in Mroueh et al  in Sobolev Descent.  AISTATS 2019. 

We encourage the authors to layout in the beginning the derivations form this point of view which will make the paper easier to digest, the expression in Equation 7 seems mysterious and pulled out of a hat, but it is easier to understand by going to perturbation analysis usually done on KL for Fisher Natural gradient and to do it also here starting from the linearization of $W_2$ with $||.||_{H^{-1}(q)}$  , and how to approximate it in RKHS as it was already proposed in the literature in Mroueh et al Sobolev Descent. 


I read carefully the proofs of Proposition 1, 2, 3. I did not ready full the proofs of the concentration of the estimator , but they seem sensible as they follow usual bounding strategies in this context. 

Questions:

- There is nothing special about the wasserstein natural gradient flow variational form and implicit model, once can apply the same to the variational form of Fisher, that would be probably more efficient? It would be great to baseline this one ? 
-the constraint $\int f(x)p_{\theta}(x)=0$ is not imposed in the kernelized version?
- the method comes disappointing since it seems that the preconditioning that the Wasserstein gradient gives is not enough and $r(u)=u^{\top}D u$ is need where D is diagonal depends on T. Have you tried with $D=Identity$? it might be that the scaling of the gradients is coming only from that $D^{-1}$?

- Can you give timings for computing each gradient update and how it compares to regular SGD or diagonal approximation of Fisher natural gradient?

- Does one need preconditioned gradient if the network was self normalized (like batch norm or spectral norm etc)?   


Overall assessment: 

That is a good theoretical work with provable guarantees. The computational complexity of each gradient estimate is large which makes the method not quite appealing in practice. 
review_title: Official Blind Review #2

final_score: rating: 6: Weak Accept
review_content: The authors propose an approximate of the natural gradient under Wasserstein metric when optimizing some cost function over a parametric family of probability distributions. The authors leverage the dual formulation and restrict the feasible space to a RKHS. The authors show a trade-off between accuracy and computational cost with theoretical guarantees for the proposed method, and empirically verify it for classification tasks.

The motivation of the natural gradient is well-motivated. Although the choice of Wasserstein metric is sound, especially for models that do not admit a density, it seems that there are no supporting experiments for this choice over Fisher Information metric. In general, the writing is fine. The flow idea is clear. However, the content is quite dense. Some assumptions just pump out without careful judgment. The idea to restrict into RKHS and use low-rank approach is interesting to approximate for the natural gradient under Wasserstein metric. Overall, I lean to the acceptance side.

Below are some of my concerns:

1) It seems that the natural gradient under Wasserstein metric is well-motivated for models which do not admit a density (to compare with the natural gradient under Fisher information metric). However, it seems that there is no supporting experiments about it yet. For models in the experiments, it is better to show a comparison between natural gradient under Wasserstein metric and Fisher information metric w.r.t. time consumption and accuracy.

2) In proposition 3 and theorem 5, they require some assumptions. The authors should place those assumptions into the main text instead of only putting it in the appendix, and should give more discussions about those assumptions. Especially, for assumption (D), why one can have this assumption? It seems that this assumption (D) has a strong influence to the complexity in Theorem 5? More detail discussion is required.

3) For the relaxation in Equation (9), it seems that the authors do not simply add some regularization terms. How does it relate to the original Equation (7)? What is the meaning of the 3rd term in Equation (9)? and how's about the 2nd term?

4) For the experiments, the authors evaluate the multivariate normal model and the multivariate log-normal model which are very special cases under Wasseserstein information matrix where one can compute in closed-form. The authors should show some general models, especially models which do not admit a density. For the experiments in Section 4.2, the authors should add the natural baseline: natural gradient under Fisher information metric. It is unclear to me why one needs natural gradient under Wasserstein metric over Fisher information metric for this setup? What is the benefit to use natural gradient under Wasserstein metric?

 
review_title: Official Blind Review #3

Decision: Accept (Spotlight)