Challenge an ICML Paper: For a given set of probability predictions and a log loss value, is the set of true labels giving such a loss unique?

Question

Aggarwal's 2021 ICML paper "Label Inference Attacks from Log-loss Scores", seems to argue that the answer to the question in the title is "YES". The paper claims that, given predicted probability values (such as from a logistic regression or neural network) and the log-loss calculated from those predictions and the true labels, there is an algorithm that will produce the true labels.

This means that the label order giving such a log-loss must be unique. If not, then we could have $\left\{dog, cat, dog, cat\right\}$ and $\left\{dog, dog, cat, cat\right\}$ result in the same log-loss values.

How would the algorithm be able to pick which set of labels is the correct set!?

Coding $dog$ and $0$ and $cat$ as $1$, I believe that I have such an example.

library(ModelMetrics)
p  <- c(0.2, 0.8, 0.8, 0.2)
y0 <- c(0, 1, 0, 1) # dog, cat, dog, cat
y1 <- c(0, 0, 1, 1) # dog, dog, cat, cat
ModelMetrics::logLoss(y0, p) == ModelMetrics::logLoss(y1, p)

Both log-loss values are the same.

The "Results on Real Binary Classification Datasets" section sure makes it look like we can just take a vector of labels and a vector of claimed probability values; calculate the log-loss from the claimed probability values and labels; and perfectly reconstruct the labels, as implied by the, "As our attacks construct..." sentence, yet that is impossible for the p that I gave. There are multiple plausible label vectors (y0 and y).

ICML is one of the top conferences in machine learning, so I do not want to be too quick to dismiss the Aggarwal paper. Nonetheless, I seem to have developed a counterexample.

What's going on?

EDIT

After seeing some answers posted, their claim sounds more plausible, but it still seems to have counterexamples. Consider their example after theorem 1, where $L_v(\sigma)$ is the log loss for true labels $\sigma$ and predictions $v$.

As an example, for N = 5, let v = [2, 3, 5, 7, 11]. Suppose the true labeling is [0, 1, 1, 0, 1]. Then, the adversary observes $L_v(\sigma) = 1/5 \ln ( 2304/ 55 )$ (obtained by plugging in $v$ and $\sigma$ in Equation 2). For reconstructing the labels, observe that $T = 3\times4\times6\times8\times12 = 6912$, so that all we need is to compute primes that divide $T \exp (−NL_v(\sigma)) = 165 = 3 \times 5 \times 11$. This tells us that only the labels for the second, third and fifth datapoints must be 1, which is indeed true.

However, I get multiple possible $\sigma$ values that correspond to the same log-loss value.

library(ModelMetrics)

p  <- c(2, 3, 5, 7, 11)
sigma0 <- c(0, 1, 1, 0, 1) # dog, cat, cat, dog, cat
sigma1 <- c(0, 0, 1, 1, 1) # dog, dog, cat, cat, cat
ModelMetrics::logLoss(sigma0, p) == ModelMetrics::logLoss(sigma1, p)

EDIT 2

Yes, I did make a mistake. This is the correct simulation, and it gives distinct loss values.

v  <- c(2, 3, 5, 7, 11) # The prime number code from the paper
p <- v/(1 + v) # Transform to probability values
sigma0 <- c(0, 1, 1, 0, 1) # dog, cat, cat, dog, cat
sigma1 <- c(0, 0, 1, 1, 1) # dog, dog, cat, cat, cat
ModelMetrics::logLoss(sigma0, p) == ModelMetrics::logLoss(sigma1, p) # Unequal!

Answer 1

Take another look at section 3.1 of the paper.

The 'probability' is not real model output, but a code to hack the response.

Answer 2

The statement from the paper has an important addition

We answer the question in affirmative by showing that for any finite number of label classes, it is possible to infer all of the dataset labels from just the reported log-loss scores if the prediction probability vectors are carefully constructed and this can be done without any model training

You need to use a carefully constructed probability vector $\mathbf{u}$, or otherwise, you won't be able to infer the labels. With your vector you have repeated probabilities so that makes that you get ambiguities. If you have a vector that has no repeated probabilities and more generally no possibilities that linear combinations of the probabilities are the same, then you can infer the true labels $\sigma$ based on the log loss.

The code below demonstrates all the 16 possible log likelihood outcomes when you use the prediction vector

$$\mathbf{u} = (0.413, 0.332, 0.198, 0.057)$$

These outcomes are all unique, and therefore, given that vector $\mathbf{u}$ and the given log loss outcome that it produces, you can reverse engineer the labels $\sigma$ that have been the input.

library(ModelMetrics)
p = c(0.413,0.332,0.198,0.057)
M = matrix(c(0,0,0,0,
             1,0,0,0,
             0,1,0,0,
             1,1,0,0,
             0,0,1,0,
             1,0,1,0,
             0,1,1,0,
             1,1,1,0,
             0,0,0,1,
             1,0,0,1,
             0,1,0,1,
             1,1,0,1,
             0,0,1,1,
             1,0,1,1,
             0,1,1,1,
             1,1,1,1), 16, byrow=TRUE)  ### all 16 possibilities

losses = apply(M, 1, function(y) ModelMetrics::logLoss(y, p))
losses
### output =
# [1] 0.3038833 0.3917776 0.4786716 0.5665659 0.6535937
# [6] 0.7414880 0.8283820 0.9162763 1.0053871 1.0932814
# [11] 1.1801754 1.2680697 1.3550975 1.4429918 1.5298858
# [16] 1.6177801

### with this specific vector p
### we can even convert the possible losses 
### to an integer between 0 and 15
round((losses-0.3038833)/0.08789431) 
### output = 
#  [1]  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15

Answer 3

As my counterexample shows, the answer to the question in the title is that the labels need not be unique.

However, that is not the point of the paper. The paper proposes a method that feeds specific values into the loss function, and the combination of loss value and those specific values reveals the true labels. The values fed into the loss function to do this, however, are not the values from any kind of fitted model; they arise from prime number theory as a way to get the loss function to "confess" what the true labels are.