1st-Order Magic: Analysis of Sharpness-Aware Minimization

Nalin Tiwary, Siddarth Aananth · 2024

Read 1st-Order Magic: Analysis of Sharpness-Aware Minimization by Nalin Tiwary, Siddarth Aananth (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2411-01714.txt.

Description

A 2024 arXiv research paper by Nalin Tiwary, Siddarth Aananth. Sharpness-Aware Minimization (SAM) is an optimization technique designed to improve generalization by favoring flatter loss minima. To achieve this, SAM optimizes a modified objective that penalizes sharpness, using computationally efficient approximations. Interestingly, we find that more precise approximations of the proposed SAM objective degrade generalization performance, suggesting that the generalization benefits of SAM are rooted in these approximations rather than in the original intended mechanism.

Catalog record

CREATORNalin Tiwary, Siddarth Aananth
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE16 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2411-01714

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

1st-Order Magic: Analysis of Sharpness-Aware Minimization Nalin Tiwary, Siddarth Aananth Abstract Sharpness-Aware Minimization (SAM) is an optimization technique designed to improve generalization by favoring flatter loss minima. To achieve this, SAM optimizes a modified objective that penalizes sharpness, using computationally efficient approximations. Interestingly, we find that more precise approximations of the proposed SAM objective degrade generalization performance, suggesting that the generalization benefits of SAM are rooted in these approximations rather than in the original intended mechanism. This highlights a gap in our understanding of SAM’s effectiveness and calls for further investigation into the role of approximations in optimization. 1 Introduction Modern machine learning relies heavily on overparameterization to achieve state-of-the-art performance across various tasks. However, with this overparameterization comes the risk of overfitting, where models can easily memorize training data, even when the labels are random Zhang et al. 2021 . To mitigate this risk, effective training techniques must minimize training error in a way that also ensures good generalization. One promising direction for improving generalization is focusing on the geometry of the loss landscape, particularly sharpness. Previous studies have demonstrated that flatter minima in the loss landscape are often associated with better generalization. Keskar et al. 2017 showed that larger batch sizes can lead to sharper minima and poorer generalization. This insight, along with the work of others such as Dinh et al. 2017 and Neyshabur et al. 2017 , has motivated the development of optimization techniques that explicitly address sharpness. Building on these ideas, several Sharpness-Aware optimization methods have been introduced. For instance, Foret et al. 2021 , Kwon et al. 2021 , and Zheng et al. 2021 leverage the connection between sharpness and generalization by minimizing the loss at perturbed parameter points, thereby penalizing sharp regions of the loss landscape. Despite the empirical success of these methods, the underlying mechanisms behind SAM’s effectiveness remain unclear. Specifically, the Sharpness-Aware Minimization (SAM) objective aims to penalize a specific notion of sharpness, but the practical implementation of SAM involves a series of approximations. These approximations, including the use of a first-order Taylor expansion, imply assumptions about the local linearity of the loss landscape around the current parameters, which are often inaccurate. Surprisingly, improving these approximations does not lead to better generalization Kim et al. 2023 . In this paper, we analyze SAM’s performance when using better approximations of its proposed objective, explore the reasons behind the observed discrepancy in generalization, and provide a standardized sharpness comparison. We also investigate the approximations involved in the SAM objective and, specifically, the role the 1st-order Taylor expansion approximation plays in the superior generalization of the 1st-order formulation of SAM. We propose a modification, Rand-SAM, which empirically demonstrates our proposed reasoning behind the seemingly "magical" performance benefits of the original SAM formulation. 2 Related Works 2.1 Sharpness-Aware Minimization Figure 1: The figure to the left is a sharp minima obtained through SGD while the figure to the right is a flat minima obtained through SAM We focus on the Sharpness-Aware Minimization objective introduced in Foret et al. 2021 . \mathcal{L}^{SAM}(w)=max_{\|\epsilon\|\leq\rho}\mathcal{L}(w+\epsilon) (1) In this formulation, w\in\mathbb{R}^{d} represents the model parameters, and \mathcal{L} is the training loss. The parameter \rho controls the size of the neighborhood used to penalize sharpness, typically set to 0.05 . The SAM objective aims to find parameter values where the entire neighborhood of radius \rho exhibits low training loss, leading to flatter minima. Figure. 1 illustrates an example of such a flat minimum. In order to make the computation efficient, Foret et al. 2021 propose a series of approximations. The approximations of interest to us occur while obtaining the value of \epsilon \epsilon^{*}(w)=argmax_{\|\epsilon\|\leq\rho}\mathcal{L}(w+\epsilon) (2) Since directly solving Eq. 2 is computationally expensive, SAM approximates \epsilon^{*} using a first-order Taylor expansion around w w.r.t \epsilon around 0: \epsilon^{*}(w)\approx\epsilon_{1}(w)=argmax_{\|\epsilon\|\leq\rho}(\mathcal{L}(w)+\epsilon^{T}\nabla_{w}\mathcal{L}(w))=argmax_{\|\epsilon\|\leq\rho}\epsilon^{T}\nabla_{w}\mathcal{L}(w) (3) Since Eq. 3 is maximizing a linear function under a norm 1 1 1 We utilize L2 norm unless specified otherwise and gradient w.r.t to w unless specified otherwise constraint, \epsilon_{1} will be a vector with norm \rho is the same direction as \nabla L(w) as shown in Eq. 4 \epsilon_{1}=\rho\frac{\nabla L(w)}{\|\nabla L(w)\|} (4) Utilizing \epsilon , Foret et al. 2021 approximates \nabla L^{SAM}(w) as \nabla L(w+\epsilon_{1}) and utilizes gradient descent. 2.2 Gradient-Ascent Foret et al. 2021 proposes N -step Gradient Ascent as an alternate way to estimate \epsilon^{*} . For each iteration n\in\{1,2,..,N\} and w^{N}=w+\epsilon_{N} w^{n}=w^{n-1}+\frac{\rho}{N}\frac{\nabla L(w^{n-1})}{\|\nabla L(w^{n-1})\|} (5) Kim et al. 2023 discusses this formulation of SAM and the impact of the value of N on the loss landscape and specifically addresses the phenomenon that an increase in N, which should provide a better approximation of \epsilon^{*} , rarely improves generalization performance. 2.3 Notion of Sharpness Table 1: Notions of sharpness Type of Loss Notation Definition Worst-direction L^{\text{Max}} \max_{\|\epsilon\|\leq\rho}L(w+\epsilon) Ascent-direction L^{\text{Asc}} L\left(w+\rho\frac{\nabla L(w)}{\|\nabla L(w)\|}\right) Average-direction L^{\text{Avg}} \mathbb{E}_{g\sim N(0,I)}L\left(w+\rho\frac{g}{\|g\|_{2}}\right) As pointed out in Wen et al. 2023 , the proposed SAM objective ( L^{\text{Max}} ) and the actual SAM objective ( L^{\text{Asc}} ) use subtly different notions of sharpness due to the approximations mentioned in Sec. 2.1 . Both of these notions of sharpness differ from the notion of sharpness used to upper bound the generalization error of SAM ( L^{\text{Avg}} ), as shown in Table. 1 . Wen et al. 2023 also utilizes a gradient flow-based analysis, in the style of Arora et al. 2022 , to analyze the biases introduced by these notions of sharpness and utilizes this analysis to provide theoretical underpinnings for the mechanism behind the different formulations of SAM from Foret et al. 2021 . Since the analysis is based on gradient flow, it assumes \rho\rightarrow 0 , which is not appropriate for SAM since \rho=0.05 . Furthermore, with the first-order assumption being made for each discrete step in the algorithm, the continuous nature of gradient-flow analysis introduces further differences. So, while this analysis does shed light on the role of the approximations shown in Sec. 2.1 in the generalization success of SAM, it does not paint the complete picture. 3 Intuition and Analysis To demonstrate that the approximations made in the SAM objective, leading to Eq. 4 , are the driving factor behind SAM’s generalization success, we analyze SAM using N -step gradient ascent. Specifically, previous works Foret et al. 2021 ; Kim et al. 2023 show that increasing N improves the accuracy of the approximation of \epsilon^{*} . However, counter intuitively, this does not improve generalization. In fact, higher values of N often result in significantly sharper solutions, with sharpness measured using Eq. 6 . sharpness=\mathcal{L}(w+\epsilon_{N})-\mathcal{L}(w) (6) One issue with comparing sharpness using this metric is that the accuracy of the \epsilon^{*} approximation varies for different values of N . Therefore, a standardized measure of sharpness is needed to make fair comparisons between implementations. Nevertheless, the critical question remains: why does improving the approximation of \epsilon^{*} —leading to more accurate sharpness penalization—result in worse generalization? To answer this question, we must look at Eq. 4 . Specifically due to the reasons mentioned in Sec. 2.1 , the condition \|\epsilon_{1}\|=\|(w+\epsilon_{1})-w\|=\rho implies that \epsilon always lies on the boundary of the \rho -radius ball around the current parameter values w . Without additional assumptions about the loss landscape, there is no direct relationship between the loss at

Read the complete text