Source-linked AI summary
Model Reconstruction from Model Explanations
Smitha Milli, Ludwig Schmidt, Anca D. Dragan, Moritz Hardt
TL;DR
The paper examines the tension between explaining consequential machine-learning models and keeping proprietary models secret. It introduces gradient-query reconstruction methods and shows theoretically and experimentally that explanations can efficiently reveal the underlying model.
Problem
Growing demand for model explanations conflicts with companies’ interests in protecting competitive value, predictive power, and training-data confidentiality.
Method
The paper develops a learning model and algorithm for reconstructing two-layer ReLU networks from input-gradient queries, alongside practical heuristics that train a classifier to match model outputs and gradients.
Results
The algorithm recovers a functionally equivalent model using O(h log h) input-gradient queries and function evaluations with high probability, while gradient-based reconstruction heuristics are practically effective.
Takeaways & Limitations
Gradient explanations can substantially expose proprietary models, and gradient queries are a more powerful learning primitive than labels or membership queries in the studied setting.
Takeaways & Limitations
The paper leaves open whether its theoretical result extends to deeper ReLU networks and how to formally study explanation quality without an agreed-upon measure.
Abstract
from arXiv · showhide
We show through theory and experiment that gradient-based explanations of a model quickly reveal the model itself. Our results speak to a tension between the desire to keep a proprietary model secret and the ability to offer model explanations. On the theoretical side, we give an algorithm that provably learns a two-layer ReLU network in a setting where the algorithm may query the gradient of the model with respect to chosen inputs. The number of queries is independent of the dimension and nearly optimal in its dependence on the model size. Of interest not only from a learning-theoretic perspective, this result highlights the power of gradients rather than labels as a learning primitive. Complementing our theory, we give effective heuristics for reconstructing models from gradient explanations that are orders of magnitude more query-efficient than reconstruction attacks relying on prediction interfaces.
1 Introduction
The paper identifies a tension between explaining consequential models and preserving their secrecy: gradient-based explanations can quickly reveal the underlying model. It develops theoretical and practical reconstruction methods showing that gradients enable highly query-efficient model recovery.
- Motivation: Gradient explanations can quickly reveal a proprietary model, creating a tension between decision transparency and model secrecy.Companies may also fear competitive loss, easier gaming, and leakage of training-data information.
- Learning from input gradients: The paper studies reconstruction from input gradients, treating gradients as a learning primitive richer than single prediction labels.The gradient of a linear model directly equals its parameter vector, so one gradient query suffices there.
- Learning from input gradients: O(h log h) input gradient queries and function evaluations recover a functionally equivalent two-layer ReLU model with high probability.The guarantee assumes the rows of the hidden-layer matrix A are linearly independent.
- Learning from input gradients: Gradient queries have no dependence on input dimension d and reduce query requirements by approximately a factor of d relative to membership queries.The comparison is O(h log h) gradient queries versus Ω(dh) membership queries for specifying the model.
- Practical reconstruction methods: A practical heuristic fits a model to queried gradients and reduces the queries needed on MNIST and CIFAR10 by orders of magnitude.This result holds even when the target model class or data distribution is unknown.
- Conclusion: The conclusion argues that explanation quality must be weighed against model-leakage risk, while leaving extensions and formal trade-off measures open.The authors describe the work as a first step and identify depth-3 learning and explanation robustness as open questions.
2 Problem statement: reconstructing a two-layer ReLU network
The paper formulates reconstruction as finding a classifier identical to an unknown two-layer ReLU network using membership and gradient queries. Under structural assumptions on the hidden-layer weights, its theorem gives a dimension-independent gradient-query guarantee and a membership-query conversion.
- Problem formulation: The reconstruction task is to find a classifier ˆf identical to an unknown classifier f using oracle access to evaluations and input gradients.The oracle returns both f(x) and ∇_xf(x) for a chosen input x.
- Model class: The target function is a one-hidden-layer neural network with ReLU activations and parameters A ∈ R^(h×d) and w ∈ R^h.ReLU applies max{u, 0} coordinate-wise.
- Assumptions: The analysis assumes unit hidden-layer rows, non-collinear rows separated by a positive margin, and linearly independent rows.The first two conditions can be obtained without loss of generality through simple reparameterizations or dimension reduction.
- Main guarantee: The gradient-query sample complexity has no dependence on the input dimension d.The paper contrasts this with a membership-query implementation requiring O(dh log(h/δ)) queries to approximate gradients.
- Main guarantee: With probability 1 − δ, the algorithm recovers ˆf = f in O(h log(h/δ)) queries and reports failure if unsuccessful.The stated theorem assumes that the unknown function satisfies the paper’s structural assumptions.
3 Algorithm
The algorithm reconstructs a two-layer ReLU network by first recovering unsigned weighted normal vectors from gradient changes, then recovering their signs. With probability 1−δ, it identifies the function using O(h log h) queries under the stated assumptions.
- Algorithm overview: The input space is partitioned into cells by separating hyperplanes, within which the network has a constant gradient.Each cell corresponds to a possible activation pattern of the hidden units.
- Step two: recovering the signs of the normal vectors: Algorithm 1b recovers a sign-encoding vector s from Z, and together Z and s identify the function f.Theorem 3 establishes correctness of this second step using O(h) queries, yielding the overall guarantee.
- Step one: recovering the separating hyperplanes: Algorithm 1a uses binary search to locate nearby points with differing gradients and adds their gradient difference to matrix Z.When only one hyperplane lies between the points, the difference equals wiAi up to sign.
- Step one: recovering the separating hyperplanes: Repeating the search h times recovers every weighted normal vector wiAi up to sign, arranged as rows of Z up to permutation.The procedure succeeds when gradient change points are sufficiently separated and lie within the searched segment.
- Theoretical guarantee: Theorem 2 guarantees that Algorithm 1a succeeds with probability 1−δ in O(h log h) queries, or reports failure.Its output contains each wiAi or −wiAi under a permutation of the hidden units.
4 Experimental design
The experiments compare membership-only reconstruction with reconstruction using raw or SmoothGrad-processed gradients across tasks, model classes, and query distributions. Models are evaluated by test accuracy, including settings with matched or different model classes and Gaussian queries.
- Training objective: The reconstruction objective matches either model outputs or gradients, with a joint loss combining gradient loss ℓG and membership loss λℓM.The experiments compare the joint objective ℓJ(x) = ℓG(x) + λℓM(x) against membership loss alone.
- Query type: The study compares membership-only queries with membership-plus-gradient queries, including gradients processed by SmoothGrad.SmoothGrad averages gradients around the input rather than returning the raw gradient.
- Task and model complexity: The design varies task complexity using MNIST and CIFAR10 and model complexity using three model types per task.The models range from logistic regression and ReLU networks to convolutional, VGG11, and ResNet-18 architectures.
- Evaluation procedure: The true and reconstructed classifiers are evaluated on 10,000-image test sets using ground-truth labels.The reconstructed classifier is trained from sampled inputs and queried outputs without access to ground-truth labels during reconstruction.
- Follow-up experiments: Follow-up experiments test reconstruction with a different model class and with Gaussian-generated queries.These experiments use a subset of the main conditions.
5 Experimental results and discussion
Gradient queries substantially reduce reconstruction queries across known and unknown model classes and data distributions, with larger relative gains for simpler target classes or more complex reconstruction classes. Absolute query requirements still grow with task complexity, and Gaussian queries can widen the gradient-versus-membership gap.
- Type of query: Orders of magnitude fewer queries are required with gradient queries than with membership queries across the main experiments.For the MNIST convolutional model, 10 gradient queries reached 95% accuracy versus 1000 membership queries.
- Complexity of model class: 1000x fewer queries reconstruct the MNIST 1-layer network with gradients, requiring one query instead of 784 membership queries.The 1-layer model is identifiable from one gradient and membership query.
- Complexity of task: Gradient queries provide a larger relative reduction for convolutional reconstruction across MNIST and CIFAR10, while absolute query counts increase with task complexity.The convolutional model uses 10 versus 1000 queries on MNIST and 100 versus 10,000 on CIFAR10.
- Unknown model class: When the model class is unknown, gradients help more if the reconstructed class is more complex than the true classifier.Reconstructing MNIST 1-layer with a 2-layer network yields a 100x reduction, versus an initial 10x reduction in the reverse direction.
- Unknown data distribution: Gaussian queries widen the gradient-versus-membership gap on MNIST, reaching at least a 1000x reduction for the 2-layer network.The convolutional network reaches 84% accuracy in 10 gradient queries, versus 71% after 10,000 membership queries.
6 Related work
This section places reconstruction from explanations alongside prediction-API attacks and introduces learning from input gradient queries as a complementary framework.
- 6 Related work: The paper studies model leakage through a hypothetical explanation API as a threat complementary to prediction-API reconstruction.The related-work discussion contrasts explanation leakage with prior prediction-interface attacks.
- 6 Related work: Prediction APIs support model reconstruction through membership-query-style access to labels at chosen inputs.This frames prediction-interface attacks as active learning with label queries.
- 6 Related work: Learning from input gradient queries gives an algorithm direct access to gradients at selected inputs rather than only labels.The framework is proposed as an analogue of membership queries for explanation-based reconstruction.
- 6 Related work: The paper gives a near-optimal algorithm for learning a two-layer ReLU network through gradient queries.Its geometric intuition is related to earlier work on learning two-layer linear threshold networks with membership queries.
A Omitted proofs for Algorithm 1a
The omitted proofs establish probabilistic bounds for the random-vector constructions used in Algorithm 1, analyzing separation variables through Gaussian, Cauchy, product-Gaussian, and chi-squared distributions.
- A Omitted proofs for Algorithm 1a: The analysis uses distributions of products of independent Gaussians and chi-squared variables to simplify probability bounds.The product-Gaussian lemma rewrites independent Gaussian combinations using independent chi-squared variables.
- A Omitted proofs for Algorithm 1a: Lemma 2 analyzes the separation between two scalar zero-crossing parameters generated from random Gaussian vectors and non-collinear unit vectors.The assumption bounds the absolute inner product of the two unit vectors away from one.
- A Omitted proofs for Algorithm 1a: The proof decomposes Gaussian vectors into components parallel and orthogonal to a reference vector to bound numerator and denominator events separately.This decomposition introduces independent standard-normal variables and supports the concentration analysis.
- A Omitted proofs for Algorithm 1a: Union bounds and optimization over an auxiliary parameter complete the stated probability estimates.The proof applies a union bound to complementary events and minimizes the resulting bound with respect to k.
- A Omitted proofs for Algorithm 1a: Lemma 3 identifies the scalar that makes a random affine combination orthogonal to a fixed unit vector and characterizes its ratio distribution.The relevant inner product ratio follows a standard Cauchy distribution.
B Picking query points in Algorithm 1b
The query-point construction finds a cell of a random hyperplane arrangement, inscribes its largest feasible Euclidean ball, and selects independent points to obtain a full-rank query matrix.
- B Picking query points in Algorithm 1b: A random vector v defines a sign cell C through the indicator g(v) = 1{Zv ≥0}.The construction uses the cell containing the sampled vector as its feasible region.
- B Picking query points in Algorithm 1b: The largest ℓ2 ball inside C ∩ [0, 1]^d is found using its Chebyshev center and radius.Both quantities can be obtained through a linear program.
- B Picking query points in Algorithm 1b: The method constructs d linearly independent vectors within the selected cell.These vectors form the columns of a matrix Y.
- B Picking query points in Algorithm 1b: Selecting h vectors from Y yields a matrix X for which Rank(ZX) = h.The rank condition follows because Y has rank d and the selected columns can preserve rank h.
C Reconstruction from membership queries
The paper converts its gradient-query reconstruction method into a membership-query method by estimating gradients from model evaluations.
- C Reconstruction from membership queries: The reconstruction algorithm can be adapted to use membership queries alone instead of both membership and gradient queries.The conversion estimates the required gradients using membership-query evaluations.
- C Reconstruction from membership queries: Gradient estimation from membership queries supplies the missing gradient information needed by the original reconstruction procedure.This establishes a direct reduction from the gradient-query setting to the membership-query setting.
C.1 Membership query version of Algorithm 1
Algorithm 1-MQ replaces exact gradient queries with finite-difference estimates obtained from membership queries, yielding a dimension-dependent reconstruction guarantee.
- Algorithm 1-MQ replaces each use of ∇f(x) with a finite-difference gradient estimate computed using d membership queries.Each gradient component is estimated separately through finite differences.
- O(dh log h/δ) membership queries suffice for Algorithm 1-MQ to recover f with probability 1 − δ under the stated condition on s.The condition constrains s using δ, ϵ, l, and ϵ, where l and ϵ parameterize the binary search.
C.2 Proofs
The proofs establish that finite-difference estimates equal exact gradients when queried points remain within one activation cell, and then bound the probability that this holds throughout reconstruction.
- If all points used to estimate a gradient lie in the same cell as x, then the estimated gradient b∇f(x) equals ∇f(x).This follows by preserving every activation indicator under the finite-difference perturbations.
- When |Ax| is at least s1, the estimated gradient equals the exact gradient because unit-norm rows prevent activation-pattern changes under perturbations.The proof compares the perturbation magnitude |s a_j| with the margin |Ax|.
- The proof bounds the probability that all gradients estimated during the algorithm are exactly equal to the true gradients.A set X of candidate query points and a union bound over rows of A are used in this argument.
- O(dh log h/δ) membership queries result after computing each gradient required by Algorithm 1a with d membership queries.Algorithm 1-MQ inherits Algorithm 1a’s success when all estimated gradients are exact.
D SmoothGrad
SmoothGrad averages gradients around an input using Gaussian noise, and the experiments examine how its noise scale and sample count affect reconstruction and saliency maps.
- SmoothGrad returns an average of gradients around x, controlled by Gaussian noise scale σ and sample count N.The perturbations satisfy z_i ∼ N(0, σ^2I).
- For MNIST, the experiments use σ equal to 1000 times the dataset standard deviation, while CIFAR10 uses σ equal to the dataset standard deviation.The CIFAR10 setting applies to both VGG-11 and ResNet-18 experiments.
- The authors expect SmoothGrad performance may degrade as σ increases, but observe no degradation for the tested values despite their large scale.The tested values are described as comparable to values that may be used in practice.
- For CIFAR10 RGB images, the visualizations show the absolute value of SmoothGrad’s output.This convention is used for both the VGG-11 and ResNet-18 figures.