Venue: ICLR 2023 Conference

Reviews:

final_score: rating: null
review_content: The reviewers mentioned specific sections/paragraphs/equations, which are now relocated with the new revision. Could the authors upload the original manuscript in supplementary material for reference for our first-stage reviews?

===================

Oh I found it by clicking "Show Revisions", never mind. 
review_title: [Closed] Could the authors please upload the original submission for reference?

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper studies the gap between the theoretical and empirical optimal hyperparameters values for adaptive gradient methods such as Adam for stochastic non-convex optimization. It provides new convergence upper bounds for several of these methods under bounded gradients and variance assumptions. These upper bounds are shown to be the lowest for the aforementioned hyperparameters being close to one, which is close to practice. 


strength_and_weaknesses: The first major problem with the paper is assuming both bounded variance and bounded gradients. It is well known that in this setting, mini-batching doesn't help because for usual problems $G\approx \sigma$ unless there is some stylized noise structure. Bounded variance assumptions are usually paired with smoothness assumptions, for instance, [this paper](https://arxiv.org/pdf/1912.02365.pdf). Under the paper's assumptions, if $\sigma$ is replaced by $G$, then $C_2 \leq C_3$ so there is no benefit of mini-batching! Similarly, it is not reasonable to assume the boundedness of parameters without explicitly making any projection steps in the algorithm. 

The second major problem is that the paper makes no comparison to the existing upper bounds for these algorithms. As a result, it is unclear if Adam's analysis is an improvement over the existing work. And if the upper bounds are worse than the previous bounds, then it is a fallacy to make any conclusions about the optimal hyper-parameters. Ideally, one would never make such conclusions with just upper bounds without matching lower bounds. 

Another issue is that the final guarantees in the paper are not comparable to usual guarantees upper bounding $\frac{1}{K}\sum_{k\in[K]} \mathbb{E}||\nabla f(\theta_k)||^2$, which guarantees that at least one iterate was an approximate stationary point. The paper instead uses a variational metric, but it is not reasonable to average it across $k$ because that doesn't imply that the best $\theta_k$ satisfies the variational metric for all $\theta$. 

Overall, the paper is not technically sound. 
clarity,_quality,_novelty_and_reproducibility: The paper is not very well written. 

1. I suggest using a different notation for oracle complexity, something like $N$ instead of $Kb$. It might be a bit confusing to think of $Kb$ as a function of the batch size. 

2. The paper mentions it studies stochastic first-order oracle complexity and does so in its theory because it considers a stochastic optimization problem. However, most of the previous empirical work mentioned in the paper uses SGD with multiple passes, i.e., it doesn't use sampling with replacement, which means different batches are not independent (for context on theory, consider [this paper](https://proceedings.neurips.cc/paper/2021/hash/e64c9ec33f19c7de745bd6b6d1a7a86e-Abstract.html)). This is confusing and can lead the readers to believe that there is a watertight connection between theory and experiments when there is not. Were the experiments in this paper performed using sampling with replacement? It is important to specify this explicitly in algorithm 1. 

