Dual Averaging and Proximal Gradient Descent for Online Alternating Direction Multiplier Method

Taiji Suzuki
Proceedings of the 30th International Conference on Machine Learning, PMLR 28(1):392-400, 2013.

Abstract

We develop new stochastic optimization methods that are applicable to a wide range of structured regularizations. Basically our methods are combinations of basic stochastic optimization techniques and Alternating Direction Multiplier Method (ADMM). ADMM is a general framework for optimizing a composite function, and has a wide range of applications. We propose two types of online variants of ADMM, which correspond to online proximal gradient descent and regularized dual averaging respectively. The proposed algorithms are computationally efficient and easy to implement. Our methods yield O(1/\sqrtT) convergence of the expected risk. Moreover, the online proximal gradient descent type method yields O(\log(T)/T) convergence for a strongly convex loss. Numerical experiments show effectiveness of our methods in learning tasks with structured sparsity such as overlapped group lasso.

Cite this Paper

BibTeX
@InProceedings{pmlr-v28-suzuki13, title = {Dual Averaging and Proximal Gradient Descent for Online Alternating Direction Multiplier Method}, author = {Suzuki, Taiji}, booktitle = {Proceedings of the 30th International Conference on Machine Learning}, pages = {392--400}, year = {2013}, editor = {Dasgupta, Sanjoy and McAllester, David}, volume = {28}, number = {1}, series = {Proceedings of Machine Learning Research}, address = {Atlanta, Georgia, USA}, month = {17--19 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v28/suzuki13.pdf}, url = {https://proceedings.mlr.press/v28/suzuki13.html}, abstract = {We develop new stochastic optimization methods that are applicable to a wide range of structured regularizations. Basically our methods are combinations of basic stochastic optimization techniques and Alternating Direction Multiplier Method (ADMM). ADMM is a general framework for optimizing a composite function, and has a wide range of applications. We propose two types of online variants of ADMM, which correspond to online proximal gradient descent and regularized dual averaging respectively. The proposed algorithms are computationally efficient and easy to implement. Our methods yield O(1/\sqrtT) convergence of the expected risk. Moreover, the online proximal gradient descent type method yields O(\log(T)/T) convergence for a strongly convex loss. Numerical experiments show effectiveness of our methods in learning tasks with structured sparsity such as overlapped group lasso.} }
Endnote
%0 Conference Paper %T Dual Averaging and Proximal Gradient Descent for Online Alternating Direction Multiplier Method %A Taiji Suzuki %B Proceedings of the 30th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2013 %E Sanjoy Dasgupta %E David McAllester %F pmlr-v28-suzuki13 %I PMLR %P 392--400 %U https://proceedings.mlr.press/v28/suzuki13.html %V 28 %N 1 %X We develop new stochastic optimization methods that are applicable to a wide range of structured regularizations. Basically our methods are combinations of basic stochastic optimization techniques and Alternating Direction Multiplier Method (ADMM). ADMM is a general framework for optimizing a composite function, and has a wide range of applications. We propose two types of online variants of ADMM, which correspond to online proximal gradient descent and regularized dual averaging respectively. The proposed algorithms are computationally efficient and easy to implement. Our methods yield O(1/\sqrtT) convergence of the expected risk. Moreover, the online proximal gradient descent type method yields O(\log(T)/T) convergence for a strongly convex loss. Numerical experiments show effectiveness of our methods in learning tasks with structured sparsity such as overlapped group lasso.
RIS
TY - CPAPER TI - Dual Averaging and Proximal Gradient Descent for Online Alternating Direction Multiplier Method AU - Taiji Suzuki BT - Proceedings of the 30th International Conference on Machine Learning DA - 2013/02/13 ED - Sanjoy Dasgupta ED - David McAllester ID - pmlr-v28-suzuki13 PB - PMLR DP - Proceedings of Machine Learning Research VL - 28 IS - 1 SP - 392 EP - 400 L1 - http://proceedings.mlr.press/v28/suzuki13.pdf UR - https://proceedings.mlr.press/v28/suzuki13.html AB - We develop new stochastic optimization methods that are applicable to a wide range of structured regularizations. Basically our methods are combinations of basic stochastic optimization techniques and Alternating Direction Multiplier Method (ADMM). ADMM is a general framework for optimizing a composite function, and has a wide range of applications. We propose two types of online variants of ADMM, which correspond to online proximal gradient descent and regularized dual averaging respectively. The proposed algorithms are computationally efficient and easy to implement. Our methods yield O(1/\sqrtT) convergence of the expected risk. Moreover, the online proximal gradient descent type method yields O(\log(T)/T) convergence for a strongly convex loss. Numerical experiments show effectiveness of our methods in learning tasks with structured sparsity such as overlapped group lasso. ER -
APA
Suzuki, T.. (2013). Dual Averaging and Proximal Gradient Descent for Online Alternating Direction Multiplier Method. Proceedings of the 30th International Conference on Machine Learning, in Proceedings of Machine Learning Research 28(1):392-400 Available from https://proceedings.mlr.press/v28/suzuki13.html.

Related Material