📊 statistics

Two-Sided Nearest Neighbors: An adaptive and minimax optimal procedure for matrix completion

Dit artikel stelt een tweezijdig nearest neighbor-algoritme voor voor matrixcompletie onder latente niet-lineaire factormodellen met lage gladheid en hoge ontbreken, waarbij wordt bewezen dat het minimax optimale foutenmarges bereikt die zich aanpassen aan de gladheid van de onderliggende functie en de prestaties van een oracle evenaart, zelfs bij deterministische ontbrekende invoer.

Oorspronkelijke auteurs: Tathagata Sadhukhan, Manit Paul, Raaz Dwivedi

Gepubliceerd 2026-08-26

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Tathagata Sadhukhan, Manit Paul, Raaz Dwivedi

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

In het digitale tijdperk worden we voortdurend omringd door enorme rasters van informatie, van de films die een streamingdienst aanbeveelt tot de dagelijkse stappen die een gezondheidsapp bijhoudt. Deze rasters zijn zelden compleet; gebruikers slaan beoordelingen over, sensoren falen bij het registreren van gegevens, en mensen verschijnen simpelweg niet bij elke geplande controle. De uitdaging voor wetenschappers is om deze ontbrekende stukjes nauwkeurig in te vullen zonder valse informatie te verzinnen. Dit probleem, bekend als matrixcompletie, rust op het idee dat verborgen patronen de gegevens die we zien verbinden met de gegevens die we niet zien. Als een persoon die van actiefilms houdt ook de neiging heeft om sciencefiction te waarderen, kan een systeem die connectie gebruiken om te raden wat diegene van een nieuwe film zou vinden die nog niet is gezien. De werkelijkheid is echter rommelig. De ontbrekende informatie is vaak niet willekeurig; een gebruiker kan een film alleen overslaan omdat hij de film zo verschrikkelijk vond dat hij de moeite niet meer nam om hem te beoordelen, of een sensor kan alleen onder specifieke omstandigheden falen. Bovendien zijn de relaties tussen gebruikers en items vaak complex en niet-lineair, wat betekent dat eenvoudige rechte regels niet het volledige beeld kunnen vatten.

Een team onderzoekers van de Cornell University en de University of Pennsylvania heeft een nieuwe methode ontwikkeld om dit moeilijke puzzelstukje aan te pakken, specifiek wanneer de gegevens op een bevooroordeelde manier ontbreken en de onderliggende patronen complex zijn. Ze richtten zich op een techniek genaamd 'nearest neighbors' (dichtstbijzijnde buren), die werkt door vergelijkbare rijen en kolommen in een gegevensraster te vinden om voorspellingen te doen. Hoewel deze benadering eerder is bestudeerd, gingen eerdere theorieën er vaak vanuit dat de gegevens willekeurig ontbraken of dat de relaties tussen gegevenspunten vloeiend en eenvoudig waren. De onderzoekers vroegen zich af of deze methode nog steeds kon werken wanneer de gegevens ontbreken vanwege de zeer specifieke waarden die ze bevatten, en wanneer de verbindingen tussen gebruikers en items grillig en onregelmatig zijn in plaats van vloeiend.

Om dit te beantwoorden, analyseerde het team een tweezijdige nearest neighbor-algoritme. Stel je een raster voor waarbij de rijen mensen vertegenwoordigen en de kolommen momenten in de tijd of specifieke gebeurtenissen. Het algoritme zoekt naar mensen die zich vergelijkbaar gedragen als de persoon in kwestie, en het zoekt ook naar momenten die vergelijkbaar zijn met het moment in kwestie. Door de bekende uitkomsten van deze vergelijkbare mensen en vergelijkbare momenten te middelen, schat de methode de ontbrekende waarde in. De onderzoekers bewezen wiskundig dat deze benadering zich aanpast aan de complexiteit van de gegevens. Als de verborgen patronen zeer ruw en onregelmatig zijn, past de methode zijn zoektocht aan om de juiste mate van gelijkenis te vinden. Als de patronen vloeiender zijn, verfijnt de methode de zoektocht dienovereenkomstig. Cruciaal was dat ze lieten zien dat deze methode net zo goed presteert als een perfect, alwetend systeem dat al over de verborgen factoren beschikt die de gegevens aansturen, ook al kent het algoritme zelf die factoren niet.