3. Why do the authors mention Chen et al. reference for the convergence of SGD? There are several older papers analyzing SGD. In particular, in the convex setting, [this paper](https://arxiv.org/abs/1106.4574) discusses the linear scaling with batch size and when it fails to hold. In the non-convex setting, [this paper](https://arxiv.org/pdf/1912.02365.pdf) shows the optimality of several existing analyses for SGD. Finally, which results are people talking about in the following statement: 
> Accordingly, the practical results for large batch sizes match the theoretical ones

4. It is unclear what is the metric in equation (5). The sentence below the equation as well doesn't explain the metric.

5. It would be good to indicate predicted critical batch sizes for different algorithms in the plots in the experimental section. Furthermore, how was the learning rate tuned for SGD and SGD with momentum while changing the batch size? Ideally, the learning rate and momentum should be tuned separately for each batch size, but from the paper, it seems like a constant learning rate of $10^{-3}$ was used. 
summary_of_the_review: The paper tries to study an interesting gap between the theory and practice of adaptive methods. However, it lacks a clear comparison to existing theoretical results, and the provided guarantees seem weaker than usual stationarity guarantees. The experiments don't have any new insights, as similar experiments exist on much larger datasets in the references cited within the paper. I thus recommend rejecting the paper.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper presents an analysis of adaptive gradient methods with an emphasis on providing insights into the optimal setting of hyperparameters. The presented convergence results suggest settings that are in line with practical observations. From these results, the paper derives a "critical batch size", which minimizes the stochastic first-order oracle complexity.
strength_and_weaknesses: ### Strengths

1. I commend the effort to shed light on the influence of hyperparameter settings in adaptive gradient methods.

2. I found it very interesting to see the experimental analysis regarding the critical batch size (Fig. 2), especially seeing that the SFO complexity for Adam is minimized at a relatively large batch size, in contrast to SGD.


### Weaknesses

1. I partially disagree with the premise of the paper that previous works suggest a setting of $\beta_1\approx \beta_2 \approx 0$. I checked a few of the provided references and, e.g., Zaheer et al (2019) analyze a setting with $\beta_2$ close to 1 (they set $\beta_1$ to 0 though). Moreover, some of the cited papers study a situation where the batch size is increased over time, so one should be careful to transfer conclusions to the setting of a fixed batch size. I would ask that the authors make the discussion of prior work more precise and specify exact results which they think constitute a gap between theory and practice. Overall, I don't think the present version of the paper does a great job of positioning itself in the context of the (admittedly numerous) existing papers analyzing adaptive gradient methods.

2. The analysis is based on the "variational inequality" $K^{-1}\sum_k \nabla f(\theta_k)^T(\theta_k - \theta) \leq \epsilon$ for all $\theta$. I see why this is characterizing a stationary point for $\epsilon=0$, but this seems not very meaningful for $\epsilon>0$. I can just pick some $k$ and set $\theta = c (\theta_k - \nabla f(\theta_k))$ and if $\nabla f(\theta_k) \neq 0$, I can always break the inequality by scaling up $c$. I would like the authors to clarify: To what extent does this inequality really characterize a stationary point? Has prior work used a similar formulation (if so, it should be cited)? Why is it meaningful to establish an upper bound on this quantity?

3. The paper assumes a lot of absolute upper bounds on various gradient-related quantities, most strikingly $\Vert \nabla f(\theta_k)\Vert \leq G$. I know that many previous works have used this assumption, but I still see this very critically since it is completely unrealistic. Usually, it is possible to relax such assumptions. For example, Eq. (7) could be replaced with a bound of the form $\mathbf{E}[\Vert g_k- \nabla f(\theta_k) \Vert^2] \leq \sigma_0^2 + c \Vert \nabla f(\theta_k)\Vert^2$.

4. As the paper rightly points out, Adam is not guaranteed to converge on a convex stochastic optimization problem. The "breaking point" of the convergence proof is that Eq. (8) is _not_ fulfilled by Adam. The present paper goes on to simply _assume_ that Eq. (8) holds for Adam. In my opinion, that is not acceptable. You can analyze variants of Adam that enforce Eq. (8) to hold (AMSGrad) but you can not just _assume_ an algorithm to have a property that it demonstrably does not have. I would like the authors to clarify whether the presented analysis would extend to AMSGrad? If so, the paper should be adapted to reflect that.


### Update after Rebuttal

Thanks for clarifying point (2). This was mostly a misunderstanding on my part and I apologize for that! It seems quite clear in hindsight. Point (4) is still relevant and should be addressed in a possible camera-ready. I will increase my score.
clarity,_quality,_novelty_and_reproducibility: - Clarity: I have several concerns here, detailed in the weaknesses above. The meaning of the variational inequality formulation is not clear to me and is not discussed adequately in the paper (weakness 2). I also think related work needs to be discussed in more detail (weakness 1).

- Quality: I think the theoretical analysis has some two flaws, detailed in weakness 3 and 4 above. The absolute upper bounds on gradient-related quantities should be relaxed where possible. Crucially, one can not simply assume an algorithm to have a property that is provably does not have (weakness 4).

- Originality: To the best of my knowledge, the results are novel in the terms of the insights they provide w.r.t. the hyperparameter settings and the critical batch size.
summary_of_the_review: Given the caveats detailed above, I recommend rejection. I hope that the authors can clarify some of my questions/concerns in the rebuttal phase.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studies the relationship between the batch size and the required step number to achieve the local optimum in the conditions of small constant learning rate and hyperparameters close to 1. The authors also present a critical batch size. These theoretical results are also supported by numerical results.
strength_and_weaknesses: Overall, this paper presents novel results with solid foundations. My concerns mainly exist in the presentation. Some details are missing; some are not clear enough.

1. The presented results on critical results are new to me, though the suggestion of using a small batch size is not new. The current draft needs a more detailed, comprehensive comparison with the related results. As described in Section 1.2, some similar results have been seen in the literature. The authors need to clarify the advances this paper has made more clearly.

2. The proofs are given in the appendices in detail. However, I suggest the authors give a sketch in the main text. Also, the authors need to clarify the significance and difficulty of their proofs in the response and the revised draft.
clarity,_quality,_novelty_and_reproducibility: For clarity and novelty, please refer to point 1 above.

This paper is of fair quality in its current form.


summary_of_the_review: Overall, I recommend "5: marginally below the acceptance threshold." I need the authors to give more details in their responses, and if this paper is accepted, the draft needs a revision.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper analyzes the batch size for fastest convergence of optimization algorithms applied in deep learning. The metric is the total number of stochastic gradient estimations, which is the product of number of iterations and batch size. The optimal point should be in the middle, that both number of iterations and batch size are reasonably big. The proof is given in details and the experiments verify the conclusion.
strength_and_weaknesses: I think this paper treats the theory seriously and gives thorough proof in all details, on a fundamental problem in machine learning. The algorithm covers the most widely used optimization algorithms with tuning parameters such as momentum, adaptive gradient, etc. so is very practical. I have a few questions below.

Critical: This paper proposes the upper bound and minimizes this upper bound wrt batch size. However, I’m not sure if the upper bound of VI is tight, say, whether it’s also a lower bound? Basically you want to minimize the exact rate (in big O) or at least a somehow tight upper bound, rather than a loose one. Does the experiment result exactly align with the upper bound? A figure with both experimental and theoretical "iteration vs. error" curves would justify the point. 

But on the other hand, I think the bound makes some sense. The $1/K$ term is the bias and the $1/b$ term is the variance, but I'm not sure they are exact like both a plain inverse, in big O sense. With the same decomposition of bias/variance, does the bound, by any chance, match the bound for Table 1 of https://www.jmlr.org/papers/volume18/16-595/16-595.pdf? It should also be convincing if the bounds matches previous works' results. 

I would like to see more justification of SFO as a metric. For example, the gradient computation in batches can be parallel, thus intrinsically faster than running more GD iterations that cannot be concurrent. I think it also depends on how many machines you have, so that, in terms of experiments, I like the ones with SFO as y-axis rather than the tables using time as a metric (computation time really depends on the device, like how many computational “units” it has). 

Are the step sizes among different batch sizes the same? And within the algorithm on a same batch size, is the step size fixed? For the latter question, I think ADAM can adapt the step size by itself but one can still vary batch size along the iterations to get a better result. Intuitively, when batch size is smaller, the noise is bigger and one needs smaller steps sizes for the same convergence error target $\epsilon$. A diminishing step size can handle/mitigate the error caused by noise variance, i.e., caused by finite batch sizes, somehow.


clarity,_quality,_novelty_and_reproducibility: I think the paper is novel and written clearly. All the theories are reproducible. I would like to see the authors' response to my questions above to judge its quality/correctness.
summary_of_the_review: I would like to see the authors' response to my questions above to judge its quality/correctness. If they are addressed, I believe the paper is sound and solid. I think the score is 5 or 6 but I feel/expect the above questions can be addressed later and give a 6 here.

=======================

I still have some questions about the tightness but I think it matches the intuition and some other results. But given the proof technique for diminishing step sizes, I would like to tentatively rescore it as 8 (I would say 7 if the tightness issue still remains, and I'd suggest more reasoning about the SFO regarding the computational cost of "parallelizable" or "unparallelizable" steps). I believe diminishing step size is more important than constant step size if the bound is more optimal, since it can also achieve any small error for a non-smooth function and tweak the variance, etc., so I'd like to see it in the paper or appendix.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper attempts to theoretically analyze some empirical observations about critical batch sizes of optimization algorithms. The paper derives some convergence bounds for Adam using a Variational Inequality convergence measure. Based on these bounds, they derive a formula for the critical batch size.

One one hand, reviewers generally feel like there is probably a new and interesting contribution here. On the other hand, they have raised a lot of specific concerns regarding clarity, relationships to prior analyses of Adam, reasonableness of various assumptions, and the meaningfulness of the experimental results. There has been quite a bit of discussion, and the authors have persuaded some of the reviewers on some of the specific points.

However, much of the discussion points at a central concern I have, which is that the contribution relative to prior work isn't stated very clearly. There have been a lot of convergence analyses of Adam and related algorithms, and a lot of analyses of batch size scaling of stochastic optimizers (including the classic Bottou and Bousquet (2007), "The tradeoffs of large-scale learning", Ma et al. (2018), "The power of interpolation", etc., as well as various references the reviewers point out). The papers I just listed don't investigate exactly the same issues (and aren't necessarily the most relevant), but it feels like there needs to be some discussion of what is the current state of knowledge regarding batch size scaling, where current analyses fall short, and how this paper fills the gap.

I also don't feel like I have a clear picture of what we learn from the experiments; the take-aways are never quite stated. I presume it is meant to validate some of the theoretical predictions, but which ones?  From the experiments, the SFO metric also seems to behave qualitatively differently from more traditional notions of batch size which are relevant to practical optimization; e.g., it seems to indicate the critical batch size for SGD is <= 4; this makes me question how practically relevant the analyses are.

Overall, I think there is some promise here, but the presentation seems to require enough cleanup that it should go through another round of review.
justification_for_why_not_higher_score: See above.
Decision: Reject