MAGMA: multilevel accelerated gradient mirror descent algorithm for large-scale convex composite minimization
From MaRDI portal
Publication:3179624
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.
Recommendations
- A multilevel proximal gradient algorithm for a class of composite optimization problems
- Fast first-order methods for minimizing convex composite functions
- Gradient methods for minimizing composite functions
- Accelerated first-order methods for large-scale convex optimization: nearly optimal complexity under strong convexity
- Accelerated first-order primal-dual proximal methods for linearly constrained composite convex programming
Cites work
- scientific article; zbMATH DE number 1818892 (Why is no real title available?)
- scientific article; zbMATH DE number 3850830 (Why is no real title available?)
- scientific article; zbMATH DE number 3790208 (Why is no real title available?)
- scientific article; zbMATH DE number 845714 (Why is no real title available?)
- scientific article; zbMATH DE number 936298 (Why is no real title available?)
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- A Line Search Multigrid Method for Large-Scale Nonlinear Optimization
- A Multigrid Tutorial, Second Edition
- A multigrid approach to discretized optimization problems
- A multigrid method for nonconforming FE-discretisations with application to non-matching grids
- A proximal stochastic gradient method with progressive variance reduction
- Accelerated, parallel, and proximal coordinate descent
- An EM algorithm for wavelet-based image restoration
- An accelerated randomized proximal coordinate gradient method and its application to regularized empirical risk minimization
- An iterative thresholding algorithm for linear inverse problems with a sparsity constraint
- Compressed sensing
- Compressive sampling
- Dense Error Correction Via $\ell^1$-Minimization
- Exact matrix completion via convex optimization
- Fast Gradient-Based Algorithms for Constrained Total Variation Image Denoising and Deblurring Problems
- Gradient methods for minimizing composite functions
- Image Super-Resolution Via Sparse Representation
- Introductory lectures on convex optimization. A basic course.
- Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
- Linear coupling: an ultimate unification of gradient and mirror descent
- Multigrid Methods for PDE Optimization
- Nonlinear wavelet image processing: variational problems, compression, and noise removal through wavelet shrinkage
- On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems
- On the convergence of block coordinate descent type methods
- Primal-dual subgradient methods for convex problems
- Recursive Trust-Region Methods for Multiscale Nonlinear Optimization
- Robust principal component analysis?
- Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
- Smooth minimization of non-smooth functions
- Smoothing and first order methods: a unified framework
- Sparse and redundant representations. From theory to applications in signal and image processing.
Cited in
(10)- Inexact proximal stochastic gradient method for convex composite optimization
- A multilevel method for self-concordant minimization
- Newton-type multilevel optimization method
- An inexact gradient mirror descent algorithm for non-smooth convex optimization
- A multilevel proximal gradient algorithm for a class of composite optimization problems
- Stochastic incremental mirror descent algorithms with Nesterov smoothing
- Distributed constrained optimization with periodic dynamic quantization
- A multigrid approach to SDP relaxations of sparse polynomial optimization problems
- Numerical optimal control of a size-structured PDE model for metastatic cancer treatment
- IML FISTA: a multilevel framework for inexact and inertial forward-backward. Application to image restoration
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)
