Publications
1 results found
Hovhannisyan V, Parpas P, Zafeiriou S, 2016, MAGMA: Multi-level accelerated gradient mirror descent algorithm for large-scale convex composite minimization, SIAM Journal on Imaging Sciences, Vol: 9, Pages: 1829-1857, ISSN: 1936-4954
Composite convex optimization models arise in several applications, and are especially prevalentin inverse problems with a sparsity inducing norm and in general convex optimization with simpleconstraints. The most widely used algorithms for convex composite models are accelerated first ordermethods, however they can take a large number of iterations to compute an acceptable solution forlarge-scale problems. In this paper we propose to speed up first order methods by taking advantageof the structure present in many applications and in image processing in particular. Our method isbased on multi-level optimization methods and exploits the fact that many applications that giverise to large scale models can be modelled using varying degrees of fidelity. We use Nesterov’sacceleration techniques together with the multi-level approach to achieve an O(1/√ǫ) convergencerate, where ǫ denotes the desired accuracy. The proposed method has a better convergence ratethan any other existing multi-level method for convex problems, and in addition has the same rateas accelerated methods, which is known to be optimal for first-order methods. Moreover, as ournumerical experiments show, on large-scale face recognition problems our algorithm is several timesfaster than the state of the art.
This data is extracted from the Web of Science and reproduced under a licence from Thomson Reuters. You may not copy or re-distribute this data in whole or in part without the written consent of the Science business of Thomson Reuters.