Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Cocoercivity, smoothness and bias in variance-reduced stochastic gradient methods

Morin, Martin LU and Giselsson, Pontus LU orcid (2022) In Numerical Algorithms 91(2). p.749-772
Abstract

With the purpose of examining biased updates in variance-reduced stochastic gradient methods, we introduce SVAG, a SAG/SAGA-like method with adjustable bias. SVAG is analyzed in a cocoercive root-finding setting, a setting which yields the same results as in the usual smooth convex optimization setting for the ordinary proximal-gradient method. We show that the same is not true for SVAG when biased updates are used. The step-size requirements for when the operators are gradients are significantly less restrictive compared to when they are not. This highlights the need to not rely solely on cocoercivity when analyzing variance-reduced methods meant for optimization. Our analysis either match or improve on previously known convergence... (More)

With the purpose of examining biased updates in variance-reduced stochastic gradient methods, we introduce SVAG, a SAG/SAGA-like method with adjustable bias. SVAG is analyzed in a cocoercive root-finding setting, a setting which yields the same results as in the usual smooth convex optimization setting for the ordinary proximal-gradient method. We show that the same is not true for SVAG when biased updates are used. The step-size requirements for when the operators are gradients are significantly less restrictive compared to when they are not. This highlights the need to not rely solely on cocoercivity when analyzing variance-reduced methods meant for optimization. Our analysis either match or improve on previously known convergence conditions for SAG and SAGA. However, in the biased cases they still do not correspond well with practical experiences and we therefore examine the effect of bias numerically on a set of classification problems. The choice of bias seem to primarily affect the early stages of convergence and in most cases the differences vanish in the later stages of convergence. However, the effect of the bias choice is still significant in a couple of cases.

(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
Bias, Monotone inclusion, Root finding, SAG, SAGA, Stochastic gradient, Variance reduction
in
Numerical Algorithms
volume
91
issue
2
pages
749 - 772
publisher
Springer
external identifiers
  • scopus:85128058610
ISSN
1017-1398
DOI
10.1007/s11075-022-01280-4
language
English
LU publication?
yes
id
ae6c650d-957c-48e3-90e8-6faefd8524f6
date added to LUP
2022-06-15 11:45:11
date last changed
2023-11-21 05:49:16
@article{ae6c650d-957c-48e3-90e8-6faefd8524f6,
  abstract     = {{<p>With the purpose of examining biased updates in variance-reduced stochastic gradient methods, we introduce SVAG, a SAG/SAGA-like method with adjustable bias. SVAG is analyzed in a cocoercive root-finding setting, a setting which yields the same results as in the usual smooth convex optimization setting for the ordinary proximal-gradient method. We show that the same is not true for SVAG when biased updates are used. The step-size requirements for when the operators are gradients are significantly less restrictive compared to when they are not. This highlights the need to not rely solely on cocoercivity when analyzing variance-reduced methods meant for optimization. Our analysis either match or improve on previously known convergence conditions for SAG and SAGA. However, in the biased cases they still do not correspond well with practical experiences and we therefore examine the effect of bias numerically on a set of classification problems. The choice of bias seem to primarily affect the early stages of convergence and in most cases the differences vanish in the later stages of convergence. However, the effect of the bias choice is still significant in a couple of cases.</p>}},
  author       = {{Morin, Martin and Giselsson, Pontus}},
  issn         = {{1017-1398}},
  keywords     = {{Bias; Monotone inclusion; Root finding; SAG; SAGA; Stochastic gradient; Variance reduction}},
  language     = {{eng}},
  number       = {{2}},
  pages        = {{749--772}},
  publisher    = {{Springer}},
  series       = {{Numerical Algorithms}},
  title        = {{Cocoercivity, smoothness and bias in variance-reduced stochastic gradient methods}},
  url          = {{http://dx.doi.org/10.1007/s11075-022-01280-4}},
  doi          = {{10.1007/s11075-022-01280-4}},
  volume       = {{91}},
  year         = {{2022}},
}