# On Codomain Separability and
Label Inference from (Noisy) Loss Functions

Abhinav Aggarwal
Amazon
<EMAIL_ADDRESS>
&Shiva Prasad Kasiviswanathan
Amazon
<EMAIL_ADDRESS>
&Zekun Xu
Amazon
<EMAIL_ADDRESS>
&Oluwaseyi Feyisetan
Amazon
<EMAIL_ADDRESS>
&Nathanael Teissier
Amazon
<EMAIL_ADDRESS>

###### Abstract

Machine learning classifiers rely on loss functions for performance
evaluation, often on a private (hidden) dataset. Label inference was recently
introduced as the problem of reconstructing the ground truth labels of this
private dataset from just the (possibly perturbed) loss function values
evaluated at chosen prediction vectors, without any other access to the hidden
dataset. Existing results have demonstrated this inference is possible on
specific loss functions like the cross-entropy loss. In this paper, we
introduce the notion of codomain separability to formally study the necessary
and sufficient conditions under which label inference is possible from any
(noisy) loss function values. Using this notion, we show that for many
commonly used loss functions, including multiclass cross-entropy with common
activation functions and some Bregman divergence-based losses, it is possible
to design label inference attacks for arbitrary noise levels. We demonstrate
that these attacks can also be carried out through actual neural network
models, and argue, both formally and empirically, the role of finite precision
arithmetic in this setting.

##  1 Introduction

Consider a situation where a machine learning (ML) modeler is interacting with
a data curator. The data curator owns a private dataset for a classification
task, and the curator agrees to evaluate on this private dataset the
prediction vector (or an ML model) that the modeler submits, and replies back
with loss function values. Such a situation is commonly encountered in machine
learning competition settings like Kaggle111https://www.kaggle.com,
KDDCup222https://www.kdd.org/kdd-cup, and ILSVRC
Challenges333http://www.image-net.org/challenges/LSVRC/. In some competitions,
the features of the private (hold-out) dataset are revealed but not its
labels, and the modeler submits the prediction vector on those features. In
some other competitions, no information about the private dataset is revealed
(i.e., neither the features nor the labels). The modeler submits a model that
is then evaluated on the private dataset. In these settings, it is common for
the curator to return the loss scores to the modeler (such as for the purposes
of fine-turning the models or ranking etc.). A similar situation also appears
when dealing with sensitive datasets, where either labels, or, both features
and labels could be considered sensitive, and again a modeler and curator
interact through loss scores.

In this paper, we investigate if it is possible for a (malicious) modeler to
recover all the private labels using these interactions with the data curator.
More broadly, we investigate the problem of (robust) label inference, where
the goal is to infer the labels of a hidden dataset from just the (noisy) loss
function queries evaluated on the dataset. Our focus will be on a particularly
strong inference attack where the modeler gets just one loss query output,
which could be distorted by noise. Surprisingly, we show that even with just
this single query (and no access to the private feature set), for many common
ML loss functions, our label inference attack succeeds in exactly recovering
all the true labels. This has important ramifications; for example, our
attacks could be used by: a) an unscrupulous participant to an ML competition
who could learn the labels of the hold-out test set in order to construct a
fake model that achieves perfect classification; or b) an adversary to execute
a privacy breach by learning labels associated with a sensitive dataset.444See
our ethics and malpractice statement at the end of this paper.

Overview of Our Results. Our attacks rely on a mathematical notion of codomain
separability of loss functions, which posits that the output of the loss
function is distinct on every possible labeling of the input datapoints. We
assume that the curator that returns the loss scores can add noise to these
scores up to some (known) error bound $\tau$. This noise can also be
introduced as error when the scores are communicated over noisy channels or
computed on low-precision machines. We prove that separating the loss function
outputs by more than $2\tau$ is a necessary and sufficient condition for this
label recovery to be accurate (see Proposition 1), and outline our end-to-end
inference attack in Algorithm LabelInf. We discuss some caveats associated
with running this algorithm on machines with finite floating point precision,
which help explain our experimental findings in Section 5.

The main technical challenge here is to design prediction vectors for which a
loss function demonstrates the required codomain separability for arbitrary
noise levels.555We show that for general functions, determining codomain
separability is co-NP-hard (see Appendix E). We provide constructions of such
vectors for broad classes of functions: multiclass cross-entropy with common
activations (such as sigmoid and softmax) and Bregman divergence-based losses
(see Table 1). In the unnoised setting, the adversary gets the true loss
function score, whereas in the noised setting, the adversary only gets the
loss function score within an absolute error bound. In addition to the single
query model where the adversary has to work with only one (noisy) loss
function value, we also analyze extensions where the adversary has access to
multiple (noisy) loss function values from different prediction vectors. This
extension comes in handy primarily when we look at the local computation time
required by the adversary for the inference attack.

Together, these constructions characterize the vulnerability of loss functions
in leaking private information about the ground truth labels, which we
empirically verify on three publicly available datasets in Section 5.
Additionally, to handle situations where the curator might require a
submission of an actual ML model (and not just the prediction vector), we
provide a construction of a feed-forward neural network, which can be used to
carry out these label inference attacks (see Appendix D).

Table 1: Summary of our label inference results on commonly used ML loss functions. Here, $N$ is the number of labels to be inferred, and $K\geq 2$ is number of label classes. In the multi-query case, our attacks utilize $O(N/\log N)$ queries. Loss Function | $K$ |  Past Work | This Work | Local Computation
---|---|---|---|---
|  1-Query |  Multi-Query
Binary Cross-Entropy | 2 |  Noised [5] | Noised (Thm. 3) |  $O(2^{N})$ |  $O(\mbox{poly}(N))$
K-ary Cross-Entropy | $K$ |  Unnoised [5] | Noised (Thm. 3) |  $O(K^{N})$ |  –
Softmax Cross-Entropy | $K$ |  – | Noised (Sec. 3) |  $O(K^{N})$ |  –
Sigmoid Cross-Entropy | 2 |  – | Noised (Sec. 3) |  $O(2^{N})$ |  $O(\mbox{poly}(N))$
Itakura-Saito Divergence | 2 |  – | Noised (Cor. 2) |  $O(2^{N})$ |  $O(\mbox{poly}(N))$
Squared Euclidean | 2 |  – | Unnoised (Cor. 3) |  $O(2^{N})$ |  $O(\mbox{poly}(N))$
Norm-like Divergence | 2 |  – | Unnoised (Cor. 3) |  $O(2^{N})$ |  $O(\mbox{poly}(N))$
Mahalanobis Divergence | 2 |  – | Noised (Thm. 8) |  $O(2^{N})$ |  –

Central Idea. Our main algorithmic approach is to reduce codomain separability
to the construction of sets with distinct subset sums. Two simple examples of
such sets of size $n$ are $\\{1,2,4,\dots,2^{n-1}\\}$ and $\\{\ln
p_{1},\dots,\ln p_{n}\\}$, where $p_{1},\dots,p_{n}$ are distinct primes. For
the first set, the fact that each subset sum corresponds to representing an
integer in its binary representation suffices to establish the distinction in
the subset sums. For the second set, it suffices to use the fact that each
integer has a unique prime factorization. Sets like these are useful when
characterizing the sufficient conditions under which the required codomain
separability can be achieved. For example, in the binary classification
setting with $N$ datapoints, the following problem comes up often in our
analysis:

$\displaystyle\text{Construct $\theta=[\theta_{1},\dots,\theta_{N}]$ such that
}:\
\min_{\sigma_{1},\sigma_{2}\in\\{0,1\\}^{N}}\left|\sum_{i:\sigma_{1}(i)=1}g(\theta_{i})-\sum_{j:\sigma_{2}(j)=1}g(\theta_{j})\right|\geq
b,$

for some function $g$ and bound $b$. To satisfy this inequality, it suffices
to set $\theta$ such that the set
$g(\theta):=\\{g(\theta_{i}),\dots,g(\theta_{N})\\}$ has all distinct subset
sums. This is because the summation operators essentially filter out subsets
of elements from the vector $\theta$, and because $\sigma_{1}\neq\sigma_{2}$
in the minima operator, these subsets must differ in at least one element.
Now, to ensure that the minimum difference of the subset sums in $g(\theta)$
is at least $b$, one can solve for $g(\theta_{i})=2^{i}b$ or
$g(\theta_{i})=b\ln p_{i}$ (or using some other set with distinct subset sums)
depending on actual form of $g$ and the application.

Related Work. Label inference attacks using loss function values were
introduced in [18, 4], where the focus was primarily on the binary cross-
entropy loss. These attacks range from heuristically solving a min-max
optimization problem [18] to using prime factorization [4] for recovering the
true labeling. However, neither attacks extend to the noised setting. The
problem was partially addressed recently by Aggarwal _et al._ in [5], where
they provide an algorithm for label inference on noisy binary cross-entropy
scores. Even though their approach was not formalized using codomain
separability, their construction also used the idea of making the loss
function outputs distinct for each labeling of the dataset using distinct
subset sums. They also provide an algorithm for label inference from
multiclass cross-entropy scores in the unnoised setting (see Table 1). Our
results not only subsume these, but also significantly extend them. In
addition to covering the case of multiclass cross-entropy with noise, we
examine cross-entropy with various activation functions and Bregman
divergence-based losses that are common in ML applications.

For attacks on leaderboards, such as in Kaggle competitions, Blum and Hardt
demonstrate an adversarial boosting attack in [8], where the adversary
observes loss scores on randomly generated prediction vectors to generate a
labeling which, with probability $2/3$, gives a low loss score. Our focus on
the other hand is on exact label recovery, especially in the noised setting.

An alternate view of our results can be seen through the lens of information
theory. In the standard channel coding problem, the goal is to construct a
coding scheme (in our case, the prediction vector) that takes a message (true
labels), passes it though a noisy channel (loss function), to produce an
output which is then used to infer the message (label inference mechanism). A
standard coding theory goal is to have a high minimum distance between the
codewords (separability). Our idea for using sets with distinct subset sums in
our construction is motivated by similar concepts appearing in information
theory, e.g., coding schemes based on Sidon sequences [15] and Golomb rulers
[17].

Additional Notation. We will denote $[n]=\\{1,2,\dots,n\\}$, use $\mathbb{R}$
for real numbers, $\mathbb{Z}$ for integers, and $\mathbb{Z}^{+}$ for the set
of positive integers. We use $\mathbb{Z}_{K}=\\{0,\dots,K-1\\}$ to denote the
set of integers mod $K$. For any vector $\mathbf{v}=[v_{1},\dots,v_{n}]$, we
use $\mathbf{v}[:a]$ to denote $[v_{1},\dots,v_{a}]$ for $a\in[n]$ and $v_{i}$
to denote the $i$th element in $\mathbf{v}$. Unless specified, all logarithms
use the natural base ($e$). For any set $S\in\mathbb{R}^{n}$, we define
$\mu(S)=\min_{S_{1},S_{2}\subseteq S}\left|\sum_{s_{1}\in
S_{1}}s_{1}-\sum_{s_{2}\in S_{2}}s_{2}\right|$ as the minimum difference
between any two subset sums in $S$. Recall from the discussion of our central
idea above that for any $m>0$, the set $S_{m}:=\\{m2^{i}\mid
i\in\mathbb{Z}_{n}\\}$ (with $|S_{m}|=n$) satisfies $\mu(S_{m})=m$.

##  2 Codomain Separability and Robust Label Inference

We begin our discussion by formally defining the notion of codomain
separability and its connections to the problem of label inference in the
noised and unnoised settings (missing details in Appendix A).

Our objects of interest are functions whose domain is the Cartesian product of
the space of all labelings (defined by the
$\mathbb{Z}_{K}^{N}=\mathbb{Z}_{K}\times\dots\times\mathbb{Z}_{K}\ \text{($N$
times)}=\\{0,\dots,K-1\\}^{N}$) and an arbitrary set
$\Theta\subseteq\mathbb{R}^{N}$. Here, $K\geq 2$ represents the number of
label classes. This formulation captures the common scenario in machine
learning, where we evaluate a loss function using the true labeling in
$\mathbb{Z}_{K}^{N}$ for $N$ datapoints based on a (prediction) vector in
$\mathbb{R}^{N}$ generated by an ML model. $\Theta$ is the space of prediction
vectors, and for $\theta=[\theta_{1},\dots,\theta_{N}]\in\Theta$, the value of
$\theta_{i}$ encodes the label prediction for the $i$th datapoint. For
example, in the case of binary cross-entropy loss (log-loss), we have a
prediction probability vector $\theta\in[0,1]^{N}$ and a labeling
$\sigma\in\\{0,1\\}^{N}$; the loss on $(\sigma,\theta)$ is given by:

$\displaystyle\textsc{CEloss}\left(\sigma,\theta\right)=\frac{-1}{N}\ln\left(\prod_{i=1}^{N}\theta_{i}^{\sigma_{i}}(1-\theta_{i})^{1-\sigma_{i}}\right).$
(1)

In this case, $\theta_{i}$ is the probability assigned to the event
$\sigma_{i}=1$ by the ML model. We work with different loss functions that
place different restrictions on $\Theta$. For example, in the case of
multiclass cross-entropy loss (with $K$ classes), we have
$\Theta\in[0,1]^{N\times K}$.

Codomain Separability. Informally, we call a function codomain separable if
there exists some vector $\theta\in\Theta$ such that the function output on
each $\mathbb{Z}_{K}^{N}$ is distinct (keeping $\theta$ fixed). Thus, when
$\theta$ is known, this one-one correspondence between the function’s output
and the labelings in $\mathbb{Z}_{K}^{N}$ can be exploited to exactly recover
all the labels from just observing the output.

######  Definition 1 ($\tau$-codomain separability).

Let $f:\mathbb{Z}_{K}^{N}\times\Theta\to\mathbb{R}$ be a function. For
$\theta\in\Theta$, define
$\Lambda_{\theta}(f):=\min_{\sigma_{1},\sigma_{2}\in\mathbb{Z}_{K}^{N}}\left|f(\sigma_{1},\theta)-f(\sigma_{2},\theta)\right|$
to be the minimum difference in the function output keeping $\theta$ fixed.
For a fixed $\tau>0$, we say that $f$ admits _$\tau$ -codomain separability_
using $\theta$ if $\Lambda_{\theta}(f)\geq\tau$. In particular, we say that
$f$ admits _$0^{+}$ -codomain separability_ using $\theta$ if there exists any
$\tau>0$ such that $\Lambda_{\theta}(f)\geq\tau$.

