  It has been a long-standing goal in machine learning, as well as in AI more
generally, to develop life-long learning systems that learn many different
tasks over time, and reuse insights from tasks learned, "learning to learn" as
they do so. In this work we pose and provide efficient algorithms for several
natural theoretical formulations of this goal. Specifically, we consider the
problem of learning many different target functions over time, that share
certain commonalities that are initially unknown to the learning algorithm. Our
aim is to learn new internal representations as the algorithm learns new target
functions, that capture this commonality and allow subsequent learning tasks to
be solved more efficiently and from less data. We develop efficient algorithms
for two very different kinds of commonalities that target functions might
share: one based on learning common low-dimensional and unions of
low-dimensional subspaces and one based on learning nonlinear Boolean
combinations of features. Our algorithms for learning Boolean feature
combinations additionally have a dual interpretation, and can be viewed as
giving an efficient procedure for constructing near-optimal sparse Boolean
autoencoders under a natural "anchor-set" assumption.
