Bridging Lottery Ticket and Grokking: Understanding Grokking from Inner Structure of Networks

• URL: http://arxiv.org/abs/2310.19470v3
• Date: Fri, 09 May 2025 15:21:11 GMT
• Title: Bridging Lottery Ticket and Grokking: Understanding Grokking from Inner Structure of Networks
• Authors: Gouki Minegishi, Yusuke Iwasawa, Yutaka Matsuo,
• Abstract summary: We investigate the influence of internal network structures on grokking.<n>We show that utilizing lottery tickets during the generalizing phase (termed grokked tickets) significantly reduces delayed generalization.<n>We find that grokked tickets exhibit periodic weight patterns, beneficial graph properties, and undergo rapid structural changes.
• Score: 27.020990219204343
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Grokking is an intriguing phenomenon of delayed generalization, where neural networks initially memorize training data with perfect accuracy but exhibit poor generalization, subsequently transitioning to a generalizing solution with continued training. While factors such as weight norms and sparsity have been proposed to explain this delayed generalization, the influence of network structure remains underexplored. In this work, we link the grokking phenomenon to the lottery ticket hypothesis to investigate the impact of internal network structures. We demonstrate that utilizing lottery tickets obtained during the generalizing phase (termed grokked tickets) significantly reduces delayed generalization across various tasks, including multiple modular arithmetic operations, polynomial regression, sparse parity, and MNIST classification. Through controlled experiments, we show that the mitigation of delayed generalization is not due solely to reduced weight norms or increased sparsity, but rather to the discovery of good subnetworks. Furthermore, we find that grokked tickets exhibit periodic weight patterns, beneficial graph properties such as increased average path lengths and reduced clustering coefficients, and undergo rapid structural changes that coincide with improvements in generalization. Additionally, pruning techniques like the edge-popup algorithm can identify these effective structures without modifying the weights, thereby transforming memorizing networks into generalizing ones. These results underscore the novel insight that structural exploration plays a pivotal role in understanding grokking. The implementation code can be accessed via this link: https://github.com/gouki510/Grokking-Tickets.

Related papers

• Find A Winning Sign: Sign Is All We Need to Win the Lottery [52.63674911541416]
  We show that a sparse network trained by an existing IP method can retain its basin of attraction if its parameter signs and normalization layer parameters are preserved. To take a step closer to finding a winning ticket, we alleviate the reliance on normalization layer parameters by preventing high error barriers along the linear path between the sparse network trained by our method and its counterpart with normalization layer parameters.
  arXiv  Detail & Related papers  (2025-04-07T09:30:38Z)
• 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)
• Exact, Tractable Gauss-Newton Optimization in Deep Reversible Architectures Reveal Poor Generalization [52.16435732772263]
  Second-order optimization has been shown to accelerate the training of deep neural networks in many applications. However, generalization properties of second-order methods are still being debated. We show for the first time that exact Gauss-Newton (GN) updates take on a tractable form in a class of deep architectures.
  arXiv  Detail & Related papers  (2024-11-12T17:58:40Z)
• Generalization emerges from local optimization in a self-organized learning network [0.0]
  We design and analyze a new paradigm for building supervised learning networks, driven only by local optimization rules without relying on a global error function. Our network stores new knowledge in the nodes accurately and instantaneously, in the form of a lookup table. We show on numerous examples of classification tasks that the networks generated by our algorithm systematically reach such a state of perfect generalization when the number of learned examples becomes sufficiently large. We report on the dynamics of the change of state and show that it is abrupt and has the distinctive characteristics of a first order phase transition, a phenomenon already observed for traditional learning networks and known as grokking.
  arXiv  Detail & Related papers  (2024-10-03T15:32:08Z)
• Progress Measures for Grokking on Real-world Tasks [0.0]
  Grokking is a phenomenon where machine learning models generalize long after overfitting. This paper explores grokking in real-world datasets using deep neural networks for classification under the cross-entropy loss.
  arXiv  Detail & Related papers  (2024-05-21T13:06:41Z)
• Generalization of Scaled Deep ResNets in the Mean-Field Regime [55.77054255101667]
  We investigate emphscaled ResNet in the limit of infinitely deep and wide neural networks. Our results offer new insights into the generalization ability of deep ResNet beyond the lazy training regime.
  arXiv  Detail & Related papers  (2024-03-14T21:48:00Z)
• Understanding Grokking Through A Robustness Viewpoint [3.23379981095083]
  We show that the popular $l$ norm (metric) of the neural network is actually a sufficient condition for grokking. We propose new metrics based on robustness and information theory and find that our new metrics correlate well with the grokking phenomenon and may be used to predict grokking.
  arXiv  Detail & Related papers  (2023-11-11T15:45:44Z)
