NeurIPS 2020

### Review 1

Summary and Contributions: The paper investigates the use of adaptive importance sampling in the stochastic gradient descent algorithm for empirical risk type of functions. It focuses on the expected dynamic regret with decreasing step-size. The paper is mainly methodological and the contributions are: - a novel algorithm and its theoretical study regarding the dynamic regret - a variant of their algorithm with mini-batch estimates - some numerical experiments

Strengths: (S1) - The use of an adaptive strategy with decreasing steps for the analysis of dynamic regret seems relatively new. (S2) - Some work has been done to propose an efficient algorithm.

Correctness: (C1) - Appendix of Lemma 2, line.504 : The constant in the third line is a G squared and not a G as written. This has to be changed, as well as the results that follow from this lemma. The empirical methodology is not convincing enough: (C2) - The numerical details of the experiments are not sufficiently specified (number of simulations, etc.). (C3) - There is a lack of comparisons between constant and adaptive steps to measure the performance of the proposed approach. (C4) - There is no experiment showing the impact of a different batch size or strong convexity.

Clarity: The paper is readable but it suffers from a lack of clarity that increases as it is read: (CL1) - The mention of SGLD, which seems important from the beginning of the paper, is not studied in the experiments and does not bring much to the paper. (CL2) - The very definition of dynamic regret does not make clear the dependence on the past. It would be helpful to clarify this as in Equation (3) of . (CL3) - Subsection 3.3 would probably be more appropriate in the form of an algorithm or pseudo-code. (CL4) - The different assumptions in section 4 are listed one after the other and it would be more pleasant to have some comments and discussions between each one to better appreciate their links. In particular the authors should discuss the links of assumption 3 and the different path-length assumptions in the literature (mentioned in section 2.2 of ) (CL5)- Section 6 on numerical experiments needs to be reviewed (see previous remark W3)

Relation to Prior Work: Section 2 discusses in depth past work on online learning problems in the study of static or dynamic regret. The authors are inspired by the approach of  and show a similar bound for dynamic regret with a complexity in O(T^{2/3}). It would be a good idea to discuss the different assumptions related to assumption 3 about the behaviour of the trajectory, as this assumption about the path-length is the key to the whole analysis. A huge litterature about sampling gradients is given by the authors in the introduction ( to ). It is claimed that they are not concerned with any regret analysis but are the methods developed in these references really different from the proposal of the authors. More generally the authors should take care of differentiating their methodological contribution form their theoretical contribution.

Reproducibility: Yes

Additional Feedback: The framework of the paper is asymptotic. In the mean time, the assumptions on the decrease of the step sizes is stated with constants which then contaminates heavily the proofs and statements. This is not realy logic and I suggest to define the step size at 1 / t^delta (starting with t = 1) or A/t^delta. However, if a constant is introduce, then I suggest to add a discussion around its choice/meaning. Below Lemma 3, a confusing discussion takes place about a positive and negative term. It is difficult the understand the presentation choice of the authors regarding Assumption 3 and Proposition 1 (which is trivial). Assumption 3 is valid under the framework of the authors hence useless. If the authors want some gain in the generality of their resutls then it should be more carefully explained. The links with (strong) convexity are not sufficiently discussed. In , an important discussion on convexity is addressed and it would be interesting to see where the article fits in this literature. typo line 27 : «approach to achieving » → « approach to achieve » typo line 504 (appendix) : a square appears in a development but should not I encourage the authors to write a new version that would take into consideration my recommendations. [After Rebuttal] I would like to thank the authors for the detailed answer concerning their contributions. As the contribution of the authors appears now more clear to me and seems sufficiently significant (looking at the other reviewers coments), I changed my evaluation accordingly (+1). I still have some concerns about the mathematics of the paper which, from my point of view, are not well educated. For this reason, my final score is 5.

### Review 2

