Venue: ICLR 2022 Conference

Reviews:

final_score: rating: null
review_content: I have read the rebuttals. The authors answered "correctly" some of my questions  and responded with general statements to others. I also read the other criticisms from other reviews. I still think this work has some merit as it is, but I cannot increase my score to more than 6.
review_title: After rebuttal

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper uses importance sampling in SGD to improve performance.
main_review: The importance sampling procedure is new, however there have been many similar works in the past and this paper's results maybe very incremental.
summary_of_the_review: The importance sampling procedure is new, however there have been many similar works in the past and this paper's results maybe very incremental.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The authors propose the stochastic reweighted gradient (SRG) algorithm, which is based on importance sampling in SGD to reduce the variance for the SGD method. The authors also extend SRG to combine the benefits of both importance-sampling-based preconditioning and variance reduction. The convergence rate is studied and the authors show that the proposed method can achieve a better asymptotic error than SGD. 
main_review: There is a rich literature in the domain for SGD based on importance sampling and conditional variances approximation. The paper combines these two ideas, and I believe that it is useful for reducing the asymptotic error and computational complexities. I have some concerns as follows.
1.	I might be misunderstanding part of the proofs, but I hope the author could help me understand more on why Lemma 2 holds. In the algorithm, $p_k$ is calculated based on $q_k$, which is related to a binomial distribution with parameter $\theta_k$. So the randomness of $q_k$ may have an impact on the expectation. However in the proof, the impact of $q_k$ is not involved, and $p_k$ seems to be treated as a constant. In other words, since the importance sampling process can be regarded as a kind of Bayes procedure, how does the distribution of the sampling probability impact the convergence?
2.	In the experiments, the proposed method is compared with SGD+ (SGD with $L_i$-sampling) and SGD++ (SGD with partially biased sampling), how about comparing with importance sampling SGD with the optimal sample probabilities?

summary_of_the_review: I believe the paper has its value in combining importance sampling SGD with conditional variances approximation to reduce the asymptotic error as well as the computational complexity. I just have one question on the technical soundness of the convergence results.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper considers minimizing the finite sum problem with SGD with non-uniform sampling. 
The optimal sampling weight at a given point is achieved via minimizing the variance of stochastic gradient which needs the norm of the gradient of each function at that point. To approximate these sampling weights and also be efficient this paper proposes to take the approach similar to SAGA and use auxiliary memory with the size of number of functions and update one of the stored values in each iterate similar to SAGA. Using stale and stored gradient norms gives an upper bound to the stochastic gradient variance that could be minimized similarly. Since this new upper bound contains two terms, they propose a mixture of non-uniform and uniform sampling to make both terms small. They analyze SGD with the proposed sampling scheme and show that the sub-optimality upper bound is n (the number of functions)-times smaller than the upper bound of SGD with uniform sampling. They also propose another weighting scheme that mixes uniform and non-uniformes schemes proportioned with gradient norms and smoothness parameters of each function. 

main_review: 1- The paper is well-written and it is easy to follow and walk through the proofs. 

2- The major comment is that the analysis is for very limiting settings. It would be more practical to analyze the method for non-convex settings to see the effectiveness of the method in practice for training NNs. It would be useful to apply this method to NN training. 

3- For the experiments, it is not clear how many times each experiment has been run and if the result is the average of those.   


summary_of_the_review: The major comment is that the analysis is for very limiting settings. It would be more practical to analyze the method for non-convex settings to see the effectiveness of the method in practice for training NNs. It would be useful to apply this method to NN training.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This work proposes a variance-reduced method called stochastic reweighted gradient (SRG) method which is based on importance sampling.  SRG improves on the of stochastic gradient descent error for the strongly convex and smooth objective functions. The authors extended  also SRG to SRG+ to combine the importance-sampling-based preconditioning and variance reduction. Numerical experiments are provided to assess the numerical efficiency of these methods.
main_review: 
One of the biggest challenge in this paper is the assumption for SRG+ that we know all the Lipschitz constants of f_i s. For linear & logistic regressions, I agree that we can know them. But for many problems, especially in real world scenarios, it will be difficult to either compute these values or use them to do sampling. More comments on this is needed in the paper.

I would like to see more applications and experiments than those in the paper. The analysis does not convince me that importance sampling is truly helpful. Does this matter? Should I try to use this? Do I have any hope of using it in settings that are large-scale enough that I want to simply stream the data? 

Since there is extra computation at each iteration compared to SGD (computation of norms, updates....), then experiments with run time in x-axis make more sense?

What about minibatch versions of your methods, do they support this? how? comments on this are needed.

What is the sensitivity of your methods to theta?
summary_of_the_review: See above
review_title: null

Meta-review: The reviewers and AC all find the presented approach interesting and promising. 

However, as pointed out in the reviews and as the authors recognized, the strongly convex + smooth objective setting considered is limited. Given the prevalence of non-convex settings in many practical applications and the rich related literature on the analysis of SGD and variants in the non-convex setting,  it would be highly desirable to (i) consider experiments on small NN architectures (since the method cannot accommodate larger architectures)  to gain some understanding of the value of the approach and (ii)  to try and extend the present analysis to the non-convex case. 

It would also be valuable to perform experiments illustrating the impact of theta indicated by the theory.
Decision: Reject