Structured vs. Unstructured Pruning: An Exponential Gap

Dit paper toont aan dat er een exponentieel verschil bestaat tussen gestructureerde en ongestructureerde pruning, waarbij het benaderen van een ReLU-neuron via neuron-pruning aanzienlijk meer overparameterisatie vereist dan via gewichts-pruning.

De kern

Het Grote Verhaal: De "Winnende Loterij" in een Netwerk

Stel je voor dat je een enorm, ondoorzichtig labyrint bouwt met miljoenen muren en deuren. Dit is een neuraal netwerk (de hersenen van een computer). Meestal trainen we deze netwerken door ze duizenden keren door het labyrint te sturen, zodat ze de kortste weg leren vinden.

Maar er is een fascinerend idee, de "Sterke Loterij Ticket Hypothese". Deze zegt: "Je hoeft het labyrint niet te leren! Als je het net zo groot bouwt, zit er al van nature een perfect, klein pad in verstopt. Je hoeft alleen maar de verkeerde muren weg te halen (prunen), en je hebt een perfect werkend systeem zonder ooit te hoeven leren."

Het probleem is: Hoe haal je die muren weg?

De Twee Manieren om te "Prunen" (Weghalen)

In dit artikel vergelijken de auteurs twee manieren om dit labyrint te versimpelen:

1. Ongestructureerd Weghalen (Gewichtspruning):

   • De analogie: Je hebt een muur met 100 bakstenen. Je mag één enkele steen uit elke muur verwijderen, waar je maar wilt. Je kunt de steen linksboven, rechtsonder of in het midden eruit halen.
   • Het resultaat: Je hebt nog steeds een muur, maar hij zit vol met gaten. Het ziet er rommelig uit, maar je kunt de weg nog steeds vinden.
   • De theorie: Wetenschappers wisten al dat je met deze methode een heel klein netwerk kunt maken dat bijna perfect werkt, zelfs als je maar heel weinig extra ruimte (overparametrisatie) hebt. Het is alsof je met een heel klein aantal extra stenen een perfect pad kunt bouwen.

2. Gestructureerd Weghalen (Neuronen-pruning):

   • De analogie: Je mag geen losse stenen meer weghalen. Je mag alleen hele kolommen van bakstenen verwijderen. Als je een kolom verwijdert, verdwijnt die hele verticale rij.
   • Het voordeel: Dit is veel handiger voor de computerhardware. Het is makkelijker om een hele kolom weg te halen dan om 100 losse stenen op willekeurige plekken te verwijderen. Het maakt het systeem sneller en compacter.
   • Het probleem: Dit is veel moeilijker om goed te doen zonder de weg te blokkeren.

De Ontdekking: Een Enorme Kloof

De auteurs van dit artikel (uit 2026) hebben gekeken naar een heel simpel geval: een computer die één simpele taak moet leren (een rechte lijn tekenen die bij 0 stopt). Ze keken of ze dit konden bereiken door alleen hele kolommen (neuronen) weg te halen.

Hun conclusie is schokkend:
Om die ene simpele taak perfect te doen met alleen het weghalen van hele kolommen, moet je enorm veel extra kolommen hebben om mee te beginnen.

• Met losse stenen weghalen: Je hebt een beetje extra ruimte nodig (ongeveer evenveel als het aantal letters in een woord).
• Met hele kolommen weghalen: Je hebt een exponentieel grotere ruimte nodig.

De Analogie van de Zoektocht:
Stel je voor dat je een sleutel zoekt in een kamer.

• Bij loze stenen weghalen (gewichtspruning) mag je elke steen apart controleren. Je vindt de sleutel snel, zelfs als de kamer niet heel groot is.
• Bij kolommen weghalen (neuronen-pruning) mag je alleen hele planken weghalen. Als de sleutel op een specifieke, kleine plek in een plank zit, moet je die hele plank hebben om de sleutel te vinden. Als je de plank niet hebt, is de sleutel weg. Om zeker te zijn dat je alle mogelijke plekken waar de sleutel zou kunnen zitten, hebt, moet je de kamer enorm groot maken.