Note that, for a fixed $\theta$, if a function is $\tau$-codomain separable,
then it is also $\tau^{\prime}$-codomain separable for $0<\tau^{\prime}<\tau$.
Compared to $\tau$-codomain separability for $\tau>0$, the $0^{+}$-codomain
separability is weaker as it only requires $\Lambda_{\theta}(f)>0$. This
condition is used for label inference in the unnoised case.

As an example for $\tau$-codomain separability, consider the function
$f(\sigma,\theta)=\langle\sigma,\theta\rangle$ for $\sigma\in\\{0,1\\}^{N}$.
To demonstrate $\tau$-codomain separability, it suffices to set
$\theta=[1,2,4,\dots,2^{N-1}]$. Using this, the output $f(\sigma,\theta)$ is
the integer whose binary representation (in reverse) is given by the _bits_
defined in $\sigma$. Moreover, since the difference between any two integers
that can be represented this way is one, it also holds that
$\Lambda_{\theta}(f)=1$, which makes $f$ admit $1$-codomain separability using
$\theta$. Multiplying each entry in $\theta$ by $\tau$ will, thus, make $f$
admit $\tau$-codomain separability for any $\tau>0$.

We highlight that in general, determining whether a loss function is codomain
separable is co-NP-hard However, in the upcoming sections, we discuss our
constructions that make many popular loss functions separable. In Appendix F,
we present some function classes that are provably not $\tau$-codomain
separable.

Robust Label Inference. Next, we formally define the problem of (robust) label
inference from functions defined over the domain
$\mathbb{Z}_{K}^{N}\times\Theta$. Informally, the goal here is to recover some
true labeling (in $\mathbb{Z}_{K}^{N}$) upon observing only the function
output, even if noised. We consider recovery from noised (perturbed) function
outputs in this paper, and the results trivially holds for the unnoised case.

######  Definition 2 ($\tau$-Robust Label Inference).

Let $f:\mathbb{Z}_{K}^{N}\times\Theta\to\mathbb{R}$ be a function. Let
$\sigma^{\star}\in\mathbb{Z}_{K}^{N}$ be an unknown true labeling. For a given
$\tau>0$, we say that $f$ admits $\tau$-robust label inference if there exists
$\theta\in\Theta$ and an algorithm (Turing machine) $\mathcal{A}$ that can
recover $\sigma^{\star}$ given any $\ell\in\mathbb{R}$ where
$\left|f(\sigma^{\star},\theta)-\ell\right|<\tau$, _i.e.,_ for all
$\sigma^{\star}\in\mathbb{Z}_{K}^{N}$, we have
$\mathcal{A}\left(\theta,N,\ell\right)=\sigma^{\star}$.

Observe that the above definition can also work for the unnoised case by
setting $\tau$ arbitrarily small. An important point to note here is that
$\tau$-robust label inference requires perfect reconstruction of
$\sigma^{\star}$, which is a stronger notion than that required by notions
like blatant non-privacy [11], where the goal is to only reconstruct a good
fraction of $\sigma^{\star}$. Also, while the above definition is based on a
single query, we will later relax this requirement to study $\tau$-robust
label inference under a multi-query model.

The following simple proposition formally establishes the connection between
the above definitions of separability and robust label inference. The
proposition is stated for the noised setting.

######  Proposition 1.

A function $f$ admits $\tau$-robust label inference using $\theta\in\Theta$ if
and only if $\Lambda_{\theta}(f)\geq 2\tau$.

In a typical ML setting, assume that we have a server (machine) that holds a
private labeled dataset with labels in $\sigma^{\star}\in\mathbb{Z}_{K}^{N}$.
Let $f:\mathbb{Z}_{K}^{N}\times\Theta\to\mathbb{R}$ denote a (classification)
loss function. In Algorithm LabelInf, we present a general label inference
technique based on Proposition 1. The adversary picks $\theta\in\Theta$ based
on Definition 1, to query the server, and gets back the noisy loss function
value. It then iterates over the labelings to recover the closest one to the
loss value. Throughout this paper, we assume that the adversary knows the loss
function, number of datapoints $N$ and an upper bound $\tau$ on the resulting
error. We also assume that the loss is computed on all labels in
$\sigma^{\star}$.

Input: Number of datapoints $N$, bound on error (noise) $\tau>0$

Output: Recovered labels $\hat{\sigma}$

Model Setting : A server (oracle) with private dataset with true labels
$\sigma^{\star}$

1

2Design a vector $\theta\in\Theta$ with respect to which $f$ admits
$2\tau$-codomain separability (Definition 1).

3 Query the server using $\theta$ as the prediction vector and observe output
$\ell$ with $\left|f(\sigma^{\star},\theta)-\ell\right|<\tau$.

Return
$\hat{\sigma}\leftarrow\arg\min_{\sigma\in\mathbb{Z}_{K}^{N}}\left|f(\sigma,\theta)-\ell\right|$.

Algorithm 1 LabelInf: Robust Label Inference for function
$f:\mathbb{Z}_{K}^{N}\times\Theta\to\mathbb{R}$

######  Remark 1.

A special case of Algorithm LabelInf is the unnoised setting, wherein
$\ell=f(\sigma^{\star},\theta)$. In that case, in Algorithm LabelInf, it
suffices to design a vector $\theta\in\Theta$ with respect to which $f$ admits
$0^{+}$-codomain separability and $\tau$ plays no role (i.e., can be set to an
arbitrarily small positive constant).

An important feature about Algorithm LabelInf is that it makes just one call
to the server to retrieve the (loss) function $f$ evaluated at a single
$\theta$, but still reconstructs the entire private vector (see theorem
below).666To baseline Algorithm LabelInf with a naive exponential search over
the space of all labelings, we simulated label inference on the Titanic
dataset (see Section 5) for the cross-entropy loss, by replacing the
prediction vector $\theta$ from Step 1 in Algorithm LabelInf by a uniformly
random vector in $[0,1]^{N}$. We observed that over 1000 independent runs, the
randomly generated vector failed to correctly infer the true label for even a
single datapoint at even mild noise levels ($\tau=0.1$ and higher).
We also note that the optimization problem
$\arg\min_{\sigma\in\mathbb{Z}_{K}^{N}}\left|f(\sigma,\theta)-\ell\right|$ can
be solved naively by an exponential search over all $\sigma$ in general, and
faster for certain functions under multiple-queries as we discuss in Section
4. Even the exponential search is a local computation for the adversary.

######  Theorem 2.

Let $f:\mathbb{Z}_{K}^{N}\times\Theta\to\mathbb{R}$. Algorithm LabelInf
performs $\tau$-robust label inference on $f$, in that it recovers
$\sigma^{\star}$ (i.e., $\hat{\sigma}=\sigma^{\star}$) from $\ell$ where
$\left|f(\sigma^{\star},\theta)-\ell\right|<\tau$.

Separability in Arbitrary Precision vs. Finite Floating-Point Precision. One
important consideration in our label inference attacks is the precision of
arithmetic that is required at the adversary. In this context, there are two
natural models of arithmetic computation: a) arbitrary precision and b) finite
floating-point precision. Arbitrary precision arithmetic model allows precise
arithmetic results even with very large numbers. In the floating-point
precision model, the arithmetic is constrained by limited precision. An
example of the floating-point precision model is the commonly used IEEE-754
double precision standard. Designing algorithms for standard arithmetic in
both these models have been studied extensively [13, 10]. Following [5], we
refer to the arbitrary precision arithmetic model as $\mathsf{APA}$ and
floating point arithmetic model with $\phi$ bits as $\mathsf{FPA}(\phi)$.

We begin by observing that Definition 1 does not take into account fixed
arithmetic precision (i.e., deals with the case where we have arbitrary
precision arithmetic). Finite floating-point precision has an effect on
separability, as bits of precision places a bound on the resolution. For
example, even if $f(\sigma_{1},\theta)\neq f(\sigma_{2},\theta)$ in the
$\mathsf{APA}$ model, with only $\phi$ bits of precision, this difference may
not be observable. This leads to notion of separability in the
$\mathsf{FPA}(\phi)$ model (formalized in Definition 3, Appendix A). Let
$f_{\phi}$ be the representation of $f$ in the $\mathsf{FPA}(\phi)$
model.777Informally, representation in the $\mathsf{FPA}(\phi)$ model implies
computing $f$ within the granularity defined by $\phi$, and reporting
underflow/overflow when the results are out of range. It is easy to show that
if $f_{\phi}$ admits $\tau$-codomain separability using $\theta$, then $f$
also admits $\tau$-codomain separability in the $\mathsf{APA}$ model using
$\theta$ (see Proposition 2, Appendix A). The other direction is trickier, but
we can establish that if $f$ admits $\tau$-codomain separability in the
$\mathsf{APA}$ model using $\theta$, then $f_{\phi}$ admits $\tau$-codomain
separability using $\theta$ if
$\phi\geq\max(2\log_{2}\tau+5,-2\log_{2}\tau-1)$ (see Proposition 3, Appendix
A).

Moving to label inference, note that Algorithm LabelInf is also described in
the APA model. The above mentioned bound on $\phi$ may not suffice for
$\tau$-robust label inference using Algorithm LabelInf in the
$\mathsf{FPA}(\phi)$ model. This is because unlike codomain separability,
Algorithm LabelInf requires the adversary to compute the loss function on all
labelings of the datapoints, which may require additional bits. For example,
the prediction vector we provide for multiclass cross-entropy loss in Theorem
3 contains entries that are doubly-exponential in $N$ (number of datapoints)
and $K$ (number of classes). This would prohibit the correct computation of
loss scores beyond some values of $N$ and $K$ in the $\mathsf{FPA}(\phi)$
model. However, this issue could be overcome by the ability to perform
multiple queries that we utilize in our experimental evaluation in Section 5.
For simplicity of description, we present our inference attacks under the
$\mathsf{APA}$ model in the main body of this paper.

##  3 $\tau$-Robust Label Inference for Cross-Entropy Loss and its Extensions

We start with establishing $\tau$-codomain separability for multiclass cross-
entropy loss and its variants, for any $\tau>0$. This implies that for these
loss functions, Algorithm LabelInf succeeds in recovering all the labels when
the loss scores are noised by less than $\tau$ in magnitude. We explain our
main results at a high level and defer all missing details from this section
to Appendix B.

Multiclass Cross-Entropy Loss. We first recall the definition of multiclass
cross-entropy (extending Definition 1). We assume $K\geq 2$ classes, and let
$N$ and $\mathbb{Z}_{K}$ denote the number of datapoints and the set of label
classes, respectively. The $K$-ary cross-entropy loss on $\theta$ with respect
to a labeling $\sigma\in\mathbb{Z}_{K}^{N}$ is denoted by
$\textsc{K-CEloss}\left(\sigma,\theta\right)$ and defined as follows:

$\displaystyle\textsc{K-CEloss}\left(\sigma,\theta\right):=\frac{-1}{N}\sum_{i=1}^{N}\sum_{k=0}^{K-1}\
\Big{(}[\sigma_{i}=k]\cdot\ln\theta_{i,k}\Big{)},$ (2)

where $[\sigma_{i}=k]=1$ if $\sigma_{i}=k$ and $0$, otherwise. Here,
$\theta\in\Theta=[0,1]^{N\times K}$ is a matrix of prediction probabilities,
where the $i$th row is the vector of prediction probabilities
$\theta_{i,0},\dots,\theta_{i,K-1}$ (with
$\sum_{k\in\mathbb{Z}_{K}}\theta_{i,k}=1$) for the $i$th datapoint on classes
$0,\dots,K-1$ respectively.

With this definition, we can now describe our construction of a matrix
$\theta\in[0,1]^{N\times K}$ that makes K-CEloss function $2\tau$-codomain
separable for any $\tau>0$ (i.e., $\Lambda_{\theta}(\textsc{K-CEloss})\geq
2\tau$). At a high level, we obtain the required codomain separability for
K-CEloss by designing the entries in the matrix $\theta$ in such a way that
the expression inside the logarithm in (2) reduces to a distinct integer in
some set. This calibration allows us to control the minimum difference in the
output of the cross-entropy loss on different labelings, which we can scale to
the desired amount ($\geq 2\tau$) easily. The following theorem summarizes our
construction.

######  Theorem 3.

Let $\tau>0$. Define matrices $\vartheta,\theta\in\mathbb{R}^{N\times K}$ such
that $\vartheta_{n,k}=3^{\left(2^{(n-1)K+k}N\tau\right)}$ and
$\theta_{n,k}=\vartheta_{n,k}/\sum_{k=1}^{K}\vartheta_{n,k}$. Then, it holds
that K-CEloss is $2\tau$-codomain separable using $\theta$.

The following corollary follows by combining the above result with Theorem 2.

######  Corollary 1.

Using $\theta$ from Theorem 3, Algorithm LabelInf performs $\tau$-robust label
inference from the K-ary cross-entropy loss (K-CEloss).

Note that Theorem 3 only holds for the error $\tau>0$. However, as mentioned
in Remark 1, in the unnoised case it suffices to instantiate Theorem 3 with an
arbitrarily small positive value of $\tau$. We bring to the reader’s attention
the doubly-exponential nature of the entries used to construct the prediction
vector in Theorem 3. This blowup is unfortunately unavoidable for constructing
$\tau$-codomain separability, even for the binary case, as shown in [5,
Theorem 7].

Extensions of Cross-Entropy Loss. Often in practice, when using the cross-
entropy loss to assess the performance of ML models (like CNNs), it is common
to apply an activation function (such as softmax or sigmoid) before the cross-
entropy loss calculation. For example, a common idea in multiclass
classification is to apply the softmax function (to convert any sequence of
real outputs into a probability distribution), defined as follows for
$\sigma\in\mathbb{Z}_{K}^{N}$, $\theta\in[0,1]^{N\times K}$:

$\displaystyle\frac{-1}{N}\sum_{i=1}^{N}\sum_{k=0}^{K-1}\
\Big{(}[\sigma_{i}=k]\cdot\ln\textsc{softmax}(\theta_{i,k})\Big{)},\mbox{
where
}\textsc{softmax}(\theta_{i,k})=\exp(\theta_{i,k})/\sum_{j=1}^{K}\exp(\theta_{i,j}).$

