text:
\section{Missing Details from Section~\ref{sec:prelim}} \label{app:prelim}
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~\citep{aggarwal2021icml}.

\noindent\textbf{Restatement of Proposition~\ref{prop:bound_on_tau_for_label_inference}.} \emph{A function $f$ admits $\tau$-robust label inference using $\theta \in \Theta$ if and only if $\Lambda_{\theta}(f) \geq 2\tau$.}
\begin{proof}
We start with one direction and show that if we can do label inference (there exists algorithm $\mathcal{A}$ in Definition~\ref{def:robust_label_inference}), then $\Lambda_{\theta}(f) \ge 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 = \paran{f(\sigma_1,\theta)+f(\sigma_2,\theta)}/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}\abs{f(\sigma_2,\theta) - f(\sigma_1,\theta)} \geq 2\tau$.

For the other direction, let $\ell$ be as given in Definition~\ref{def:robust_label_inference} with $\abs{f(\sigma^\star,\theta) - \ell} < \tau$. By triangle inequality it follows that if $\Lambda_{\theta}(f) \geq 2\tau$, then $\abs{\ell - f(\sigma^\star,\theta)} < \min_{\sigma \in \mathbb{Z}_K^N \setminus \sigma^\star} \abs{\ell-f(\sigma,\theta)}$ (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} \abs{f(\sigma,\theta) -\ell}$ will return the true label $\sigma^\star$ (which is how Algorithm~\textsc{LabelInf}\xspace works).
\end{proof}

\noindent\textbf{Details about the $\mathsf{FPA}(\phi)$ Model.} For ease of discussion, as in~\citep{aggarwal2021icml}, 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.

\begin{definition} [$\tau$-codomain Separability in the $\textsc{FPA}(\phi)$ model]
\label{def:FPA_codomain_separability}
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} \abs{f_\phi(\sigma_1,\theta) - f_\phi(\sigma_2,\theta)}$ to be the minimum difference in the function output keeping $\theta$ fixed. For a fixed $\tau > 0$, we say that $f$ admits \emph{$\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 \emph{$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$.
\end{definition}

\begin{proposition} \label{prop:FPAAPA}
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'}$ also admits $\tau$-codomain separability in the $\mathsf{FPA}(\phi')$ model using $\theta$ for all $\phi' > \phi$.
\end{proposition}
\begin{proof}
Given $\theta$ and the fact that $f_\phi$ admits $\tau$-codomain separability using $\theta$ in the $\mathsf{FPA}(\phi)$ model, denote
\begin{align*}
    \Lambda_\theta(f_\phi) = \min_{\sigma_1,\sigma_2 \in \mathbb{Z}_K^N} \abs{f_\phi(\sigma_1,\theta) - f_\phi(\sigma_2,\theta)} = b_{\frac{\phi-3}{2}}\cdots b_1 b_0\ .\ b_{-1}b_{-2} \cdots b_{-\frac{\phi-1}{2}} \geq 2\tau,
\end{align*}
where each bit $b_i \in \{0,1\}$. Then, in the $\mathsf{FPA}(\phi+1)$ model, we can write (without loss of generality):
\begin{align*}
    \Lambda_\theta(f_{\phi+1}) &= \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}\\
     &= b_{\frac{\phi-3}{2}}\cdots b_1 b_0\ .\ b_{-1}b_{-2} \cdots b_{-\frac{\phi-1}{2}} \geq 2\tau,
\end{align*}
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'}$ admits $\tau$-codomain separation in the $\mathsf{FPA}(\phi')$ model using $\theta$ for all $\phi' > \phi$. In the limit when $\phi \to \infty$, this is equivalent to saying that $f$ admits $\tau$-codomain separation in the $\mathsf{APA}$ model.
\end{proof}

\begin{proposition} \label{prop:APAFPA}
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)$.
\end{proposition}
\begin{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)$.
\end{proof}

