Technical Summary: Efficient Public Verification of Private ML via Regularization

Problem Statement

Differential Privacy (DP) is the standard framework for protecting sensitive information in machine learning training datasets, guaranteeing that model users cannot infer specific data points. However, a critical gap exists: data providers and the public lack efficient methods to verify that a released model was indeed trained under DP guarantees.

Current verification methods face two primary limitations:

1. Black-box Auditing: Approaches that query a model trainer with different datasets are statistically insufficient. The paper demonstrates that under the assumption of digital signatures, a malicious trainer can plant a "computationally undetectable" backdoor. This backdoor remains dormant during standard audits but allows the trainer to leak the dataset to specific entities, rendering the algorithm non-private despite passing any black-box check.
2. Interactive Verification Costs: Existing interactive proofs for DP (e.g., verifying DP-SGD) require the verifier to re-compute nearly all training steps. For instance, verifying DP on the MNIST dataset previously required approximately 100 hours of computation, scaling with the training cost. This makes public verification impractical for large datasets.

The paper addresses the challenge of designing a DP algorithm where the verification cost is strictly lower than the training cost, specifically for Stochastic Convex Optimization (DP-SCO).

Methodology

1. Theoretical Foundation: Undetectable Backdoors

The authors first formalize the insufficiency of black-box auditing. They construct a backdoored training algorithm $T'$ that is computationally indistinguishable from a legitimate DP algorithm $T$ to any polynomial-time auditor.

• Mechanism: The algorithm embeds a digital signature verification step into the training data. If a specific input contains a valid signature (which only the malicious trainer possesses), the algorithm outputs the raw training dataset instead of the model.
• Implication: This proves that without interactive protocols, no public auditor can guarantee a model's privacy, necessitating a shift to interactive certification.

2. Core Algorithm: Modified Phased ERM

To achieve efficient verification, the authors propose a modification to the Phased Empirical Risk Minimization (ERM) algorithm (Feldman et al., 2020).

• Standard Phased ERM: Solves a series of regularized objectives on disjoint subsets of data, increasing regularization strength over phases. It relies on parallel composition of privacy budgets to achieve tight guarantees. However, verifying parallel composition is expensive because the verifier must confirm that each phase used a specific, disjoint subset of the data.
• The Modification: The authors alter the stopping criteria for the approximate minimizers in each phase.
  • Instead of requiring the excess loss to be small, they require the gradient norm to be small ($\|\nabla F_i(\tilde{w}_i)\|_2 \leq \frac{2}{n_i} L$).
  • They adjust the privacy budget $\delta$ for each phase to $\delta / \lceil \log_2(n) \rceil$.
• Resulting Benefit: This modification allows the algorithm to derive near-optimal privacy-utility trade-offs using only standard sequential composition rather than parallel composition. Standard composition is significantly easier to verify because it does not require proving the disjointness of data subsets, only that the noise was added correctly and the gradient norms were satisfied.

3. Verification Protocol

The proposed protocol (Algorithm 2) involves an interactive proof between a Prover (trainer) and a Verifier (public):

1. Commitment: The Prover commits to the dataset and model weights at each phase.
2. Gradient Verification: Using Zero-Knowledge Proofs (ZKPs), the Verifier checks that the gradient norm of the approximate minimizer is below the required threshold.
3. Noise Verification: The Verifier checks that Gaussian noise was added to the weights using a discrete Gaussian commitment scheme.
4. Complexity: The verification requires checking $n$ gradients (where $n$ is the dataset size) and $d \cdot \lceil \log_2(n) \rceil$ Gaussian random variable commitments (where $d$ is the dimension).

4. Extension to Machine Unlearning

The authors extend these techniques to Approximate Machine Unlearning for strongly convex losses. By leveraging the stability of strongly convex functions, they show that unlearning can be certified by checking gradients on the retain dataset ($D'$) rather than the full dataset, requiring only $|D'|$ gradient checks and $d$ noise commitments.

Key Results

Theoretical Guarantees

• Privacy-Utility Trade-off: The modified algorithm achieves an excess population risk of $\tilde{O}(L D (\frac{1}{\sqrt{n}} + \frac{\sqrt{d \ln(1/\delta)}}{\epsilon n}))$, which is near-optimal (matching known lower bounds up to $\log \log(n)$ factors).
• Verification Efficiency: The certification requires verifying only $n$ gradients and $d \cdot \lceil \log(n) \rceil$ Gaussian random variables.
  • Compared to the fastest known training algorithms for DP-SCO, which require $\tilde{\Omega}(\min(n^{1.5}, n^2/\sqrt{d}))$ gradients, the verification cost is significantly lower (at least an $O(\sqrt{n})$ improvement in non-smooth settings).
  • In smooth settings, the reduction in Gaussian random variable checks (from $\Omega(dn)$ to $d \log n$) provides a substantial runtime advantage.

Empirical Evaluation

The authors implemented the protocol using the EMP-toolkit for binary logistic regression on the MNIST dataset ($n=60,000, d=784$).

• Runtime Comparison:
  • Previous Approach (DP-SGD verification): ~100 hours.
  • Proposed Approach: ~3 hours on a laptop CPU.
• Bottleneck Analysis:
  • Gradient Verification: Dominates the runtime. The number of gradients to verify was reduced by over 4-fold compared to previous methods.
  • Noise Verification: The time to verify Gaussian random variables dropped drastically (from being the dominant cost to being negligible, taking less time than a single gradient verification).
  • Communication: Network overhead (LAN/WAN) was found to be insignificant compared to computation.
  • Training: Training time was negligible (seconds) because it does not require homomorphic encryption, unlike the verification process.

Significance and Claims

The paper claims to present the first known DP-SCO algorithm where the DP verification scales better than the training cost.

• Paradigm Shift: It moves the field from "black-box auditing" (which is provably insufficient against computationally bounded adversaries) to "efficient public verification" via interactive proofs.
• Practicality: By reducing verification time from ~100 hours to ~3 hours on standard hardware for MNIST-scale data, the paper argues that public certification of private ML is becoming feasible.
• Limitations: The authors modestly note that the current approach is limited to convex settings and does not directly apply to deep neural networks (though it could apply to fine-tuning the final layer). They also acknowledge that for very large datasets, the linear scaling with $n$ may still be impractical, and future work is needed to handle stochastic gradients more efficiently (e.g., via randomized smoothing).

In summary, the paper establishes that by leveraging regularization to stabilize optimization and modifying the verification criteria to focus on gradient norms rather than loss excess, it is possible to construct DP algorithms that are both near-optimal in utility and efficiently verifiable by the public.