De studie toonde ook aan dat de methode robuust blijft, zelfs wanneer een aanzienlijk deel van de gegevens op een deterministische manier ontbreekt. Denk bijvoorbeeld aan een scenario waarin twintig procent van de gegevens gegarandeerd ontbreekt vanwege een specifieke regel — zoals een gebruiker die nooit een melding ontvangt als hij niet beschikbaar is — het algoritme slaagt er nog steeds in. Het stort niet in wanneer de ontbrekende gegevens niet willekeurig zijn, maar gekoppeld zijn aan de onderliggende structuur van het systeem. De onderzoekers valideerden deze theoretische bevindingen via uitgebreide computersimulaties, waarbij ze de methode testten tegen diverse andere technieken. In deze tests presteerde hun tweezijdige benadering consequent beter dan standaardmethoden, waarbij een gestage daling in foutmarges werd waargenomen naarmate er meer gegevens beschikbaar kwamen, terwijl andere methoden moeite hadden of niet verbeterden.

Om te zien hoe dit in de echte wereld werkt, paste het team hun methode toe op gegevens van een mobiele gezondheidsstudie genaamd HeartSteps. Deze studie omvatte zevenendertig deelnemers die meldingen op hun telefoon ontvingen om wandelen te stimuleren. Het doel was om te schatten hoeveel stappen een persoon zou hebben gezet als hij een specifiek type melding had ontvangen, zelfs wanneer die melding niet daadwerkelijk was verzonden. Omdat deelnemers niet op elk moment beschikbaar waren, en omdat meldingen alleen met een bepaalde waarschijnlijkheid werden verzonden, waren de gegevens incompleet en bevooroordeeld. De onderzoekers behandelden de gebruikers als rijen en de beslissingstijden als kolommen, waardoor een raster met ontbrekende invoer ontstond. Wanneer zij hun methode vergeleken met andere, produceerde de tweezijdige nearest neighbor-benadering de meest nauwkeurige schattingen, met de kleinste fouten en de meest consistente resultaten. Het navigeerde succesvol door de ontbrekende gegevens om de waarschijnlijke uitkomsten van de interventies te onthullen.

De betekenis van dit werk ligt in het vermogen om om te gaan met de rommelige realiteit van menselijk gedrag en sensorgegevens. Door te bewijzen dat een relatief eenvoudige, adaptieve zoekstrategie de prestaties kan evenaren van een ideaal systeem met volledige kennis, hebben de onderzoekers een krachtig instrument geboden voor velden variërend van aanbevelingsmotoren tot medische onderzoeken. Ze toonden aan dat zelfs wanneer gegevens niet willekeurig ontbreken en de relaties complex zijn, we niet de verborgen oorzaken hoeven te kennen om nauwkeurige voorspellingen te doen. We hoeven alleen maar te kijken naar de buren in beide richtingen — over de mensen heen en over de tijd heen — en de patronen te laten ontstaan. Deze bevinding suggereert dat in een wereld van incomplete informatie, de juiste vorm van middelen de waarheid kan onthullen zonder eerst het hele mysterie te hoeven oplossen.

Technische Samenvatting: Two-Sided Nearest Neighbors voor Matrix Completion

Probleemstelling

Het artikel behandelt het matrix completion probleem binnen de context van latente factor modellen, waarbij specifiek wordt gefocust op situaties waarin de onderliggende grondwaarheid matrix $\Theta$ wordt gegenereerd door een niet-lineaire latente functie $f$ die werkt op onbekende rij- en kolomlatente factoren. Het model is gedefinieerd als:
$\theta_{i,j} = f(u_i, v_j)$
waarbij $u_i \in \mathbb{R}^{d_1}$ en $v_j \in \mathbb{R}^{d_2}$ latente factoren zijn, en $f$ behoort tot een Hölder functieklasse met een gladheidsparameter $\lambda \in (0, 1]$ . Deze setting generaliseert standaard bilaterale modellen (waarbij $f(u,v) = \langle u, v \rangle$ ) naar niet-parametrische, potentieel minder gladde functies (minder glad dan Lipschitz).

