Model Reconstruction from Model Explanations

Introduction

Commercial machine learning models increasingly support consequential decisions in numerous domains including medical diagnosis, employment, and criminal justice. In such applications, there is now growing demand for methods that explain a model’s decision. The secrecy of a model strongly fuels this demand.

At the same time, there are a number of valid reasons a company might wish to keep its machine learning models secret. The competitive value of the product is one consideration. Revealed models may also be easier to game, resulting in diminished predictive power . Yet another reason is that the model might leak sensitive information about the data it was trained on .

In this work, we point out a tension between keeping a model secret and explaining its decisions. We show that a popular class of existing methods to explain a model’s decision quickly reveals the model itself in what is typically an undesired side effect.

Numerous explanation methods have been proposed in an ongoing line of research. Among these methods, saliency maps are a widespread technique to highlight characteristics of an input deemed relevant for the prediction of a model. The most basic saliency map is to compute the gradient of the model with respect to a chosen input and numerous variants add different transformations to the raw gradients leading to some disagreement over which of these heuristics is preferable in what context . Abstracting away from these implementation details, we focus on reconstructing models given the basic underlying primitive, which is gradients of the model with respect to its inputs.

Our contributions are twofold, spanning both a theoretical and experimental component.

Learning from input gradients. On the theoretical side, we introduce a model of learning from input gradient queries. In this model, a learning algorithm can observe gradients of an unknown model at chosen query inputs. This model turns out to be rich in its mathematical structure and connections to standard learning models, such as learning from membership queries, in which the learner can request the model’s prediction at a given input.

Assuming the rows of the weight matrix $A$ are linearly independent, our algorithm recovers a functionally equivalent model from $O(h\log h)$ input gradient queries and function evaluations with high probability.

The $O(h\log h)$ queries our theorem requires is optimal to within a logarithmic factor, since it takes $dh+h$ parameters to specify the model, and each query reveals only $O(d)$ numbers. Furthermore, compared to membership queries, gradient queries reduce the number of queries needed by approximately a factor of $d$, since it takes $\Omega(dh)$ membership queries to specify the model.

Although our algorithm enjoys an intuitive geometric interpretation, the proof requires a delicate argument, as well as an anti-concentration bound that may be useful independently.

Practical reconstruction methods. In a second step, we explore practically effective heuristics to reconstruct a model from input gradient queries. Our experiments show that reconstructing models from explanations is not just a theoretical concern. If a company were to provide an explanation API with standard saliency maps, it would effectively give up the underlying model, which it may not be willing to do for reasons mentioned above. This situation parallels an ongoing investigation on stealing models from prediction APIs . However, as our results show, with explanation APIs we need far fewer queries, thus greatly exacerbating the threat of model leakage.

Our experiments focus on a heuristic for learning from input query gradients. While our theoretical method is specific to two-layer networks, our heuristic is agnostic to the shape of the target model. At the outset, our heuristic simply queries a number of input gradients and fits a model against the observed gradients in much the same way we would fit a model against labels. We find that this heuristic reduces the number of queries needed to learn models on MNIST and CIFAR10 by orders of magnitude, even in cases where the model class is unknown or the data distribution is unknown.

Conclusion. Our work demonstrates that establishing usable explanation methods for machine learning models faces another hurdle in commercial applications. Whatever criteria of explanation quality we choose must be weighed against the risk of model leakage resulting from the method at hand. We see our work as only a first step in this new direction that raises many intriguing questions.

Problem statement: reconstructing a two-layer ReLU network

We consider the problem of finding a classifier $\hat{f}$ identical to an unknown classifier $f$ when given access to membership and gradient queries. That is, we assume access to an oracle that given a query input $x$ returns the evaluation of $f$ at $x$ and the gradient $\nabla_{x}f(x)$ of $f$ with respect to $x.$

The rows $A_{1},\dots A_{h}$ are unit vectors.

No two rows $A_{i}$ and $A_{j}$ with $i\neq j$ are collinear, i.e., $\langle A_{i},A_{j}\rangle\leq 1-c$ for some $c>0$.

The rows $A_{1},\dots,A_{h}$ are linearly independent.

