Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studies the generalization of full-batch gradient descent for strongly convex, convex, and nonconvex smooth but possibly non-Lipschitz functions. In particular, the authors extend the existing results for SGD to full-batch GD in all cases and compare the excess risk bounds. More importantly, the authors derive these results without the Lipschitz assumption, which is customary in the stability analysis. 
strength_and_weaknesses: I believe the main interesting result is regarding the strongly convex case where the number of iterations decreases from $n$ to $\log(n)$. While this is expected (because of the GD convergence rate for the ERM problem), it shows the benefit of full-batch GD in this case.

Regarding the convex case, for the case that the interpolation error is zero, GD and SGD have similar performance, while for the case that the interpolation error is non-zero, full-batch GD leads to $\sqrt{n}$ improvement. However, one should note that full-batch GD requires $n$ times more gradient computation, and so overall complexity is worse than SGD. I would appreciate the authors' comments on this matter. 

Regarding the non-convex case, I am slightly confused by the assumption on learning rate ($\eta_t \leq \Omega(1/t)$). I believe the convergence rate to a stationary point would be very slow in this case. I would appreciate it if the authors comment on the convergence rate under this assumption.  
clarity,_quality,_novelty_and_reproducibility: The problem formation and the results are stated clearly and the summary tables provide a good and clear summary of contributions. 
In terms of originality and novelty, I believe the techniques are close to the Lei & Ying, 2020b paper. 
summary_of_the_review: Overall, I find this paper interesting as it drops the Lipschitz assumption for the generalization analysis of full-batch GD. However, I have two main questions (mentioned above) regarding the convex case's overall complexity and the nonconvex's convergence rate. I would appreciate it if the authors could clarify these two matters (and I am willing to increase my score given the authors' response).
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper provides sharp generalization bounds for the full-batch Gradient Descent algorithm on smooth losses. It builds upon the stability argument and risk decomposition. It derives a generalization error specifically for nonconvex, convex and strongly convex cases with smoothness assumption. 
strength_and_weaknesses: Strength:
The paper provides tighter generalization bounds for Gradient Descent via stability argument, which can serve as basic results for this type of references.
The paper is clearly written, and references are covered sufficiently.

Weakness: 
There are no convincing insights for such bounds. Though the generalization bounds for GD are comparable to that of SGD with much fewer iterations, GD cost much more computation than SGD for each iteration.  Even for the literature where GD achieves the "same" excess risk as SGD, GD requires much more pass of data. There is no sufficient motivation to advocate the use of GD over SGD.



The expectations in many definitions and theorems all have the same meaning. Please do specify what is expected over.
clarity,_quality,_novelty_and_reproducibility: The presentation is clear and easy to follow. The contribution is original.
summary_of_the_review: The paper provides improved generalization analysis for gradient descent for various cases under smoothness assumption. However, the improvement on the number of iterations for GD over SGD is not surprising, which mainly attributes to the less noise in GD and the better convergence rate GD. The paper does not provide insightful implication for practice.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: Summary:
This paper tries to derive generalization bound using stability-based techniques under full-batch gradient descent. The results in this paper do not require any Lipschitz assumption, and the authors consider both convex and non-convex regimes. The techniques used in this paper follows Lei and Ying, where their techniques are mainly used in SGD regimes. This paper generalizes the results into GD regimes. The main difference here is Lemma~18, where the authors show a 1-expansion property for GD. Besides, the authors improve the previous analysis using Thm3. 
Overall, this paper is technically sound and clean, and I would like to see it published in ICLR. 

strength_and_weaknesses: Strength:
1. This paper proposes a generalization bound under GD regimes using stability-based techniques. 
2. Although this paper generally follows the ideas of Lei and Ying (this leads to the relaxation of the Lipschitz), this paper makes some improvements.
3. The authors consider both convex and non-convex regimes in this paper. 
4. The writing is clear and easy to follow. 

Questions:
1. I find that the results in this paper can be deployed in non-convex cases. Could the authors re-claim the technical aspects and difficulties of this paper in non-convex cases compared to Lei and Ying? 
2. The definition of path error (Def3) is for any i. However, I did not find the dependency of i in the notion $\epsilon_path$. Do the authors mean the sup over i, or expectation?
clarity,_quality,_novelty_and_reproducibility: 1. I checked the proofs and statements in the convex part and did not find mistakes here. I did not check all the proofs in the non-convex part, but I believe that most statements are correct. 
2. I cannot evaluate the technical contributions of this paper. This stops me from giving a better score. The authors may need to restate their technical contributions compared to the existing papers. 
3. The paper is well-written.
summary_of_the_review: Overall, this paper is technically sound and clean, and I would like to see it published in ICLR.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This provides us with expected generalization and excess risk guarantees for symmetric, deterministic algorithms on smooth loss functions. These bounds depend on the $\ell_2$ expected output stability, the expected optimization error, and the model capacity (hence, Theorem 3 and its proof are interesting contributions).

The bounds are specialized to full-batch gradient descent (GD) in the case of non-convex, convex, and strongly convex functions. Interestingly, the resulting bounds from this paper show that:

* When the loss is convex, GD can reach an expected risk in $\mathcal{O}(1/\sqrt{n})$ in $T=\sqrt{n}$ iterations, as opposed to SGD that requires $T=n$ iterations, albeit with a different choice of the learning rate. 
* When the loss is convex, GD can also reach an expected risk in $\mathcal{O}(1/n)$ in $T=n$ iterations like SGD with the same learning rate.
* When the loss is strongly convex, GD can reach a risk of $\mathcal{O}(\sqrt{\log n}/n)$ in only $\Theta(\log n)$ iterations, while SGD requires $\Theta(n)$ iterations to reach a risk in $\mathcal{O}(1/n)$.

At the core of the proofs for the bounds on full-batch GD is the path error, which is defined as the cumulative sum of the squared norm of the gradient over iterations, weighted by the learning rate. This is also an important contribution, that is in line with other works from the literature in the idea that the norm of the gradients is one of the keys to understanding the behavior of these algorithms.
strength_and_weaknesses: **Strengths**

* The paper is generally well written and easy to follow. It feels that this would be true even for people that are only somewhat familiar with these kind of results.
* The results for full-batch GD in all of the settings are stronger than previously known in the literature. They show that GD can converge faster or equally fast and to better or equal rates than SGD for smooth and both convex and strongly convex losses (which is in line with current experimental results).
* The appearance of the path error in their proofs and the way it is bounded is interesting and provides insights on what makes full-batch GD perform as it does.

**Weaknesses**

* As mentioned in the text after Theorem 3, (4) is essentially the tightest version of Theorem 2 b) of *[Lei and Ying 2020b]*. However, it would be nice to clarify that this is only up to constants, since the first term in (4) would be divided by 2 and the second by 4 if one were to obtain the variant in that paper.
* In the remark about the particularization of Theorem 3 under the Polyak-Łojasiewicz (PL) condition, it would be nice to write what PL stands for and to cite the original references from *[Polyak 1963]* and *[Łojasiewicz 1963]* or the paper that coined the term *[Karimi et al. 2016]*. Also, the way the discussion after (5) is written, although correct, is a little confusing. Could you please re-write or explain further the arguments under the interpolation regime and $\beta \leq n \mu / 4$?
* After Corollary 8 it is said that (9) matches bounds in prior work, including information-theoretic bounds for the SGLD algorithm and it cites *[Wang et al. 2021b]*. I could not see to which bound the text refers after reading the reference, could you point that out and, in case that it needs some further modification, explain that?
* Throughout the paper it is said that the only assumptions are smoothness (and after convexity and strong convexity) of the loss, and that the algorithm is symmetric and deterministic. Then, apparently dimension-independent complexity of the generalization and the risk are provided. However, the bounds depend on the standard term $\mathbb{E}[\lVert W_1 - W_S^\star \rVert_2^2]$, which usually depends on the dimension and is only in $\mathcal{O}(1)$ when the parameter space is bounded by some constant.\
An important element for the bounds of gradient methods under the Lipschitz/smooth assumptions is that they are dimension-independent when the parameter space is bounded. This is also the case here and I believe it should be mentioned clearly before showing the complexity terms that can be derived from these bounds.