Summary and Contributions: This paper provides a new method for importance sampling of examples to use when picking minibatches for SGD. At the t^th iterate, the minibatch is sampled (without replacement) from a sampling distribution p_t over the dataset. A new algorithm is given that leverages the dynamics of SGD to produce sampling distributions p_1,...,p_T for which the sum of the variances estimated gradients is with an additive O(T^{2/3}) of the sum of the variances for the estimates gradients obtainable using the optimal sequence of distributions p_1*,..,p_T^* (i.e. the dynamic regret is O( T^{2/3} ). The technique is pleasingly simple: the algorithm remembers the last observed gradient for each example in the dataset and uses this to construct an estimate of the variance as a function of p_t at the t^th iterate. Many of the last observed gradients are “stale”, but since SGD has decreasing learning rates they cannot be too stale. The algorithm then simple returns the minimizing distribution for this estimate, subject to some minimum weight assigned to each example.

Strengths: The idea and analysis here seem clean and intuitive, and get around several difficulties in past works (e.g. unbounded gradients estimated from bandit information). Getting good dynamic regret is impressive.

Weaknesses: My main concern is that I am not sure how to translate this result into an improved bound for the final optimization algorithm. Is there some realistic scenario in which we can quantify how helpful using this adaptive importance sampling scheme will be vs just uniform samples? Especially given that it looks like each iteration of the importance sampler takes O(N) time and the algorithm requires O(N) memory, I am concerned that I could do better by just doing O(N) iterations of regular SGD with uniform sampling, which takes the same amount of time and less memory. ---- The rebuttal gives me more confidence in the iteration complexity of the algorithm, so I raise my score by one point.

Correctness: The claims seem correct, but I may have missed some details in the appendix.

Clarity: yes

Relation to Prior Work: yes

Reproducibility: Yes

### Review 3

Summary and Contributions: The paper proposes an importance sampling strategy for finite sum optimization with decreasing stepsize. The motivation of importance sampling is to reduce the variance of (mini-batch) SGD and the proposed method achieves this in an implementation efficient way. Several aspects of the algorithm are discusses. From a theoretical side the authors show that the algorithm achieves sub-linear dynamic regret (while prior work focused on static regret). And they propose a new unbiased gradient estimator that is compatible with sampling without replacement which is particularly efficient for the proposed method. From a practical side the authors discuss implementation challenges and give pseudo code for the proposed algorithm. Finally, empirical results show the potential of importance sampling on real datasets.

Strengths: I think it is a nice, well written and quite complete piece of work. The proposed algorithm is well motivated and both theoretical as well as practical aspects of the method are addressed. The proof sketch is insightful and the discussion around the implementation challenges helps a practitioner to efficiently implement the proposed method.

Weaknesses: The experimental section is not as well motivated as the rest of the paper, and misses some details.

Correctness: There are some small errors in the theorem statements and the proofs (see comments) but they can easily be fixed and have no major implications on the results.

Clarity: The paper is well written and I particularly like that almost any design choice and assumption is discussed and well motivated.

Relation to Prior Work: I like the related work section a lot. It is not too extensive but points out and explains the issues of existing methods and tools and why things need to be addressed differently. The only thing I miss is an empirical comparison to related methods.

Reproducibility: Yes

### Review 4

Summary and Contributions: In this work, authors propose importance sampling to reduce the variance in stochastic gradient. The distribution over examples is learned by an online learning method. Estimating the probability is essential for importance sampling, the proposed method seems simple yet effective. For stable learning, they lower bound the probability and decay it when training.

Strengths: Importance sampling is a popular technique to reduce the variance. Authors provide the theoretical analysis about convergence and the experiments for demonstration.

Weaknesses: My concerns are as follows. 1. The regret in  is defined on function value while this work defines it with the norm of gradient. It is better to provide the same measurement for a fair comparison. 2. The topic that reduces variance with importance sampling is not new. Besides vanilla SGD, more baselines with variance reduction or importance sampling should be included in experiments for demonstration, especially when the theoretical improvement is not significant. 3. It lacks the experiments for the main method in this work that the gradient is computed from a single example. The only experiment is for mini-batch estimator while the additional experiment for the extreme case is necessary for evaluating the effectiveness of the theorem. 4. Authors claim that the regret bound for the proposed mini-batch method is cast to appendix. However, I didn’t find the regret bound for the mini-batch estimator in the supplementary.  Zalan Borsos, Andreas Krause, and Kfir Y Levy. Online Variance Reduction for Stochastic Optimization.

Correctness: seems right

Clarity: Yes

Relation to Prior Work: Yes

Reproducibility: Yes

Additional Feedback: I have read the rebuttal and my major concern can be addressed if they have the promised experiments in the revised version.
{"ft_lang_label":"__label__en","ft_lang_prob":0.93410605,"math_prob":0.86914796,"size":19620,"snap":"2021-31-2021-39","text_gpt3_token_len":4060,"char_repetition_ratio":0.13009788,"word_repetition_ratio":0.009971954,"special_character_ratio":0.209684,"punctuation_ratio":0.0954113,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.97319233,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-09-26T01:16:00Z\",\"WARC-Record-ID\":\"<urn:uuid:cbcc3b67-feb2-44f4-878c-f7010cb4eca2>\",\"Content-Length\":\"22372\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:356a9fcd-586e-40ad-916d-43e5a4584cdb>\",\"WARC-Concurrent-To\":\"<urn:uuid:d1a41e7e-fcf9-43d0-8ea6-5237aaa4f086>\",\"WARC-IP-Address\":\"198.202.70.94\",\"WARC-Target-URI\":\"https://papers.nips.cc/paper/2020/file/b58f7d184743106a8a66028b7a28937c-Review.html\",\"WARC-Payload-Digest\":\"sha1:DO6KLWPH2ZZRPI65ZJMTBR53LFU6FGA3\",\"WARC-Block-Digest\":\"sha1:G5TSSKFJ3LLQDUS5GL4KFBA3MNXWAHJA\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-39/CC-MAIN-2021-39_segments_1631780057787.63_warc_CC-MAIN-20210925232725-20210926022725-00457.warc.gz\"}"}