Exponential Weights on the Hypercube in Polynomial Time
  We study a general online linear optimization problem(OLO). At each round, a
subset of objects from a fixed universe of $n$ objects is chosen, and a linear
cost associated with the chosen subset is incurred. To measure the performance
of our algorithms, we use the notion of regret which is the difference between
the total cost incurred over all iterations and the cost of the best fixed
subset in hindsight. We consider Full Information and Bandit feedback for this
problem. This problem is equivalent to OLO on the $\{0,1\}^n$ hypercube. The
Exp2 algorithm and its bandit variant are commonly used strategies for this
problem. It was previously unknown if it is possible to run Exp2 on the
hypercube in polynomial time.
  In this paper, we present a polynomial time algorithm called PolyExp for OLO
on the hypercube. We show that our algorithm is equivalent Exp2 on $\{0,1\}^n$,
Online Mirror Descent(OMD), Follow The Regularized Leader(FTRL) and Follow The
Perturbed Leader(FTPL) algorithms. We show PolyExp achieves expected regret
bound that is a factor of $\sqrt{n}$ better than Exp2 in the full information
setting under $L_\infty$ adversarial losses. Because of the equivalence of
these algorithms, this implies an improvement on Exp2's regret bound in full
information. We also show matching regret lower bounds. Finally, we show how to
use PolyExp on the $\{-1,+1\}^n$ hypercube, solving an open problem in Bubeck
et al (COLT 2012).