\section{Missing Details from Section~\ref{sec:logloss}} \label{app:logloss}
\noindent\textbf{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~\citep{aggarwal2021icml}. Note that in Theorem~\ref{thm:multi_class_proof}, 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~\eqref{eq:multi_class_log_loss}, are distinct for all labelings. For example, if the true labeling is $[0,2]$, then we obtain $\textsc{K-CEloss}\xspace([0,2]; \theta) = -\frac{1}{2}\paran{\ln \frac{2}{10} + \ln \frac{13}{31}} = -\frac{1}{2} \ln\paran{\frac{2 \cdot 13}{10 \cdot 31}}$. Similarly, if the true labeling is $[1,0]$, then we obtain $\textsc{K-CEloss}\xspace([1,0]; \theta) = -\frac{1}{2}\paran{\ln \frac{3}{10} + \ln \frac{7}{31}} = -\frac{1}{2}\ln\paran{\frac{3 \cdot 7}{10 \cdot 31}} $. The use of primes makes this selection of summands in the $\textsc{K-CEloss}\xspace$ score uniquely defined by the true labeling. This follows as the only thing that changes in the $\textsc{K-CEloss}\xspace$ 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.

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

\noindent\textbf{Restatement of Theorem~\ref{thm:multi_class_proof}.} \emph{Let $\tau > 0$. Define matrices $\vartheta, \theta \in \mathbb{R}^{N \times K}$ such that
$$\vartheta_{n,k} = 3^{\paran{2^{(n-1)K+k}N\tau}} \mbox{ and } \theta_{n,k} = \vartheta_{n,k} / \sum_{k=1}^K \vartheta_{n,k}.$$ Then, it holds that $\textsc{K-CEloss}\xspace$ is $2 \tau$-codomain separable using $\theta$.}
\begin{proof}
We begin by simplifying the expression for $\textsc{K-CEloss}\xspace\paran{\theta,\sigma}$~\eqref{eq:multi_class_log_loss} to write it as a sum of two terms: one dependent on the labeling $\sigma$, and the other independent of this labeling.
\begin{align}\label{eq:multi_class_log_loss_difference}
    \textsc{K-CEloss}\xspace\paran{\theta,\sigma} &= \frac{-1}{N}\sum_{i=1}^N \sum_{k=1}^K \ \Big([\sigma_i = k] \cdot \ln \theta_{i,k} \Big)

    = \frac{-1}{N}\paran{\underbrace{\sum_{i=1}^N \ln \vartheta_{i,\sigma_i}}_{\substack{\text{Labeling Dependent}\\\text{Term}}} - \underbrace{\sum_{i=1}^N \ln \paran{\sum_{k=1}^K \vartheta_{i,k}}}_{\substack{\text{Labeling Independent}\\\text{Term}}}}.
\end{align}
Using~\eqref{eq:multi_class_log_loss_difference}, we then obtain the following:
\begin{align*}
    \Lambda_{\theta}(\textsc{K-CEloss}\xspace) &= \min_{\sigma_1, \sigma_2 \in \mathbb{Z}_K^N} \abs{\textsc{K-CEloss}\xspace\paran{\theta,\sigma_1} - \textsc{K-CEloss}\xspace\paran{\theta,\sigma_2}}\\
    &= \min_{\sigma_1, \sigma_2 \in \mathbb{Z}_K^N} \frac{1}{N}\abs{\sum_{i=1}^N \ \Big(\ln \theta_{i,\sigma_1(i)} \Big) - \sum_{i=1}^N \ \Big(\ln \theta_{i,\sigma_2(i)} \Big)}\\
    &= \min_{\sigma_1, \sigma_2 \in \mathbb{Z}_K^N} \frac{1}{N}\abs{\sum_{i=1}^N \ \Big(\ln \vartheta_{i,\sigma_1(i)} \Big) - \sum_{i=1}^N \ \Big(\ln \vartheta_{i,\sigma_2(i)} \Big)}\\

    &= \min_{\sigma_1, \sigma_2 \in \mathbb{Z}_K^N} (\tau\ln 3) \abs{\sum_{i=1}^N 2^{(i-1)K+\sigma_1(i)} - \sum_{i=1}^N 2^{(i-1)K+\sigma_2(i)}} \geq 2\tau\ln 3 > 2\tau.
\end{align*}

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.
\end{proof}

\section{Missing Details from Section~\ref{sec:linearly_separable}} \label{app:linearly_separable}

\noindent\textbf{Restatement of Theorem~\ref{thm:linear_separable}.} \emph{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^iN\tau$ for all $i \in [N]$.}
\begin{proof}
We begin by observing that~\eqref{eq:linear_separable} can be rewritten as follows:
\begin{align*}
    f(\sigma,\theta) &= \frac{1}{N}\sum_{i=1}^N\paran{\sigma_i g(\theta_i) + (1-\sigma_i)g(1-\theta_i)} \\ &= \frac{1}{N} \paran{\sum_{i:\sigma(i)=1}\paran{g(\theta_i)-g(1-\theta_i)}+\sum_{i=1}^N g(1-\theta_i)}.
\end{align*}
For any $\theta\in(0,1)^N$, we can then write the following:
\begin{align*}
    \Lambda_\theta(f) &= \min_{\sigma_1,\sigma_2 \in \{0,1\}^N} \abs{f(\sigma_1,\theta)-f(\sigma_2,\theta)}\\
    &= \frac{1}{N} \min_{\sigma_1,\sigma_2 \in \{0,1\}^N} \abs{\sum_{i:\sigma_1(i)=1}\paran{g(\theta_i)-g(1-\theta_i)} - \sum_{j:\sigma_2(j)=1}\paran{g(\theta_j)-g(1-\theta_j)}}
\end{align*}
If for all $i \in [N]$, it holds that $g(\theta_i) - g(1-\theta_i) = 2^iN\tau(1+\delta)$ for some $\delta > 0$, then:
\begin{align*}
    \Lambda_\theta(f) &= (2\tau(1+\delta)) \min_{\sigma_1,\sigma_2 \in \{0,1\}^N} \abs{\sum_{i:\sigma_1(i)=1} 2^{i-1} + \sum_{j:\sigma_1(j)=1}2^{j-1}} = 2\tau(1+\delta) > 2\tau,
\end{align*}
where the last step holds because $\sigma_1 \neq \sigma_2$.
\end{proof}

\noindent\textbf{Restatement of Theorem~\ref{thm:zero_codomain_linear_separable}.} \emph{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.}
\begin{proof}
From the definition of linear-decomposability, we can write:
\begin{align*}
    f(\sigma,\theta) &= \frac{1}{N}\paran{\sum_{i \in [N]:\sigma_i=1} g(\theta_i) + \sum_{i \in [N]:\sigma_i=0} g(1-\theta_i)} \\
    &= \frac{1}{N}\sum_{i \in [N]} \paran{\sigma_i g(\theta_i) + (1-\sigma_i)g(1-\theta_i)} = \frac{1}{N}\sum_{i \in [N]} \paran{\sigma_i \paran{g(\theta_i)-g(1-\theta_i)} + g(1-\theta_i)}\\
    &= \frac{1}{N}\sum_{i\in [N]:\sigma_i=1} \paran{g(\theta_i)-g(1-\theta_i)} + \frac{1}{N}\sum_{i=1}^N g(1-\theta_i).
\end{align*}
Using this reformulation, we can compute $\Lambda_\theta(f)$, for any $\theta \in (0,1)^N$, as follows:
\begin{align*}
    \Lambda_\theta(f) = \frac{1}{N} \min_{\sigma_1,\sigma_2 \in \{0,1\}^N}\abs{\sum_{i\in [N]:\sigma_1(i)=1} \paran{g(\theta_i)-g(1-\theta_i)} - \sum_{j\in [N]:\sigma_2(j)=1} \paran{g(\theta_j)-g(1-\theta_j)}}.
\end{align*}
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$.
\end{proof}

\subsection{Bregman Divergence-based Binary Losses}
\label{app:bregman}
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$.

\noindent\textbf{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,
\begin{align} \label{eq:KL}
    \textsc{KLLoss}(\sigma,\theta) & = \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) \nonumber \\
    & = \frac{-1}{N} \paran{ \sum_{i: \sigma_i = 1} \ln \theta_i + \sum_{i: \sigma_i = 0} \ln (1-\theta_i)},
\end{align}
which is exactly the binary cross-entropy loss~\eqref{eq:log_loss_defn}\footnote{Here, we adopt the notion that $0\ln 0=0$, so that KL divergence is well-defined.} and is therefore covered by results in Section~\ref{sec:logloss}.

\noindent\textbf{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]} \paran{\frac{p_i}{q_i} - \ln \frac{p_i}{q_i} - 1},$$
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:
\begin{align}
\label{eq:IS}
  \textsc{ISLoss}(\sigma,\theta) =  \frac{1}{N}  \paran{\sum_{i:\sigma_i=1} \paran{\frac{1}{\theta_i}+\ln \theta_i - 1} + \sum_{i:\sigma_i=0}  \paran{\frac{1}{1-\theta_i}+\ln (1-\theta_i) - 1}}
