# Overestimation learning with guarantees

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 27 references that are in the map.
- First posted on arXiv 26 Jan 2021.

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

- [Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks](https://mlsanity.com/paper/1702.01135/) (2017)
- [Input Convex Neural Networks](https://mlsanity.com/paper/1609.07152/) (2016)
- [Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks](https://mlsanity.com/paper/1703.02930/) (2017)
- [Certified Defenses against Adversarial Examples](https://mlsanity.com/paper/1801.09344/) (2018)
- [Bayesian Convolutional Neural Networks with Bernoulli Approximate Variational Inference](https://mlsanity.com/paper/1506.02158/) (2015)
- [High-Quality Prediction Intervals for Deep Learning: A Distribution-Free, Ensembled Approach](https://mlsanity.com/paper/1802.07167/) (2018)
- [The loss surface of deep and wide neural networks](https://mlsanity.com/paper/1704.08045/) (2017)
- [Deep Neural Network Compression for Aircraft Collision Avoidance Systems](https://mlsanity.com/paper/1810.04240/) (2018)
- [CNN-Cert: An Efficient Framework for Certifying Robustness of Convolutional Neural Networks](https://mlsanity.com/paper/1811.12395/) (2018)
- [A Comprehensive Analysis of Deep Regression](https://mlsanity.com/paper/1803.08450/) (2018)
- [Generalization Error in Deep Learning](https://mlsanity.com/paper/1808.01174/) (2018)
- [Calibrated Prediction Intervals for Neural Network Regressors](https://mlsanity.com/paper/1803.09546/) (2018)
- [Artificial Neural Network Surrogate Modeling of Oil Reservoir: a Case Study](https://mlsanity.com/paper/1905.07859/) (2019)

## Built on by (most cited first, 1 of 1)

- [Hybrid Convolutional Neural Networks with Reliability Guarantee](https://mlsanity.com/paper/2405.05146/) (2024)

## Abstract (arXiv)

We describe a complete method that learns a neural network which is guaranteed to overestimate a reference function on a given domain. The neural network can then be used as a surrogate for the reference function. The method involves two steps. In the first step, we construct an adaptive set of Majoring Points. In the second step, we optimize a well-chosen neural network to overestimate the Majoring Points. In order to extend the guarantee on the Majoring Points to the whole domain, we necessarily have to make an assumption on the reference function. In this study, we assume that the reference function is monotonic. We provide experiments on synthetic and real problems. The experiments show that the density of the Majoring Points concentrate where the reference function varies. The learned over-estimations are both guaranteed to overestimate the reference function and are proven empirically to provide good approximations of it. Experiments on real data show that the method makes it possible to use the surrogate function in embedded systems for which an underestimation is critical; when computing the reference function requires too many resources.