Koncentracijske nejednakosti i primjene

diplomski rad

• Naslov (engleski): Concentration inequalities and applications
• Autor: Marko Jukić
• Mentor: Bojan Basrak (mentor)
• Član povjerenstva: Bojan Basrak (predsjednik povjerenstva)
• Član povjerenstva: Damir Bakić (član povjerenstva)
• Član povjerenstva: Juraj Šiftar (član povjerenstva)
• Član povjerenstva: Dijana Ilišević (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Prirodoslovno-matematički fakultet; (Matematički odsjek); Zagreb
• Datum i država obrane: 2021-12-01, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

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.

Sažetak (engleski)

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.

• Ključne riječi: Centralni granični teorem; neasimptotske koncentracijske nejednakosti; Chernoffljeva metoda; Hoeffdingova nejednakost; Bernsteinova nejednakost; Rademacherova usrednjenja; Dudleyeva nejednakost
• Ključne riječi (engleski): Central boundary theorem; non-asymptotic concentration inequalities; Chernoffle method; Hoeffding inequality; Bernstein's inequality; Rademacher averaging; Dudley's inequality
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:709527
• Studijski program: Naziv: Matematička statistika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra matematike (mag. math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2021-12-14 13:54:24