Certifying the True Error: Machine Learning in Coq with Verified Generalization Guarantees

Alexander Bagnall, Gordon StewartAAAI 2019 · DOI

Introduction

In safety-critical domains such as autonomous driving and medical diagnostics, empirical validation of machine learning models is often insufficient. Standard practices rely on holdout sets to estimate performance, but this approach is susceptible to $p$-hacking, data leakage, and lacks a rigorous mathematical link between statistical theory and the actual deployed code. MLCERT addresses this "trust gap" by providing the first system for machine-checked, formal proofs of generalization bounds for executable machine learning models.

The MLCERT Framework

MLCERT is built within the Coq theorem prover and integrates statistical learning theory with formal verification. The framework rests on three primary pillars:

  1. Mechanized Learning Theory: Core statistical tools, including Chernoff and Hoeffding bounds, are formalized in Coq to ensure the mathematical foundations of error calculation are verified.
  2. Probabilistic Programming Semantics: Learning procedures are treated as probabilistic programs with formal denotational semantics, allowing for proven properties regarding expected accuracy over a distribution.
  3. Model Extraction and Interoperability: MLCERT can import models from external frameworks like TensorFlow. Once a model is defined or imported, Coq extracts it into executable OCaml or Haskell code. This process ensures that generalization guarantees carry over to the deployed software.
The MLCERT workflow: importing models from TensorFlow to produce a certified executable model with guaranteed error bounds.

A key innovation in MLCERT is certifying the resulting classifier rather than the entire training algorithm. This "oracular" approach allows developers to use high-performance, unverified tools to find optimal weights, while MLCERT provides the formal certification for the final model.

Regularization through Quantization

Standard statistical bounds often become "vacuous" (meaningless) for complex deep learning models. To achieve useful, "tight" bounds, MLCERT utilizes neural network quantization. By restricting weights to low precision (e.g., 2-bit integers), the framework drastically reduces the "Hypothesis Space"—the total number of possible models. This reduction is a formal tool for regularization that makes mathematical certification feasible.

Experimental Results

The researchers evaluated MLCERT using the EMNIST digit classification task on a fully connected network with one hidden layer. They compared two types of certified bounds:

  • Union Bounds: These bounds are based on training performance and model complexity. For a 2-bit quantized model, MLCERT proved a guaranteed expected accuracy of 77.3% (despite a training accuracy of 92.5%). While loose, this represents a non-trivial mathematical guarantee.
  • Holdout Bounds: By employing a certified holdout protocol, the framework achieved significantly tighter bounds, certifying expected accuracy between 91% and 94% with extremely high confidence ($1 - 10^{-9}$).
Experimental results on EMNIST showing the impact of quantization (W) on certified generalization bounds.

Limitations and Future Directions

While MLCERT represents a significant step toward "Verified AI," several challenges remain. The current proofs rely on the "independent and identically distributed" (I.I.D.) assumption and do not yet account for distribution shifts or adversarial attacks. Furthermore, while quantization helps, union bounds for high-precision models (e.g., 16-bit) remain loose. Future work may explore PAC-Bayes bounds to provide tighter guarantees for more complex, deep architectures like ResNets or Transformers.

Summary updated

BibTeX
@inproceedings{bagnall2019certifying,
  author = {Alexander Bagnall and Gordon Stewart},
  title = {{Certifying the True Error: Machine Learning in Coq with Verified Generalization Guarantees}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33012662},
}
Figure