PaperlayerView exact revision on arXiv

Source-linked AI summary

Linear Mode Connectivity and the Lottery Ticket Hypothesis

Jonathan Frankle, Gintare Karolina Dziugaite, Daniel M. Roy, Michael Carbin

arXiv:1912.05671v4cs.LGcs.NEstat.ML

TL;DR

The paper asks whether SGD noise leads networks to different optimization outcomes and whether this explains when IMP discovers trainable lottery-ticket subnetworks. It introduces instability analysis using linear interpolation, finding that standard networks and matching IMP subnetworks become stable at initialization or early in training depending on the setting. The work extends lottery-ticket observations to larger-scale models through rewinding.

  • Problem

    The paper investigates how SGD noise affects optimization and why IMP finds matching subnetworks in smaller settings but not more challenging ones.

  • Method

    The paper compares networks trained from the same state under different SGD noise by measuring the error barrier along their linear interpolation.

  • Results

    Standard networks become stable early in training, while extremely sparse IMP subnetworks reach full accuracy only when stable, at initialization in some settings and after training in others.

  • Takeaways & Limitations

    Rewinding IMP to early-training weights can find matching subnetworks in larger settings than initialization-only approaches.

  • Takeaways & Limitations

    At extreme sparsities, IMP subnetworks may remain non-matching at every rewinding iteration considered, despite error decreasing when they become stable.

Abstract

from arXiv · show

We study whether a neural network optimizes to the same, linearly connected minimum under different samples of SGD noise (e.g., random data order and augmentation). We find that standard vision models become stable to SGD noise in this way early in training. From then on, the outcome of optimization is determined to a linearly connected region. We use this technique to study iterative magnitude pruning (IMP), the procedure used by work on the lottery ticket hypothesis to identify subnetworks that could have trained in isolation to full accuracy. We find that these subnetworks only reach full accuracy when they are stable to SGD noise, which either occurs at initialization for small-scale settings (MNIST) or early in training for large-scale settings (ResNet-50 and Inception-v3 on ImageNet).

1. Introduction

The paper examines how SGD noise changes neural-network optimization and introduces instability analysis based on linear mode connectivity. It uses this perspective to explain when IMP finds matching subnetworks and extends those findings to larger-scale settings.

  • SGD randomness from data ordering and augmentation can alter a network’s optimization trajectory even with fixed initialization and hyperparameters.
  • Instability analysis trains copies from the same state under different SGD noise, then tests whether their solutions are connected by a low-error linear path.
  • Networks become stable to SGD noise early in training: by 3% of training for ResNet-20 on CIFAR-10 and 20% for ResNet-50 on ImageNet.
  • IMP subnetworks are matching only when they are stable to SGD noise, with stability occurring at initialization in some settings and later in training in others.

2. Preliminaries and Methodology

The methodology measures sensitivity to SGD noise by training two copies from the same network state and quantifying the error barrier along their linear interpolation. Stability means the resulting networks are linearly mode connected.

  • Instability analysis trains two copies from weights Wk to completion using independent SGD-noise samples, producing terminal weights W1_T and W2_T.
  • The analysis can begin at initialization or after k training steps, allowing stability to be measured throughout training.
  • Linear interpolation evaluates error along Eα(W1, W2) = E(αW1 +(1−α)W2), with Esup representing the highest error on the path.
  • Linear interpolation instability is the path’s error barrier height above the mean endpoint error, and stability corresponds to instability ≈0.

3. Instability Analysis of Unpruned Networks

Standard vision networks generally become stable to SGD noise early in training, so different noise samples converge to linearly connected minima. This stability is not usually present at initialization, except for LeNet.

  • Only LeNet is stable to SGD noise at initialization; every examined network becomes stable early in training.
  • Instability analysis starts from a network state at step k, trains two copies with different SGD noise, and linearly interpolates their final solutions.
  • Test-set instability decreases as k increases, reaching stability after 2,000 iterations for ResNet-20 and 1,000 for VGG-16.These correspond to 3% and 1.5% of training, respectively.
  • Train and test instability are nearly identical for LeNet, ResNet-20, and VGG-16, while train stability occurs later for ResNet-50 and is absent in the analyzed range for Inception-v3.
  • The apparent decrease in instability could reflect shorter post-k training, but resetting the schedule and training copies for T steps produces indistinguishable results.

4. Instability Analysis of Lottery Tickets

