Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a new variance reduced algorithm for solving smooth and strongly convex optimization. The authors build on SARAH and propose AI-SARAH which aims to estimate the local Lipschitz smoothness parameters on the fly. The authors provide theoretical analysis for a modified version of AI-SARAH and provide extensive practical experiments for AI-SARAH.

main_review: - I cannot see it explained how to pick $\alpha_{max}^k$, In Lemmas B.7 and B.8 they depend on some Lipschitz constant depending on the set in eq. (11) how to estimate these?
- The authors talk about using Newton method to solve the sub-problem, but how does this affects the analysis explicitly?
- What about adaptivity to strong convexity? While it is easy to know the strong convexity for the regularizers, it can be quite difficult to estimate the strong convexity of the loss function ("data-term"). The authors say the algorithm is "fully adaptive". Probably,it should be explained that this "full adaptivity" is not to the strong convexity.


For the experiments, I understand the authors point: even though each iteration of AI-SARAH can be expensive because of the local Lipschitz constant estimation, it doesn't require tuning and the other methods require tuning. The authors state that they do "fine-tuning" for all the other methods, which takes a lot of time and therefore the overall cost of AI-SARAH is reasonable. My question is: what happens when the authors do a "rough tuning"? Is the improvement of the other methods is significant between the "rough tuning" and "fine tuning"? Maybe "fine tuning" isn't necessary for these methods to be competitive and the overall time for these algorithms can be reduced this way. It would be nice to see a tradeoff of these algorithms in terms of the accuracy/total time/budget of tuning.


- Why is sparsity of the datasets mentioned? Does the algorithm use this information in any way?

Overall, I am concerned that the writing is not too transparent to show this fact about the difference of analyzed and implemented algorithms. I find the discussions before Section 3.4 too long and repetitive whereas Section 3.4 is too quick and unclear for the readers why all these modifications are being done for analysis.


While I do appreciate the value of extensive practical comparisons, for such a well-studied class of problems (smooth and strongly convex), I expect a smaller gap between the theory and practice within the paper. Therefore, I think the authors should either implement the algorithm they analyze or analyze an algorithm closer to the one they implement. Moreover, if the paper wants to make a claim more on the practical side, then I am curious what happens with "a rough and systematic tuning" for other algorithms.

summary_of_the_review: I really appreciate the promise of the paper and the direction pursued by the authors. However, I have some concerns regarding the theory-practice mismatch within the paper. Unfortunately, until Section 3.4, the writing is as if the authors will analyze AI-SARAH which is implemented in practice, however Section 3.4 introduces many modifications on the algorithm. On this front, it is not explained if the analyzed algorithm does really work well in practice or how much theory can be shown for the implemented algorithm. 

I am willing to increase my score if the authors reply to my questions in a satisfactory way.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studies the stochastic recursive gradient method for finite-sum problems. The proposed approach AI-SARAH is a practical variant of SARAH by exploring the local geometry of the stochastic functions. Specifically, in each iteration of the inner loop, AI-SARAH estimates the parameter of local Lipschitz smoothness by solving a sub-problem so that can use a larger step size for faster convergence when approaching the optimum. 
main_review: Strengths:

1: This paper proposes a practical variant of SARAH with faster convergence by exploring the local geometry of the stochastic functions.

2: Extensive experiments are conducted to verify the effectiveness and efficiency of the proposed algorithm.

3: This paper is well-organized and well written with clear language and structures. The background knowledge is presented and the related papers are cited. 


Weaknesses:

1: The contribution of SARAH over SVRG is mainly on convex functions rather than strongly convex functions. However, this paper only analyzes the case of the strongly convex function for AI-SARAH. As a variant of SARAH, I believe theoretical results on the general convex function are required.

2: In convex optimization, the convergence results are usually evaluated with regard to the function value rather than the squared norm of the gradient. However, the proposed AI-SARAH is usually slower than the compared methods with regard to the function value. 

3: To tune the hyperparameter of SARAH and SVRG, in my personal experience, we do not really need 5000 runs to find a good hyperparameter. The authors may need to explain more on that.  

summary_of_the_review: Although the authors make some contributions in this paper, the weaknesses above are very critical to evaluating the contributions of the proposed method. I would like to vote for 'reject' if they are not addressed well.

After the discussion, some of the concerns are solved. I will increase the score to 5.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: In this paper, the authors proposed a SARAH-type variance reduced gradient method that adaptively and automatically selects the stepsize. 
In each step, the authors propose to do an approximate line-search of the currently sampled function $f_{i_t}$ (or $f_{S_t}$) to estimate the local Lipschitz constant of the sampled function. To estimate the Lipschitz constant of the true objective function (the summation), the authors propose to do an exponential moving average of the estimated local Lipschitz constants. 

Extensive experiments are done in solving convex problems, and the comparison with other state-of-the-art first-order methods is also carefully presented. The authors also presented some theoretical guarantees of the algorithm with certain modifications.
 
main_review: The authors presented a parameter-free and hence tunning-free variant of the SARAH variance reduction method. An extensive empirical study of the algorithm has been done and the result shows some advantages of the proposed method compared to other state-of-the-art methods that may need parameter tuning. This is the strength of the result. 

However, the weakness of the paper is that, though the authors do show some theoretical results, there is a big gap between the theory and the implemented algorithm. 


summary_of_the_review: The reviewer does appreciate the efforts in the empirical study. However, the reviewer has a few comments about the gap between theory and practice. 

1. The strength of the proposed algorithm is "tuning-free" and "parameter-free". However, to theoretically guarantee the convergence, the author actually requires knowing the local Lipschitz constant in the set $\mathcal{W}_k$, see Eq(6). 

