Learning Permutations with Exponential Weights

摘要

We give an algorithm for the on-line learning of permutations.The algorithm maintains its uncertainty about thetarget permutation as a doubly stochastic weight matrix, and makes predictions usingan efficient method for decomposing the weight matrix into a convex combinationof permutations.The weight matrix is updated by multiplying the currentmatrix entries by exponential factors, and an iterative procedure is needed to restore double stochasticity.Even though the result of this proceduredoes not have a closed form, a new analysis approachallows us to prove an optimal (up to small constant factors) bound on the regret of our algorithm.This regret bound is significantly better than that of eitherKalai and Vempala's more efficient Follow the Perturbed Leader algorithm orthe computationally expensive method of explicitly representing each permutation asan expert. color="gray">