Why is the time complexity of the Triplet Loss $O(N^3)$

Question

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)

Answer 1

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.