Een cruciale uitdaging die wordt aangepakt is het Missing Not At Random (MNAR) regime. In tegen tegenstelling tot Missing Completely At Random (MCAR), waarbij ontbreken onafhankelijk is van de data, gaat MNAR ervan uit dat de waarschijnlijkheid dat een invoer ontbreekt afhankelijk is van de ongeobserveerde latente factoren. Bovendien beschouwen de auteurs scenario's waarin invoer deterministisch ontbreekt (d.w.z. ontbreken met een waarschijnlijkheid van 0 voor specifieke configuraties), wat een veelvoorkomende situatie is in realistische systemen zoals aanbevelingsmotoren waar gebruikersvoorkeuren de zichtbaarheid dicteren.

Het doel is om de grondwaarheid $\theta_{i,j}$ te schatten voor zowel geobserveerde als ontbrekende invoer zonder voorafgaande kennis van de latente factoren $U$ en $V$ of de functie $f$ , terwijl minimax optimale snelheden worden bereikt.

Methodologie: Two-Sided Nearest Neighbors (TS-NN)

De auteurs stellen het Two-Sided Nearest Neighbor (TS-NN) algoritme voor. De kernintuïtie is het benaderen van de latente afstanden tussen rijen en kolommen met behulp van geobserveerde data, om vervolgens de uitkomsten over de resulterende buurten te middelen.

Afstandschatting: Omdat de latente functie $f$ onbekend is, construeert het algoritme datagedreven proxies voor de gekwadrateerde $L_2$ -afstanden tussen rijfactoren ( $d^2_{row}$ ) en kolomfactoren ( $d^2_{col}$ ).
- Het algoritme schat de afstand tussen rij $i$ en $i'$ door het gemiddelde van de gekwadrateerde verschillen van hun geobserveerde invoer over gemeenschappelijke kolommen te nemen, gecorrigeerd voor variantie van de ruis ( $2\sigma^2$ ).
- Op vergelijkbare wijze worden kolomafstanden geschat met behulp van gemeenschappelijke rijen.
- Formeel is de geschatte rijafstand:
  $\hat{d}^2_{row}(i, i') = \frac{\sum_{j} (X_{i,j} - X_{i',j})^2 A_{i,j}A_{i',j}}{\sum_{j} A_{i,j}A_{i',j}} - 2\sigma^2$
  (Een symmetrische formule geldt voor kolommen).
Buurtconstructie: Met behulp van afstemmingsparameters $\eta_{row}$ en $\eta_{col}$ definieert het algoritme buurten:
- $N_{row}(i) = \{i' : \hat{d}^2_{row}(i, i') \leq \eta^2_{row}\}$
- $N_{col}(j) = \{j' : \hat{d}^2_{col}(j, j') \leq \eta^2_{col}\}$
Schatting: De schatting $\hat{\theta}_{i,j}$ is het gemiddelde van alle geobserveerde invoer $X_{i',j'}$ waar $i' \in N_{row}(i)$ en $j' \in N_{col}(j)$ .

Belangrijkste Bijdragen en Theoretische Resultaten

1. Adaptiviteit aan Gladheid en Minimax Optimaliteit

De primaire theoretische bevinding is dat TS-NN adapteert aan de gladheid $\lambda$ van de latente functie $f$ .

MCAR Regime: Onder standaard MCAR-aannames bewijzen de auteurs dat met passende afstemming ( $\eta \propto (mn)^{-\frac{\lambda}{2\lambda + d_1 + d_2}}$ ), de Mean Squared Error (MSE) de niet-parametrische minimax optimale snelheid bereikt:
$\text{MSE} = O\left( (mn)^{-\frac{2\lambda}{2\lambda + d_1 + d_2}} \right)$
Deze snelheid komt overeen met die van een "oracle" algoritme dat toegang heeft tot de ware latente factoren $U$ en $V$ .
MNAR Regime: Het artikel stelt vast dat deze optimaliteit ook geldt onder MNAR-condities, mits aan een regulariteitsvoorwaarde (Aanname 6) wordt voldaan. Deze voorwaarde vereist in essentie dat het aantal geobserveerde invoer in de intersectie van rij- en kolombuurten voldoende groot is ten opzichte van het product van de buurtgroottes, zelfs als sommige invoer deterministisch ontbreken.

2. Robuustheid tegen Deterministisch Ontbreken

