Publication: UN MÉTODO DE DESCENSO POR COORDENADAS DOBLEMENTE ACELERADO, PROXIMAL Y PARALELO
Loading...
Date
2019-08-12
Authors
BENAVIDES LORCA, FRANCISCO JAVIER
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
En este trabajo proponemos una variante del algoritmo APProx, el cual pertenece
a la familia de los algoritmos de descenso por bloque aleatorios, los que se caracterizan
por actuar en cada iteración sobre una cantidad de coordenadas (o bloques de ellas), igual
o menor al total disponible, las cuales se seleccionan de manera aleatoria.La importancia del algoritmo APProx esta dada por la particularidad de ser acelerado, proximal y paralelizable. Paralelizable, en el sentido de que cada bloque puede ser actualizado en una CPU diferente; Proximal, al poder lidiar con funciones subdiferenciables; Y acelerado, pues posee una tasa de convergencia de O(1/k 2 ). Nuestra variante, la cual nombramos aAPProx posee estas mismas cualidades y, conjeturamos, posee una tasa de convergencia
menor (o(1/k 2 )).
En concreto, presentamos un bosquejo de la demostración de dicha convergencia, la cual se
obtiene al extrapolar las ideas presentes en [1], en donde se obtiene este mismo resultado
para el algoritmo Backward-Forward de Nesterov, el cual es (a grandes rasgos) la versión
determinista de APPROX. Además se presenta de manera empı́rica este resultado, mediante
un problema de recuperación de imágenes.
In this work, we propose a variant of the APProx algorithm. This belongs to the block coordinate descent algorithm family, which principal characteristic is, on each inter- ation, update just some coordinates (or blocks of them) less or equal to the total available, selected by random. The importance of APProx, is because this is acccelerated, proximal and parallel. Parallel in the sense of each block can be updated on each CPU; Proximal, because APProx can handle with not smooth convex functions; And Accelerated, because this has a convergence rate of O(1/k 2 ). Our variant, named as aAPProx has this same properties and, we guess, a convergence rate of (o(1/k 2 )). In fact, we presented a scheme of the proof for this convergence rate, obtained using some ideas presented on [1], where they obtained this result for the Backward-Forward Neste- rov algorithm, which could be considered as the deterministic version of APProx. Also we presented some empirical results, for the recovery images problem.
In this work, we propose a variant of the APProx algorithm. This belongs to the block coordinate descent algorithm family, which principal characteristic is, on each inter- ation, update just some coordinates (or blocks of them) less or equal to the total available, selected by random. The importance of APProx, is because this is acccelerated, proximal and parallel. Parallel in the sense of each block can be updated on each CPU; Proximal, because APProx can handle with not smooth convex functions; And Accelerated, because this has a convergence rate of O(1/k 2 ). Our variant, named as aAPProx has this same properties and, we guess, a convergence rate of (o(1/k 2 )). In fact, we presented a scheme of the proof for this convergence rate, obtained using some ideas presented on [1], where they obtained this result for the Backward-Forward Neste- rov algorithm, which could be considered as the deterministic version of APProx. Also we presented some empirical results, for the recovery images problem.
Description
Keywords
APPROX , LASSO , NESTEROV