Loading...

f-Divergences and Their Applications in Lossy Compression and Bounding Generalization Error

Masiha, S ; Sharif University of Technology | 2023

538 Viewed
  1. Type of Document: Article
  2. DOI: 10.1109/TIT.2023.3268527
  3. Publisher: Institute of Electrical and Electronics Engineers Inc , 2023
  4. Abstract:
  5. In this paper, we provide three applications for f-divergences: (i) we introduce Sanov's upper bound on the tail probability of the sum of independent random variables based on super-modular f-divergence and show that our generalized Sanov's bound strictly improves over ordinary one, (ii) we consider the lossy compression problem which studies the set of achievable rates for a given distortion and code length. We extend the rate-distortion function using mutual f -information and provide new and strictly better bounds on achievable rates in the finite blocklength regime using super-modular f -divergences, and (iii) we provide a connection between the generalization error of algorithms with bounded input/output mutual f -information and a generalized rate-distortion problem. This connection allows us to bound the generalization error of learning algorithms using lower bounds on the f -rate -distortion function. Our bound is based on a new lower bound on the rate-distortion function that (for some examples) strictly improves over previously best-known bounds. © 1963-2012 IEEE
  6. Keywords:
  7. F-divergence ; F-ratedistortion ; Generalization error ; Mutual f-information ; Super-modular f-divergence
  8. Source: IEEE Transactions on Information Theory ; Volume 69, Issue 12 , 2023 , Pages 7538-7564 ; 00189448 (ISSN)
  9. URL: https://ieeexplore.ieee.org/document/10105643