We explain how to extend Theorem 3 to obtain separability in this setting. Our
idea is the following: (1) Let $\theta\in[0,1]^{N\times K}$ be the matrix from
Theorem 3. Recall that by definition, $\theta$ is such that for each
$i\in[N]$, the vector $\theta_{i}\in[0,1]^{K}$ is a probability distribution;
(2) For each $i\in[N]$, solve the following (fully specified) system of
equations for $\theta^{\prime}_{i,k}$’s: for all $k\in\mathbb{Z}_{K},i\in[N]$:
$\exp\left(\theta^{\prime}_{i,k}\right)/\sum_{j=1}^{K}\exp\left(\theta^{\prime}_{i,j}\right)=\theta_{i,k}$.
This is a system of linear equations in the variables
$\exp\left(\theta^{\prime}_{i,j}\right)$, for each $i\in[N]$, hence, can be
solved in polynomial time using standard techniques. Once $\theta^{\prime}$ is
obtained, since $\textsc{softmax}(\theta^{\prime}_{i,k})=\theta_{i,k}$, from
Theorem 3, we get that softmax cross-entropy loss is $2\tau$-codomain
separable using $\theta^{\prime}$; Algorithm LabelInf can now be used for
$\tau$-label inference.

The separability from Theorem 3 also holds if we apply any bijective
activation function before applying the cross-entropy loss. As an example,
consider the sigmoid cross-entropy commonly used in the binary classification
setting (to compresses arbitrary reals into the range $(0,1)$), defined as
follows for $\sigma\in\\{0,1\\}^{N}$, $\theta\in(0,1)^{N}$:

$\displaystyle\frac{-1}{N}\sum_{i=1}^{N}\
\Big{(}\sigma_{i}\ln\left(\textsc{Sigmoid}(\theta_{i})\right)+(1-\sigma_{i})\ln\left(1-\textsc{Sigmoid}(\theta_{i})\right)\Big{)},$
(3)

where $\textsc{Sigmoid}(x)=\left(1+e^{-x}\right)^{-1}$ is the sigmoid
function. Since $\textsc{Sigmoid}:\mathbb{R}\to(0,1)$ is a bijection (and
hence, invertible), given $\textsc{Sigmoid}(x)=y$, we can obtain
$x=\ln(y/(1-y))$. Thus, given the matrix $\theta\in[0,1]^{N\times 2}$ from
Theorem 3, we can construct $\theta^{\prime}\in(0,1)^{N}$ such that
$\theta^{\prime}_{i}=\ln(\theta_{i,1}/(1-\theta_{i,1}))$ for all $i\in[N]$.
Once $\theta^{\prime}$ is obtained, since
$\textsc{Sigmoid}(\theta_{i})=\theta_{i,1}$ and
$1-\textsc{Sigmoid}(\theta_{i})=\theta_{i,2}$ we get that sigmoid cross-
entropy loss is $2\tau$-codomain separable using $\theta^{\prime}$, and hence
Algorithm LabelInf can be used for $\tau$-robust label inference.

##  4 $\tau$-Robust Label Inference for Linearly-Decomposable Binary Losses

The analysis for cross-entropy loss and its extensions above can be
generalized to determine $\tau$-codomain separability for a broad class of
loss functions, defined as follows. Let $g:[0,1]\to\mathbb{R}$ be some
deterministic function. We say that a binary loss function
$f:\\{0,1\\}^{N}\times(0,1)^{N}\to\mathbb{R}$ is linearly-decomposable in
$\\{0,1\\}$ using $g$ if it can be expressed in the following form:

$\displaystyle f(\sigma,\theta)$
$\displaystyle=\frac{1}{N}\left(\sum_{i\in[N]:\sigma_{i}=1}g(\theta_{i})+\sum_{i\in[N]:\sigma_{i}=0}g(1-\theta_{i})\right).$
(4)

Our ideas from the previous section can be used to establish the following
separability result for linearly-decomposable loss functions, hence, enabling
the use Algorithm LabelInf for $\tau$-robust label inference in these cases.
Missing details are presented in Appendix C.1.

######  Theorem 4.

Let $g:[0,1]\to\mathbb{R}$ be some deterministic function and
$f:\\{0,1\\}^{N}\times(0,1)^{N}\to\mathbb{R}$ be a loss function that is
linearly-decomposable in $\\{0,1\\}$ using $g$. Then, for any $\tau>0$, the
function $f$ is $2\tau$-codomain separable if there exists
$\theta\in(0,1)^{N}$ so that $g(\theta_{i})-g(1-\theta_{i})>2^{i}N\tau$ for
all $i\in[N]$.

Some Examples of Linearly-Decomposable Loss Functions. Observe that the KL-
divergence loss (which reduces to binary cross-entropy loss) is of this form,
using $g(\theta_{i})=-\ln\theta_{i}$ (see (C.1), Appendix C.1). Some other
common examples of linearly-decomposable losses include the (i) Itakura-Saito
divergence loss, which can be expressed using
$g(\theta_{i})=1/\theta_{i}+\ln\theta_{i}-2$ (see (7), Appendix C.1); (ii)
squared Euclidean loss, which can be expressed using
$g(\theta_{i})=(1-\theta_{i})^{2}$, (see (8), Appendix C.1); and, (iii) norm-
like divergence loss, which can be expressed using
$g(\theta_{i})=1+(\alpha-1)\theta_{i}^{\alpha}-\alpha\theta_{i}^{\alpha-1}+(\alpha-1)(1-\theta_{i})^{\alpha}$
for some $\alpha\geq 2$ (see (10), Appendix C.1).

Connections to Bregman Divergence. The loss functions mentioned in (i)-(iii)
above are some popular instances of the general class of Bregman divergence-
based loss functions. Unlike the distance metrics for probability
distributions, Bregman divergence [9] does not require its inputs to be
necessarily distributions. Thus, to use these divergences as loss functions,
one can directly compare the outputs of the ML model with the point
distribution from the ground truth labels [14]. We defer the details on our
general result for $\tau$-codomain separability on Bregman divergence,
including that for the Mahalanobis divergence loss (which is not linearly-
decomposable) to Appendix C.2.

Applying Theorem 4. Observe that Theorem 4 immediately allows constructing a
vector that will make a given linearly-decomposable function $f$ admit
$\tau$-codomain separability for a given $\tau>0$: (1) Compute $x^{*}(y)$ as
the solution to $g(x)-g(1-x)=y$; (2) If $x^{*}(y)$ exists, then set
$\theta_{i}=x^{*}(2^{i}N\tau)$ for all $i\in[N]$. This vector $\theta$ can now
be used for $\tau$-robust label inference from $f$ using Algorithm LabelInf.
However, such a $\theta$ might not exist for all loss functions, e.g., it does
not exist for squared Euclidean and norm-like divergence losses, and we will
deal those loss functions later. It does exist though for the Itakura-Saito
divergence loss (defined in (7), Appendix C.1).

######  Corollary 2.

The Itakura-Saito divergence loss is $2\tau$-codomain separable with
$\theta_{i}=(1+3^{2^{i}N\tau})^{-1}$.

Multi-Query Polynomial Time Attacks. The linear-decomposability of $f$ allows
for an efficient multi-query label inference algorithm for $f$. In particular,
we could have a trade-off between the ability to perform multiple queries with
faster computation times for solving the optimization problem solved in Step 3
of Algorithm LabelInf. To see this, observe that setting $\theta_{i}=1/2$
gives $g(\theta_{i})-g(1-\theta_{i})=0$. Thus, if we want to infer the first
$M<N$ labels in a single query, we can set
$\theta=[\theta_{1},\dots,\theta_{M},1/2,\dots,1/2]$ to obtain:

$\displaystyle\Lambda_{\theta}(f)$
$\displaystyle=\frac{1}{N}\min_{\sigma_{1},\sigma_{2}\in\\{0,1\\}^{N}}\left|\sum_{i\leq
M:\sigma_{1}(i)=1}\left(g(\theta_{i})-g(1-\theta_{i})\right)-\sum_{j\leq
M:\sigma_{2}(j)=1}\left(g(\theta_{j})-g(1-\theta_{j})\right)\right|.$

Similar to Theorem 4, choosing $\theta_{i}$ that ensures
$g(\theta_{i})-g(1-\theta_{i})>2^{i}N\tau$ will ensure
$\Lambda_{\theta}(f)>2\tau$. Moreover, using this $\theta$ will ensure that if
$f(\sigma_{1},\theta)=f(\sigma_{2},\theta)$, then
$\sigma_{1}[:M]=\sigma_{2}[:M]$ must hold. Note that after recovering the
first $M$ labels, we can recover the next $M$ labels using
$\theta=[1/2,\dots,1/2,\theta_{M+1},\dots,\theta_{2M},1/2,\dots,1/2]$, and so
on. The result below immediately follows.

(a)

(b)

(c)

Figure 1: Results for $\tau$-robust label inference using Algorithm LabelInf.
Figures (a)-(b) plots the length of vector ($N$) on which Algorithm LabelInf
always succeeds with multiclass cross-entropy loss with 100% and at least 50%
accuracy respectively. Here, Titanic⋆⋆ implements the binary label inference
attack proposed in [5]. Figure (c) plots the same for the softmax cross-
entropy loss at 50% accuracy (wherever computable). The computation time per
inference attack is roughly 10 seconds.

######  Theorem 5.

Let $g:[0,1]\to\mathbb{R}$ be some finite deterministic function and
$f:\\{0,1\\}^{N}\times(0,1)^{N}\to\mathbb{R}$ be a loss function that is
linearly-decomposable in $\\{0,1\\}$ using $g$. Then, for any $\tau>0$ and
integer $M\geq 1$, a sufficient condition for $f$ to admit $\tau$-robust label
inference with $\lceil N/M\rceil$ queries is for the inequality
$g(x)-g(1-x)>2^{i}N\tau$ to have a solution for all $i\in[N]$.

Observe that an $\lceil N/M\rceil$-query algorithm for robust label inference
will require $O(N2^{M}/M)$ local computations by the adversary (using
Algorithm LabelInf in each query). Thus, while the single query case ($M=N$)
required $O(2^{N})$ computations, any multi-query algorithm using $M=O(\log
N)$ requires only $O(\text{poly}(N))$ local computations, which allow a
polynomial-time robust label inference.

Linearly-Decomposable Functions Not Covered by Theorem 4. We now deal with
linearly-decomposable functions for whom there exists no $\theta$ that could
satisfy the condition required in Theorem 4 (examples include, squared
Euclidean and norm-like divergence loss). Here, we establish the weaker
$0^{+}$-codomain separability, which as discussed earlier suffices for label
inference in the unnoised case.

######  Theorem 6.

Let $g:[0,1]\to\mathbb{R}$ be some deterministic function and
$f:\\{0,1\\}^{N}\times(0,1)^{N}\to\mathbb{R}$ be a loss function that is
linearly-decomposable in $\\{0,1\\}$ using $g$. Let $\theta\in(0,1)^{N}$ be
some vector and $S_{\theta}=\\{g(\theta_{i})-g(1-\theta_{i})\\}_{i=1}^{N}$.
Then, the function $f$ is $0^{+}$-codomain separable with respect to $\theta$
if $\mu(S_{\theta})>0$, i.e., all subset sums in the set $S_{\theta}$ are
distinct.

######  Corollary 3.

The squared Euclidean loss is $0^{+}$-codomain separable using
$\theta_{i}=(1/2)\left(1-\ln(p_{i})/N\right)$, where $p_{i}$ is the $i$th
prime number for $i\in[N]$. The norm-like divergence loss for $\alpha\geq 2$
is $0^{+}$-codomain separable using $\theta$ that satisfies
$(1-\theta_{i})^{\alpha-1}-\theta_{i}^{\alpha-1}=(\ln p_{i})/(N\alpha)$.

Finally, the idea behind the multi-query attack mentioned in Theorem 5 also
extends to loss functions covered by Theorem 6, thus, providing a multi-query
polynomial time inference here too.

##  5 Empirical Analysis

We now present our empirical evaluation of label inference attacks on cross-
entropy loss and its extensions (see Appendix G for additional results)888All
experiments are run on a 64-bit machine with 2.6GHz 6-Core processor, using
the standard IEEE-754 double precision format. For reproducibility, the code
is included as part of the supplementary material.. We use the following
datasets for our analysis. As our attacks construct prediction vectors that
are independent of the dataset contents, we ignore the dataset features in our
experiments. All the labels of the dataset are considered for the attack.

(a)

(b)

(c)

(d)

(e)

(f)

Figure 2: Label reconstruction accuracy with multi-query label inference
attack by performing Algorithm LabelInf on $M$ datapoints at a time using a
total of $\lceil N/M\rceil$ queries. Here, $N$ is the total number of rows in
the corresponding dataset (2201 for Titanic, 150 for Iris, and 6430 for
Satellite).

  * $\bullet$

Titanic [3]: a binary classification dataset (2201 rows) on the survival
status of passengers.

  * $\bullet$

Iris [1]: a three-class classification dataset (150 rows) on the Iris species.

  * $\bullet$

Satellite [2]: a six-class classification dataset (6430 rows) on the satellite
images of soil.

We consider three common loss functions mentioned in Section 3: multiclass
cross-entropy, softmax cross-entropy, and sigmoid cross-entropy (deferred to
Appendix G). As a baseline, for the binary labeled dataset (Titanic) with the
cross-entropy loss, we implemented the label inference attack of Aggarwal  _et
al._ [5] (see Theorem 14, Appendix G for a restatement of their main result).

We start with the distinction between our experiments and Algorithm LabelInf,
which is presented in the APA model. For example in the multiclass cross-
entropy loss (K-CEloss) case, to simulate Algorithm LabelInf on a finite
precision machine, we must be able to differentiate $\min_{i,k}\theta_{i,k}$
from 0 (or else the label inference will be ambiguous). A rough analysis (from
Theorem 3) gives that $\phi=\Omega(2^{NK}N\tau)$ bits are required to make
this distinction. This bound hides constant factors and is likely not tight,
but gives an idea of how arithmetic precision plays a role in our experiments.

Figure 1 shows the number of datapoints $N$ recovered by Algorithm LabelInf as
we increase the noise for various loss functions. We sample 1000 random sets
of labels each of length $N$ from the dataset here. At error magnitude
$\tau=1$, the noise is comparable to the actual loss function values computed.
We measure accuracy as the percentage of labels correctly inferred out of $N$.
Figure 1(a) shows that the number of datapoints ($N$) for which 100% label
inference accuracy is achieved for cross-entropy loss decreases as the noise
magnitude ($\tau$) increases, which is expected. Moreover, at the same noise
magnitude, the accuracy also drops as the number of classes ($K$) increases
from 2 (in Titanic) to 6 (in Satellite), which is also expected. These happen
because of the dependence on number of datapoints and number of classes in our
prediction vector construction (Theorem 3), which given fixed machine
precision runs into representation issues. We note that for the Titanic
dataset, the construction from [5] works slightly better (especially at lower
$\tau$ values) than ours due to a small difference in the exponent: it holds
that $\min_{i\in[N]}(-\ln\theta_{i})=\Omega(2^{N}N\tau)$ in [5] (see Theorem
14, Appendix G), but $\Omega(2^{2N}N\tau)$ when using Theorem 3 with $K=2$.

