Improvements to Sanov and PAC Sublevel-set Bounds for Discrete Random Variables

Simple item page
dc.contributor.authorTope, Michael A.
dc.contributor.authorMorris, Joel M.
dc.date.accessioned2021-05-25T18:48:24Z
dc.date.available2021-05-25T18:48:24Z
dc.date.issued2021-04-19
dc.description2021 55th Annual Conference on Information Sciences and Systems (CISS)en_US
dc.description.abstractWe derive an improvement for probably approximately correct (PAC) sublevel-set bounds for the multinomial distributed discrete random variables. Previous bounds (including Sanov's Theorem) show that the Kullback Leibler (KL) divergence between the empirical probability mass function (pmf) and the true PMF converges with rate O(log(N)/N), where N is the number of independent and identically distributed (i.i.d.) samples used to compute the empirical pmf. We interpret the KL divergence as bounding the probability that a multinomial distributed random variable (RV) deviates into a halfspace and construct improved uniform PAC sublevel-set bounds that converge with rates O (log (log (N)) / N). These results bound the worst case performance for a number of machine learning algorithms. Finally, the ‘halfspace bound’ methodology suggests further improvements are possible for non-uniform bounds. In this paper, we derive an improvement (on the convergence rate) for various Probably Approximately Correct (PAC) bounds (including Sanov's Theorem) for multinomially distributed discrete random variables.en_US
dc.description.urihttps://ieeexplore.ieee.org/document/9400225en_US
dc.format.extent6 pagesen_US
dc.genreconference papers and proceedings preprintsen_US
dc.identifierdoi:10.13016/m2abay-5ech
dc.identifier.citationTope, Michael A.; Morris, Joel M.; Improvements to Sanov and PAC Sublevel-set Bounds for Discrete Random Variables; 2021 55th Annual Conference on Information Sciences and Systems (CISS); https://ieeexplore.ieee.org/document/9400225en_US
dc.identifier.urihttps://doi.org/10.1109/CISS50987.2021.9400225
dc.identifier.urihttp://hdl.handle.net/11603/21617
dc.language.isoen_USen_US
dc.publisherIEEEen_US
dc.relation.isAvailableAtThe University of Maryland, Baltimore County (UMBC)
dc.relation.ispartofUMBC Computer Science and Electrical Engineering Department Collection
dc.relation.ispartofUMBC Faculty Collection
dc.relation.ispartofUMBC Student Collection
dc.rightsThis item is likely protected under Title 17 of the U.S. Copyright Law. Unless on a Creative Commons license, for uses protected by Copyright Law, contact the copyright holder or the author.
dc.rights© 2021 IEEE.  Personal use of this material is permitted.  Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
dc.titleImprovements to Sanov and PAC Sublevel-set Bounds for Discrete Random Variablesen_US
dc.typeTexten_US

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
20210206_tope_morris_ciss_2021_pac_paper_2029_final_v4_001 (1).pdf
Size:
1.58 MB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
2.56 KB
Format:
Item-specific license agreed upon to submission
Description:
Download

Collections

UMBC Computer Science and Electrical Engineering Department
UMBC Faculty Collection
UMBC Student Collection