Efficient Learning in Graphs and in Combinatorial Multi-Armed Bandits

QC 20241107

Abstract

Grafer har rika strukturer både på lokal och global skala. Genom att utnyttja strukturella egenskaper i vissa grafproblem är det möjligt att designa beräkningsmässigt effektiva algoritmer eller förfina prestandaanalysen. Denna avhandling är uppdelad i två delar: (i) att designa nya metoder för att upptäcka struktur från grafer och (ii) att studera samspelet mellan grafer och kombinatoriska multi-armbanditer. De skiljer sig .t i hur strukturer definieras, upptäcks och utnyttjas.

I del (i) börjar vi med ett grafgruvningsproblem på signerade nätverk [TOG20], där de grafmönster vi siktar på att upptäcka är grupper med mestadels positiva intra-gruppkanter och mestadels negativa inter-gruppkanter. Vi utformar vårt mål så att, givet en lösning, det återspeglar hur väl den lösningen matchar det önskade mönstret. Vår föreslagna algoritm ger inga antaganden om grafen. Den visar konkurrenskraftig empirisk prestanda i verkliga grafer och syntetiska grafer. Prestandautvärderingen genomförs genom en värsta fall-analys, som approximativt finner den optimala lösningen. Dessutom utvidgar vi vår konfliktgruppsdetektion [BGG+19, TOG20] samt andra grafgruvningsuppgifter (såsom rättvis tätaste subgrafdetektion [ABF+20], två-samhällesdetektion [New06]) till en minnesbegränsad och passbegränsad inställning. Under en sådan inställning är Randomized SVD, som föreslagits av [HMT11], den mest föredragna metoden i en minnesbegränsad och passbegränsad inställning. Men för en ingångsmatris av storlek n × n har den ingen garanti i o(ln n)-passregimen, vilket är av största intresse för praktiker. Vi härleder därför en stramare analys [TWA+22] för Randomized SVD för positivt semi-definita matriser i vilket antal pass som helst och för indefinita matriser under vissa villkor. Vidare initierar vi studien av en blandning av Johnson-Lindenstrauss distribution och 0/1 Bernoulli-distributionen. Vi visar att denna blandning hjälper till att göra detektionen av 2-konfliktgrupper [BGG+19] mer effektiv.

I del (ii) studerar vi kombinatoriska multi-arm banditproblem, där grafer- nas egenskaper spelar viktiga roller men är något dolda i optimeringsproblemet. I stället härleder man de fundamentala gränserna för antingen den förväntade provtagningskomplexiteten eller den förväntade kumulativa ånger, vanligtvis i informations-teoretisk mening, och utforskar sedan de abstrakta egenskaperna associerade med dessa gränser för att lösa problemet på ett tillfredsställande sätt, antingen statistiskt eller beräkningsmässigt. Vi fokuserar på kombinatoriska semi-banditer där läraren observerar individuella återkopplingar för varje arm som är en del av urvalet. Denna formulering modellerar många verkliga problem, inklusive online ranking [ DKC21 ] i rekommendationssystem, nätverksrouting [ CLK+14] hos internetleverantörer, lånefördelning [ KWA+14 ], vägplanering [JMKK21 ], och influencer-marknadsföring [ Per22 ]. För bästa armidentifiering med fast förtroende föreslår vi den första polynomtidalgoritmen vars provtagningskomplexitet är instansspecifikt optimal i hög förtroenderegim och har polynomberoende på antalet armar i måttlig förtroenderegim. För ångerminimering föreslår vi den första algoritmen vars per-rundans tidskomplexitet är sublinjär i antalet armar samtidigt som den matchar den instansspecifikt gapberoende nedre gränsen asymptotiskt.

urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-355999