Figures 1(b)-(c) show the number of datapoints on which Algorithm LabelInf
achieves at least 50% accuracy for cross-entropy and softmax cross-entropy
loss. We notice this number is smaller for softmax cross-entropy as compared
to regular cross-entropy (see Figure 1(a)), which is also not surprising.
Through a similar argument as that above for the number of bits required for
cross-entropy loss, one can show that computing the softmax cross-entropy loss
will require an additional $\Omega(NK+\ln(N\tau))$ bits (see the discussion in
Appendix G for details). This additional requirement further constraints the
number of labels that can be recovered with softmax cross-entropy loss.

We also examine a multi-query label inference algorithm in Figure 2. For these
plots, we simulated Algorithm LabelInf on $M<N$ datapoints at a time (instead
of all $N$ datapoints at once), to obtain a total of $\lceil N/M\rceil$
queries. The idea is to use Figure 1 to determine the maximum number of labels
that can be correctly inferred in a single query for a given noise level, and
then perform label inference on only those many datapoints at a time. As
expected, we observed that the accuracy increases with the number of queries:
for cross-entropy loss on Titanic, we achieved 100% accuracy using $M\geq 220$
with $\tau=0.0001$, and $M\geq 550$ with $\tau=1$. The accuracy is again lower
for the softmax case again due to reasons mentioned above.

Concluding Remarks. In this paper, we formalized a notion of codomain
separability of arbitrary loss functions. Through an equivalence established
between this notion and the ability to perform label inference attacks, we
characterize necessary and sufficient conditions for label inference from a
large class of commonly used loss functions in ML, under arbitrary noise
levels. For defending against such attacks, one could consider differentially
private mechanisms for releasing loss scores [12].

An interesting open question is to study the implications of codomain
separability on discrete function optimization (e.g., maximization of
functions defined on $\mathbb{Z}_{K}^{N}$). Intuitively, a large separation in
the function’s output space can be exploited to design algorithms that
converge inside a small neighborhood around the global optimum, which may then
be recoverable using local search.

## References

  * [1] https://www.openml.org/d/41511.
  * [2] https://www.openml.org/d/182.
  * [3] https://www.openml.org/d/40704.
  * Aggarwal et al. [2020] Abhinav Aggarwal, Zekun Xu, Oluwaseyi Feyisetan, and Nathanael Teissier.  On primes, log-loss scores and (no) privacy.  In _Workshop on Privacy in Natural Language Processing at the 2020 Conference on Empirical Methods in Natural Language Processing_ , 2020.
  * Aggarwal et al. [2021] Abhinav Aggarwal, Shiva Kasiviswanathan, Zekun Xu, Oluwaseyi Feyisetan, and Nathanael Teissier.  Label inference attacks from log-loss scores.  In _International Conference on Machine Learning_. PMLR, 2021.
  * Arora and Barak [2009] Sanjeev Arora and Boaz Barak.  _Computational complexity: A Modern Approach_.  Cambridge University Press, 2009.
  * Blass and Gurevich [1982] Andreas Blass and Yuri Gurevich.  On the unique satisfiability problem.  _Information and Control_ , 55(1-3):80–88, 1982\.
  * Blum and Hardt [2015] Avrim Blum and Moritz Hardt.  The ladder: A reliable leaderboard for machine learning competitions.  _arXiv preprint arXiv:1502.04585_ , 2015.
  * Bregman [1967] Lev M Bregman.  The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming.  _USSR computational mathematics and mathematical physics_ , 7(3):200–217, 1967.
  * Brent and Zimmermann [2010] Richard P Brent and Paul Zimmermann.  _Modern computer arithmetic_ , volume 18.  Cambridge University Press, 2010.
  * Dinur and Nissim [2003] Irit Dinur and Kobbi Nissim.  Revealing information while preserving privacy.  In _Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems_ , pages 202–210, 2003.
  * Dwork et al. [2014] Cynthia Dwork, Aaron Roth, et al.  The algorithmic foundations of differential privacy.  _Foundations and Trends® in Theoretical Computer Science_ , 9(3–4):211–407, 2014.
  * Knuth [2014] Donald E Knuth.  _Art of computer programming, volume 2: Seminumerical algorithms_.  Addison-Wesley Professional, 2014.
  * Liu and Belkin [2016] Chaoyue Liu and Mikhail Belkin.  Clustering with bregman divergences: An asymptotic analysis.  In _Proceedings of the 30th International Conference on Neural Information Processing Systems_ , pages 2351–2359. Citeseer, 2016.
  * O’Bryant [2004] Kevin O’Bryant.  A complete annotated bibliography of work related to sidon sequences.  _arXiv preprint math/0407117_ , 2004.
  * Papadimitriou and Yannakakis [1982] Christos H Papadimitriou and Mihalis Yannakakis.  The complexity of facets (and some facets of complexity).  In _Proceedings of the fourteenth annual ACM symposium on Theory of computing_ , pages 255–260, 1982.
  * Robinson and Bernstein [1967] J p Robinson and A Bernstein.  A class of binary recurrent codes with limited error propagation.  _IEEE Transactions on Information Theory_ , 13(1):106–113, 1967.
  * Whitehill [2018] Jacob Whitehill.  Climbing the kaggle leaderboard by exploiting the log-loss oracle.  In _Workshops at the Thirty-Second AAAI Conference on Artificial Intelligence_ , 2018.

## Checklist

  1. 1.

For all authors…

    1. (a)

Do the main claims made in the abstract and introduction accurately reflect
the paper’s contributions and scope? [Yes]

    2. (b)

Did you describe the limitations of your work? [Yes] See Section 5.

    3. (c)

Did you discuss any potential negative societal impacts of your work? [Yes]
See our ethics and malpractice statement.

    4. (d)

Have you read the ethics review guidelines and ensured that your paper
conforms to them? [Yes]

  2. 2.

If you are including theoretical results…

    1. (a)

Did you state the full set of assumptions of all theoretical results? [Yes]
See Section 2.

    2. (b)

Did you include complete proofs of all theoretical results? [Yes] See the
technical appendix.

  3. 3.

If you ran experiments…

    1. (a)

Did you include the code, data, and instructions needed to reproduce the main
experimental results (either in the supplemental material or as a URL)? [Yes]
See the supplemental material.

    2. (b)

Did you specify all the training details (e.g., data splits, hyperparameters,
how they were chosen)? [Yes] See Section 5.

    3. (c)

Did you report error bars (e.g., with respect to the random seed after running
experiments multiple times)? [N/A]

    4. (d)

Did you include the total amount of compute and the type of resources used
(e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Section
5.

  4. 4.

If you are using existing assets (e.g., code, data, models) or
curating/releasing new assets…

    1. (a)

If your work uses existing assets, did you cite the creators? [Yes] See
Section 5.

    2. (b)

Did you mention the license of the assets? [N/A]

    3. (c)

Did you include any new assets either in the supplemental material or as a
URL? [Yes] Code included in the supplementary material.

    4. (d)

Did you discuss whether and how consent was obtained from people whose data
you’re using/curating? [N/A] Datasets we used are publicly available.

    5. (e)

Did you discuss whether the data you are using/curating contains personally
identifiable information or offensive content? [N/A]

  5. 5.

If you used crowdsourcing or conducted research with human subjects…

    1. (a)

Did you include the full text of instructions given to participants and
screenshots, if applicable? [N/A]

    2. (b)

Did you describe any potential participant risks, with links to Institutional
Review Board (IRB) approvals, if applicable? [N/A]

    3. (c)

Did you include the estimated hourly wage paid to participants and the total
amount spent on participant compensation? [N/A]

Ethics and Malpractice Statement. Our paper can be viewed from two different
lenses: exploiting, and information with the intent of protection. On one
hand, the results from our paper demonstrate how to exploit loss scores that
are routinely vended from ML models. This can potentially be leveraged by
malicious attackers who might take these techniques and use them to craft the
prediction vectors used to launch these attacks. The negative effects of these
are as varied as the domains which expose these scores over a classification
API. For example, it can be exploited for financial gains such as with ML
competitions, or to discover the test sets of sensitive models such as in
health domains.

On the other hand, our results call to attention these vulnerabilities which
might be currently under silent exploitation. Armed with this information,
individuals and organizations which vend these seemingly innocuous aggregate
metrics from their classification models, can grasp the potential scope of the
information leakage that can result from this. While this paper did not go
into full details on how to prevent these attacks, the knowledge of it can
lead to tightening of security permissions such as preventing ad-hoc
prediction vectors from running against the models, or requiring other methods
of querying the classification models.

Technical Appendix for “On Codomain Separability
and Label Inference from (Noisy) Loss Functions”

##  Appendix A Missing Details from Section 2

The following proposition states the connection between $\tau$-robust label
inference and $\tau$-codomain separability. This connection, for the specific
case of binary cross-entropy loss, was also noted by [5].

Restatement of Proposition 1. _A function $f$ admits $\tau$-robust label
inference using $\theta\in\Theta$ if and only if $\Lambda_{\theta}(f)\geq
2\tau$._

###### Proof.

We start with one direction and show that if we can do label inference (there
exists algorithm $\mathcal{A}$ in Definition 2), then $\Lambda_{\theta}(f)\geq
2\tau$ must hold. We prove this by contradiction. The idea is to construct a
score from which a unique labeling cannot be unambiguously derived. Without
loss of generality, let $\sigma_{1},\sigma_{2}$ be two distinct labelings for
which $0<f(\sigma_{2},\theta)-f(\sigma_{1},\theta)<2\tau$. It follows that
$f(\sigma_{2},\theta)-\tau<f(\sigma_{1},\theta)+\tau$. Now, let
$\ell=\left(f(\sigma_{1},\theta)+f(\sigma_{2},\theta)\right)/2$ and
$x=\ell-f(\sigma_{1},\theta)$. Clearly, $x<\tau$. Similarly,
$f(\sigma_{2},\theta)-\ell<\tau$. In other words, $\ell$ could be generated by
a $\tau$ magnitude perturbation to both $f(\sigma_{1},\theta)$ and
$f(\sigma_{2},\theta)$ (with $\sigma_{1}\neq\sigma_{2}$). Therefore, there can
exists no algorithm $\mathcal{A}$ that, given just $\ell$, can recover whether
the true label is $\sigma_{1}$ or $\sigma_{2}$ (i.e., no $\mathcal{A}$ can
succeed with $\tau$-robust label inference). This is a contradiction,
therefore,
$\Lambda_{\theta}(f)=\min_{\sigma_{1},\sigma_{2}}\left|f(\sigma_{2},\theta)-f(\sigma_{1},\theta)\right|\geq
2\tau$.

For the other direction, let $\ell$ be as given in Definition 2 with
$\left|f(\sigma^{\star},\theta)-\ell\right|<\tau$. By triangle inequality it
follows that if $\Lambda_{\theta}(f)\geq 2\tau$, then
$\left|\ell-f(\sigma^{\star},\theta)\right|<\min_{\sigma\in\mathbb{Z}_{K}^{N}\setminus\sigma^{\star}}\left|\ell-f(\sigma,\theta)\right|$
(i.e., addition of any noise less than $\tau$ in magnitude will maintain the
invariant that the noised score is closest to the score on the true labeling).
Hence, solving
$\arg\min_{\sigma\in\mathbb{Z}_{K}^{N}}\left|f(\sigma,\theta)-\ell\right|$
will return the true label $\sigma^{\star}$ (which is how Algorithm LabelInf
works). ∎

Details about the $\mathsf{FPA}(\phi)$ Model. For ease of discussion, as in
[5], we assume that in the $\mathsf{FPA}(\phi)$ model, we have $1$ bit for
sign, $(\phi-1)/2$ bits for the exponent and $(\phi-1)/2$ bits for the
fractional part (mantissa). This assumption can be relaxed to accommodate
$\phi_{a}>0$ bits for the exponent and $\phi_{b}>0$ bits for the fractional
part where $\phi_{a}+\phi_{b}=\phi-1$. Furthermore, for any loss function $f$
in the $\mathsf{APA}$ model, we denote by $f_{\phi}$ the algorithm that
computes $f$ on a machine with an instruction set for performing computations
within these $\phi$ bits of precision.

######  Definition 3 ($\tau$-codomain Separability in the $\textsc{FPA}(\phi)$
model).

Let $f:\mathbb{Z}_{K}^{N}\times\Theta\to\mathbb{R}$ be a function. Let
$f_{\phi}$ be the representation of $f$ in the $\textsc{FPA}(\phi)$ model. For
$\theta\in\Theta$, define
$\Lambda_{\theta}(f_{\phi}):=\min_{\sigma_{1},\sigma_{2}\in\mathbb{Z}_{K}^{N}}\left|f_{\phi}(\sigma_{1},\theta)-f_{\phi}(\sigma_{2},\theta)\right|$
to be the minimum difference in the function output keeping $\theta$ fixed.
For a fixed $\tau>0$, we say that $f$ admits _$\tau$ -codomain separability_
using $\theta$ in the $\textsc{FPA}(\phi)$ model if
$\Lambda_{\theta}(f_{\phi})\geq\tau$.

In particular, we say that $f$ admits _$0^{+}$ -codomain separability_ using
$\theta$ in the $\textsc{FPA}(\phi)$ model if there exists any $\tau>0$ such
that $\Lambda_{\theta}(f_{\phi})\geq\tau$.

######  Proposition 2.

Let $f:\mathbb{Z}_{K}^{N}\times\Theta\to\mathbb{R}$, $\theta\in\Theta$, and
$\tau>0$. Let $f_{\phi}$ be the representation of $f$ in the
$\mathsf{FPA}(\phi)$ model. If $f_{\phi}$ admits $\tau$-codomain separability
in the $\mathsf{FPA}(\phi)$ model (using $\theta$) for some $\phi>0$, then $f$
also admits $\tau$-codomain separability in the $\mathsf{APA}$ model using
$\theta$. Moreover, $f_{\phi^{\prime}}$ also admits $\tau$-codomain
separability in the $\mathsf{FPA}(\phi^{\prime})$ model using $\theta$ for all
$\phi^{\prime}>\phi$.

