🤖 machine learning

A Unified Framework for Quantized and Continuous Strong Lottery Tickets

Dit artikel presenteert een verenigd raamwerk voor de Strong Lottery Ticket Hypothesis dat het Random Subset Sum Problem in discrete settings analyseert om nauwe gekwantiseerde garanties af te leiden, die eerdere resultaten exponentieel verbeteren en zowel continue als gekwantiseerde regimes natuurlijk omvatten als limietgevallen.

Oorspronkelijke auteurs: Aakash Kumar, Emanuele Natale

Gepubliceerd 2026-07-07

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Aakash Kumar, Emanuele Natale

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Het Grote Idee: Een Naald in een Hooiberg Zoeken (Zonder te Kijken)

Stel je voor dat je een enorme, chaotische bibliotheek hebt vol met miljoenen boeken (een enorme, willekeurig opgebouwde neurale netwerk). Je bent op zoek naar een heel specifiek, klein verhaal (een kleiner, getraind neuraal netwerk) dat een perfect verhaal vertelt.

De Strong Lottery Ticket Hypothesis (SLTH) is een gedurfde bewering: het zegt dat als je bibliotheek groot genoeg is, het perfecte verhaal al verborgen zit in de willekeurige boeken. Je hoeft geen nieuw verhaal te schrijven of de bestaande verhalen aan te passen (trainen); je hoeft alleen de juiste pagina's te vinden en de rest eruit te scheuren (pruning).

Lange tijd hebben wetenschappers bewezen dat dit werkt als de boeken zijn geschreven met oneindige precisie (zoals een pen die elke tint grijs kan schrijven). Maar in de echte wereld zijn computers als printers die alleen in specifieke, discrete stappen kunnen printen (zoals zwart, donkergrijs, lichtgrijs en wit). Dit wordt kwantisatie genoemd.

Deze paper vraagt zich af: Werkt de "naald in de hooiberg"-truc nog steeds als onze boeken gedrukt zijn in deze beperkte, blokkerige stappen?

Het Probleem: De "Afrondings"-kloof

Vorig onderzoek kende twee aparte kampen:

Het Continue Kamp: Bewees dat je de naald kunt vinden als je oneindige precisie hebt, maar de wiskunde was rommelig en hield geen rekening met de beperkingen van echte computers.
Het Gekwantiseerde Kamp: Probeerde dit te bewijzen voor blokkerige, beperkte-precisie computers, maar de wiskunde was zwak. Het suggereerde dat je misschien een enorme bibliotheek nodig hebt om de naald te vinden, en dat de kans op falen langzaam afnam (zoals een langzame lek in een band).

De auteurs van deze paper wilden een brug slaan tussen deze twee werelden. Ze wilden bewijzen dat je zelfs met beperkte precisie het perfecte sub-netwerk kunt vinden, en dat de kans dat je het niet vindt extreem snel afneemt (zoals een band die direct klapt als je niet genoeg lucht hebt).

Het Gereedschap: Het "Subset Sum"-spel

Om dit op te lossen, gebruikten de auteurs een klassieke wiskundige puzzel genaamd het Random Subset Sum Problem.

De Analogie:
Stel je voor dat je een zak met willekeurige gewichten hebt (sommige zwaar, sommige licht). Je wilt er een paar uitkiezen om op een weegschaal te leggen om exact een specifieke doelgewicht te bereiken.

De Oude Manier: Als de gewichten glad en continu zijn, is het makkelijk om een combinatie te vinden die het doel raakt.
De Nieuwe Uitdaging: Als de gewichten "blokkerig" zijn (alleen specifieke waarden toegestaan), lijkt dit veel moeilijker. Je zou kunnen denken dat je het doel nooit exact zult raken.

De auteurs ontwikkelden een nieuw, scherper wiskundig instrument om dit "blokkerige" spel te analyseren. Ze bewezen dat zelfs met deze blokkerige gewichten, als je er genoeg hebt, je bijna zeker een combinatie kunt vinden die het doel perfect raakt.

De Doorbraak: Het Verenigen van de Twee Werelden

De grootste prestatie van de paper is het aantonen dat de "gladde" wereld en de "blokkerige" wereld eigenlijk twee kanten van dezelfde munt zijn.

Het "Magische Getal": De auteurs vonden een enkele formule die berekent hoe groot je bibliotheek (netwerk) moet zijn.
De Limiet-truc:
- Als je de "blokken" oneindig klein maakt (glad), verandert hun formule in de oude, beroemde resultaten voor continue netwerken.
- Als je de blokken groot houdt (gekwantiseerd), verandert hun formule in de resultaten voor discrete netwerken.

Dit betekent dat ze niet alleen een nieuw probleem hebben opgelost; ze hebben laten zien dat alle eerdere oplossingen slechts speciale gevallen waren van hun nieuwe, verenigde theorie.

Het Resultaat: Een Supersterke Garantie

Het meest opwindende deel is de waarschijnlijkheid.

