Turaco: Complexity-Guided Data Sampling for Training Neural Surrogates
  of Programs
Alex Renda Yi Ding Michael Carbin
Programmers and researchers are increasingly developing surrogates of
programs, models of a subset of the observable behavior of a given program, to
solve a variety of software development challenges. Programmers train
surrogates from measurements of the behavior of a program on a dataset of input
examples. A key challenge of surrogate construction is determining what
training data to use to train a surrogate of a given program.
  We present a methodology for sampling datasets to train neural-network-based
surrogates of programs. We first characterize the proportion of data to sample
from each region of a program's input space (corresponding to different
execution paths of the program) based on the complexity of learning a surrogate
of the corresponding execution path. We next provide a program analysis to
determine the complexity of different paths in a program. We evaluate these
results on a range of real-world programs, demonstrating that complexity-guided
sampling results in empirical improvements in accuracy.