The first two assumptions are without loss of generality, as they follow from simple reparameterizations of the network that involve scaling $w$ or $A$ or reducing the hidden dimension.

Our main result is the following theorem, which shows that our sample complexity for learning the function with gradient queries has no dependence on the input dimension $d$.

Suppose, the unknown function $f$ satisfies our assumptions. Then, with probability $1-\delta$, Algorithm 1 succeeds to find a function $\hat{f}$ such that $\hat{f}=f$ in $O(h\log\frac{h}{\delta})$ queries. If the Algorithm fails, then it notifies of the failure.

Section 3 contains our algorithm and proof of correctness. In Appendix C we show that our algorithm can also be converted to one which learns the function $f$ in $O(dh\log\frac{h}{\delta})$ membership queries by using membership queries to approximate gradients of $f$.

Algorithm

Before we formally introduce our algorithm, we briefly provide some high-level intuition. First, note that we can express our two-layer ReLU networks as

Our algorithm can be separated into two steps. First, we find the separating hyperplanes of $f$. In particular, we recover unsigned, weighted normal vectors $w_{i}A_{i}$ or $-w_{i}A_{i}$ for $i\in[h]$. The second step then recovers the sign information for these normal vectors. More precisely, the two steps are the following:

Recover a vector $s\in\{-1,0,1\}^{2h}$ such that $f(x)=\begin{bmatrix}\max(Zx,0)^{\top}&\max(-Zx,0)^{\top}\end{bmatrix}s$. (Algorithm 3)

Together, the matrix $Z$ and vector $s$ identify the function $f$. We analyze the first step in Section 3.1 and the second step in Section 3.2.

Algorithm 2 finds the separating hyperplanes by exploiting the structure of the gradient of $f$:

In this way, Algorithm 2 isolates changes in the gradient of $f$ to recover $w_{i}A_{i}$ up to a sign for every $i\in[h]$. Figure 1 provides an illustrated explanation of the algorithm, which we briefly sketch below:

Repeat Step (2) $h$ times to recover all rows $w_{i}A_{i}$ up to their sign, which become the rows of the matrix $Z$.

The proof of correctness relies on showing that with high probability, the following two events hold: (i) The points at which the gradient of $f$ changes are spaced sufficiently far apart. (ii) The same gradient change points are within some line segment of $u$ and $v$ that is not too big. The change points can then be found with a binary search that is bounded within a range that is not too large and uses step sizes that are not too small. In the next lemma, we prove correctness of the binary search given that the change points are spaced appropriately.

Let $k_{1},\dots,k_{h}$ be the indices such that $t_{k_{1}}<t_{k_{2}}<\dots<t_{k_{h}}$. To prove the lemma we will show that on the $i$-th call to binarySearch, either $-w_{k_{i}}A_{k_{i}}$ or $w_{k_{i}}A_{k_{i}}$ is added as a row to matrix $Z$.

First, we make the following assumption, which we will later prove: assume that $t_{k_{i}}=\min_{j:t_{j}\geq t^{(i)}_{l}}t_{j}$ where $t^{(i)}_{l}$ is the value of the variable $t_{l}$ at the start of the $i$-th call to binarySearch. Given this assumption, the $i$-th call to binarySearch adds $-w_{k_{i}}A_{k_{i}}$ or $w_{k_{i}}A_{k_{i}}$ to the matrix $Z$. To see this, note that on each iteration of the while loop in binarySearch either the variable $t_{l}$ increases or the variable $t_{r}$ decreases, and thus binarySearch always terminates. However, $t_{l}$ dose not increase past $t_{k_{i}}$ and $t_{r}$ does not decrease past $t_{k_{i}}$. So, when the condition for termination of the while loop is met we have $|t_{l}-t_{r}|\leq\epsilon$, $t_{l}\leq t_{k_{i}}$, and $t_{r}\geq t_{k_{i}}$. Since $|t_{k_{j}}-t_{k_{i}}|\geq\epsilon$ for all $j\neq i$, the row $\nabla f(t_{r})-\nabla f(t_{l})$ returned by binarySearch is equal to either $w_{k_{i}}A_{k_{i}}$ or $-w_{k_{i}}A_{k_{i}}$.

