Asymptotic optimality of adaptive importance sampling
Adaptive importance sampling (AIS) uses past samples to update the sampling policy q t . Each stage t is formed with two steps : (i) to explore the space with n t points according to q t and (ii) to exploit the current amount of information to update the sampling policy. The very fundamental question raised in this paper concerns the behavior of empirical sums based on AIS. Without making any assumption on the allocation policy n t , the theory developed involves no restriction on the split of computational resources between the explore (i) and the exploit (ii) step. It is shown that AIS is asymptotically optimal : the asymptotic behavior of AIS is the same as some "oracle" strategy that knows the targeted sampling policy from the beginning. From a practical perspective, weighted AIS is introduced, a new method that allows to forget poor samples from early stages.
In this manuscript the authors consider adaptive importance sampling (AIS) schemes for estimating the integral of some target function \phi. To estimate such an integral a probability distribution (called sampling policy) generates an i.i.d. data sample and the integral is estimated by the empirical average of the function \phi weighted by the sampling policy. The key ingredient in adaptive sampling is to do multiple iterations of this procedure, updating the sampling procedure between each iteration to optimize the estimation.  The authors point to many convergence results regarding AIS but stress that these are in the case where the number of iterations is fixed while the number of samples taken per iteration goes to infinity. They argue that a more natural and general setting is where the total number of samples of all iterations goes to infinity, which includes the previous case as well as the case where the sample size per iteration stays fixed but the total number of iterations tends to infinity. In this setting the authors use Martingale techniques to prove a central limit theorem for both standard and normalized AIS. Both results are independent of the exact update strategy.   Next the authors consider a specific class of sampling policies, where the sampling policy is picked from a parametrized set. They prove that under certain mild assumptions, by applying risk minimization one obtains a collection of sampling policies that will converge to the optimal sampling policy. From this they then deduce a central limit theorem for parametric sampling policies, using risk minimization. Finally, a weighted update scheme for sampling policies is introduced. The weights enable the exclusion of previous bad updates when sampling the new data points. Using numerical experiments the authors show that such weighted AIS perform very well in practice as well as display their results for AIS. This paper is well-written with a clear overall structure, well defined objects and clearly stated results. In particular, I appreciate the fact that the authors make specific reference to the exact results from other papers they use for their proofs, which make the proof checking so much easier. I agree with the authors that the setting where the total number of samples tends to infinity is much more natural and hence I think their results are significant. I do however have a small problem with the proof of Theorem 5, since it assumes independence between variables U_i and U_j which does not seem to hold. In addition, I felt that the section on experiments was a bit short, which makes it hard for other researchers to duplicate the results. Apart from these two point I only have some small comments which I have listed below.  In summary, I think the result on adaptive importance sampling presented in this paper are relevant and new, and the numerical experiments clearly show that weighted AIS could improve estimations. Therefore I would recommend this paper for acceptance in NIPS. ADDED AFTER FEEDBACK: My main concern regarding the proof of Theorem 5 was properly addressed and the authors agreed to improve/expand the experiments section. My overall recommendation regarding this paper remains unchanged. Comments main text: Line 1, [policy of stage t]: Within the first six words you introduce a variable that is not defined. Please consider changing the text to be more high level. Line 8, [raised in the paper]: I would change this to: raised in this paper. Line 17, [choice of the sampling…]: I would write: choice of a sampling… Algorithm (AIS): This is just an abstract representation of an AIS scheme, since no explicit update scheme is provided. I would be helpful to the reader if this was stated explicitly in the text. Line 57, [is there a weighted…]: I would change this to: is then a weighted. Line 61, [based on parametric]: I would write: based on a parametric. Line 82, [inspired from the]: I would change this to: inspired by the. Algorithm AIS at sample scale: Again, this seems to be an abstract algorithm. Please specify this in the text. The for loop refers to i but the index in the rest of the algorithm is j. Which one is it? Also, you explain what x_j is but what about q_{j-1}? Line 106: Here you use I without ever specifying that it is \int \phi, which creates confusion with the reader. Please define this. Proposition 1 and 2: Given the short proofs and the fact that these are just simple technical statements I would recommend merging these into one lemma. Line 118: It would help the reader if you recall that \phi maps into \mathbb{R}^p. Line 130: I do not understand what you mean with the part: \int \phi \pi, not \int \phi. Could you explain this a bit more. Line 140: What does (\phi \pi, \pi) stand for? I thought we only needed to replace \phi with \phi \pi in (4) and (5). Section 3: Here there is a huge jump with respect to the previous part. In particular, \theta_t is never defined not mentioned in the previous text. This makes it very difficult for the reader to digest this part. Please provide a bit more introduction here. Expression below line 156: I thought we were using parametric sampling policies q_{\theta}. How are the q_{s-1} related to these? This is particularly important since they appear again in equation (10). Line 161: Here there is a typo, compute twice. Line 179-180: The expression given her for R_t(\theta) seems to be exactly the same as (10). Line 208: Please remind the reader that V(q,\phi) is defined as in (3). Line 230: How do (8) and (9) work in practice? I thought we did not know q^\ast. Could you please add more explanation so that other researcher can reproduce these experiments. Comments supplementary material: Line 13, [using (4)]: Please be explicit when referring to equations in the main text to avoid unnecessary confusion. Also it might help to provide a bit more details on the use of Cesaro, for instance state that a_n = \sum_{j = 1}^n (V(q_j,\phi) - V_\ast) and b_n = n. Derivation below line 18: At the end of the first line there should be absolute value bars around \frac{\phi(x)}{q_{j-1}(x)}. In addition the equation sign on the next line should be a \leq sign. Line 24, [apply Theorem 1]: This is very confusing since the main text contains no Theorem 1. Please be very specific that you are referring to results that you will discuss later in this text. Line 25-26, [(H1)…(H2)]: Similar to the above comment, please be very specific that both these refer to statement that appear later in the text. Or preferably, move section 2.2 before the proof of Theorem 5. Derivation below line 31: Here it seems that something is going wrong. The first equality sign is only true when U_i and U_j are independent, which I do not think they are since they involve the updated versions of the sampling policy which depends on previous samples.  Theorem 2: I do not follow the proof, especially the use of the n^2. From the fact that Var(S_n) \le cn it immediately follows that E[(\frac{S_n – E[S_n]}{n})^2] goes to zero as n \to \infty. This then immediately implies concentration and hence the result. Also, given that this result is fairly straightforward, I would recommend changing this to a lemma.