* There are some claims that I did not understood. Please, could you explain/justify them to me/in the text a little more?

  * Why does (51) hold? I understand that you use the quadratic growth property in $\lVert A(S) - \pi_S \rVert_2^2$, but I don't see why that would hold for $\lVert \pi_{S^{(i)}} - \pi_S \rVert_2^2$. Both $\pi_S$ and $\pi_{S^{(i)}}$ are projections, of $A(S)$ and $A(S^{(i)})$, but not the projections of each other.
  * Why does (89) hold?
  * In (101) you use $1- \frac{\eta_j \gamma}{2}$ and then you replace that in the next array of equations for $(1-\eta_j \gamma_{loo})$. Why can you do that?
  * Why is true that $\Lambda(\gamma_{loo}, T) \leq 2 T / \beta$?
  * How do you obtain the third inequality of page 29? I am particularly surprised by the $\mathbb{E}[R_S(W_S^\star)]$ before the max inside the squared root. 

**References**

*[Polyak 1963] Gradient methods for minimizing functionals (in Russian).* \
*[Łojasiewicz 1963] A topological property of real analytic subsets (in French).* \
*[Karimi et al. 2016] Linear convergence of gradient and proximal-
gradient methods under the Polyak- Łojasiewicz condition.* \
*[Lei and Ying 2020b] Fine-grained analysis of stability and generalization for stochastic gradient descent.* \
*[Wang et al. 2021b] Analyzing the generalization capability of SGLD using properties of gaussian channels.*

