I det senaste arbetet, Kalai, Klivans, Mansour, och Servedio (2005) studerade en variant av "Low-Degree (Fourier) Algoritm" för lärande under den enhetliga sannolikhetsfördelning på {0, 1} n. De visade att L 1 polynomial regressionsalgoritmen ger agnostic (tolerant till godtyckligt buller) lärande algoritmer med avseende på klassen av tröskelfunktioner-under vissa begränsade instansfördelningar, inklusive uniform på {0, 1} n och Gaussian på R n. I detta arbete visar vi hur alla lärande resultat baserade på låg-Degree Algorithm kan generaliseras för att ge nästan identiska agnostiska garantier under godtyckliga produktdistributioner på instans utrymmen X 1 × · · · × X n. Vi utvidgar också dessa resultat till lärande under blandningar av produktdistributioner. Den viktigaste tekniska innovationen är användningen av (Hoeffding) ortogonal nedbrytning och utvidgningen av "bullerkänslighetsmetoden" till godtyckliga produktutrymmen. I synnerhet ger vi ett mycket enkelt bevis på att tröskelfunktioner över godtyckliga produktutrymmen har δ-buller känslighet O ( ε δ), lösa ett öppet problem som föreslås av Peres (2004).
REF utvidgade dessa resultat från enhetliga distributioner till produktdistributioner.
Polynomial regression under arbitrary product distributions
{'venue': 'Machine Learning', 'journal': 'Machine Learning', 'mag_field_of_study': ['Mathematics', 'Computer Science']}