Robust Low Rank Kernel Embeddings of Multivariate Distributions
Kernel embedding of distributions has led to many recent advances in machine learning. However, latent and low rank structures prevalent in real world distributions have rarely been taken into account in this setting. Furthermore, no prior work in kernel embedding literature has addressed the issue of robust embedding when the latent and low rank information are misspecified. In this paper, we propose a hierarchical low rank decomposition of kernels embeddings which can exploit such low rank structures in data while being robust to model misspecification. We also illustrate with empirical evidence that the estimated low rank embeddings lead to improved performance in density estimation.
The authors make a kernel extension of paper [1]. That 
      is they give an svd based algorithm for low rank approximations of 
      embeddings with an underlying latent structure. Weak guarantees are given 
      under the assumption that low rank approximations of certain key objects 
      have a low error. Experimental results are promising. Section 4 is 
      cryptic. This is Section 3.1 in [1] in which the ideas seem more clear due 
      to the simpler setting. Eq 7 (and the follow ups) are the point of concern 
      ( I'm actually not sure how they define C_X|Z; before sec 3 they write 
      mu_X|z = C_X|Z phi(z) so C_X|Z : H -> F; but in the sentence above it 
      is said that C_X|Z acts on z. I think for 7 the phi definition is wrong 
      and they mean the second (?) let's go with this one). They want to 
      condition to extract the conditioning variable and show a low rank of the 
      covariance matrix. I guess the argument is 1) condition 
      with Z and average over Z. 2) Fubini theorem (?) for vector 
      integrals(?) -- I guess technical details, e.g. when can we apply this for 
      vector integrals, are not really of interest to the community and I'm 
      happy to follow the heuristic argument of the authors 3) The next 
      step is then really cryptic. I think what they do is to denote the vector 
      (E_X1|Z=(1 0) [phi(X1)] E_X1|Z=(0 1) [phi(X1)] ) with E_X1|Z [phi(X1)] and 
      then the multiple this with Z itself to regain the conditional 
      expectation. The notation really needs to be cleaned up a lot. 
      Actually it might be better to first go through a short version of Sec 3.1 
      from [1] and just show what changes in the kernel setting. 4) The 
      next step is then to substitute the cond exp vector with C_X1|Z . The 
      whole thing is just super confusing since the notation is not explained 
      and it is up to the reader to guess what the objects are. # 
      I must admit that I found it hard to follow the algorithm 
      discussion in Sec 5/6. E.g. in Sec 5 the svd of A_1 is understandable, but 
      I guess ,this is the trivial part. The main algorithm seems to be then in 
      the sentence: "This leads to the first intermediate tensor G_1 = U_r and 
      we reshape S_r V_r and recursively decompose it" which I admit does not 
      give me much of a picture of what is going on. As far as I get it they 
      split (say for their example Fig 2 c) the problem into the first Z1- X1 
      pair and all the rest and perform an svd on the covariance between the 
      first X1 and this potentially really long tensor. I'm wondering 
      here how this can lead to anything good. This sounds really like a 
      formidable challenge if you have an averaged length HMM, say with d=100, 
      to get anything of relevance from the svd?? # The bounds 
      in sec 7 are a bit odd. First, the statement "More specifically, we will 
      bound, in terms of generalized Frobenius norm || ... ||, the difference 
      between the true kernel embeddings and the low rank kernel embeddings 
      estimated from a set of n iid sample {..} " is misleading, since they make 
      the assumption that they have already low rank approximations of different 
      covariance operators with error at max epsilon. So what they really seem 
      to do here is just to say if the individual estimates are very good then 
      the chained together is not so bad either. But obviously getting these 
      guarantees on the low rank approximations will be a real difficulty. 
      The next thing with the bound is the 1/lambda^(d-2). lambda is the 
      smallest singular value of a family of covariance matrices and d the 
      dimension of the latent variable. I would expect that this lambda can get 
      really small as you go over quite a number of matrices. The authors also 
      argue in a similar line and say that lambda might be misleading and that 
      in experiments the behaviour differs significantly from the exponential 
      dependence of performance on lambda. So this seems to say that 
      under the rather strong conditions they found a bound that is far from 
      tight. Also, in the introduction they motivate with a mixture of 
      Gaussians and argue that their estimate outperforms kernel density 
      estimators. But there seems to be no statements to support this like 
      asymptotic results or bounds. # In general there is 
      significant overlap with the paper [1]. The authors say at one point that 
      it is a kernel generalization of [1]. Some of the arguments look extremely 
      similar like the low rank k thing in Sec 4 and Sec 3.1 in [1]. A clear 
      discussion of what are the significant new findings compared to [1] must 
      be given. # A spell-checker would also be much 
      appreciated, so would be checking the math parts for typos and an overall 
      polishing of the presentation. # The experimental results 
      are the positive aspect of the paper where the method outperforms a number 
      of competitors. # In summary I think that the paper has 
      one main idea which is to kernelize the approach in [1]. The novelty 
      itself does not feel ground breaking due to this. The paper is also 
      lacking in presentation. I can't see people outside a small community to 
      follow this paper through without significant difficulties. I think the 
      main ideas could be nicely summarised in one or two paragraphs but it is 
      currently a pain to extract these; the notation is guesswork and will 
      frustrate a reader who is not from the field or wants to go into details. 
      There is no theory to support the density estimation point they make and 
      the covariance approximation bounds are also not super significant since 
      they make strong assumptions and the bounds seem to be not very tight. 
      Also the link to paper [1] needs to be pointed out clearly with a proper 
      discussion. On the plus side is Table 1 with the experimental results 
      which seem promising. [1] Hierarchical Tensor Decomposition of 
      Latent Tree Graphical Models. Le Song et al 2013 ICML.