Een belangrijke bijdrage is de demonstratie dat TS-NN niet-triviale foutenmarges oplevert, zelfs wanneer een aanzienlijk deel van de matrix deterministisch ontbreekt (bijv. 50% van de invoer ontbreekt voor specifieke gebruiker-item paren). Theoretische grenzen tonen aan dat zolang de "effectieve" ontbrekende waarschijnlijkheid binnen de buurten begrensd blijft boven nul, de minimax-snelheid behouden blijft.

3. Puntuele Garanties en Asymptotische Normaliteit

Puntuele Grenzen: Het artikel biedt niet-asymptotische puntuele foutgrenzen voor individuele invoer $\hat{\theta}_{i,j}$ . Deze grenzen vertonen een "vloek van dimensionaliteit" met betrekking tot de afstemmingsparameters en de matrixdimensies, die verdwijnt wanneer ze worden gemiddeld naar het populatieniveau (MSE).
Asymptotische Normaliteit: Onder specifieke voorwaarden op de buurtgrootte bewijzen de auteurs dat de puntuele schatter asymptotisch normaal is:
$\sqrt{|N_{row,col}(i,j)|} (\hat{\theta}_{i,j} - \theta_{i,j}) \xrightarrow{d} \mathcal{N}(0, \sigma^2)$
Dit resultaat maakt de constructie van geldige betrouwbaarheidsintervallen voor counterfactual schattingen mogelijk.

Empirische Resultaten

De auteurs valideren hun theoretische bevindingen via:

Synthetische Simulaties:
- Experimenten vergelijken TS-NN met baselines inclusief Row-NN, Column-NN, Doubly-Robust NN (DR-NN), Universal Singular Value Thresholding (USVT) en SoftImpute.
- Resultaten: TS-NN bereikt consistent de beste MSE-decay rates, waarbij het de Oracle-TS-NN (die de latente factoren kent) evenaart in MCAR-settings. Cruciaal is dat TS-NN robuuste prestaties behoudt in MNAR-settings waar andere methoden (zoals DR-NN) aanzienlijk verslechteren.
- Gladheid Adaptiviteit: De empirische decay rates van TS-NN komen overeen met de theoretische voorspellingen naarmate de gladheidsparameter $\lambda$ varieert.
- Betrouwbaarheidsintervallen: De geconstrueerde betrouwbaarheidsintervallen bereiken een bijna nominale dekking (95%) voor gematigde steekproefgroottes, wat de resultaten van de asymptotische normaliteit valideert.
Real-World Case Study (HeartSteps):
- De methode wordt toegepast op de HeartSteps mobiele gezondheidsdataset, een micro-gerandomiseerde trial met 37 gebruikers en beslispunten over 6 weken.
- De dataset vertoont MNAR-kenmerken (gebruikers zijn ongeveer 20% van de tijd niet beschikbaar, en meldingen worden alleen verzonden als zij wel beschikbaar zijn).
- Resultaten: In een 5-voudige cross-validatie setting presteert TS-NN beter dan eenzijdige NN-varianten (Row-NN, Col-NN) en baselines zoals "All-Row-NN" bij het schatten van counterfactual stappenaantallen, wat de praktische bruikbaarheid van de tweezijdige aanpak bij het afhandelen van deterministisch ontbreken aantoont.

Betekenis en Claims

Het artikel claimt twee verschillende onderzoeksgebieden te verenigen: niet-parametrische matrix completion en MNAR ontbrekende data analyse.

Eerste van zijn soort Analyse: De auteurs stellen dat dit de eerste theoretische analyse is van een methode die tegelijkertijd onbekende rij- en kolomlatente factoren, een niet-lineaire Hölder-continue functie (met $\lambda < 1$ ) en MNAR ontbrekende data behandelt.
Oracle Equivalentie: Het werk toont aan dat het gebrek aan kennis over latente factoren de convergentiesnelheid niet benadeelt; TS-NN presteert even goed als een oracle met volledige kennis van $U$ en $V$ in het tussenliggende regime.
Robuustheid: De methodologie blijkt robuust tegen deterministische patronen van ontbrekende data, een kenmerk dat vaak genegeerd wordt in de standaard matrix completion literatuur maar cruciaal is voor real-world toepassingen zoals aanbevelingssystemen.

De auteurs concluderen dat TS-NN een theoretisch onderbouwde, adaptieve en robuuste oplossing biedt voor matrix completion in complexe, niet-gladde en niet-willekeurig ontbrekende omgevingen.