Gradient descent in a generalised Bregman distance framework

Martin Benning, Marta M. Betcke, Matthias J. Ehrhardt, Carola-Bibiane Schönlieb

Research output: Working paper

10 Downloads (Pure)

Abstract

We discuss a special form of gradient descent that in the literature has become known as the so-called linearised Bregman iteration. The idea is to replace the classical (squared) two norm metric in the gradient descent setting with a generalised Bregman distance, based on a more general proper, convex and lower semi-continuous functional. Gradient descent as well as the entropic mirror descent by Nemirovsky and Yudin are special cases, as is a specific form of non-linear Landweber iteration introduced by Bachmayr and Burger. We are going to analyse the linearised Bregman iteration in a setting where the functional we want to minimise is neither necessarily Lipschitz-continuous (in the classical sense) nor necessarily convex, and establish a global convergence result under the additional assumption that the functional we wish to minimise satisfies the so-called Kurdyka-{\L}ojasiewicz property.
Original languageEnglish
Publication statusPublished - 8 Dec 2016

Keywords

  • math.OC
  • 49M37, 65K05, 65K10, 90C26, 90C30
  • G.1.0; G.1.6

Cite this

Benning, M., Betcke, M. M., Ehrhardt, M. J., & Schönlieb, C-B. (2016). Gradient descent in a generalised Bregman distance framework.

Gradient descent in a generalised Bregman distance framework. / Benning, Martin; Betcke, Marta M.; Ehrhardt, Matthias J.; Schönlieb, Carola-Bibiane.

2016.

Research output: Working paper

Benning M, Betcke MM, Ehrhardt MJ, Schönlieb C-B. Gradient descent in a generalised Bregman distance framework. 2016 Dec 8.
Benning, Martin ; Betcke, Marta M. ; Ehrhardt, Matthias J. ; Schönlieb, Carola-Bibiane. / Gradient descent in a generalised Bregman distance framework. 2016.
@techreport{3422886483c448139f008498927a3bdc,
title = "Gradient descent in a generalised Bregman distance framework",
abstract = "We discuss a special form of gradient descent that in the literature has become known as the so-called linearised Bregman iteration. The idea is to replace the classical (squared) two norm metric in the gradient descent setting with a generalised Bregman distance, based on a more general proper, convex and lower semi-continuous functional. Gradient descent as well as the entropic mirror descent by Nemirovsky and Yudin are special cases, as is a specific form of non-linear Landweber iteration introduced by Bachmayr and Burger. We are going to analyse the linearised Bregman iteration in a setting where the functional we want to minimise is neither necessarily Lipschitz-continuous (in the classical sense) nor necessarily convex, and establish a global convergence result under the additional assumption that the functional we wish to minimise satisfies the so-called Kurdyka-{\L}ojasiewicz property.",
keywords = "math.OC, 49M37, 65K05, 65K10, 90C26, 90C30, G.1.0; G.1.6",
author = "Martin Benning and Betcke, {Marta M.} and Ehrhardt, {Matthias J.} and Carola-Bibiane Sch{\"o}nlieb",
note = "Conference proceedings of '2016 Geometric Numerical Integration and its Applications Maths Conference at La Trobe University, Melbourne Australia', MI Lecture Notes series of Kyushu University, six pages, one figure, program code: https://doi.org/10.17863/CAM.6714",
year = "2016",
month = "12",
day = "8",
language = "English",
type = "WorkingPaper",

}

TY - UNPB

T1 - Gradient descent in a generalised Bregman distance framework

AU - Benning, Martin

AU - Betcke, Marta M.

AU - Ehrhardt, Matthias J.

AU - Schönlieb, Carola-Bibiane

N1 - Conference proceedings of '2016 Geometric Numerical Integration and its Applications Maths Conference at La Trobe University, Melbourne Australia', MI Lecture Notes series of Kyushu University, six pages, one figure, program code: https://doi.org/10.17863/CAM.6714

PY - 2016/12/8

Y1 - 2016/12/8

N2 - We discuss a special form of gradient descent that in the literature has become known as the so-called linearised Bregman iteration. The idea is to replace the classical (squared) two norm metric in the gradient descent setting with a generalised Bregman distance, based on a more general proper, convex and lower semi-continuous functional. Gradient descent as well as the entropic mirror descent by Nemirovsky and Yudin are special cases, as is a specific form of non-linear Landweber iteration introduced by Bachmayr and Burger. We are going to analyse the linearised Bregman iteration in a setting where the functional we want to minimise is neither necessarily Lipschitz-continuous (in the classical sense) nor necessarily convex, and establish a global convergence result under the additional assumption that the functional we wish to minimise satisfies the so-called Kurdyka-{\L}ojasiewicz property.

AB - We discuss a special form of gradient descent that in the literature has become known as the so-called linearised Bregman iteration. The idea is to replace the classical (squared) two norm metric in the gradient descent setting with a generalised Bregman distance, based on a more general proper, convex and lower semi-continuous functional. Gradient descent as well as the entropic mirror descent by Nemirovsky and Yudin are special cases, as is a specific form of non-linear Landweber iteration introduced by Bachmayr and Burger. We are going to analyse the linearised Bregman iteration in a setting where the functional we want to minimise is neither necessarily Lipschitz-continuous (in the classical sense) nor necessarily convex, and establish a global convergence result under the additional assumption that the functional we wish to minimise satisfies the so-called Kurdyka-{\L}ojasiewicz property.

KW - math.OC

KW - 49M37, 65K05, 65K10, 90C26, 90C30

KW - G.1.0; G.1.6

M3 - Working paper

BT - Gradient descent in a generalised Bregman distance framework

ER -