###### Proof.

Given $\theta$ and the fact that $f_{\phi}$ admits $\tau$-codomain
separability using $\theta$ in the $\mathsf{FPA}(\phi)$ model, denote

$\displaystyle\Lambda_{\theta}(f_{\phi})=\min_{\sigma_{1},\sigma_{2}\in\mathbb{Z}_{K}^{N}}\left|f_{\phi}(\sigma_{1},\theta)-f_{\phi}(\sigma_{2},\theta)\right|=b_{\frac{\phi-3}{2}}\cdots
b_{1}b_{0}\ .\ b_{-1}b_{-2}\cdots b_{-\frac{\phi-1}{2}}\geq 2\tau,$

where each bit $b_{i}\in\\{0,1\\}$. Then, in the $\mathsf{FPA}(\phi+1)$ model,
we can write (without loss of generality):

$\displaystyle\Lambda_{\theta}(f_{\phi+1})$
$\displaystyle=\begin{cases}0b_{\frac{\phi-3}{2}}\cdots b_{1}b_{0}\ .\
b_{-1}b_{-2}\cdots b_{-\frac{\phi-1}{2}}&\ \ \text{if $\phi$ is even},\\\
b_{\frac{\phi-3}{2}}\cdots b_{1}b_{0}\ .\ b_{-1}b_{-2}\cdots
b_{-\frac{\phi-1}{2}}0&\ \ \text{if $\phi$ is odd}\end{cases}$
$\displaystyle=b_{\frac{\phi-3}{2}}\cdots b_{1}b_{0}\ .\ b_{-1}b_{-2}\cdots
b_{-\frac{\phi-1}{2}}\geq 2\tau,$

which establishes that $f_{\phi+1}$ is $\tau$-codomain separable using
$\theta$ in the $\mathsf{FPA}(\phi+1)$ model. By induction, this implies that
$f_{\phi^{\prime}}$ admits $\tau$-codomain separation in the
$\mathsf{FPA}(\phi^{\prime})$ model using $\theta$ for all
$\phi^{\prime}>\phi$. In the limit when $\phi\to\infty$, this is equivalent to
saying that $f$ admits $\tau$-codomain separation in the $\mathsf{APA}$ model.
∎

######  Proposition 3.

Let $f:\mathbb{Z}_{K}^{N}\times\Theta\to\mathbb{R}$, $\theta\in\Theta$, and
$\tau>0$. Let $f_{\phi}$ be the representation of $f$ in the
$\mathsf{FPA}(\phi)$ model. If $f$ admits $\tau$-codomain separation in the
$\mathsf{APA}$ model using some $\theta\in\Theta$ and for some $\tau>0$, then
$f_{\phi}$ admits $\tau$-codomain separation in the $\mathsf{FPA}(\phi)$ model
using $\theta$ for $\phi\geq\max(2\log_{2}\tau+5,-2\log_{2}\tau-1)$.

###### Proof.

Suppose $f$ admits $\tau$-codomain separation in the $\mathsf{APA}$ model. To
establish $f_{\phi}$ admits $\tau$-codomain separation in the
$\mathsf{FPA}(\phi)$ model, we need to split the two cases: $\tau>1$ and
$\tau<1$. Represent $\Lambda_{\theta}(f_{\phi})$ in the $\mathsf{FPA}(\phi)$
model as

$b_{\frac{\phi-3}{2}}\cdots b_{1}b_{0}\ .\ b_{-1}b_{-2}\cdots
b_{-\frac{\phi-1}{2}}.$

When $\tau>1$, a sufficient condition for $f_{\phi}$ to satisfy the
$\tau$-codomain separation is to have enough precision before the decimal
point,

$2^{\frac{\phi-3}{2}}\geq 2\tau,$

which gives $\frac{\phi-3}{2}\geq 1+\log_{2}\tau\Longrightarrow\phi\geq
2\log_{2}\tau+5$. When $\tau<1$, a sufficient condition for $f_{\phi}$ to
satisfy $\tau$-codomain separation is to have enough precision after the
decimal point,

$2^{-\frac{\phi-1}{2}}\leq 2\tau,$

which gives $-\frac{\phi-1}{2}\leq
1+\log_{2}\tau\Longrightarrow\phi\geq-2\log_{2}\tau-1$. The proposition
follows from combining the two together to obtain
$\phi\geq\max(2\log_{2}\tau+5,-2\log_{2}\tau-1)$. ∎

##  Appendix B Missing Details from Section 3

Worked out example for $0^{+}$-codomain separability for multiclass cross-
entropy loss. For illustration, we provide a simple example to demonstrate
$0^{+}$-codomain separability for the multiclass cross-entropy loss using a
construction of prediction vector from [5]. Note that in Theorem 3, we
establish that in fact, multiclass cross-entropy loss admits the stronger
notion of $\tau$-codomain separability for any $\tau>0$.

Assume $N=2$ and $K=3$. Construct a matrix $\theta$ with first row
$[\frac{2}{10},\frac{3}{10},\frac{5}{10}]$ and second row
$[\frac{7}{31},\frac{11}{31},\frac{13}{31}]$. Observe that these vectors are
chosen using unique prime numbers in the numerator (the denominator is for
normalizing the sum to 1), the reasoning for which will be clear shortly.
Using $\theta$, one can prove that the cross-entropy loss will be distinct for
every labeling by observing that the terms inside the logarithm, that are
chosen for the outer sum in (2), are distinct for all labelings. For example,
if the true labeling is $[0,2]$, then we obtain
$\textsc{K-CEloss}([0,2];\theta)=-\frac{1}{2}\left(\ln\frac{2}{10}+\ln\frac{13}{31}\right)=-\frac{1}{2}\ln\left(\frac{2\cdot
13}{10\cdot 31}\right)$. Similarly, if the true labeling is $[1,0]$, then we
obtain
$\textsc{K-CEloss}([1,0];\theta)=-\frac{1}{2}\left(\ln\frac{3}{10}+\ln\frac{7}{31}\right)=-\frac{1}{2}\ln\left(\frac{3\cdot
7}{10\cdot 31}\right)$. The use of primes makes this selection of summands in
the K-CEloss score uniquely defined by the true labeling. This follows as the
only thing that changes in the K-CEloss score based on the true labeling is
the numerator in the $\ln$ term, which is a product of primes based on true
labeling. Since the product of primes has a unique factorization, we can
recover which primes were used from the product, and since each entry in the
matrix $\theta$ is associated with a unique prime, this recovers the true
labels.

Missing proofs. We show that the (multiclass) $K$-ary cross-entropy loss is
$\tau$-codomain separable for any $\tau>0$.

Restatement of Theorem 3. _Let $\tau>0$. Define matrices
$\vartheta,\theta\in\mathbb{R}^{N\times K}$ such that_

$\vartheta_{n,k}=3^{\left(2^{(n-1)K+k}N\tau\right)}\mbox{ and
}\theta_{n,k}=\vartheta_{n,k}/\sum_{k=1}^{K}\vartheta_{n,k}.$

_Then, it holds that K-CEloss is $2\tau$-codomain separable using $\theta$._

###### Proof.

We begin by simplifying the expression for
$\textsc{K-CEloss}\left(\theta,\sigma\right)$ (2) to write it as a sum of two
terms: one dependent on the labeling $\sigma$, and the other independent of
this labeling.

$\displaystyle\textsc{K-CEloss}\left(\theta,\sigma\right)$
$\displaystyle=\frac{-1}{N}\sum_{i=1}^{N}\sum_{k=1}^{K}\
\Big{(}[\sigma_{i}=k]\cdot\ln\theta_{i,k}\Big{)}=\frac{-1}{N}\left(\underbrace{\sum_{i=1}^{N}\ln\vartheta_{i,\sigma_{i}}}_{\begin{subarray}{c}\text{Labeling
Dependent}\\\
\text{Term}\end{subarray}}-\underbrace{\sum_{i=1}^{N}\ln\left(\sum_{k=1}^{K}\vartheta_{i,k}\right)}_{\begin{subarray}{c}\text{Labeling
Independent}\\\ \text{Term}\end{subarray}}\right).$ (5)

Using (5), we then obtain the following:

$\displaystyle\Lambda_{\theta}(\textsc{K-CEloss})$
$\displaystyle=\min_{\sigma_{1},\sigma_{2}\in\mathbb{Z}_{K}^{N}}\left|\textsc{K-CEloss}\left(\theta,\sigma_{1}\right)-\textsc{K-CEloss}\left(\theta,\sigma_{2}\right)\right|$
$\displaystyle=\min_{\sigma_{1},\sigma_{2}\in\mathbb{Z}_{K}^{N}}\frac{1}{N}\left|\sum_{i=1}^{N}\
\Big{(}\ln\theta_{i,\sigma_{1}(i)}\Big{)}-\sum_{i=1}^{N}\
\Big{(}\ln\theta_{i,\sigma_{2}(i)}\Big{)}\right|$
$\displaystyle=\min_{\sigma_{1},\sigma_{2}\in\mathbb{Z}_{K}^{N}}\frac{1}{N}\left|\sum_{i=1}^{N}\
\Big{(}\ln\vartheta_{i,\sigma_{1}(i)}\Big{)}-\sum_{i=1}^{N}\
\Big{(}\ln\vartheta_{i,\sigma_{2}(i)}\Big{)}\right|$
$\displaystyle=\min_{\sigma_{1},\sigma_{2}\in\mathbb{Z}_{K}^{N}}(\tau\ln
3)\left|\sum_{i=1}^{N}2^{(i-1)K+\sigma_{1}(i)}-\sum_{i=1}^{N}2^{(i-1)K+\sigma_{2}(i)}\right|\geq
2\tau\ln 3>2\tau.$

Here, the third step follows from the fact that the label-independent term in
the cross-entropy loss gets canceled when taking the difference inside the
modulus. The last step follows from the fact that since
$\sigma_{1}\neq\sigma_{2}$, each summand inside the modulus represents a
distinct even integer in $[2^{NK}]$, and hence, the difference is at least
one. ∎

##  Appendix C Missing Details from Section 4

Restatement of Theorem 4. _Let $g:[0,1]\to\mathbb{R}$ be some deterministic
function and $f:\\{0,1\\}^{N}\times(0,1)^{N}\to\mathbb{R}$ be a loss function
that is linearly-decomposable in $\\{0,1\\}$ using $g$. Then, for any
$\tau>0$, the function $f$ is $2\tau$-codomain separable using any
$\theta\in(0,1)^{N}$ for which $g(\theta_{i})-g(1-\theta_{i})>2^{i}N\tau$ for
all $i\in[N]$._

###### Proof.

We begin by observing that (4) can be rewritten as follows:

$\displaystyle f(\sigma,\theta)$
$\displaystyle=\frac{1}{N}\sum_{i=1}^{N}\left(\sigma_{i}g(\theta_{i})+(1-\sigma_{i})g(1-\theta_{i})\right)$
$\displaystyle=\frac{1}{N}\left(\sum_{i:\sigma(i)=1}\left(g(\theta_{i})-g(1-\theta_{i})\right)+\sum_{i=1}^{N}g(1-\theta_{i})\right).$

For any $\theta\in(0,1)^{N}$, we can then write the following:

$\displaystyle\Lambda_{\theta}(f)$
$\displaystyle=\min_{\sigma_{1},\sigma_{2}\in\\{0,1\\}^{N}}\left|f(\sigma_{1},\theta)-f(\sigma_{2},\theta)\right|$
$\displaystyle=\frac{1}{N}\min_{\sigma_{1},\sigma_{2}\in\\{0,1\\}^{N}}\left|\sum_{i:\sigma_{1}(i)=1}\left(g(\theta_{i})-g(1-\theta_{i})\right)-\sum_{j:\sigma_{2}(j)=1}\left(g(\theta_{j})-g(1-\theta_{j})\right)\right|$

If for all $i\in[N]$, it holds that
$g(\theta_{i})-g(1-\theta_{i})=2^{i}N\tau(1+\delta)$ for some $\delta>0$,
then:

$\displaystyle\Lambda_{\theta}(f)$
$\displaystyle=(2\tau(1+\delta))\min_{\sigma_{1},\sigma_{2}\in\\{0,1\\}^{N}}\left|\sum_{i:\sigma_{1}(i)=1}2^{i-1}+\sum_{j:\sigma_{1}(j)=1}2^{j-1}\right|=2\tau(1+\delta)>2\tau,$

where the last step holds because $\sigma_{1}\neq\sigma_{2}$. ∎

Restatement of Theorem 6. _Let $g:[0,1]\to\mathbb{R}$ be some deterministic
function and $f:\\{0,1\\}^{N}\times(0,1)^{N}\to\mathbb{R}$ be a loss function
that is linearly-decomposable in $\\{0,1\\}$ using $g$. Let
$\theta\in(0,1)^{N}$ be some vector and
$S_{\theta}=\\{g(\theta_{i})-g(1-\theta_{i})\\}_{i=1}^{N}$. Then, the function
$f$ is $0^{+}$-codomain separable with respect to $\theta$ if
$\mu(S_{\theta})>0$, i.e., all subset sums in the set $S_{\theta}$ are
distinct._

###### Proof.

From the definition of linear-decomposability, we can write:

$\displaystyle f(\sigma,\theta)$
$\displaystyle=\frac{1}{N}\left(\sum_{i\in[N]:\sigma_{i}=1}g(\theta_{i})+\sum_{i\in[N]:\sigma_{i}=0}g(1-\theta_{i})\right)$
$\displaystyle=\frac{1}{N}\sum_{i\in[N]}\left(\sigma_{i}g(\theta_{i})+(1-\sigma_{i})g(1-\theta_{i})\right)=\frac{1}{N}\sum_{i\in[N]}\left(\sigma_{i}\left(g(\theta_{i})-g(1-\theta_{i})\right)+g(1-\theta_{i})\right)$
$\displaystyle=\frac{1}{N}\sum_{i\in[N]:\sigma_{i}=1}\left(g(\theta_{i})-g(1-\theta_{i})\right)+\frac{1}{N}\sum_{i=1}^{N}g(1-\theta_{i}).$

Using this reformulation, we can compute $\Lambda_{\theta}(f)$, for any
$\theta\in(0,1)^{N}$, as follows:

