Maximum entropy discrimination is a method for estimating distributions such that they meet classification constraints and perform accurate prediction. These distributions are over parameters of a classifier, for instance, log-linear prediction models or log-likelihood ratios of generative models. Many of the resulting optimization problems are convex programs and sometimes just simple quadratic programs. In multi-task settings, several discrimination constraints are available from many tasks which potentially produce even better discrimination. This advantage manifests itself if some parameter tying is involved, for instance, via multi-task sparsity assumptions. Using new variational bounds, it is possible to implement the multitask variants as (sequential) quadratic programs or sequential versions of the independent discrimination problems. In these settings, it is possible to show that multi-task discrimination requires no more than a constant increase in computation over independent single-task discrimination.