Vorlesung Konzentrationsungleichungen (Concentration Inequalities)

Nummer: Vorlesung 011396 (SS17), Übung 011397 (SS17), Modulbeschreibung im Modulhandbuch

CI_banner.jpg

Aktuelles

  • Aufgabe 26 auf Blatt 13 war schlecht gestellt und wurde entfernt (20.07.2017)
  • Blatt 13 ist online (12.07.2017)
  • Blatt 12 ist online (29.06.2017)
  • Blatt 10 und 11 sind online (20.06.2017)
  • Blatt 9 ist online (12.06.2017)
  • Lösungsskizzen zu den Blättern 6 und 7 sind online (06.06.2017)
  • Die Übung am 30.05.2017 entfällt und wird am 06.06.2017 ab 8:30 Uhr nachgeholt.
  • Blatt 7 und 8 sind online (24.05.2017)
  • Notation in Aufgabe 12a) auf Blatt 6 minimal geändert (22.05.2017)
  • Blatt 6 ist online (16.05.2017)
  • Blatt 5 ist online (09.05.2017)
  • Die Definition von gammaverteilten Zufallsvariablen und Aufgabe 8 auf Blatt 4 wurden präzisiert (09.05.2017)
  • Blatt 4 ist online (03.05.2017)
  • Blatt 3 ist online (25.04.2017)
  • Blatt 1 und 2 sind online (19.04.2017)

Übungen

Voraussetzung zur Zulassung zur Prüfung ist das erfolgreiche Bearbeiten der Übungsaufgaben. Dazu müssen in jedem Semester mindestens 50% der Punkte erreicht werden.

Organisatorisches

Die Veranstaltung umfasst 2 Wochenstunden Vorlesung und eine Wochenstunde Übung (2 V + 1 Ü) und ist der erste Teil einer zweiteiligen Veranstaltung. Teil II wird im Wintersemester 2017/2018 angeboten; beide Veranstaltungen zusammen bilden ein Modul mit 9 Leistungspunkten (4 V + 2 Ü).

  • Vorlesung: Prof. Dr. Ivan Veselic, Raum 611, Di 10-12
  • Übung: Matthias Täufer, Raum 611, Di 9:15-10:00.

Vorkenntnisse:

Voraussetzungen sind die Vorlesungen Analysis I, II, Lineare Algebra I, II und Stochastik I.

Kenntnisse aus der Vorlesung Analysis III, Stochastik II sind nützlich, aber nicht notwendig.

Mehrfachintegrale und bedingte Erwartungen werden zu Beginn der Vorlesung eingeführt, bzw. wiederholt.

Inhalte

Ausgangspunkt der Vorlesung ist das Gesetz der großen Zahlen: Bei unabhängiger, gleichartiger Wiederholung von Experimenten konvergiert die Folge der empirischen Mittel gegen den Erwartungswert der einzelnen Zufallsgrößen. Man interessiert sich nun für die Geschwindigkeit der Konvergenz und für explizite Abschätzungen an den Approximationsfehler bei einer endlichen Anzahl von Experimenten. Die einfachste Abschätzung liefert die Markov—Chebyshev Ungleichung, die unter anderem für den Beweis des schwachen Gesetzes der großen Zahlen verwendet wird. Präzisere quantitative Aussagen sind mit Hilfe der klassischen Konzentrationsungleichungen von Chernov, Bernstein, Bennet, Efron—Stein, Harris, Hoeffding, McDiarmid, Dvoretzki—Kiefer—Wolfowitz, usw. möglich. Dagegen liefert die die Theorie der Großen Abweichungen (large deviations principles) scharfe asymptotische Abschätzungen. Dies führt in natürlicher Weise auf die Konzepte der Legendre-Transformation, der Entropie, der Sobolev-Ungleichungen und der Vapnik—Chervonenkis Klassen. Anwendungsbeispiele, etwa aus der Kombinatorik, der Lerntheorie, der Statistik, der Analysis und der Perkolationstheorie runden die Vorlesung ab.

Literatur:

Concentration Inequalities: A Nonasymptotic Theory of Independence
Stephane Boucheron, Gabor Lugosi, Pascal Massart (Oxford)