MAGMA: Multi-level accelerated gradient mirror descent algorithm for large-scale convex composite minimization
File(s)
Accepted version
Published version
Author(s)
Hovhannisyan, V
Parpas, P
Zafeiriou, S
Type
Journal Article
Abstract
Composite convex optimization models arise in several applications, and are especially prevalent
in inverse problems with a sparsity inducing norm and in general convex optimization with simple
constraints. The most widely used algorithms for convex composite models are accelerated first order
methods, however they can take a large number of iterations to compute an acceptable solution for
large-scale problems. In this paper we propose to speed up first order methods by taking advantage
of the structure present in many applications and in image processing in particular. Our method is
based on multi-level optimization methods and exploits the fact that many applications that give
rise to large scale models can be modelled using varying degrees of fidelity. We use Nesterov’s
acceleration techniques together with the multi-level approach to achieve an O(1/
√
ǫ) convergence
rate, where ǫ denotes the desired accuracy. The proposed method has a better convergence rate
than any other existing multi-level method for convex problems, and in addition has the same rate
as accelerated methods, which is known to be optimal for first-order methods. Moreover, as our
numerical experiments show, on large-scale face recognition problems our algorithm is several times
faster than the state of the art.
in inverse problems with a sparsity inducing norm and in general convex optimization with simple
constraints. The most widely used algorithms for convex composite models are accelerated first order
methods, however they can take a large number of iterations to compute an acceptable solution for
large-scale problems. In this paper we propose to speed up first order methods by taking advantage
of the structure present in many applications and in image processing in particular. Our method is
based on multi-level optimization methods and exploits the fact that many applications that give
rise to large scale models can be modelled using varying degrees of fidelity. We use Nesterov’s
acceleration techniques together with the multi-level approach to achieve an O(1/
√
ǫ) convergence
rate, where ǫ denotes the desired accuracy. The proposed method has a better convergence rate
than any other existing multi-level method for convex problems, and in addition has the same rate
as accelerated methods, which is known to be optimal for first-order methods. Moreover, as our
numerical experiments show, on large-scale face recognition problems our algorithm is several times
faster than the state of the art.
Date Issued
2016-11-15
Date Acceptance
2016-09-01
Citation
SIAM Journal on Imaging Sciences, 2016, 9 (4), pp.1829-1857
ISSN
1936-4954
Publisher
Society for Industrial and Applied Mathematics
Start Page
1829
End Page
1857
Journal / Book Title
SIAM Journal on Imaging Sciences
Volume
9
Issue
4
Copyright Statement
Copyright © by SIAM. Unauthorized reproduction of this article is prohibited
Sponsor
Commission of the European Communities
Engineering & Physical Science Research Council (EPSRC)
Engineering & Physical Science Research Council (E
Grant Number
FP7 - 321698
EP/K040723/1
EP/M028240/1
Subjects
Science & Technology
Technology
Physical Sciences
Computer Science, Artificial Intelligence
Computer Science, Software Engineering
Mathematics, Applied
Imaging Science & Photographic Technology
Computer Science
Mathematics
convex optimization
multilevel optimization
linear inverse problem
optimal gradient methods
face recognition
accelerated proximal gradient method
ROBUST FACE RECOGNITION
LINEAR INVERSE PROBLEMS
SPARSE REPRESENTATION
THRESHOLDING ALGORITHM
NONLINEAR OPTIMIZATION
COORDINATE DESCENT
MULTIGRID METHOD
SHRINKAGE
L(1)-MINIMIZATION
SELECTION
Artificial Intelligence & Image Processing
Publication Status
Published