Proof of 2. We use 1. Let us define the partial instances \({\boldsymbol{y}}^{(0)}, {\boldsymbol{y}}^{(1)} \ldots, {\boldsymbol{y}}^{(d)}\) so that \({\boldsymbol{y}}^{(k)} \subseteq {\boldsymbol{x}}\) is the partial instance defined only in the \(k\) features with maximum score (line [line:greedy]). We then define a sequence of values \(v_k\) as \[v_k := \Pr_{{\boldsymbol{z}}\sim \mathbf{U}({\boldsymbol{y}}^{(k)})}[\mathcal{L}({\boldsymbol{z}}) = \mathcal{L}({\boldsymbol{x}})],\] and note that due to 1, the sequence \(v_0, \ldots, v_d\) is non-decreasing. Let \(M = \frac{\log^2{d}}{2\varepsilon^2 \gamma^2} \log(2 \log d / \gamma)\), as in line [line:mdef], and let us define random variables \(\widetilde{v_k}\) as follows: if 1 enters line [line:montecarlo] with \(m=k\), then \(\widetilde{v_k}\) is the output of 2 (i.e., \(\widehat{v}_k(M)\)), and otherwise \(\widetilde{v_k} = v_k\). We use binary search (lines [line:while]-[line:endwhile]), to find \(k^\star\), the smallest \(k\) such that \[\widetilde{v_k} \geq \delta^\star,\] and our goal is to show that with good probability \(k^\star\) is also the smallest \(k\) such that \(v_k \geq \delta^\star\), which would imply the correctness of the algorithm by 1. Note, however, that even though the sequence \(v_0, \ldots, v_d\) is non-decreasing (1), the estimated values \(\widehat{v_k}\) are not necessarily so. Let \(S\) be a random variable corresponding to the set of values \(k\) such that 1 enters line [line:montecarlo] with \(m=k\), and note that if for every \(k\) in \(S\) it happens that the events \[A_k := \left(v_k \geq \delta^\star \right) \text{ and } B_k := \left(\widetilde{v_k} \geq \delta^\star\right)\] are equivalent (i.e., either both occur or neither occurs), then the algorithm will succeed, as that would indeed imply that \(k^\star\) is the smallest \(k\) such that \(v_k \geq \delta^\star\).

Then, for \(k \in [d]\), define events \(E_k\) and \(F_k\) as follows: \[\begin{align} E_k &:= |\delta^\star - v_k| \geq \frac{\varepsilon \gamma}{\log d},\\ F_k &:= |\widetilde{v_k} - v_k| \leq \frac{\varepsilon \gamma}{\log d}. \end{align}\] We claim that if both \(E_k\) and \(F_k\) hold for some \(k\), then \(A_k\) and \(B_k\) are equivalent events for that \(k\). Indeed, \[\begin{align} A_k &\iff v_k \geq \delta^\star\\ &\iff v_k \geq \delta^\star + \frac{\varepsilon \gamma}{\log d} \\ &\iff v_k - \frac{\varepsilon \gamma}{\log d} \geq \delta^\star\\ &\iff \widetilde{v_k} \geq \delta^\star \\ &\iff B_k. \end{align}\]

Thus, if we show that \(E_k\) and \(F_k\) hold with good probability for every \(k \in S\), we can conclude the theorem. First, note that because of the condition on the variable \(\mathrm{\small steps}\) (lines [line:while], [line:steps]) we have \(|S| \leq \log d\), allowing us to do a binary search in case the desired events \(E_k\) and \(F_k\) hold, and preventing the algorithm from looping otherwise; this way the runtime is bounded not only on expectation but deterministically. ⁷ Then, note that for any \(k\) we have \[\begin{align} \Pr\left[ \, \overline{F_k} \,\right] \leq \Pr\left[ \, \overline{F_k} \mid k \in S \right] &= \Pr\left[|\widehat{v_k}(M) - v_k| > \frac{\varepsilon \gamma}{\log d}\right]\\ &\leq \frac{\gamma}{\log d}. } \end{align}\] Because \(S\) itself is a random variable, whose size is also a random variable, we need to be careful before applying a union bound or any related tricks. Let us refer to the elements of \(S\) as \(\{s_1, \ldots, s_\ell\}\), and let us call \(F(i)\), for \(i \in [\log d]\),⁸ to the event \(F_{s_i}\) if \(i \leq \ell\), and to the sample space \(\Omega\) (i.e., the event that always happens) otherwise. Then, we claim that for any \(0 \leq i \neq j \leq \lceil\log d\rceil\), we have \[\label{eq:quasi-independence} \Pr[F(i) \cap F(j)] = \Pr[F(i)] \cdot \Pr[F(j)],\tag{1}\] as either \(\max \{i, j\} \leq \ell\), in which case the claim holds by independence (since both events depend only on disjoint sets of independent random samples), or the claim holds trivially since \(\Pr[F(i)] = 1\) for \(i > \ell\). Therefore, we have \[\begin{align} \Pr\left[\bigcap_{k \in S} F_k\right] &= \Pr\left[F(0) \cap F(1) \cap \cdots \cap F(\lceil\log d\rceil)\right]\\ &= \prod_{i \in [\log d]} \Pr[F(i)]}\\ &\geq \left(1 - \frac{\gamma}{\log d}\right)^{\log d} \geq 1 - \gamma. \end{align}\]