Now we revisit the assumption that $t_{k_{i}}=\min_{j:t_{j}\geq t^{(i)}_{l}}t_{j}$. We prove the assumption by induction. The base case $i=0$ is clearly true: $t_{k_{1}}=\min_{j}t_{j}=\min_{j:t_{j}\geq t^{(i)}_{l}}t_{j}$ because $t^{(1)}_{l}=-l$ and $-l\leq t_{k_{1}}<t_{k_{2}}<t_{k_{l}}\leq l$. On the $(i+1)$-th call to binarySearch the variable $t_{l}$ is set to the value of $t_{r}$ when the $i$-th call to binarySearch terminated. When the $i$-th call to binarySearch finishes, the value of the variable $t_{r}$ is above $\min_{j:t_{j}\geq t^{(i)}_{l}}t_{j}=t_{k_{i}}$, but less than $t_{k_{i+1}}$. Thus, $t_{k_{i+1}}=\min_{j:t_{j}\geq t^{(i+1)}_{l}}t_{j}$.

Therefore, the returned matrix $Z$ is such that $Z_{p(i)}=w_{i}A_{i}$ or $Z_{p(i)}=-w_{i}A_{i}$ where the permutation $p$ of $[h]$ is defined by $p(i)=j$ where $k_{j}=i$. ∎

The next two lemmas (proved in Appendix A) establish the necessary anti-concentration and concentration bounds for showing that the change points are spaced sufficiently far apart (Lemma 2), but still within some line segment of $u$ and $v$ that is not too big (Lemma 3).

Finally, the proof of our main theorem for Algorithm 2 follows by combining the probabilistic guarantees of Lemmas 2 and 3 with the deterministic proof of correctness in Lemma 1.

By Lemma 1, if $|t_{i}-t_{j}|$ and $|t_{i}|\leq l$ for all $i$ and $j\neq i$, then Algorithm 2 succeeds. The probability of this event can be lower-bounded as the following.

Let $\delta=3^{\frac{4}{3}}\left(\frac{\epsilon}{c}\right)^{\frac{2}{3}}h^{2}-\frac{2}{\pi l}h$. Set $l=h^{2}$. Then, solving for $\epsilon$ yields $\epsilon=3^{-2}c\frac{(\delta+\frac{2\pi}{h})^{\frac{3}{2}}}{h^{3}}$. So, Algorithm 2 succeeds with probability $1-\delta$ and uses less than $h\log\left(\frac{l}{\epsilon}\right)$ queries, which is upper bounded as the following.

2 Step two: recovering the signs of the normal vectors

Algorithm 2 recovers unsigned, weighted normal vectors: $w_{i}A_{i}$ or $-w_{i}A_{i}$ for $i\in[h]$. But to identify the function $f$, we still need the sign of these vectors. In Algorithm 3, we recover a vector $s\in\{-1,0,1\}^{2h}$ that encodes this sign information. Precisely, Algorithm 3 returns a vector $s$ such that

It is clear that if Algorithm 3 returns the vector $s$, then the function $f$ is identified. Algorithm 3 solves $2h$ linear equations to determine the vector $s$. To prove correctness of Algorithm 3, we show that the $2h$ query points picked in the algorithm lead to a determined set of linear equations.

The determinant of the matrix is $\det(M)=\det((ZX)^{2}-0)=\det^{2}(ZX)>0$. Thus, $M$ is a full-rank matrix. ∎

In Appendix B we describe a simple linear program that can be used to pick a matrix $X$ that satisfies the conditions of the above Lemma 4. Since Algorithm 3 picks such a matrix $X$, Lemma 4 immediately implies our main theorem proving correctness of Algorithm 3.

Together, Theorem 2 proving correctness of Algorithm 2 and Theorem 3 proving correctness of 3 imply our main Theorem 1 that proves correctness of Algorithm 1.

Suppose the unknown function $f$ satisfies the assumptions in Section 2. Then, with probability $1-\delta$, Algorithm 1 succeeds to find a function $\hat{f}$ such that $\hat{f}=f$ in $O(h\log\frac{h}{\delta})$ queries. If the Algorithm fails, then it notifies of the failure.

