Summary
The authors focus on the study of sliced Wasserstein distances.
It consists in projecting measures onto Euclidean lines, such that OT between these projected measures has low complexity because it amounts to sort samples.
The projections are unit vectors of the d-dimensional sphere of R^d, and in practice one samples a set of projections uniformly samples over the unit sphere.
However, this might be sub-efficient since some projections might be redundant by sampling close directions, or uniformative by projecting in directions where measures are similar.
To solve this issue, the authors propose to sample projections non-uniformly. In particular they consider sampling processus satisfying a first-order Markov property.
They propose a sliced OT variant called 'Markovian Sliced Wasserstein'.
They prove metric, weak* convergence and statistical properties.
They propose two families of Markov processes, focusing on orthogonality or data-driven.
They propose a 'burning and thinning' variant to reduce the number of projections and improve complexity.
They run experiments of gradient flows, color transfer and generative learning to illustrate the properties of their losses.
Strengths
- I believe that the directions tackled by the authors is interesting, in that they propose ways to change the sampling process of projections, with the hope that it improves the properties of the discretized sliced divergences in practice.
- The contributions are thorough, with both methodological, theoretical and numerical content on their proposed sliced OT variant.
Weaknesses
Major issues:
- To my mind, the use of a Markov chain does not seem to bring a significant improvement.
Concerning Table 1, after running the gradient flow, all W2 distances are of order of $10^{-5}$, whatever the choosen loss.
The running times are also equivalent up to a factor $2$.
In table 2, the FID and IS scores are not significantly different when we take into account the variance of scores (which is nice to have included it).
My take-home message of these experiments is the negative result (as an open question to prove rigorously) that there exists no sampling process which yields a significantly better error rate of the Monte-Carlo approximation.
However, I acknowledge that exploring this question of sampling is an interesting, and that even absence of significant improvement is a beneficial insight to the ML community.
- Section (3.3) on 'burning and thinning' processes is not sufficiently motivated.
First, is it a standard approach in MCMC sampling ?
If so, could the authors provide references in the main body about this ?
Second, what are the main advantages of doing this ?
There should be a key property highlighting the benefits in the main body, otherwise it looks like a variant with no main benefit.
Except the reduced computational complexity, nothing else is discussed.
If the sampling error rates scale the same as before, I am not motivated by using a more elaborate variant, and would personnally prefer to use a simple yet straightforward algorithm.
Numerical experiment also do not support a significant advantage of using these techniques.
- I have an issue with the proof of Proposition 2.
In the proof there is a term $\log (8 / \delta)$ which somehow disappears when the 'universal constant' C is defined.
However, this term seem not to converge to zero when the number of samples goes to infinity.
Could the authors provide more details on this proof ?
With all due respect to the authors, I am not completely sure of the rigor of the proof yielding this statistical rate.
Minor remarks:
- Line 51: Do we only use one projection to optimize Max-SW via gradient ascent ? It seems to be a terrible idea, probe to fall into local maxima. Also why not solving sliced Wasserstein for a set of random projections and then keep the projection yielding the largest score ?
- Line 62: Do we really need in practice to have a loss which is a distance ? In practice training a model by minimizing a loss which is only definite (e.g. Kullback-Leibler) seems to be suffice.
- Line 222: From what I understand, L is the number of Monte-Carlo chains, and T is the number of projections for a given MC chain. Thus the number of total projections is $T \times L$.
- Line 251: Maybe a notation 'Proj' and not 'Prod' would be more relevant to denote a projection operation.
- Line 263: How do you tune $\kappa$ in the Input-Aware sampling ? Do we need to scale it w.r.t. loss, data, or something else ? Some insights would be welcome here.
- In general figures have legends which are too small to read without zooming significantly. Could the authors increase their size ?
- Line 343: You could comment that this remark on having a larger T is better by connecting it to Proposition 3, since the error scales proportionnaly to $1 / T \sqrt{L}$. Theory indeed show it is more efficient to take T large rather than L.
Questions
See my questions which are detailed above.
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Limitations
They adressed the societal impact of their work.