\end{align}
The above equation shows the linear decomposability of this loss, therefore, Theorem~\ref{thm:linear_separable} can be applied to get the following result.

\noindent\textbf{Restatement of Corollary~\ref{cor:IS}.} \emph{The Itakura-Saito divergence loss (\textsc{ISLoss}) is $2\tau$-codomain separable with $\theta_i = \paran{1+3^{2^iN\tau}}^{-1}$.}
\begin{proof}
We apply Theorem~\ref{thm:linear_separable} here. For the Itakura-Saito divergence loss in~\eqref{eq:IS}, we begin by noticing that for $x\in\paran{0,1/2}$, 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\parfrac{\theta_i}{1-\theta_i}$$
for this loss, it suffices to ensure that $\ln\parfrac{1-\theta_i}{\theta_i} > 2^iN\tau$ for Theorem~\ref{thm:linear_separable} to apply. In particular, we solve $\ln\parfrac{1-\theta_i}{\theta_i} = 2^iN\tau\ln 3$ to obtain $\theta_i = \paran{1+3^{2^iN\tau}}^{-1}$. Note that $\theta_i < 1/2$ as needed above.
\end{proof}

\noindent\textbf{Squared Euclidean Loss.} The squared Euclidean divergence for vectors $\mathbf{p}, \mathbf{q} \in \mathcal{S} \subseteq \mathbb{R}^d$ is defined as:
\begin{align}
    \label{eq:sqEuc}
    D_{\text{SE}}(\mathbf{p},\mathbf{q}) = \sum_{i \in [d]} \paran{\abs{p_i - q_i}^2},
\end{align}
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:
\begin{align}
\label{eq:sq}
\textsc{SELoss} (\sigma,\theta) &=  \frac{1}{N}  \paran{\sum_{i:\sigma_i=1} \abs{\sigma_i - \theta_i}^2 + \sum_{i:\sigma_i=0} \abs{\sigma_i - \theta_i}^2} = \frac{1}{N}  \paran{\sum_{i:\sigma_i=1} ( 1 - \theta_i)^2 + \sum_{i:\sigma_i=0} \theta_i^2}.
\end{align}
In this case, there exists no $\theta$ such that the condition of Theorem~\ref{thm:linear_separable} is satisfied. However, we can still use Theorem~\ref{thm:zero_codomain_linear_separable} to establish $0^+$-codomain separability.

\noindent\textbf{Restatement of the first part of Corollary~\ref{cor:eucl}.} \emph{The squared Euclidean loss (\textsc{SELoss})  is  $0^+$-codomain separable using $\theta_i = (1/2)\paran{1-\ln(p_i)/N}$, where $p_i$ is the $i$th prime number.}
\begin{proof}
To apply Theorem~\ref{thm:zero_codomain_linear_separable} 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}\paran{1-\frac{\ln p_i}{N}}$ works.
\end{proof}

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

\noindent\textbf{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]} \paran{p_i^\alpha + (\alpha-1)q_i^\alpha - \alpha p_i q_i^{\alpha-1}}, $$
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:
\begin{multline*}
D_{\text{NL}}([\sigma_i,1-\sigma_i],[\theta_i,1-\theta_i])
\\= \paran{ \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}}.
\end{multline*}
Summing over the $N$ datapoints (and dividing by $N$), and simplifying gives the norm-like divergence loss.
\begin{multline}
\label{eq:norm}
\textsc{NLLoss}(\sigma,\theta)= \frac{1}{N}  \big (\sum_{i:\sigma_i=1} \paran{1 + (\alpha-1) \theta_i^\alpha - \alpha \theta_i^{\alpha-1} + (\alpha-1)(1-\theta_i)^\alpha}
\\ + \sum_{i:\sigma_i=0} \paran{1 + (\alpha-1) (1-\theta_i)^\alpha - \alpha(1-\theta_i)^{\alpha-1} + (\alpha-1) \theta_i^\alpha}
 \big ).
\end{multline}
Again while Theorem~\ref{thm:linear_separable} is not applicable in this case, Theorem~\ref{thm:zero_codomain_linear_separable} is applicable.