Oude Resultaten: In de blokkerige wereld nam de kans op falen bij het vinden van de naald langzaam af (inverse-polynomiaal). Het was alsoverzeggen: "Als je 100 keer probeert, zul je misschien slagen."
Nieuwe Resultaten: De auteurs bewezen dat de kans op falen exponentieel afneemt. Dit is alsof je zegt: "Als je slechts een klein beetje extra bibliotheekruimte toevoegt, wordt de kans op falen praktisch nul."

Ze lieten zien dat een willekeurig geïnitialiseerd, blokkerig netwerk kan worden gesnoeid om een doelnetwerk perfect na te bootsen, en de wiskunde garandeert dat dit met overweldigende zekerheid gebeurt, mits het netwerk groot genoeg is.

Samenvatting in een Notendop

Het Doel: Bewijzen dat enorme, willekeurige, "blokkerige" computernetwerken perfecte, kleinere versies van zichzelf bevatten, klaar om eruit te worden gesneden.
De Methode: Ze hebben een moeilijke wiskundige puzzel (Subset Sum) opgelost, specifiek voor "blokkerige" getallen.
De Ontdekking: Ze creëerden één enkel kader dat zowel "gladde" als "blokkerige" netwerken verklaart.
De Beloning: Ze bewezen dat het vinden van deze verborgen netwerken niet alleen mogelijk is, maar ook extreem waarschijnlijk (exponentieel hoog), waarmee ze de zwakke garanties van eerder onderzoek hebben gecorrigeerd.

Kortom: Ze hebben bewezen dat zelfs met de beperkingen van de precisie van echte computers, de "magie" van het vinden van perfecte sub-netwerken binnen willekeurige netwerken echt, betrouwbaar en wiskundig onderbouwd is.

Technische Samenvatting: Een Verenigd Raamwerk voor Gekwantiseerde en Continue Sterke Loterijtickets

Probleemstelling

De Strong Lottery Ticket Hypothesis (SLTH) stelt dat voldoende overgeparameteriseerde, willekeurig geïnitialiseerde neurale netwerken ijle sub-netwerken bevatten die in staat zijn de prestaties van een kleiner getraind netwerk te evenaren zonder gewichtupdates uit te voeren. Hoewel de theoretische fundamenten van SLTH sterk leunen op het Random Subset Sum Problem (RSSP), is de bestaande literatuur grotendeels beperkt gebleven tot de continue setting (gewichten met willekeurige precisie).

Recente uitbreidingen naar de gekwantiseerde setting, waarbij gewichten worden gesampled uit discrete verzamelingen, zijn geconfronteerd met significante beperkingen. Eerdere werken in dit domein (bijv. Diffenderfer en Kailkhura [2021], Sreenivasan et al. [2022], Kumar en Natale [2025]) beperkten zich ofwel tot doelnetwerken met continue gewichten terwijl ze benaderingen met binaire netwerken gebruikten, of boden garanties voor exacte representaties in gekwantiseerde settings met slechts een inverse-polynomiale afname van de faalkans. Bovendien behandelden deze benaderingen benaderde representaties (continu) en exacte representaties (gekwantiseerd) als gescheiden onderzoekslijnen, zonder een verenigd theoretisch raamwerk dat zowel afrondingsfouten als benaderingsfouten gelijktijdig kan verklaren.

Methodologie

De auteurs pakken deze hiaten aan door een rigoureuze analyse van de RSSP in de discrete setting te ontwikkelen en deze toe te passen op de gekwantiseerde SLTH.

1. Discreet Random Subset Sum Problem (RSSP)

De kern van de wiskundige bijdrage is een nieuwe analyse van de discrete RSSP. De auteurs definiëren het probleem waarbij willekeurige variabelen $X_1, \dots, X_n$ uniform worden gesampled uit een discrete verzameling $\{-M, \dots, M\}$ , en het doel is om een deelverzameling te vinden die een doel $z$ benadert binnen een tolerantie $\Delta$ .

Recurrente Relatie: De analyse maakt gebruik van een recurrente relatie voor de indicatorfunctie $f_t(z)$ , die vertegenwoordigt of een doel $z$ op tijdstip $t$ binnen $\Delta$ wordt benaderd.
Volume Groei Analyse: De auteurs volgen de groei van het "volume" $v_t$ $v_{t}$ , gedefinieerd als het aantal verschillende waarden in het bereik $\{-M, \dots, M\}$ ${- M, \dots, M}$ dat binnen $\Delta$ $Δ$ kan worden benaderd. Ze bewijzen dat $v_t$ $v_{t}$ in twee verschillende fasen groeit:
1. Snelle Groei: $v_t$ bereikt snel $M+1$ .
2. Langzame Groei: $v_t$ stijgt langzaam om het volledige bereik $2M+1$ te dekken.
Probabilistische Grenzen: Door deze fasen te analyseren met behulp van martingale-achtige argumenten en concentratie-ongelijkheden (specifiek door gebruik te maken van de reverse Markov-ongelijkheid en de Hoeffding-bound), leiden de auteurs nauwe grenzen af voor de tijd $\tau$ die nodig is om de gehele verzameling binnen $\Delta$ te benaderen.