$\displaystyle\Lambda_{\theta}(f)=\frac{1}{N}\min_{\sigma_{1},\sigma_{2}\in\\{0,1\\}^{N}}\left|\sum_{i\in[N]:\sigma_{1}(i)=1}\left(g(\theta_{i})-g(1-\theta_{i})\right)-\sum_{j\in[N]:\sigma_{2}(j)=1}\left(g(\theta_{j})-g(1-\theta_{j})\right)\right|.$

Thus, ensuring that
$S_{\theta}:=\\{g(\theta_{i})-g(1-\theta_{i})\\}_{i=1}^{N}$ satisfies
$\mu(S_{\theta})>0$ will ensure that $\Lambda_{\theta}(f)>0$. ∎

###  C.1 Bregman Divergence-based Binary Losses

Given a continuously differentiable strictly convex function
$F:\mathcal{S}\to\mathbb{R}$ over some closed convex set
$\mathcal{S}\subseteq\mathbb{R}^{d}$, the Bregman divergence
$D_{F}:\mathcal{S}\times\mathcal{S}\to\mathbb{R}$ associated with $F$ is
defined as
$D_{F}(\mathbf{p},\mathbf{q})=F(\mathbf{p})-F(\mathbf{q})-\langle\nabla
F(\mathbf{q}),\mathbf{p}-\mathbf{q}\rangle$.

We will focus on the binary case for our discussion in this section and assume
that the domain of $F$ is the closed convex set $[0,1]^{N}$.

Kullback-Leibler Divergence Loss. The (generalized) Kullback-Leibler (KL)
divergence between vectors
$\mathbf{p},\mathbf{q}\in\mathcal{S}\subseteq\mathbb{R}^{d}$ is defined as:

$D_{\text{KL}}(\mathbf{p},\mathbf{q})=\sum_{i\in[d]}p_{i}\ln\frac{p_{i}}{q_{i}}-\sum_{i\in[d]}(p_{i}-q_{i}),$

where $\mathbf{p}=(p_{1},\dots,p_{d})$ and $\mathbf{q}=(q_{1},\dots,q_{d})$.

For a binary classification setting, considering the $i$th datapoint, we have
the true label $\sigma_{i}\in\\{0,1\\}$ and $\theta_{i}\in(0,1)$ which is the
probability assigned to the event $\sigma_{i}=1$ by the ML model. In that
case, we have

$D_{\text{KL}}([\sigma_{i},1-\sigma_{i}],[\theta_{i},1-\theta_{i}])=-\sigma_{i}\ln\theta_{i}-(1-\sigma_{i})\ln(1-\theta_{i}).$

Summing over the $N$ datapoints (and dividing by $N$) gives the Kullback-
Leibler divergence loss,

$\displaystyle\textsc{KLLoss}(\sigma,\theta)$
$\displaystyle=\frac{1}{N}\sum_{i=1}^{N}D_{\text{KL}}([\sigma_{i},1-\sigma_{i}],[\theta_{i},1-\theta_{i}])=\frac{-1}{N}\sum_{i=1}^{N}\sigma_{i}\ln\theta_{i}+(1-\sigma_{i})\ln(1-\theta_{i})$
$\displaystyle=\frac{-1}{N}\left(\sum_{i:\sigma_{i}=1}\ln\theta_{i}+\sum_{i:\sigma_{i}=0}\ln(1-\theta_{i})\right),$
(6)

which is exactly the binary cross-entropy loss (1)999Here, we adopt the notion
that $0\ln 0=0$, so that KL divergence is well-defined. and is therefore
covered by results in Section 3.

Itakura-Saito Divergence Loss. The Itakura-Saito divergence for vectors
$\mathbf{p},\mathbf{q}\in\mathcal{S}\subseteq\mathbb{R}^{d}$ is defined as:

$D_{\text{IS}}(\mathbf{p},\mathbf{q})=\sum_{i\in[d]}\left(\frac{p_{i}}{q_{i}}-\ln\frac{p_{i}}{q_{i}}-1\right),$

where $\mathbf{p}=(p_{1},\dots,p_{d})$ and $\mathbf{q}=(q_{1},\dots,q_{d})$.

For a binary classification setting, considering the $i$th datapoint, we have
the true label $\sigma_{i}\in\\{0,1\\}$ and $\theta_{i}\in(0,1)$, which is the
probability assigned to the event $\sigma_{i}=1$ by the ML model. In this
case, based on $D_{\text{IS}}$, the Itakura-Saito divergence loss is defined
as:

$\displaystyle\textsc{ISLoss}(\sigma,\theta)=\frac{1}{N}\left(\sum_{i:\sigma_{i}=1}\left(\frac{1}{\theta_{i}}+\ln\theta_{i}-1\right)+\sum_{i:\sigma_{i}=0}\left(\frac{1}{1-\theta_{i}}+\ln(1-\theta_{i})-1\right)\right)$
(7)

The above equation shows the linear decomposability of this loss, therefore,
Theorem 4 can be applied to get the following result.

Restatement of Corollary 2. _The Itakura-Saito divergence loss ( ISLoss) is
$2\tau$-codomain separable with
$\theta_{i}=\left(1+3^{2^{i}N\tau}\right)^{-1}$._

###### Proof.

We apply Theorem 4 here. For the Itakura-Saito divergence loss in (7), we
begin by noticing that for $x\in\left(0,1/2\right)$, it holds that

$\frac{1}{x}-\frac{1}{1-x}+\ln\frac{x}{1-x}>\ln\frac{1-x}{x}>0.$

Thus, since

$g(\theta_{i})-g(1-\theta_{i})=\frac{1}{\theta_{i}}-\frac{1}{1-\theta_{i}}+\ln\left(\frac{\theta_{i}}{1-\theta_{i}}\right)$

for this loss, it suffices to ensure that
$\ln\left(\frac{1-\theta_{i}}{\theta_{i}}\right)>2^{i}N\tau$ for Theorem 4 to
apply. In particular, we solve
$\ln\left(\frac{1-\theta_{i}}{\theta_{i}}\right)=2^{i}N\tau\ln 3$ to obtain
$\theta_{i}=\left(1+3^{2^{i}N\tau}\right)^{-1}$. Note that $\theta_{i}<1/2$ as
needed above. ∎

Squared Euclidean Loss. The squared Euclidean divergence for vectors
$\mathbf{p},\mathbf{q}\in\mathcal{S}\subseteq\mathbb{R}^{d}$ is defined as:

$\displaystyle
D_{\text{SE}}(\mathbf{p},\mathbf{q})=\sum_{i\in[d]}\left(\left|p_{i}-q_{i}\right|^{2}\right),$
(8)

where $\mathbf{p}=(p_{1},\dots,p_{d})$ and $\mathbf{q}=(q_{1},\dots,q_{d})$.

Again for the binary classification setting, considering the $i$th datapoint,
we get the following expression for this loss:

$D_{\text{SE}}([\sigma_{i},1-\sigma_{i}],[\theta_{i},1-\theta_{i}])=2\|\sigma_{i}-\theta_{i}\|^{2}.$

Summing over the $N$ datapoints (and dividing by $N$, and ignoring the factor
of $2$), we get the squared Euclidean loss as follows:

$\displaystyle\textsc{SELoss}(\sigma,\theta)$
$\displaystyle=\frac{1}{N}\left(\sum_{i:\sigma_{i}=1}\left|\sigma_{i}-\theta_{i}\right|^{2}+\sum_{i:\sigma_{i}=0}\left|\sigma_{i}-\theta_{i}\right|^{2}\right)=\frac{1}{N}\left(\sum_{i:\sigma_{i}=1}(1-\theta_{i})^{2}+\sum_{i:\sigma_{i}=0}\theta_{i}^{2}\right).$
(9)

In this case, there exists no $\theta$ such that the condition of Theorem 4 is
satisfied. However, we can still use Theorem 6 to establish $0^{+}$-codomain
separability.

Restatement of the first part of Corollary 3. _The squared Euclidean loss (
SELoss) is $0^{+}$-codomain separable using
$\theta_{i}=(1/2)\left(1-\ln(p_{i})/N\right)$, where $p_{i}$ is the $i$th
prime number._

###### Proof.

To apply Theorem 6 to the squared Euclidean loss, we have
$g(\theta_{i})=(1-\theta_{i})^{2}$, which gives
$g(\theta_{i})-g(1-\theta_{i})=1-2\theta_{i}$. Setting this to $\frac{\ln
p_{i}}{N}$, where $p_{i}$ is the $i$th prime number, ensures that
$\mu(S_{\theta})>0$. Equivalently, $\theta_{i}=\frac{1}{2}\left(1-\frac{\ln
p_{i}}{N}\right)$ works. ∎

Note that the proof above assumes that $\theta\in(0,1)^{N}$. We show in
Theorem 11 that restricting $\theta$ to $\\{0,1\\}^{N}$ prohibits
$\tau$-codomain separability for any $\tau>0$.

Norm-like Divergence Loss. The norm-like divergence for vectors
$\mathbf{p},\mathbf{q}\in\mathcal{S}\subseteq\mathbb{R}^{d}$ and $\alpha\geq
2$ is defined as:

$D_{\text{NL}}(\mathbf{p},\mathbf{q})=\sum_{i\in[d]}\left(p_{i}^{\alpha}+(\alpha-1)q_{i}^{\alpha}-\alpha
p_{i}q_{i}^{\alpha-1}\right),$

where $\mathbf{p}=(p_{1},\dots,p_{d})$ and $\mathbf{q}=(q_{1},\dots,q_{d})$.
Again for binary classification, considering the $i$th datapoint, we get the
following expression for this loss:

$D_{\text{NL}}([\sigma_{i},1-\sigma_{i}],[\theta_{i},1-\theta_{i}])\\\
=\left(\sigma_{i}^{\alpha}+(\alpha-1)\theta_{i}^{\alpha}-\alpha\sigma_{i}\theta_{i}^{\alpha-1}+(1-\sigma_{i})^{\alpha}+(\alpha-1)(1-\theta_{i})^{\alpha}-\alpha(1-\sigma_{i})(1-\theta_{i})^{\alpha-1}\right).$

Summing over the $N$ datapoints (and dividing by $N$), and simplifying gives
the norm-like divergence loss.

$\textsc{NLLoss}(\sigma,\theta)=\frac{1}{N}\big{(}\sum_{i:\sigma_{i}=1}\left(1+(\alpha-1)\theta_{i}^{\alpha}-\alpha\theta_{i}^{\alpha-1}+(\alpha-1)(1-\theta_{i})^{\alpha}\right)\\\
+\sum_{i:\sigma_{i}=0}\left(1+(\alpha-1)(1-\theta_{i})^{\alpha}-\alpha(1-\theta_{i})^{\alpha-1}+(\alpha-1)\theta_{i}^{\alpha}\right)\big{)}.$
(10)

Again while Theorem 4 is not applicable in this case, Theorem 6 is applicable.

Restatement of the second part of Corollary 3. _The norm-like divergence loss
( NLLoss) for $\alpha\geq 2$ is $0^{+}$-codomain separable using $\theta$
where: $(1-\theta_{i})^{\alpha-1}-\theta_{i}^{\alpha-1}=(\ln p_{i})/(N\alpha)$
with $p_{i}$ as the $i$th prime number._

###### Proof.

Here we have
$g(\theta_{i})=1+(\alpha-1)\theta_{i}^{\alpha}-\alpha\theta_{i}^{\alpha-1}+(\alpha-1)(1-\theta_{i})^{\alpha}$,
which gives
$g(\theta_{i})-g(1-\theta_{i})=\alpha((1-\theta_{i})^{\alpha-1}-\theta_{i}^{\alpha-1})$.
Similar to above, setting $g(\theta_{i})-g(1-\theta_{i})=\frac{\ln p_{i}}{N}$
suffices. This is equivalent to finding a solution to the following equation,
which has a unique solution in $(0,1)$ for any fixed $\alpha\geq 2$:

$(1-\theta_{i})^{\alpha-1}-\theta_{i}^{\alpha-1}=\frac{\ln p_{i}}{N\alpha}.$

It is easy to see that such a $\theta_{i}<1/2$ exists. ∎

###  C.2 A General Result for Bregman Divergence

Similar to the general construction of robust label inference for linearly-
decomposable functions in Section 4, we now demonstrate $\tau$-robust label
inference for a special class of Bregman divergences: the ones associated with
functions $F$ that are additive on the elements of its input vector.

######  Theorem 7.

Let $F:(0,1)^{2}\to\mathbb{R}$ be a strictly convex function that can be
written in the form $F(\mathbf{v})=\sum_{i=1}^{2}h(v_{i})$ for some
differentiable function $h:(0,1)\to\mathbb{R}$. Let $D_{F}$ denote the Bregman
divergence associated with $F$, and
$f_{F}:\\{0,1\\}^{N}\times(0,1)^{N}\to\mathbb{R}$ be the corresponding loss
function, defined as
$f_{F}(\sigma,\theta)=(1/N)\sum_{i=1}^{N}D_{F}([\sigma_{i},1-\sigma_{i}],[\theta_{i},1-\theta_{i}])$.
Then, for $\tau>0$, the function $f_{F}$ is $2\tau$-codomain separable if
there exists $\theta\in(0,1)^{N}$ that satisfies
$h^{\prime}(\theta_{i})+h^{\prime}(1-\theta_{i})>2^{i}N\tau$ for all
$i\in[N]$, where $h^{\prime}(x)=dh/dx$.

###### Proof.

From the definitions of $F$ and $f_{F}$ in the theorem statement, we can
simplify the expression for $f_{F}$ as follows:

$\displaystyle Nf_{F}(\sigma,\theta)$
$\displaystyle=\sum_{i=1}^{N}D_{F}([\sigma_{i},1-\sigma_{i}],[\theta_{i},1-\theta_{i}])=\sum_{i=1}^{N}\left(A_{i}\sigma_{i}+B_{i}\right),$

where $A_{i}=h^{\prime}(\theta_{i})+h^{\prime}(1-\theta_{i})$ and
$B_{i}=h(0)+h(1)-(h(\theta_{i})+h(1-\theta_{i}))-\theta_{i}(h^{\prime}(\theta_{i})+h^{\prime}(1-\theta_{i}))$.
Using this, we can compute, for any $\theta\in(0,1)^{N}$ the following:

$\displaystyle\Lambda_{\theta}(f_{F})$
$\displaystyle=\min_{\sigma_{1},\sigma_{2}\in\\{0,1\\}^{N}}\frac{1}{N}\left|\sum_{i=1}^{N}A_{i}\sigma_{1}(i)-\sum_{j=1}^{N}A_{j}\sigma_{2}(j)\right|=2\tau(1+\delta)>2\tau,$

