On the Statistical Efficiency of $\ell_{1,p}$ Multi-Task Learning of Gaussian Graphical Models

In this paper, we present $\ell_{1,p}$ multi-task structure learning for Gaussian graphical models. We discuss the uniqueness and boundedness of the optimal solution of the maximization problem. A block coordinate descent method leads to a provably convergent algorithm that generates a sequence of positive definite solutions. Thus, we reduce the original problem into a sequence of strictly convex $\ell_p$ regularized quadratic minimization subproblems. We further show that this subproblem leads to the continuous quadratic knapsack problem for $p=\infty$ and to a separable version of the well-known quadratic trust-region problem for $p=2$, for which very efficient methods exist. Finally, we show promising results in synthetic experiments as well as in two real-world datasets.