  We propose a game-based formulation for learning dimensionality-reducing
representations of feature vectors, when only a prior knowledge on future
prediction tasks is available. In this game, the first player chooses a
representation, and then the second player adversarially chooses a prediction
task from a given class, representing the prior knowledge. The first player
aims is to minimize, and the second player to maximize, the regret: The minimal
prediction loss using the representation, compared to the same loss using the
original features. For the canonical setting in which the representation, the
response to predict and the predictors are all linear functions, and under the
mean squared error loss function, we derive the theoretically optimal
representation in pure strategies, which shows the effectiveness of the prior
knowledge, and the optimal regret in mixed strategies, which shows the
usefulness of randomizing the representation. For general representations and
loss functions, we propose an efficient algorithm to optimize a randomized
representation. The algorithm only requires the gradients of the loss function,
and is based on incrementally adding a representation rule to a mixture of such
rules.