2. The authors argue that as the iterations approach the optimal solution, the curvature may tend to be flatter. Therefore, the global Lipschitz constant may be much larger than the local Lipschitz constant, resulting in a more conservative stepsize, i.e., the stepsize $1/L_{global}$ may be much smaller than the stepsize $1/L_{local}$. However, since $\alpha_{max}^k$ is already $1/2L_{local}$, doing a line search only results in smaller stepsizes. This contradicts the philosophy of using larger stepsize when possible. Therefore, the theory does not explain the strength of the algorithm. Moreover, if $1/L_{local}$ is known, why not directly apply SARAH with this local parameter? 

3. There is a small flaw in the logic of the proof. First, the authors define the set \mathcal{W}_k:= {w:||w- \tilde w_{k-1}|| \leq m\alpha_{max}^k||v_0||}. The authors argued that $\mathcal{W}_k$ is the set where all the iterations of the $k$-th epoch should lie within. This only happens when all the later gradient estimators $||v_t||\leq ||v_0||$ almost surely, otherwise the proof wouldn't work. However, the authors are not able to show this because all the descent results are in the sense of expectation instead of almost surely. 

4. With $\alpha_{max}^k = 1/2L_{local}$, the analysis is more or less the same as the original SARAH algorithm, with little modification. Therefore, the current analysis is not very interesting to the reviewer. However, a much more interesting thing is how well the proposed procedure approximates the local gradient, this has never been addressed in the existing works. However, with the current assumptions on $\alpha_{max}^k$, this challenge is left undone.

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
After the rebutal, the authors have cleared my question in comment #3. The issue stated in this comment can be cleared with a few more explanation.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a novel algorithm by using adaptive tuning-free stepsize in SARAH, obtains its convergence rate in convex optimization, and demonstrates its empirical superiority by logistic regression experiments. 
main_review: Pros: 

(1) The combination of adaptive tuning-free stepsize + SARAH is novel. Its motivation is very clear. 

(2) The experiments show that AI-SARAH outperforms some main-stream stochastic optimizers.  

Concerns:

(1) My major concern is that both the theorem and the experiments only involve convex optimization, while nonconvex optimization is more popular in machine learning, and SARAH achieves near-optimal sample complexity for nonconvex optimization. For convex optimization, SVRG and SAGA [2] have better sample complexity than SARAH. Hence, I suggest adding both theorem and experiments for nonconvex optimization.

(2) Also, for convex optimization, usually we obtain convergence rate of function value gap $f(w_t)-f(w^*)$ or point distance $\|w_t-w^*\|$, while the authors only obtain convergence rate of gradient norm which is weaker and usually obtained for nonconvex optimization. 

(3) I suggest adding theoretical results of sample complexity (The number of computing function value and derivatives) and compare with that of SARAH for nonconvex optimization, since most works on SGD and variance reduction techniques (including SARAH) have sample complexity results. For the convex optimization, the complexity result can be directly obtained from Theorem 1.

**I reject this paper mainly due to the above three concerns. Once they are solved, I will change to accept.**

(4) The algorithm is claimed as "First-order", while $\xi'(0)$ and $\xi''(0)$ require the second and the third order derivatives of $P$ respectively. Hence, the sample complexity result also needs to involve the number of evaluations of the second and the third order derivatives.

(5) There is an unclear point in Algorithm 1. If $k>0$ and $t=1$, then the line 14 is implemented using the undefined $\delta_0^k$. What is the value of $\delta_0^k$?

Minor comments: 

(1) It is better to add y-axis labels to Figures 1c, 1d and 8. For example, The y-axis label of Figure 8 may be "stepsize".

(2) In line 10 of Algorithm 1, you could add "using $\xi_t$ defined in (4)", and in (4), I think you could still use $f_{S_t}$ since that looks the same simple as $f_{i_t}$ and guides us to correctly use Algorithm 1. Then, when explaining (4) by the example of quadratic function, you could let $S_t=\{i_t\}$ for simplicity.

(3) For nonconvex optimization, you might use STORM algorithm [1] instead of SARAH, since both of them achieve the near-optimal sample complexity for nonconvex finite-sum optimization, but STORM does not require full gradient. 

(4) At the beginning of page 5, use "Let" (capitalized) in "let us focus on a simple quadratic function". 

(5) You might compare with SAGA [2], another important variance reduction technique as well in your experiment. 

(6) The authors may add intuition of the line 17 of Algorithm, i.e., the reason for using $\alpha_{\max}$.

(7) In the final paragraph of Section 1.2, all the variance reduced work I read use $w_{t+1}=w_t-\alpha_t v_t$, with either constant stepsize $\alpha_t=\alpha$ or predetermined diminishing stepsize. Also "allow use" could be "allow to use". 

References:

[1] Cutkosky, Ashok, and Francesco Orabona. Momentum-based variance reduction in non-convex sgd. ArXiv:1905.10018 (2019).

[2] Defazio, Aaron, Francis Bach, and Simon Lacoste-Julien. SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives. Advances in neural information processing systems. 2014.
summary_of_the_review: I reject this paper mainly due to the above concerns 1-3. Once they are solved, I will change to accept.
review_title: null

Meta-review: This paper presents a variant of SARAH, which employs the stochastic recursive gradient and adjustable step-size based on local geometry. The main concerns about this paper include (1) the empirical comparison with other algorithms might not be fair (which is arguable); and (2)  the theorem proved in the paper is for a simplified algorithm rather than the algorithm used in the experiments. Even after author response and reviewer discussion, this paper does not gather sufficient support from the reviewers. Thus I recommend rejection.
Decision: Reject