Adaptivitet är ett viktigt inslag i dataanalys-typiskt valet av frågor om en datauppsättning beror på tidigare interaktioner med samma datauppsättning. Generaliseringsfel är dock vanligtvis begränsat till en icke-adaptiv modell, där alla frågor specificeras innan datauppsättningen dras. Nyligen utfört arbete av Dwork et al. (STOC '15) och Hardt och Ullman (FOCS '14) inledde den formella undersökningen av detta problem och gav de första övre och nedre gränserna för det uppnåeliga generaliseringsfelet för adaptiv dataanalys. Specifikt, anta att det finns en okänd distribution P och en uppsättning av n oberoende prover x dras från P. Vi söker en algoritm som, givet x som ingång, " korrekt" svarar en sekvens av adaptivt valda " krav" om den okända distributionen P. Hur många prover n måste vi dra från distributionen, som en funktion av typen av frågor, antalet frågor, och önskad nivå av noggrannhet? I detta arbete lämnar vi två nya bidrag för att lösa denna fråga: 1. Vi ger övre gränser för antalet prover n som behövs för att besvara statistiska frågor som förbättrar över gränserna för Dwork et al. 2. Utgångspunkten är följande: Vi bevisar de första övre gränserna på antalet prover som krävs för att besvara mer allmänna familjer av frågor. Dessa inkluderar godtyckliga frågor med låg känslighet och den viktiga klassen av konvexa riskminimeringsfrågor. Som i Dwork et al. är våra algoritmer baserade på en koppling mellan differentialintegritet och generaliseringsfel, men vi känner att vår analys är enklare och mer modulär, vilket kan vara användbart för att studera dessa frågor i framtiden.
Slutligen, i ett uppföljande arbete nyligen, Bassily et al. ge en alternativ metod för att använda en differentialt privat algoritm för att svara på statistiska och mer allmänna typer av frågor REF.
More General Queries and Less Generalization Error in Adaptive Data Analysis
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}