By Theorem 2, with probability $1-\delta$, Algorithm 2 returns a matrix $Z$ that satisfies the conditions of Theorem 3 in $O(h\log\frac{h}{\delta})$ queries. By Theorem 3, Algorithm 3 then returns a vector $s$ such that $f(x)=\begin{bmatrix}\max(Zx,0)^{\top}&\max(-Zx,0)^{\top}\end{bmatrix}s$ in $O(h)$ queries. Thus, overall Algorithm 1 succeeds with probability $1-\delta$ in $O(h\log h)$ queries. ∎

Experimental design

While our theoretical analysis provides insight into the power of gradient queries over membership queries, it is specific to a two-layer ReLU network. To complement our theory, we also experimentally investigate the impact of gradients on reconstructing models used in practice.

Manipulated factors. We manipulate three independent variables. First, we manipulate the type of query. We test membership only queries as well as membership and gradients. Further, because in practice explanations often provide a processed version of the gradients, instead of the raw gradients, we also test membership and gradients processed with SmoothGrad, a saliency map denoising technique . Instead of returning the raw gradient $\nabla f(x)$, SmoothGrad returns an average of gradients around the input $x$: $\widetilde{\nabla}f(x)=\sum_{i=1}^{N}\frac{1}{N}\nabla f(x+z_{i})$ where $z_{i}\sim\mathcal{N}(0,\sigma I)$.

Second, we manipulate the complexity of the task to test whether gradients help more or less on more complex tasks. We experiment on both MNIST and CIFAR10. Finally, we manipulate the complexity of the model class to test whether gradients help more when the model is simpler. We train three models on each of the two tasks that are chosen to display a range of complexity.

Dependent measure. We measure the accuracy of our reconstructed classifier $\hat{f}$ on a test set of 10,000 images from the task (MNIST or CIFAR10).

Experimental procedure. We split our datasets into three parts:

A training set of images and ground-truth labels for the true classifier $f$. The training set for MNIST has 50,000 examples and for CIFAR10 has 40,000 examples.

A training set of 10,000 images for the reconstructed classifier $\hat{f}$. Note that $\hat{f}$ does not have access to ground-truth labels, so it must query $f$ for labels.

A test set of 10,000 images and ground-truth labels for $f$ and $\hat{f}$.

We first train models to serve as the true classifier $f$. We train three types of models on MNIST: a 1-layer network (multinomial logistic regression), a 2-layer neural network with ReLu activations, and a network with two convolutional layers (each followed by a max-pool layer) followed by two dense layers. We also train three types of models on CIFAR10: the same convolutional network used for MNIST (with the input dimension changed appropriately), a VGG11 network , and a ResNet-18 network .

Next, we train a new classifier $\hat{f}$ from the same model class as the true classifier $f$. The inputs $x$ given to $\hat{f}$ are randomly sampled from the training set for $\hat{f}$. After training, we compute the accuracy of our reconstructed classifier $\hat{f}$ on the test set.

Follow-up experiments: unknown model class and data distribution An adversary trying to reconstruct the classifier $f$ may not know the model class of $f$ or the data distribution. So, in follow-up experiments we (1) reconstruct the classifier $f$ with a classifier $\hat{f}$ from a different model class and (2) reconstruct the classifier $f$ using Gaussian generated queries. In these follow-up experiments we analyze the same factors, but with a subset of conditions.

Experimental results and discussion

Figure 2 shows the results of our main experiments, described in Section 4.

Type of query. Across all experiments, training with gradient queries leads to orders of magnitude fewer queries required to learn the model. For example, for the MNIST convolutional model we get to 95% accuracy in 10 gradient queries, compared to 1000 membership queries. We find practically no difference between gradient queries and SmoothGrad queries, despite picking the hyperparameters for SmoothGrad that produced the best saliency maps (See Appendix D).

Complexity of model class. We find that the gap in performance between gradient queries and membership queries is larger for models of lower complexity.

On MNIST with the 2-layer or convolutional network we find a 100x decrease in the number of queries needed to reconstruct the model. On CIFAR10 we find that the convolutional network (which is the same as the convolutional network used for MNIST) also has at least a 100x decrease in the number of queries needed. On the other hand, VGG11 and Resnet-18 show only a 10x decrease in the number of queries needed to reach 75% accuracy.