Waarom is dit belangrijk?

1. Hardware vs. Theorie: Computers werken sneller met "kolommen" (gestructureerd) dan met "losse gaten" (ongestructureerd). Maar dit artikel zegt: "Als je echt efficiënt wilt zijn en alleen kolommen wilt weghalen, moet je je netwerk gigantisch groot maken om het te laten werken."
2. De "Exponentiële Kloof": Het verschil tussen de twee methoden is niet klein; het is als het verschil tussen een fiets en een raket. Als je een netwerk wilt verkleinen door alleen neuronkolommen te verwijderen, moet je het oorspronkelijke netwerk veel, veel groter maken dan wanneer je losse gewichten mag verwijderen.

Samenvatting in één zin

Je kunt een neuraal netwerk wel verkleinen door alleen hele blokken (neuronen) weg te halen, maar om dat goed te doen zonder het systeem te breken, moet je het oorspronkelijke netwerk exponentieel groter maken dan wanneer je gewoon losse onderdelen mag verwijderen.

Kortom: Het is makkelijker om een netwerk te "snoeien" door losse takken te knippen dan door hele takken te verwijderen, en de prijs voor het verwijderen van hele takken is dat je een veel grotere boom nodig hebt om te beginnen.

Technische samenvatting

Titel: Gestructureerd versus Ongestructureerd Pruning: Een Exponentiële Kloof

Auteurs: Davide Ferré, Frédéric Giroire, Frederik Mallmann-Trenn, en Emanuele Natale.
Datum: 5 maart 2026

---

1. Probleemstelling

Het artikel onderzoekt de theoretische beperkingen van pruning (het verwijderen van parameters uit een neuraal netwerk) binnen de context van de Sterke Loterij Ticket Hypothese (SLTH). De SLTH stelt dat grote, willekeurig geïnitieerde netwerken subnetwerken bevatten die een doelfunctie kunnen benaderen zonder dat er training nodig is; alleen pruning volstaat.

Er wordt een onderscheid gemaakt tussen twee benaderingen:

• Ongestructureerd pruning (Weight Pruning): Het verwijderen van individuele gewichten (kanten) in het netwerk. Bestaande theorie toont aan dat dit zeer efficiënt is; een netwerk met een logaritmische overparametrisatie ($O(\log(1/\varepsilon))$) volstaat om een doelfunctie te benaderen.
• Gestructureerd pruning (Neuron Pruning): Het verwijderen van volledige eenheden (neuronen), wat overeenkomt met het verwijderen van rijen en kolommen in de gewichtsmatrices. Dit is praktischer voor hardware-versnelling, maar de theoretische onderbouwing is beperkt.

De kernvraag: Is neuron pruning even effectief als weight pruning voor het benaderen van een doelfunctie, of zijn er fundamentele beperkingen? Voorgaande resultaten suggereerden dat neuron pruning zwakker is, maar deze waren vaak afhankelijk van de aanwezigheid van grote biases in de doelfuncties. Het artikel onderzoekt of deze inefficiëntie ook geldt in een "schone" setting zonder biases.

2. Methodologie

De auteurs analyseren het probleem door een specifiek, vereenvoudigd scenario te isoleren:

• Doel: Het benaderen van een enkele bias-vrije ReLU-neuron ($f(x) = \sigma(\langle w^*, x \rangle)$) met een willekeurig geïnitieerd, tweelaags ReLU-netwerk zonder biases.
• Beperking: Alleen neuron pruning is toegestaan; de gewichten van de overgebleven neuron worden niet aangepast.
• Analysestrategie:
  1. Breakpoint-tracking: De auteurs analyseren het gedrag van het netwerk langs specifieke één-dimensionale inputpaden. Een ReLU-netwerk is stuksgewijs lineair; de overgangspunten (breakpoints) worden bepaald door de gewichten.
  2. Stochastisch proces: Het selecteren van een subset van neuron wordt gemodelleerd als een stochastisch proces waarbij het aantal "gebroken" bins (intervallen waarin de functie niet-lineair is) evolueert.
  3. Koppeling (Coupling): Om de analyse hanteerbaar te maken, koppelen ze het originele pruning-proces aan een vereenvoudigd "birth-death" proces (geboorte-sterfte proces). Dit dominante proces schat de kans op succesvolle benadering van bovenaf.
  4. Unie-bounds: Ze gebruiken een unie-bound over alle mogelijke subsets van neuron om de totale kans te berekenen dat minstens één subnetwerk de doelfunctie binnen een foutmarge $\varepsilon$ benadert.

