The Implicit Bias of Adam on Separable Data

Summary

The main focus of this paper is on the implicit bias of Adam for a single layer linear model which performs binary classification on separable data. In particular, assuming a zero stability constant $\epsilon$, this paper reveals that Adam finds the solution that achieves maximum-$\ell_\infty$-margin and characterizes the convergence rate for different classes of learning rate. This implicit bias is different from the $\ell_2$-norm minimization solution obtained by previous work which does not assume $\epsilon = 0$.

Strengths

- This paper is clearly written and well-organized. It is easy and clear to follow the argument and motivation of this paper, e.g., the proof sketch makes it easy to follow the way how the theoretical conclusion is developed. In addition, to me, the introduction of the related works are comprehensive and clear. It also clearly summarizes the difference between this paper and related works. - The settings and results of this paper are new compared to previous works, i.e., previous works showed an $\ell_2$-norm solution implicit bias of Adam on separable data while this paper reveals an $\ell_{\infty}$-norm implicit bias when the stability constant $\epsilon$ is zero.

Weaknesses

Despite the novelty of the theoretical claims, I still have several concerns, which I will discuss in the following. 1. Removing the stability constant $\epsilon$ makes the approach of this paper fails to characterize the influence of it, which, though being small, still has non-negligible effect, e.g., [1] observed that Adam with an $\epsilon$ that is too small does not even converge in certain circumstances. Treating $\epsilon$ as 0 seems a bit rough to me. In addition, [2] showed that Adam minimizes the interpolation norm of gradients that depends on magnitudes of various hyper parameters including the stability constant $\epsilon$ (although [2] did not specify the types of loss functions and model architectures). [1] claimed that Adam with nonzero $\epsilon$ converges to $\ell_2$-norm solution, which is also verified by extensive experiments. As a comparison, this paper showed that both Adam with $\epsilon=0$ and with a non-negligible $\epsilon$ do not converge to the aforementioned solutions (line 210). In this sense, it seems that the conclusion reached by this paper contradicts with those derived by [1, 2]. Therefore, in my view, it would be better to start with a non-zero $\epsilon$ and let the case with $\epsilon=0$ be a special case to better capture the effect of the $\epsilon$ on the implicit bias. 2. This paper only considers a simple setting: the model is only a one-layer linear model and there is no stochastic sampling noise which is typically necessary in practice. As a comparison, authors of [1] have already studied Adam on separable data for homogeneous models, which can cover the single layer model of the current work as a special case. Thus excluding the stochastic sampling noise in the current work is kind of unsatisfying to me since the model is already a simple one. In addition, I think that the authors of the current work should at least repeat the experiments conducted in [1] (such as those for homogeneous neural networks) to further support their theoretical claims, especially considering that the authors claimed in line 210 that their results are more accurate than those of [1]. **Reference** [1] Wang et al. The implicit bias for adaptive optimization algorithms on homogeneous neural networks. [2] Cattaneo et al. On the Implicit Bias of Adam.

Questions

1. Could the authors explain the contradiction and connection with previous works? Is it possible to start with a non-zero $\epsilon$ and let $\epsilon=0$ be a special case? 2. How will adding stochastic sampling noise affect the implicit bias?

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

I do not find a separate limitation section in the main part. In my view, removing the stability constant is a bit rough. This makes the approach presented in this paper fail to capture how the implicit bias of Adam changes for different values of stability constant. The societal impact is not applicable to this work as it focuses on theoretical parts of Adam.

Summary

This paper examines the implicit bias of the Adam optimizer in the context of linear logistic regression, demonstrating that it converges to the maximum $\ell_\infty$-margin solution under certain mild conditions. The authors note that omitting the stability constant in Adam updates results in a different implicit bias than gradient descent, with or without momentum, which converges to the maximum $\ell_2$-margin solution. They also explore various decreasing learning rates, showing that Adam's margin converges at a polynomial rate, which is faster than that of gradient descent. Additionally, they provide numerical experiments that support their findings.

Strengths

- Understanding why Adam performs better than GD in several settings is an important problem and this work takes an important step towards this by showing that Adam has a different implicit bias than GD in the linear logistic regression setting. - Overall, the paper is well-written and easy to follow. The proof sketch in Section 6 is explained well.

Weaknesses

- The paper does not present results for a fixed learning rate and only considers a set of decreasing learning rates. - The discussion in lines 50-52 and after Corollary 4.7, comparing the rates of Adam and GD, should also comment on the convergence rates for GD with adaptive learning rates (e.g., normalized GD) which have been shown to converge faster (see [1] and related work) than GD. - (Minor) In Assumption 4.3, ‘non-increasing’ should be ‘decreasing’ or ‘diminishing’. - The results in prior work on implicit bias of GD are global (hold for any initialization), whereas the results in this paper require an assumption on the initialization (Ass. 4.2). Based on the discussion following this assumption, it might be better to state an assumption on the data and then show that the condition on the initialization holds as a Lemma. - The paper does not comment on how optimal the obtained rates in Corollary 4.7 are. **References:** [1] Wang et al., Achieving Margin Maximization Exponentially Fast via Progressive Norm Rescaling, 2023.

Questions

Can the authors comment more on why considering the stability constant $\epsilon=0$ makes the setting more challenging? I understand the motivation in lines 105-107, but it is unclear what the challenge is since the accumulated second-order moments would be non-zero.

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

There is no potential negative impact of this work.

Summary

In this work, the author studies the implicit bias of Adam optimizer for a single layer neural network on separable data. The author's work suggests that, compared to the implicit bias of gradient descent which is the max $ \ell_2 $ margin solution, Adam solution converges to the maximum $ \ell_\infty $ margin solution. For this work, authors take both exponential and logistic loss and find that the convergence speed is on a polynomial order. In order to confirm the results, the authors perform experiments on synthetic datasets for binary classification tasks and confirm Adam’s convergence to the $ \ell_\infty $ margin comparatively.

