Implicit Bias of Gradient Descent for Logistic Regression at the Edge of Stability

Summary

The authors study gradient descent for logistic regression on linearly separable data, with a focus on large stepsizes, and in particular stepsizes in the edge of stability (EoS) regime. With the logistic loss, they show that for *any* positive stepsize, the empirical loss is minimized as the number of GD steps increases, and the limit direction maximises the margin. Explicit rates are given. The authors also provide counterexamples for the exponential loss: if the stepsize is too large, the loss diverges and the iterates cannot converge to the maxmargin direction.

Strengths

The authors study a hot topic (Edge of Stability) on an overall very well studied problem (logistic regression). In these lines of work, the results are rather strong: proving convergence for any stepsize, beyond those that provide a nice descent lemma, seemed like a challenging problem, and this forms a strong contribution. The other contributions (comparison between logistic and exp. losses, , the technical analysis) are also independently of interest. Overall, the paper is neatly written and easy to follow.

Weaknesses

There are no main concerns or weaknesses to this paper, in terms of results or presentation. However, if I had to give one, I would say that since the implicit bias is the same whatever the stepsize is (it is thus the same for infinitesimal ones and for stepsizes at the EoS), Theorem 1 extends previous results on the implicit bias of logistic regression, but does not give insight onto what happens at the edge of stability, and what drives generalization to increase. Could this be commented by the authors ? Also, here are some recent references that study the EoS phenomenon on other problems, and that should be mentionned in the related works (they are all quite recent): In contrast to the logistic regression problem studied in this submission, large stepsizes on regression problem lead to different solutions for GD and SGD when at the edge of stability: *(S) GD over Diagonal Linear Networks: Implicit Regularisation, Large Stepsizes and Edge of Stability*, Even et al. 2022. The following paper also studies *scalar* linear networks (a scalar parametered by a product $xy$), as done in Ahn et al. 2022a,b and Zhu et al. 2022 cited in the submission, but in a more precise way: *Gradient Descent Monotonically Decreases the Sharpness of Gradient Flow Solutions in Scalar Networks and Beyond*. Finally, *SGD with Large Step Sizes Learns Sparse Features*, Andriushchenko et al. 2022 study large stepsizes SGD and generalization (more experimental piece of work).

Questions

I have no further questions.

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed 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

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

No such limitations.

Summary

This paper analyzes the convergence and implicit bias of logistic regression on linearly separable datasets with arbitrarily large step sizes. The paper proves that gradient descent converges _for any_ constant step size, even those which result in non-decreasing loss curves. Similar to the regime of small step sizes, gradient descent converges along the direction of the max-margin linear separator. In contrast to logistic loss, the paper proves that for exponential loss there exist datasets and step sizes where the optimizer fails to converge, shedding light on why logistic loss may be preferable in practice over exponential loss.

Strengths

- It's interesting (and far from obvious a priori) that GD with _any_ constant step size will converge. - The separation between logistic and exponential losses sheds light on why the former is preferred in practice (since both losses are equivalent under the small step size regime studied in previous works) - The separable / non-separable orthogonal decomposition seems like it might be useful for other analyses of logistic regression on separable datasets.

Weaknesses

- Minor: would Assumption 3 hold if the dataset were the last-layer features from a neural net has undergone neural collapse, or would such a dataset not satisfy assumption 3?

Questions

- Could you include some numerical examples of convergence at extremely large step sizes? I am curious to see what the loss curve looks like. - The following recent paper should be discussed: Chunrui Liu, Wei Huang, and Richard Yi Da Xu. "Implicit Bias of Deep Learning in the Large Learning Rate Phase: A Data Separability Perspective." Applied Sciences, 2023. https://www.mdpi.com/2076-3417/13/6/3961 The paper does not seem to be on arxiv, and the venue is not a standard one ... nevertheless, the paper is quite related. In their Proposition 1, that paper argues that for logistic regression on _non-separable datasets_ (or, more generally, for any strongly convex optimization problem), gradient descent fails to converge for large enough step sizes.

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

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

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

n/a

Summary