clarity,_quality,_novelty_and_reproducibility: * **Clarity**: The paper is clear and well-written.

* **Quality**: The quality of the paper is good. The ideas are interesting and well-executed.

* **Novelty**: The first theorem (Theorem 3) is not novel, but the proof is. Then, the theory for full-batch GD (the main part of the paper) is novel.

* **Reproducibility**: \
*Theory*: I reproduced all the proofs except for the questions that I placed the authors in the weaknesses. \
*Experiments*: There are no experiments.
summary_of_the_review: This paper focuses on bounding the expected generalization and excess risk for symmetric, deterministic algorithms for smooth losses. In particular, it focuses on full-batch gradient descent (GD).

The paper provides an alternative proof for general algorithms and then generates new proofs for full-batch (GD). These proofs depend on a quantity (path error) that depends on the norm of the loss gradients, which has been shown to be important for this algorithm generalization in the past. The bounds are sharper than previous bounds in the literature and show that GD can obtain better or equal rates than stochastic gradient descent, providing some understanding to recent experimental results.

In general, I believe the theory is interesting and the results are a valuable asset for the community. Hence, I recommend acceptance. Nonetheless, I would appreciate it if the questions raised in the weaknesses were addressed so that all the theory could be verified and if the following minor comments were taken into account. 

**Minor comments and nitpicks that did not impact the score of the review**

* $R_S^\star$ is never defined, I assume it is $R_S(W_S^\star)$.

* In Theorem 7, I believe it would be clearer to say that $\eta_t \leq C/t$ where $\beta C \leq 1$, and then let $\epsilon \triangleq \beta C$.
* In Theorem 12, you forgot to write that $W_{T+1} \equiv A(S)$ and $W_{T+1}^{(i)} \equiv A(S^{(i)})$.

* In the proof of Lemma 15, it seems that in the part where $\eta_t = C/t \leq 2 / (\beta + \gamma)$, you forgot a jump of line in the inequality in the third line of the array of equations and inequalities.

* Sometimes the notation for the mathematical expressions changes. For instance, you use "The inequality (8)" in page 6 and many times in the appendix you don't use the parenthesis. Could you please homogenize the notation in this regard throughout the paper?

* The equation before inequality (37) should be $Ce^{2C\beta}T^{2C\beta} \Big(1 + \frac{1}{2C\beta} \Big) - \frac{e^{2C\beta}}{2\beta}$. 

* In Appendix D: in the third line it should be "generalization error bounds for symmetric and smooth algorithms".

* In the proof of Lemma 18, it should $\sum_{j \in \mathcal{J}} f(W,z_j)$ that is convex and then the gradient of that, $h(W)$ that is $\beta |\mathcal{J}|$-Lipschitz. 

* It is not immediately clear that $\epsilon_{\textnormal{opt}} \leq 3 \geta \mathbb{E}[\lVert W_1 - W_S^\star \rVert_2^2] / T$. It would be helpful to say that we obtain that from Lemma 20 where we see that $\epsilon_{\textnormal{opt}} \leq 8/3 \geta \mathbb{E}[\lVert W_1 - W_S^\star \rVert_2^2] / T$

* In the last array of expressions from appendix E, the second to last expression should be an inequality, not an equality (note that the multiplicative factor of 3 was not present in the first term of the second factor inside the square root).

* In page 29, after (105), I believe you forgot to take into account the factor 2 in that was present in $\sqrt{2 \beta \Lambda(\gamma_{loo}, T)}$. Then, in all equations following the first $\min$ is of $\frac{2\beta}{\gamma_{loo}}$ and $2T$. This carries over and I believe the final result should have the multiplicative factor $8 \sqrt{6}$ instead of $8 \sqrt{3}$.

* Sometimes the introduced extra notation harms the readability of the text instead of helping it. For instance:

  * $\Delta_T$ is used in Theorem 14, but never introduced. 
  * The incorporation of $\textnormal{m}(\gamma_{loo})$ is used in only one equation to quickly move to $\textnormal{m}_{n,\gamma_{loo}}$, practically having no impact in the proof (page 30).

* Some expressions are numbered and some are not. This is okay and standard when the numbered equations are those that are referred to later on. Could you choose either to number all of them or only those that are referred to, please?
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper provides a wide array of stability-based generalization analyses of gradient descent.  While the reviews were somewhat mixed, overall the internal discussions focused on a variety of new contributions within the proofs, and therefore I am happy to recommend acceptance for this paper.
justification_for_why_not_higher_score: Reviews are highly mixed
justification_for_why_not_lower_score: Overall the most active reviewers were satisfied and come out in support of the paper, and therefore I find it natural to accept.
Decision: Accept: poster