Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 1: strong reject
review_content: 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.
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.

Weaknesses: the paper has many technical inconsistencies which impair significantly my trust in the presented results.

First, 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'.

Second, 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). 

Third, 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.

Fourth, 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. 
clarity,_quality,_novelty_and_reproducibility: The paper has inconsistencies, certain things are used before they are introduced (e.g. the language for the didactic example in figure 1). I do not see an easy way to attempt to reproduce the results presented in the paper.
summary_of_the_review: The paper addresses an interesting topic but does not stand by publication standards.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: 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.
strength_and_weaknesses: Strength: 
The authors proposed an optimal allocation approach, which allocates different number of samples by considering different complexity of the path in the program.
In addition, they also presented a new programming language to realize the proposed method.


Major comments:
Page 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?

Page 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?

Page 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?

Page 4, "Training methodology".  Is the proposed method sensitive to these parameters?  How do these parameters influence the result?

Page 4, Section 3 "A given function f is probably approximately correctly learnable...". Please provide the definition of "probably approximately correctly learnable".

Page 6. "For a 2-layer neural network trained with stochastic gradient descent..." Instead of stochastic gradient decent, can other methods be used?

Page 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? 

Page 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?

Page 13 "Optimal sampling". It is suggested that the restrictiveness of the assumptions should be discussed.
clarity,_quality,_novelty_and_reproducibility: Clarity: The paper is mostly clear, well-written, and easy to follow.

Quality: The quality of this paper looks reasonable and they achieve more accurate surrogates than existing works.

Novelty: The novelty of the proposed approach is medium. But they present a new programming language, which is quite novel.

Reproducibility: The author has uploaded their code in the github, so this work is reproducibility.
summary_of_the_review: This paper is well written in general, and the simulation is nice.
The contribution is interesting and enough, but the method seems not very novel.
The motivation for the presented programming language should be improved.  

---------------------------------
After 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.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper presents a methodology to optimally sample datasets to train neural
network based surrogates of programs written in Turaco, a programming language
introduced by the authors. The programs are represented as stratified functions,
which are functions that behave differently in different regions (strata) of the
input space (these correspond to different traces of the program according to
the branches chosen during execution). An independent neural network surrogate
is trained for each strata. The question the paper tackles is how to sample the
dataset to train these networks, that is, given a budget of how many samples we
have, how many samples to allocate to the training of each strata.

The authors determine the optimal number of samples $n_i$ for the strata by
minimizing the upper bound of the error of the learned stratified surrogate of
the stratified function, with the constraint that the sum of the number of
samples must be equal to the budget (Theorem 3.1).

To compute the number of samples using this theorem, the complexity of the
component functions $\zeta(f_i)$ is required. To this end, the authors introduce
a programming language called Turaco, in which all programs denote learnable
stratified functions. They also provide the semantics and a complexity analysis
for the language which makes it possible to calculate an upper bound on the
complexity of traces $\zeta$, and so the number of samples $n_i$.

The theoretical results are verified empirically on a 60 line shader program
which is part of a larger 3D renderer. The authors find considerable reductions
in error compared to the baselines of uniform and frequency-based sampling.

strength_and_weaknesses: 
### Strengths

The paper presents a solid theoretical analysis with proofs, which is also
verified empirically on a real-world program.

### Weaknesses and Questions

The paper works with upper bounds both for Theorem 3.1 and when determining the
complexity of a trace of the program, so we substitute upper bounds of the
complexities of traces into an estimate arrived by minimizing the upper bound of
the error. Even though the authors present empirically verified gains compared
to the baselines, it would be good to know something about how tight these
bounds are.

The complexities of the traces in Table 1 are very similar to each other in
magnitude, probably because the branches in the program don't differ that much
in complexity. It would be good to see a program where the complexities are more
skewed. The path frequencies are the opposite of this: they are very skewed
towards rrrlrr (the rightmost one). Here it would be good to see a less skewed
distribution.

The Turaco programming language lacks iterative constructs like loops or
recursion, which is very important for programming. Could they also be included,
and how difficult would it be?

I think that the original C++ code of the shader (for which there is a GitHub
link on page 7) should be included in the Appendix as it may change on GitHub.

The captions of Table 1 and 2 should be below the tables.
clarity,_quality,_novelty_and_reproducibility: 
### Clarity

The paper is well-written and fairly easy to follow despite the many different
elements of the topic which are combined. Section 2 with the example is
especially helpful.

### Quality

I found the paper to be of high quality.

### Novelty

The paper has novel and interesting results, and it addresses novelty directly
in Appendix B.

### Reproducibility

This is a concern for the paper. I believe that in order for the results to be
reproducible, the implementations of the Turaco programming language and the
methodology to compute the complexity bounds of the traces should be made
public.

summary_of_the_review: Overall I found the paper to be a significant contribution, well-written, and
convincing. Reproducibility is a concern, but that could be easily addressed.

I did not verify the proofs in the Appendix.

------------------------------------------------------------------------------

Update:

Similarly to reviewer #2, I read the comments of reviewer #1 and their
discussion with the authors. I agree with reviewer #1's points that calling the
method "optimal sampling" and the method converging to uniform sampling are
significant issues, so I'm decreasing my score.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper was a borderline paper which led to quite extensive discussion among the reviewers (and was selected for a virtual meeting). The initial scores from the three reviewers were 8/8/1, obviously representing a fairly severe divergence. The negative review identified a few technical errors; these were largely addressed by the authors in their update and in the rebuttal. However, this kicked off a broader discussion among the reviewers regarding the relevance of the theory. Ultimately the consensus was that the revised paper represented a "major revision", which would be best served by a fresh round of review at the next appropriate conference. More details are in the summary of the AC-reviewer meeting below.
justification_for_why_not_higher_score: There were sufficient concerns from the reviewers that they felt the paper deserved a revision with a full new round of review.
Decision: Reject