Answers.Body: <p>You probably are not going to get much faster than cosine similarity, the main reason why your calculations are slow is the fact that you execute your operation <code>batch_size</code><span class="math-container">$^2$</span> times which results in a runtime complexity of <span class="math-container">$O(N^2)$</span> no matter which metric you choose. However, just to test how much of an improvement you will get by a simpler metric, you might just try the <span class="math-container">$\infty$</span>-norm: <span class="math-container">$d(u, v) = \max_i | u_i - v_i |$</span> or the dot product (i.e. cosine similarity without normalizing the vectors). Just to see whether a <em>simpler</em> metric will actually provide you significant performance improvements.</p>
  <p>If you then find out that its not the metric, you can check out <a href="https://arxiv.org/abs/2006.04768" rel="nofollow noreferrer">Linformer by Wang et al.</a>. As you might know the Transformer architecture also compares N vectors pairwisely. Wang et al. deviced a method how to get memory and time complexity from <span class="math-container">$O(N^2)$</span> to <span class="math-container">$O(N)$</span>. This fits your problem exactly, so maybe it is a good read for you.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-05-23T18:46:32.900Z
Answers.Text: Sampling is also a good idea if you can afford missing out on some comparisons - I think the sampling strategy would depend on your usecase. Do you maybe have a prior on the vector similarities which you could use to speed up the process? Can you provide a bit more information on what exactly you want to do? maybe something else comes to mind
Answers.UserDisplayName: Chillston
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-05-24T11:29:32.777Z
Answers.Text: Firstly, nice summary of what you are planning - As this is only a sort of regularization term, I think you should easily get away with sampling in this case. However, by minimizing the pairwise distance between the latent vectors, all vectors should move closer together and ultimately approach some point $p$, right?
Answers.UserDisplayName: Chillston
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-05-24T11:29:58.417Z
Answers.Text: I wonder if you would get similar behavior by just taking the euclidean vector norms instead of the pairwise stuff. If you do that, all vectors should approach the $0$-vector and thus also move closer together. So in the end, the effect should be the same(?). Doing that would also be linear instead of $N^2$. However, I am not sure I completely understand the idea in general: It's not super intuitive to me why term should promote disentanglement. Since you worked with VAEs, you probably know about $\beta$-VAE? Apparently it generates more disentangled representations.
Answers.UserDisplayName: Chillston
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-05-23T09:01:34.463Z
Answers.LastActivityDate: 2023-05-23T09:01:34.463Z
Answers.UserDisplayName: Chillston
Body: <p>I am looking to compute the similarity between a large set of vectors during neural network training - a process that is considerably expensive when choosing the wrong metric. So far, I am making use of cosine similarity, but I found that the training gets slowed down by several orders of magnitude because of that. Each batch, I compute batch_size^2 similarities of vectors with 9000 entries containing non-sparse floating-point numbers. Is there an alternative metric to cosine similarity that is much faster but also differentiable?</p>
  
Tags: <optimization><cosine-similarity>
Title: Cheap differentiable similarity metrics of vectors
UserDisplayName: postnubilaphoebus
ThreadText: # Cheap differentiable similarity metrics of vectors
  
  (Asked by: username_0 on 2023-05-22)
  
  I am looking to compute the similarity between a large set of vectors during neural network training - a process that is considerably expensive when choosing the wrong metric. So far, I am making use of cosine similarity, but I found that the training gets slowed down by several orders of magnitude because of that. Each batch, I compute batch\_size^2 similarities of vectors with 9000 entries containing non-sparse floating-point numbers. Is there an alternative metric to cosine similarity that is much faster but also differentiable?
  
  **Tags:** optimization, cosine-similarity
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2023-05-23. Score: 2 | Accepted answer
  
  You probably are not going to get much faster than cosine similarity, the main reason why your calculations are slow is the fact that you execute your operation `batch_size`$^2$ times which results in a runtime complexity of $O(N^2)$ no matter which metric you choose. However, just to test how much of an improvement you will get by a simpler metric, you might just try the $\infty$-norm: $d(u, v) = \max\_i | u\_i - v\_i |$ or the dot product (i.e. cosine similarity without normalizing the vectors). Just to see whether a *simpler* metric will actually provide you significant performance improvements.
  
  If you then find out that its not the metric, you can check out [Linformer by Wang et al.](https://arxiv.org/abs/2006.04768). As you might know the Transformer architecture also compares N vectors pairwisely. Wang et al. deviced a method how to get memory and time complexity from $O(N^2)$ to $O(N)$. This fits your problem exactly, so maybe it is a good read for you.
  
  > **Comments:**
  > **username_1**: Sampling is also a good idea if you can afford missing out on some comparisons - I think the sampling strategy would depend on your usecase. Do you maybe have a prior on the vector similarities which you could use to speed up the process? Can you provide a bit more information on what exactly you want to do? maybe something else comes to mind  
  > **username_1**: Firstly, nice summary of what you are planning - As this is only a sort of regularization term, I think you should easily get away with sampling in this case. However, by minimizing the pairwise distance between the latent vectors, all vectors should move closer together and ultimately approach some point $p$, right?  
  > **username_1**: I wonder if you would get similar behavior by just taking the euclidean vector norms instead of the pairwise stuff. If you do that, all vectors should approach the $0$-vector and thus also move closer together. So in the end, the effect should be the same(?). Doing that would also be linear instead of $N^2$. However, I am not sure I completely understand the idea in general: It's not super intuitive to me why term should promote disentanglement. Since you worked with VAEs, you probably know about $\beta$-VAE? Apparently it generates more disentangled representations.  
  
  ---
  
  