Adaptive Restart of the Optimized Gradient Method for Convex Optimization

Cited 7 time in webofscience Cited 0 time in scopus
  • Hit : 168
  • Download : 0
DC FieldValueLanguage
dc.contributor.authorKim, Donghwanko
dc.contributor.authorFessler, Jeffrey A.ko
dc.date.accessioned2018-09-18T05:52:36Z-
dc.date.available2018-09-18T05:52:36Z-
dc.date.created2018-08-21-
dc.date.created2018-08-21-
dc.date.issued2018-07-
dc.identifier.citationJOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, v.178, no.1, pp.240 - 263-
dc.identifier.issn0022-3239-
dc.identifier.urihttp://hdl.handle.net/10203/245422-
dc.description.abstractFirst-order methods with momentum, such as Nesterov's fast gradient method, are very useful for convex optimization problems, but can exhibit undesirable oscillations yielding slow convergence rates for some applications. An adaptive restarting scheme can improve the convergence rate of the fast gradient method, when the parameter of a strongly convex cost function is unknown or when the iterates of the algorithm enter a locally strongly convex region. Recently, we introduced the optimized gradient method, a first-order algorithm that has an inexpensive per-iteration computational cost similar to that of the fast gradient method, yet has a worst-case cost function rate that is twice faster than that of the fast gradient method and that is optimal for large-dimensional smooth convex problems. Building upon the success of accelerating the fast gradient method using adaptive restart, this paper investigates similar heuristic acceleration of the optimized gradient method. We first derive a new first-order method that resembles the optimized gradient method for strongly convex quadratic problems with known function parameters, yielding a linear convergence rate that is faster than that of the analogous version of the fast gradient method. We then provide a heuristic analysis and numerical experiments that illustrate that adaptive restart can accelerate the convergence of the optimized gradient method. Numerical results also illustrate that adaptive restart is helpful for a proximal version of the optimized gradient method for nonsmooth composite convex functions.-
dc.languageEnglish-
dc.publisherSPRINGER/PLENUM PUBLISHERS-
dc.subjectCONVERGENCE-
dc.subjectALGORITHMS-
dc.titleAdaptive Restart of the Optimized Gradient Method for Convex Optimization-
dc.typeArticle-
dc.identifier.wosid000436425000012-
dc.identifier.scopusid2-s2.0-85046554246-
dc.type.rimsART-
dc.citation.volume178-
dc.citation.issue1-
dc.citation.beginningpage240-
dc.citation.endingpage263-
dc.citation.publicationnameJOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS-
dc.identifier.doi10.1007/s10957-018-1287-4-
dc.contributor.localauthorKim, Donghwan-
dc.contributor.nonIdAuthorFessler, Jeffrey A.-
dc.description.isOpenAccessN-
dc.type.journalArticleArticle-
dc.subject.keywordAuthorConvex optimization-
dc.subject.keywordAuthorFirst-order methods-
dc.subject.keywordAuthorAccelerated gradient methods-
dc.subject.keywordAuthorOptimized gradient method-
dc.subject.keywordAuthorRestarting-
dc.subject.keywordPlusCONVERGENCE-
dc.subject.keywordPlusALGORITHMS-
Appears in Collection
MA-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡ Click to see webofscience_button
⊙ Cited 7 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0