We now argue that the event \(\bigcap_{k \in S} E_k\) happens with good probability. To see that, note first that for every \(k \in [d]\), line [line:delta] implies \[\Pr[\overline{E_k}] = \Pr\left[\delta^\star \in \left[v_k \pm \frac{\varepsilon \gamma}{\log d}\right]\right] \leq \frac{\frac{2\varepsilon \gamma}{\log d}}{2\varepsilon} = \frac{\gamma}{\log d}.\] Once again, we need to be careful as the events \(E_k\) are not independent of \(S\), nor between them this time. Using the law of total probabilities, we have \[\begin{align} \Pr\left[\bigcap_{k \in S} E_k\right] &= \sum_{S' \subseteq [d]} \Pr\left[S = S' \mid \bigcap_{k \in S'} E_k \right] \Pr\left[\bigcap_{k \in S'} E_k\right]\\ &= \sum_{\substack{S' \subseteq [d]\\ |S'| \leq \log d}} \Pr\left[S = S' \mid \bigcap_{k \in S'} E_k\right] \Pr\left[\bigcap_{k \in S'} E_k\right], \end{align}\] where we can now effectively use the union bound to say that for any fixed \(S'\) with \(|S'| \leq \log d\) we have \[\Pr\left[\bigcap_{k \in S'} E_k \right] \geq 1 - \gamma.\] Therefore, we conclude that \[\Pr\left[\bigcap_{k \in S} E_k\right] = \sum_{\substack{S' \subseteq [d]\\ |S'| \leq \log d}} \Pr\left[S = S'\mid \bigcap_{k \in S'} E_k\right] \Pr\left[\bigcap_{k \in S'} E_k\right] \geq (1-\gamma) \sum_{\substack{S' \subseteq [d]\\ |S'| \leq \log d}} \Pr\left[S = S' \mid \bigcap_{k \in S'} E_k\right]. \label{eq:align}\tag{2}\] It is not obvious, however, whether the sum on the right-hand side of 2  equals \(1\); we will, however, argue that it is at least \(1-\gamma\). Recall that \(\Pr[F_k | k \not\in S] \geq \Pr[F_k | k \in S]\) for any \(k\), from where it follows that for every set \(S'\) of size at most \(\log d\) we have \[\Pr\left[\bigcap_{k \in S'} F_k \right] \geq \Pr\left[\bigcap_{k \in S} F_k \right].\] Then, note that for any index \(k \in [d]\), the event \(F_k\) is conditionally independent of all events \(E_{j}\), with \(j \in [d]\) given the event \(k \in S\). That is, \[\Pr\left[F_k | k \in S\right] = \Pr\left[F_k | E_{j}, k \in S\right], \quad \text{for any } j \in [d].\] We thus deduce that for any fixed \(S'\) with \(|S'| \leq \log d\) we have \[\begin{align} \label{eq:2} \begin{aligned} \Pr\left[\bigcap_{k \in S'} F_k \mid \bigcap_{k \in S'} E_k\right] & \geq \Pr\left[\bigcap_{k \in S'} F_k \mid \bigcap_{k \in S'} E_k \text{ and } \bigcap_{k \in S'} {k \in S}\right] \\ &= \Pr\left[\bigcap_{k \in S'} F_k \mid \bigcap_{k \in S'} {k \in S}\right] \geq \Pr\left[\bigcap_{k \in S} F_k\right] \geq (1-\gamma). \end{aligned} \end{align}\tag{3}\] Then, our key observation is that there is a single value \(S^\star \subseteq [d]\), with \(|S^\star| \leq \log d\), that the binary search can take if we condition on all the events \(E_k\) and \(F_k\) happening, since in that case events \(A_k\) and \(B_k\) coincide. In other words, there exists \(S^\star\), with \(S^\star \subseteq [d]\) and \(|S^\star| \leq \log d\), such that \[\label{eq:prob1} \Pr\left[S = S^\star \mid \bigcap_{k \in S^\star} E_k \cap \bigcap_{k \in S^\star} F_k\right] = 1.\tag{4}\] We can then argue as follows: \[\begin{align} \Pr\left[\bigcap_{k \in S} E_k\right] &\geq (1-\gamma) \sum_{\substack{S' \subseteq [d]\\ |S'| \leq \log d}} \Pr\left[S = S' \mid \bigcap_{k \in S'} E_k\right]}\\ &\geq (1-\gamma) \Pr\left[S = S^\star \mid \bigcap_{k \in S^\star} E_k \right]\\ &\geq (1-\gamma) \Pr\left[S = S^\star \text{ and } \bigcap_{k \in S^\star} F_k \mid \bigcap_{k \in S^\star} E_k \right]\\ &= (1-\gamma) \Pr\left[S = S^\star \mid \bigcap_{k \in S^\star} E_k \cap \bigcap_{k \in S^\star} F_k\right] \cdot \Pr\left[\bigcap_{k \in S^\star} F_k \mid \bigcap_{k \in S^\star} E_k\right]\\ &\geq (1-\gamma)^2. } \end{align}\]

