Bound to the log-sum-exp function

There is a relatively simple way to bound the log-sum-exp by a quadratic function. An upper bound was known for the binary case since 1996. It was due to Jordan and Jaakkola in the context of variational inference for logistic regression. The bound is:

for all

where

The extension to the multinomial case was first presented at NIPS 2007 conference in the Workshop on approximate inference in hybrid models. It is a very natural generalization of the previous formula:

for all and

Matlab code available here. A example of output from this script is:

References

• T. Jaakkola and M. Jordan (1996). A variational approach to Bayesian logistic regression problems and their extensions. In Proceedings of the sixth international workshop on artificial intelligence and statistics.

• G. Bouchard. Efficient bounds for the softmax and applications to approximate inference in hybrid models (2007). In NIPS 2007 Workshop on Approximate Inference in Hybrid Models, Whistler, Canada, December 7-8, 2007. [ bib]