Exact gradient methodso with memory

FLOREA Mihai I., ()
Additional contact information
FLOREA Mihai I.,: Université catholique de Louvain, CORE, Belgium

No 2019026, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

Abstract: The Inexact Gradient Method with Memory (IGMM) is able to considerably outperform the Gradient Method by employing a piecewise linear lower model on the smooth part of the objective. However, this model cannot be solved exactly and IGMM relies on an inaccuracy term d. The need for a bound on inexactness narrows the range of problems to which IGMM can be applied. In addition, d carries over to the worst-case convergence rate. In this work, we show how a simple modification of IGMM eliminates the reliance on d for convergence. The resulting Exact Gradient Method with Memory (EGMM) is as broadly applicable as the Bregman Distance Gradient Method (NoLips) and has a worst-case rate of O(1/k), recently shown to be optimal for its class. Moreover, the elimination of d allows us to accelerate EGMM without error accumulation, yielding an Accelerated Gradient Method with Memory (AGMM) possessing a worst-case rate of O(1/k2) on the largest subclass of problems for which acceleration is known to be attainable. Preliminary computational experiments show that the flexibility of our model enables EGMM to surpass IGMM in practical performance. The convergence speed of AGMM also consistently exceeds that of FGM, even with small bundles.

Keywords: gradient method; bundle; piece-wise linear model; acceleration; Bregman distance; relative smoothness; composite problem (search for similar items in EconPapers)
Date: 2019-12-17
New Economics Papers: this item is included in nep-cmp
References: Add references at CitEc
Citations:

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp2019.html (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvco:2019026

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().