Therefore, the algorithm will succeed with probability at least \[\Pr\left[\bigcap_{k \in S} E_k\right] \cdot \Pr\left[\bigcap_{k \in S} F_k\right] \geq (1-\gamma)^3 \geq 1-3\gamma.\] The runtime is simply \(O(\log d \cdot M \cdot d )\); as (i) the binary search performs \(O(\log d)\) steps; (ii) each of the binary search steps requires \(M\) samples, and (iii) each sample requires evaluating the model \(\mathcal{L}\) and thus takes time \(O(d)\). Naturally, running the algorithm with \(\gamma' = 1/3 \cdot \gamma\) will yield a success probability of \(1-\gamma\) without changing the asymptotic runtime, and thus we conclude the proof. ◻

Proof sketch. Define the “locality” gap \(\mathrm{\small lgap}({\boldsymbol{y}})\) of a locally minimal \(\delta\)-SR \({\boldsymbol{y}}\) as the smallest value \(g\) such that \(|{\boldsymbol{y}}^\star|_\bot - |{\boldsymbol{y}}|_\bot = g\) for some \({\boldsymbol{y}}^\star \subseteq {\boldsymbol{y}}\) that is a \(\delta\)-SR. If \(g = 0\), then \({\boldsymbol{y}}\) is globally minimal, and we are done. If \(g\) were to be \(1\), then \({\boldsymbol{y}}\) would not be locally minimal, a contradiction. Therefore, we can safely assume \(g \geq 2\) from now on. Let \(\mathcal{L}, {\boldsymbol{y}}\) be such that \({\boldsymbol{y}}\) is locally minimal \(\delta\)-SR and \(\mathrm{\small lgap}({\boldsymbol{y}}) \geq 2\). We will find a contradiction by the following method:

• Let \({\boldsymbol{y}}^\star\) be the \(\delta\)-SR such that \(| {\boldsymbol{y}}\setminus {\boldsymbol{y}}^\star | = \mathrm{\small lgap}({\boldsymbol{y}})\).

• Every feature in \({\boldsymbol{y}}\setminus {\boldsymbol{y}}^\star\) is either “good”, if its score is positive, or “bad” if its score is negative.

• Fix any feature \(i\) in \({\boldsymbol{y}}\setminus {\boldsymbol{y}}^\star\). If \(i\) is good, then \({\boldsymbol{y}}^\star \oplus i\), meaning the partial instance obtained by taking \({\boldsymbol{y}}\) and setting its \(i\)-th feature to \(x_i\), has a probability guarantee greater or equal than that of \({\boldsymbol{y}}^\star\) (the proof of this fact is very similar to the proof of 1), and the gap has reduced. On the other hand, if \(i\) is bad, then \({\boldsymbol{y}}\ominus i\), meaning the partial instance obtained from \({\boldsymbol{y}}\) by setting \(y_i = \bot\), has greater-equal probability than \({\boldsymbol{y}}\), contradicting the fact that \({\boldsymbol{y}}\) is locally minimal.

 ◻

Proof. We can think of \(P(n, k)\) as the probability of getting at least \(k\) heads out of \(n\) tosses of a fair coin. By casing on the value (heads or tails) of the first coin we can see that for \(n \geq k \geq 1\) we have \[P(n, k) = \frac{1}{2}P(n-1, k-1) + \frac{1}{2}P(n-1, k),\] which we can rearrange into \[P(n, k) = P(n-1, k-1) + \frac{1}{2}\big[P(n-1, k) - P(n-1, k-1)\big],\] and thus \[P(n-1, k-1) - P(n, k) = \frac{1}{2}\big[P(n-1, k-1) - P(n-1, k)\big].\] But \(P(n-1, k-1) - P(n-1, k)\) is the probability of getting exactly \(k-1\) heads in \(n-1\) tosses, which is \(\frac{1}{2^{n-1}} \binom{n-1}{k-1}\), and clearly positive. Hence, using 3, we have \[0 \leq P(n-1, k-1) - P(n, k) \leq \frac{1}{2^{n}} \binom{n-1}{k-1} \leq \frac{1}{2^{n}} \binom{n-1}{\lfloor (n-1)/2 \rfloor} \leq \frac{1}{2^{n}} \frac{2^n}{\sqrt{ 2n - 1}} \leq \frac{1}{\sqrt{n}}.\] ◻

Proof. Fix any value of \(n\) and note that \(P(n, k-1) - P(n, k)\) is the probability of getting exactly \(k-1\) heads in \(n\) tosses of a fair coin. Thus, for any \(k \in \{1, \ldots, n\}\) we can use 3 to say \[\label{eq:prob-diff} P(n, k-1) - P(n, k) = \frac{1}{2^{n}} \binom{n}{k-1} \leq \frac{1}{2^{n}} \binom{n}{\lfloor n/2 \rfloor} \leq \frac{1}{2^{n}} \frac{2^n}{\sqrt{2n+1}} \leq \frac{1}{\sqrt{n}}.\tag{5}\] Now, choose a large enough \(n\) so that \(\frac{1}{\sqrt{n}} < \varepsilon\). Then, choose \(k\) as the largest integer such that \(P(n, k) \geq \delta\), which exists since \(P(n, 0) = 1\) and \(P(n, n+1) = 0\). This definition of \(k\) yields \[P(n, k) \geq \delta > P(n, k+1),\] and using 5 we can see that \[|P(n, k+1) - \delta| = \delta - P(n, k+1) \leq P(n, k) - P(n, k+1) \leq \frac{1}{\sqrt{n}} < \varepsilon,\] which completes the proof. ◻

Proof of 2. Let \(\delta\) and \(\varepsilon\) be the values in the statement of the proposition. Let \(n\) and \(m\) be large integers whose precise value will be determined later. We will construct a linear model \(\mathcal{L}\) of dimension \(d = n+1\), with threshold \(t = 2\), and weights \(w_1 = 1\), \(w_i = 1/m\) for \(i \in \{2, \ldots, d\}\). Let \({\boldsymbol{x}}= (1, 1, \ldots, 1) \in \{0, 1\}^d\) be the instance to explain, and \({\boldsymbol{y}}= (1, \bot, \bot, \ldots, \bot) \subseteq {\boldsymbol{x}}\) be a partial instance. Now, use 5 with parameters \(\delta' = \delta + \varepsilon/4\) and \(\varepsilon' = \varepsilon/4\) to choose values for \(n, m\) such that \[\left|P\big(n,\, m\big) - \delta'\right| < \varepsilon',\] with \(m \leq n\). Note now that \(\mathcal{L}({\boldsymbol{x}}) = 1\), and that \[\label{eq:prob-lin} \Pr_{{\boldsymbol{z}}\sim \mathbf{U}({\boldsymbol{y}})}\left[\mathcal{L}({\boldsymbol{z}}) = 1\right] = P\big(n,\, m\big),\tag{6}\] since in order for a completion of \({\boldsymbol{y}}\) to have \(\mathcal{L}({\boldsymbol{z}}) = 1\) it must have at least \(m\) features (besides the 1st one) set to \(1\), as that way its value according to the weights \(w_i\) will be at least \(1 + m \cdot 1/m = 2 = t\). As we have \[\left|P\big(n,\, m\big) - (\delta+ \varepsilon/4) \right| < \varepsilon/4,\] we can deduce \[\delta \leq P\big(n,\, m\big) \leq \delta + \varepsilon/2.\] Combining our last equation with 6 we have that \({\boldsymbol{y}}\) is a \(\delta\)-SR for \({\boldsymbol{x}}\) of size \(1\). Now, let us see how many more features need to be added to \({\boldsymbol{y}}\) in order to get a \((\delta+\varepsilon)\)-SR. Suppose that we add \(k\) features to \({\boldsymbol{y}}\) (as all features are equal, we add any \(k\) of them) obtaining a partial instance \({\boldsymbol{y}}'\). Then, we have that \[\Pr_{{\boldsymbol{z}}\sim \mathbf{U}({\boldsymbol{y}}')}\left[\mathcal{L}({\boldsymbol{z}}) = 1\right] = P\big(n - k,\, m - k\big),\] as now \(k\) features have been set to \(1\). We can now use 4 \(k\) times in a row: \[\begin{align} P(n-k, m - k) &\leq P(n-k+1, m - k+1) + \frac{1}{\sqrt{n-k}}\\ &\leq P(n-k+2, m - k+2) + \frac{1}{\sqrt{n-k}} + \frac{1}{\sqrt{n-k+1}}\\ & \leq P(n-k+2, m - k+2) + \frac{2}{\sqrt{n-k}}\\ & \vdots\\ & \leq P(n, m) + \frac{k}{\sqrt{n-k}}. \end{align}\]

