NDSS 2025

Provably Unlearnable Data Examples

Certified learnability for understanding and controlling how much a dataset can support model training.

Derui Wang^1,2, Minhui Xue^1,2, Bo Li³, Seyit Camtepe^1,2, Liming Zhu¹

¹CSIRO's Data61, Australia ²Cyber Security Cooperative Research Centre, Australia ³University of Chicago, USA

Distinguished Paper Award

Certified learnability of unlearnable datasets — Certified learnability provides a principled way to measure and reduce the learnability of protected datasets.

Highlights

PUEs turn data learnability into a certified quantity, giving data owners a formal tool for reasoning about whether protected data can still be used to train accurate models.

Certified learnability Computes probabilistic upper bounds on classifier performance over a certified parameter set.

Provable protection Uses learnability certification to evaluate and construct unlearnable examples with formal guarantees.

Robust evaluation Measures how effective and robust unlearnable examples remain under different training settings.

Abstract

We introduce the theory of certified learnability. Certified $(q,\eta)$-Learnability measures how learnable a dataset is by computing a probabilistic upper bound on the test performance of classifiers trained on this dataset, as long as those classifiers fall within a certified parameter set.

Using certified $(q,\eta)$-Learnability, we measure the effectiveness and robustness of unlearnable examples and propose Provably Unlearnable Examples (PUEs), which can reduce the learnability of protected training data.

Motivation

Challenge

Unlearnable examples are designed to prevent unauthorized model training, but their protection strength needs to be measured beyond empirical attack-and-defense benchmarks.

Solution

PUE connects data protection to certified learnability, giving a principled measurement for how learnable a protected dataset can be under certified training conditions.

BibTeX

@inproceedings{wang2025provably,
  title={Provably Unlearnable Data Examples},
  author={Wang, Derui and Xue, Minhui and Li, Bo and Camtepe, Seyit and Zhu, Liming},
  booktitle={Network and Distributed System Security Symposium},
  year={2025}
}