MAGMA: Multilevel Accelerated Gradient Mirror Descent Algorithm for Large-Scale Convex Composite Minimization
From MaRDI portal
Publication:3179624
DOI10.1137/15M104013XzbMATH Open1358.90097arXiv1509.05715MaRDI QIDQ3179624FDOQ3179624
Vahan Hovhannisyan, Panos Parpas, Stefanos P. Zafeiriou
Publication date: 19 December 2016
Published in: SIAM Journal on Imaging Sciences (Search for Journal in Brave)
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 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.
Full work available at URL: https://arxiv.org/abs/1509.05715
convex optimizationlinear inverse problemface recognitionmultilevel optimizationaccelerated proximal gradient methodoptimal gradient methods
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- Smooth minimization of non-smooth functions
- Introductory lectures on convex optimization. A basic course.
- Robust principal component analysis?
- Gradient methods for minimizing composite functions
- Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent
- Exact matrix completion via convex optimization
- Primal-dual subgradient methods for convex problems
- Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
- Dense Error Correction Via $\ell^1$-Minimization
- Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
- Sparse and Redundant Representations
- Fast Gradient-Based Algorithms for Constrained Total Variation Image Denoising and Deblurring Problems
- Compressed sensing
- An EM algorithm for wavelet-based image restoration
- An iterative thresholding algorithm for linear inverse problems with a sparsity constraint
- Accelerated, Parallel, and Proximal Coordinate Descent
- Recursive Trust-Region Methods for Multiscale Nonlinear Optimization
- Multigrid Methods for PDE Optimization
- A multigrid approach to discretized optimization problems
- Nonlinear wavelet image processing: variational problems, compression, and noise removal through wavelet shrinkage
- A Multigrid Tutorial, Second Edition
- A Proximal Stochastic Gradient Method with Progressive Variance Reduction
- Image Super-Resolution Via Sparse Representation
- On the Convergence of Block Coordinate Descent Type Methods
- Smoothing and first order methods: a unified framework
- A Line Search Multigrid Method for Large-Scale Nonlinear Optimization
- On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems
- A multigrid method for nonconforming FE-discretisations with application to non-matching grids
- An Accelerated Randomized Proximal Coordinate Gradient Method and its Application to Regularized Empirical Risk Minimization
Cited In (10)
- Stochastic incremental mirror descent algorithms with Nesterov smoothing
- IML FISTA: a multilevel framework for inexact and inertial forward-backward. Application to image restoration
- Title not available (Why is that?)
- Numerical optimal control of a size-structured PDE model for metastatic cancer treatment
- Inexact proximal stochastic gradient method for convex composite optimization
- Newton-type multilevel optimization method
- A Multigrid Approach to SDP Relaxations of Sparse Polynomial Optimization Problems
- A multilevel method for self-concordant minimization
- Distributed constrained optimization with periodic dynamic quantization
- A Multilevel Proximal Gradient Algorithm for a Class of Composite Optimization Problems
Uses Software
This page was built for publication: MAGMA: Multilevel Accelerated Gradient Mirror Descent Algorithm for Large-Scale Convex Composite Minimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3179624)
