Optimal Affine-Invariant Smooth Minimization Algorithms

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

19 citations recorded by the source corpus.

We formulate an affine-invariant implementation of the accelerated first-order algorithm in [Y. Nesterov, Dokl. Math., 27 (1983), pp. 372--376]. Its complexity bound is proportional to an affine-invariant regularity constant defined with respect to the Minkowski gauge of the feasible set. We extend these results to more general problems, optimizing Holder smooth functions using $p$-uniformly convex prox terms, and derive an algorithm whose complexity better fits the geometry of the feasible set and adapts to both the best Holder smoothness parameter and the best gradient Lipschitz constant. Finally, we detail matching complexity lower bounds when the feasible set is an $\ell_p$ ball. In this setting, our upper bounds on iteration complexity for the algorithm in [Y. Nesterov, Dokl. Math., 27 (1983), pp. 372--376] are thus optimal in terms of target precision, smoothness, and problem dimension.

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis, Optimization & Training

How researchers see this paper

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

In Artificial Intelligence

In Computational Mechanics

In Numerical Analysis

In Optimization & Training

Citations in the corpus

Affine Invariant Analysis of Frank-Wolfe on Strongly Convex Sets (2020, methodology): “Usually, most works using gauge function assume that the set Q is centrally symmetric [d’Aspremont et al. 2018; Molinaro 2020], which add the assumption that In that case, the gauge function is a norm [Rockafel-lar 1970, Theorem 15.2.].”
Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization (2020, unknown): “‖·‖p that is larger thanO( 1 d1−2/p ) [17].”
Linear Bandits on Uniformly Convex Sets (2021, result): “At a high level, our work shares some similarities with (d’Aspremont et al., 2018) for affine-invariant analysis of accelerated first-order methods or with (Srebro et al.”