An optimal affine invariant smooth minimization algorithm

We formulate an affine invariant implementation of the algorithm in Nesterov (1983). We show that the complexity bound is then proportional to an affine invariant regularity constants defined with respect to the Minkowski gauge of the feasible set. We then discuss implications in the design and efficient implementation of accelerated first-order methods. [Joint work with Martin Jaggi]