Vi studerar det grundläggande problemet med högdimensionell medeluppskattning i en robust modell där en konstant bråkdel av proverna är motsträvigt korrumperade. Det senaste arbetet gav de första polynom tid algoritmer för detta problem med dimensionsoberoende fel garantier för flera familjer av strukturerade distributioner. I detta arbete ger vi de första nästan linjära tidsalgoritmerna för högdimensionell robust medeluppskattning. Speciellt fokuserar vi på distributioner med (i) känd kovarians och sub-gaussiska svansar, och (ii) okänd avgränsad kovarians. Med tanke på N prover på R d, en brott av vilka kan godtyckligt korrumperas, våra algoritmer köras i tiden O(N d)/poly( ska) och ungefär det sanna medelvärdet inom information-teoretiskt optimal fel, upp till konstanta faktorer. Tidigare robusta algoritmer med jämförbara felgarantier har gångtider..(N d 2 ), för.. =..(1). Våra algoritmer förlitar sig på en naturlig familj av SDPs parameteriseras av vår nuvarande gissning v för det okända medelvärdet μ. Vi ger en win-win analys etablera följande: antingen en näraoptimal lösning till den primära SDP ger en bra kandidat för μ / -oberoende av vår nuvarande gissning v -eller en nära-optimal lösning till den dubbla SDP ger en ny gissning v ′ vars avstånd från μ / är mindre med en konstant faktor. Vi utnyttjar den speciella strukturen hos motsvarande SDP för att visa att de är ungefär solvable i nästan linjär tid. Vårt tillvägagångssätt är ganska allmänt, och vi tror att det också kan tillämpas för att få nästan linjära tidsalgoritmer för andra högdimensionella robusta inlärningsproblem.
En robust genomsnittlig estimator föreslås i REF som fungerar i R d och förlitar sig på ett semidefinit program för att dämpa effekten av de avvikelser som planterats av en motståndare.
High-Dimensional Robust Mean Estimation in Nearly-Linear Time
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}