Inferenz, Schätzung und Entscheidungsfindung aus Daten
Bislang ging es in der Statistik vor allem um Mittelwerte und asymptotische Fragen. Konzentrationsungleichungen stellen eine schärfere Frage für endliche Stichproben: Wie wahrscheinlich ist es, dass eine zufällige Größe weit von ihrem Mittelwert abweicht? Ihre Antworten bilden das mathematische Rückgrat dafür, warum maschinelles Lernen überhaupt Garantien geben kann.
Die einfachste, die nur eine nicht-negative Größe und deren Mittelwert benötigt, ist die Markov-Ungleichung:
Sie besagt, dass eine nicht-negative Größe nicht oft ein Vielfaches ihres Mittelwerts annehmen kann. Ist der Mittelwert klein, müssen große Werte selten sein. Grob, aber sie kommt mit fast keinen Voraussetzungen aus.