Grokking at the Edge of Linear Separability

• URL: http://arxiv.org/abs/2410.04489v1
• Date: Sun, 6 Oct 2024 14:08:42 GMT
• Title: Grokking at the Edge of Linear Separability
• Authors: Alon Beck, Noam Levi, Yohai Bar-Sinai,
• Abstract summary: We analyze the long-time dynamics of logistic classification on a random feature model with a constant label. We find that Grokking is amplified when classification is applied to training sets which are on the verge of linear separability.
• Score: 1.024113475677323
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the generalization properties of binary logistic classification in a simplified setting, for which a "memorizing" and "generalizing" solution can always be strictly defined, and elucidate empirically and analytically the mechanism underlying Grokking in its dynamics. We analyze the asymptotic long-time dynamics of logistic classification on a random feature model with a constant label and show that it exhibits Grokking, in the sense of delayed generalization and non-monotonic test loss. We find that Grokking is amplified when classification is applied to training sets which are on the verge of linear separability. Even though a perfect generalizing solution always exists, we prove the implicit bias of the logisitc loss will cause the model to overfit if the training data is linearly separable from the origin. For training sets that are not separable from the origin, the model will always generalize perfectly asymptotically, but overfitting may occur at early stages of training. Importantly, in the vicinity of the transition, that is, for training sets that are almost separable from the origin, the model may overfit for arbitrarily long times before generalizing. We gain more insights by examining a tractable one-dimensional toy model that quantitatively captures the key features of the full model. Finally, we highlight intriguing common properties of our findings with recent literature, suggesting that grokking generally occurs in proximity to the interpolation threshold, reminiscent of critical phenomena often observed in physical systems.

Related papers

• Beyond Progress Measures: Theoretical Insights into the Mechanism of Grokking [50.465604300990904]
  Grokking refers to the abrupt improvement in test accuracy after extended overfitting.<n>In this work, we investigate the grokking mechanism underlying the Transformer in the task of prime number operations.
  arXiv  Detail & Related papers  (2025-04-04T04:42:38Z)
• The global convergence time of stochastic gradient descent in non-convex landscapes: Sharp estimates via large deviations [29.642830843568525]
  We study the time it takes for the gradient of descent to reach the global minimum of a general, non- loss function.<n>Motivated by applications to neural networks, we provide a series of refinements and extensions of our analysis for loss functions with local minima.
  arXiv  Detail & Related papers  (2025-03-20T17:54:04Z)
• Universality in Transfer Learning for Linear Models [18.427215139020625]
  We study the problem of transfer learning and fine-tuning in linear models for both regression and binary classification. In particular, we consider the use of gradient descent (SGD) on a linear model with pretrained weights and using a small training data set from the target distribution.
  arXiv  Detail & Related papers  (2024-10-03T03:09:09Z)
• Scaling and renormalization in high-dimensional regression [72.59731158970894]
  This paper presents a succinct derivation of the training and generalization performance of a variety of high-dimensional ridge regression models. We provide an introduction and review of recent results on these topics, aimed at readers with backgrounds in physics and deep learning.
  arXiv  Detail & Related papers  (2024-05-01T15:59:00Z)
• On the Convergence of Gradient Descent for Large Learning Rates [55.33626480243135]
  We show that convergence is impossible when a fixed step size is used.<n>We provide a proof of this in the case of linear neural networks with a squared loss.<n>We also prove the impossibility of convergence for more general losses without requiring strong assumptions such as Lipschitz continuity for the gradient.
  arXiv  Detail & Related papers  (2024-02-20T16:01:42Z)
• On the Dynamics Under the Unhinged Loss and Beyond [104.49565602940699]
  We introduce the unhinged loss, a concise loss function, that offers more mathematical opportunities to analyze closed-form dynamics. The unhinged loss allows for considering more practical techniques, such as time-vary learning rates and feature normalization.
  arXiv  Detail & Related papers  (2023-12-13T02:11:07Z)
• Curvature-Independent Last-Iterate Convergence for Games on Riemannian Manifolds [77.4346324549323]
  We show that a step size agnostic to the curvature of the manifold achieves a curvature-independent and linear last-iterate convergence rate. To the best of our knowledge, the possibility of curvature-independent rates and/or last-iterate convergence has not been considered before.
  arXiv  Detail & Related papers  (2023-06-29T01:20:44Z)
• Implicit Bias of Gradient Descent for Logistic Regression at the Edge of Stability [69.01076284478151]
  In machine learning optimization, gradient descent (GD) often operates at the edge of stability (EoS) This paper studies the convergence and implicit bias of constant-stepsize GD for logistic regression on linearly separable data in the EoS regime.
  arXiv  Detail & Related papers  (2023-05-19T16:24:47Z)
• On the ISS Property of the Gradient Flow for Single Hidden-Layer Neural Networks with Linear Activations [0.0]
  We investigate the effects of overfitting on the robustness of gradient-descent training when subject to uncertainty on the gradient estimation. We show that the general overparametrized formulation introduces a set of spurious equilibria which lay outside the set where the loss function is minimized.
  arXiv  Detail & Related papers  (2023-05-17T02:26:34Z)
