En populär metod för att hantera storskaliga datamängder är provtagning. Till exempel genom att använda den empiriska statistiska hävstångspoängen som en viktig provtagningsfördelning, metoden för algoritmisk hävstångsprov och skala om rader/kolumner av datamatriser för att minska datastorleken innan beräkningar utförs på delproblemet. Denna metod har varit framgångsrik i att förbättra beräkningseffektiviteten av algoritmer för matrisproblem såsom minsta-kvarts approximation, minst absoluta avvikelser approximation, och låg-rank matris approximation. Befintligt arbete har fokuserat på algoritmiska frågor som värsta tänkbara drifttider och numeriska frågor i samband med att tillhandahålla högkvalitativa implementeringar, men inget av det tar upp statistiska aspekter av denna metod. I detta dokument ger vi en enkel men effektiv ram för att utvärdera de statistiska egenskaperna hos algoritmisk hävstång i samband med uppskattning av parametrar i en linjär regressionsmodell med ett fast antal prediktorer. I synnerhet för flera versioner av hävstångsbaserad provtagning, härleder vi resultat för bias och varians, både villkorligt och villkorslöst på de observerade data. Vi visar att ur ett statistiskt perspektiv av partiskhet och varians dominerar varken hävstångsbaserad provtagning eller enhetlig provtagning den andra. Detta resultat är särskilt slående, med tanke på det välkända resultatet att, ur algoritmiskt perspektiv av värsta fall analys, hävstångsbaserad provtagning ger enhetligt överlägsen värsta fall algoritmiska resultat, jämfört med enhetlig provtagning. Baserat på dessa teoretiska resultat föreslår och analyserar vi två nya mobiliseringsalgoritmer: den ena konstruerar ett mindre minsta-kvarts problem med "krympta" hävstångspoäng (SLEV), och den andra löser ett mindre och oviktat (eller partisk) minst-kvarts problem (LEVUNW). En detaljerad empirisk utvärdering av befintliga hävstångsbaserade metoder samt dessa två nya metoder görs på både syntetiska och verkliga datamängder. De empiriska resultaten visar att vår teori är en bra prediktor för praktisk prestanda hos befintliga och nya hävstångsbaserade algoritmer och att de nya algoritmerna uppnår bättre prestanda. Till exempel, med samma beräkningsminskning som i den ursprungliga algoritmiska hävstångseffekten, leder vår föreslagna SLEV vanligtvis till förbättrade fördomar och avvikelser både villkorslöst och villkorligt (på de observerade data), och vår föreslagna LEVUNW ger vanligtvis förbättrade villkorslösa fördomar och varianser.
Två provtagningsstrategier (uniform provtagning och hävstångsprovtagning) övervägdes och analyserades i REF och det visade sig att ingen av dem dominerar den andra när det gäller statistikfrekvensen.
A Statistical Perspective on Algorithmic Leveraging
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}