Abstract:
We formulate an affine invariant implementation of the algorithm in Nesterov (1983). We show that the complexity bound is then proportional to a 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.

Note: Joint work with Martin Jaggi.