Abstract.When we have several related tasks, solving them simultaneously has been shown to be more effective than solving them individually. This approach is called multi-task learning (MTL). In this paper, we propose a novel MTL algorithm. Our method controls the relatedness among the tasks locally, so all pairs of related tasks are guaranteed to have similar solutions. We apply the above idea to support vector machines and show that the optimization problem can be cast as a second-order cone program, which is convex and can be solved efficiently. The usefulness of our approach is demonstrated in ordinal regression, link prediction and collaborative filtering, each of which can be formulated as a structured multi-task problem.