which follows by setting $A_{i}=2^{i}N\tau(1+\delta)$ for some $\delta>0$. ∎

Codomain Separability for Mahalanobis Divergence Loss. Not all Bregman
divergences are additive in the sense of Theorem 7. A popular example of a
Bregman divergence that is not additive is the Mahalanobis divergence, which,
for vectors $\mathbf{p},\mathbf{q}\in\mathcal{S}\subseteq\mathbb{R}^{d}$ is
defined as:

$D_{\text{MH}}(\mathbf{p},\mathbf{q})=\frac{1}{2}(\mathbf{p}-\mathbf{q})^{\top}A(\mathbf{p}-\mathbf{q}),$

where $A$ is a positive definite matrix.

As in the case of other divergence, for binary classification, the Mahalanobis
divergence loss can be defined as:

$\textsc{MHLoss}(\sigma,\theta)=\frac{1}{N}\sum_{i=1}^{N}([\sigma_{i},1-\sigma_{i}]-[\theta_{i},1-\theta_{i}])^{\top}A([\sigma_{i},1-\sigma_{i}]-[\theta_{i},1-\theta_{i}])\mbox{
where}A\in\mathbb{R}^{2\times 2}.$

We discuss $\tau$-robust label inference for the Mahalanobis loss function in
the theorem below.

######  Theorem 8.

Let $A=\bigl{[}\begin{smallmatrix}a&b\\\
c&d\end{smallmatrix}\bigr{]}\in\mathbb{R}^{2\times 2}$ be a positive definite
matrix with $(a+d)>(b+c)$. Denote $\alpha=a+d-(b+c)$ and let
$\tau\in[0,\alpha/N)$. Then, for any $\tau>0$, the Mahalanobis loss (defined
above) is $2\tau$-codomain separable using any $\theta\in(0,1)^{N}$ with
$\|\theta\|_{\infty}\leq(1/2)\left(1-N\tau/\alpha\right)$.

###### Proof.

We begin by noticing that for $A=\left[\begin{matrix}a&b\\\
c&d\end{matrix}\right]$, we can write
$([\sigma_{i},1-\sigma_{i}]-[\theta_{i},1-\theta_{i}])^{\top}A([\sigma_{i},1-\sigma_{i}]-[\theta_{i},1-\theta_{i}])=\alpha(\sigma_{i}-\theta_{i})^{2}$.
Thus, for a given $\theta\in(0,1)^{N}$, we can compute the magnitude of the
difference
$\textsc{MHLoss}(\sigma_{1};\theta)-\textsc{MHLoss}(\sigma_{2};\theta)$ as
follows:

$\displaystyle\Lambda_{\theta}(\textsc{MHLoss})$
$\displaystyle=\min_{\sigma_{1},\sigma_{2}\in\\{0,1\\}^{N}}\frac{\alpha}{N}\left|\sum_{i=1}^{N}\left(\sigma_{1}(i)-\theta_{i}\right)^{2}-\left(\sigma_{2}(i)-\theta_{i}\right)^{2}\right|$
$\displaystyle=\min_{\sigma_{1},\sigma_{2}\in\\{0,1\\}^{N}}\frac{\alpha}{N}\left|\sum_{i:\sigma_{1}(i)\neq\sigma_{2}(i)}(1-2\theta_{i})\right|=\min_{\sigma_{1},\sigma_{2}\in\\{0,1\\}^{N}}\left[\frac{\alpha}{N}\sum_{i:\sigma_{1}(i)\neq\sigma_{2}(i)}(1-2\theta_{i})\right],$

where the last equation can be satisfied by restricting
$\theta\in(0,1/2)^{N}$. Now, since $\sigma_{1}$ and $\sigma_{2}$ must differ
in at least one element, it holds that
$\Lambda_{\theta}(\textsc{MHLoss})\geq\min_{i}\frac{\alpha}{N}(1-2\theta_{i})$.
Thus, for $2\tau$-codomain separability, it suffices to set
$\min_{i}\frac{\alpha}{N}(1-2\theta_{i})\geq 2\tau$, which gives
$\max_{i}\theta_{i}\leq\frac{1}{2}-\frac{N\tau}{\alpha}$. ∎

##  Appendix D A Neural Network to Imitate Robust Label Inference

The results in Sections 3 and 4 highlight how prediction vectors ($\theta$’s)
could be generated that succeed with $\tau$-robust label inference. Typically,
these prediction vectors are output of a ML model, and in many scenarios
(e.g., ML contests held by Kaggle and other platforms) the submission to the
server is not the prediction vector but rather the ML model itself. This
raises an interesting question, whether the prediction vectors utilized in
these label inference attacks can actually be an output of a “natural” looking
ML model?101010Technically, we can have a constant function that on all inputs
generate the prediction vectors required for the attack. However, that we all
can agree is not a “natural” ML model.

Formally, we ask: Is there a feed-forward neural network, that for any input
$\mathbf{v}$ recovers the ground truth $\sigma_{\mathbf{v}}$ through only one
query to the server for the loss function value? We now show that this is
possible for any codomain separable loss function.

Setup. Assume a classification problem on $K$ classes. We will design a multi-
layer feed-forward neural network MutNet using following specifications. (1)
The input to MutNet is a vector $\mathbf{v}\in\mathbb{R}^{d_{1}}$ with true
label $\sigma_{\mathbf{v}}\in\mathbb{Z}_{K}$. (2) The output of MutNet is a
vector in $(0,1)^{d_{2}}$ that represents an encoding of the prediction. Let
$f:\mathbb{Z}_{K}\times(0,1)^{d_{2}}\to\mathbb{R}$ be a loss function. The
goal of the network is to ensure that on any input $\mathbf{v}$ the network
generates an output $\mathbf{u}_{m+1}$ such that $f$ admits $2\tau$-codomain
separability using $\mathbf{u}_{m+1}$. Consequently, for any input
$\mathbf{v}$, given a noisy value of
$f(\sigma_{\mathbf{v}},\mathbf{u}_{m+1})$, an adversary can use Algorithm
LabelInf to infer $\sigma_{\mathbf{v}}$.

Our Mutator Network. We construct a 2-layer network
$\textsc{MutNet}_{\mathbf{x}}:\mathbb{R}^{d_{1}}\to(0,1)^{d_{2}}$ that can
convert any real vector $\mathbf{v}\in\mathbb{R}^{d_{1}}$ into any desired
fixed vector $\mathbf{x}\in(0,1)^{d_{2}}$. The transformations we use in this
network are the ReLU and Sigmoid activation functions: one layer of the former
and one layer of the latter. Let $M_{1}\in\mathbb{R}^{d_{1}\times d_{1}}$ and
$M_{2}\in\mathbb{R}^{d_{1}\times d_{2}}$ be matrices such that all entries in
$M_{1}$ are negative (the entries in $M_{2}$ can be arbitrary). Let
$\mathbf{x}^{\prime}$ be a vector such that $x^{\prime}_{i}=\ln
x_{i}/(1-x_{i})$. Then, for an input vector $\mathbf{v}$, the transformations
in $\textsc{MutNet}_{\mathbf{x}}$ are as follows:

$\displaystyle\centering\mathbf{u}_{1}=\mathbf{v},\;\;\mathbf{u}_{2}=\textsc{ReLU}\left(\mathbf{v}^{\top}M_{1}\right),\;\;\mathbf{u}_{3}=\
\textsc{Sigmoid}\left(\mathbf{u}_{2}^{\top}M_{2}+\mathbf{x}^{\prime}\right),\@add@centering$
(11)

where ReLU and Sigmoid are applied element-wise on their input vectors.
Effectively, this construction inhibits the propagation of $\mathbf{v}$ by
outputting the same vector $\mathbf{u}_{3}=\mathbf{x}$ always (i.e., the
output of $\textsc{MutNet}_{\mathbf{x}}$ equals $\mathbf{x}$ for all inputs
$\mathbf{v}$). By setting $\mathbf{x}$ to the desired (prediction vector)
$\theta$ with respect to which $f$ admits $2\tau$-codomain separability, we
get the following result

######  Theorem 9.

Let $\tau>0$ and let $\theta\in(0,1)^{d_{2}}$ be such that
$f:\\{0,1\\}^{d_{2}}\times(0,1)^{d_{2}}\to\mathbb{R}$ is $2\tau$-codomain
separable using $\theta$. Then, for any input $\mathbf{v}\in(0,1)^{d_{2}}$,
given $\ell$ such that
$\left|f(\sigma_{\mathbf{v}},\textsc{MutNet}_{\theta}(\mathbf{v}))-\ell\right|\leq\tau$,
Algorithm LabelInf recovers $\sigma_{\mathbf{v}}$.

###### Proof.

It suffices to show that for given $\theta\in(0,1)^{d_{2}}$ and any
$\mathbf{v}\in(0,1)^{d_{2}}$, the construction above ensures that
$\textsc{MutNet}_{\theta}(\mathbf{v})=\theta$. To see this, observe that since
all entries in $M_{1}$ are negative, the product $\mathbf{v}^{\top}M_{1}$ has
non-positive entries. Thus, when ReLU is applied to $\mathbf{v}^{\top}M_{1}$
(element-wise), the output is the zero vector. This zero vector, when fed into
the Sigmoid, produces the desired output $\theta$ since $\mathbf{x}^{\prime}$
in (11) is constructed in a way such that
$\textsc{Sigmoid}(\mathbf{x}^{\prime})=\theta$ (element -wise). ∎

##  Appendix E Computational Hardness of Codomain Separability

We now show that that determining the codomain separability is co-NP-
hard.111111See [6] for a definition of co-NP-hard. We establish the result for
the weaker notion of $0^{+}$-codomain separability (Definition 1) and restrict
ourselves to functions of the form
$f:\\{0,1\\}^{N}\times\mathbb{Z}_{+}^{N}\to\mathbb{R}$, where the decision
problem is to determine whether there exists a $\theta\in\mathbb{Z}_{+}^{N}$
such that $f$ is $0^{+}$-codomain separable using $\theta$. We denote this
decision problem by Codomain-Separability. Note that this automatically
implies that determining the $\tau$-codomain separability of such functions is
also co-NP-hard.

Let $\Phi(x_{1},\dots,x_{N})$ be a Boolean formula over $N$ variables in the
3-CNF form $\Phi(x_{1},\dots,x_{N})=C_{1}\land\dots\land C_{N}$, where $C_{i}$
are disjunctive clauses containing 3 literals each. We say that
$\Phi(x_{1},\dots,x_{N})$ is an _almost tautology_ if there are at least
$2^{N}-1$ satisfying assignments for $\Phi$. In other words, there is at most
one assignment of the variables that makes $\Phi(x_{1},\dots,x_{N})$ false.
Define Almost-Tautology to be the problem of determining if a given Boolean
formula is an almost tautology.

######  Lemma 1.

Almost-Tautology is co-NP-complete.

###### Proof.

We first show that Almost-Tautology is in co-NP, i.e., any certificate that
$\Phi$ is not an almost-tautology can be checked in polynomial time. To see
this, observe that such a certificate must contain at least two distinct
assignments for which $\Phi$ is not satisfied, which can be verified
efficiently.

To show that Almost-Tautology is co-NP Hard, there are two cases: either
$\Phi$ is a tautology, or there is exactly one assignment that does not
satisfy $\Phi$. Deciding the former is co-NP-hard [6]. For the latter,
consider the logical negation $\lnot\Phi(x_{1},\dots,x_{N})$. If $\Phi$ is an
almost tautology (but not a tautology), then there is exactly one satisfying
assignment for $\lnot\Phi$. This is the same as the Unique-SAT problem, in
which we determine if a Boolean formula has a unique solution. This problem is
also co-NP-hard [16, 7], and hence, Almost-Tautology is co-NP-hard. ∎

We start with an arbitrary Boolean formula $\Phi(x_{1},\dots,x_{N})$. For
$\theta\in\mathbb{Z}_{+}^{N}$, define the following function:

$f_{\Phi}(\sigma,\theta)=\hat{C}_{1}^{\theta_{1}}\cdots\hat{C}_{N}^{\theta_{N}}p_{1}^{\sigma_{1}}\cdots
p_{N}^{\sigma_{N}},$

where $p_{1},\dots,p_{N}\geq 5$ are distinct prime numbers, and
$\hat{C}_{i}=C_{i}(\sigma)$ in the additive form (i.e., mapping all variables
to $\\{0,1\\}^{N}$ by representing all negative literals $\bar{x}_{i}$ as
$1-x_{i}$, and converting all disjunctions to addition). For example, if
$C_{1}=(x_{3}\lor\bar{x}_{4}\lor x_{6})$, then
$\hat{C}_{1}=C_{1}(\sigma)=\sigma_{3}+(1-\sigma_{4})+\sigma_{6}$. Another
example is as follows: assume $\Phi(x_{1},x_{2},x_{3})=(\bar{x}_{1}\lor
x_{2}\lor x_{3})\land(x_{1}\lor x_{2}\lor\bar{x}_{3})$. Then, first repeat the
third clause in $\Phi$ to make the number of clauses the same as the number of
variables to obtain $\Phi(x_{1},x_{2},x_{3})=(\bar{x}_{1}\lor x_{2}\lor
x_{3})\land(x_{1}\lor x_{2}\lor\bar{x}_{3})\land(x_{1}\lor
x_{2}\lor\bar{x}_{3})$. Now, the corresponding function can be written as
follows:

$\displaystyle
f_{\Phi}(\sigma,\theta)=5^{\sigma_{1}}7^{\sigma_{2}}11^{\sigma_{3}}(1-\sigma_{1}+\sigma_{2}+\sigma_{3})^{\theta_{1}}(1+\sigma_{1}+\sigma_{2}-\sigma_{3})^{\theta_{2}+\theta_{3}}.$
(12)

We now prove our hardness result for $0^{+}$-codomain separability using this
reduction.

######  Lemma 2.

For any $\theta\in\mathbb{Z}_{+}^{N}$ and distinct
$\sigma_{1},\sigma_{2}\in\\{0,1\\}^{N}$, it holds that
$f(\sigma_{1},\theta)\neq f(\sigma_{2},\theta)$ if and only if at least one of
$\sigma_{1}$ or $\sigma_{2}$ satisfies $\Phi$. Here, we abuse the notation to
represent the Booleans True and False by $1$ and $0$, respectively.

###### Proof.

