# The Iterative Optimal Brain Surgeon: Faster Sparse Recovery by Leveraging Second-Order Information

arXiv: https://arxiv.org/abs/2408.17163 · HTML: https://mlsanity.com/paper/2408.17163/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 45 references that are in the map.
- First posted on arXiv 30 Aug 2024.

## Builds on (most cited first, 22 of 22)

- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Distilling the Knowledge in a Neural Network](https://mlsanity.com/paper/1503.02531/) (2015)
- [SparseGPT: Massive Language Models Can Be Accurately Pruned in One-Shot](https://mlsanity.com/paper/2301.00774/) (2023)
- [LLM.int8(): 8-bit Matrix Multiplication for Transformers at Scale](https://mlsanity.com/paper/2208.07339/) (2022)
- [Sparsity in Deep Learning: Pruning and growth for efficient inference and training in neural networks](https://mlsanity.com/paper/2102.00554/) (2021)
- [ZeroQuant: Efficient and Affordable Post-Training Quantization for Large-Scale Transformers](https://mlsanity.com/paper/2206.01861/) (2022)
- [Why gradient clipping accelerates training: A theoretical justification for adaptivity](https://mlsanity.com/paper/1905.11881/) (2019)
- [Optimal Brain Compression: A Framework for Accurate Post-Training Quantization and Pruning](https://mlsanity.com/paper/2208.11580/) (2022)
- [SqueezeLLM: Dense-and-Sparse Quantization](https://mlsanity.com/paper/2306.07629/) (2023)
- [Model compression via distillation and quantization](https://mlsanity.com/paper/1802.05668/) (2018)
- [Learning to Prune Deep Neural Networks via Layer-wise Optimal Brain Surgeon](https://mlsanity.com/paper/1705.07565/) (2017)
- [ReLoRA: High-Rank Training Through Low-Rank Updates](https://mlsanity.com/paper/2307.05695/) (2023)
- [Dynamic Model Pruning with Feedback](https://mlsanity.com/paper/2006.07253/) (2020)
- [Apprentice: Using Knowledge Distillation Techniques To Improve Low-Precision Network Accuracy](https://mlsanity.com/paper/1711.05852/) (2017)
- [AC/DC: Alternating Compressed/DeCompressed Training of Deep Neural Networks](https://mlsanity.com/paper/2106.12379/) (2021)
- [RoSA: Accurate Parameter-Efficient Fine-Tuning via Robust Adaptation](https://mlsanity.com/paper/2401.04679/) (2024)
- [The Combinatorial Brain Surgeon: Pruning Weights That Cancel One Another in Neural Networks](https://mlsanity.com/paper/2203.04466/) (2022)
- [Fast as CHITA: Neural Network Pruning with Combinatorial Optimization](https://mlsanity.com/paper/2302.14623/) (2023)
- [Regularized Newton Method with Global O(1/k2) Convergence](https://mlsanity.com/paper/2112.02089/) (2021)
- [Supervision Complexity and its Role in Knowledge Distillation](https://mlsanity.com/paper/2301.12245/) (2023)
- [Global and Quadratic Convergence of Newton Hard-Thresholding Pursuit](https://mlsanity.com/paper/1901.02763/) (2019)
- [Newton-Step-Based Hard Thresholding Algorithms for Sparse Signal Recovery](https://mlsanity.com/paper/2001.07181/) (2020)

## Built on by (most cited first, 8 of 8)

- [SparseSSM: Efficient Selective Structured State Space Models Can Be Pruned in One-Shot](https://mlsanity.com/paper/2506.09613/) (2025)
- [HARP: Hadamard-Preconditioned Adaptive Rotation Processor for Extreme LLM Quantization](https://mlsanity.com/paper/2605.29843/) (2026)
- [WeightLoRA: Keep Only Necessary Adapters](https://mlsanity.com/paper/2506.02724/) (2025)
- [On Information Geometry and Iterative Optimization in Model Compression: Operator Factorization](https://mlsanity.com/paper/2507.09428/) (2025)
- [Train Large, Deploy Compact: Structured Compression for Compact Low-Rank Adaptation](https://mlsanity.com/paper/2510.00192/) (2025)
- [Frustratingly Easy Task-aware Pruning for Large Language Models](https://mlsanity.com/paper/2510.22489/) (2025)
- [Optimization over Trained (and Sparse) Neural Networks: A Surrogate within a Surrogate](https://mlsanity.com/paper/2505.01985/) (2025)
- [When Compression Scores Cannot Decide: Information Boundaries for Group-Robust LLM Pruning](https://mlsanity.com/paper/2608.02940/) (2026)

## Abstract (arXiv)

The rising footprint of machine learning has led to a focus on imposing model sparsity as a means of reducing computational and memory costs. For deep neural networks (DNNs), the state-of-the-art accuracy-vs-sparsity is achieved by heuristics inspired by the classical Optimal Brain Surgeon (OBS) framework~citeplecun90brain, hassibi1992second, hassibi1993optimal, which leverages loss curvature information to make better pruning decisions. Yet, these results still lack a solid theoretical understanding, and it is unclear whether they can be improved by leveraging connections to the wealth of work on sparse recovery algorithms. In this paper, we draw new connections between these two areas and present new sparse recovery algorithms inspired by the OBS framework that comes with theoretical guarantees under reasonable assumptions and have strong practical performance. Specifically, our work starts from the observation that we can leverage curvature information in OBS-like fashion upon the projection step of classic iterative sparse recovery algorithms such as IHT. We show for the first time that this leads both to improved convergence bounds under standard assumptions. Furthermore, we present extensions of this approach to the practical task of obtaining accurate sparse DNNs, and validate it experimentally at scale for Transformer-based models on vision and language tasks.