The paper studies the convergence of gradient descent with large step sizes beyond the classical stepsize suggest by smoothness-based convergence. Across the iterates, the risk here exhibits non-monotonic behaviour and yet converges in the long range. To show these phenomenon, the paper rigorously studies the gradient descent with large step-size in the case of logistic regression with linearly separable data.

Strengths

a) The paper studies logistic regression in the case of separable data. Even in this simpler case, the authors prove a very strong result. It is shown that gradient descent with **any** constant stepsize converges. b) For gradient descent with any step-size, the implicit bias towards the max $\ell_2$-margin solution is shown. c) A novel proof technique was introduced to handle any stepsize and it was clearly presented with a simple example. In contrast to existing works, the implicit bias is shown which leads to convergence in risk.

Weaknesses

a) The proof is tailor made for linear regression and does not work beyond that for any convex functions.

Questions

a) In the case of exponential loss, it is shown that it can diverge with a large stepsize for a simple example. Do you think there exists a sub-class of problems where exponential loss can converge with any step size?

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

3 good

Contribution

3 good

Summary

This research investigates the convergence and implicit bias of constant-stepsize GD for logistic regression on linearly separable data in the EoS regime. The authors assert that despite local oscillations, the logistic loss can be minimized by GD with constant stepsize over a long time scale. Experiments on neural networks and logistic regression verify the theory and illustrate the non-monotonic convergence and implicit bias of GD.

Strengths

- Provides novel theoretical analysis of GD allowing constant step sizes, complementing existing theories requiring small step sizes. This better matches practical deep learning where large steps are used. - Establishes implicit bias results for GD with any constant step size. Shows GD aims to maximize the margin regardless of step size. - The analysis technique of decomposing GD iterates into orthogonal components is innovative. It allows handling large step sizes that cause loss oscillations. - Experiments on neural networks and logistic regression align with theory and illustrate non-monotonic convergence and implicit bias. - Shows logistic loss is better behaved than exponential loss for large-stepsize GD, providing practical insights.

Weaknesses

- The analysis is limited to logistic regression on linearly separable data. Extending it to more complex models like neural networks is not clear. - Some assumptions made, like linearly separable data and non-degenerate support vectors, may be restrictive and not hold in practice. For example, wrongly labeled samples are common.

Questions

How to define linearly separable in neural network literature? It is clear that when you use a large learning rate, the neural network goes far away from the linear regime. How can you make a compensation to use the current model to understand the non-linearity in neural networks?

Rating

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

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

2 fair

Limitations

This work makes valuable theoretical contributions but has limitations in terms of connection to practice. Extending the analysis to address these limitations remains an open challenge.

Summary

This work investigates the implicit bias in linear regression with logistic loss with large learning rates. It shows the convergence result of logistic loss for any learning rates, as long as an counter-example of exponential loss to show the gap between these two losses.

Strengths

1. The motivation and setting are good: large learning rates (i.e., Edge of Stability) are a rising topic recently. As pointed out by the authors, it requires reconsideration of previous results of implicit regularization with small learning rates. To my knowledge, this work is the first to redo one of the bias results in the standard setting. 2. The gap between logistic and exponential losses is good: typically implicit-bias works handle these two similarly, but this work shows that logistic loss can contain arbitrarily large learning rates while exponential loss has an upper bound.

Weaknesses

1. The covered setting is somehow simple in lack of detailed discussions of what impact logistic loss + large learning rates have on more complicated settings possibly. For instance, does the max-margin bias in deep homogenous model (Lyu and Li) hold any more? This kind of impact could be verified with visualized experiments, with the theoretical development left as future works.

Questions

As above in weakness. Typos & minor suggestions: 1. below 299: it is $\nabla G$ instead of $G$ in the inner product. 2. in Figure 2, the bound of $2/\eta=0.2$ can be plotted in a more clear way, such as log.

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

3 good

Presentation

3 good

Contribution

3 good

Limitations

N/A

Reply to Author Rebuttal

Q1. I apologize for the overlook it should have been logistic instead of linear. Thanks for the clarifications.