A Guide Through the Zoo of Biased SGD

Summary

The paper analyzes the assumptions for biasedSGD for various applications and proposes a more general and weaker ABC-assumption that covers the mentioned assumptions. The paper provides a detailed comparison with several existing literature trying to build up a unified framework for biasedSGD. It seems to be a further generalization of [Ahmad Ajalloeian and Sebastian U Stich, 2020].

Strengths

The paper provides a clear link of different assumption used in the BiasedSGD literature and compare them in Figure 1. In additional, it proposes a set of assumption for biasedSGD that can guarantee the same iteration complexity as the unbiased SGD. I appreciate the clarity and structure of these relationships as they can be invaluable when addressing a new problem requiring BiasedSGD, thus saving time for the reader.

Weaknesses

I mainly have two concerns: missing reference on other biasedSGD methods and how the proposed ABC assumption can serve as a useful assumption. This paper overlooks a substantial body of literature on biasedSGD in contexts beyond classical stochastic optimization/finite-sum and distributed training settings, such as 1. Stochastic compositional/minimax/bilevel optimization. [1,2,3] 2. Conditional stochastic optimization. [4,5,6] 3. Distributionally robust optimization. [7,8] 4. Meta learning. [9] These works are centered on constructing biased gradient estimators and analyzing biasedSGD. Unlike the manuscript, these studies not only consider iteration complexity but also the total sample size needed to reach the desired solution, given the potential high sampling/computational cost of creating low-bias or unbiased gradient estimators. This angle is neglected in the manuscript, causing the title "A Guide Through the Zoo of Biased SGD" to seem overstated. Consequently, Section 2, addressing the source of bias, appears narrow given the wide applicability of biasedSGD. I suggest that the authors limit their claims, incorporate and discuss the above references, and address other bias sources. Specifically, it would be insightful if they could compare two biasedSGD construction methodologies: 1. The approach in [1] that progressively reduces the bias level of the biased gradient estimators as the algorithm evolves. 2. The approach in [5] that constructs low-bias gradient estimators at a cheap cost at each iteration. Notably, it seems that [1,2,3] don't meet the proposed ABC condition, but the proposed biasedSGD algorithm can still achieve optimal sample complexity. For [5], the gradient estimator constructed in [5] should satisfy ABC condition or its variants but the submitted paper fails to address the potential high costs of obtaining gradient estimators that adhere to the proposed ABC assumption. The authors should discuss these limitations. The proposed ABC assumption appears difficult to validate. It remains unclear when this condition should be employed. [1] Chen, Tianyi, Yuejiao Sun, and Wotao Yin. "Closing the gap: Tighter analysis of alternating stochastic gradient methods for bilevel problems." Advances in Neural Information Processing Systems 34 (2021): 25294-25307. [2] Chen, Tianyi, Yuejiao Sun, and Wotao Yin. "Solving stochastic compositional optimization is nearly as easy as solving stochastic optimization." IEEE Transactions on Signal Processing 69 (2021): 4937-4948. [3] Chen, Tianyi, Yuejiao Sun, and Wotao Yin. "A single-timescale stochastic bilevel optimization method." arXiv preprint arXiv:2102.04671 (2021). [4] Hu, Yifan, et al. "Biased stochastic first-order methods for conditional stochastic optimization and applications in meta learning." Advances in Neural Information Processing Systems 33 (2020): 2759-2770. [5] Hu, Yifan, Xin Chen, and Niao He. "On the bias-variance-cost tradeoff of stochastic optimization." Advances in Neural Information Processing Systems 34 (2021): 22119-22131. [6] Hu, Yifan, Xin Chen, and Niao He. "Sample complexity of sample average approximation for conditional stochastic optimization." SIAM Journal on Optimization 30.3 (2020): 2103-2133. [7] Levy, Daniel, et al. "Large-scale methods for distributionally robust optimization." Advances in Neural Information Processing Systems 33 (2020): 8847-8860. [8] Wang, Jie, Rui Gao, and Yao Xie. "Sinkhorn distributionally robust optimization." arXiv preprint arXiv:2109.11926 (2021). [9] Ji, Kaiyi, Junjie Yang, and Yingbin Liang. "Theoretical convergence of multi-step model-agnostic meta-learning." Journal of machine learning research (2022).

Questions

See weakness. Other questions: 1. Ahmad Ajalloeian and Sebastian U Stich 2020 has been published. Please update the preprint references if they are published. 2. Table 4, it says that "In most cases, we ensure the same rate", but the table 4 last column does not seem to suggest so. 3. For strongly convex case, what happens when Assumption 12 fail?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

The main drawback of the work is its predominant focus on iteration complexity in specific contexts, such as finite-sum, zeroth-order, and distributed stochastic optimization settings. Other perspectives on BiasedSGD, such as sample costs/computational costs for different problem settings, are not sufficiently addressed. Numerous biasedSGD methods applicable to a variety of other contexts are overlooked.

Summary

