  We present a general regularization-based framework for Multi-task learning
(MTL), in which the similarity between tasks can be learned or refined using
$\ell_p$-norm Multiple Kernel learning (MKL). Based on this very general
formulation (including a general loss function), we derive the corresponding
dual formulation using Fenchel duality applied to Hermitian matrices. We show
that numerous established MTL methods can be derived as special cases from
both, the primal and dual of our formulation. Furthermore, we derive a modern
dual-coordinate descend optimization strategy for the hinge-loss variant of our
formulation and provide convergence bounds for our algorithm. As a special
case, we implement in C++ a fast LibLinear-style solver for $\ell_p$-norm MKL.
In the experimental section, we analyze various aspects of our algorithm such
as predictive performance and ability to reconstruct task relationships on
biologically inspired synthetic data, where we have full control over the
underlying ground truth. We also experiment on a new dataset from the domain of
computational biology that we collected for the purpose of this paper. It
concerns the prediction of transcription start sites (TSS) over nine organisms,
which is a crucial task in gene finding. Our solvers including all discussed
special cases are made available as open-source software as part of the SHOGUN
machine learning toolbox (available at \url{http://shogun.ml}).
