# Synthesizing Machine Learning Programs with PAC Guarantees via Statistical Sketching

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

## Key facts

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

## Builds on (most cited first, 30 of 33)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Microsoft COCO: Common Objects in Context](https://mlsanity.com/paper/1405.0312/) (2014)
- [Faster R-CNN: Towards Real-Time Object Detection with Region Proposal Networks](https://mlsanity.com/paper/1506.01497/) (2015)
- [End-to-End Training of Deep Visuomotor Policies](https://mlsanity.com/paper/1504.00702/) (2015)
- [Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks](https://mlsanity.com/paper/1702.01135/) (2017)
- [Conformalized Quantile Regression](https://mlsanity.com/paper/1905.03222/) (2019)
- [BranchyNet: Fast Inference via Early Exiting from Deep Neural Networks](https://mlsanity.com/paper/1709.01686/) (2017)
- [Conformal Prediction Under Covariate Shift](https://mlsanity.com/paper/1904.06019/) (2019)
- [Uncertainty Sets for Image Classifiers using Conformal Prediction](https://mlsanity.com/paper/2009.14193/) (2020)
- [Safety Verification of Deep Neural Networks](https://mlsanity.com/paper/1610.06940/) (2016)
- [Programmatically Interpretable Reinforcement Learning](https://mlsanity.com/paper/1804.02477/) (2018)
- [The Case for Learned Index Structures](https://mlsanity.com/paper/1712.01208/) (2017)
- [Verifiable Reinforcement Learning via Policy Extraction](https://mlsanity.com/paper/1805.08328/) (2018)
- [Adaptive Neural Networks for Efficient Inference](https://mlsanity.com/paper/1702.07811/) (2017)
- [Measuring Neural Net Robustness with Constraints](https://mlsanity.com/paper/1605.07262/) (2016)
- [Verisig: verifying safety properties of hybrid systems with neural network controllers](https://mlsanity.com/paper/1811.01828/) (2018)
- [Scenic: A Language for Scenario Specification and Scene Generation](https://mlsanity.com/paper/1809.09310/) (2018)
- [Scalable End-to-End Autonomous Vehicle Testing via Rare-event Simulation](https://mlsanity.com/paper/1811.00145/) (2018)
- [Learning to Infer Graphics Programs from Hand-Drawn Images](https://mlsanity.com/paper/1707.09627/) (2017)
- [PAC Confidence Sets for Deep Neural Networks via Calibrated Prediction](https://mlsanity.com/paper/2001.00106/) (2019)
- [Adaptive, Distribution-Free Prediction Intervals for Deep Networks](https://mlsanity.com/paper/1905.10634/) (2019)
- [Neurosymbolic Reinforcement Learning with Formally Verified Exploration](https://mlsanity.com/paper/2009.12612/) (2020)
- [Probabilistic Verification of Fairness Properties via Concentration](https://mlsanity.com/paper/1812.02573/) (2018)
- [Optimization and Abstraction: A Synergistic Approach for Analyzing Neural Network Robustness](https://mlsanity.com/paper/1904.09959/) (2019)
- [An Inductive Synthesis Framework for Verifiable Reinforcement Learning](https://mlsanity.com/paper/1907.07273/) (2019)
- [HOUDINI: Lifelong Learning as Program Synthesis](https://mlsanity.com/paper/1804.00218/) (2018)
- [Learning Differentiable Programs with Admissible Neural Heuristics](https://mlsanity.com/paper/2007.12101/) (2020)
- [Differentiable Programs with Neural Libraries](https://mlsanity.com/paper/1611.02109/) (2016)
- [PAC Confidence Predictions for Deep Neural Network Classifiers](https://mlsanity.com/paper/2011.00716/) (2020)
- [Bayesian Synthesis of Probabilistic Programs for Automatic Data Modeling](https://mlsanity.com/paper/1907.06249/) (2019)

## Abstract (arXiv)

We study the problem of synthesizing programs that include machine learning components such as deep neural networks (DNNs). We focus on statistical properties, which are properties expected to hold with high probability -- e.g., that an image classification model correctly identifies people in images with high probability. We propose novel algorithms for sketching and synthesizing such programs by leveraging ideas from statistical learning theory to provide statistical soundness guarantees. We evaluate our approach on synthesizing list processing programs that include DNN components used to process image inputs, as well as case studies on image classification and on precision medicine. Our results demonstrate that our approach can be used to synthesize programs with probabilistic guarantees.