2. Toepassing op Gekwantiseerde SLTH

De auteurs breiden de resultaten van Cunha et al. [2023] van de continue RSSP uit naar de discrete setting om SLTH-garanties voor gekwantiseerde netwerken vast te stellen.

Netwerkconstructie: Ze beschouwen een willekeurig geïnitialiseerd, overgeparameteriseerd netwerk $g$ met $2\ell$ lagen, waarbij de gewichten uniform worden getrokken uit een discrete verzameling $S_\delta$ (precisie $\delta$ ).
Pruning Strategie: Het doel is om $g$ te snoeien (pruning) om een doel $\ell$ -laags netwerk $f$ met gewichten in $S_\delta$ te benaderen. Het snoeiproces wordt gedecomposeerd in het oplossen van een collectie onafhankelijke RSSP-instanties voor individuele gewichten en neuronen.
Foutpropagatie: Het bewijs volgt de strategie van Pensia et al. [2020], waarbij de benaderingsgarantie wordt opgetild van een enkel gewicht naar een neuron, vervolgens naar een laag, en uiteindelijk naar het gehele netwerk. Cruciaal is dat de analyse de foutpropagatie door niet-lineariteiten (ReLU) volgt en rekening houdt met de accumulatie van fouten over de lagen heen.

Belangrijkste Bijdragen

Nauwkeurige Grenzen voor Discrete RSSP: Het artikel stelt nieuwe, scherpe probabilistische grenzen vast voor de discrete RSSP. In tegen tegenstelling tot eerdere discrete analyses (zoals Kumar en Natale [2025]) die een inverse-polynomiale afname van de faalkans opleverden, bewijst dit werk een exponentieel kleine faalkans in het aantal precisiebits.
Verenigd Raamwerk: Het voorgestelde raamwerk verenigt de literatuur door aan te tonen dat:
- Benaderde representaties in de continue setting (zoals in Malach et al. [2020], Pensia et al. [2020]) verschijnen als een limietgeval wanneer de precisie $\delta \to 0$ .
- Exacte representaties in de gekwantiseerde setting (zoals in Kumar en Natale [2025]) verschijnen als een limietgeval wanneer de tolerantie $\Delta = 0$ .
- Het raamwerk behandelt gelijktijdig zowel afrondingsfouten (door kwantisatie) als benaderingsfouten (door pruning).
Verbeterde Overparameterisatie Garanties: De auteurs leiden af dat een diepte- $2\ell$ willekeurig netwerk met breedte $O(d \log(1/\delta))$ (waarbij $d$ de doelbreedte is en $\delta$ de precisie) kan worden gesnoeid om elk doelnetwerk van diepte $\ell$ en breedte $d$ tot $\epsilon$ te benaderen.

Resultaten

Theoretische Garanties: De hoofdbestelling (Theorem 3) stelt dat met een hoge waarschijnlijkheid ( $1 - 4d^{2\ell} \exp(-C'n)$ ), een willekeurig geïnitialiseerd $2\ell$ -laags gekwantiseerd netwerk kan worden gesnoeid om elk doel $\ell$ -laags gekwantiseerd netwerk binnen fout $\epsilon$ te benaderen. De faalkans neemt exponentieel af met de overparameterisatiefactor.
Experimentele Validatie:
- Subset Sum Experimenten: De auteurs hebben de discrete RSSP-theorie empirisch gevalideerd, waarbij zij observeerden dat de kans op het oplossen van een exact subset sum probleem ( $\Delta=0$ ) de 1 nadert wanneer het aantal samples $n \gtrsim C \log(M)$ , met $C \approx 1.5$ .
- Efficiëntie van Pruning: In een praktische test slaagden de auteurs erin om een sub-netwerk te identificeren dat een ResNet-50 (25 miljoen parameters, FP8 precisie) benadert door de vereiste RSSP-instanties op te lossen. Dit proces duurde ongeveer 33 minuten op een enkele CPU zonder parallellisatie, wat de computationele haalbaarheid aantoont.

Betekenis en Claims

Het artikel claimt een fundamentele stap te bieden naar een samenhangende theorie van sterke loterijtickets die de kloof tussen continue en gekwantiseerde settings overbrugt. Door deze voorheen gescheiden onderzoekslijnen te verenigen, werkt het:

Bestaande grenzen aanscherpt: Het verbetert de garantie voor de faalkans van een inverse-polynomiale naar een exponentiële afname in het gekwantiseerde regime.
Praktische relevantie vergroot: Het adresseert de realiteit van rekenen met eindige precisie (kwantisatie) terwijl het de theoretische strengheid van benaderingsgaranties behoudt.
Het veld verenigt: Het toont aan dat zowel benaderde continue representaties als exacte gekwantiseerde representaties speciale gevallen zijn van één enkel, algemener raamwerk.

De auteurs benadrukken dat hun resultaten de bestaande empirische observaties ondersteunen met betrekking tot het bestaan van loterijtickets in gekwantiseerde netwerken en een sterkere theoretische basis bieden voor het gebruik van pruning in omgevingen met beperkte middelen en eindige precisie.