Answers.Body: <p>For each anchor data point <span class="math-container">$x_i^a$</span> in class <span class="math-container">$j$</span>, the intra-distance should be computed <span class="math-container">$g_j$</span> times, where <span class="math-container">$g_j$</span> is the sample size of that class and the inter-distance should be computed as <span class="math-container">$N$</span> times, where <span class="math-container">$N$</span> is the sample size of the dataset. In other words, for each data point, the triplet loss computes all possible distance between the intra-distance and the inter-distance, and the computation cost for <span class="math-container">$x_i^a$</span> should be <span class="math-container">$g_i \cdot N$</span>.</p>
  <p>For the dataset, the total computation cost is  <span class="math-container">$\Sigma_j^c (g_j^2 \cdot N)$</span>.</p>
  <p><span class="math-container">$$
  \begin{align*} O(*) &amp;= \Sigma_j^c (g_j^2 \cdot N) \\      &amp;= N \cdot \Sigma_j^c g_j^2 \\      \end{align*}
  $$</span></p>
  <p>According to the arithmetic mean and quadratic mean inequality[28], <span class="math-container">$\frac{\Sigma_i^n x_i}{n} \leq \sqrt{\frac{\Sigma_i^n x_i^2}{n}}$</span>, when <span class="math-container">$x_1 = x_2 = x_3 ... = x_n$</span> the arithemtic mean is equal to the quadratic mean.</p>
  <p>Therefore,</p>
  <p><span class="math-container">$$
  \begin{align*}N \cdot (\frac{\Sigma_j^c g_j}{c})^2 \cdot c &amp;\leq O(*) &lt; N \cdot \Sigma_j^c N^2 \\N \cdot \frac{N^2}{c} &amp;\leq O(*) &lt; c \cdot N^3 \\ \frac{N^3}{c} &amp;\leq O(*) &lt; c \cdot N^3\\\end{align*}
  $$</span></p>
  <p>The lower boundary of <span class="math-container">$O(*)$</span> is consistent with the paper result.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-11-22T06:49:19.020Z
Answers.LastActivityDate: 2022-11-23T01:32:50.670Z
Answers.LastEditDate: 2022-11-23T01:32:50.670Z
Answers.UserDisplayName: dd123
Body: <p>The triplet loss function uses an anchor, positive, and negative examples. If <span class="math-container">$N$</span> are the number of examples in the training set with <span class="math-container">$C$</span> classes, then I think that the time complexity should be <span class="math-container">$O(NN_cN_{c'})$</span> not <span class="math-container">$O(N^3)$</span> from Probabilistic Machine Learning, Murphy (2022)</p>
  <blockquote>
  <p>Naively minimzing the triplet loss takes <span class="math-container">$O(N^3)$</span> time</p>
  </blockquote>
  <p>Because for every example in the training set, we have <span class="math-container">$N_c$</span> possible positive examples in a class <span class="math-container">$C=c$</span> and <span class="math-container">$N_{c'}$</span> possible negative examples not in class <span class="math-container">$C=c$</span></p>
  <p>(I've seen other research papers used that however with a modification in the denominator: <span class="math-container">$\mathcal{O}(N^3/C)$</span>, where <span class="math-container">$C$</span> is the number of classes)</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-07-10T10:57:56.690Z
Comments.Text: Can you please provide source tha claims that the complexity is $O(N^3)$?
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-07-10T11:06:20.677Z
Comments.Text: @nbro In "Probabilistic Machine Learning, Murphy (2022)" - "Naively minimzing the triplet loss takes $O(N^3)$ time". I've seen other research papers used that however with a modification in the denominator: $O(N^3/C)$ where $C$ is the number of classes
Comments.UserDisplayName: wd violet
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-07-10T11:10:58.730Z
Comments.Text: Please, edit your post to include all this info directly there.
Comments.UserDisplayName: nbro
Tags: <computational-complexity><time-complexity><triplet-loss-function>
Title: Why is the time complexity of the Triplet Loss $O(N^3)$
UserDisplayName: wd violet
ThreadText: # Why is the time complexity of the Triplet Loss $O(N^3)$
  
  (Asked by: username_0 on 2022-07-09)
  
  The triplet loss function uses an anchor, positive, and negative examples. If $N$ are the number of examples in the training set with $C$ classes, then I think that the time complexity should be $O(NN\_cN\_{c'})$ not $O(N^3)$ from Probabilistic Machine Learning, Murphy (2022)
  
  > Naively minimzing the triplet loss takes $O(N^3)$ time
  
  Because for every example in the training set, we have $N\_c$ possible positive examples in a class $C=c$ and $N\_{c'}$ possible negative examples not in class $C=c$
  
  (I've seen other research papers used that however with a modification in the denominator: $\mathcal{O}(N^3/C)$, where $C$ is the number of classes)
  
  **Tags:** computational-complexity, time-complexity, triplet-loss-function
  
  > **Comments:**
  > **username_1**: Can you please provide source tha claims that the complexity is $O(N^3)$?  
  > **username_0**: @username_1 In "Probabilistic Machine Learning, Murphy (2022)" - "Naively minimzing the triplet loss takes $O(N^3)$ time". I've seen other research papers used that however with a modification in the denominator: $O(N^3/C)$ where $C$ is the number of classes  
  > **username_1**: Please, edit your post to include all this info directly there.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2022-11-22. Score: 2 | Accepted answer
  
  For each anchor data point $x\_i^a$ in class $j$, the intra-distance should be computed $g\_j$ times, where $g\_j$ is the sample size of that class and the inter-distance should be computed as $N$ times, where $N$ is the sample size of the dataset. In other words, for each data point, the triplet loss computes all possible distance between the intra-distance and the inter-distance, and the computation cost for $x\_i^a$ should be $g\_i \cdot N$.
  
  For the dataset, the total computation cost is $\Sigma\_j^c (g\_j^2 \cdot N)$.
  
  $$
  \begin{align\*} O(\*) &= \Sigma\_j^c (g\_j^2 \cdot N) \\ &= N \cdot \Sigma\_j^c g\_j^2 \\ \end{align\*}
  $$
  
  According to the arithmetic mean and quadratic mean inequality[28], $\frac{\Sigma\_i^n x\_i}{n} \leq \sqrt{\frac{\Sigma\_i^n x\_i^2}{n}}$, when $x\_1 = x\_2 = x\_3 ... = x\_n$ the arithemtic mean is equal to the quadratic mean.
  
  Therefore,
  
  $$
  \begin{align\*}N \cdot (\frac{\Sigma\_j^c g\_j}{c})^2 \cdot c &\leq O(\*) < N \cdot \Sigma\_j^c N^2 \\N \cdot \frac{N^2}{c} &\leq O(\*) < c \cdot N^3 \\ \frac{N^3}{c} &\leq O(\*) < c \cdot N^3\\\end{align\*}
  $$
  
  The lower boundary of $O(\*)$ is consistent with the paper result.
  
  
  ---
  
  