Therefore, we have that \[P(n-k, m - k) \leq P(n, m) + \frac{k}{\sqrt{n-k}} \leq \delta + \varepsilon/2 + \frac{k}{\sqrt{n-k}}.\] It now remains to show that, unless \(k\) is large enough (relatively to \(n\)), the right-hand side of the previous inequality is less than \(\delta + \varepsilon\). Indeed, take \(k = n^{1/2 - \gamma}\) for any positive \(\gamma\). Then, we want to show that for sufficiently large \(n\) we have \[\frac{k}{\sqrt{n-k}} < \varepsilon/2.\] To do so, note that \[\frac{k}{\sqrt{n-k}} < \frac{k}{\sqrt{n}} = \frac{n^{1/2 - \gamma}}{n^{1/2}} = n^{-\gamma},\] from where taking \(n > \left(\frac{2}{\varepsilon}\right)^{1/\gamma}\) suffices to complete the proof. ◻

Proof of 1. The proof is a twist on  [6]; let \((s_1, \ldots, s_n, T) \in \mathbb{N}^{n+1}\) be an instance of the \(\# \mathrm{P}\)-complete problem \(\#\mathrm{\small Knapsack}\), that consists on counting the number of sets \(S \subseteq \{s_1, \ldots, s_n\}\) such that \(\sum_{s \in S}s \leq T\). We can assume that \(\sum_{i=1}^n s_i > T\), as otherwise the \(\# \mathrm{\small Knapsack}\) instance is trivial. Then, let \(\mathcal{L}\) be a linear model with weights \(w_i = s_i\), and threshold \(t = T+1\). Now, consider the problem of deciding whether \(\#\mathrm{\small Knapsack}(s_1, \ldots, s_n, T) \geq m\) for an input \(m\), which cannot be solved in polynomial time unless \(\mathrm{P}= \# \mathrm{P}\). Let \({\boldsymbol{x}}= (1, 1, \ldots, 1)\), and \(\delta = \frac{m}{2^{n}}\). We claim that \((\mathcal{L}, {\boldsymbol{x}}, \delta, k=0)\) is a Yes-instance for Uniform-Min-\(\delta\)-SR\((\mathrm{\small Linear})\) if and only if \(\#\mathrm{\small Knapsack}(s_1, \ldots, s_n, T) \geq m\). First, note that \(\mathcal{L}({\boldsymbol{x}}) = 1\), since \(\sum_{i=1}^n w_i x_i = \sum_{i=1}^n s_i \geq T+1 = t\). For every set \(S \subseteq \{s_1, \ldots, s_n\}\) such that \(\sum_{s \in S}s \leq T\), its complement \(\overline{S} := \{s_1, \ldots, s_n\} \setminus S\) holds \(\sum_{s \in \overline{S}}s > T\), and as all values are integers, this implies as well \[\sum_{s \in \overline{S}} s \geq T+1 = t.\] To each such set \(\overline{S}\), we associate the instance \({\boldsymbol{z}}(\overline{S})\) defined as \[z(\overline{S})_i = \begin{cases} 1 & \text{if } s_i \in \overline{S}\\ 0 & \text{otherwise}. \end{cases}\] Now note that \[\mathcal{L}({\boldsymbol{z}}(\overline{S})) = \begin{cases} 1 & \text{if } \sum_{s_i \in \overline{S}} w_i \geq T+1\\ 0 & \text{otherwise} \end{cases} = 1,\] and thus there is a bijection between the sets \(S\) whose sum is at most \(T\) and the instances \({\boldsymbol{z}}(\overline{S})\) such that \(\mathcal{L}({\boldsymbol{z}}(\overline{S})) = 1 = \mathcal{L}({\boldsymbol{x}})\). To conclude, simply note that the previous bijection implies \[\Pr_{{\boldsymbol{z}}\sim \mathbf{U}(\bot^d)}\Big[\mathcal{L}({\boldsymbol{z}}) = 1\Big] = \frac{\#\mathrm{\small Knapsack}(s_1, \ldots, s_n, T)}{2^n},\] and thus the “empty explanation” \(\bot^d := (\bot, \bot, \ldots, \bot)\) has probability at least \(\delta\) if and only if \[\#\mathrm{\small Knapsack}(s_1, \ldots, s_ n, T) \geq m.\] As the empty explanation is the only one with size \(\leq 0\), we conclude the proof. ◻

Proof of 6. Let \((w_1, \ldots, w_d)\) be the weights of \(\mathcal{L}\) and \(t\) its threshold. Then, let us assume without loss of generality that \(\mathcal{L}({\boldsymbol{x}}) = 1\), as the case \(\mathcal{L}({\boldsymbol{x}}) = 0\) is analogous. We thus have that \[s_i = w_i \cdot (2x_i - 1) \geq 0,\] from where \(s_i = w_i\) if \(x_i = 1\) and \(s_i = -w_i\) if \(x_i = 0\). Let us denote by \(S\) the set of features \(j\) such that \(y_j = x_j \neq \bot\), and define \[t' := t - \sum_{j \in S} y_j w_j.\] We can then rewrite the probability of interest as \[\Pr_{{\boldsymbol{z}}\sim \mathbf{D}({\boldsymbol{y}})}[\mathcal{L}({\boldsymbol{z}}) = \mathcal{L}({\boldsymbol{x}})] = \Pr_{{\boldsymbol{z}}\sim \mathbf{D}({\boldsymbol{y}})}[\mathcal{L}({\boldsymbol{z}}) = 1] = \Pr_{{\boldsymbol{z}}\sim \mathbf{D}({\boldsymbol{y}})}\left[\sum_{j \not\in S} z_j w_j \geq t'\right].\] Let us define the following two amounts: \[\mathcal{A} := \Pr_{{\boldsymbol{z}}\sim \mathbf{D}({\boldsymbol{y}})}\left[\sum_{j \not\in S, j \neq i} z_j w_j \geq t' - w_i\right],\] \[\mathcal{B} := \Pr_{{\boldsymbol{z}}\sim \mathbf{D}({\boldsymbol{y}})}\left[\sum_{j \not\in S, j \neq i} z_j w_j \geq t'\right].\] If \(p_i\) is the probability of feature \(i\) under \(\mathbf{D}\), then we have \[\Pr_{{\boldsymbol{z}}\sim \mathbf{D}({\boldsymbol{y}})}[\mathcal{L}({\boldsymbol{z}}) = \mathcal{L}({\boldsymbol{x}})] = \Pr_{{\boldsymbol{z}}\sim \mathbf{D}({\boldsymbol{y}})}\left[\sum_{j \not\in S} z_j w_j \geq t'\right] = p_i \cdot \mathcal{A} + (1-p_i)\cdot \mathcal{B}.\] Now we proceed by cases on \(x_i\). If \(x_i = 1\), then \(s_i = w_i\), and thus we know \(w_i \geq 0\), from where \(t' - w_i \leq t'\) and thus \(\mathcal{A} \geq \mathcal{B}\). Moreover, as \(x_i = 1\), we conclude \[\begin{align} \Pr_{{\boldsymbol{z}}\sim \mathbf{D}({\boldsymbol{y}}\oplus i)}[\mathcal{L}({\boldsymbol{z}}) = \mathcal{L}({\boldsymbol{x}})] &= \mathcal{A}\\ &= p_i \cdot \mathcal{A} + (1-p_i)\cdot \mathcal{A}\\ &\geq p_i \cdot \mathcal{A} + (1-p_i)\cdot \mathcal{B}\\ &= \Pr_{{\boldsymbol{z}}\sim \mathbf{D}({\boldsymbol{y}})}[\mathcal{L}({\boldsymbol{z}}) = \mathcal{L}({\boldsymbol{x}})]. \end{align}\]

Similarly, if \(x_i = 0\), then \(s_i = -w_i\), and thus we know \(w_i \leq 0\), from where \(t' - w_i \geq t'\) and thus \(\mathcal{A} \leq \mathcal{B}\). As \(x_i = 0\), we conclude \[\begin{align} \Pr_{{\boldsymbol{z}}\sim \mathbf{D}({\boldsymbol{y}}\oplus i)}[\mathcal{L}({\boldsymbol{z}}) = \mathcal{L}({\boldsymbol{x}})] &= \mathcal{B}\\ &= p_i \cdot \mathcal{B} + (1-p_i)\cdot \mathcal{B}\\ &\geq p_i \cdot \mathcal{A} + (1-p_i)\cdot \mathcal{B}\\ &= \Pr_{{\boldsymbol{z}}\sim \mathbf{D}({\boldsymbol{y}})}[\mathcal{L}({\boldsymbol{z}}) = \mathcal{L}({\boldsymbol{x}})]. \end{align}\] This concludes the proof. ◻

Proof of 8. Let us assume without loss of generality that the features are already sorted decreasingly in terms of score, so \[s_1 \geq s_2 \geq \cdots \geq s_d.\] This way, we have that \({\boldsymbol{y}}^{(k)} \subseteq {\boldsymbol{x}}\) is defined as follows: \[y^{(k)}_i = \begin{cases} x_i & \text{if } i \leq k\\ \bot & \text{otherwise}. \end{cases}\] The proof now requires considering two cases. First, if \(s_{k+1} \geq 0\), then we can apply 6 to conclude that \[\Pr_{{\boldsymbol{z}}\sim \mathbf{U}({\boldsymbol{y}}^{(k+1)})}[\mathcal{L}({\boldsymbol{z}}) = \mathcal{L}({\boldsymbol{x}})] \geq \Pr_{{\boldsymbol{z}}\sim \mathbf{U}({\boldsymbol{y}}^{(k)})}[\mathcal{L}({\boldsymbol{z}}) = \mathcal{L}({\boldsymbol{x}})].\] We will now show that if \(s_{k+1} < 0\), then \[\Pr_{{\boldsymbol{z}}\sim \mathbf{U}({\boldsymbol{y}}^{(k+1)})}[\mathcal{L}({\boldsymbol{z}}) = \mathcal{L}({\boldsymbol{x}})] = 1,\] which will be enough to conclude. Indeed, as \(s_{k+1} < 0\), we have that \[0 > s_{k+2} \geq s_{k+3} \geq \cdots \geq s_d,\] from where we can repeatedly apply 7 to deduce \[\Pr_{{\boldsymbol{z}}\sim \mathbf{U}({\boldsymbol{y}}^{(k+1)})}[\mathcal{L}({\boldsymbol{z}}) = \mathcal{L}({\boldsymbol{x}})] \geq \Pr_{{\boldsymbol{z}}\sim \mathbf{U}({\boldsymbol{y}}^{(k+2)})}[\mathcal{L}({\boldsymbol{z}}) = \mathcal{L}({\boldsymbol{x}})] \geq \cdots \geq \Pr_{{\boldsymbol{z}}\sim \mathbf{U}({\boldsymbol{y}}^{(d)})}[\mathcal{L}({\boldsymbol{z}}) = \mathcal{L}({\boldsymbol{x}})] = 1.\] This concludes the proof. ◻

Proof of 9. For the forward direction, assume that \(\operatorname{\textrm{\mathrm{\small Min}}}(\mathcal{L}, {\boldsymbol{x}}, \delta) = k\). Then, by definition, we have that there exists a \(\delta\)-SR \({\boldsymbol{y}}^\star\) for \({\boldsymbol{x}}\) such that \({\boldsymbol{y}}^\star\) has \(k\) defined features. By 10, we have that \[\Pr_{{\boldsymbol{z}}\sim \mathbf{U}({\boldsymbol{y}}^{(k)})}\left[\mathcal{L}({\boldsymbol{z}}) = \mathcal{L}({\boldsymbol{x}})\right] \geq \Pr_{{\boldsymbol{z}}\sim \mathbf{U}({\boldsymbol{y}}^\star)}\left[\mathcal{L}({\boldsymbol{z}}) = \mathcal{L}({\boldsymbol{x}})\right] \geq \delta,\] and thus \({\boldsymbol{y}}^{(k)}\) is a \(\delta\)-SR for \({\boldsymbol{x}}\). On the other hand, if \({\boldsymbol{y}}^{(k-1)}\) were to be a \(\delta\)-SR for \({\boldsymbol{x}}\), then we would have \(\operatorname{\textrm{\mathrm{\small Min}}}(\mathcal{L}, {\boldsymbol{x}}, \delta) \leq k-1\), a contradiction. For the backward direction, assume that \({\boldsymbol{y}}^{(k)}\) is a \(\delta\)-SR for \({\boldsymbol{x}}\) but \({\boldsymbol{y}}^{(k-1)}\) is not. Then, by 10, we have that \[\delta > \Pr_{{\boldsymbol{z}}\sim \mathbf{U}({\boldsymbol{y}}^{(k-1)})}[\mathcal{L}({\boldsymbol{z}}) = \mathcal{L}({\boldsymbol{x}})] = \max_{{\boldsymbol{y}}\in P_{k-1}} \Pr_{{\boldsymbol{z}}\sim \mathbf{U}({\boldsymbol{y}})}[\mathcal{L}({\boldsymbol{z}}) = \mathcal{L}({\boldsymbol{x}})],\] from where \(\operatorname{\textrm{\mathrm{\small Min}}}(\mathcal{L}, {\boldsymbol{x}}, \delta) > k-1\), and because \({\boldsymbol{y}}^{(k)}\) is a \(\delta\)-SR for \({\boldsymbol{x}}\), we have \(\operatorname{\textrm{\mathrm{\small Min}}}(\mathcal{L}, {\boldsymbol{x}}, \delta) \leq k\); we conclude that \(\operatorname{\textrm{\mathrm{\small Min}}}(\mathcal{L}, {\boldsymbol{x}}, \delta) = k\). ◻

Proof of 10. Let \(w_1, \ldots, w_d\) be the weights of \(\mathcal{L}\), and \(t\) its threshold. Let us use the \(\oplus, \ominus\) notation defined in [lemma:positive-score,lemma:negative-score]. We will prove something slightly stronger than 10: that if \(i\) and \(j\) are features such that \(s_i \leq s_j\), then for any partial instance \({\boldsymbol{y}}\) such that \(y_i \neq \bot\) and \(y_j = \bot\), we have \[\Pr_{{\boldsymbol{z}}\sim \mathbf{U}({\boldsymbol{y}}\ominus i \oplus j)}[\mathcal{L}({\boldsymbol{z}}) = \mathcal{L}({\boldsymbol{x}})] \geq \Pr_{{\boldsymbol{z}}\sim \mathbf{U}({\boldsymbol{y}})}[\mathcal{L}({\boldsymbol{z}}) = \mathcal{L}({\boldsymbol{x}})].\] If we prove this, then we can apply it repeatedly to deduce 10. To prove the claim, we start by defining \[S = \{ \ell \mid y_\ell \neq \bot \} \setminus \{i \},\] and \[t' = t - \sum_{\ell \in S} y_\ell w_\ell.\] We will also assume without loss of generality that \(\mathcal{L}({\boldsymbol{x}}) = 1\) since the other case is analogous. We can then rewrite the probabilities of interest as follows, using notation \(\bar{S} := [d] \setminus S\): \[\Pr_{{\boldsymbol{z}}\sim \mathbf{U}({\boldsymbol{y}}\ominus i \oplus j)}[\mathcal{L}({\boldsymbol{z}}) = \mathcal{L}({\boldsymbol{x}})] = \Pr_{{\boldsymbol{z}}\sim \mathbf{U}({\boldsymbol{y}}\ominus i \oplus j)}\left[\sum_{\ell \in \bar{S} \setminus \{i, j\}} z_\ell w_\ell + x_j w_j + z_i w_i\geq t'\right],\] \[\Pr_{{\boldsymbol{z}}\sim \mathbf{U}({\boldsymbol{y}})}[\mathcal{L}({\boldsymbol{z}}) = \mathcal{L}({\boldsymbol{x}})] = \Pr_{{\boldsymbol{z}}\sim \mathbf{U}({\boldsymbol{y}})}\left[\sum_{\ell \in \bar{S} \setminus \{i, j\}} z_\ell w_\ell + x_i w_i + z_j w_j\geq t'\right].\] Let us write \(t^\star = t' - \sum_{\ell \in \bar{S} \setminus \{i, j\}} z_\ell w_\ell\), and note that \(t^\star\) is a random variable. With this notation, it remains to prove that

\[\begin{align} &\Pr_{z_i, t^\star}[z_i w_i + x_j w_j \geq t^\star] \geq \Pr_{z_i, t^\star}[z_j w_j + x_i w_i \geq t^\star] \\ \iff& \frac{1}{2}\Pr_{t^\star}[w_i + x_j w_j \geq t^\star] + \frac{1}{2}\Pr_{t^\star}[x_j w_j \geq t^\star] \geq \frac{1}{2}\Pr_{t^\star}[w_j + x_i w_i \geq t^\star] + \frac{1}{2}\Pr_{t^\star}[x_i w_i \geq t^\star] \\ \iff& \Pr_{t^\star}[w_i + x_j w_j \geq t^\star] + \Pr_{t^\star}[x_j w_j \geq t^\star] \geq \Pr_{t^\star}[w_j + x_i w_i \geq t^\star] + \Pr_{t^\star}[x_i w_i \geq t^\star]. \end{align}\] We will prove the last inequality by cases, recalling that \(s_j \geq s_i\) and thus \(w_j (2x_j - 1) \geq w_i (2x_i - 1)\).

• (Case 1: \(x_i = 1, x_j = 1\)) The desired inequality is \[\begin{align} \Pr_{t^\star}[w_i + w_j \geq t^\star] + \Pr_{t^\star}[w_j \geq t^\star] &\geq \Pr_{t^\star}[w_j + w_i \geq t^\star] + \Pr_{t^\star}[w_i \geq t^\star]\\ \iff \Pr_{t^\star}[w_j \geq t^\star] &\geq \Pr_{t^\star}[w_i \geq t^\star], \end{align}\] which is true since \(s_j \geq s_i\) implies \(w_j \geq w_i\) given \(x_i = x_j = 1\).

• (Case 2: \(x_i = 1, x_j = 0\)) The desired inequality is \[\begin{align} \Pr_{t^\star}[w_i \geq t^\star] + \Pr_{t^\star}[0\geq t^\star] &\geq \Pr_{t^\star}[w_j + w_i \geq t^\star] + \Pr_{t^\star}[w_i \geq t^\star]\\ \iff \Pr_{t^\star}[0 \geq t^\star] &\geq \Pr_{t^\star}[w_j + w_i \geq t^\star], \end{align}\] which is true since \(s_j \geq s_i\) implies \(-w_j \geq w_i\) given \(x_i = 1, x_j = 0\), and thus \(w_i + w_j \leq 0\).

• (Case 3: \(x_i = 0, x_j = 1\)) The desired inequality is \[\begin{align} \Pr_{t^\star}[w_i + w_j \geq t^\star] + \Pr_{t^\star}[w_j \geq t^\star] &\geq \Pr_{t^\star}[w_j \geq t^\star] + \Pr_{t^\star}[0 \geq t^\star],\\ \iff \Pr_{t^\star}[w_i + w_j \geq t^\star] &\geq \Pr_{t^\star}[0\geq t^\star], \end{align}\] which is true since \(s_j \geq s_i\) implies \(w_j \geq -w_i\) given \(x_i = 0, x_j = 1\), and thus \(w_i + w_j \geq 0\).

• (Case 4: \(x_i = 0, x_j = 0\)) The desired inequality is \[\begin{align} \Pr_{t^\star}[w_i \geq t^\star] + \Pr_{t^\star}[0 \geq t^\star] &\geq \Pr_{t^\star}[w_j \geq t^\star] + \Pr_{t^\star}[0 \geq t^\star],\\ \iff \Pr_{t^\star}[w_i \geq t^\star] &\geq \Pr_{t^\star}[w_j \geq t^\star], \end{align}\] which is true since \(s_j \geq s_i\) implies \(-w_j \geq -w_i\) given \(x_i = x_j = 0\), and thus \(w_i \geq w_j\).

 ◻