Optimal Brain Damage (OBD)

OBD's core innovation is its saliency measure for parameters. Unlike simple magnitude-based pruning, OBD estimates the increase in training error from removing a weight using a second-order Taylor expansion. The saliency for weight (w_i) is approximated as:

(S_i = \frac{1}{2} h_{ii} w_i^2)

Where (h_{ii}) is the diagonal element of the Hessian matrix (second derivatives of the loss with respect to (w_i)). Parameters with the smallest saliency scores are pruned first, as their removal theoretically causes the least increase in error.

Calculating the full Hessian matrix for a modern neural network is computationally prohibitive. OBD's critical simplification is to assume the Hessian is diagonal, ignoring interactions between parameters ((h_{ij}=0) for (i \neq j)).

• Assumption: Parameters are uncorrelated with respect to the loss function.
• Benefit: Reduces complexity from (O(N^2)) to (O(N)), where N is the number of parameters.
• Limitation: This approximation is a primary source of inaccuracy, as weights in neural networks are highly correlated. Later algorithms like Optimal Brain Surgeon (OBS) addressed this by using the inverse Hessian.

OBD is not a one-shot operation. It follows an iterative prune-retrain cycle:

1. Train the network to convergence (or a good solution).
2. Compute the diagonal Hessian approximation and saliency for all weights.
3. Prune a small percentage (e.g., 5-20%) of weights with the lowest saliency.
4. Retrain the pruned network to recover accuracy lost from pruning.
5. Repeat steps 2-4 until a target sparsity or accuracy threshold is met. This iterative process allows the network to adapt its remaining weights to compensate for the removed connections.

OBD produces unstructured or fine-grained sparsity. It removes individual weights anywhere in the network based solely on their saliency, not their position.

• Result: A network with an irregular, non-patterned sparsity map.
• Hardware Challenge: This irregularity does not translate to speedups on standard dense hardware (CPUs/GPUs) without specialized sparse linear algebra libraries.
• Contrast with Structured Pruning: Unlike channel pruning or filter pruning, OBD does not create hardware-friendly, dense sub-networks. Its value is in maximal parameter reduction for a given accuracy drop.

OBD (1990) and its successor OBS provided the theoretical framework that much of modern pruning research builds upon.

• It formalized pruning as an optimization problem: minimizing performance degradation subject to a parameter count constraint.
• It introduced the concept of using loss landscape curvature (the Hessian) to judge parameter importance.
• While its diagonal approximation is crude, it demonstrated that better importance metrics exist beyond weight magnitude. Modern gradient-based methods like Movement Pruning are intellectual descendants of this idea.

Understanding OBD's limitations is key to placing it in the modern ML landscape.

• Computational Cost: Even with the diagonal approximation, computing the Hessian elements requires a backward pass per parameter, which was costly then and remains non-trivial for very large models.
• Accuracy of Approximation: The diagonal assumption is its weakest point, often leading to suboptimal pruning decisions compared to more modern criteria.
• Historical Artifact: Today, OBD is primarily of historical and pedagogical importance. Simpler methods like Iterative Magnitude Pruning (IMP) often achieve comparable or better results with less computational overhead, though they lack OBD's theoretical grounding.

Magnitude-based pruning is a heuristic technique that removes network parameters with the smallest absolute values, operating under the assumption that low-magnitude weights contribute less to the model's output. It is computationally cheap and forms the basis for many iterative pruning schedules.

• Key Mechanism: Ranks weights by absolute value and applies a global or local threshold.
• Contrast with OBD: Unlike OBD's second-order saliency estimate, magnitude pruning uses a first-order heuristic, making it faster but potentially less accurate in identifying truly unimportant parameters.
• Example: Pruning 50% of weights by removing all with |weight| < 0.01.

These terms define the granularity of the sparsity pattern introduced by pruning.

• Unstructured Pruning: Removes individual weights anywhere in the network, resulting in irregular sparsity. This is the type performed by OBD. It achieves high theoretical compression but requires specialized software or hardware (sparse kernels) for efficient inference.
• Structured Pruning: Removes entire structural components like neurons, channels, or filters. This results in a smaller, dense network that runs efficiently on standard hardware but may offer less fine-grained compression.
• Trade-off: Unstructured pruning (OBD's domain) typically allows for higher sparsity with less accuracy loss but complicates deployment.

Pruning-aware training is a model development paradigm where pruning constraints or regularizers are applied during the initial training process to encourage the emergence of sparsity-friendly representations. This contrasts with the classic OBD workflow of pruning a fully-trained network.

• Objective: Train a network that is inherently robust to parameter removal, often leading to better performance at high sparsity levels.
• Methods: Include techniques like adding L1 regularization to encourage small weights or using straight-through estimators to train with a sparse mask from the start.
• Evolution: Represents a shift from OBD's post-hoc analysis to designing models with compression as a first-class constraint.

The sparsity-accuracy tradeoff describes the fundamental inverse relationship between the level of sparsity (compression) induced in a model and its resulting predictive performance. Analyzing this tradeoff is critical for any pruning operation, including OBD.

• Central Challenge: The goal is to find the optimal point on the curve that meets deployment constraints (e.g., model size, latency) with minimal accuracy degradation.
• OBD's Role: By using a more accurate saliency metric (diagonal Hessian), OBD aims to produce a better tradeoff curve than simpler heuristics—more sparsity for the same accuracy loss.
• Visualization: Typically plotted as accuracy (y-axis) vs. sparsity percentage or model size (x-axis), creating a Pareto frontier.

Iterative Magnitude Pruning (IMP) is a widely adopted algorithm that alternates between training a model and pruning a fraction of the smallest-magnitude weights over multiple cycles. It is a practical successor to one-shot pruning methods.

• Process: 1) Train to convergence, 2) Prune a percentage (e.g., 20%) of lowest-magnitude weights, 3) Retrain the remaining network, 4) Repeat steps 2-3 until target sparsity is reached.
• Connection to OBD: IMP simplifies the saliency criterion to magnitude alone, forgoing OBD's Hessian calculation for scalability. The iterative retraining is crucial for recovering accuracy lost after pruning.
• Foundation: IMP is the experimental basis for the Lottery Ticket Hypothesis.

Hardware-aware pruning is a model compression approach that selects sparsity patterns and granularities specifically to maximize efficiency on a target hardware accelerator's execution engine and memory hierarchy. This modern focus extends beyond OBD's algorithmic saliency.

• Goal: Ensure the theoretical sparsity translates to actual latency, throughput, or energy savings on specific silicon (e.g., GPUs, NPUs, mobile CPUs).
• Pattern Examples: N:M Sparsity (e.g., 2:4), where in every block of 4 weights, 2 are zero, is designed to leverage NVIDIA's Sparse Tensor Cores.
• Contrast: While OBD produces unstructured sparsity, hardware-aware pruning often imposes structured constraints (like N:M or block-wise) to align with hardware capabilities, representing a co-design philosophy.