Faster subgradient methods for functions with Hölderian growth

Patrick R. Johnstone, Pierre Moulin

Research output: Contribution to journalArticle

Abstract

The purpose of this manuscript is to derive new convergence results for several subgradient methods applied to minimizing nonsmooth convex functions with Hölderian growth. The growth condition is satisfied in many applications and includes functions with quadratic growth and weakly sharp minima as special cases. To this end there are three main contributions. First, for a constant and sufficiently small stepsize, we show that the subgradient method achieves linear convergence up to a certain region including the optimal set, with error of the order of the stepsize. Second, if appropriate problem parameters are known, we derive a decaying stepsize which obtains a much faster convergence rate than is suggested by the classical O(1/k) result for the subgradient method. Thirdly we develop a novel “descending stairs” stepsize which obtains this faster convergence rate and also obtains linear convergence for the special case of weakly sharp functions. We also develop an adaptive variant of the “descending stairs” stepsize which achieves the same convergence rate without requiring an error bound constant which is difficult to estimate in practice.

Original languageEnglish (US)
Pages (from-to)417-450
Number of pages34
JournalMathematical Programming
Volume180
Issue number1-2
DOIs
StateAccepted/In press - Jan 1 2019

Fingerprint

Subgradient Method
Convergence Rate
Linear Convergence
Stairs
Nonsmooth Function
Growth Conditions
Convergence Results
Error Bounds
Convex function
Estimate

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Cite this

Faster subgradient methods for functions with Hölderian growth. / Johnstone, Patrick R.; Moulin, Pierre.

In: Mathematical Programming, Vol. 180, No. 1-2, 01.03.2020, p. 417-450.

Research output: Contribution to journalArticle

Johnstone, Patrick R. ; Moulin, Pierre. / Faster subgradient methods for functions with Hölderian growth. In: Mathematical Programming. 2020 ; Vol. 180, No. 1-2. pp. 417-450.
@article{98ce93b74de542b6a87933a1ae12b254,
title = "Faster subgradient methods for functions with H{\"o}lderian growth",
abstract = "The purpose of this manuscript is to derive new convergence results for several subgradient methods applied to minimizing nonsmooth convex functions with H{\"o}lderian growth. The growth condition is satisfied in many applications and includes functions with quadratic growth and weakly sharp minima as special cases. To this end there are three main contributions. First, for a constant and sufficiently small stepsize, we show that the subgradient method achieves linear convergence up to a certain region including the optimal set, with error of the order of the stepsize. Second, if appropriate problem parameters are known, we derive a decaying stepsize which obtains a much faster convergence rate than is suggested by the classical O(1/k) result for the subgradient method. Thirdly we develop a novel “descending stairs” stepsize which obtains this faster convergence rate and also obtains linear convergence for the special case of weakly sharp functions. We also develop an adaptive variant of the “descending stairs” stepsize which achieves the same convergence rate without requiring an error bound constant which is difficult to estimate in practice.",
author = "Johnstone, {Patrick R.} and Pierre Moulin",
year = "2019",
month = "1",
day = "1",
doi = "10.1007/s10107-018-01361-0",
language = "English (US)",
volume = "180",
pages = "417--450",
journal = "Mathematical Programming",
issn = "0025-5610",
publisher = "Springer-Verlag GmbH and Co. KG",
number = "1-2",

}

TY - JOUR

T1 - Faster subgradient methods for functions with Hölderian growth

AU - Johnstone, Patrick R.

AU - Moulin, Pierre

PY - 2019/1/1

Y1 - 2019/1/1

N2 - The purpose of this manuscript is to derive new convergence results for several subgradient methods applied to minimizing nonsmooth convex functions with Hölderian growth. The growth condition is satisfied in many applications and includes functions with quadratic growth and weakly sharp minima as special cases. To this end there are three main contributions. First, for a constant and sufficiently small stepsize, we show that the subgradient method achieves linear convergence up to a certain region including the optimal set, with error of the order of the stepsize. Second, if appropriate problem parameters are known, we derive a decaying stepsize which obtains a much faster convergence rate than is suggested by the classical O(1/k) result for the subgradient method. Thirdly we develop a novel “descending stairs” stepsize which obtains this faster convergence rate and also obtains linear convergence for the special case of weakly sharp functions. We also develop an adaptive variant of the “descending stairs” stepsize which achieves the same convergence rate without requiring an error bound constant which is difficult to estimate in practice.

AB - The purpose of this manuscript is to derive new convergence results for several subgradient methods applied to minimizing nonsmooth convex functions with Hölderian growth. The growth condition is satisfied in many applications and includes functions with quadratic growth and weakly sharp minima as special cases. To this end there are three main contributions. First, for a constant and sufficiently small stepsize, we show that the subgradient method achieves linear convergence up to a certain region including the optimal set, with error of the order of the stepsize. Second, if appropriate problem parameters are known, we derive a decaying stepsize which obtains a much faster convergence rate than is suggested by the classical O(1/k) result for the subgradient method. Thirdly we develop a novel “descending stairs” stepsize which obtains this faster convergence rate and also obtains linear convergence for the special case of weakly sharp functions. We also develop an adaptive variant of the “descending stairs” stepsize which achieves the same convergence rate without requiring an error bound constant which is difficult to estimate in practice.

UR - http://www.scopus.com/inward/record.url?scp=85059742309&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85059742309&partnerID=8YFLogxK

U2 - 10.1007/s10107-018-01361-0

DO - 10.1007/s10107-018-01361-0

M3 - Article

AN - SCOPUS:85059742309

VL - 180

SP - 417

EP - 450

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

IS - 1-2

ER -