Instability analysis links IMP subnetworks’ matching accuracy to stability under SGD noise, while showing that stability emerges later as sparsity and task difficulty increase.

  • Stability and matching: IMP subnetworks only reach full accuracy when different SGD-noise samples lead to linearly connected minima.When interpolation reveals nonconnected minima, test accuracy is lower.
  • Stability and matching: At initialization, IMP finds matching subnetworks for LeNet and modified ResNet-20 and VGG-16 settings, but not for standard larger settings.Standard ResNet-20, standard VGG-16, ResNet-50, and Inception-v3 IMP subnetworks are no more accurate than random-pruning or reinitialized controls.
  • Stability over training: Later rewinding makes initially unstable IMP subnetworks stable: ResNet-20 and VGG-16 stabilize at 0.8% and 1.6% of training, while ResNet-50 and Inception-v3 stabilize at 5.5% and 3.5%.These points precede the corresponding unpruned-network stability points, substantially so for ResNet-50 and Inception-v3.
  • Stability over training: Randomly pruned or reinitialized subnetworks remain unstable and non-matching across rewinding points, except for the stated LeNet case.For other networks, interpolation error approaches random-guessing error.
  • Other sparsity levels: As sparsity increases, IMP stability first appears earlier, plateaus, and eventually appears later, unlike random-pruning stability, which only shifts later before disappearing.The sparsity ranges distinguish trivial matching by random subnetworks, IMP-only matching, and sparsities where even IMP fails to match.

5. Discussion

The paper introduces instability analysis to show when linear mode connectivity emerges and uses it to connect optimization dynamics with lottery-ticket behavior and pruning practice.

  • Instability analysis reveals situations where linear mode connectivity emerges, unlike prior comparable examples that required nonlinear paths.
  • Training separates into an unstable phase, where SGD noise leads to linearly unconnected minima, and a stable phase, where the linearly connected minimum is determined.
  • Instability analysis can evaluate optimization changes after stability emerges, including learning-rate schedules and optimizer choices.
  • The lottery ticket analysis connects IMP successes and failures to neural-network optimization dynamics in different settings.
  • Rewinding extends IMP to find matching subnetworks in larger settings, although from early training rather than initialization.
  • In larger-scale settings, matching IMP subnetworks emerge only after some full-network training, suggesting earlier pruning than current methods may be possible.

6. Conclusions

The paper uses instability analysis to study SGD-noise sensitivity in standard networks and IMP subnetworks. It finds that stability and linear connectivity emerge early, while sparse subnetworks reach full accuracy only under stability.

  • Standard networks on MNIST, CIFAR-10, and ImageNet become stable to SGD noise early in training, after which optimization is determined to a linearly connected minimum.
  • Extremely sparse IMP subnetworks train to full accuracy only when stable to SGD noise, with stability occurring at initialization in some settings and later in others.
  • Instability analysis and linear mode connectivity provide empirical tools for studying neural-network training dynamics and lottery-ticket phenomena.

Overview and Contents

The supplementary material documents data, selection procedures, pruning configurations, and rewinding analyses supporting the paper’s main experiments.

  • The appendices include processed plotting data and additional data omitted from the main paper.
  • Appendix contents: Appendix A explains how the extreme sparsity levels used in Section 4.3 were selected.
  • Appendix contents: Appendices B–F provide rewinding-state measurements, instability data across training and sparsity, and training-set instability results.
  • Appendix contents: Appendix G compares alternative network-comparison functions, including L2 distance, cosine distance, classification agreement, and loss distance.
  • Selecting sparsity: Extreme sparsity is selected as the most extreme level at which any IMP rewinding iteration produces a matching subnetwork.
  • Selecting sparsity: Figure 10 compares maximum rewinding accuracy with unpruned-network accuracy and includes IMP at k = 0, random pruning, and random reinitialization.
  • Pruning configuration: ResNet-50 and Inception-v3 use one-shot pruning for computational reasons, whereas other networks are pruned iteratively by 20% per IMP iteration.
  • Rewinding analysis: The rewinding analysis trains two masked or unmasked copies from step k under different SGD noise samples and examines when they reach the same linearly connected minimum.

B.2. Results

The appendix compares stability timing, errors, parameter distances, and copy separation for unpruned and IMP-pruned networks. IMP subnetworks generally stabilize earlier, while remaining SGD-noise variation can still be substantial.

  • Unpruned networks: Unpruned ResNet-20 and VGG-16 stabilize at iterations 2000 and 1000, with test errors of 25% and 20% versus final errors of 8.3% and 6.3%.
  • Unpruned networks: Unpruned ResNet-50 and Inception-v3 stabilize at epochs 18 and 28, with test errors of 55% and 33% versus final errors of 24% and 22%.
  • IMP-pruned subnetworks: IMP-pruned ResNet-20 and VGG-16 stabilize at iterations 500 and 1000, with errors of 30% and 35% versus final errors of 8.3% and 6.3%.
  • IMP-pruned subnetworks: IMP subnetworks of ResNet-50 and Inception-v3 stabilize at epochs 5 and 6, when errors remain 55% and 40%, leaving substantial room for further training.
  • L2 distances: Unpruned ResNet-20 and VGG-16 are closer to initialization than final weights when stable, indicating substantial remaining optimization distance.
  • L2 distances: Unpruned ResNet-50 and Inception-v3 are closer to final than initial weights at stabilization, while distance from initialization plateaus and final-weight distance decreases slowly.
  • L2 distances: At stabilization, ResNet-20 and VGG-16 are about 2x and 3x closer to initialization than to final weights, whereas ResNet-50 and Inception-v3 are about equally distant.
  • L2 distances: For IMP subnetworks, copy distance decreases with instability and plateaus lower at the stable rewinding iteration, while remaining 25%, 45%, 27%, and 28% of total travel across four networks.

