Minimax Optimal Algorithms for Unconstrained Linear Optimization
  We design and analyze minimax-optimal algorithms for online linear
optimization games where the player's choice is unconstrained. The player
strives to minimize regret, the difference between his loss and the loss of a
post-hoc benchmark strategy. The standard benchmark is the loss of the best
strategy chosen from a bounded comparator set. When the the comparison set and
the adversary's gradients satisfy L_infinity bounds, we give the value of the
game in closed form and prove it approaches sqrt(2T/pi) as T -> infinity.
  Interesting algorithms result when we consider soft constraints on the
comparator, rather than restricting it to a bounded set. As a warmup, we
analyze the game with a quadratic penalty. The value of this game is exactly
T/2, and this value is achieved by perhaps the simplest online algorithm of
all: unprojected gradient descent with a constant learning rate.
  We then derive a minimax-optimal algorithm for a much softer penalty
function. This algorithm achieves good bounds under the standard notion of
regret for any comparator point, without needing to specify the comparator set
in advance. The value of this game converges to sqrt{e} as T ->infinity; we
give a closed-form for the exact value as a function of T. The resulting
algorithm is natural in unconstrained investment or betting scenarios, since it
guarantees at worst constant loss, while allowing for exponential reward
against an "easy" adversary.
