Skip to Main content Skip to Navigation
Journal articles

Efficient First-order Methods for Convex Minimization: a Constructive Approach

Yoel Drori 1 Adrien Taylor 2, 3
2 SIERRA - Statistical Machine Learning and Parsimony
DI-ENS - Département d'informatique de l'École normale supérieure, CNRS - Centre National de la Recherche Scientifique, Inria de Paris
Abstract : We describe a novel constructive technique for devising efficient first-order methods for a wide range of large-scale convex minimization settings, including smooth, non-smooth, and strongly convex minimization. The technique builds upon a certain variant of the conjugate gradient method to construct a family of methods such that (a) all methods in the family share the same worst-case guarantee as the base conjugate gradient method, and (b) the family includes a fixed-step first-order method. We demonstrate the effectiveness of the approach by deriving optimal methods for the smooth and non-smooth cases, including new methods that forego knowledge of the problem parameters at the cost of a one-dimensional line search per iteration, and a universal method for the union of these classes that requires a three-dimensional search per iteration. In the strongly convex case, we show how numerical tools can be used to perform the construction, and show that the resulting method offers an improved worst-case bound compared to Nesterov’s celebrated fast gradient method.
Complete list of metadata

https://hal.inria.fr/hal-01902048
Contributor : Adrien Taylor <>
Submitted on : Tuesday, October 23, 2018 - 2:18:29 PM
Last modification on : Thursday, July 1, 2021 - 5:58:09 PM

Links full text

Identifiers

Collections

Citation

Yoel Drori, Adrien Taylor. Efficient First-order Methods for Convex Minimization: a Constructive Approach. Mathematical Programming, Series A, Springer, 2020, 184, pp.183-220. ⟨10.1007/s10107-019-01410-2⟩. ⟨hal-01902048⟩

Share

Metrics

Record views

139