The families of $f$-divergences (e.g. the Kullback-Leibler divergence) and Integral Probability Metrics (e.g. total variation distance or maximum mean discrepancies) are widely used to quantify the similarity between probability distributions. In this work, we systematically study the relationship between these two families from the perspective of convex duality. Starting from a tight variational representation of the $f$-divergence, we derive a generalization of the moment-generating function, which we show exactly characterizes the best lower bound of the $f$-divergence as a function of a given IPM. Using this characterization, we obtain new bounds while also recovering in a unified manner well-known results, such as Hoeffding's lemma, Pinsker's inequality and its extension to subgaussian functions, and the Hammersley-Chapman-Robbins bound. This characterization also allows us to prove new results on topological properties of the divergence which may be of independent interest.

The families of f-divergences (e.g. the Kullback-Leibler divergence) and Integral Probability Metrics (e.g. total variation distance or maximum mean discrepancies) are commonly used in optimization and estimation. In this work, we systematically study the relationship between these two families from the perspective of convex duality. Starting from a tight variational representation of the f-divergence, we derive a generalization of the moment generating function, which we show exactly characterizes the best lower bound of the f-divergence as a function of a given IPM. Using this characterization, we obtain new bounds on IPMs defined by classes of unbounded functions, while also recovering in a unified manner well-known results for bounded and subgaussian functions (e.g. Pinsker’s inequality and Hoeffding’s lemma).

We show that the moment generating function of the Kullback-Leibler divergence (relative entropy) between the empirical distribution of n independent samples from a distribution P over a finite alphabet of size k (i.e. a multinomial distribution) and P itself is no more than that of a gamma distribution with shape k - 1 and rate n. The resulting exponential concentration inequality becomes meaningful (less than 1) when the divergence ε is larger than (k - 1)/n, whereas the standard method of types bound requires ε > 1/n · log (k-1n+k-1) ≥ (k - 1)/n · log (1 + n/(k-1)), thus saving a factor of order log (n/k) in the standard regime of parameters where n ≫ k. As a consequence, we also obtain finite-sample bounds on all the moments of the empirical divergence (equivalently, the discrete likelihood-ratio statistic), which are within constant factors (depending on the moment) of their asymptotic values. Our proof proceeds via a simple reduction to the case k = 2 of a binary alphabet (i.e. a binomial distribution), and has the property that improvements in the case of k = 2 directly translate to improvements for general k. In particular, we conjecture a bound on the binomial moment generating function that would almost close the quadratic gap between our finite-sample bound and the asymptotic moment generating function bound from Wilks' theorem (which does not hold for finite samples).

Blasiok (SODA'18) recently introduced the notion of a subgaussian sampler, defined as an averaging sampler for approximating the mean of functions $f:\{0,1\}^m \to \mathbb{R}$ such that $f(U_m)$ has subgaussian tails, and asked for explicit constructions. In this work, we give the first explicit constructions of subgaussian samplers (and in fact averaging samplers for the broader class of subexponential functions) that match the best-known constructions of averaging samplers for $[0,1]$-bounded functions in the regime of parameters where the approximation error $\varepsilon$ and failure probability $δ$ are subconstant. Our constructions are established via an extension of the standard notion of randomness extractor (Nisan and Zuckerman, JCSS'96) where the error is measured by an arbitrary divergence rather than total variation distance, and a generalization of Zuckerman's equivalence (Random Struct. Alg.'97) between extractors and samplers. We believe that the framework we develop, and specifically the notion of an extractor for the Kullback-Leibler (KL) divergence, are of independent interest. In particular, KL-extractors are stronger than both standard extractors and subgaussian samplers, but we show that they exist with essentially the same parameters (constructively and non-constructively) as standard extractors.