Complexity of task. We find that the relative reduction in queries needed seems to depend on the complexity of the model class, rather than the complexity of the task. But, not surprisingly, the absolute number of queries needed increases with the complexity of the task.

On both MNIST and CIFAR10 gradient queries lead to a 100x decrease for reconstructing the convolutional network, suggesting that for the relative decrease in query complexity depends more on the complexity of the model class than the complexity of the task. However, as might be expected, for both gradient and membership queries the absolute number of queries needed increases as the complexity of the task increases. On MNIST the convolutional model is reconstructed in 10 gradient queries, compared to 1000 membership queries. On CIFAR10 the convolutional model is reconstructed in 100 gradient queries, compared to 10,000 membership queries.

2 Unknown model class

In the scenario where we do not know the true model class beforehand, we experiment with:

MNIST: Reconstructing the 1-layer model with the 2-layer network (and vice versa).

MNIST: Reconstructing the 2-layer model with the convolutional network (and vice versa).

CIFAR10: Reconstructing the VGG11 model with the ResNet-18 network (and vice versa).

We refer the reader to Section 4 for details on the models. Figure 3 displays our results.

We find that gradient queries seem to help more when the the model class of $\hat{f}$ is more complex than the true classifier $f$. For example, we see a 100x decrease in the number of queries needed to reconstruct MNIST 1-layer with a 2-layer network. But, we only get an initial 10x decrease in the number of queries needed to reconstruct MNIST 2-layer with a 1-layer network. Similarly reconstructing the 2-layer network with the convolutional network works much better than reconstructing the convolutional network with the 2-layer network.

We have been fairly loose when referring to the relative complexities of different models, and it is unclear to us how to compare VGG11 and ResNet-18 in terms of complexity. Interestingly however, we find that although gradient queries still lead to a 10x decrease when reconstructing ResNet-18 with VGG11, they help very little when reconstructing a VGG11 model with a ResNet-18 network.

3 Unknown data distribution

We now analyze the setting where we do not know the data distribution. Instead we query using randomly generated Gaussian queries, i.e $x\sim\mathcal{N}(0,I_{d})$. Figure 4 displays our results.

On MNIST we find that Gaussian queries lead to a greater gap in performance between gradient and membership queries, compared to when using images from the data distribution.On the 1-layer network we see the same relative decrease because it is identifiable with a single gradient + membership query or 784 membership queries, independent of the distribution the queries are generated from. On the MNIST 2-layer network, we see at least a 1000x decrease, compared to the 100x decrease we saw in Section 4 when using queries from the data distribution. On the MNIST convolutional network, we see that in 10 gradient queries we get to 84% accuracy. On the other hand, it takes 10,000 membership queries to learn at all, and even then we get to only 71%. Thus, we seem to get at least a 1000x decrease, compared to the 100x reduction we saw when using queries from the data distribution.

On CIFAR10 it is harder to interpret the results because the performance degrades so much for both gradient and membership queries. However, at least in the convolutional network, the gap between gradient and membership queries also seems to increase. The reconstructed model gets to 50% accuracy in 10 gradient queries, but only to 11% accuracy in 10,000 membership queries.

Related work

Tramèr et al. show how models can be reconstructed in practice through prediction APIs . Our work addresses the complementary threat of model leakage through a hypothetical explanation API. While differential privacy can help guard against attacks from prediction APIs , it is not clear if this is a viable approach for preventing reconstruction from explanations.

Learning a model via a prediction API instantiates the framework of learning with membership queries, in which the learner gets to actively query an oracle for labels to inputs of its choosing . In our work, we propose a complementary learning framework: learning from input gradient queries. Similar to membership queries and prediction APIs, we believe that learning from gradients is likely to be the theoretical framework underpinning reconstruction from explanation APIs.

We give a near-optimal algorithm for learning a two-layer network with ReLU activations through gradient queries. The geometric intuition for our algorithm is similar to the work of Baum for learning two-layer linear threshold networks with membership queries .

References