\noindent\textbf{Restatement of the second part of Corollary~\ref{cor:eucl}.} \emph{The norm-like divergence loss (\textsc{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.}
\begin{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.
\end{proof}

\subsection{A General Result for Bregman Divergence} \label{app:breg_general}
Similar to the general construction of robust label inference for linearly-decomposable functions in Section~\ref{sec:linearly_separable}, 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.
\begin{theorem}
\label{thm:bregman_general} 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'(\theta_i) + h'(1-\theta_i) > 2^iN\tau$ for all $i \in [N]$, where $h'(x) = dh/dx$.
\end{theorem}
\begin{proof}
From the definitions of $F$ and $f_F$ in the theorem statement, we can simplify the expression for $f_F$ as follows:
\begin{align*}
    Nf_F(\sigma,\theta) &= \sum_{i=1}^N D_F([\sigma_i,1-\sigma_i],[\theta_i,1-\theta_i])

    = \sum_{i=1}^N \paran{A_i\sigma_i + B_i},
\end{align*}
where $A_i = h'(\theta_i) + h'(1-\theta_i)$ and $B_i = h(0)+h(1)-(h(\theta_i)+h(1-\theta_i)) - \theta_i(h'(\theta_i) + h'(1-\theta_i))$. Using this, we can compute, for any $\theta \in (0,1)^N$ the following:
\begin{align*}
    \Lambda_\theta(f_F) &= \min_{\sigma_1,\sigma_2 \in \{0,1\}^N} \frac{1}{N} \abs{\sum_{i=1}^N A_i\sigma_1(i) - \sum_{j=1}^N A_j\sigma_2(j)} = 2\tau(1+\delta) > 2\tau,
\end{align*}
which follows by setting $A_i = 2^iN\tau (1+\delta)$ for some $\delta>0$.
\end{proof}

\noindent\textbf{Codomain Separability for Mahalanobis Divergence Loss.}
Not all Bregman divergences are additive in the sense of Theorem~\ref{thm:bregman_general}. 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.
\begin{theorem}
\label{thm:mahalanobis}
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 \le (1/2)\paran{1 - N\tau/\alpha}$.
\end{theorem}
\begin{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:
\begin{align*}
    \Lambda_\theta(\textsc{MHLoss}) &= \min_{\sigma_1,\sigma_2 \in \{0,1\}^N} \frac{\alpha}{N}\abs{\sum_{i=1}^N \paran{\sigma_1(i)-\theta_i}^2 - \paran{\sigma_2(i)-\theta_i}^2}\\
    &= \min_{\sigma_1,\sigma_2 \in \{0,1\}^N}\frac{\alpha}{N}\abs{\sum_{i:\sigma_1(i)\neq \sigma_2(i)} (1-2\theta_i)} = \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],
\end{align*}
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) \ge 2\tau$, which gives $\max_i \theta_i \le \frac{1}{2} - \frac{N\tau}{\alpha}$.
\end{proof}

\section{A Neural Network to Imitate Robust Label Inference}
\label{app:neural_network}
The results in Sections~\ref{sec:logloss} and~\ref{sec:linearly_separable} 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?\footnote{Technically, 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.

\noindent\textbf{Setup.} Assume a classification problem on $K$ classes.
We will design a multi-layer feed-forward neural network $\textsc{MutNet}$ using following specifications.
(1) The input to $\textsc{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 $\textsc{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~\textsc{LabelInf}\xspace to infer~$\sigma_{\mathbf{v}}$.

\noindent\textbf{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 \textsc{ReLU} and \textsc{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}'$ be a vector such that $x'_i = \ln x_i/(1 - x_i)$. Then, for an input vector $\mathbf{v}$, the transformations in $\textsc{MutNet}_{\mathbf{x}}$ are as follows:
\begin{align}
\label{eq:mutator}
\centering
   \mathbf{u}_1   = \mathbf{v}, \;\; \mathbf{u}_2 = \textsc{ReLU}\paran{\mathbf{v}^\top M_1},\;\; \mathbf{u}_3 =\    \textsc{Sigmoid}\paran{\mathbf{u}_2^\top M_2 + \mathbf{x}'},
\end{align}
where $\textsc{ReLU}$ and $\textsc{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

\begin{theorem}
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 $\abs{f(\sigma_\mathbf{v},\textsc{MutNet}_\theta(\mathbf{v})) - \ell} \leq \tau$, Algorithm~\textsc{LabelInf}\xspace recovers $\sigma_\mathbf{v}$.
\end{theorem}
\begin{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 $\textsc{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}'$ in~\eqref{eq:mutator} is constructed in a way such that $\textsc{Sigmoid}(\mathbf{x}') = \theta$ (element -wise).
\end{proof}

\section{Computational Hardness of Codomain Separability}\label{app:hardness_results}
We now show that that determining the codomain separability is co-NP-hard.\footnote{See~\citep{arora2009computational} for a definition of co-NP-hard.} We establish the result for the weaker notion of $0^+$-codomain separability (Definition~\ref{def:codomain_separability}) 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 \textsc{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 \emph{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 \textsc{Almost-Tautology} to be the problem of determining if a given Boolean formula is an almost tautology.

\begin{lemma}
\label{lem:almost_taut_conpcomplete}
\textsc{Almost-Tautology} is co-NP-complete.
\end{lemma}
\begin{proof}
We first show that \textsc{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 \textsc{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~\citep{arora2009computational}. 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~\citep{papadimitriou1982complexity,blass1982unique}, and hence, \textsc{Almost-Tautology} is co-NP-hard.
\end{proof}

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:
\begin{align}
\label{eq:conpcomplete}
    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}.
\end{align}
We now prove our hardness result for $0^+$-codomain separability using this reduction.

\begin{lemma}
\label{lem:conp_helper}
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.
\end{lemma}
\begin{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.
\end{proof}

\begin{theorem} \label{thm:conp}
\textsc{Codomain-Separability} is co-NP-hard.
\end{theorem}
\begin{proof}
We prove this by demonstrating a Karp reduction from the \textsc{Almost-Tautology} problem, which we showed is co-NP-complete in Lemma~\ref{lem:almost_taut_conpcomplete}. Let $\Phi(x_1,\dots,x_N)$ be an arbitrary Boolean formula and $f_\Phi(\sigma,\theta)$ be the corresponding function from~\eqref{eq:conpcomplete}. 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~\ref{lem:conp_helper}, 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.
\end{proof}

\section{Some Negative Results on $\tau$-codomain Separability}
\label{sec:negative_results}
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~\ref{prop:bound_on_tau_for_label_inference}.

\noindent\textbf{Discrete $L_p$-losses.}
We start with the simple $L_p$-loss defined on the {\em discrete} domain and show it is not $\tau$-codomain separable for any $\tau > 0$.
\begin{theorem}
\label{thm:lp_loss}
For any $p > 0$, the function $f: \{0,1\}^N \times \{0,1\}^N \to \mathbb{R}$ of the form $f(\sigma,\theta) = \pnorm{p}{\theta-\sigma}$ is not $\tau$-codomain separable for any $\tau > 0$.
\end{theorem}
\begin{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:
\begin{align*}
    f(\sigma,\theta) = \paran{\sum_{i=1}^N \abs{\theta(i)-\sigma(i)}^p}^{1/p} = \paran{\sum_{i \in I(\sigma,\theta)} \abs{\theta(i)-\sigma(i)}^p}^{1/p} = \abs{I(\sigma,\theta)}^{1/p}.
\end{align*}
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$.
\end{proof}

\noindent\textbf{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.

\begin{theorem}
\label{thm:separability_monotonic}
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} \parfrac{f(B \cup \{j\},\theta) - f(B,\theta)}{2}.$$
In particular, if $f(\emptyset,\theta) = 0$, then $f$ is not $\tau$-codomain separable using $\theta$ for any $\tau > \frac{1}{2} \paran{\min_{j \in [N]} f(\{j\},\theta)}$.
\end{theorem}
\begin{proof}
Fix some $\sigma \in [0,1]^N$. Then, for $f$ to be $\tau$-codomain separable using $\sigma$, it must hold that:
\begin{align*}
    &\forall B\subset [N], j \not\in B.\ \ \ \ \ \abs{f(B \cup \{j\},\theta) - f(B,\theta)} \ge 2\tau \nonumber\\
    \Longrightarrow &\forall B\subset [N].\ \ \ \ \ \tau \le \frac{1}{2} \paran{\min_{j \not\in B} f(B \cup \{j\},\theta) - f(B,\theta)} \ \ \ \text{(since $f(\theta,\cdot)$ is monotonic)}\nonumber\\
    \Longleftrightarrow &\ \tau \le \min_{B \subset [N]}\min_{j \not\in B} \parfrac{f(B \cup \{j\},\theta) - f(B,\theta)}{2}.
\end{align*}
Taking the contrapositive of this statement establishes the desired result. When $f(\emptyset,\theta)=0$, then setting $B = \emptyset$ gives the desired result.
\end{proof}

\begin{corollary}
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} \parfrac{f(B \cup \{j\},\theta) - f(B,\theta)}{2}.$$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} \paran{\sup_{\theta \in \mathbb{R}^N}\min_{j \in [N]} f(\{j\},\theta)}.$$
\end{corollary}

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

\begin{theorem}
\label{thm:separability_monotonic_bounded}
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$.
\end{theorem}
\begin{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 \paran{v_i - v_{i-1}} = 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$.
\end{proof}

\begin{figure}[t]
    \centering
    \vspace{-0.5em}
    \subfloat[(a)]{\includegraphics[width=160pt]{individual_figure/sigmoid_50_singlequery.png}}
    \hspace{2em}
    \subfloat[(b)]{\includegraphics[width=160pt]{individual_figure/sigmoid_titanic.png}}
    \vspace{-1ex}
    \caption{The plot on the left shows results on the label inference on sigmoid cross-entropy loss using Algorithm~\textsc{LabelInf}\xspace over 1000 runs. We plot the  length for which Algorithm~\textsc{LabelInf}\xspace 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~\textsc{LabelInf}\xspace 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).}
    \label{fig:sigmoid_experiments}
       \vspace{1ex}
\end{figure}

\section{Additional Experimental Results}
\label{app:experiments}
We now discuss the missing details from Section~\ref{sec:experiments} and present our results for label inference from the Sigmoid cross entropy loss function.

\noindent\textbf{Label Inference from Binary Cross-Entropy.} In our experiments, for the binary label case, we use the label inference attack of Aggarwal \emph{et al.} \citep{aggarwal2021icml} as a baseline (see Figures~\ref{fig:singlequery}(a) and (b)). We begin by restating the label inference result of Aggarwal \emph{et al.} \citep{aggarwal2021icml}.

\begin{theorem}[$\tau$-codomain Separability from Algorithm 2 in~\citep{aggarwal2021icml}]\label{thm:from_icml}
Let $\tau > 0$. For the binary case (with class labels $0$ and $1$), define $\theta_i = \parfrac{3^{2^i}N\tau}{1+3^{2^i}N\tau}$ for all $i \in [N]$. Then, $\textsc{CEloss}\xspace$ is $2 \tau$-codomain separable using $\theta$.
\end{theorem}

Next, we discuss some technical caveats about the results for the softmax cross entropy loss, as observed in Figure~\ref{fig:singlequery}(c).

\noindent\textbf{Additional bits Needed for Softmax Cross-Entropy Loss.} Recall from our discussion in Section~\ref{sec:experiments} 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' = [\theta'_1,\dots,\theta'_N]$ such that $\textsc{Softmax}(\theta'_i) = \theta$, where $\theta$ is our desired vector for label inference. This is equivalent to requiring: $e^{\theta'_i}/\sum_j e^{\theta'_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'_i = \theta'_j + \ln \parfrac{\theta_i}{\theta_j}$. 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 \parfrac{\theta_{i_{\shortuparrow}}}{\theta_{i_{\shortdownarrow}}}$. Thus, the additional number of bits required to represent the entries in $x$ is $\Omega\paran{\ln \ln \parfrac{\theta_{i_{\shortuparrow}}}{\theta_{i_{\shortdownarrow}}} - \ln \theta_{i_{\shortuparrow}}} = \Omega\paran{\ln \ln \parfrac{\theta_{i_{\shortuparrow}}}{\theta_{i_{\shortdownarrow}}}}$. From our construction in Theorem~\ref{thm:multi_class_proof}, 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\paran{\ln \ln 3^{2^{NK}N\tau}} = \Omega\paran{NK + \ln (N\tau)}$ bits for the softmax cross-entropy loss as compared to the regular cross-entropy.

\textbf{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~\ref{fig:sigmoid_experiments}). Note that we do this only for the binary label case (see~\eqref{eq:sigmoid_definition}). We note that while~\eqref{eq:sigmoid_definition} guarantees 100\% accurate inference theoretically, this was not observed during our experiments (Figure~\ref{fig:sigmoid_experiments}(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\paran{\ln\abs{\ln (\theta_i/(1-\theta_i))}}$, which asymptotically dominates the $\Omega\paran{\abs{\ln \theta_i}}$ many bits required to represent $\theta_i$ for the cross-entropy loss.

\section{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 Kaggle\footnote{https://www.kaggle.com}, KDDCup\footnote{https://www.kdd.org/kdd-cup}, and ILSVRC Challenges\footnote{http://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  {\em 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 {\em  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.\footnote{See our ethics and malpractice statement at the end of this paper.\\}

\noindent\textbf{Overview of Our Results.}
Our attacks rely on a mathematical notion of {\em 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~\ref{prop:bound_on_tau_for_label_inference}), and outline our end-to-end inference attack in Algorithm~\textsc{LabelInf}\xspace. We discuss some caveats associated with running this algorithm on machines with finite floating point precision, which help explain our experimental findings in Section~\ref{sec:experiments}.

The main technical challenge here is to design prediction vectors for which a loss function demonstrates the required codomain separability for arbitrary noise levels.\footnote{We show that for general functions, determining codomain separability is co-NP-hard (see Appendix~\ref{app:hardness_results}).} 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~\ref{tab:overview_results}). 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~\ref{sec:experiments}. 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~\ref{app:neural_network}).

\begin{table}[t]
\caption{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.}
\label{tab:overview_results}
\centering
\vspace{0.5ex}
\begin{tabular}{|c|c|P{1.7cm}|c|P{1.3cm}|P{2cm}|}
 \hline
 \multirow{2}{*}{\textbf{Loss Function}} & \multirow{2}{*}{\textbf{$K$}} & \multirow{2}{*}{\textbf{Past Work}} & \multirow{2}{*}{\textbf{This Work}} & \multicolumn{2}{|c|}{\textbf{Local Computation}}\\
 &&&&\textbf{1-Query}&\textbf{Multi-Query}\\\hline \hline
 Binary Cross-Entropy & 2 &  Noised~\cite{aggarwal2021icml} & Noised (Thm.\ \ref{thm:multi_class_proof}) & $O(2^N)$ & $O(\mbox{poly}(N))$ \\ \hline
 K-ary Cross-Entropy & $K$ & Unnoised~\cite{aggarwal2021icml} & Noised (Thm.\ \ref{thm:multi_class_proof}) & $O(K^N)$ & -- \\ \hline
  Softmax Cross-Entropy & $K$ & -- & Noised (Sec.\ \ref{sec:logloss}) &$O(K^N)$ & -- \\ \hline
 Sigmoid Cross-Entropy & 2 & -- & Noised (Sec.\ \ref{sec:logloss}) & $O(2^N)$ & $O(\mbox{poly}(N))$ \\ \hline
 Itakura-Saito Divergence & 2 & -- & Noised (Cor.\ \ref{cor:IS}) &$O(2^N)$ & $O(\mbox{poly}(N))$ \\ \hline
 Squared Euclidean  & 2 & -- & Unnoised (Cor.\ \ref{cor:eucl}) &$O(2^N)$ & $O(\mbox{poly}(N))$\\ \hline
 Norm-like Divergence & 2 & -- & Unnoised (Cor.\ \ref{cor:eucl}) &$O(2^N)$ & $O(\mbox{poly}(N))$\\ \hline
 Mahalanobis Divergence & 2 & -- & Noised (Thm.
  \ref{thm:mahalanobis}) &$O(2^N)$& --\\ \hline
\end{tabular}
\vspace*{2ex}
\end{table}

\noindent\textbf{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:
\begin{align*}
\text{Construct $\theta = [\theta_1,\dots,\theta_N]$ such that }:\ \min_{\sigma_1,\sigma_2 \in \{0,1\}^N}\abs{\sum_{i:\sigma_1(i)=1}g(\theta_i) - \sum_{j:\sigma_2(j)=1}g(\theta_j)} \geq b,
\end{align*}
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^ib$ 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.

\noindent\textbf{Related Work.} Label inference attacks using loss function values were introduced in~\citep{whitehill2018climbing,aggarwal2020logloss}, where the focus was primarily on the binary cross-entropy loss. These attacks range from heuristically solving a min-max optimization problem~\citep{whitehill2018climbing} to using prime factorization~\citep{aggarwal2020logloss} for recovering the true labeling. However, neither attacks extend to the noised setting. The problem was partially addressed recently by Aggarwal \emph{et al.}\ in~\citep{aggarwal2021icml}, 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~\ref{tab:overview_results}). 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~\citep{blum2015ladder}, 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~\citep{o2004complete} and Golomb rulers~\citep{robinson1967class}.

\noindent\textbf{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} \abs{\sum_{s_1 \in S_1}s_1 - \sum_{s_2 \in S_2}s_2}$ 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 := \{m 2^{i}\mid i \in \mathbb{Z}_n\}$ (with $|S_m|=n$) satisfies $\mu(S_m) = m$.
\vspace{-2ex}
\section{Codomain Separability and Robust Label Inference} \label{sec:prelim}
\vspace{-1ex}
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~\ref{app:prelim}).

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:
\begin{align}
    \label{eq:log_loss_defn}
    \textsc{CEloss}\xspace\paran{\sigma,\theta} = \frac{-1}{N}\ln \paran{\prod_{i=1}^N \theta_i^{\sigma_i}(1-\theta_i)^{1-\sigma_i}}.
\end{align}
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}$.

\noindent\textbf{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.
\begin{definition} [$\tau$-codomain separability]
\label{def: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} \abs{f(\sigma_1,\theta) - f(\sigma_2,\theta)}$ to be the minimum difference in the function output keeping $\theta$ fixed. For a fixed $\tau > 0$, we say that $f$ admits \emph{$\tau$-codomain separability} using $\theta$ if $\Lambda_{\theta}(f) \geq \tau$. In particular, we say that $f$ admits \emph{$0^+$-codomain separability} using $\theta$ if there exists any $\tau > 0$ such that $\Lambda_{\theta}(f) \geq \tau$.
\end{definition}
Note that, for a fixed $\theta$, if a function is $\tau$-codomain separable, then it is also $\tau'$-codomain separable for $0 < \tau' < \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 \emph{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~\ref{sec:negative_results}, we present some function classes that are provably not $\tau$-codomain separable.

\noindent\textbf{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.
\begin{definition}[$\tau$-Robust Label Inference]
\label{def: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 $\abs{f(\sigma^\star,\theta) - \ell} < \tau$, \emph{i.e.,} for all $\sigma^\star \in \mathbb{Z}_K^N$, we have $\mathcal{A}\paran{\theta, N, \ell} = \sigma^\star$.
\end{definition}
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 {\em stronger} notion than that required by notions like {\em blatant non-privacy}~\citep{dinur2003revealing}, 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.

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

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~\textsc{LabelInf}\xspace, we present a general label inference technique based on Proposition~\ref{prop:bound_on_tau_for_label_inference}. The adversary picks $\theta \in \Theta$ based on Definition~\ref{def:codomain_separability}, 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$.

\renewcommand{\thealgocf}{}
\SetAlgoCaptionSeparator{}
       \begin{algorithm}[t]
        \SetAlgoLined
        \SetKwInput{KwData}{Input}
        \SetKwInput{KwResult}{Output}
        \SetKwInOut{Model}{Model Setting}
        \KwData{Number of datapoints $N$, bound on error (noise) $\tau > 0$}
        \KwResult{Recovered labels $\hat{\sigma}$}
        \Model{A server (oracle) with private dataset with true labels $\sigma^\star$}

        \smallskip
        Design a vector $\theta\in \Theta$ with respect to which $f$ admits $2\tau$-codomain separability (Definition~\ref{def:codomain_separability}).\\
        Query the server using $\theta$ as the prediction vector and observe output $\ell$ with $\abs{f(\sigma^\star,\theta) - \ell } < \tau$.\\
         \textbf{Return} $\hat{\sigma} \gets \arg\min_{\sigma\in \mathbb{Z}_K^N} \abs{f(\sigma,\theta) -\ell}$.
        \caption{\textsc{LabelInf}\xspace: Robust Label Inference for function $f:\mathbb{Z}_K^N \times \Theta \to \mathbb{R}$}
        \label{alg:general_label_inference}
        \end{algorithm}

\begin{remark} \label{rem:first}
A special case of Algorithm~\textsc{LabelInf}\xspace is the unnoised setting, wherein $\ell = f(\sigma^\star,\theta)$. In that case, in Algorithm~\textsc{LabelInf}\xspace, 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).
\end{remark}

An important feature about Algorithm~\textsc{LabelInf}\xspace 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).\!\footnote{To baseline Algorithm~\textsc{LabelInf}\xspace with a naive exponential search over the space of all labelings, we simulated label inference on the Titanic dataset (see Section~\ref{sec:experiments}) for the cross-entropy loss, by replacing the prediction vector $\theta$ from Step 1 in Algorithm~\textsc{LabelInf}\xspace 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} \abs{f(\sigma,\theta) -\ell}$ 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~\ref{sec:linearly_separable}. Even the exponential search is a local computation for the adversary.
\begin{theorem} \label{thm:inf}
Let $f :\mathbb{Z}_K^N \times \Theta \to \mathbb{R}$.
Algorithm~\textsc{LabelInf}\xspace performs $\tau$-robust label inference on $f$, in that it recovers $\sigma^\star$ (i.e., $\hat{\sigma} = \sigma^\star$) from $
\ell$ where $\abs{f(\sigma^\star,\theta) - \ell } < \tau$.
\end{theorem}
\vspace*{-0.9ex}
\noindent\textbf{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~\citep{knuth2014art,brent2010modern}. Following~\citep{aggarwal2021icml}, 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~\ref{def:codomain_separability} 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~\ref{def:FPA_codomain_separability}, Appendix~\ref{app:prelim}).
Let $f_\phi$ be the representation of $f$ in the $\mathsf{FPA}(\phi)$ model.\!\footnote{Informally, 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~\ref{prop:FPAAPA}, Appendix~\ref{app:prelim}). 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~\ref{prop:APAFPA}, Appendix~\ref{app:prelim}).

Moving to label inference, note that Algorithm~\textsc{LabelInf}\xspace is also described in the $\textsc{APA}$ model. The above mentioned bound on $\phi$ may not suffice for $\tau$-robust label inference using Algorithm~\textsc{LabelInf}\xspace in the $\mathsf{FPA}(\phi)$ model. This is because unlike codomain separability, Algorithm~\textsc{LabelInf}\xspace 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~\ref{thm:multi_class_proof} 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~\ref{sec:experiments}. For simplicity of description, we present our inference attacks under the $\mathsf{APA}$ model in the main body of this paper.

\vspace*{-2ex}
\section{$\tau$-Robust Label Inference for Cross-Entropy Loss and its Extensions} \label{sec:logloss}
\vspace*{-1ex}
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~\textsc{LabelInf}\xspace 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~\ref{app:logloss}.

\noindent\textbf{Multiclass Cross-Entropy Loss.} We first recall the definition of multiclass cross-entropy (extending Definition~\ref{eq:log_loss_defn}).
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}\xspace\paran{\sigma, \theta}$ and defined as follows:
	\begin{align}
	\label{eq:multi_class_log_loss}
		\textsc{K-CEloss}\xspace\paran{\sigma, \theta} := \frac{-1}{N}\sum_{i=1}^N \sum_{k=0}^{K-1} \ \Big([\sigma_i = k] \cdot \ln \theta_{i,k} \Big),
	\end{align}
 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 $\textsc{K-CEloss}\xspace$ function $2\tau $-codomain separable for any $\tau >0$ (i.e., $\Lambda_{\theta}(\textsc{K-CEloss}\xspace) \geq 2 \tau $). At a high level, we obtain the required codomain separability for $\textsc{K-CEloss}\xspace$ by designing the entries in the matrix $\theta$ in such a way that the expression inside the logarithm in~\eqref{eq:multi_class_log_loss} 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.
\begin{theorem}\label{thm:multi_class_proof}
Let $\tau > 0$. Define matrices $\vartheta, \theta \in \mathbb{R}^{N \times K}$ such that $\vartheta_{n,k} = 3^{\paran{2^{(n-1)K+k}N\tau}}$ and $\theta_{n,k} = \vartheta_{n,k} / \sum_{k=1}^K \vartheta_{n,k}$. Then, it holds that $\textsc{K-CEloss}\xspace$ is $2 \tau $-codomain separable using $\theta$.
\end{theorem}

The following corollary follows by combining the above result with Theorem~\ref{thm:inf}.
\begin{corollary}
Using $\theta$ from Theorem~\ref{thm:multi_class_proof}, Algorithm~\textsc{LabelInf}\xspace performs $\tau$-robust label inference from the K-ary cross-entropy loss ($\textsc{K-CEloss}\xspace$).
\end{corollary}
Note that Theorem~\ref{thm:multi_class_proof} only holds for the error $\tau >0$. However, as mentioned in Remark~\ref{rem:first}, in the unnoised case it suffices to instantiate Theorem~\ref{thm:multi_class_proof} 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~\ref{thm:multi_class_proof}. This blowup is unfortunately unavoidable for constructing $\tau$-codomain separability, even for the binary case, as shown in \citep[Theorem~7]{aggarwal2021icml}.

\noindent\textbf{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}$:
\begin{align*}
 \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}).
\end{align*}
We explain how to extend Theorem~\ref{thm:multi_class_proof} 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~\ref{thm:multi_class_proof}. 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'_{i,k}$'s: for all $k \in \mathbb{Z}_K , i \in [N]$: $\exp\paran{\theta'_{i,k}}/\sum_{j=1}^K \exp\paran{\theta'_{i,j}} = \theta_{i,k}$.
This is a system of linear equations in the variables $\exp\paran{\theta'_{i,j}}$, for each $i \in [N]$, hence, can be solved in polynomial time using standard techniques. Once $\theta'$ is obtained, since $\textsc{softmax}(\theta'_{i,k}) = \theta_{i,k}$, from Theorem~\ref{thm:multi_class_proof}, we get that softmax cross-entropy loss is $2\tau $-codomain separable using $\theta'$; Algorithm~\textsc{LabelInf}\xspace can now be used for $\tau$-label inference.

The separability from Theorem~\ref{thm:multi_class_proof} 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$:
\begin{align}
\label{eq:sigmoid_definition}
	 \frac{-1}{N}\sum_{i=1}^N \ \Big( \sigma_i \ln \paran{\textsc{Sigmoid}(\theta_i)} + (1-\sigma_i)\ln \paran{1-\textsc{Sigmoid}(\theta_i)} \Big),
\end{align}
where $\textsc{Sigmoid}(x) = \paran{1+e^{-x}}^{-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~\ref{thm:multi_class_proof}, we can construct $\theta' \in (0,1)^{N}$ such that $\theta'_{i} = \ln (\theta_{i,1}/(1-\theta_{i,1}))$ for all $i \in [N]$.
 Once $\theta'$ 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'$, and hence Algorithm~\textsc{LabelInf}\xspace can be used for $\tau$-robust label inference.

\vspace{-1ex}
\section{$\tau$-Robust Label Inference for Linearly-Decomposable Binary Losses}
\label{sec:linearly_separable}
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:
\begin{align}
\label{eq:linear_separable}
f(\sigma,\theta) &= \frac{1}{N}\paran{\sum_{i \in [N]:\sigma_i=1} g(\theta_i) + \sum_{i \in [N]:\sigma_i=0} g(1-\theta_i)}.
\end{align}
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~\textsc{LabelInf}\xspace for $\tau$-robust label inference in these cases. Missing details are presented in Appendix~\ref{app:bregman}.
\begin{theorem}
\label{thm:linear_separable}
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^iN\tau$ for all $i \in [N]$.
\end{theorem}

\noindent\textbf{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~\eqref{eq:KL}, Appendix~\ref{app:bregman}). 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~\eqref{eq:IS}, Appendix~\ref{app:bregman}); (ii) squared Euclidean loss, which can be expressed using $g(\theta_i) = (1-\theta_i)^2$, (see~\eqref{eq:sqEuc}, Appendix~\ref{app:bregman}); 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 \ge 2$ (see~\eqref{eq:norm}, Appendix~\ref{app:bregman}).

\textbf{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~\citep{bregman1967relaxation} 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~\citep{liu2016clustering}. 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~\ref{app:breg_general}.

\textbf{Applying Theorem~\ref{thm:linear_separable}.} Observe that Theorem~\ref{thm:linear_separable} 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^iN\tau)$ for all $i \in [N]$. This vector $\theta$ can now be used for $\tau$-robust label inference from $f$ using Algorithm~\textsc{LabelInf}\xspace. 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~\eqref{eq:IS}, Appendix~\ref{app:bregman}).
\begin{corollary} \label{cor:IS}
The Itakura-Saito divergence loss is $2\tau$-codomain separable with $\theta_i = (1+3^{2^{i}N\tau})^{-1}$.
\end{corollary}

\noindent\textbf{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~\textsc{LabelInf}\xspace.
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:
\begin{align*}
    \Lambda_\theta(f) &= \frac{1}{N} \min_{\sigma_1,\sigma_2 \in \{0,1\}^N} \abs{\sum_{i\leq M:\sigma_1(i)=1}\paran{g(\theta_i)-g(1-\theta_i)} - \sum_{j\leq M:\sigma_2(j)=1}\paran{g(\theta_j)-g(1-\theta_j)}}.
\end{align*}
Similar to Theorem~\ref{thm:linear_separable}, choosing $\theta_i$ that ensures $g(\theta_i)-g(1-\theta_i) > 2^iN\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.

\input{single_query_plot}

\begin{theorem}
\label{thm:multi_query_general}
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^iN\tau$ to have a solution for all $i \in [N]$.
\end{theorem}
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~\textsc{LabelInf}\xspace 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.

\noindent\textbf{Linearly-Decomposable Functions Not Covered by Theorem~\ref{thm:linear_separable}.} We now deal with linearly-decomposable functions for whom there exists no $\theta$ that could satisfy the condition required in Theorem~\ref{thm:linear_separable} (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.

\begin{theorem}
\label{thm:zero_codomain_linear_separable}
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.
\end{theorem}
\begin{corollary} \label{cor:eucl}
The squared Euclidean loss  is  $0^+$-codomain separable using $\theta_i = (1/2)\paran{1-\ln(p_i)/N}$, 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)$.
\end{corollary}
Finally, the idea behind the multi-query attack mentioned in Theorem~\ref{thm:multi_query_general} also extends to loss functions covered by Theorem~\ref{thm:zero_codomain_linear_separable}, thus, providing a multi-query polynomial time inference here too.

\vspace*{-1ex}
\section{Empirical Analysis}\label{sec:experiments}
\vspace*{-1ex}

We now present our empirical evaluation of label inference attacks on cross-entropy loss and its extensions (see Appendix~\ref{app:experiments} for additional results)\footnote{All 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.
\input{plots}
\begin{CompactItemize}
    \item {\bf{Titanic}}~\cite{titanic}: a binary classification dataset (2201 rows) on the survival status of passengers.

    \item {\bf{Iris}}~\cite{iris}: a three-class classification dataset (150 rows) on the Iris species.
    \item {\bf{Satellite}}~\cite{satellite}: a six-class classification dataset (6430 rows) on the satellite images of soil.
\end{CompactItemize}
We consider three common loss functions mentioned in Section~\ref{sec:logloss}: multiclass cross-entropy, softmax cross-entropy, and sigmoid cross-entropy (deferred to Appendix~\ref{app:experiments}). As a baseline, for the binary labeled dataset (Titanic) with the cross-entropy loss, we implemented the label inference attack of Aggarwal~\emph{et al.}\ \citep{aggarwal2021icml} (see Theorem~\ref{thm:from_icml}, Appendix~\ref{app:experiments} for a restatement of their main result).

We start with the distinction between our experiments and Algorithm~\textsc{LabelInf}\xspace, which is presented in the $\textsc{APA}$ model. For example in the multiclass cross-entropy loss (\textsc{K-CEloss}\xspace) case, to simulate Algorithm~\textsc{LabelInf}\xspace 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~\ref{thm:multi_class_proof}) 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~\ref{fig:singlequery} shows the number of datapoints $N$ recovered by Algorithm~\textsc{LabelInf}\xspace 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~\ref{fig:singlequery}(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~\ref{thm:multi_class_proof}), which given fixed machine precision runs into representation issues. We note that for the Titanic dataset, the construction from~\cite{aggarwal2021icml} 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~\cite{aggarwal2021icml} (see Theorem~\ref{thm:from_icml}, Appendix~\ref{app:experiments}), but $\Omega(2^{2N}N\tau)$ when using Theorem~\ref{thm:multi_class_proof} with $K=2$.

Figures~\ref{fig:singlequery}(b)-(c) show the number of datapoints on which Algorithm~\textsc{LabelInf}\xspace 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~\ref{fig:singlequery}(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~\ref{app:experiments} 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 \ref{fig:multiquery}. For these plots, we simulated Algorithm~\textsc{LabelInf}\xspace 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~\ref{fig:singlequery} 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.

\noindent\textbf{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~\cite{dwork2014algorithmic}.

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.

\newpage

redpajama_set_name: RedPajamaArXiv


Valentine's Day is a special occasion and Buxton is an ideal place to spend the evening at some of our top restaurants and of course stay the night at the Portland Hotel.
Here is a selection of restaurants that are all within walking distance of the Portland.
In our attempt to offer value for money we are offering double rooms at The Portland Hotel on Wednesday February 14th 2018 from £50.00 including breakfast.
That represents a price that could be less than your evening meal.
Please give us a call (01298) 71493 or book on on our website in order to reserve a room and take advantage of this offer..