Optimal Data Sampling for Training Neural Surrogates of Programs
Authors: Alex Renda
Yi Ding
Michael Carbin
Venue: Submitted to ICLR 2023 (2023)
Keywords: programming languages
surrogates
program analysis

Abstract: 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.

We present a methodology for optimally sampling datasets to train neural network based surrogates of programs. We first characterize the optimal proportion of data to sample from each path in a program based on the complexity of learning the path. We next provide a program analysis to determine the complexity of different paths in a program. We evaluate these results on a large-scale graphics program, demonstrating that theoretically optimal sampling results in empirical improvements in accuracy.

Under review as conference paper at ICLR 2023
OPTIMAL DATA SAMPLING FOR TRAINING NEURAL SURROGATES OF PROGRAMS
Anonymous authors Paper under double-blind review
ABSTRACT
Programmers and researchers are increasingly developing surrogates of programs, models of 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 program on a dataset of input examples. We present a methodology for optimally sampling datasets to train neural network based surrogates of programs. We first characterize the optimal proportion of data to sample from each path in a program based on the complexity of learning the path. We next provide program analysis to determine the complexity of different paths in program. We evaluate these results on a large-scale graphics program, demonstrating that theoretically optimal sampling results in empirical improvements in accuracy.
INTRODUCTION
Programmers and researchers are increasingly developing surrogates of programs, models of subset of the observable behavior of a given program, to solve a variety of software development challenges (Renda et al., 2021). For example, Esmaeilzadeh et al. (2012) train small neural networks to mimic existing programs, then deploy the neural networks in place of the programs to speed up computation. Generally, surrogates are used to accelerate programs (Esmaeilzadeh et al., 2012; Mendis et al., 2019; Munk et al., 2019), apply transfer learning to programs (Tercan et al., 2018; Kustowski al., 2020; Kwon & Carloni, 2020), and approximate the gradient of programs to optimize their inputs (Renda et al., 2020; She et al., 2019; Tseng et al., 2019).
Dataset generation. Training surrogate of program requires measurements of the behavior of the program on a dataset of input examples. There are three common approaches to collecting this dataset. The first use data that is uniformly sampled (or sampled using another manually defined distribution) from the input space of the program (Tseng et al., 2019; Kustowski et al., 2020). The second is to use data instrumented from running the original program on a workload of interest (Renda et al., 2020; Esmaeilzadeh et al., 2012). The third is to use active learning (Settles, 2009), class of online methods that iteratively query labels for data points based on the expected improvement in accuracy resulting from additional samples (ipek al., 2006; She et al., 2019; Pestourie al., 2020).
These approaches show promise, but they face challenges with programs with control flow. Programs with control flow (e.g. branches and loops) piecewise functions: each control flow path induces a different trace of operations that are applied to the input. The sampling techniques above do not optimally allocate samples between different paths, resulting in surrogates which do not adequately learn the behavior of the program along all paths. For example, Renda et al. (2020, Section IV.A) identify scenario in which instrumented dataset does exercise set of paths in the program enough times for the surrogate to learn the behavior along those paths.
Our approach uses the source code and semantics of the program under study guide dataset generation for training a surrogate of the program. The core concept is to analyze the complexity of each path in program and to allocate more samples to paths that are more complex learn.
Our approach.
Stratified functions. Our approach represents the program as functioon function with different behavior in different regions (strata) of the input space (i.e., piecewise function). We use
We choose the term stratiffed by analogy with the technique of stratified sampling.

---

Under review as conference paper at ICLR 2023
stratified surrogates to model such functions. To construct stratified surrogate, we train independent surrogates of each component of the stratified function. At evaluation time, a stratified surrogate checks which stratum input is in (using the original program) then applies the corresponding surrogate.
This evaluation- time stratum check must not preclude the use of the surrogate for its downstream task. We therefore adopt standard modeling assumption in the approximate computing literature: that precisely determining paths is an acceptable cost during approximate program execution (Sampson al., 2011; I; Carbin al., 2013). 2.33
Optimal sampling. With this stratified modeling assumption, we then determine how many samples allocate train each surrogate. Using neural network sample complexity bounds for learning ana- lytic functions (Arora et al., 2019; Agarwala et al., 2021) we calculate a complexity for each component function which gives an upper bound on how many samples are required to learn the behavior of that com- ponent to given error. Given data distribution describing the frequency of each component and given each component function's 's complexity, we then derive the optimal number samples to allocate to train- ing each surrogate of each component, minimizing the upper bound on the stratified surrogate' error.
Complexity analysis. We present a programming language, TUR ACO, in which programs denote stratified functions with well-defined complexity measures. We provide a program analysis for TURACO programs that automatically determines the strata of the function and calculates an upper bound on the complexity of each component of the stratified function that the program denotes.
Renderer demonstration. To demonstrate that optimal sampling using our complexity analysis improves surrogate accuracy on downstream tasks, we present a case study of learning a surrogate of renderer in video game engine. We show that our optimal sampling approach results in between 15% and 47% lower error than training using distributions that do not take into account path complexity. These accuracy improvements correlate with perceptual improvements in the generated renders.
Contributions. In sum, we present the following contributions:
An optimal approach to allocating samples among strata to train stratified neural network surro- gates of stratified analytic functions that minimizes the upper bound the surrogate's error.
A programming language, TURACO, in which all programs are learnable stratified functions, and a program analysis to determine the complexity of learning surrogates of those programs.
An evaluation of these results on graphics program, demonstrating that theoretically optimal sampling using TURACO's complexity analysis results in empirical improvements in accuracy.
We lay the groundwork for analyzing optimal sampling approaches for training surrogates of programs. Our results hold out the promise of surrogate training approaches that intelligently use the program's s semantics to guide the design and training of surrogates of programs.
EXAMPLE
Figure la presents an example distilled from our evaluation (Section 5) that we use demonstrate how optimal path sampling, sampling from paths according both to their frequency in a data distribution and their complexity, results a more accurate surrogate than frequencynn sampling according to the frequency of paths alone.
path sampling.
Program under study. We study graphics program that calculates the luminance (i.e., brightness) at a point in a scene as a function of sunPos ition, the height of the sun in the sky (i.e., the time of day) which ranges from - to 1, and emi ssion, a property of the material at that point which ranges from -1 to 1. The program first checks whether it is daytime (Line 2), and sets the ambient lighting variable accordingly. The program next checks whether the sun position is above a threshold (Line 7) and sets the emission variable accordingly. The output is then the sum of the ambient light and the light emitted by the material. Figure 1b presents the output of this program on inputs between 1 and 1.
><Ener] ... prohibit(s] approximate values in conditions that affect control flow." (Sampson et al., 201 1). *"Rely assumes that.. ... control flow branch targets are computed reliably." (Carbin al., 2013).
2

---

