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


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: