Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: Update: I raised my score to 5 after reading the authors' rebuttal.  

--------  
The paper studies gradient regularization, a technique that is often associated with improved generalization in deep learning. The authors consider a finite-difference approximation of gradient regularization that not only decreases the computational cost but also is shown to improve generalization empirically. This effect is proven to hold for diagonal linear networks, which can be seen as a very simple example of neural networks. The authors also validate their claims using numerical experiments on neural networks.
strength_and_weaknesses: ## Strengths  
1. Gradient regularization has been popular recently and the paper might be of interest to the conference attendees.
2. The finite-difference approximation is indeed cheaper to calculate than the full gradient with backpropagation.
3. Some of the theoretical claims are checked numerically.

## Weaknesses  
1. The overall intuition behind the efficiency of finite-difference approximation is not clear. In general, finite differences yield very noisy estimates of gradients that poorly scale with dimension, and it is not explained why in this case this approximation happens to be better. As far as I can see, this issue, which is normally the main counter-argument against finite-differences, is not addressed in the paper.
2. The reduction of double backpropagation to forward passes is not a critical improvement. It is of course nice to reduce the training time, but the impact of this change is limited and is only worth it if all other factors (such as variance) remain the same.
3. The diagonal linear network is mostly a toy example that no one uses in practice. On top of that, the derivation for this problem is mostly the same as done in prior works. A more general theory, for instance, for locally smooth objectives, could be of more interest.
clarity,_quality,_novelty_and_reproducibility: I did not understand the following aspect: why is $\frac{\gamma}{2}R(\theta)$ used in equation (1) instead of $\frac{\gamma}{4}R(\theta)$? If I understood correctly, the latter was shown to correspond to the implicit bias of SGD in equation (20) of (Smith et al., 2021) when $\gamma$ is the stepsize.

summary_of_the_review: All in all, this paper presents a number of small results about finite-difference schemes for gradient regularization. Each result on its own seems to be quite small. The results do not become much stronger together either, since they are on orthogonal topics: numerical efficiency, implicit bias on diagonal linear networks, and the relation to other deep learning techniques. The work seems to lack depth in its theoretical investigation, which makes me suggest a rejection.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the algorithmic behavior of gradient regularization in deep learning. In particular, this paper considers three versions of practical implementations of the gradient calculation of the gradient regularization term: forward finite-difference, backward finite-difference, and double backpropagation. The authors theoretically investigate the algorithmic bias of these three implementations on a diagonal linear network and prove that gradient regularization has an implicit bias to find the solution with potentially better generalization. Finally, the authors illustrate the close connection between finite-difference GR and other training methods such as SAM and the flooding method. 
strength_and_weaknesses: Strength:
1. This paper demonstrates certain advantages of using finite-difference computation over double backpropagation on the gradient regularization term.
2. This paper provides a theoretical analysis to study the implicit bias of gradient regularization on a diagonal linear network and shows that GR can potentially lead to better solutions.
3. This paper further builds a connection between GR and other learning methods.

weakness:
1. The theoretical analysis is not clear to me. In particular, Theorem 4.1 and  Proposition 4.2 only give bounds on the final solutions found by the algorithms, while their sharpness is not fully justified. So I am still not clear what’s the exact quantity of the solution. 
2. Following the previous comment, why the final solutions found by F-GR will be smaller than $\alpha_0$? Does it require $\alpha_0$ to be positive?
3. I also cannot understand why Theorem 4.1 suggests that GR tends to select the L1 solution and why the L1 solution has a better generalization performance. It may need a rigorous theory to connect the implicit bias of GR and the generalization performance.
4. When performing experiments on CIFAR, do you add standard weight decay regularization? More details of the experiment setup should be added.

clarity,_quality,_novelty_and_reproducibility: This paper has good clarity, quality, and novelty. The theoretical analysis is new and is useful for understanding the role of gradient regularization.

summary_of_the_review: Overall this is a good paper. However, both the theoretical and experimental parts need to be improved according to my comments in the weakness section.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: GR is a method that penalizes the gradient norm of the training loss during training. However, computing the gradient of GR objectives leads to Hessian evaluation, which is computationally expensive. The paper attempts to accelerate the gradient regularized (GR) training by finite-difference approximations. In particular, forward and backward finite-difference methods are discussed. Theoretically, the implicit bias of GR in diagonal linear model is explicitly characterized. The paper also connects GR to other algorithms based on iterative ascent and descent steps for exploring flat minima.
strength_and_weaknesses: ==================== Strength ====================

The paper targets at an important problem of circumventing expensive Hessian computations in regularized training. Regularized training is essential to the success of modern learning models and gradient regularization has close ties to the flatness of minima and generalization properties. The finite-difference method resolves the computational issue and also achieves good -- even better -- performance. This should be of high interest to practitioners.

The paper is well motivated and clearly written. The theoretical results seem to be correct.

The scope of the paper is actually broad; it aims to provide a comprehensive understanding of GR, touching its implementation, implicit bias, and connection to other popular methods.

==================== Weakness ====================

Section 4 is rather toy and seems to lack technical contributions (compared to Woodworth et al. (2020)).
clarity,_quality,_novelty_and_reproducibility: How can we better understand Theorem 4.1 as GR has an implicit bias to select the L1 solution? From the closed-form expression, we find an exponential shrinkage of $\alpha$. While for L1 solution, the coefficient should be sparse if I am correct.

It is interesting to see why forward finite-difference method performs better than the backward one. Meanwhile, different discretization approximation methods have very distinct performance dependence on learning rate; it would be helpful to provide any intuition behind these observations. Does the theory in Section 4 justifies the observation in Section 3.3?

Apart from aforementioned questions and concerns, the paper is easy to follow, and the results are correct.
summary_of_the_review: I am leaning towards a positive rating, due to the clarity and the broad scope of the paper.

A major criticism might be Section 4 is a bit disconnected, as the implicit bias does not provide deeper understanding of the finite-difference implementation of GR. This is partly due to the limited analytical tools. Therefore, I would recognize Section 4 as some understanding of GR. In this sense, the concept in the paper is broad, while the inner coherence can still be improved.

==================== Post author response ====================

Thank you for addressing my concerns and I am willing to keep the initial rating. A minor point is that I am still not very clear what are the technical contributions in theory. The analysis handles the new term $\Psi_1$, but what are the new proof details or tools leveraged (developed) in paper? Providing these details would be even more helpful.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The work considers a gradient norm regularizer and the implicit bias afforded by the numerical methods for computing the regularization terms, namely, (1) forward finite difference, (2) backward finite difference, or (3) double back propagation. It was suggested that forward finite difference with a relatively large time step gives the best generalization among the three methods. Additionally, the paper discussed some theory for this phenomenon using a diagonal linear networks. Finally, some connections to two existing algorithms, sharpness-aware-minimization and flooding method, are discussed. 
strength_and_weaknesses: # Strength 
1. Overall I find the writing is good and most of the presentation is clear. 
2. It is very novel to my knowledge the observation/conjecture that a finite difference scheme with a positive and large time step might bring additional implicit bias. 
3. I like the discussion about the connection of the authors' finding and the existing SAM, flooding methods. I think it brings some interesting insights that could potentially unify several existing methods that were developed from different areas. 

# Weakness

The Strength#2 is too surprising to me such that I have to ask a lot of questions to be fully convinced. 
1. Section 3.3. Could you report the stand deviation/error bar for the data obtained for MLP and ResNet-18? 

2. I checked Table S.1 that presents test accuracy for WRN, where some error bar is provided. However, the difference between the three schemes is too small to be interesting to be honest (most of the cases the differences is O(0.1%) in terms of accuracy).

3. Figure 3 is interesting, but is hard to interpret as the exact numbers are hard to read. 

4. Note that compared to DB, finite difference introduces an additional hyper parameter $\\epsilon$. Would you say that the small advantage of finite difference is actually due to the additional flexibility for tuning the new hyperparameter? I would love to hear some discussion on this issue, because the improvement does not seem to be significant so I think it is very likely caused by tuning the hyperparameter. 

The following questions are about the theory, which I find not been presented as clear as the other part of the paper. 

5. Theorem 4.1. Assumption (iiI) could use more discussions. First of all, $L(\\cdot)$ is a function of a $2d$-dimensional vector, why it can be integral over a real line? Secondly, it requires the upper and lower bound for the integral to be independent of small $\\gamma$ and $\\epsilon$. Why this is related to the convergence speed of the dynamics with/without GR?

6. Can you briefly discuss how large the quanatity $\\epsilon$ and $\\gamma$ could be in Theorem 4.1? Because in the follow-up discussion you have mentioned that a larger $\\epsilon$ leads to a stronger regularization. I am just wondering how much changing on the bound is allowed to happen. 

7. Since Theorem 4.1 only provides upper bound on $\\alpha$, this does not necessarily support the follow-up discussion that a larger $\\epsilon$ leads to a stronger regularization. Note that a larger $\\epsilon$ only leads to a smaller upper bound on $\alpha$, which does not necessarily mean that $\alpha$ itself is decreased. Indeed, Eq(12) provides another upper bound on $\\alpha$ that does not decrease when $\epsilon$ increases. So at least one can take the minimum of the bounds in Eqs(11) and (12), which is still a valid upper bound on $\alpha$. Would you say that this improved upper bound is still decreasing when $\\epsilon$ increases? 

8. It seems that $c$ in Eq(12) is a vector? But $c\^\*$ in Eq(11) is a constant? I am just confused by the notations, and I find the follow-up discussion after Proposition 4.2 is hard to interpret because it mentioned "the average over entries" of $c$.
 

# Typos
- A lot of figures are not correctly numbered. Please double check. 
- Theorem 4.1, assumption (ii), upper -> upper bound.
- The comments on Figure 5 might have some typos. It seems to me that the loss gets close to the flood level at about the $100$ epoch instead of the $10$-th epoch. 






clarity,_quality,_novelty_and_reproducibility: Clarity is good except for the theory part. 

Quality could have been improved by providing more details on the experimental results like std. 

Novelty is very good. In fact it is too good and requires a careful examination in my prespective. 

Reproducibility is fine. 
summary_of_the_review: Please see above. Due to the mentioned issues I would like to keep my scoring conservative for now. I will consider increasing my score if my questions receive proper replies. I am being conservative because some of the results are quite surprising to me.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: Gradient regularization was proposed to improve generalization by finding flatter minima in previous work.  The authors propose a computationally efficient approximation to gradient regularization, using a finite-difference method, evaluate it experimentally, and analyze its effect on the inductive bias in the case of diagonal linear models.

The consensus view was that the paper has some interesting ideas, but that the experiments did not strongly support the claims of the paper, that the theoretical results were difficult to interpret and not clearly explained, and that the theoretical analysis was somewhat incremental.

justification_for_why_not_higher_score: Please see the above.
Decision: Reject