[Paper] Efficient Public Verification of Private ML via Regularization

Source: arXiv - 2512.04008v1

Overview

This paper tackles a practical gap in differential‑privacy (DP) machine learning: while DP training protects individual data points, there’s currently no cheap way for data owners or the public to verify that a released model truly satisfies its claimed DP guarantees. The authors present the first DP‑stochastic convex optimization (DP‑SCO) algorithm whose privacy guarantees can be checked with far less computation than it takes to train the model, while still achieving near‑optimal privacy‑utility trade‑offs.

Key Contributions

• Verification‑efficient DP algorithm: Introduces a DP‑SCO method whose DP guarantee can be audited at a fraction of the training cost.
• Tight privacy‑utility trade‑offs: Matches the known optimal bounds for DP‑SCO by privately minimizing a sequence of regularized objectives.
• Standard DP composition: Relies only on the classic DP composition theorem, avoiding complex accounting tricks that hinder verification.
• Scalable verification: Demonstrates that verification time grows sub‑linearly compared to training time, making public audits feasible on large datasets.
• Theoretical guarantees: Provides rigorous proofs that the verification procedure yields the same privacy parameters as the training algorithm.

Methodology

1. Regularized Objective Sequence

   • The authors reformulate the original convex loss into a series of regularized losses (adding a carefully chosen penalty term).
   • Each regularized problem is solved with a standard DP optimizer (e.g., DP‑SGD) using a modest privacy budget per step.

2. Privacy Accounting via Standard Composition

   • Instead of sophisticated privacy accountants, they apply the basic DP composition bound across the sequence of regularized problems.
   • This yields a clean, additive privacy loss that is easy to compute and verify.

3. Verification Procedure

   • After training, the verifier only needs to re‑run the regularized optimizations with the published randomness seeds (or check the published noise statistics).
   • Because each sub‑problem is smaller and the composition is additive, the total verification cost is dramatically lower than re‑training the full model from scratch.

4. Theoretical Analysis

   • The paper proves that the regularization does not degrade utility beyond the optimal DP‑SCO lower bound.
   • It also shows that the verification algorithm recovers the exact privacy parameters used during training.

Results & Findings

The experiments on standard convex tasks (logistic regression, SVM) confirm that utility remains essentially unchanged while verification time drops by an order of magnitude on datasets with millions of samples.

Practical Implications

• Public Audits: Regulators, data providers, or users can now independently verify DP claims without needing the original training infrastructure.
• Compliance Pipelines: Companies can embed the cheap verification step into CI/CD pipelines, ensuring every released model passes a DP audit before deployment.
• Cost Savings: For large‑scale training (e.g., recommendation systems), verification can be run on modest cloud instances, cutting operational expenses.
• Trust in Data‑Sharing Platforms: Platforms that host third‑party models (e.g., Model Zoos) can display a verifiable DP certificate, boosting user confidence.
• Simplified Tooling: Since the method uses standard DP composition, existing DP libraries (TensorFlow Privacy, Opacus) can be extended with a lightweight verification module.

Limitations & Future Work

• Convex‑only scope: The technique is proved for stochastic convex optimization; extending it to deep, non‑convex models remains an open challenge.
• Regularization overhead: While verification is cheap, the training loop now solves multiple regularized sub‑problems, which may add modest overhead in wall‑clock time.
• Assumption of honest randomness disclosure: Verification relies on access to the randomness seeds or noise parameters; malicious providers could withhold this information.
• Future directions suggested by the authors include: adapting the regularization‑based verification to DP‑SGD for neural networks, exploring tighter composition methods that preserve verification efficiency, and building open‑source tooling that integrates seamlessly with existing ML pipelines.

Authors

• Zoë Ruha Bell
• Anvith Thudi
• Olive Franzese-McLaughlin
• Nicolas Papernot
• Shafi Goldwasser

Paper Information

• arXiv ID: 2512.04008v1
• Categories: cs.LG, cs.CR
• Published: December 3, 2025
• PDF: Download PDF