Super-Linear Convergence of Dual Augmented-Lagrangian Algorithm for Sparsity Regularized Estimation
Preprint
Abstract
We analyze the convergence behaviour of a recently proposed algorithm for regularized estimation called Dual Augmented Lagrangian (DAL). Our analysis is based on a new interpretation of DAL as a proximal minimization algorithm. We theoretically show under some conditions that DAL converges super-linearly in a non-asymptotic and global sense. Due to a special modelling of sparse estimation problems in the context of machine learning, the assumptions we make are milder and more natural than those made in conventional analysis of augmented Lagrangian algorithms. In addition, the new interpretation enables us to generalize DAL to wide varieties of sparse estimation problems. We experimentally confirm our analysis in a large scale $\ell_1$-regularized logistic regression problem and extensively compare the efficiency of DAL algorithm to previously proposed algorithms on both synthetic and benchmark datasets.Keywords
All Related Versions
This publication has 24 references indexed in Scilit:
- Gradient methods for minimizing composite functionsMathematical Programming, 2012
- Dual Augmented Lagrangian Method for Efficient Sparse ReconstructionIEEE Signal Processing Letters, 2009
- Gradient Projection for Sparse Reconstruction: Application to Compressed Sensing and Other Inverse ProblemsIEEE Journal of Selected Topics in Signal Processing, 2007
- An Interior-Point Method for Large-Scale -Regularized Least SquaresIEEE Journal of Selected Topics in Signal Processing, 2007
- Majorization–Minimization Algorithms for Wavelet-Based Image RestorationIEEE Transactions on Image Processing, 2007
- Bayesian wavelet-based image deconvolution: a GEM algorithm exploiting a class of heavy-tailed priorsIEEE Transactions on Image Processing, 2006
- An iterative thresholding algorithm for linear inverse problems with a sparsity constraintCommunications on Pure and Applied Mathematics, 2004
- An EM algorithm for wavelet-based image restorationIEEE Transactions on Image Processing, 2003
- Sparse signal reconstruction from limited data using FOCUSS: a re-weighted minimum norm algorithmIEEE Transactions on Signal Processing, 1997
- Constrained Optimization and Lagrange Multiplier Methods1982