Strengths

The work is novel (to the best of my knowledge) and interesting as the study of implicit bias of Adam could have further implications in characterizing the difference in optimization behavior of Adam vs SGD in practical scenarios. The assumptions of the work have been clearly presented and seem reasonable. With regard to the $ \epsilon $, while theoretical results are not provided, the authors include convincing experimental illustrations to convince me of the assumption. I also appreciate the well written proof sketch which helps convey the ideas

Weaknesses

At the moment, I have some concerns with the paper which are more fit to be discussed as questions.

Questions

1) Can the authors expand on how they arrive at the right side of inequality after line 292 using 6.1 ? Perhaps take me through the inequality step by step ? 2) Can the author provide some comments regarding the independence of convergence in the case of $ a = \frac{2}{3} $ from $ \rho $ ? Is there some intuition with regards to the boundaries and case on $ a $ ?

Rating

7

Confidence

3

Soundness

3

Presentation

4

Contribution

4

Limitations

None

Summary

This paper studies the implicit bias of the Adam optimizer for logistic regression on linearly separable data. The authors prove that Adam converges to the linear classifier with the maximum $\ell_\infty$-margin. This result contrasts with the classical results on (stochastic) gradient descent (with or without momentum), which converge to the maximum $\ell_2$-margin solution.

Strengths

- The authors theoretically study a popular yet not well-understood optimization method, Adam, in the context of a well-studied classical problem: logistic regression on linearly separable data. This offers a solid and insightful contribution to understanding Adam. In particular, distinguishing Adam from (S)GD with/without momentum on this classical problem is a very interesting result. - The technical contributions are also of independent interest, as they prove the results for Adam without relying on the stability constant (which is closer to practice) and use mild assumptions. - The paper is well-written and easy to follow. The proof sketch provides a clear and comprehensive overview of the proof of the main theorem.

Weaknesses

There are no major concerns about this paper. Below are minor comments and some areas for improvement: - The paper does not provide an intuition behind why Adam achieves the maximum $\ell_\infty$-margin solution, in contrast to GD which achieves the maximum $\ell_2$-margin solution. It would be great if the authors could offer insights on how the $\ell_\infty$-margin arises instead of the $\ell_2$-margin, for example, through a warm-up analysis with SignGD ($\beta_1=\beta_2=0$) or RMSProp ($\beta_1=0$). One way to provide an intuition is as follows: Gunasekar et al. (2018) proved that steepest descent converges to the max-margin solution, implying that SignGD (steepest descent w.r.t. $\ell_\infty$-norm) converges to the maximum $\ell_\infty$-margin solution. Since SignGD is known to be a good proxy for Adam, this may offer an insight into why Adam converges to the maximum $\ell_\infty$-margin solution. - The authors claim that the bounds in Corollary 4.7 are derived under worst-case scenarios and argue that this is why, in practice, we often observe margins converging faster than the bounds in the corollary. However, this statement lacks supporting evidence. The paper should prove that the rate of convergence is tight. Otherwise, the observed faster convergence of margins in experiments might simply indicate that the bound is not tight enough. - Some sentences, including those in the abstract, use the term "convergence" unclearly. For example, in the abstract, "this convergence occurs within polynomial time" does not indicate the objective (the normalized $\ell_\infty$-margin in this case) of convergence. This could be confused with other notions of convergence, such as convergence in direction (i.e., $\frac{w_t}{\lVert w_t \rVert} \to \frac{w^*}{\lVert w^* \rVert}$). - (page 6, line 183) According to the paper, the normalized $\ell_2$-margin converges at a speed of $O(\log \log t / \log t)$ when using GD. However, this should be corrected to $O(1 / \log t)$. According to Soudry et al. (2018), the normalized weight vector converges to the maximum $\ell_2$-margin vector "in direction" with a convergence rate of $O(\log \log t / \log t)$, i.e., $\lVert \frac{w_t}{\lVert w_t \rVert} - \frac{w^*}{\lVert w^* \rVert}\rVert = O(\log \log t / \log t)$. However, the normalized $\ell_2$-margin converges at the speed of $O(1/\log t)$, i.e., $|\min \frac{\langle w_t, y_t \cdot x_t \rangle}{\lVert w_t \rVert} - \frac{\langle w^*, y_t \cdot x_t \rangle}{\lVert w^* \rVert} | = O(1/\log t)$. - (page 1, line 25) Typo: reply on -> rely on --- [Gunasekar et al. 2018] Characterizing Implicit Bias in Terms of Optimization Geometry, ICML 2018. [Soudry et al. 2018] The Implicit Bias of Gradient Descent on Separable Data, JMLR 2018.

Questions

- Does Theorem 4.5 imply that Adam (with a learning rate $\eta_t = (t+2)^{-a}$, $a<1$) reduces loss faster than GD (Adam: $O(e^{-\gamma t^{1-a} / 4(1-a)})$ vs. GD: $O(1/t)$)? It would be great if the authors could provide a detailed comparison of the convergence rates of loss between Adam and (S)GD with/without momentum. - Is $\beta_1 \le \beta_2$ a necessary condition? What happens if we use Adam with $\beta_1 > \beta_2$? - Assumption 4.4 seems to be a non-standard assumption. Is this assumption a necessary condition? Can you explain why such an assumption is needed?

Rating

7

Confidence

3

Soundness

4

Presentation

3

Contribution

4

Limitations

The paper discusses its limitations and future directions, including the extension of the results to homogeneous neural networks and the analysis of stochastic Adam instead of full-batch Adam. I think both directions are promising avenues for future research.