Observe that for any distinct $\sigma_{1},\sigma_{2}\in\\{0,1\\}^{N}$, we have
$f(\sigma_{1},\theta)=f(\sigma_{2},\theta)$ only when there is some set of
clauses $\hat{C}_{i}$ and $\hat{C}_{j}$ such that
$\hat{C}_{i}(\sigma_{1})=\hat{C}_{i}(\sigma_{2})=0$, i.e. they are unsatisfied
by $\sigma_{1}$ and $\sigma_{2}$, respectively. This is because the product of
the primes satisfies
$\prod_{i=1}^{N}p_{i}^{\sigma_{1}(i)}\neq\prod_{j=1}^{N}p_{j}^{\sigma_{2}(j)}$
(since both products differ in at least one prime – the one corresponding to
the index of the element at which $\sigma_{1}$ and $\sigma_{2}$ differ). The
lemma statement then follows from the contrapositive of this result. ∎

######  Theorem 10.

Codomain-Separability is co-NP-hard.

###### Proof.

We prove this by demonstrating a Karp reduction from the Almost-Tautology
problem, which we showed is co-NP-complete in Lemma 1. Let
$\Phi(x_{1},\dots,x_{N})$ be an arbitrary Boolean formula and
$f_{\Phi}(\sigma,\theta)$ be the corresponding function from (12). Now, for
$\Phi$ to be an almost tautology, there can at most one unsatisfying solution:
(1) if there are no unsatisfying solutions, then for any Boolean assignment of
$x_{1},\dots,x_{N}$, all clauses in $\Phi(x_{1},\dots,x_{N})$ must be
satisfied and hence, from Lemma 2, the value of $f_{\Phi}(\sigma,\theta)$ must
also be distinct for all $\sigma$, implying that $f_{\Phi}$ is
$0^{+}$-codomain separable; (2) if there is an unsatisfying assignment, then
the value of $f_{\Phi}(\sigma,\theta)$ at this assignment must be zero, and it
is non-zero at all other assignments. This also implies that $f_{\Phi}$ is
$0^{+}$-codomain separable. Lastly, let $\theta$ be a vector with respect to
which $f_{\Phi}$ is $0^{+}$-codomain separable. This immediately implies that
$\Phi(x_{1},\dots,x_{N})$ must be an almost tautology — if not, then either
one of (1) or (2) must be false since there will be at least two unsatisfying
assignments in this case, implying that the function $f_{\Phi}$ will be zero
on at least two inputs. ∎

##  Appendix F Some Negative Results on $\tau$-codomain Separability

We now show certain loss functions are not $\tau$-codomain separable. This
complements our positive results on $\tau$-codomain separability for cross-
entropy and its variants, and Bregman divergence based losses. These negative
results on codomain separability rules out label inference in these cases,
because of the connections between these two notion established in Proposition
1.

Discrete $L_{p}$-losses. We start with the simple $L_{p}$-loss defined on the
discrete domain and show it is not $\tau$-codomain separable for any $\tau>0$.

######  Theorem 11.

For any $p>0$, the function $f:\\{0,1\\}^{N}\times\\{0,1\\}^{N}\to\mathbb{R}$
of the form $f(\sigma,\theta)=\left|\left|{\theta-\sigma}\right|\right|_{p}$
is not $\tau$-codomain separable for any $\tau>0$.

###### Proof.

Fix some $\theta\in\\{0,1\\}^{N}$. For any $\sigma\in\\{0,1\\}^{N}$, let
$I(\sigma,\theta)=\\{i\in[N]\ |\ \sigma(i)\neq\theta(i)\\}$ be the set of
indices on which $\sigma$ and $\theta$ differ. Then, we can simplify the
expression for $f$ as follows:

$\displaystyle
f(\sigma,\theta)=\left(\sum_{i=1}^{N}\left|\theta(i)-\sigma(i)\right|^{p}\right)^{1/p}=\left(\sum_{i\in
I(\sigma,\theta)}\left|\theta(i)-\sigma(i)\right|^{p}\right)^{1/p}=\left|I(\sigma,\theta)\right|^{1/p}.$

Now, let $\sigma_{1},\sigma_{2}\in\\{0,1\\}^{N}$ be such that they differ from
$\theta$ in exactly one label, i.e.,
$|I(\sigma_{1},\theta)|=|I(\sigma_{2},\theta)|=1$ and hence,
$f(\sigma_{1},\theta)=f(\sigma_{2},\theta)=1$. Note that for any choice of
$\theta$, there are $N-1$ such labelings. Thus, $\Lambda_{\theta}(f)=0$. ∎

Set-valued Functions. We now study set-valued loss functions. These are
functions that are expressed with respect to a fixed set, as a mapping from
subsets of this set to the real line. For example, in our context of codomain
separability (in the binary classification setting), the set of interest is
that of the $N$ datapoints, and the subsets are interpreted as comprising of
those that have been assigned label $1$. For example, if $N=3$ and the subset
is $\\{1,3\\}$, then this would represent the case where datapoints $1$ and
$3$ have labels $1$, and datapoint $2$ has label $0$. As we will see, this
generalization helps compute upper bounds on the magnitude of noise that will
admit label inference (in a single query) using any prediction vector.

We now present our main results in this section. For the discussion here, we
will assume $\Omega=\\{s_{1},\dots,s_{N}\\}$ to denote a set and $2^{\Omega}$
to denote the power set of $\Omega$. As mentioned before, since the sets of
interest in our application can be thought of as the labels for the
datapoints, we will assume $|\Omega|=N$, unless mentioned otherwise.

######  Theorem 12.

Let $\Omega=\\{s_{1},\dots,s_{N}\\}$ be a set. Let
$f:2^{\Omega}\times\Theta\to\mathbb{R}_{+}$ be a function and
$\theta\in\mathbb{R}^{N}$ be such that $f(\cdot,\theta)$ is monotonic, i.e.,,
for all $A\subseteq B\subseteq[N]$, it holds that $f(A,\theta)\leq
f(B,\theta)$. Then, $f$ is not $\tau$-codomain separable using $\theta$ for
any

$\tau>\min_{B\subset[N]}\min_{j\not\in
B}\left(\frac{f(B\cup\\{j\\},\theta)-f(B,\theta)}{2}\right).$

In particular, if $f(\emptyset,\theta)=0$, then $f$ is not $\tau$-codomain
separable using $\theta$ for any
$\tau>\frac{1}{2}\left(\min_{j\in[N]}f(\\{j\\},\theta)\right)$.

###### Proof.

Fix some $\sigma\in[0,1]^{N}$. Then, for $f$ to be $\tau$-codomain separable
using $\sigma$, it must hold that:

$\displaystyle\forall B\subset[N],j\not\in B.\ \ \ \ \
\left|f(B\cup\\{j\\},\theta)-f(B,\theta)\right|\geq 2\tau$
$\displaystyle\Longrightarrow$ $\displaystyle\forall B\subset[N].\ \ \ \ \
\tau\leq\frac{1}{2}\left(\min_{j\not\in
B}f(B\cup\\{j\\},\theta)-f(B,\theta)\right)\ \ \ \text{(since
$f(\theta,\cdot)$ is monotonic)}$ $\displaystyle\Longleftrightarrow$
$\displaystyle\ \tau\leq\min_{B\subset[N]}\min_{j\not\in
B}\left(\frac{f(B\cup\\{j\\},\theta)-f(B,\theta)}{2}\right).$

Taking the contrapositive of this statement establishes the desired result.
When $f(\emptyset,\theta)=0$, then setting $B=\emptyset$ gives the desired
result. ∎

######  Corollary 4.

Let $f:2^{\Omega}\times\Theta\to\mathbb{R}_{+}$ be a function such that
$f(\cdot,\theta)$ is monotonic for all $\theta\in\mathbb{R}^{N}$. Then, $f$ is
not $\tau$-codomain separable for any

$\tau>\sup_{\theta\in\mathbb{R}^{N}}\min_{B\subset[N]}\min_{j\not\in
B}\left(\frac{f(B\cup\\{j\\},\theta)-f(B,\theta)}{2}\right).$

In particular, if $f(\emptyset,\theta)=0$ for all $\theta\in\mathbb{R}^{N}$,
then $f$ is not $\tau$-codomain separable for any

$\tau>\frac{1}{2}\left(\sup_{\theta\in\mathbb{R}^{N}}\min_{j\in[N]}f(\\{j\\},\theta)\right).$

We now show that if in addition to monotonicity, the loss function is also
bounded, then we can get stronger negative results.

######  Theorem 13.

Let $\Omega=\\{s_{1},\dots,s_{N}\\}$ be a set. Let
$f:2^{\Omega}\times\Theta\to\mathbb{R}_{+}$ be a function such that
$f(\cdot,\theta)$ is monotonic and $f(\cdot,\theta)\leq\beta$ for all
$\theta\in\mathbb{R}^{N}$ and for some finite $\beta>0$. Then, $f$ is not
$\tau$-codomain separable for any $\tau>\beta/N$.

###### Proof.

Assume that $f$ is $\tau$-codomain separable using some $\theta$. Consider the
chain of values $v_{0}=f(\\{\
\\},\theta),v_{1}=f(\\{1\\},\theta),f(\\{1,2\\},\theta),\dots,v_{N}=f(\\{1,\dots,N\\},\theta)$.
For each $i\in[N]$, since $f$ is $\tau$-codomain separable, we must have
$|v_{i}-v_{i-1}|\geq\tau$. Since $f$ is monotonic, this implies
$v_{i}-v_{i-1}\geq\tau$. Summing both sides over $i$ gives
$\sum_{i=1}^{N}\left(v_{i}-v_{i-1}\right)=v_{N}-v_{0}$, which must be at least
$N\tau$ for the inequality above to hold. This implies $v_{N}\geq
N\tau+v_{0}$, which, for $\tau>\beta/N$ gives $v_{N}>\beta$ (since $f$ is non-
negative). This is a contradiction since $f$ is bounded above by $\beta$. ∎

(a) (a)

(b) (b)

Figure 3: The plot on the left shows results on the label inference on sigmoid
cross-entropy loss using Algorithm LabelInf over 1000 runs. We plot the length
for which Algorithm LabelInf always succeeds with at least 50% accuracy. The
plot on the right shows label reconstruction accuracy with multi-query label
inference attack on sigmoid cross-entropy by performing Algorithm LabelInf on
$M$ data points at a time using a total of $\lceil N/M\rceil$ queries (where
$N=2201$ is the number of rows in the Titanic dataset).

##  Appendix G Additional Experimental Results

We now discuss the missing details from Section 5 and present our results for
label inference from the Sigmoid cross entropy loss function.

Label Inference from Binary Cross-Entropy. In our experiments, for the binary
label case, we use the label inference attack of Aggarwal _et al._[5] as a
baseline (see Figures 1(a) and (b)). We begin by restating the label inference
result of Aggarwal _et al._[5].

######  Theorem 14 ($\tau$-codomain Separability from Algorithm 2 in [5]).

Let $\tau>0$. For the binary case (with class labels $0$ and $1$), define
$\theta_{i}=\left(\frac{3^{2^{i}}N\tau}{1+3^{2^{i}}N\tau}\right)$ for all
$i\in[N]$. Then, CEloss is $2\tau$-codomain separable using $\theta$.

Next, we discuss some technical caveats about the results for the softmax
cross entropy loss, as observed in Figure 1(c).

Additional bits Needed for Softmax Cross-Entropy Loss. Recall from our
discussion in Section 5 that computing the softmax cross-entropy loss will
require an additional $\Omega(NK+\ln(N\tau))$ bits over those required for the
multiclass cross-entropy loss. We now formally argue this result.

Observe that for label inference in the softmax case, it suffices to compute a
vector $\theta^{\prime}=[\theta^{\prime}_{1},\dots,\theta^{\prime}_{N}]$ such
that $\textsc{Softmax}(\theta^{\prime}_{i})=\theta$, where $\theta$ is our
desired vector for label inference. This is equivalent to requiring:
$e^{\theta^{\prime}_{i}}/\sum_{j}e^{\theta^{\prime}_{j}}=\theta_{i}$, which
gives rise to:

$\frac{e^{x_{1}}}{\theta_{1}}=\cdots=\frac{e^{x_{N}}}{\theta_{N}}.$

Thus, for any $i$ and $j$, we can write
$\theta^{\prime}_{i}=\theta^{\prime}_{j}+\ln\left(\frac{\theta_{i}}{\theta_{j}}\right)$.
Now, let

$i_{\shortuparrow}=\arg\max_{i\in[N]}\theta_{i}\mbox{ and
}i_{\shortdownarrow}=\arg\min_{i\in[N]}\theta_{i}.$

Then, we can write
$x_{i_{\shortuparrow}}=x_{i_{\shortdownarrow}}+\ln\left(\frac{\theta_{i_{\shortuparrow}}}{\theta_{i_{\shortdownarrow}}}\right)$.
Thus, the additional number of bits required to represent the entries in $x$
is
$\Omega\left(\ln\ln\left(\frac{\theta_{i_{\shortuparrow}}}{\theta_{i_{\shortdownarrow}}}\right)-\ln\theta_{i_{\shortuparrow}}\right)=\Omega\left(\ln\ln\left(\frac{\theta_{i_{\shortuparrow}}}{\theta_{i_{\shortdownarrow}}}\right)\right)$.
From our construction in Theorem 3, we know that the ratio
$\frac{\theta_{i_{\shortuparrow}}}{\theta_{i_{\shortdownarrow}}}\approx
3^{2^{NK}N\tau}$. This means that we need an additional $\Omega\left(\ln\ln
3^{2^{NK}N\tau}\right)=\Omega\left(NK+\ln(N\tau)\right)$ bits for the softmax
cross-entropy loss as compared to the regular cross-entropy.

Experimental Results for Label Inference from Sigmoid Cross-Entropy Loss.
Similar to the softmax cross-entropy loss, we empirically examine label
inference from the sigmoid activation performed prior to the cross-entropy
calculation (see Figure 3). Note that we do this only for the binary label
case (see (3)). We note that while (3) guarantees 100% accurate inference
theoretically, this was not observed during our experiments (Figure 3(a)).
This is because the number of bits required to represent
$\textsc{Sigmoid}^{-1}(\theta_{i})$ (where $\theta_{i}$ is an element of
$\theta$) is
$\Omega\left(\ln\left|\ln(\theta_{i}/(1-\theta_{i}))\right|\right)$, which
asymptotically dominates the $\Omega\left(\left|\ln\theta_{i}\right|\right)$
many bits required to represent $\theta_{i}$ for the cross-entropy loss.