Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The authors propose a variance-reduced algorithm ZeroSARAH for solving the nonconvex finite-sum problems. They also propose a distributed variant D-ZeroSARAH for the corresponding distributed framework. They provide the state-of-the-art convergence results for these methods using standard assumptions. The authors claim that both methods does not require computing full gradients, which gives a major advantage when the number of samples $n$ is large. They further validate ZeroSARAH using nonconvex linear regression and binary classification for neural networks.
main_review: - The authors propose ZeroSARAH and its variant for distributed framework. They highlight that "Avoiding any full gradient computations is important especially in this distributed setting, periodic computation of full gradient across all n clients may be impossible or unaffordable." Furthermore, "the main advantage of (their) algorithms is that they do not need to compute any full gradients".

- However, ZeroSARAH needs a group of auxiliary variables $y_i^k$ for $i= 1,\dots, n$ and $k = 0,1,2,\dots$. I find it surprising when the authors did not discuss these variables in the description of Algorithm 2 (Section 4.1). The update in line 5 in fact requires us to compute the summation of $n$ such variables $\sum_{j=1}^n y_j^{k-1}$, which is relatively similar to computing the full gradient. Again, I am surprised that the authors did not discuss the storage cost needed for ZeroSARAH. From my understanding, this algorithm needs to keep a table of past gradients in the auxiliary variables $y_i^k$, and at the moment I can not find a solution to get rid of this storage cost. For that reason, it is reasonable that your algorithm does not need many full gradient computations while still achieves the same state-of-the-art rate. I recommend that the authors discuss your method with SAG/SAGA where these methods also need to store a table of past gradients. 

- Similarly in the distributed setting, although we don't need a full gradient, we still need to compute a sum of $n$ variables (Line 11 of Algorithm 3). Hence this may slow down the training process no matter the fact that we don't collect every gradient. 

- For these reasons above, I do not see that ZeroSARAH has any major advantage over existing works. Please note that not every VR method needs to compute full gradients. For example, the reference [Inexact SARAH Algorithm for Stochastic Optimization] (Nguyen et al, 2020) only compute a mini-batch gradient in the training process. This should be added and discussed in this paper.

- The authors might want to edit some statements that could be confusing/misleading. For example, the statement "all existing variance-reduced methods, including SARAH, SVRG, SAGA and their variants, need to compute the full gradient" while "SCSG (Lei et al., 2017), SVRG+ (Li & Li, 2018), PAGE (Li et al., 2021)) may avoid full gradient computations by using a large minibatch of stochastic gradients instead". Also the statement "(our methods) improve the previous best-known result" is also misleading.

- A minor point: the authors might want to specify the output $\hat{x}^K$ in the main paper.
summary_of_the_review: The authors present a new method named ZeroSARAH where the main advantage is that they do not need to compute any full gradients. However this algorithms may requires more storage/computational cost than the previous methods that use minibatch to update. Therefore I do not see any advantage and do not support publication at the moment when these issues are unresolved.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper introduce ZeroSARAH which is a variant of variance reduced SARAH algorithm, for solving $\min_x 1/n \sum_{i=1}^n f_i(x)$ with nonconvex and smooth $f_i$. ZeroSARAH and its distributed version are the first algorithms that do not require any full gradient computations. Most algorithms for this setting either required computing the full gradient once in the beginning or periodically. The paper also argues that in distributed optimization, computation of full gradients can be a bottleneck and therefore avoiding it is important.

main_review: 1. The authors say in the abstract, intro and conclusion that "their complexity improves existing ones in current regimes", but I cannot see this written down explicitly. The closest I can find is the Remark after Corol. 2 that states "if G_0, \hat \Delta_0" are constants, which is obviously a too much of a simplification and also not true in most cases. For example, why is $\hat \Delta_0$ is even finite? Assuming the objective is lower bounded is a common assumption, but of course each component can be without a lower bound (take linear functions. Their sum can lower bounded whereas they individually are not). Then what will happen to $\hat \Delta_0$?

2. Due to my previous point, it is not clear if it is possible to give a fair comparison between the current complexity and previous best complexity. The new complexities depend on $G_0, \hat \Delta_0$ and their relation to the other terms is quite unclear.

3. In the experiments, only comparison is with SARAH which is insufficient. Since one of the main motivations of the paper is distributed optimization, I think the authors need to compare with the algorithms from Table 2, for example SCAFFOLD, or other SOTA algorithms in this setting to see if the new method is really useful in practice.

4. Please define $\hat x_K$ either in the algorithm or the theorem/corollaries. I had to check the proof to see how it is defined.

I am of course open to increase my score if my concerns in 1,2,3 are addressed.
summary_of_the_review: Overall, I agree that an algorithm with zero full gradient computation is definitely interesting, it is not clear if this brings any advantage in theory (due to different parameters in the bounds) and also in practice (experiments are only compared to SARAH and not with the SOTA solvers in distributed settings.)
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper proposes ZeroSARAH (and its distributed version D-ZeroSARAH), a variant of the well-known variance-reduced method SARAH, for non convex finite-sum optimization. The main benefit of ZeroSARAH and D-ZeroSARAH is that they do not require any full gradient computations, in contrast to other known variance reduction algorithms. In distributed setting, this can avoid the burden of synchronizing all clients. 
main_review: The paper first presents ZeroSARAH, which slightly modifies SARAH in the sense that ZeroSARAH replaces the past gradient estimator $v^{k-1}$ of SARAH with the weighted sum of $v^{k-1}$ and another estimator to avoid the periodic computation of the full gradient. The technique is definitely new, but still a bit incremental. 


