  Can deep learning solve multiple tasks simultaneously, even when they are
unrelated and very different? We investigate how the representations of the
underlying tasks affect the ability of a single neural network to learn them
jointly. We present theoretical and empirical findings that a single neural
network is capable of simultaneously learning multiple tasks from a combined
data set, for a variety of methods for representing tasks -- for example, when
the distinct tasks are encoded by well-separated clusters or decision trees
over certain task-code attributes. More concretely, we present a novel analysis
that shows that families of simple programming-like constructs for the codes
encoding the tasks are learnable by two-layer neural networks with standard
training. We study more generally how the complexity of learning such combined
tasks grows with the complexity of the task codes; we find that combining many
tasks may incur a sample complexity penalty, even though the individual tasks
are easy to learn. We provide empirical support for the usefulness of the
learning bounds by training networks on clusters, decision trees, and SQL-style
aggregation.