Under review conference paper at ICLR 2023
Luminunce Auross Eapu: Distribution
400
2.0
I fun (sunPosition emission)
1.5
-06
2 if (sunPosition
ambient =
ediecion 1on
-02
0.5
else {
5 amhient = sun Punioiion
022
6
7 emission max 10.1, sunPosition)
06
return ambient emission
100
-10
.0.6
10
0.2
0.5
1.0
tioon
(a) Graphics program calculating the luminance of pixel a function of ambient light and material properties.
(b) Output of the program on inputs in [-1,1], with dashes separating the three paths.
assume: sunPasition
assume sunPosition fun (sunPosition emission) ambicat sunPosition: emission == 0.1: return ambient emission:
assume: sunPosition fun (sunPasition emission)
fun (sunPasition emission) [ ambient
ambicnt sunPosition: emission sunPosition;
emission 0.1:
return ambient + emission:
return ambient + emission:
(c) Nighttime (1.1 path.
(d) Twilight path.
(e) Daytime (rx)
Figure 1: Example program, outputs, and traces.
The path conditions (Lines 2 and 7) partition the program into three traces: nighttime, when sunPositinn ion is less than (Figure Ic); twilight, when sunFosition is between 0 and 0.1 (Figure Id); and daytime, when sunPosi i in greater than 0.1 (Figure le). These paths are separated by dashed black lines in Figure lb.
Training a surrogate of this program poses particular challenge because of the different behavior of these traces. Furthermore, these traces have different relative complexities: when sunPosi ii toitiii on less than 0.1 the function linear, but when sunPos i tion above 0.1 the function is quadratic.
We must ensure that the data distribution that we use for training surrogates reflects not only the different paths of the program, but also the relative complexities each path the program.
Optimal path sampling. We present approach to determining the optimal amount of training data to sample from each path to train stratified surrogate of this program. Specifically, given data distribution and a data budget path to minimize the expected error of surrogate the program over the data distribution. Intuitively, our approach prioritize sampling paths that are frequent and paths that are complex (and thus require more samples to learn).
find the optimal number of data points to sample from each
First we determine the frequency of each path in the underlying data distribution. We assume that the data has uniform distribution over inputs between - and 1. This results in path frequencies for the nighttime path (sunPod os i on < 50%, the twilight path (O < sunPosition < 0. of 10%, and the daytime path (C 1 sunPosition) of 40%.
Next we determine the sample complexity of each path, the number of samples required to learn the function along that path given error. We use the sample complexity results of Agarwala et al. (2021), who give upper bound on the number of samples required to learn neural network approximation of a given function. Using this bound (as implemented by our TURACO analysis described in Section 4.2), we determine that the twilight path takes 1.5x many samples to train a surrogate to a given error as the nighttime path, and the daytime path requires 5 as many samples.
Finally, we combine these metrics to determine the optimal sampling rates. Using Equation (3) in Section 3.2, we find that the optimal sampling rate to sample 39.3% of the data from the nighttime path, 14.3% of the data from the twilight path, and 46.4% of the data from the daytime path.
Stratified surrogates. The class of surrogate model for which the above approach optimal is that of stratified neural surrogate set of disjoint neural networks which are applied based on which
3

---

Under review as conference paper at ICLR 2023
Sample Effiriencies of Paths
Surmaate Frrr
Daytie Thilight
Oyeinal Sumpling
Fregumyy Samping
1071
Nigetimm
Eroo
Brrez
10m2
10"2
10-0
10
Nuraber of Path Somples
Total Dataset Size
(a) Per-path surrogate errors (log-log plot).
(b) Stratified surrogate errors (log-log plot). Optimal decresssss the error by 15%.
decreases
Figure 2: Per-path surrogate errors (left) and combined errors (right) for the example.
path the inputs induce in the program. Concretely, this means that we train one surrogate per path, and pick which to apply for each imput evaluation time. For this example program, picking which surrogate to apply just requires comparing sunPosit ton against constant threshold values.
Training methodology. For each surrogate, we train a 1-hidden-layer MLP with 512 hidden units with ReLU activation, using 10,000 steps of Adam with learning rate 0.0005 and batch size 128.
Results. Figure 2 presents the error of surrogates trained to mimic this program, as function of the training dataset size. On the left, Figure 2a presents the eттоr of surrogates of each path. On the right, Figure 2b presents the error of stratified surrogates of the entire program for optimal path sampling and baseline of sampling according to path frequency alone. The axis of each plot is the dataset size used to train the surrogate (on the left, the dataset size per path; on the right, the total dataset size used for all paths). The y axis of each plot is the error of the resulting surrogate (lower is better).
Figure 2a shows that though the complexity measure is not exactly proportional to the empirical sample complexity, it does correlate with it: at given data budget, the daytime path with the highest complexity has the highest error, followed by twilight then nighttime.
Figure 2b shows that the optimal path sampling approach results in lower error than sampling according to path frequency alone. For datasets total size below 70 samples, the surrogate trained with optimal path sampling has geometric mean decrease in error of 27.5%. For datasets of total size above 70 samples, the surrogate trained with optimal path sampling has a geometric mean decrease in error of 5.5%. Across the entire range of dataset sizes evaluated in this plot, the surrogate trained with optimal path sampling has a geometric mean decrease in error of 15%.
3 OPTIMAL SAMPLING
In this section, formally define stratified functions and stratified surrogates, and derive the optimal sampling distribution to use when training stratified surrogate of stratified function.
3.1 SETUP
We define a learning algorithm, function that trains a surrogate of given input function, as random function tr: (X'+))) x X C (X' y)) that takes function f X + from inputs e X to outputs y E ), a distribution D e D over inputs æ, number of training examples E N, and a loss function &E x R2 which measures the cost of an incorrect prediction, and returns function (representing the output surrogate) f:X 7:x++3 +.y
Equation defines a given function f as probably approximately correctly learnable (abbreviated as learnable for the remainder of the paper) for given learning algorithm tr and loss function & if for all distributions D. with high probability - 5 the learning algorithm returns surrogate f that
4

---

Under review as conference paper at ICLR 2023
approximately matches the original function over the distribution D:
50)
(D,,E(0.1),EE(0)))... f.tr(f.D,n.8)
E Low
(I)
Following Arora et al. (2019) and Agarwala al. (2021) study functions and learning algorithms for which there is measure of the complexity {(f) of function ff for the learning algorithm tr such that the relationship between n, ((f), and in Equation (1) is:
(() -lgg(oo(( log(6-)) (6-2)
CCnSC
(2)
2²
We instantiate the complexity measure ((J) for neural networks in Section 3.3.
We define stunittttd f as follows:
fi(a) if
f(x) -
fe(z) if
where is the number of strata, {8: 1i are strata, vi and =
We define stratified surrogate f stratified function with components ft.
For a data distribution D, let (2x) be the probability that x sampled from D, and (8;)) ) be the total probability mass all data points within s; over D (i.e., D(s:) D(x)) Let (xlss. be the probability of data point æ sampled from D if Es.
3.2 OPTIMAL SAMPLING
Our goal learn a stratified surrogate of a stratified function f. where each component function f, is learnable. We are given data distribution D, maximum sample budget n. learning algorithm tr, a loss function and failure probability ò. Our task therefore to find the number of samples to allocate each stratum train surrogate of that function component. We assume that each surrogate component's s failure probability 6; o==² = which satisfies the overall failure probability by union bound.
Note that Equation (2) is upper bound and not an exact equality. We therefore minimizing the upper bound of the error of the resulting surrogate, rather than directly minimizing the error.
Formally, solve the following optimization problem:
(f(s))(()) s.t. En.sn and f:~tr(fi,Daass))nn
argmin E (m.)²_, ENHEED
Theorem 3.1. With 6, the upper bound of Equation (3) is minimized at:
200
(Dls)//(Uf++oollo))
n4 =n
3²
(D(()))))(U
The proof of this theorem presented in Appendix C.
3.3 NEURAL NETWORK LEARNABILITY
Equation (2) defines the required sample complexity for learning ff as a function ((f), the complexity of f. This section defines ((f) for training neural network surrogates of analytic functions. This section is an abridged summary assumptions and results presented by Agarwala et al. (2021) and Arora et al. (2019); refer to Agarwala et al. (2021) for the full set of assumptions.

---

Under review as conference paper at ICLR 2023
Agarwala et al. (2021) provide calculus for learning surrogates of analytic functions f (around 0) based on the tilde f of the function:
00
f(x)
f(x)
- an
|2"
n=0
n=0
Note the following properties for x 2:
f(x)+g(() h()) - ((x))((() (((()) ith(x)) [o(()) and))) f forī(z)
ith(x))= = +g))+(()) ith(z)= (x) .g(x)
(4)
For 2-layer neural network trained with stochastic gradient descent, if f is analytic, H is the d-dimensional unit sphere (œ E 5 3 e R2 parameter set to control the scale of the inputs), and ê is 1-L.ipschitz, then (B--F) is learnable with:
<() = (U)=~(1915/(19911))) (1891)
TURACO: PROGRAMS AS STRATIFIED FUNCTIONS
In this section we present TURACO, programming language in which all programs denote learnable stratified functions. We provide a program analysis for TURACO programs which calculates an upper bound on the complexity of each component of the stratified functions that the program denotes.
4.1 SYNTAX AND STANDARD INTERPRETATION
p: f:=fun (x++ {s returnæ
Figure 3
presents the syntax of TURACO, a loop-free IMP-like language (Winskel, 1993). A TURACO program takes list of imputs x, executes a top-level statement s, and returns a single variable Statements are skips, sequences, assignments, or if statements. Expressions are variables v, values v, binary opera- tions b, or unary operations
skip s:s :===
lif (e 0) (8 { (
6::=00 u ((c,))))))))))))))))))))) (u(e)
b: ADD MUL.
W:: =:=NEG SIN EXP |LOGIP
TURACO supports analytic operations (e.g.. NEG, SIN, EXP), including those which can be represented by power series within given domain: LOG1P computes log(1 (1++) for x E (-1,1]. We restrict the supported operations to those required implement the case study in Section 5.
T:: d::-Set of variable names
0:: of floating point values
Figure 3: Syntax of TURACO.
Appendix D.I presents the full set of semanties for TURACO.
4.2 COMPLEXITY ANALYSIS
now present a program analysis that gives an upper bound on the complexity of traces of TURACO programs. This section presents core set of rules; Appendix D.2 presents the full analysis.
The analysis uses three core concepts: a complexity interpretation of expressions to calculate an upper bound on the tilde of expressions based the calculus in Equation (4), dual-number execu- tion (Wengert, 1964; Griewank & Walther, 2008) to calculate the derivative the upper bound on the tilde (to compute the first term in Equation (5)), and a path analysis which splits the program by paths to compute the complexity of each trace.
Figure 4 presents the big-step relations used to calculate upper bound on the complexity for subset of expressions. The relation (o](e)) & (0,6") says that under the variable complexity mapping ă (mapping variables to tuples with their respective tilde and tilde derivative), the expression e has é and é' < T'. Note that the rule for MUL uses the upper bound for multiplication in Equation (4).
Figure presents the complexity relation for if statements. For statements, (ā,s) I E says that under the variable complexity mapping ,, the statement & results in set of paths with complexity mappings E(p) for path p. We use a period to denote string concatenation (e.g.. 1.p to prepend p with 1).
'https: : //////gtttb//t con. (clr-0022 UoKEoeTPtiI/turee contains our implementation of
TURACo and of the experiments Sections 2 5.

---

Under review as conference paper at ICLR 2023
(0,,)) (12,1)))
((o,))))))))
(x,z) (((x)
(U, $ (ör 02 -2
Figure Complexity relation for expressions in TURACO
( ( Of (e>0)) else { s22 1) / pe p
Figure Complexity relation for statements, using period to denote string concatenation.
To calculate the complexity ( as defined in Section 3.3 (for a given input 9 parameter, which represents the scale of the input data) of each path of a program, we use the statement relation to calculate f3) and f0). Appendix D.3 presents this rule, along with the theorem that the complexity calculated by this analysis is an upper bound on the complexity as defined in Section 3.3.
RENDERER DEMONSTRATION
In this section we present a case study of our optimal sampling results and complexity analysis. The program under study is demonstration 3D renderer (Lettier, 2019), such forms the of graphics rendering pipeline for movie or 3D game engine (Christensen et al., 2018; Tatarchuk, 2006). Figures 6a and 6b show scenes that the renderer generates. We demonstrate that the sampling and analysis techniques in Sections 3 and 4 consistently result in more accurate surrogates than those trained using baseline distributions (the frequency distribution paths and the uniform distribution).
Compared to training surrogates on the frequency distribution of paths, optimal path sampling decreases error by 15%. Compared training on the uniform distribution of paths, optimal path sampling decreases error by 47%. These improvements in error correspond to perceptual improvements in the generated images, shown in Figures 6e to 6e.
5.1 PROGRAM UNDER STUDY
The full renderer program is 2750 lines-of-code C++ program, which invokes 38 different GLSL shader programs totaling 2446 lines of code. We learn surrogate a section of one core shader, totaling 60 lines of code. Figure 18 in Appendix E presents the code under study.
Input-output specification. This program is shader which assigns colors to pixels in the image based on the scene geometry, materials, lights, and other properties. The program is called for each pixel that is rendered in the image. Each invocation the program takes as input a set of 11 fixed-size vectors, totaling 35 inputs. The program returns output set of 2 fixed-sizz vectors, totaling outputs. 5 These outputs are two RGBA colors, the first representing the base color of the pixel, and the second representing the color and intensity of specular map that pixel.
Scenes and datasets. We evaluate the renderer on four different scenes, which we combine into nine different datasets. Figures 6a and 6b present two of the four different scenes under consideration; the four scenes are all combinations views from the front and top, during the day and night. We combine these scenes into nine datasets: dataset with each scene, dataset combining each scene from each angle (front day and front night, top day and top night), a dataset combining each scene from each time of day, and a dataset combining all scenes. Figure 14 in Appendix E presents the full set of scenes under study.
$1 Linees 278 through 337 of httpss: http://hhh......m/e/eettttee//// sartssd--aaa-eeeee Saaeiaaaaaaassseseeeeeeee shaders-------- for-begi ners/bi /b1 ht//b/ob/297008 htt////770/////m/n/// demonst rat on swwsshhaaase/eee http///aaaan//aaaeeeeeee wawaggenntbbae.....eeee /base. frag. *Our implementation of TURACO extends the interpreter and analysis vectors, with the resulting complexity heing the sum of the complexity of each component of the output vector.
7

---

Under review conference paper at ICLR 2023
(a) Ground-truth front-day scene.
(b) Ground-trum top-night scene.
(c) Optimal surrogate.
(d) Frequency--neeee surrogate.
(e) Uniform surrogate.
Figure Ground-truth (top) and surrogate renderings (hottom) of scenes generated by the renderer.
Table 1: Top: the identifier, lines of code, complexity, and description of each path present in our datasets. Bottom: the distribution (abbreviated distr.) of each path across subset of datasets: the frequency (freq.) of each observed path, and the optimal sampling rate (opt.) that path.
Path
Irclir
Irrirl
Irrirr
Irrrir
Irrrel
Irrrr
rrrlir
rrrirl
rrrir
Lines of Code
17
17
17
18
18
17
17
17
Complexity
6210
5899
6369
6650
6328
6814
6459
6142
6621
Twilight
Twilight
Twilight
Nighttime
Nighttime Nightime
Daytime
Daytime
Daytime
Description
Water
Smoke
Solids
Water
Smoke
Solids
Water
Smoke
Solids
Dataset
Distr:
Irrllr
Irrirl
Irrrr
Irrrir
lrrrll
Irrrrr
rrelir
rerirl
vrrlrr
Front Day
Freq.
5.0%
7,9%
87.1%
Opt.
11.0%
14.7%
74,4%
Top Night
Freq. Opt.
0.16%
0.06%
1.2%
0.3%
0.1%
2.4%
6.3%
12.9%
76.5%
0.95%
0.49%
3.6%
1.5%
0.8%
5.9%
10.9%
17.4%
58.4%
All
Froq. 0.04%
0.02%
0.3%
1.3%
2.0%
13.5%
4.5%
8,5% 12.4%
69.8%
Opt. 0.35%
0.18%
1.3%
3.7%
4.8%
17.4%
8.2%
51.6%
Table 2: Average change in error across all budgets from using optimal sampling compared to baselines on each dataset (negative means optimal sampling has lower error).
Front Day
Front Night
Top Day
Top Night
Baseline
Front
Top
Day
Night
All
Mean
Frequency Uniform
-4%
+6%
+2%
-9%
+3%
-33%
-2%
-13%
-29%
-15%
-6%
-32%
-36%
-45%
-47%
-64%
-35%
-58%
-53%
-47%
8

---

Under review as conference paper at ICLR 2023
Paths. The program is a conjunction of 48 different paths, of which exercised by the renderer. The top part of Table presents statistics about the paths under study, showing the identifier (a trace of 1 and characters denoting which branch of each if statement the path takes), the lines of code in the corresponding trace, and the complexity of the corresponding trace according to the analysis in Section 4.2. The paths are broken up into a path for rendering smoke particles from the chimney, water particles in the river, and the solids of the ground and house. Each set of paths is duplicated for twilight, nighttime, and daytime. Within each time of day, the smoke paths are the least complex, followed by water then solids. Across time, twilight paths the least complex, followed by daytime then nighttime.
Table I also presents the observed and optimal distributions of paths for each dataset. In general, the twilight paths are rarer than the nighttime paths, which are rarer than the daytime paths: this is because data collection for the nighttime scenes extends through twilight and into the morning. For all datasets, the smoke paths are rarer than the water paths, which are in turn rarer than the solids paths; this is purely due to the number of points observed for each scene.
Appendix E.1 presents code, statistics, and visualizations of all paths in the scene.
5.2 SURROGATE TRAINING AND DEPLOYMENT METHODOLOGY
To create and deploy surrogate of the renderer, we train surrogate of each path, then create a stratified surrogate which branches on the set of path conditions and applies the corresponding surrogate.
Our goal is to compare the theoretical and empirical errors achieved by training on the optimal sampling distribution against those of baseline distributions. We compare the approaches across different training datasets, different total numbers of training data points, and evaluating across different evaluation sets, all with multiple trials. Full methodological details are presented in Appendix E.2.
5.3 SURROGATE ERRORS
Table 2 presents the geometric mean change in error of using optimal sampling compared to each baseline, on each dataset. Across most datasets, optimal path sampling results in lower error than both frequency-ban -basen path sampling and uniform path sampling. On datasets with few paths (front- day) and in which all paths are well represented (minimum 5% frequency), the gap minimal, and frequency- based path sampling matches or outperforms optimal path sampling. On datasets with more and rarer paths (top-night), the gap widens and optimal path sampling outperforms frequency-bard based path sampling. On all datasets, optimal path sampling outperforms uniform path sampling.
5.4 VISUALIZATION
Figure 6 presents the renderings generated by the surrogates for the front-day and the top-night scene. These budgets correspond to the smallest budget that lead to a validation error less than 2%, which was qualitatively chosen as threshold around which surrogate renders converge the ground truth.
The top row shows the front day scene using surrogates trained on the front day dataset. In this scene, the optimal and frequency- based surrogates result in similarly accurate renders, with the primary difference being that the frequency-based surrogate is overall more red, which is most notable the windows and the front face of the house. This similarity is expected given the similar errors observed in Table 2. Uniform sampling results in an inaccurate render, as expected given its high error.
The bottom row show the top night scene using surrogates trained on the dataset combining all scenes. In this scene the optimal surrogate has the most accurate render, as expected given the errors observed in Table The frequency-trained surrogate colors everything (especially the roof and water) slightly more pink. The uniform-trained surrogate colors everything significantly more green.
In sum, the error improvements in Table 2 result in visual improvements in the generated renders.
6 CONCLUSION
We present an optimal approach to allocating samples among strata to train stratified neural network surrogates of stratified functions. We also present a programming language, TURACO, in which all programs are learnable stratified functions and a program analysis to determine the complexity of learning surrogates of those programs. Our results take a step towards a cohesive, end-to-end methodology for programming using surrogates of programs.

---

Under review as conference paper at ICLR 2023
REFERENCES
Atish Agarwala, Abhimanyu Das, Brendan Juba, Rina Panigrahy, Vatsal Sharan, Xin Wang, and Qiuyi Zhang. One network fits all? modular versus monolithic task formulations in neural networks. In International Conference on Learning Representations, 2021.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine- Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In International Conference Machine Learning, 2019.
Tao Bao, Yunhui Zheng, and Xiangyu Zhang. White box sampling in uncertain data processing enabled by program analysis. In ACM International Conference Object Oriented Programming Systems Languages and Applications, 2012.
Cristian Cadar, Daniel Dunbar, and Dawson Engler. Klee: Unassisted and automatic generation of high-coverage tests for complex systems programs. In USENIX Conference on Operating Systems Design and Implementation, 2008
Michael Carbin, Sasa Misailovic, and Martin Rinard. Verifying quantitative reliability for programs that execute unreliable hardware. In Conference Srrject-Oreetted Programming, Systems, Languages and Applications, 2013.
Per Christensen, Julian Fong, Jonathan Shade, Wayne Wooten, Brenden Schubert, Andrew Kensler, Stephen Friedman, Charlie Kilpatrick, Cliff Ramshaw, Marc Bannister, Brenton Rayner, Jonathan Brouillat, and Max Liani. Renderman: An advanced path-tracing architecture for movie rendering. ACM Trans. Gruph., 37(3), 2018.
Corinna Cortes, Giulia DeSalvo, Claudio Gentile, Mehryar Mohri, and Ningshan Zhang. Region-based active learning. International Conference on Artificial Intelligence and Statistics, 2019.
Patrick Cousot and Radhia Cousot. Abstract interpretation: unified lattice model for static analysis of programs by construction or approximation of fixpoints. In ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, 1977.
Hadi Esmaeilzadeh, Adrian Sampson, Luis Ceze, and Doug Burger. Neural accelcration for general- purpose approximate programs. In IEEE/ACM International Symposium on Microarchitectuve, 2012.
Andreas Griewank and Andrea Walther. Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation. SIAM, 2nd edition, 2008.
Jan Hoffmann and Martin Hofmann. Amortized resource analysis with polynomial potential. In Programming Languages and Systems, European Symposium on Programming, 2010.
Engin lpek, Sally A. McKee, Rich Caruana, Bronis R. de Supinski, and Martin Schulz. Efficiently exploring architectural design spaces via predictive modeling. In International Conference on Architectural Support P Programming Languages and Operating Systems, 2006.
James C. King. Symbolic execution and program testing. Commun. ACM, 19(7):385-394) 394, July 1976.
Bogdan Kustowski, Jim A. Gaffney, Brian K. Spears, Gemma J. Anderson, Jayaraman J. Thiagarajan, and Rushil Anirudh. Transfer learning as tool for reducing simulation bias: Application to inertial confinement fusion. IEEE Transactions Plasma Science, 2020),
Jihye Kwon and Luca Carloni. Transfer learning for design-space exploration with high-level synthesis. In ACM/IEEE Workshop on Machine Learning for CAD) 2020.
Lettier. 3d game shaders for beginners, 2019. / wtt.tttt....ccccco.c.ooo//// d- Baggammessl hadeerssshaersssee s- for beoo-bbeginers...
Charith Mendis, Cambridge Yang. Yewen Pu, Saman Amarasinghe, and Michael Carbin. Compiler auto-vectorization with imitation learning. In Advances in Neural Information Processing Systems, 2019.
10

---

Under review as conference paper at ICLR 2023
Andreas Munk, Adam Scibior, Atilmm Güneş Baydin, Andrew Stewart, Goran Fernlund, Anoush Poursartip, and Frank Wood. Deep probabilistic surrogate networks for universal simulator approxi- mation, 2019.
Flemming Nielson, Hanne Riis Nielson, and Chris Hankin. Principles of Program Analysis. Springer, 1999.
Raphaël Pestourie, Youssef Mroueh, Thanh V. Nguyen, Payel Das, and Steven G. Johnson. Active learning of deep surrogates for PDEs: application metasurface design. npj Computational Materials, 6(164), 2020.
Alex Renda, Yishen Chen, Charith Mendis, and Michael Carbin. Difftune: Optimizing epu simulator parameters with learned differentiable surrogates. In IEEE/ACM International Symposium on Microarchitectture, 2020.
Alex Renda, Yi Ding, and Michael Carbin. Programming with neural surrogates of programs. AMM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software (Onward!), 2021.
Adrian Sampson, Werner Dietl, Emily Fortuna, Danushen Gnanapragasam, Luis Ceze, and Dan Grossman. Enerj: Approximate data types for safe and general low-power computation. In Conference on Programming Language Design and Implementation, 2011.
Thomas J. Santner, Williams Brian J., and Notz William I. The Design and Analysis of Computer Experiments. Springer-Verlas 2nd edition, 2018.
Burr Settles. Active learning literature survey. Technical report, University of Department of Computer Sciences, 2009.
Dongdong She, Kexin Pei, D. Epstein, J. Yang. Baishakhi Ray, and Suman Jana. NEUZZ: Efficient fuzzing with neural program smoothing. In IEEE Symposium on Security and Privacy, 2019.
Natalya Tatarchuk. Advances in real-time rendering in 3d graphics and games, 2006. URL https: com.
//advances realt imerenddrrreeeeee
Hasan Tercan, Alexandro Guajardo, Julian Heinisch, Thomas Thiele, Christian Hopmann, and Tobias Meisen. Transfer-learning Bridging the gap between real and simulation data for machine learning in injection molding. CIRP Conference on Manufacturing Systems, 72, 2018.
Steven K. Thompson. Stratified Sampling, chapter 11, pp. 139-156. John Wiley & Sons, 2012.
Ethan Tseng, Felix Yu, Yuting Yang, Fahim Mannan, Karl St. Arnaud, Derek Nowrouzezahrai, Jean- François Lalonde, and Felix Heide. Hyperparameter optimization in black-box image processing using differentiable proxies. ACM Transactions on Graphics (Proc. SIGGRAPH), 38(4), 2019.
R. E. Wengert. A simple automatic derivative evaluation program. Commun. ACM, 7(8):633 464, August 1964.
Glynn Winskel. The Formal Semantics of Programming Languages: An Introduction. MIT Press, 1993.

---

Under review as conference paper at ICLR 2023
A
RELATED WORK
In this appendix we survey related work for each contribution.
A.1 OPTIMAL STRATIFIED SAMPLING
Optimal stratified sampling is classic area in statistics (Thompson, 2012). Most work in this domain focuses on optimal parameter estimation, and uses stratified sampling to reduce the variance of estimates by ensuring sufficient independent samples taken from each subpopulation. Our approach is novel in the assumptions we make for training stratified surrogates of programs, and in the specific sample complexity bounds we base our results on.
Santner et al. (2018) survey sampling techniques for computer experiments. Chapter 5.2.3 discusses stratified random sampling in particular, showing optimality criteria for sampling for unbiased esti- mators. These approaches are generic for minimizing the variance of estimators, and do not consider specifically training a neural network. These approaches also do not consider the different complexity of different strata.
Cortes al. (2019) present an active learning approach for learning in the regime where the input space is partitioned into separate regions (strata, using our terminology) and a separate hypothesis (surrogate) trained of each, and derive similar optimal of allocation of data points. This approach has two primary differences from our approach. First, it is an active learning approach that determines whether or not to query a label of given data point for an input stream of data points, whereas our approach operates offline. Second, it assumes a different form for sample complexity and derives correspondingly different optimal sampling bounds than ours. The definition of complexity (C in our formalism) that Cortes et al. use is a function of the number of hypotheses in the hypothesis class, the total number of data points used, and the number of data points for a given stratum that have been queried thus far. It is not a function of any complexity metric of the function being learned. Cortes et al. 's approach thus a better fit when learning stratified functions of unknown complexity (i.e., non- oon-analytic functions) using a finitely sized hypothesis class (not a neural network), and is targeted at the online setting when given a sampler the overall data distribution but not one for each stratum. Our approach is a better when learning stratified analytic functions with neural networks, and targeted the offline setting when given a sampler for each stratum.
A.2 SAMPLE COMPLEXITY PROGRAM ANALYSIS
Program analysis is a broad set of techniques to determine properties of programs (Nielson et al., 1999; Cousot & Cousot, 1977). Our analysis in Section 4.2 is novel nonstandard interpretation calculating the tilde, combined with a standard implementation of forward-mode automatic differentiation (Wengert, 1964; Griewank & Walther, 2008) and a standard symbolic execution which executes all paths in the program (King, 1976; Cadar et al., 2008).
Bao et al. (2012) present a program analysis that decomposes programs into continuous regions, with the goal of characterizing the sensitivity of each continuous region to input noise. This analysis computes a different notion of complexity than ours, and does not represent the sample complexity of learning surrogate of each region.
Hoffmann & Hofmann (2010) present a program analysis that calculates the algorithmic complexity of program. This complexity again does not lead to bounds on the sample complexity of learning surrogate of the program.
B ASSUMPTIONS
Our contributions in Sections and 4 make assumptions about the programs under study, the functions that those programs denote, and the surrogate training algorithms. Here we document these assumptions and note possible failure modes for our techniques.
Assumptions imported from prior work. Our sample complexity results are subject to all as- sumptions from the prior work that gives the sample complexity bounds for neural networks that
12

---

Under review as conference paper at ICLR 2023
use (Agarwala et al., 2021). These sample complexity bounds only apply to analytic functions. They further assume that imputs come from the unit sphere; this does not match many practical applications, including those in Section 5. Finally, these sample complexity bounds assume that the neural network under study is 2-layer, infinitely wide neural network trained with SGD with an infinitely small step size, using 1-Lipschitz loss function.
Despite these assumptions, Agarwala et al. (2021, Appendix B.2) empirically verify that the sample complexity bounds hold. We also show in Section 2 that the theoretical sample complexity bounds correlate with empirical sample complexity results on three functions.
Optimal sampling. The first assumption is that know the distribution of inputs ahead of time D(x), both in terms of the distribution of strata ((s;) and the distribution of inputs within given stratum ((r) st). The second assumption that optimizing the upper bound of the per-stratum loss results in reasonable optimum for the combined surrogate, The third is the technical assumption we make that == f; this is not guaranteed be optimal.
Program analysis. The main assumption here is that Agarwala et al. (2021)'s algebra on tilde functions results in sufficiently precise upper bound on the tilde. This not always the case for instance, this assumption says that ADD (x, NEG (x) has positive tilde (since the tilde of NEG (x) equal to the tilde of x), whereas it should have a tilde of
Stratified surrogates. We provide sample complexity bounds for constructing stratified surrogates, assuming that for a given program every path different function. This assumes both that is tractable to compute which stratum given input resides in before applying the surrogate. This also assumes that there are tractable number of paths, which excludes programs with large number statements or loops.
C PROOF OF OPTIMAL SAMPLING
This appendix provides the proof for the optimal sampling result in Section For convenience we duplicate the definitions of Icarnability. A learnable function is one such that:
L>D ee (TT(((()))) (f()))()))] Se 21-8
yDm,ee,..m Fn.
f.tr(F.D,m.f)
Following Arora al. (2019) and Agarwala et (2021) we study functions and learning algorithms for which the relationship between and d in Equation (1) is:
<()) 100+logg log (0))())))))))))
CCnSC
(2)
2²
The optimization problem of our optimal sampling approach
argmin {n.) { ENHaND (f()) s.t. En.sn and (r
(6)
Theorem 3.1. With 8, = _ the upper bound of Equation (3) is minimized at:
(D(s)) Hlggocc
n4: =
(D(si) (U) :
EE
Proof. The task to find n; for each surrogate f. that minimize the expectation of error and such that E,n, n. We first separate out the expectation by stratum, and upper bound the error using the sample
13

---

Under review as conference paper at ICLR 2023
complexity assuming for the surrogates:
((()),))((())]]
[(((W)))(())]
E
E (-((D()))
anD
D(alse))
[S(0))+
E (D(a))
-. n
[((U))+
Plugging in 6; and writing out the Lagrangian, we have:
c 2 ((((A)) = Cs ((f))+
+ _n-)
nm
L Cs ((fi) +log n4
-3 -
n
===
On,
0A
Σ
2/ ((s ((())+
n1
T1
n,
n Σ
(l1))+
2/11
A
1
p(s)jct
((())+
D(s:JCt
((())+
V 1o88
74
n1 = (D(si) ((f))+
(D(s:) +og
Because the objective is convex ny, this is the optimal solution.
D FULL TURACO SEMANTICS
This appendix presents the full semantics and analysis for TURACO. Figure 7 re-presents TURACO.
D.1 NORMAL EVALUATION SEMANTICS
Figure 8 presents the big-step evaluation relation for expressions TURACO. The expression relation (a,e) $ says that under variable store (assigning values to all variables in e), the expression evaluates to value v.
fun (x+) {s return
s:= |=:= lif (e () elss s)
sskip
e:=z v/ ((eee) u(e)
6: ADD MUL
U: um= NEG SIN EXP LOGIP
0:1 set of variable names
w:: of floating point values
Figure 7: Syntax of TURACO.
14

---

Under review as conference paper at ICLR 2023
(a,e) 4o
(a,e) to (o,SIN(e)) Usin(a)
(a.u) 4
(o
(o.NEG(c))4-o
(a,e) to (g.ExP(e)) (cxp(()
(o,e) -I<v51
(o,e1) (0,e2)
(oLLOGIP(e) (lgg(1+))
(1, (0,02)
(o,MUL(ee,e2)) 01.02
Figure Big-step evaluation relation for expressions in TURACO
(a,81) Vo'
(o' ,8,2 t0"
ote) dv
(o v>0 (a,81)
(0,81882)(0 10"
(o,il(e>0) (8) eole e { (x2)) fo
(o, 000 (0,82) fo,
(a,if(e>)) else {
82
Figure 9: Big-step evaluation relation for statements.
(o,s) Yo (a,fun (1...I {8) returnz)) (a(r)
Figure 10: Big-step evaluation relation for programs.
Figure presents the big-step evaluation relation for statements in TURACO. The statement relation (a,s) Vo says that under variable store a, the statement evaluates to new variable store o'.
Figure 10 presents the big-step evaluation relation for TURACO programs. The program relation (a,fun (I... {s return x) Y says that under variable store a (assigning values to all x;) the program evaluates value
D.2 COMPLEXITY ANALYSIS
Figure 11 presents the full complexity relation used calculate the complexity for all expressions. The relation (ō.(e) je]) (ū,6") says that under the variable complexity mapping ō (mapping variables to tuples with their respective tilde and tilde derivative), the expression e has ē 6 and غ' <
Figure 12 presents the complexity relation for statements. For statements, the relation (ā s.) Σ says that under the variable complexity mapping o the statement results in set of paths with variable complexity mappings E((p) for path p.
Figure 13 presents the complexity Ç (for given input 3 parameter) each path a program.
D.3 ANALYSIS CORRECTNESS
This appendix presents the statement of correctness for the TURACO complexity analysis. Theorem 1. Given:
Ço [uu (1o, (s return < (p
then for all paths Co(f) S Ep. where f is the function denoted by the standard execution of the path through s.
Proof.
The is by induction using Fact (p. 17) and Lemma (p.22) in At (202)). n
15

---

Under review as conference paper at ICLR 2023
(ā (6,0)
(ō,e) $ (0,0")
(0,0)
(o(z)
(o.NEG (6,0")
(G,SIN(e)) & (sinh(0) (i),,ccosh(i))
(..
(o.6)
Oj0<2
(epx)
(6.LOGI((e)) i loo((2 (0
(ū.
(0,62)
(.,0)) (ō,e2) (12,
((+ +i0y)
(), (8-02, i2. 00)
Figure 11: Complexity relation for expressions in TURACO
(8,
(2 4E"
(ō,91132) 133""
(0,51) (8.82) 5
(e>if(e>)) else {s2 i
E pe Σn uf ESr (p) p
Figure 12: Complexity relation for statements.
S.D (B.)) (z)
- Salfuu (f(x)) return { (1poo m/))) Eo
Figure 13: Complexity relation for full programs.
E EXTENDED RENDERER DEMONSTRATION
This appendix provides further details on the evaluation on the renderer program in Section 5.
Figure 18 presents the full code for the renderer program under study. 7 Figure 14 presents the full set of scenes used in our evaluation.
This program is good candidate to train a surrogate of for several reasons. First, it an approximable program: as long as the outputs of surrogate of the program are sufficiently close to the ground-truth outputs, the generated image will perceptually indistinguishable. Second, its paths are all determined by uniform input variables, variables in GLSL that are constant across each invocation of the shader. This means that relative to cost of executing the program, it cheap to determine which path a given input induces in the program (and thus which surrogate to apply). Third, its execution environment well suited to be replaced with a neural network, since the original program itself performs batch processing GPU,
E.
PATHS
Table 3 presents statistics about the entire set of paths paths under study.
Figure 16 presents bideeb comparison of traces of two paths: irrlrl (twilight smoke), the least complex path in the dataset, and irrrır (nighttime solids), the most complex path in the dataset.
"The original program is written in GL SL. We present a semantically equivalent translation (preserving all paths) of the program TURACO for simplicity of presentation.
16

---

Under review conference paper at ICLR 2023
(a) Front-day scene.
(b) Front-night scene.
Koudy
(c) dap-day scene.
(d) Top-night seene.
Figure 14: Ground-truth scenes generated by the renderer.
(a) Water path.
(b) Smoke path.
(c) Solids path.
Figure 15: Daytime scene with each different path highlighted red, and all others black.
Two factors lead to the twilight smoke path being less complex than the nighttime solids path. First, the twilight smoke path computes one lighting factor from constant (Figure 16a, line 14) rather than from function of the sun's 's position (Figure 16b, lines 13-. Second, the twilight smoke path does not have any specular output (Figure 66,, line 18), unlike the nighttime solid output (Figure 16b, line 18).
Figure 15 shows side-by-side comparisons of the three classes of paths: water, smoke, and solids. In each of these images, one path returns red for all pixels. while the other paths return black for all pixels. The base scene is the front daytime scene in Figure 19a.
17

---

Under review as conference paper at ICLR 2023
Table 3: Top:
the identifier, lines of code, complexity, and description of each path present in our datasets. Bottom: the distribution (abbreviated distr.) of each path across each dataset: the frequency (freq.) of each observed path, and the optimal sampling rate (opt.) of that path.
Path
Irrlir
Irrirl
Irrler
Irrrlr
Irrrrl
Irrrrr
rrrllr
rerlel
rrrler
Lines Code
17
17
18
17
17
Complexity
6210
6369
6328
6814
6459
6142
6621
Twilight
Twilight
Twilight
Nighttime
Nighttime
Nighttime
Daytime
Daytime
Daytime
Description
Water
Smoke
Solids
Water
Smoke
Solids
Water
Smoke
Solids
Dataset
Distr.
Irrlir
Irrlrr
Irrrl
Irrrrr
rrellr
rrrler
Front Day
Freq.
5.0%
7.9%
87.1%
Opt.
11.0%
14.7%
74.4%
Front Night
Frey.
5.0%
7.9%
51.4%
35.6%
Opt.
9.3%
12.4%
44.1%
34.2%
Top Day
Frey.
6.7%
13.1%
80.1
Opt.
12.8%
19.7%
67.4%
Top Night
Freq.
0.16%
0.066
1.2%
0.3%
0.1%
2.4%
6.3%
12.9%
76.5%
Opt.
0.95%
3.6%
0.8%
10.9%
17.4%
58.4
Front
Freq.
2,5%
4.0%
2.5%
61.4%
Opt.
5.6%
7.5%
26.7%
5.5%
7,4%
47.2%
Top
Freg. Opl.
0.08% 0.62%
0.03%
0.65/
0.2%
0.1%
1.2%
6.5%
13.0%
78.3%
0.32%
2.4%
1.0%
0.5%
3.8%
11.6%
18.2%
61.5%
Day
Freq.
5.9%
10.5%
83.6%
Opt.
11.9%
17.3%
70.7%
Night
Freq. Opt. 0.53%
0.08%
0.03%
0.6%
2.7%
4.0%
26.9%
3.1%
6.5%
$6.1
2.0%
7.2%
6.1%
42.3%
All
Freq. 0.04%
0.02%
0.3%
1.3%
2.0%
4.5%
69.8%
Opt.
0.35%
0.18%
1.3%
3.7%
4.8%
17.4%
8.2%
12.4%
51.6%
fun (...)
fun (...)
suunosstionn mul( sunPosition [0], < mpl 0.0055556)))
sunPosition sin muul sunPosition [0].
mul pi 0.0055556))
14
SunPositionPow = wtwp::/wwww...ooooooaaoaaaaooaaa -1.0), 0.4)
15 emission malcmmision 0.1)
15 emicsion :- mu (emiscion, sunFositisnFow)
16 outürgb add emission)
16 outürgb
add
emission)
outOa := diffaseCnlor
outfa diffuse
18 ouila := diffuxeColor
18 outla == diffuseColor
outl:gb:1000000000
outizab [szeculat(0), spsculartiiiiii specuaas
20 return (outOrgb. outOa, outlrgb. outla)
20
return (outOrgb. outda, outlrgb, outla)
(a) Twilight smoke (1rrl trace.
(b) Nighttime solids (Iererr) trace.
Figure 16: Side-by-side comparison of the trace of the least complex path (Irrirl: twilight smoke) and that of the most complex path (1 (irrrrr: nighttime solids), with differences highlighted.
E.2 ARCHITECTURE AND HYPERPARAMETER DETAILS
For the design of each surrogate, units and ReLU activations. This architecture matches that of Agarwala et al. (2021), except using 512 rather than 1000 hidden units (we found that the accuracy of each path surrogate plateaued by 512 hidden units). We train the surrogate using the Adam optimizer with a learning rate of 0.0001 and a batch size of 256 for 50,000 steps. We 5 trials of all experiments, and report the mean error.
simple MLP architecture with single hidden layer of 512
E.3
FULL RESULTS
Figure presents the error of surrogates on each dataset. Each plot shows the error for a different dataset. Each plot has three different lines, respectively showing the error of each surrogate training saaueeccy-bssede and uniform). Each x axis the total training data budget. Each
distribution (optimal, y axis is the error of the resulting stratified surrogate.
18

---

Under review conference paper at ICLR 2023
Surrugate Error (Test Path Distribution)
Front Day
Front Night
Top Day
Optimal Frequency
10-3
10-3.
Error
10-4
Uniform
10
10-6
10a
10a
10a
10
10a
10a
10a
10
10
10
10
10
10a
10
Top Night
Front
Тoр
10
10-1
10-3.
Brror
10-4
10-4
10-5
10
10
10
10
109
10
10
10
10a
10a
10
10
10
10P
10
10
10
Day
Night
All
10
10-1
10-3
Errur
10
10-1
10-5
10a
10a
10a
10
10
10"
10a
10a
10a
104
10
10
10
10
102
10
102 10"
Number of Data Points
Number of Data Points
Number of Data Points
Figure 17: Errors of stratified surrogates of each dataset.
Figures 19 and 20 present larger versions of the renders in Section 5.4 for ease of comparison. The training budgets for these surrogates are 61 samples for the front-day surrogate and 206 samples for the top-night surrogate.
19

---

Under review conference paper at ICLR 2023
fun (rimlightt [4], IsCelShadnngnnaheeed22 [2]] sunPosition [2], gamma
worldNormal [3]. ssao [3]o diffuseColor(4), diffuse [4]. specular (4].
emission [3]. is is isParticle
(2]) i
sunPositon sin (mul (uuoosxtioio [0], mul 0.0055556)))
sunMixFactor (0.5. neg (mul( sunPosition 0.5)))
ambie exp(mul (log (add ((0.302. 0.451. 0.471). -1))
gamma
ambientWarmBan exp (log (add ((0.765, 0.573, 0.400), -1))
gamma )
if (0.5 sunMixFactor) ambientCool mul mbientCColBase,, 0.5)
ambientWarm mul ambientWarmBase, 0.5)
clse {
11
ambieniCool mul (ambientCoolBase, sunMixFactor)
12
ambientWarm mul (ambientWarmBase, sunMixFactor)
13
14
15
if (0 MuntoxFactorr
16
skyLight ambientCool
17
groundLight ambientWarm
18
} clse {
19
if (sunMixFactor
20
skyLight ambientWarm
21
groundLight ambientCool
22
else {
23
skyLight add mul (ambientCooo) add(1, neg (eg(sunMix(actor)))
9 mul ambien sunMixFactor))
24
groundLight add mul (ambien arrm. ad neg(sunMixxFactor))
4 mul ambientCool, sunMixFactor))
25
26
27
28
worldNormal = mul (0.55 ad. worldNormal )21))
29
ambientLight = (mul (groundLight add
+ mul (skyLight, wortdNoomallMixFactoo/
30
ambient = mul ambientl.ight, mul (( diffuse [0], diffuseColor []],
4 diffuseColor (2]) ssao))
31
if (0.00316228 > sunPosition). emission = mul(emission, 0.1)
32
33
} else {
34
sunPositionPow (mul (log (add sunPosition. -1)) 0.4))
35
emission = (emisssin,, sunPositionPow)
36
37
38
outürgh = add (add (( ((ambient [0], ambient ambient [2]), (diffuse [0],
diffuse [[], diffuse (2])), (rd((riiiighht()), rimlight[1],
rimLight(2)) (2)). emission))
39
40
(is > 0) {
41
out0a
42
clse
43
outOa liffuseColor
44
45
outla diffuseColor [3]
46
47
if (isParticle 0)
48
outlrgb (0.0.0)
49
clse {
50
outlrgb (specular [0]. (pecular specular (2))
51
52
(outOrgb. outOa, outlrgb. outla)
Figure 18: Full code for the renderer case study.
20

---

Under review conference paper at ICLR 2023
(a) Ground truth front-day scene.
(b) Optimal surrogate front-day scene.
Kaudy
(c) Frequency surrogate front-day seene.
(d) Uniform surrogate front-day scene,
Figure 19: Front-day scene (ground truth in the top left; surrogates others).
21

---

Under review as conference paper at ICLR 2023
Ground truth top-night scene.
(b) Optimal surrogate top-night scene.
Kaudy
Foudf
(c) Frequency surrogate top-night seene.
(d) Uniform surrogate top-night scene.
Figure 20: Top-night scene (ground truth the top left; surrogates from the "all" dataset in others).
22


Reviews:
[{"review_id": "qPIAmoy6dtb", "reviewer": "Reviewer_RLWc", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper presents a methodology to optimally sample datasets to train neural\nnetwork based surrogates of programs written in Turaco, a programming language\nintroduced by the authors. The programs are represented as stratified functions,\nwhich are functions that behave differently in different regions (strata) of the\ninput space (these correspond to different traces of the program according to\nthe branches chosen during execution). An independent neural network surrogate\nis trained for each strata. The question the paper tackles is how to sample the\ndataset to train these networks, that is, given a budget of how many samples we\nhave, how many samples to allocate to the training of each strata.\n\nThe authors determine the optimal number of samples $n_i$ for the strata by\nminimizing the upper bound of the error of the learned stratified surrogate of\nthe stratified function, with the constraint that the sum of the number of\nsamples must be equal to the budget (Theorem 3.1).\n\nTo compute the number of samples using this theorem, the complexity of the\ncomponent functions $\\zeta(f_i)$ is required. To this end, the authors introduce\na programming language called Turaco, in which all programs denote learnable\nstratified functions. They also provide the semantics and a complexity analysis\nfor the language which makes it possible to calculate an upper bound on the\ncomplexity of traces $\\zeta$, and so the number of samples $n_i$.\n\nThe theoretical results are verified empirically on a 60 line shader program\nwhich is part of a larger 3D renderer. The authors find considerable reductions\nin error compared to the baselines of uniform and frequency-based sampling.\n", "summary_of_the_review": "Overall I found the paper to be a significant contribution, well-written, and\nconvincing. Reproducibility is a concern, but that could be easily addressed.\n\nI did not verify the proofs in the Appendix.\n\n------------------------------------------------------------------------------\n\nUpdate:\n\nSimilarly to reviewer #2, I read the comments of reviewer #1 and their\ndiscussion with the authors. I agree with reviewer #1's points that calling the\nmethod \"optimal sampling\" and the method converging to uniform sampling are\nsignificant issues, so I'm decreasing my score.\n", "strength_and_weaknesses": "\n### Strengths\n\nThe paper presents a solid theoretical analysis with proofs, which is also\nverified empirically on a real-world program.\n\n### Weaknesses and Questions\n\nThe paper works with upper bounds both for Theorem 3.1 and when determining the\ncomplexity of a trace of the program, so we substitute upper bounds of the\ncomplexities of traces into an estimate arrived by minimizing the upper bound of\nthe error. Even though the authors present empirically verified gains compared\nto the baselines, it would be good to know something about how tight these\nbounds are.\n\nThe complexities of the traces in Table 1 are very similar to each other in\nmagnitude, probably because the branches in the program don't differ that much\nin complexity. It would be good to see a program where the complexities are more\nskewed. The path frequencies are the opposite of this: they are very skewed\ntowards rrrlrr (the rightmost one). Here it would be good to see a less skewed\ndistribution.\n\nThe Turaco programming language lacks iterative constructs like loops or\nrecursion, which is very important for programming. Could they also be included,\nand how difficult would it be?\n\nI think that the original C++ code of the shader (for which there is a GitHub\nlink on page 7) should be included in the Appendix as it may change on GitHub.\n\nThe captions of Table 1 and 2 should be below the tables.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "kNL930FXA0f", "reviewer": "Reviewer_mndd", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes improved sampling for training program surrogates. The proposed sampling scheme takes into account both data distribution and sample complexity of different paths. A language suitable for application of the proposed sampling scheme is introduced, and the scheme is evaluated on a graphics program.", "summary_of_the_review": "The paper addresses an interesting topic but does not stand by publication standards. ", "strength_and_weaknesses": "Strengths: the paper takes a more thorough approach than earlier works to distribution of samples for training program surrogates. Theoretical error bounds are used to derive practical sample distribution rules. The results are empirically supported.\n\nWeaknesses: the paper has many technical inconsistencies which impair significantly my trust in the presented results.\n\nFirst, the phrase 'optimal sampling' is used through the paper, including formal statements, while it is clear that the sample distribution is based on theoretical error bounds, which are not tight, and has sampling is not 'optimal'.\n\nSecond, the proof, provided in the appendix, of the central theorem of the paper, 3.1, contains errors. 1) the derivative of the 'Lagrangian' is wrong, the derivative of n^{-1/2} is -1/2n^{-3/2} rather than 1/2n^{-3/2} (the minus is omitted). 2) the last line is obviously wrong. 3) this is not a proof of constrained optimization but rather a sketch of it, for a normal proof one has to show that the zero-gradient point is indeed the minimum (it does not have to be). \n\nThird, the formula in Theorem 3.1 has a paradoxical property --- as the number c of strata/branches increases, their relative complexity affects 'optimal' sample distribution less and less. I am not convinced that this is indeed 'optimal' behavior rather than an artifact of a particular form of upper bound used for the proof (and more suitable for theoretical analysis than for practical sampling). This should at least be discussed.\n\nFourth, there is no supplementary material, so one cannot reproduce the results, or even look at the source code. The only artifact of the empirical evaluation is the 'full code' of the renderer case study in Figure 18, which is a single function written in a version of Turaco different from introduced in the paper. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "hVNjjosbBXc", "reviewer": "Reviewer_E5p2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper is concerned with the problem of developing surrogates of programs. A major difficulty in this context is how train surrogates for programs with control flow. To overcome this challenge, this paper represents the program as a stratified function and uses stratified surrogates to model such functions. To ensure the training accuracy, an optimal allocation approach allocating different number of training samples by considering the complexity of the different paths of the program is proposed. A new programming language is presented to realize the proposed method. Finally, a demonstration 3D renderer is used for case study to verify the effectiveness of the proposed method.", "summary_of_the_review": "This paper is well written in general, and the simulation is nice.\nThe contribution is interesting and enough, but the method seems not very novel.\nThe motivation for the presented programming language should be improved.  \n\n---------------------------------\nAfter reading reviewer #1's comments and discussions, I tend to decrease the score. Although interesting, the paper seems not very rigorous in defining \"optimal sampling\", \"formulation\", and the contributions of the paper seem not significant.", "strength_and_weaknesses": "Strength: \nThe authors proposed an optimal allocation approach, which allocates different number of samples by considering different complexity of the path in the program.\nIn addition, they also presented a new programming language to realize the proposed method.\n\n\nMajor comments:\nPage 2 \"Opitmal sampling\". The authors mentioned that \"Using neural network sample complexity bounds for learning analytic functions\". The reviewer is wondering are there other complex bounds that can be used to learn analytic functions? If so, what are the differences between these bounds, and why did the authors choose this bound?\n\nPage 3 \"Optimal path sampling\". The authors mentioned that \"Using this bound (as implemented by our TURACO analysis described in Section 4.2), we determine that the twilight path takes 1.5× as many samples to train a surrogate to a given error as the nighttime path, and the daytime path requires5× as many samples.\" The reviewer is confused about this result. The frequency of these three paths is in the order: nighttime>daytime>twilight, but the complexity order is: nighttime <  twilight <  daytime. Could you explain how this happened?\n\nPage 4, Figure 2 (b). It seems that when the total data size is small (around 10^1) the error decreases faster under the frequency sampling. Could you provide a possible reason for this?\n\nPage 4, \"Training methodology\".  Is the proposed method sensitive to these parameters?  How do these parameters influence the result?\n\nPage 4, Section 3 \"A given function f is probably approximately correctly learnable...\". Please provide the definition of \"probably approximately correctly learnable\".\n\nPage 6. \"For a 2-layer neural network trained with stochastic gradient descent...\" Instead of stochastic gradient decent, can other methods be used?\n\nPage 6, section 4. The motivation to create this new language \"TuARO\" is not clear. Specifically, why not use other existing languages, e.g. C++, python? Compared with these existing languages, what are the advantages of the presented language? \n\nPage 12, A1. Could you please list the pros and cons of your offline method compared with the online method in Coetes et al (2019)? In addition, could you explain how the different choice on the sample complexity affects the result?\n\nPage 13 \"Optimal sampling\". It is suggested that the restrictiveness of the assumptions should be discussed.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject