Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Fixed Point Iterations for Finite Sum Monotone Inclusions

Morin, Martin LU (2022)
Abstract
This thesis studies two families of methods for finding zeros of finite sums of monotone operators, the first being variance-reduced stochastic gradient (VRSG) methods. This is a large family of algorithms that use random sampling to improve the convergence rate compared to more traditional approaches. We examine the optimal sampling distributions and their interaction with the epoch length. Specifically, we show that in methods like SAGA, where the epoch length is directly tied to the random sampling, the optimal sampling becomes more complex compared to for instance L-SVRG, where the epoch length can be chosen independently. We also show that biased VRSG estimates in the style of SAG are sensitive to the problem setting. More precisely,... (More)
This thesis studies two families of methods for finding zeros of finite sums of monotone operators, the first being variance-reduced stochastic gradient (VRSG) methods. This is a large family of algorithms that use random sampling to improve the convergence rate compared to more traditional approaches. We examine the optimal sampling distributions and their interaction with the epoch length. Specifically, we show that in methods like SAGA, where the epoch length is directly tied to the random sampling, the optimal sampling becomes more complex compared to for instance L-SVRG, where the epoch length can be chosen independently. We also show that biased VRSG estimates in the style of SAG are sensitive to the problem setting. More precisely, a significantly larger step-size can be used when the monotone operators are cocoercive gradients compared to when they just are cocoercive. This is noteworthy since the standard gradient descent is not affected by this change and the fact that the sensitivity to the problem assumption vanishes when the estimates are unbiased.
The second set of methods we examine are deterministic operator splitting methods and we focus on frameworks for constructing and analyzing such splitting methods. One such framework is based on what we call nonlinear resolvents and we present a novel way of ensuring convergence of iterations of nonlinear resolvents by the means of a momentum term. This approach leads in many cases to cheaper per-iteration cost compared to a previously established projection approach. The framework covers many existing methods and we provide a new primal-dual method that uses an extra resolvent step as well as a general approach for adding momentum to any special case of our nonlinear resolvent method. We use a similar concept to the nonlinear resolvent to derive a representation of the entire class of frugal splitting operators, which are splitting operators that use exactly one direct or resolvent evaluation of each operator of the monotone inclusion problem. The representation reveals several new results regarding lifting numbers, existence of solution maps, and parallelizability of the forward/backward evaluations. We show that the minimal lifting is n − 1 − f where n is the number of monotone operators and f is the number of direct evaluations in the splitting. A new convergent and parallelizable frugal splitting operator with minimal lifting is also presented. (Less)
Please use this url to cite or link to this publication:
author
supervisor
opponent
  • Associate professor Mathias Staudigl, Maastricht University, Holland.
organization
publishing date
type
Thesis
publication status
published
subject
keywords
monotone inclusions, operator splitting
pages
179 pages
publisher
Department of Automatic Control, Lund University
defense location
Lecture hall A, building KC4, Naturvetarvägen 18, Lund. Zoom: https://lu-se.zoom.us/j/62396062448
defense date
2022-11-25 10:15:00
ISSN
0280-5316
0280-5316
ISBN
978-91-8039-409-3
978-91-8039-410-9
project
Large-Scale Optimization
language
English
LU publication?
yes
id
5557c471-ff64-4cdc-9cfb-68afdc6e85eb
date added to LUP
2022-10-28 16:36:14
date last changed
2022-10-31 14:19:29
@phdthesis{5557c471-ff64-4cdc-9cfb-68afdc6e85eb,
  abstract     = {{This thesis studies two families of methods for finding zeros of finite sums of monotone operators, the first being variance-reduced stochastic gradient (VRSG) methods. This is a large family of algorithms that use random sampling to improve the convergence rate compared to more traditional approaches. We examine the optimal sampling distributions and their interaction with the epoch length. Specifically, we show that in methods like SAGA, where the epoch length is directly tied to the random sampling, the optimal sampling becomes more complex compared to for instance L-SVRG, where the epoch length can be chosen independently. We also show that biased VRSG estimates in the style of SAG are sensitive to the problem setting. More precisely, a significantly larger step-size can be used when the monotone operators are cocoercive gradients compared to when they just are cocoercive. This is noteworthy since the standard gradient descent is not affected by this change and the fact that the sensitivity to the problem assumption vanishes when the estimates are unbiased.<br/> The second set of methods we examine are deterministic operator splitting methods and we focus on frameworks for constructing and analyzing such splitting methods. One such framework is based on what we call nonlinear resolvents and we present a novel way of ensuring convergence of iterations of nonlinear resolvents by the means of a momentum term. This approach leads in many cases to cheaper per-iteration cost compared to a previously established projection approach. The framework covers many existing methods and we provide a new primal-dual method that uses an extra resolvent step as well as a general approach for adding momentum to any special case of our nonlinear resolvent method. We use a similar concept to the nonlinear resolvent to derive a representation of the entire class of frugal splitting operators, which are splitting operators that use exactly one direct or resolvent evaluation of each operator of the monotone inclusion problem. The representation reveals several new results regarding lifting numbers, existence of solution maps, and parallelizability of the forward/backward evaluations. We show that the minimal lifting is n − 1 − f where n is the number of monotone operators and f is the number of direct evaluations in the splitting. A new convergent and parallelizable frugal splitting operator with minimal lifting is also presented.}},
  author       = {{Morin, Martin}},
  isbn         = {{978-91-8039-409-3}},
  issn         = {{0280-5316}},
  keywords     = {{monotone inclusions; operator splitting}},
  language     = {{eng}},
  month        = {{11}},
  publisher    = {{Department of Automatic Control, Lund University}},
  school       = {{Lund University}},
  title        = {{Fixed Point Iterations for Finite Sum Monotone Inclusions}},
  url          = {{https://lup.lub.lu.se/search/files/127015831/thesis.pdf}},
  year         = {{2022}},
}