Appendix A Omitted proofs for Algorithm 2

First, we prove the following two lemmas that will be useful in proving the anti-concentration and concentration bounds in Lemma 2 and Lemma 3.

(Anti-concentration of difference of $\chi^{2}_{2}$ variables) Let $Q,R\sim\chi^{2}_{2}$. Then, $P(|Q-R|\leq\epsilon)\leq\epsilon$ for $\epsilon>0$.

Recall that the cumulative distribution function of a $\chi^{2}_{d}$ random variable $Q$ is

where $\gamma(s,z)=\int_{0}^{z}t^{s-1}e^{-t}dt$ is the lower incomplete gamma function and $\Gamma(z)=\int_{0}^{\infty}t^{z-1}e^{-t}dt$ is the gamma function. When $d=2$, $P(Q\leq x)$ simplifies to $\int_{0}^{x/2}e^{-z}dz$. Thus,

(Distribution of product of independent Gaussians) Let $X,Y\sim\mathcal{N}(0,1)$. Then $XY$ can be written as

where $Q,R\sim\chi^{2}_{1}$ are independent.

Since $\text{Cov}(X+Y,X-Y)=0$, we know $X+Y$ and $X-Y$ are independent random variables from a $\mathcal{N}(0,2)$ distribution. Thus, we can express $(X+Y)^{2}$ and $(X-Y)^{2}$ as $(X+Y)^{2}=2Q$ and $(X-Y)^{2}=2R$ where $Q,R$ are independent $\chi^{2}_{1}$ random variables. Thus, $XY=\frac{1}{2}(Q-R)$. ∎

Solving for the scalars $t_{1}$ and $t_{2}$ yields

Using this expression for the vector $b$ we can rewrite $|t_{1}-t_{2}|$ as

where $X_{1}=\langle a,u\rangle,X_{2}=\langle a,v\rangle,Y_{1}=\langle a^{\perp},u\rangle,Y_{2}=\langle a^{\perp},v\rangle$ are independent $\mathcal{N}(0,1)$ random variables. To bound $P(|t_{1}-t_{2}|\leq\epsilon)$ we can bound the numerator and denominator of (A) separately. For all $k>0$, the following inequality holds.

Applying a union bound to the complementary event yields,

Applying Lemma 6 to the independent products $X_{1}Y_{2}$ and $X_{2}Y_{1}$ simplifies the numerator to

where $Q,R\sim\chi^{2}_{2}$ are independent Chi-squared random variables. Then by Lemma 5,

To upper bound the tail probability of the denominator (the second term in Equation 5) note that

Minimizing the right-hand side with respect to $k$ yields

$t=-\frac{\langle a,u\rangle}{\langle a,v\rangle}$ follows a standard Cauchy distribution. The cumulative distribution function of a standard Cauchy random variable $X$ is $P(X\leq a)=\frac{1}{\pi}\arctan(a)+\frac{1}{2}$. Thus,

Appendix B Picking query points in Algorithm 3

For completeness, we show that we can easily find a matrix $X$ which satisfy the requirements of Lemma 4 through the following steps:

Construct a set of $d$ linearly independent vectors $\mathcal{Y}=y_{1},\dots,y_{d}\in\mathcal{C}$ as follows.

Appendix C Reconstruction from membership queries

We now consider how to reconstruct the two-layer ReLU neural network described in Section 2 with membership queries alone, rather than membership and gradient queries. We show that we can convert our algorithm into one that learns with membership queries by estimating the gradients of $f$ with membership queries.

We define the membership query version of Algorithm 1, referred to as Algorithm 1-MQ, by replacing any use of the gradient $\nabla f(x)$ with an estimate of the gradient, $\widehat{\nabla}f(x)$, computed with $d$ membership queries. We estimate the gradient by estimating each component separately through a finite difference approximation:

Our main result shows that we can recover the function $f$ in $O(dh\log\frac{h}{\delta})$ membership queries:

C.2 Proofs

