Super-Linear Convergence of Dual Augmented-Lagrangian Algorithm for Sparsity Regularized Estimation

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.

51 pages, 9 figures

References in corpus (6)

• The Augmented Lagrange Multiplier Method for Exact Recovery of Corrupted Low-Rank Matrices
• Estimation of low-rank tensors via convex optimization
• A Singular Value Thresholding Algorithm for Matrix Completion
• Modeling sparse connectivity between underlying brain sources for EEG/MEG
• Dual Augmented Lagrangian Method for Efficient Sparse Reconstruction
• Regularization Strategies and Empirical Bayesian Learning for MKL

Cited by in corpus (7)

• Cell Detection in Microscopy Images with Deep Convolutional Neural Network and Compressed Sensing
• FAStEN: An Efficient Adaptive Method for Feature Selection and Estimation in High-Dimensional Functional Regressions
• Crowd Scene Analysis by Output Encoding
• A trust region-type normal map-based semismooth Newton method for nonsmooth nonconvex composite optimization
• Learning a Common Substructure of Multiple Graphical Gaussian Models
• Training Convolutional Neural Networks and Compressed Sensing End-to-End for Microscopy Cell Detection
• Theoretical and Experimental Analyses of Tensor-Based Regression and Classification