Research map / Learning theory and algorithms / Matrix and tensor methods
The Iterative Optimal Brain Surgeon: Faster Sparse Recovery by Leveraging Second-Order Information
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Iterative Optimal Brain Surgeon (I-OBS), an IHT-style sparse recovery method that uses Hessian curvature in the projection step, proving local quadratic convergence and applying it to one-shot and iterative pruning of DeiT, OPT, Phi-1.5 and Llama models.
Problem
Post-training pruning of DNNs with OBS-style heuristics works well empirically but lacks theoretical guarantees, and it is unclear whether curvature information can improve classic sparse recovery algorithms such as iterative hard thresholding.
Approach
Replace the Euclidean regularizer in the IHT/proximal step with a Hessian-weighted norm so that the sparse projection uses curvature (OBS-like); the resulting Top-k-I-OBS is a sparse Newton-type method with local quadratic convergence, and WoodFisher and OBC are shown to be special cases.
Key results
- On DeiT-Tiny at 50% sparsity, I-OBS with 50 iterations reaches 64.11% top-1 vs 62.98% for one-iteration SparseGPT (dense 72.08%).
- On Phi-1.5 at 50% sparsity, I-OBS(3) reaches C4 perplexity 20.26 vs 21.13 for SparseGPT (dense 20.90), and WikiText2 23.94 vs 25.28.
- In synthetic sparse linear regression, Top-k-I-OBS converges faster than k-IHT in loss and distance to optimum.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use I-OBS (3 iterations) instead of SparseGPT for 50% uniform pruning | OPT-125M · WikiText2 | perplexity: 33.85 -> 25.20 | Helped |
| Use I-OBS (3 iterations) instead of SparseGPT for 50% uniform pruning | OPT-125M · C4 | perplexity: 32.27 -> 31.41 | Helped |
| Use I-OBS (3 iterations) instead of SparseGPT for 50% uniform pruning | Phi-1.5 · WikiText2 | perplexity: 25.28 -> 23.94 | Helped |
| Use I-OBS (3 iterations) instead of SparseGPT for 50% uniform pruning | Phi-1.5 · C4 | perplexity: 21.13 -> 20.26 | Helped |
| Increase I-OBS pruning iterations from 1 to 75 (ablation) | DeiT-Tiny · ImageNet validation | Top-1 accuracy: 62.98 -> 64.13 | Helped |
| Increase I-OBS pruning iterations from 1 to 100 (ablation) | DeiT-Small · ImageNet validation | Top-1 accuracy: 76.07 -> 76.57 | Helped |
| Increase I-OBS pruning iterations from 1 to 75 (ablation) | DeiT-Base · ImageNet validation | Top-1 accuracy: 80.29 -> 80.46 | Helped |
| Increase pruning iterations beyond 75 (ablation) | DeiT-Tiny · ImageNet validation | Top-1 accuracy: 64.13 -> 64.05 | Hurt |
| Increase pruning iterations from 75 to 100 (ablation) | DeiT-Base · ImageNet validation | Top-1 accuracy: 80.46 -> 80.43 | Hurt |
| Use I-OBS rather than CBS | MobileNetV1 · 30%–50% sparsity | accuracy: 71.6 vs 71.88; 71.3 vs 71.45; 70.6 vs 70.21 | Mixed |
| Use I-OBS rather than CBS | MobileNetV1 · 60%–80% sparsity | accuracy: 68.4 vs 66.37; 60.7 vs 55.11; 27.9 vs 16.38 | Helped |
| Increase I-OBS iterations beyond 3 (ablation) | OPT-125M and Phi-1.5 · WikiText2 and C4 | perplexity | Mixed |
Surprising findings
- Iterating I-OBS on Llama models beyond the first fine-tuning iteration degrades MMLU and perplexity, which the authors attribute to overfitting the calibration set.
- Improvements from additional I-OBS iterations saturate quickly for larger DeiT models.
Limitations
- Theoretical guarantees are only local (require a good initialization) and rely on assumptions (strong convexity, restricted smoothness) that do not hold for DNN pruning.
- Exact I-OBS mask selection is NP-hard and the practical Top-k variant lacks the same guarantees.
- Llama experiments use iterative fine-tuning, and iterating too long overfits the calibration set.
Experimental setup
Datasets: ImageNet WikiText2 Red Pajama MNIST C4
Benchmarks: ImageNet WikiText2 C4 MMLU MobileNetV1 ImageNet (via CBS comparison)
Metrics: top-1 accuracy perplexity MMLU 5-shot accuracy training loss distance to optimum
Baselines: k-IHT SparseGPT OBC CBS WoodFisher
Builds on: Optimal Brain Surgeon Iterative Hard Thresholding OBC WoodFisher SparseGPT
Closest papers by meaning
- Straight-Through Meets Sparse Recovery: the Support Exploration Algorithm (ICML 2024 · similarity 0.88)
- Sparsity May Cry: Let Us Fail (Current) Sparse Neural Networks Together! (ICLR 2023 · similarity 0.88)
- Random Sparse Lifts: Construction, Analysis and Convergence of finite sparse networks (ICLR 2024 · similarity 0.87)
- A Single-Step, Sharpness-Aware Minimization is All You Need to Achieve Efficient and Accurate Sparse Training (NeurIPS 2024 · similarity 0.87)
- Optimal Eye Surgeon: Finding image priors through sparse generators at initialization (ICML 2024 · similarity 0.86)
- Global Minimizers of $\ell^p$-Regularized Objectives Yield the Sparsest ReLU Neural Networks (NeurIPS 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.