• Theoretical Characterization of the Generalization Performance of Overfitted Meta-Learning [70.52689048213398]
  This paper studies the performance of overfitted meta-learning under a linear regression model with Gaussian features. We find new and interesting properties that do not exist in single-task linear regression. Our analysis suggests that benign overfitting is more significant and easier to observe when the noise and the diversity/fluctuation of the ground truth of each training task are large.
  arXiv  Detail & Related papers  (2023-04-09T20:36:13Z)
• Instance-Dependent Generalization Bounds via Optimal Transport [51.71650746285469]
  Existing generalization bounds fail to explain crucial factors that drive the generalization of modern neural networks. We derive instance-dependent generalization bounds that depend on the local Lipschitz regularity of the learned prediction function in the data space. We empirically analyze our generalization bounds for neural networks, showing that the bound values are meaningful and capture the effect of popular regularization methods during training.
  arXiv  Detail & Related papers  (2022-11-02T16:39:42Z)
• Harmless interpolation in regression and classification with structured features [21.064512161584872]
  Overparametrized neural networks tend to perfectly fit noisy training data yet generalize well on test data. We present a general and flexible framework for upper bounding regression and classification risk in a reproducing kernel Hilbert space.
  arXiv  Detail & Related papers  (2021-11-09T15:12:26Z)
• Model, sample, and epoch-wise descents: exact solution of gradient flow in the random feature model [16.067228939231047]
  We analyze the whole temporal behavior of the generalization and training errors under gradient flow. We show that in the limit of large system size the full time-evolution path of both errors can be calculated analytically. Our techniques are based on Cauchy complex integral representations of the errors together with recent random matrix methods based on linear pencils.
  arXiv  Detail & Related papers  (2021-10-22T14:25:54Z)
• Towards Understanding Generalization via Decomposing Excess Risk Dynamics [13.4379473119565]
  We analyze the generalization dynamics to derive algorithm-dependent bounds, e.g., stability. Inspired by the observation that neural networks show a slow convergence rate when fitting noise, we propose decomposing the excess risk dynamics. Under the decomposition framework, the new bound accords better with the theoretical and empirical evidence compared to the stability-based bound and uniform convergence bound.
  arXiv  Detail & Related papers  (2021-06-11T03:42:45Z)
• Localisation in quasiperiodic chains: a theory based on convergence of local propagators [68.8204255655161]
  We present a theory of localisation in quasiperiodic chains with nearest-neighbour hoppings, based on the convergence of local propagators. Analysing the convergence of these continued fractions, localisation or its absence can be determined, yielding in turn the critical points and mobility edges. Results are exemplified by analysing the theory for three quasiperiodic models covering a range of behaviour.
  arXiv  Detail & Related papers  (2021-02-18T16:19:52Z)
• Why do classifier accuracies show linear trends under distribution shift? [58.40438263312526]
  accuracies of models on one data distribution are approximately linear functions of the accuracies on another distribution. We assume the probability that two models agree in their predictions is higher than what we can infer from their accuracy levels alone. We show that a linear trend must occur when evaluating models on two distributions unless the size of the distribution shift is large.
  arXiv  Detail & Related papers  (2020-12-31T07:24:30Z)
• Generalization and Memorization: The Bias Potential Model [9.975163460952045]
  generative models and density estimators behave quite differently from models for learning functions. For the bias potential model, we show that dimension-independent generalization accuracy is achievable if early stopping is adopted. In the long term, the model either memorizes the samples or diverges.
  arXiv  Detail & Related papers  (2020-11-29T04:04:54Z)
• Gradient Descent for Deep Matrix Factorization: Dynamics and Implicit Bias towards Low Rank [1.9350867959464846]
  In deep learning, gradientdescent tends to prefer solutions which generalize well. In this paper we analyze the dynamics of gradient descent in the simplifiedsetting of linear networks and of an estimation problem.
  arXiv  Detail & Related papers  (2020-11-27T15:08:34Z)
• Understanding Double Descent Requires a Fine-Grained Bias-Variance Decomposition [34.235007566913396]
  We describe an interpretable, symmetric decomposition of the variance into terms associated with the labels. We find that the bias decreases monotonically with the network width, but the variance terms exhibit non-monotonic behavior. We also analyze the strikingly rich phenomenology that arises.
  arXiv  Detail & Related papers  (2020-11-04T21:04:02Z)
• Good Classifiers are Abundant in the Interpolating Regime [64.72044662855612]
  We develop a methodology to compute precisely the full distribution of test errors among interpolating classifiers. We find that test errors tend to concentrate around a small typical value $varepsilon*$, which deviates substantially from the test error of worst-case interpolating model. Our results show that the usual style of analysis in statistical learning theory may not be fine-grained enough to capture the good generalization performance observed in practice.
  arXiv  Detail & Related papers  (2020-06-22T21:12:31Z)
• Generalization Error of Generalized Linear Models in High Dimensions [25.635225717360466]
  We provide a framework to characterize neural networks with arbitrary non-linearities. We analyze the effect of regular logistic regression on learning. Our model also captures examples between training and distributions special cases.
  arXiv  Detail & Related papers  (2020-05-01T02:17:47Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.