On change of measure inequalities for $f$-divergences

• URL: http://arxiv.org/abs/2202.05568v1
• Date: Fri, 11 Feb 2022 11:53:28 GMT
• Title: On change of measure inequalities for $f$-divergences
• Authors: Antoine Picard-Weibel and Benjamin Guedj
• Abstract summary: Strategy relies on combining the Legendre transform of $f$-divergences and the Young-Fenchel inequality. We derive new PAC-Bayesian generalisation bounds with a complexity involving $f$-divergences. We instantiate our results for the most popular $f$-divergences.
• Score: 5.799808780731661
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: We propose new change of measure inequalities based on $f$-divergences (of which the Kullback-Leibler divergence is a particular case). Our strategy relies on combining the Legendre transform of $f$-divergences and the Young-Fenchel inequality. By exploiting these new change of measure inequalities, we derive new PAC-Bayesian generalisation bounds with a complexity involving $f$-divergences, and holding in mostly unchartered settings (such as heavy-tailed losses). We instantiate our results for the most popular $f$-divergences.

Related papers

• Variance-Dependent Regret Bounds for Non-stationary Linear Bandits [52.872628573907434]
  We propose algorithms that utilize the variance of the reward distribution as well as the $B_K$, and show that they can achieve tighter regret upper bounds. We introduce two novel algorithms: Restarted Weighted$textOFUL+$ and Restarted $textSAVE+$. Notably, when the total variance $V_K$ is much smaller than $K$, our algorithms outperform previous state-of-the-art results on non-stationary linear bandits under different settings.
  arXiv  Detail & Related papers  (2024-03-15T23:36:55Z)
• Quantum Rényi and $f$-divergences from integral representations [11.74020933567308]
  Smooth Csisz'ar $f$-divergences can be expressed as integrals over so-called hockey stick divergences. We find that the R'enyi divergences defined via our new quantum $f$-divergences are not additive in general. We derive various inequalities, including new reverse Pinsker inequalities with applications in differential privacy.
  arXiv  Detail & Related papers  (2023-06-21T15:39:38Z)
• Statistical Learning under Heterogeneous Distribution Shift [71.8393170225794]
  Ground-truth predictor is additive $mathbbE[mathbfz mid mathbfx,mathbfy] = f_star(mathbfx) +g_star(mathbfy)$.
  arXiv  Detail & Related papers  (2023-02-27T16:34:21Z)
• A Primal-Dual Approach to Solving Variational Inequalities with General Constraints [54.62996442406718]
  Yang et al. (2023) recently showed how to use first-order gradient methods to solve general variational inequalities. We prove the convergence of this method and show that the gap function of the last iterate of the method decreases at a rate of $O(frac1sqrtK)$ when the operator is $L$-Lipschitz and monotone.
  arXiv  Detail & Related papers  (2022-10-27T17:59:09Z)
• Benefits of Permutation-Equivariance in Auction Mechanisms [90.42990121652956]
  An auction mechanism that maximizes the auctioneer's revenue while minimizes bidders' ex-post regret is an important yet intricate problem in economics. Remarkable progress has been achieved through learning the optimal auction mechanism by neural networks.
  arXiv  Detail & Related papers  (2022-10-11T16:13:25Z)
• Function-space regularized R\'enyi divergences [6.221019624345409]
  We propose a new family of regularized R'enyi divergences parametrized by a variational function space. We prove several properties of these new divergences, showing that they interpolate between the classical R'enyi divergences and IPMs. We show that the proposed regularized R'enyi divergences inherit features from IPMs such as the ability to compare distributions that are not absolutely continuous.
  arXiv  Detail & Related papers  (2022-10-10T19:18:04Z)
• Split-kl and PAC-Bayes-split-kl Inequalities [15.63537071742102]
  We name a split-kl inequality, which combines the power of the kl inequality with the ability to exploit low variance. For Bernoulli random variables the kl inequality is tighter than the Empirical Bernstein, for random variables taking values inside a bounded interval the Empirical Bernstein inequality is tighter than the kl. We discuss an application of the split-kl inequality to bounding excess losses.
  arXiv  Detail & Related papers  (2022-06-01T18:42:02Z)
• A Unified Framework for Multi-distribution Density Ratio Estimation [101.67420298343512]
  Binary density ratio estimation (DRE) provides the foundation for many state-of-the-art machine learning algorithms. We develop a general framework from the perspective of Bregman minimization divergence. We show that our framework leads to methods that strictly generalize their counterparts in binary DRE.
  arXiv  Detail & Related papers  (2021-12-07T01:23:20Z)
• Linear Contextual Bandits with Adversarial Corruptions [91.38793800392108]
  We study the linear contextual bandit problem in the presence of adversarial corruption. We present a variance-aware algorithm that is adaptive to the level of adversarial contamination $C$.
  arXiv  Detail & Related papers  (2021-10-25T02:53:24Z)
• Moreau-Yosida $f$-divergences [0.0]
  Variational representations of $f$-divergences are central to many machine learning algorithms. We generalize the so-called tight variational representation of $f$-divergences in the case of probability measures on compact metric spaces. We provide an implementation of the variational formulas for the Kullback-Leibler, reverse Kullback-Leibler, $chi2$, reverse $chi2$, squared Hellinger, Jensen-Shannon, Jeffreys, triangular discrimination and total variation divergences.
  arXiv  Detail & Related papers  (2021-02-26T11:46:10Z)
• Novel Change of Measure Inequalities with Applications to PAC-Bayesian Bounds and Monte Carlo Estimation [29.919144859026016]
  We show how variational representation for $f$-divergences leads to novel change of measure inequalities. We also present a multiplicative change of measure inequality for $alpha$-divergences and a generalized version of Hammersley-Chapman-Robbins inequality.
  arXiv  Detail & Related papers  (2020-02-25T05:36:22Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.