Flat Minima and Generalization: Insights from Stochastic Convex Optimization

Understanding the generalization behavior of learning algorithms is a central goal of learning theory. A recently emerging explanation is that learning algorithms are successful in practice because they converge to flat minima, which have been consistently associated with improved generalization performance. In this work, we study the link between flat minima and generalization in the canonical setting of stochastic convex optimization with a non-negative, $\beta$-smooth objective. Our first finding is that, even in this fundamental setting, flat empirical minima may incur trivial $\Omega(1)$ population risk while sharp minima generalizes optimally. We then demonstrate that this phenomenon extends to sharpness-aware algorithms introduced by Foret et al. (2021), namely Sharpness-Aware Gradient Descent (SA-GD) and Sharpness-Aware Minimization (SAM). For SA-GD we prove that it successfully converges to a flat minimum at a fast rate, but the population risk of the solution can still be as large as $\Omega(1)$. For SAM we show that although it minimizes the empirical loss, it may converge to a sharp minimum and also incur population risk $\Omega(1)$. Finally, we establish population risk upper bounds for both SA-GD and SAM using algorithmic stability techniques.

Machine learning systems often learn by searching for parameters that fit their training data well. A common belief is that some good solutions are better than others because they are “flat”: small changes to the parameters do not significantly change the training loss. This idea has motivated popular training methods, such as sharpness-aware minimization, that explicitly encourage flatter solutions. In this work, we study whether flatness by itself is enough to explain good performance on new data. We focus on a fundamental mathematical setting called stochastic convex optimization, which is often used to understand learning algorithms. Our results show that even in this simple setting, flat solutions can still perform poorly on new data, while sharper solutions can perform well. We also show that some sharpness-aware algorithms may either find flat solutions that generalize poorly, or fail to find flat solutions at all. These findings do not mean that flatness is useless, but they show that the connection between flatness and generalization is more subtle than it may appear. Understanding this distinction can help researchers better evaluate when sharpness-aware training methods are expected to improve learning.