Koncentracijske nejednakosti i primjene

master's thesis

• Title (english): Concentration inequalities and applications
• Author: Marko Jukić
• Mentor: Bojan Basrak (mentor)
• Committee member: Bojan Basrak (predsjednik povjerenstva)
• Committee member: Damir Bakić (član povjerenstva)
• Committee member: Juraj Šiftar (član povjerenstva)
• Committee member: Dijana Ilišević (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2021-12-01, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

U ovom radu prikazali smo neke metode dokazivanja koncentracijskih nejednakosti i njihove primjene u teoriji statističkog učenja. Najjednostavniji i najviše proučavani primjer su sume nezavisnih slučajnih varijabli. Usporedili smo što o njihovim fluktuacijama govore Centralni granični teorem i neasimptotske koncentracijske nejednakosti. Chernoffljevom metodom pokazali smo Hoeffdingovu i Bernsteinovu nejednakost za sume ograničnih varijabli. Zatim smo definirali subgaussovske i subeskponencijalne varijable te pokazali da za njih također vrijede slične nejednakosti. Općenitiji primjer su generalne funkcije nezavisnih slučajnih varijabli. Koristeći martingalnu metodu pokazali smo Efron-Steinovu i McDiarmidovu nejednakost. Rezultate smo primijenili na funkcije sa svojstvom omeđenih razlika i samoomeđujućim svojstvom, kao što su minimum empirijskog rizika i Rademacherova usrednjenja. Uveli smo osnovne pojmove iz teorije informacija i dokazali subaditivnost \(\Phi\)-entropije, iz koje slijede Logaritamske Sobolevljeve nejednakosti. Zatim smo pokazali kako se iz njih metodom entropije mogu dobiti eksponencijalne koncentracijske nejednakosti. U raznim primjenama važno je razumijevanje fluktuacija supremuma slučajnih procesa, a posebno empirijskih procesa. Metodom ulančavanja pokazali smo Dudleyevu nejednakost, koja daje ogradu na očekivanje supremuma preko metričke entropije. Iz nje smo dobili ogradu na očekivanje supremuma empirijskog procesa preko VC dimenzije familije indeksa. Neke od posljedica tih rezultata su uniformni zakon velikih brojeva za Lipschitzove funkcije i ograda na razliku rizika i empirijskog rizika.

Abstract (english)

In this thesis, we present some methods for proving concentration inequalities and their applications in the theory of statistical learning. The simplest and most studied examples are sums of independent random variables. We compared what the Central Limit Theorem and non-asymptotic concentration inequalities say about their fluctuations. Using Chernoff bounds, we have shown that Hoeffding and Bernstein inequalities hold for sums of bounded variables. We then defined subgaussian and subexponential random variables and showed that similar inequalities hold for such variables. A more general example is that of general functions of independent random variables. Using the martingale method, we showed Efron-Stein and McDiarmid inequality. We applied the results to functions with bounded differences and self-bounding functions, such as the minimum of the empirical loss and Rademacher averages. We have introduced basic concepts from information theory and proved the subadditivity of \(\Phi\)-entropy, from which the Logarithmic Sobolev inequalities follow. Then we showed how exponential concentration inequalities can be obtained from them by the entropy method. In various applications, it is important to understand the fluctuations of the supremum of random processes, especially empirical processes. Using the chaining method we have shown the Dudley inequality, which gives a bound on the expectation of supremum using metric entropy. We used the inequality to show a bound for the expected supremum of an empirical process via VC dimension of the index family. Some of the consequences of these results are a uniform law of large numbers for Lipschitz functions and a bound on the difference between the loss and empirical loss.

• Keywords: Centralni granični teorem; neasimptotske koncentracijske nejednakosti; Chernoffljeva metoda; Hoeffdingova nejednakost; Bernsteinova nejednakost; Rademacherova usrednjenja; Dudleyeva nejednakost
• Keywords (english): Central boundary theorem; non-asymptotic concentration inequalities; Chernoffle method; Hoeffding inequality; Bernstein's inequality; Rademacher averaging; Dudley's inequality
• Language: croatian
• URN:NBN: urn:nbn:hr:217:709527
• Study programme: Title: Mathematical Statistics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra matematike (magistar/magistra matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2021-12-14 13:54:24