The proof of Theorem 4 relies on showing that we can pick an $s$ small enough so that with high probability all estimates of the gradient are equal to the exact gradient. We show this by proving that if all points used in estimating a gradient lie in the same cell defined by the separating hyperplanes of $f$, then the estimate of the gradient $\widehat{\nabla}f(x)$ is equal to the gradient $\nabla f(x)$. If $s$ is small enough, then all points evaluated for a gradient estimate will lie in the same cell, and thus the exact gradient will be recovered. By choosing $s$ small enough, we can ensure that all gradients estimated by Algorithm 1-MQ are equal to the exact gradient with high probability.

First, we show that if all points sampled in estimating the gradient lie in the same cell, then the estimate of the gradient $\widehat{\nabla}f(x)$ is equal to the gradient $\nabla f(x)$:

Suppose for all $j\in[d]$, $x+\Delta^{j}$ lies in the same cell as $x$, i.e,

Then, $\widehat{\nabla}f(x)=\nabla f(x)$.

Recall that the function $f$ can be expressed as

Thus, the $j$-th component of the gradient of $f$ is

where $a_{j}$ is the $j$-th column of $A$. Our estimate of the gradient is

Therefore, $\widehat{\nabla}f(x)=\nabla f(x)$. ∎

The next lemma shows that if $s$ is small enough, then all points evaluated used to estimate a gradient lie in the same cell, and thus the exact gradient is recovered.

Next, given a particular value of $s$, we bound the probability that all gradients we estimate with our algorithm are exactly equal to the true gradient.

First we will establish a bound for one row $a$ of the weight matrix $A$.

A union bound on all rows of the weight matrix $A$ then shows that

Finally, we show that by picking $s$ small enough so that all gradients estimate are exact with high probability, the sample complexity of Algorithm 1-MQ becomes $O(dh\log\frac{h}{\delta})$ membership queries.

Algorithm 1 only uses gradients of $f$ in Algorithm 2 and Algorithm 1 succeeds if and only if Algorithm 2 succeeds. Thus, we can bound the success of Algorithm 1-MQ by bounding the probability that all gradients used in Algorithm 2 are estimated exactly.

In $O(h\log\frac{2h}{\delta})=O(h\log\frac{h}{\delta})$ gradient queries we can guarantee that Algorithm 2 succeeds with probability $1-\frac{\delta}{2}$. The probability Algorithm 1-MQ succeeds then becomes the following.

Since, it takes $d$ membership queries to compute each gradient that Algorithm 2 requires, the sample complexity becomes $O(dh\log\frac{h}{\delta})$ membership queries.

Appendix D SmoothGrad

Instead of returning the raw gradient $\nabla f(x)$, SmoothGrad returns an average of gradients around the input $x$:

where $z_{i}\sim\mathcal{N}(0,\sigma^{2}I)$ and $N>0$. SmoothGrad has two hyperparameters: (1) $\sigma$ the standard deviation of the Gaussian noise and (2) $N$ the number of samples to pick.

As shown in Figure 5, we found that the best value of $\sigma$ for MNIST was 1000 times $\sigma_{D}$, the standard deviation of the images in the dataset. On CIFAR10 using either the VGG-11 or ResNet-18 network, no value of $\sigma$ seems to produce a sharp map (Figures 6 and 7). So for our CIFAR10 experiments, we set $\sigma$ equal to the standard deviation of the dataset $\sigma_{D}$. In the original SmoothGrad paper, Smilkov et al. find that the best value of $\sigma$ for MNIST is about 70% the spread of the dataset, while on ImageNet it is only 10-20%. So the difference between the value of $\sigma$ we use on MNIST and the value of $\sigma$ we use on CIFAR10 seems to qualitatively match the difference in the value of $\sigma$ Smilkov et al. use on MNIST and ImageNet.

We expect that SmoothGrad may eventually degrade the performance of the reconstructed model as $\sigma$ increases. But at least for the values of $\sigma$ we test, which are already quite large relative to the standard deviation of the dataset, and seem to match values that may be used in practice, we see no degradation in performance when using gradients preprocessed by SmoothGrad.

Regarding the number of samples, $N$, Smilkov et al. state that the estimated gradient becomes smoother as $N$ increases, but that they find diminishing returns for $N>50$. For computational reasons we set $N=10$ in our experiments, however, this should only make it harder to learn, since the outputs of SmoothGrad become noisier.