# Generalization Analysis on Learning with a Concurrent Verifier

arXiv: https://arxiv.org/abs/2210.05331 · HTML: https://mlsanity.com/paper/2210.05331/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 38 references that are in the map.
- First posted on arXiv 11 Oct 2022.

## Builds on (most cited first, 8 of 8)

- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks](https://mlsanity.com/paper/1702.01135/) (2017)
- [User-friendly introduction to PAC-Bayes bounds](https://mlsanity.com/paper/2110.11216/) (2021)
- [Lexically Constrained Decoding for Sequence Generation Using Grid Beam Search](https://mlsanity.com/paper/1704.07138/) (2017)
- [Guided Open Vocabulary Image Captioning with Constrained Beam Search](https://mlsanity.com/paper/1612.00576/) (2016)
- [Structured Prediction Theory Based on Factor Graph Complexity](https://mlsanity.com/paper/1605.06443/) (2016)
- [Multi-class SVMs: From Tighter Data-Dependent Generalization Bounds to Novel Algorithms](https://mlsanity.com/paper/1506.04359/) (2015)
- [Fine-grained Generalization Analysis of Structured Output Prediction](https://mlsanity.com/paper/2106.00115/) (2021)

## Abstract (arXiv)

Machine learning technologies have been used in a wide range of practical systems. In practical situations, it is natural to expect the input-output pairs of a machine learning model to satisfy some requirements. However, it is difficult to obtain a model that satisfies requirements by just learning from examples. A simple solution is to add a module that checks whether the input-output pairs meet the requirements and then modifies the model's outputs. Such a module, which we call a em concurrent verifier (CV), can give a certification, although how the generalizability of the machine learning model changes using a CV is unclear. This paper gives a generalization analysis of learning with a CV. We analyze how the learnability of a machine learning model changes with a CV and show a condition where we can obtain a guaranteed hypothesis using a verifier only in the inference time. We also show that typical error bounds based on Rademacher complexity will be no larger than that of the original model when using a CV in multi-class classification and structured prediction settings.