Sparsistency for inverse optimal transport

Thank you for your comments.

I find that the article doesn't put in enough effort to explain the practical implications of the various theoretical results [...] to provide the reader with a bit more guidance to offer a small interpretation of this quantity.

We have added an ``intuitions'' section to explain the relation between the certificate and optimality conditions. There is also now an "interpretation" after Propositions 8 and 9.

Another example is Proposition 8. It's difficult for me to extract something from this result, [...] I realize that these may be challenging questions, but I find that not much intuition is given, and the practical use of these results does not appear straightforward.

Proposition 8 is the main technical result required for proving Theorem 3 which tells us that sparsistency is possible under the abstract assumption on the certificate. Theoretically proving whether the certificate is nondegenerate is challenging and in this paper, we analyse this condition only in the Gaussian setting (Prop 8 and 9 in the updated version): Some practical insights is that in the small epsilon regime, recoverability is equivalent to recoverability in the graphical lasso setting while for large epsilon, recoverability is approximated by the lasso setting (e.g. diagonal covariance matrix in alpha and beta will always lead to this condition being satisfied). We added comments on ``interpretation'' after Prop 8 and 9. In our opinion, the result here is inline with general intuition that small epsilon leads to more dependent couplings (and hence graphical lasso in the limit) while large epsilon leads to independent couplings, so the interaction matrix recovers has a different interpretation in each setting.

My main criticism concerns the experiments section. I find the experiments too limited and somewhat confusing, [...] There is no legend for the y-axis, and while it's understood to be the certificate value between two nodes, it's unclear how it serves as a good performance measure for the invOT problem.

