ADMM for Training Sparse Structural SVMs with Augmented ℓ1 Regularizers
P. Balamurugan, Anusha Posinasetty, Shirish Shevade · 2016
Structural Support Vector Machine (Structural SVM) is a powerful tool for classification problems involving structured outputs. This paper proposes a fast Alternating Direction Method of Multipliers (ADMM) for structural SVM with augmented ℓ1 regularizers. The designed ADMM alternately solves a sequence of three problems, one of which uses a fast sequential dual optimization method [3] developed for training ℓ2 regularized structural SVM. The other two problems have easy-to-compute closed-form solutions. The algorithm is simple to implement and extensive empirical experiments show that the proposed ADMM is faster than several competing methods on a number of benchmark sequence labeling datasets. In addition to showing the convergence of the proposed ADMM, this paper is the first to prove the global non-asymptotic convergence of the sequential dual optimization method to solve a sub-problem of the ADMM algorithm.