Vi presenterar en ny uppfattning om komplexitet som interpolerar mellan och generaliserar några klassiska befintliga komplexitetsbegrepp i inlärningsteori: för estimatorer som empirisk riskminimering (ERM) med godtyckliga begränsade förluster, är den övre begränsad i termer av data-oberoende Rademacher komplexitet; för generaliserade Bayesian estimatorer, är den övre avgränsad av databeroende informationskomplex (även känd som stokastisk eller PAC-Bayerian, KL (oberior tidigare) komplexitet. För (påverkad) ERM minskar den nya komplexiteten till (generaliserad) normaliserad maximal sannolikhet (NML) komplexitet, dvs. En minimal log-loss individuella sekvens ånger. Vårt första huvudresultat begränsar risken i form av den nya komplexiteten. Vårt andra huvudsakliga resultat kopplar den nya komplexiteten via Rademacher komplexitet till L 2 (P ) entropi, vilket generaliserar tidigare resultat av Opper, Haussler, Lugosi och Cesa-Bianchi som gjorde log-loss fallet med L ∞. Tillsammans återvinner dessa resultat optimala gränser för VC- och stora (polynomisk entropi) klasser, som ersätter lokal Rademacher komplexitet med en enklare analys som nästan helt separerar de två aspekter som bestämmer de uppnåeliga nivåerna: "easiness" (Bernstein) villkor och modell komplexitet.
Grünwald och Mehta Ref fastställer nya överriskgränser i form av en ny komplexitetsåtgärd baserad på "lyckliga" funktioner.
A Tight Excess Risk Bound via a Unified PAC-Bayesian-Rademacher-Shtarkov-MDL Complexity
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}