C. Instability Throughout Training

The appendix tracks instability throughout training for unpruned networks and IMP subnetworks, asking whether their trajectories remain linearly connected. For ResNet-20, end-of-training stability corresponds to stability throughout training, while VGG-16 shows a transition around rewinding iteration 1000.

  • Figure 14 tracks train- and test-error instability throughout training for ResNet-20 and VGG-16 across rewinding iterations.It compares unpruned networks with IMP subnetworks.
  • For ResNet-20 IMP subnetworks, stability at the end of training corresponds to stability throughout training.Two differently trained copies follow optimization trajectories connected by linear interpolation.
  • VGG-16 shows initial instability spikes at rewinding iterations 500 and 1000 before later iterations generally become stable throughout training.Rewinding iteration 1000 may mark a transition between earlier unstable and later stable regimes.

D. Instability Data at All Sparsities

The appendix extends the rewinding-iteration analysis across all sparsity levels for standard ResNet-20 and VGG-16 on CIFAR-10, while omitting comparable ImageNet-wide data because of computational limits.

  • The analysis relates rewinding iteration to instability and test error across all displayed sparsity levels for standard ResNet-20 and VGG-16 on CIFAR-10.It includes the extreme sparsity level emphasized in the main analysis and less extreme levels.
  • The evaluated sparsities begin with 80% of weights remaining and include repeated 20% pruning levels such as 64% and 51% remaining.These levels match the IMP procedure used in the study.
  • The appendix does not provide all-sparsity data for ImageNet networks because computational resources were limited.Resources were prioritized for CIFAR-10 networks whose instability and accuracy were sensitive to rewinding at extreme sparsity.

E. Full Linear Interpolation Data

The appendix supplies the underlying linear-interpolation data used to derive instability values for unpruned networks, IMP subnetworks, randomly pruned subnetworks, and randomly reinitialized IMP subnetworks.

  • Linear-interpolation data are shown for four network categories: unpruned, IMP, randomly pruned, and randomly reinitialized IMP subnetworks.These data underlie the instability values plotted in the main figures.

F. Train Instability for Sparse Subnetworks

The appendix compares train and test instability for sparse subnetworks and reports that they are nearly identical. Unstable subnetworks fail to reach zero train error, whereas stable subnetworks can fully optimize it.

  • The appendix presents train- and test-set instability and error for the IMP subnetworks examined in Figure 6.Train-set quantities were not computed for Inception-v3 because of computational limitations.
  • Train-set and test-set instability are nearly identical for sparse subnetworks.The alignment is especially close for ResNet-50 IMP subnetworks compared with the unpruned networks studied earlier.
  • Unstable IMP subnetworks cannot fully optimize to 0% train error, while stable IMP subnetworks can.Train and test error follow similar trends, starting higher when subnetworks are unstable and dropping as they become stable.

G. Alternate Distance Functions

The paper evaluates alternate ways to compare networks produced by different SGD noise samples, including parameter-space and function-space distances. These measures reveal patterns related to IMP stability, but some lack a clear interpretation of functional similarity or are entangled with accuracy.

  • L2 Distance: L2 distance between weights has no clear interpretation for functional similarity or loss-landscape structure.The paper therefore treats it cautiously as a network-comparison measure.
  • L2 Distance: For unpruned networks, L2 distance decreases with later rewinding but shows no distinct change when networks become stable.The distance remains far from zero at the stability transition.
  • L2 Distance: For IMP subnetworks, L2 distance mirrors instability: it stays lower and consistent for always-stable subnetworks, but drops when initially unstable subnetworks become stable.Initially unstable subnetworks begin at the level of randomly pruned and randomly reinitialized baselines before settling lower.
  • L2 Distance: Even stable IMP subnetworks remain far from zero in L2 distance, making higher-level relationships between networks difficult to infer.This limits direct interpretation of parameter-space proximity.
  • Cosine Distance: Cosine distance produces results similar to L2 distance and receives the same interpretation.The paper presents it as an alternate parameter-space comparison.
  • Classification Differences: Classification differences compare functional behavior directly and can compare dense and sparse networks, but the measure is entangled with accuracy.When networks become stable, classification differences can drop substantially; interpreting the drop requires accounting for improved accuracy.
Loading 1912.05671v4…