The purpose of Figure 1 was to numerically illustrate the behaviour of certificates in the Gaussian setting. One of the messages of our analysis is that in the large epsilon regime, the OT coupling becomes increasingly independent and iOT approximates a Lasso problem; in the small epsilon regime, the OT coupling becomes more dependent and iOT approximates graphical Lasso which is ``harder'' for sparsistency. The identity covariance is chosen because in this case, as $\epsilon$ increases, our theory tells us that the certificate becomes nondegenerate so sparsistency will be guaranteed. We added also another figure to illustrate the setting where one attempts to recover a nonsymmetric cost function: the connection to graphical lasso is only in the case of symmetric matrices A and when A is not symmetric, the certificate in fact is not guaranteed to have a limit as epsilon goes to 0; this corroborates with numerical observations made in previous works where it has been noted that the recovery of non-symmetric costs is harder (page 23 https://arxiv.org/pdf/2002.09650.pdf and section 4.4 of https://arxiv.org/pdf/1905.03950.pdf).

Figure 2 is equally unenlightening. It aims to [...] what is the x-axis on these three figures? Is it the number of iterations? The geodesic distance? If it's the geodesic distance, [...] it's unclear how one evolves with the other.

We have added labels to the axis. The x-axis is $\lambda$. For each regularisation parameter $\lambda$, we solve iOT and record the number of wrongly estimated positions.

The conclusion appears to be that the estimation is ``good'' when the entropic regularization is sufficiently large [...] this a result expected by the theory regarding $\epsilon$?

When $\epsilon$ is small, the certificate is degenerate and hence support recovery is unstable. We added a remark on this: `` in particular, one can observe from (7) that for large $\epsilon$, the certificate is trivially non-degenerate whenever $\Sigma_\alpha$, $\Sigma_\beta$ are diagonal."

I'm curious to know whether the Gaussian results really require entropic regularization. Without regularization we also have a closed form: can't we deduce good invOT estimation guarantees in the non-regularized case?

It is true in the $\epsilon=0$ case that the OT coupling has a closed form solution, however, it is unclear how to directly estimate the matrix A from the sample covariance matrix. For instance, the $\ell^1$--iOT method collapses in this case: the optimal transport function $W(A)$ becomes 1-homogeneous in $A$ when $\epsilon=0$, and so, the loss function we have $L(A,\hat \pi)$ is also 1-homogeneous. As a result, if one considers $L(A,\hat \pi) + \lambda\|{A}\|_1$, zero is trivially a solution. So, the $\epsilon=0$ case is challenging because it is unclear if one can apply convex regularization to handle the ill-posedness of the problem.

Thank you for your comments.

Although the sample complexity bound is good, there was no discussion about the tightness of the said bound. I wonder if the is also the best lower bound.

Although we have no rigorous proof of this, the sample complexity of $1/\sqrt{n}$ is known to be tight for the direct estimation of eOT (https://arxiv.org/abs/1905.11882), so it should be expected that this sample complexity rate should also be tight for inverse eOT. We will comment about this in the revised version of the paper.

Observing that the empirical density acts like a ``plug-in" for the unknown true coupled density, can the statistical guarantees of the plug-in be translated to the guarantees for the cost function? Also, do the authors implicitly assume that we can sample from the coupled empirical density? Or do we just have access to some samples?

We assume that we have $n$ iid samples from some probability coupling $\hat\pi$, which is an eOT coupling between $\alpha$ and $\beta$ for some $\epsilon>0$ with underlying cost $c_{\hat A}$. The question we are addressing is whether $\hat A$ can be stably recovered from $n$ samples.

To clarify, we do not observe $\hat \pi = \mathrm{Sink}(c_{\hat A}, \epsilon)$ but only $n$ iid samples $(x_i,y_i)\sim \hat \pi$ and our main result is concerned with the approximation of $\hat A$ (and hence $c_{\hat A}$) by solving the iOT problem with the plug in $\hat \pi_n = \frac{1}{n} \sum_{i=1}^n \delta_{(x_i,y_i)}$. We have modified Section 2.2 to clarify this and moved some of the technical details on how to set up the finite dimensional problem to the appendix.

Questions: Can the authors please elaborate more on the penalty term $\lambda$? Is given for a given problem? Is it shrinking with ?

$\lambda$ is a regularization parameter in our inverse problem which should be balanced with the "noise" (in this case, number of samples) for accurate reconstructions. The relation between lambda and $n$ is given in Theorem 5 where we see that $e^{C/\lambda}/\lambda \leq \sqrt{n}$. So, the smaller lambda is, the larger $n$ needs to be.

Thank you for your comments.

The authors could really afford to improve the pedagogy of the paper, which is quite heavy in terms of notation. Theory is quite involved, require background references to other works such as Carlier or Galichon. The experiment description is a big block which, in my opinion, does not bring as many insights as it could.

We have added an ``intuitions'' section to explain the relation between the certificate and optimality conditions. There is also now an "interpretation" after Propositions 8 and 9. Regarding the experiments, we added an additional example for the anti-symmetric case and clarified the interpretation of the results.

Why does Proposition 8 imply $z_\infty$ is non-degenerate? Why, given its definition 1 line above, is it of the form written in (PrC)?

$z_\infty$ is actually the dual solution for $\lambda$ fixed. It corresponds, in the original submission, to $z^\lambda$ of Proposition 5. We don't claim that $z_\infty$ has the form written in (PrC) in the original solution. What we have is that $\lim_{\lambda \to 0} z_\infty\to z_A^\ast$ and hence, non-degeneracy of $z_A^\ast$ implies that the magnitude of $z_\infty$ outside the support of $A$ is less than one (for $\lambda$ sufficiently small).

We agree with the reviewer that this was not clear in the original submission and we have changed this in the new submission it to make it so.

In prop 9 shouldn't the limit of $\epsilon_n$ be $\infty$ ?

There was in fact a typo and in the $\epsilon\to \infty$ proposition in the Gaussian case. We have corrected this.

In theorem 3, $\hat A$ is such that $\text{Sink}(\hat{A},\epsilon)$ ; this has been introduced earlier but given the large number of variables defined in the paper, it may not hurt to recall it here; in addition, before, Sink was applied to $c$, so it should be $\text{Sink}(c_{\hat{A}},\epsilon$. In prop 10, prop 11 the order of the arguments is reversed.

We agree with the reviewer and we have modified the new submission accordingly.

Can the authors explain the name precertificate'' (what's pre'' about it? Is there a difference with what Dunner and coauthors call ``Dual certificate'' in https://arxiv.org/abs/1602.05205)?

The use of ``pre'' was to make a distinction with the minimal norm certificate defined afterwards. Under non-degeneracy the two are the same but not necessarily in the degenerate case. As this distinction was hurting readability, we have changed the name and reformulated the section. Moreover, we moved to the appendix the connection with duality.

The authors refer to ``condition PrC'', but that is just an equality. Condition PrC would be that the dual norm of the precertificate outside the support is $<\lambda$

We agree with the reviewer and this now reflected in the reformulated section.

what's ``the convex dual of $W (A)$''? convex conjugate of a function (as in Proposition 4)/convex dual of a convex optimization problem?

We agree with the reviewer that this was not the best terminology and we modified it.

is the notation $\langle c,A\rangle$ for a non scalar result?

The notation $\langle c, A\rangle$ corresponds to a function: given a set of fixed cost functions $\lbrace C_1(\cdot,\cdot),\ldots, C_t(\cdot,\cdot)\rbrace$, the notation meant a linear combination of those with coefficients given by the vector $A$, i.e.,

$

\langle c, A\rangle(x,y):= \sum_j A_j C_j(x,y)

$

In fact, $\langle c,A\rangle(\cdot,\cdot)$ was just another notation for $c_A(\cdot,\cdot)$ that was meant to highlight the linear dependence of $c_A(\cdot,\cdot)$ on $A$. Given that it was never re-used, we decided to drop it to avoid confusion with the inner product notation.

In theorem 7 I spent quite some time looking for what the number $m$ was in other parts of the paper (because of the analogy $m/n$ in compressed sensing) before realizing that it was a free paramert; maybe replacing it by $\log(1/\delta)$ is more common (that is only a suggestion).

We welcome the suggestion which was integrated in the new submission.

below 9, in $A_n$ definition, both $\epsilon$'s should be $\epsilon_n$? Same in Prop 11

Yes. This was a typo that is now corrected.

it follows (see e.g. Hiriart-Urruty et al. (1993)) : can you point to a specific result in the book? Also in the bibliography, the authors names appear twice for this book.

the specific result is now mentioned and the bibliography was corrected.

Typos

All the typos suggested by the reviewer were corrected.

Thank you for your comments.

How practical is inverse OT? I understand that the current work considers linear cost functions. Can one, albeit without strong theoretical guarantees, learn a general (perhaps, regular) cost function from the samples drawn from the coupling?

iOT can indeed be applied to recover other types of cost functions. There are works in this direction such as https://arxiv.org/abs/2002.09650 which considers cost functions and Kantorovich potentials given by neural networks. We have cited several of these works in the introduction, but to clarify, we also added a footnote on page 4. Note however that, in this setting it is far from trivial to give theoretical guarantees, our main goal with this work.