This paper establishes connections among the existing assumptions found in the literature on Stochastic Gradient Descent (SGD) with biased estimators. The authors provide a comprehensive map that illustrates the relationships between these assumptions, addressing the lack of coherence found in previous works. Furthermore, they introduce a new set of assumptions, namely Biased ABC that have been proven to be weaker than the previous ones. It enables a thorough analysis of Biased SGD in both convex and non-convex settings. The paper also showcases examples where biased estimators outperform their unbiased counterparts or where unbiased versions are not available. Finally, the authors validate their theoretical findings through experimental results, which further supports the effectiveness of their framework.

Strengths

This paper provides a comprehensive overview of the existing literature elaborating on connections between the existing assumptions and the proposed assumption used in the analysis for biased SGD. Often, when comparing two theoretical results, one may demonstrate slightly tighter result by relying on stricter assumptions, while the other may provide a slightly worse dependence but arguing they have milder assumption. Assessing which approach is superior can be a challenging task. In this regard, the authors have tackled a crucial and significant subject. They have made a good effort towards unifying the various assumptions by proposing a new set of assumption which believed to be weaker than all previous ones. These proposed assumptions cover the existing assumptions, and the convergence results can be suitably adapted accordingly.

Weaknesses

The newly proposed assumption Biased ABC is an incremental work based on existing work on biased SGD and the work done by Khaled and Richtárik [2023] for unbiased SGD. I felt there is not much novelty exists in this newly proposed assumption. Also, in my opinion, the balance between the discussion on the background and introduction of existing assumptions and the presentation of the authors' own theoretical results could be further improved.

Questions

1. Is there an example to support Claim 1?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

4 excellent

Limitations

1. Figure 1 summarized one of the main contribution of this paper. However, the way it presented right now is not ideal. Especially after including the blue dashed lines. With so many lines that are flying around, the main message that this figure tries to deliver is not well received, in my opinion. I would recommend the author find a more concise way to present the connections in Figure 1.

Summary

This paper summarizes various recent assumptions about the convergence of biased SGD and exposes their implication relations. Furthermore, it proposes a weaker assumption, Biased ABC, in terms of implication relations and analyzes the results under this assumption.

Strengths

This paper summarizes various recent assumptions about the convergence of biased SGD and exposes their implication relations. It is well written and in particular, Figure 1 is informative.

Weaknesses

It seems that submitting a paper, which has an Appendix of 50 pages including proofs, to an international conference where the peer review period is short and there is not enough time to adequately check proofs, is a negative impression in itself. In addition, the fact that the paper ends with a section on experiments and does not include a summary gives a half-hearted impression of the paper's presentation, which I suppose cannot be helped given the insufficient number of pages, but conversely, it seems to mean that this paper is not suitable for an international conference with a tight page limit.

Questions

Although the implication shows that Biased ABC is the weaker assumption, at first glance it seems that this assumption is more difficult to check because it requires more variables to be shown to exist and f* is needed than the other assumptions. To explain more intuitively why this assumption is weaker, please explain a situation that can be checked with this assumption but not with the other assumptions, or a situation that applies to this assumption but not to the other assumptions. Also, I know that if Assumption 8 holds, then Assumption 9 holds, but I could not catch the proof that the converse does not hold, so please tell me where in the Appendix it is written. This is important for showing the weakness of Assumption 9, which leads directly to raising the score. Since the experiment section is halfway through, wouldn't it be better to put it into the experiment part of the Appendix and write a discussion and conclusion? The experiment itself does not seem to make much sense in this paper.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Too many pages in Appendix make it difficult to check the correctness of proofs in the limited peer review period of an international conference. Currently, it is difficult to see that the assumption is weaker than Assumption 8.

Summary

This paper focuses on the relationships among various assumptions used in the analysis of biased SGD. The authors establish connections among the large number of existing assumptions present in the literature, and propose an assumption (Biased ABC) which captures all prior assumptions. The authors also show that this assumption captures stochastic gradient oracles that prior assumptions did not allow. Using this assumption, they give a simple proof of SGD convergence in a number of settings (both convex and non-convex). While in some cases, the rates are slightly suboptimal (due in part to the more general setting they consider), in many cases, these proofs recover the same (or nearly the same) bounds of prior work under weaker assumptions.

Strengths

This paper provides a very nice overview of the assumptions made in various works on analysis of biased SGD. They establish relationships among these assumptions, and suggest an assumption (Biased ABC) which captures all of these assumptions. This characterization will surely be of great utility to researchers interested or working in this area. By taking a more general assumption, they are able to recover a number of existing results in the literature, sometimes slightly generalizing the results by weakening the assumptions. Sometimes, however, the results obtained are slightly cruder (due to their assumption being weaker). Although there are no significant new proof techniques (at least that I saw) in this paper, I think there is a lot of value in simplifying and unifying results of prior works.

Weaknesses

