Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

SUBLINEAR CONVERGENCE OF A TAMED STOCHASTIC GRADIENT DESCENT METHOD IN HILBERT SPACE

Eisenmann, Monika LU orcid and Stillfjord, Tony LU orcid (2022) In SIAM Journal on Computing 51(4).
Abstract

In this paper, we introduce the tamed stochastic gradient descent method (TSGD) for optimization problems. Inspired by the tamed Euler scheme, which is a commonly used method within the context of stochastic differential equations, TSGD is an explicit scheme that exhibits stability properties similar to those of implicit schemes. As its computational cost is essentially equivalent to that of the well-known stochastic gradient descent method (SGD), it constitutes a very competitive alternative to such methods. We rigorously prove (optimal) sublinear convergence of the scheme for strongly convex objective functions on an abstract Hilbert space. The analysis only requires very mild step size restrictions, which illustrates the good... (More)

In this paper, we introduce the tamed stochastic gradient descent method (TSGD) for optimization problems. Inspired by the tamed Euler scheme, which is a commonly used method within the context of stochastic differential equations, TSGD is an explicit scheme that exhibits stability properties similar to those of implicit schemes. As its computational cost is essentially equivalent to that of the well-known stochastic gradient descent method (SGD), it constitutes a very competitive alternative to such methods. We rigorously prove (optimal) sublinear convergence of the scheme for strongly convex objective functions on an abstract Hilbert space. The analysis only requires very mild step size restrictions, which illustrates the good stability properties. The analysis is based on a priori estimates more frequently encountered in a time integration context than in optimization, and this alternative approach provides a different perspective also on the convergence of SGD. Finally, we demonstrate the usability of the scheme on a problem arising in a context of supervised learning.

(Less)
Please use this url to cite or link to this publication:
author
and
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
convergence analysis, convergence rate, Hilbert space, stochastic optimization, tamed Euler scheme
in
SIAM Journal on Computing
volume
51
issue
4
publisher
Society for Industrial and Applied Mathematics
external identifiers
  • scopus:85135696735
ISSN
0097-5397
DOI
10.1137/21M1427450
language
English
LU publication?
yes
id
07d87245-69aa-4d3b-9086-4d7d640d3cd4
date added to LUP
2022-09-09 14:12:34
date last changed
2023-04-05 14:06:34
@article{07d87245-69aa-4d3b-9086-4d7d640d3cd4,
  abstract     = {{<p>In this paper, we introduce the tamed stochastic gradient descent method (TSGD) for optimization problems. Inspired by the tamed Euler scheme, which is a commonly used method within the context of stochastic differential equations, TSGD is an explicit scheme that exhibits stability properties similar to those of implicit schemes. As its computational cost is essentially equivalent to that of the well-known stochastic gradient descent method (SGD), it constitutes a very competitive alternative to such methods. We rigorously prove (optimal) sublinear convergence of the scheme for strongly convex objective functions on an abstract Hilbert space. The analysis only requires very mild step size restrictions, which illustrates the good stability properties. The analysis is based on a priori estimates more frequently encountered in a time integration context than in optimization, and this alternative approach provides a different perspective also on the convergence of SGD. Finally, we demonstrate the usability of the scheme on a problem arising in a context of supervised learning. </p>}},
  author       = {{Eisenmann, Monika and Stillfjord, Tony}},
  issn         = {{0097-5397}},
  keywords     = {{convergence analysis; convergence rate; Hilbert space; stochastic optimization; tamed Euler scheme}},
  language     = {{eng}},
  number       = {{4}},
  publisher    = {{Society for Industrial and Applied Mathematics}},
  series       = {{SIAM Journal on Computing}},
  title        = {{SUBLINEAR CONVERGENCE OF A TAMED STOCHASTIC GRADIENT DESCENT METHOD IN HILBERT SPACE}},
  url          = {{http://dx.doi.org/10.1137/21M1427450}},
  doi          = {{10.1137/21M1427450}},
  volume       = {{51}},
  year         = {{2022}},
}