We study the block-coordinate forward-backward algorithm in which the blocks are updated in a random and possibly parallel manner, according to arbitrary probabilities. The algorithm allows different stepsizes along the block-coordinates to fully exploit the smoothness properties of the objective function. In the convex case and in an infinite dimensional setting, we establish almost sure weak convergence of the iterates and the asymptotic rate o(1/n) for the mean of the function values. We derive linear rates under strong convexity and error bound conditions. Our analysis is based on an abstract convergence principle for stochastic descent algorithms which allows to extend and simplify existing results.

Parallel random block-coordinate forward-backward algorithm: a unified convergence analysis / Salzo, S; Villa, S. - In: MATHEMATICAL PROGRAMMING. - ISSN 0025-5610. - 193:1(2022), pp. 225-269. [10.1007/s10107-020-01602-1]

Parallel random block-coordinate forward-backward algorithm: a unified convergence analysis

Salzo, S
;
2022

Abstract

We study the block-coordinate forward-backward algorithm in which the blocks are updated in a random and possibly parallel manner, according to arbitrary probabilities. The algorithm allows different stepsizes along the block-coordinates to fully exploit the smoothness properties of the objective function. In the convex case and in an infinite dimensional setting, we establish almost sure weak convergence of the iterates and the asymptotic rate o(1/n) for the mean of the function values. We derive linear rates under strong convexity and error bound conditions. Our analysis is based on an abstract convergence principle for stochastic descent algorithms which allows to extend and simplify existing results.
2022
convex optimization; parallel algorithms; random block-coordinate descent; arbitrary sampling; error bounds; stochastic quasi-Fejé r sequences; forward– backward algorithm; convergence rates
01 Pubblicazione su rivista::01a Articolo in rivista
Parallel random block-coordinate forward-backward algorithm: a unified convergence analysis / Salzo, S; Villa, S. - In: MATHEMATICAL PROGRAMMING. - ISSN 0025-5610. - 193:1(2022), pp. 225-269. [10.1007/s10107-020-01602-1]
File allegati a questo prodotto
File Dimensione Formato  
Salzo_Parallel_2022.pdf

solo gestori archivio

Note: DOI https://doi.org/10.1007/s10107-020-01602-1
Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 934.39 kB
Formato Adobe PDF
934.39 kB Adobe PDF   Contatta l'autore
Salzo_preprint_Parallel_2020.pdf

accesso aperto

Note: DOI https://doi.org/10.1007/s10107-020-01602-1
Tipologia: Documento in Pre-print (manoscritto inviato all'editore, precedente alla peer review)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 731.9 kB
Formato Adobe PDF
731.9 kB Adobe PDF

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1675254
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 10
social impact