Optimal Bounds between f-Divergences and Integral Probability Metrics

Rohit Agrawal, Thibaut Horel
Proceedings of the 37th International Conference on Machine Learning, PMLR 119:115-124, 2020.

Abstract

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).

Cite this Paper

BibTeX
@InProceedings{pmlr-v119-agrawal20a, title = {Optimal Bounds between f-Divergences and Integral Probability Metrics}, author = {Agrawal, Rohit and Horel, Thibaut}, booktitle = {Proceedings of the 37th International Conference on Machine Learning}, pages = {115--124}, year = {2020}, editor = {III, Hal Daumé and Singh, Aarti}, volume = {119}, series = {Proceedings of Machine Learning Research}, month = {13--18 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v119/agrawal20a/agrawal20a.pdf}, url = {https://proceedings.mlr.press/v119/agrawal20a.html}, abstract = {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).} }
Endnote
%0 Conference Paper %T Optimal Bounds between f-Divergences and Integral Probability Metrics %A Rohit Agrawal %A Thibaut Horel %B Proceedings of the 37th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2020 %E Hal Daumé III %E Aarti Singh %F pmlr-v119-agrawal20a %I PMLR %P 115--124 %U https://proceedings.mlr.press/v119/agrawal20a.html %V 119 %X 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).
APA
Agrawal, R. & Horel, T.. (2020). Optimal Bounds between f-Divergences and Integral Probability Metrics. Proceedings of the 37th International Conference on Machine Learning, in Proceedings of Machine Learning Research 119:115-124 Available from https://proceedings.mlr.press/v119/agrawal20a.html.

Related Material