This dissertation presents multi-objective multi-task learning, a new learning framework. Given a fixed sequence of tasks, the learned hypothesis space must minimize multiple objectives. Since these objectives are often in conflict, we cannot find a single best solution, so we analyze a set of solutions. We first propose and analyze a new learning principle, empirically efficient learning. From a sample complexity perspective, following this principle is not much worse than the single-objective multi-task learning case. In the context of empirically efficient learning, algorithms for the new learning frameworks are proposed and evaluated. First, we pose regularization as a multi-objective problem, in which training error must balance the complexity of the hypothesis space. Second, we consider multiple data-dependent loss functions, in which the error rate in one class must balance the error rate in the other class. Finally, we assume that tasks share a clustering structure in which the average loss in one cluster must balance the loss in another cluster. The algorithms are evaluated on synthetic and real datasets. The results motivate the application of multi-objective optimization, indicating that the objectives are in conflict. By controlling the relative performance of the algorithms to generate a tradeoff surface, we can effectively explore the multi-objective nature of the learning problem.