title: Learning Permutations with Exponential Weights
speaker:
Manfred K. Warmuth
Computer Science Department
University of California, Santa Cruz
abstract:
We give an algorithm for the on-line learning of permutations.
The algorithm maintains its uncertainty about the target permutation
as a doubly stochastic weight matrix (i.e. first order
information), and makes predictions using
an efficient method for decomposing the weight matrix into a convex
combination of permutations.
The weight matrix is updated by multiplying the current
matrix entries by exponential factors,
and an iterative procedure is needed to restore double stochasticity.
Even though the result of this procedure
does not have a closed form, a new analysis approach
allows us to prove optimal regret bounds
(up to small constant factors)
for the case when the loss is linear in the
doubly stochastic matrix.
We conclude with a discussion of what happens to our method
when higher order information about permutations needs to
be maintained.
This is joint work with David Helmbold.