Thanks for your comments!
Many thanks for acknowledging our rebuttal!
>> The proximal operator is known in closed-form for a huge family of regularizers . See for example [1]
> **Ok, I think I was caught up on if tau = ||Ax||_2^2, then you at least have to solve a linear system with A. But i guess you consider that a small cost, if A is small, and you can compute its SVD easily?**
This is a great question that was on our mind for a while while drafting the idea of the paper.
While it might be natural to start from $\tau_A(z) :=\|Az\|^2$, three things happen when making that choice:
(1) as you mention, one needs to compute an inverse to evaluate the proximal operator. While this can be managed, the real downside is that one would need to differentiate *through* that inverse (more precisely, through a linear system) when computing the Jacobian of our regularizer, i.e. the term $\partial R(\theta)^*[P^\star(\theta)]$ that appears in Eq. 19; This sounds fairly costly.
(2) if one uses loss (Eq.19), then one seeks a projection where, ultimately, $\|Az\|^2$ is small. For very high dimensional data, $p\ll d$, it's usually very easy to find a subspace where "nothing happens", and $\|Az\|^2$ is more or less always zero. Therefore using this approach would likely select small / noisy / uninformative projections, which is somewhat the contrary of what we seek.
(3) In the absence of any constraint on $A$, one would certainly need to deal with the *magnitude* of $A$ in the optimization, as one can imagine that $A$ going to $0$ or $\infty$ may easily impact most relevant objectives.
Taken together, these reasons explain largely why we converged instead towards the definition $\tau_A(z):=\|A^\perp z\|$^2, the norm of $z$ in the **orthogonal** of $A$, with $A$ a matrix in the Stiefel manifold: that way, we get instead that $A$ is where most of the action in the transport occurs, $A$ is easy to optimize and properly normalized.
We have explained this intuition in Appendix A, "More on Subspace Elastic Costs", but given the many questions you have asked, we are now convinced this will benefit from more details.
> > The original MBO paper looked at L1 and k-overlap norms. In our revision, we have added a plot with the k-overlap norm for the ground truth OT map.
> **Is the k overlap norm the same as the latent group norm by Obozinski et al? If so, actually the prox is a bit complex, but the dual norm is often easier to compute. I wonder if that's something you can leverage.**
We believe you refer to Obozinski et al's group overlap norm [1].
The $k$-overlap norm that we use (and which was used in the MBO paper) was proposed in [2] and generalized in [3]. The $k$-overlap norm can be viewed as a L1-norm type regularization that does not suffer from shrinkage.
Because of this, while being still sparse (i.e. most go down or left), the arrows shown in Figure A exhibit more displacements than those shown with the $\ell_1$ norm (second plot of Fig. 1 in the draft), and none stays put.
[1] Laurent Jacob, Guillaume Obozinski, Jean-Philippe VertAuthors, *Group lasso with overlap and graph lasso*, ICML '09:
[2] Andreas Argyriou, Rina Foygel, and Nathan Srebro. *Sparse prediction with the k-support norm*, NIPS, 2012.
[3] Andrew M. McDonald, Massimiliano Pontil, Dimitris Stamos, *Spectral k-Support Norm Regularization*, NIPS 2014
>> The approach outlined in S.5 requires computing Sinkhorn solutions, and differentiate them. This has compute/memory footprint in , where is the batch-size and depends on the regularization in the soft-min. These blocks are very well implemented by now. For hyperparameters, we can think of cross-validation, but this was not used.
> **I think we still need some hard numbers for the numerical experiment section (dataset sizes). Not to say that the experiments provided aren't valuable, and certainly for an OT paper I do expect smaller datasets than for a typical DNN paper, but still, we need a reference.**
This is indeed a very good point, we did not realize we had not given these numbers, we apologize for this oversight. These datasets are part of the Sciplex dataset ([Srivatsan et al. 2020], a science paper), which has gained much popularity in recent years in OT, and is featured prominently in
[4] Bunne et. al, *Learning single-cell perturbation responses using neural optimal transport*, Nature Methods 2023
The data we use has the following size:
| Cell line | Control | Dac | Bel | Quis |
|-----|--------:|------:|------:|------:|
| A549 | 3274 | 558 | 669 | 475 |
| K562 | 3346 | 388 | 656 | 339 |
| MCF7 | 6346 | 1562 | 1684 | 1520 |
For each drug, we therefore have 3 sets of source/target datasets. We average results over these cell-lines.
We have run experiments for 2 other drugs (similar size) as mentioned in our general response. We will report them in the final draft. Our method is substantially better with Givinostat (better than Dac, Bel and Quis shown in draft) and is slightly worse on Hesperadin.