3. Belangrijkste Bijdragen

• Fundamentele Ondergrens voor Neuron Pruning: Het artikel bewijst dat om een enkele bias-vrije ReLU-neuron met een foutmarge $\varepsilon$ te benaderen via neuron pruning, het startnetwerk minimaal $\Omega(d/\varepsilon)$ verborgen neuron moet bevatten (waarbij $d$ de inputdimensie is).
• Exponentiële Scheiding: Dit resulteert in een exponentiële kloof tussen de twee methoden:
  • Weight pruning: Vereist $O(d \log(1/\varepsilon))$ neuron.
  • Neuron pruning: Vereist $\Omega(d/\varepsilon)$ neuron.
    De afhankelijkheid van $\varepsilon$ is lineair bij neuron pruning versus logaritmisch bij weight pruning.
• Technische Innovatie: De auteurs ontwikkelen een nieuwe bewijsstrategie die werkt zonder de complicatie van biases, waardoor wordt aangetoond dat de inefficiëntie inherent is aan de structuur van neuron pruning en niet alleen een artefact is van grote biases in de doelfunctie.

4. Resultaten

Het hoofdresultaat is Stelling 1 (Theorem 1):
Voor een inputdimensie $d \geq 2$ en een nauwkeurigheid $\varepsilon \in (0, 1)$, als het aantal verborgen neuron $N_h$ kleiner is dan $c \cdot \frac{d}{\varepsilon}$ (voor een zekere constante $c$), dan is de kans dat er een subset van neuron bestaat die de doelfunctie $\varepsilon$-benadert, verwaarloosbaar klein (exponentieel afnemend in $d$).

De analyse toont aan dat neuron pruning worstelt met het "oplossen" van de breakpoints. Omdat het hele neuron wordt verwijderd, kan men niet subtiel de gewichten aanpassen om een breakpoint op de juiste locatie te plaatsen. Men is afhankelijk van toeval dat een neuron precies de juiste breakpoint heeft, wat statistisch zeer onwaarschijnlijk is tenzij het netwerk extreem groot is.

5. Betekenis en Conclusie

• Theoretisch Inzicht: Het werk legt een fundamenteel theoretisch verschil bloot tussen gestructureerd en ongestructureerd pruning. Hoewel neuron pruning wenselijk is voor hardware-efficiëntie (omdat het echte matrixverkleining oplevert), is het theoretisch gezien een veel zwakkere methode voor het vinden van "winning tickets" in willekeurig geïnitieerde netwerken.
• Implicaties voor de SLTH: De Strong Lottery Ticket Hypothese geldt dus niet op dezelfde manier voor gestructureerd pruning. De overparametrisatie die nodig is om een subnetwerk te vinden dat zonder training werkt, is veel groter bij neuron pruning dan bij weight pruning.
• Toekomstig Onderzoek: De auteurs speculeren dat de ondergrens zelfs exponentieel in $d$ zou kunnen zijn (in plaats van lineair), wat de kloof met weight pruning nog verder zou vergroten. Dit blijft een open vraag voor verder onderzoek.

Samenvattend: Dit artikel bewijst dat er een exponentiële kloof bestaat tussen de efficiëntie van weight pruning en neuron pruning. Neuron pruning vereist een veel grotere overparametrisatie om dezelfde benaderingsnauwkeurigheid te bereiken, wat suggereert dat het vinden van performante subnetwerken door alleen neuron te verwijderen, fundamenteel moeilijker is dan het selecteren van individuele gewichten.