# Synthesizing Machine Learning Programs with PAC Guarantees via Statistical Sketching

Source: [Synthesizing Machine Learning Programs with PAC Guarantees via Statistical Sketching](<https://www.sota2.com/research/paper/68fa6aff1e209131cea2ba02>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-28T13:56:50.176Z

Authors: Osbert Bastani

Published: 2021-10-11T16:30:04.000Z

## Abstract

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.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2110.05390>)

[PDF](<https://arxiv.org/pdf/2110.05390.pdf>)