• Explaining grokking through circuit efficiency [4.686548060335767]
  grokking is a network with perfect training accuracy but poor generalisation will transition to perfect generalisation. We make and confirm four novel predictions about grokking, providing significant evidence in favour of our explanation. We demonstrate two novel and surprising behaviours: ungrokking, in which a network regresses from perfect to low test accuracy, and semi-grokking, in which a network shows delayed generalisation to partial rather than perfect test accuracy.
  arXiv  Detail & Related papers  (2023-09-05T17:00:24Z)
• Theoretical Characterization of How Neural Network Pruning Affects its Generalization [131.1347309639727]
  This work makes the first attempt to study how different pruning fractions affect the model's gradient descent dynamics and generalization. It is shown that as long as the pruning fraction is below a certain threshold, gradient descent can drive the training loss toward zero. More surprisingly, the generalization bound gets better as the pruning fraction gets larger.
  arXiv  Detail & Related papers  (2023-01-01T03:10:45Z)
• Dual Lottery Ticket Hypothesis [71.95937879869334]
  Lottery Ticket Hypothesis (LTH) provides a novel view to investigate sparse network training and maintain its capacity. In this work, we regard the winning ticket from LTH as the subnetwork which is in trainable condition and its performance as our benchmark. We propose a simple sparse network training strategy, Random Sparse Network Transformation (RST), to substantiate our DLTH.
  arXiv  Detail & Related papers  (2022-03-08T18:06:26Z)
• Coarsening the Granularity: Towards Structurally Sparse Lottery Tickets [127.56361320894861]
  Lottery ticket hypothesis (LTH) has shown that dense models contain highly sparseworks (i.e., winning tickets) that can be trained in isolation to match full accuracy. In this paper, we demonstrate the first positive result that a structurally sparse winning ticket can be effectively found in general. Specifically, we first "re-fill" pruned elements back in some channels deemed to be important, and then "re-group" non-zero elements to create flexible group-wise structural patterns.
  arXiv  Detail & Related papers  (2022-02-09T21:33:51Z)
• Learning Theory Can (Sometimes) Explain Generalisation in Graph Neural Networks [13.518582483147325]
  We provide a rigorous analysis of the performance of neural networks in the context of transductive inference. We show that transductive Rademacher complexity can explain the generalisation properties of graph convolutional networks for block models.
  arXiv  Detail & Related papers  (2021-12-07T20:06:23Z)
• Why Lottery Ticket Wins? A Theoretical Perspective of Sample Complexity on Pruned Neural Networks [79.74580058178594]
  We analyze the performance of training a pruned neural network by analyzing the geometric structure of the objective function. We show that the convex region near a desirable model with guaranteed generalization enlarges as the neural network model is pruned.
  arXiv  Detail & Related papers  (2021-10-12T01:11:07Z)
• The Elastic Lottery Ticket Hypothesis [106.79387235014379]
  Lottery Ticket Hypothesis raises keen attention to identifying sparse trainableworks or winning tickets. The most effective method to identify such winning tickets is still Iterative Magnitude-based Pruning. We propose a variety of strategies to tweak the winning tickets found from different networks of the same model family.
  arXiv  Detail & Related papers  (2021-03-30T17:53:45Z)
• Good Students Play Big Lottery Better [84.6111281091602]
  Lottery ticket hypothesis suggests that a dense neural network contains a sparse sub-network that can match the test accuracy of the original dense net. Recent studies demonstrate that a sparse sub-network can still be obtained by using a rewinding technique. This paper proposes a new, simpler and yet powerful technique for re-training the sub-network, called "Knowledge Distillation ticket" (KD ticket)
  arXiv  Detail & Related papers  (2021-01-08T23:33:53Z)
• Neural Pruning via Growing Regularization [82.9322109208353]
  We extend regularization to tackle two central problems of pruning: pruning schedule and weight importance scoring. Specifically, we propose an L2 regularization variant with rising penalty factors and show it can bring significant accuracy gains. The proposed algorithms are easy to implement and scalable to large datasets and networks in both structured and unstructured pruning.
  arXiv  Detail & Related papers  (2020-12-16T20:16:28Z)
• Sanity-Checking Pruning Methods: Random Tickets can Win the Jackpot [55.37967301483917]
  Conventional wisdom of pruning algorithms suggests that pruning methods exploit information from training data to find goodworks. In this paper, we conduct sanity checks for the above beliefs on several recent unstructured pruning methods. We propose a series of simple emphdata-independent prune ratios for each layer, and randomly prune each layer accordingly to get a subnetwork.
  arXiv  Detail & Related papers  (2020-09-22T17:36:17Z)
• Understanding Generalization in Deep Learning via Tensor Methods [53.808840694241]
  We advance the understanding of the relations between the network's architecture and its generalizability from the compression perspective. We propose a series of intuitive, data-dependent and easily-measurable properties that tightly characterize the compressibility and generalizability of neural networks.
  arXiv  Detail & Related papers  (2020-01-14T22:26:57Z)

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.