An Optimal Affine Invariant Smooth Minimization Algorithm

By Alexandre d'Aspremont, Crist'obal Guzm'an, Martin Jaggi. 2013

13 citations recorded by the source corpus.

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 constant defined with respect to the Minkowski gauge of the feasible set. We also detail matching lower bounds when the feasible set is an $\ell_p$ ball. In this setting, our bounds on iteration complexity for the algorithm in Nesterov (1983) are thus optimal in terms of target precision, smoothness and problem dimension.

Subfields: Mathematical Optimization

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Mathematical Optimization

1. Guanghui Lan
2. Zeyuan Allen-Zhu
3. Simon Lacoste-Julien
4. Saeed Ghadimi
5. John C. Duchi

Citations in the corpus

• The Complexity of Large-scale Convex Programming under a Linear Optimization Oracle (2013, background): “This property is also referred to affine invariance (see [29,14] for more discussions).”