Projekt per år
Sammanfattning
This thesis studies two families of methods for finding zeros of finite sums of monotone operators, the first being variancereduced 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 LSVRG, 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 stepsize 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 periteration cost compared to a previously established projection approach. The framework covers many existing methods and we provide a new primaldual 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.
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 periteration cost compared to a previously established projection approach. The framework covers many existing methods and we provide a new primaldual 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.
Originalspråk  engelska 

Kvalifikation  Doktor 
Tilldelande institution 

Handledare 

Tilldelningsdatum  2022 nov. 25 
Förlag  
ISBN (tryckt)  9789180394093 
ISBN (elektroniskt)  9789180394109 
Status  Published  2022 nov. 1 
Bibliografisk information
Defence detailsDate: 20221125
Time: 10:15
Place: Lecture hall A, building KC4, Naturvetarvägen 18, Lund. Zoom: https://luse.zoom.us/j/62396062448
External reviewer(s)
Name: Mathias Staudigl
Title: Associate professor
Affiliation: Maastricht University, Holland.
Ämnesklassifikation (UKÄ)
 Reglerteknik
Fria nyckelord
 monotone inclusions
 operator splitting
Fingeravtryck
Utforska forskningsämnen för ”Fixed Point Iterations for Finite Sum Monotone Inclusions”. Tillsammans bildar de ett unikt fingeravtryck.Projekt
 1 Avslutade

LargeScale Optimization
Giselsson, P., Fält, M., Sadeghi, H., Morin, M., Banert, S., Upadhyaya, M., Nilsson, M. & Åkerman, A.
2018/01/01 → 2022/12/31
Projekt: Forskning