In the centralized setting (ZeroSARAH), the authors establish the ZeroSARAH's complexity of $O(n+\frac{\sqrt{n} L \Delta_0}{\epsilon^2})$ or $O(\frac{\sqrt{n} (L \Delta_0+G_0)}{\epsilon^2})$ versus $O(n+\frac{\sqrt{n} L \Delta_0}{\epsilon^2})$ of SARAH. The term $n$ in SARAH just means that you must run at least one iteration of the algorithm [1], which takes the full gradient snapshot, and is usually dominated by the other term due to the large condition numbers in practice. Therefore, the complexity achieved by ZeroSARAH is essentially comparable to SARAH's, where $O(\frac{\sqrt{n} (L \Delta_0+G_0)}{\epsilon^2})$ can be seen as the interpretation of the fact that no full gradient computation is needed. However, in this centralized setting, avoiding full gradient computation does not provide any real benefit. ZeroSARAH still serves as the basis for the development of D-ZeroSARAH for distributed setting where avoidance of full gradient computation can be beneficial.


In the distributed setting (D-ZeroSARAH), the complexities established for D-ZeroSARAH are comparable to distributed Sarah, which follows the same reasons as above. The main benefit of D-ZeroSARAH is the fact that it does not require full gradient computation, which can alleviate the burden of synchronizing all clients. This is an interesting perspective that has not been widely considered yet. Nevertheless, since both D-ZeroSARAH and distributed Sarah have the same gradient complexity $O(\sqrt{\frac{m}{n}} \frac{1}{\epsilon^2})$ and D-ZeroSARAH requires less gradient evaluations per iterations, the number of iterations, i.e. communication rounds, required by D-ZeroSARAH is more than by SARAH. The communication complexity (i.e. communication rounds) is one of the most common metrics considered by the distributed optimization literature, which also corresponds to the fact that setting up a synchronization round is expensive in practice. All in all, D-ZeroSARAH can be viewed as a variant of distributed SARAH with reasonable tradeoffs in number of gradient computations per iteration and communication complexity. Perhaps the authors can add some discussion on communication complexity. 

Extensive experiments for both of ZeroSARAH and D-ZeroSARAH were conducted to verify the theories and robustness of the proposed methods. 


Typos/Mismatch: In Corollary 3, the parameter is set such that $b_k= \sqrt{m}$, but in its proof it seems that $b_k=\sqrt{m/n}$. 





[1] Pham, Nhan H., Lam M. Nguyen, D. Phan and Quoc Tran-Dinh. “ProxSARAH: An Efficient Algorithmic Framework for Stochastic Composite Nonconvex Optimization.” ArXiv abs/1902.05679 (2020).
summary_of_the_review: Overall, the paper proposes ZeroSARAH and its distributed version D-ZeroSARAH, as variants of SARAH that avoid full gradient computation. Under the distributed setting (where such feature can be beneficial), requiring less number of gradient computations per iteration means that D-ZeroSARAH requires more iterations, i.e. communication rounds, than distributed SARAH to converge, since the  gradient complexity of these 2 algorithms are asymptotically the same. This provides some interesting tradeoffs, but in general, communication complexity is usually more prioritized in practice. D-ZeroSARAH can address certain situations where synchronizing all clients is impractical. This is a new perspective for this class of problems and can facilitate future work in this direction. The proposed methods are empirically validated.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper introduces a form of SARAH (the variance reduction method)  that avoids taking full gradients, which is called ZeroSARAH, and also a distributed version (D-ZeroSARAH). They offer convergence results and shows that it is on the same order of gradient calls to $$\epsilon$$-gradient norm as other state-of-the-art variance reduction methods, but claim it is without ever requiring full gradients.


main_review: Overall it's a nice method and I don't see anything wrong with the proofs (though I really only skimmed). My main counterthought is that the paper didn't really address SAG and SAGA, which are other mainstream VR methods that also do not require full gradient calls, do not even require full minibatch computations, and also have competitive convergence rates. The downside of SAG and SAGA seem to be the same as this method, which is the high memory cost; the need to store the yi's seems to be similar to the issues of SAG and SAGA. As it stands, having such a high memory cost in general makes these methods prohibitive to most deep learning applications, and is on the same order of "issues" as SVRG.

The other (maybe not that minor) thing is that, the authors say that although minibatch versions of SVRG and such methods exist, their convergence depends on bounding the variance of the stochastic gradients, which it is true is hard in general. However, this is necessary for the proofs of ALL VR methods, not just the minibatched versions. It seems like the authors bypassed this issue via telescoping, so perhaps it just isn't an issue with SARAH. But I don't believe this is somehow a new issue with minibatching to estimate the stale full gradient, is my point. 
summary_of_the_review: See above
review_title: null

Meta-review: There are many discussions among the reviewers for this paper and eventually none of the reviewers (including the one who gave most positive score) would like to support the publication of this paper. 

Some concerns from the reviewers are as follows:
1. Missing the discussion on storage cost. 
2. The improvement is limited. $G_0$ must be small and independent of $n$, hence it is not clear if it is possible to give a fair comparison between the current complexity and previous best complexity. 
3. Missing the discussion on the case when $n \leq \mathcal{O}(\varepsilon^{-4})$ of the state-the-art results. 
4. For the complexity results in terms of $\varepsilon$, it requires $\varepsilon$ to be arbitrarily small. The authors should also discuss this point for comparing with their result. 
5. Some other statements in the papers are overclaimed. 

Please take the comments and suggestions from the reviewers carefully to revise the paper for the future venues since they raised valid points.
Decision: Reject