[Theorem 2 viii and ix] If I am not mistaken, it appears there is a bug in the proof of “The reverse implication does not hold” part of Theorem 2 viii and ix. You consider $f_1(x) = (x_1^2 - x_2^2)/2$ and $f_2(x) = -f_1(x)$, and claim “Due to Claim 2, it satisfies Assumption 9 (functions $f_1$ and $f_2$ are $1$-smooth)”. To apply Claim 2, however, Assumption 13 must hold, which not only requires the functions $f_i$ to be smooth, but also to be bounded from below. $f_1(x)$ is clearly not bounded from below (take $x_1=0$ and $x_2 \rightarrow +\infty$). Thus, it seems that Claim 2 cannot be applied to your example. [Organization of the paper] I personally found the paper a bit hard to navigate. I think this is largely due to the sheer number of claims, definitions, and parts of proofs that are in the paper. I think some reorganization could greatly improve the readability of the paper. For instance, when reading section B of the appendix, you mention the Biased independent sampling without replacement (Definition 1). I was curious why Assumption 8 can break for this setting (i.e., why you need $A>0$ in Assumption 9), but actually understanding this required finding the proof of Claim 2 and the proof of Theorem 2 viii and ix. It didn’t feel like a natural flow to have to dig so much for what seemed to be the punchline of introducing Definition 1. Is there a way to bring this all in one place? I understand that organizing a paper with so many short results is difficult. However, I think that some results are less interesting than others, and perhaps can be moved to the end of the paper to reduce clutter. For instance, I think the main interesting parts of Theorem 2 concern Assumption 9. Perhaps you can separate these parts from the others, so that these are easier to find? Another note is that some parts of the appendix feel like they do not have enough bridge text. For instance, section C is just a long list of Definitions and Claims. Could you add some text describing these settings, or why they might be interesting to the reader? Also, in the main body, you mention lots of assumptions, but there is no mention of actual examples where the stochastic gradients satisfy these examples. All of this is saved for the appendix. I think it would help readability of the paper if some of the less interesting assumptions were moved to the appendix (perhaps only keep a couple of the main assumptions in the main body), and you moved some of the examples to the main body (e.g., the Biased independent sampling w/o replacement, or another of your choosing).

Questions

[Regarding Assumption ABC] I found the term $A(f(x) - f^*)$ term in eq. (19) to be somewhat mysterious, yet there is not much discussion in the main body of your paper as to why you consider this term in the variance bound. In the appendix, it becomes somewhat clear that you introduce $A$ to handle “Biased independent sampling”, but this this isn’t discussed much in the paper. Are there other reasons why you consider this term in the variance bound? It is worth noting that a similar assumption (in the unbiased setting) was considered by Polyak and Tsypkin (1973) “Pseudogradient Adaptation and Training Algorithms” (see the first equation in their Section 3). They also don’t really discuss why they consider this term in the variance bound. I don’t think I’ve seen this type of assumption anywhere else in the literature (except in Khaled and Richtárik (2023) “Better theory for SGD in the nonconvex world”, as you mention). Perhaps you have some insights into this? Also, it is probably worth giving the Polyak and Tsypkin paper a citation, given the similarity of your assumptions. [Regarding the discussions in weaknesses section above] Could you please address if the error in the proof of Theorem 2 viii and ix is easy to overcome? (I will set my score now to weak accept due to this error). Could you please describe how you plan to incorporate the feedback on paper organization? [Regarding Theorem 3] Theorem 3 gives a guarantee on $\min_t E[||\nabla f(x_t)||^2]$, while, at least for the unbiased setting, the results of Ghadimi and Lan (2013) give convergence for the average iterate. Looking at your proof, it appears that you actually get convergence for a weighted average of the gradients, but where the *smaller* iterates are weighted higher. That seemed quite counter-intuitive to me, as I would have expected a higher weighting of later iterates. Do you have any intuition on why the weighting is this way? Is there any hope in getting convergence of the average iterate in your framework?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

N/A

Thank you.

Thanks for the looking into the reference in such a short time and for the response. It addresses my concerns. I am happy to raise the score to 6. Regarding the question, I mean [Ahmad Ajalloeian and Sebastian U Stich. Analysis of SGD with biased gradient estimators. arXiv preprint arXiv:2008.00051, 2020.] has been published at ICML workshop 2020 with name "On the Convergence of SGD with Biased Gradients".

Thanks

I would like to thank the authors for their detailed responses to my questions. I've reviewed their fixes to the proof of Theorem 2 parts viii-ix, and I agree that, for this choice of objective and stochastic gradients, the "reverse implication" does not hold. Thanks for fixing this. In the next version of the paper, I would still suggest that the authors incorporate some of the reorganization as discussed above. Additionally, I think it would benefit the paper to include the author's response to "Regarding Assumption ABC" above in the next revision. With these changes to the paper, I am happy to raise my score from 6 -> 7.

After rebuttle

Thank you for showing an example when Assumptions 6 and 8 do not hold, but new Assumption 9 still holds. My concern has been adressed. I raised score. However, I still consider that this paper is unsuitable for an international conference where short peer review is forced. We know that papers have already been published at international conferences that devote pages to many proofs, which in itself is considered problematic. We understand the opinion that there is a precedent and that it should be accepted this time as well, but that does not change anything. Considering that papers with incorrect proofs may also pass peer review, papers that need to be carefully checked for proofs should still take such a step.