Proximal Average Approximated Incremental Gradient Method for Composite Penalty Regularized Empirical Risk Minimization

Yiu-ming Cheung, Jian Lou
Asian Conference on Machine Learning, PMLR 45:205-220, 2016.

Abstract

Proximal average (PA) is an approximation technique proposed recently to handle nonsmooth composite regularizer in empirical risk minimization problem. For nonsmooth composite regularizer, it is often difficult to directly derive the corresponding proximal update when solving with popular proximal update. While traditional approaches resort to complex splitting methods like ADMM, proximal average provides an alternative, featuring the tractability of implementation and theoretical analysis. Nevertheless, compared to SDCA-ADMM and SAG-ADMM which are examples of ADMM-based methods achieving faster convergence rate and low per-iteration complexity, existing PA-based approaches either converge slowly (e.g. PA-ASGD) or suffer from high per-iteration cost (e.g. PA-APG). In this paper, we therefore propose a new PA-based algorithm called PA-SAGA, which is optimal in both convergence rate and per-iteration cost, by incorporating into incremental gradient-based framework.

Cite this Paper

BibTeX
@InProceedings{pmlr-v45-Cheung15, title = {Proximal Average Approximated Incremental Gradient Method for Composite Penalty Regularized Empirical Risk Minimization}, author = {Cheung, Yiu-ming and Lou, Jian}, booktitle = {Asian Conference on Machine Learning}, pages = {205--220}, year = {2016}, editor = {Holmes, Geoffrey and Liu, Tie-Yan}, volume = {45}, series = {Proceedings of Machine Learning Research}, address = {Hong Kong}, month = {20--22 Nov}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v45/Cheung15.pdf}, url = {https://proceedings.mlr.press/v45/Cheung15.html}, abstract = {Proximal average (PA) is an approximation technique proposed recently to handle nonsmooth composite regularizer in empirical risk minimization problem. For nonsmooth composite regularizer, it is often difficult to directly derive the corresponding proximal update when solving with popular proximal update. While traditional approaches resort to complex splitting methods like ADMM, proximal average provides an alternative, featuring the tractability of implementation and theoretical analysis. Nevertheless, compared to SDCA-ADMM and SAG-ADMM which are examples of ADMM-based methods achieving faster convergence rate and low per-iteration complexity, existing PA-based approaches either converge slowly (e.g. PA-ASGD) or suffer from high per-iteration cost (e.g. PA-APG). In this paper, we therefore propose a new PA-based algorithm called PA-SAGA, which is optimal in both convergence rate and per-iteration cost, by incorporating into incremental gradient-based framework. } }
Endnote
%0 Conference Paper %T Proximal Average Approximated Incremental Gradient Method for Composite Penalty Regularized Empirical Risk Minimization %A Yiu-ming Cheung %A Jian Lou %B Asian Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2016 %E Geoffrey Holmes %E Tie-Yan Liu %F pmlr-v45-Cheung15 %I PMLR %P 205--220 %U https://proceedings.mlr.press/v45/Cheung15.html %V 45 %X Proximal average (PA) is an approximation technique proposed recently to handle nonsmooth composite regularizer in empirical risk minimization problem. For nonsmooth composite regularizer, it is often difficult to directly derive the corresponding proximal update when solving with popular proximal update. While traditional approaches resort to complex splitting methods like ADMM, proximal average provides an alternative, featuring the tractability of implementation and theoretical analysis. Nevertheless, compared to SDCA-ADMM and SAG-ADMM which are examples of ADMM-based methods achieving faster convergence rate and low per-iteration complexity, existing PA-based approaches either converge slowly (e.g. PA-ASGD) or suffer from high per-iteration cost (e.g. PA-APG). In this paper, we therefore propose a new PA-based algorithm called PA-SAGA, which is optimal in both convergence rate and per-iteration cost, by incorporating into incremental gradient-based framework.
RIS
TY - CPAPER TI - Proximal Average Approximated Incremental Gradient Method for Composite Penalty Regularized Empirical Risk Minimization AU - Yiu-ming Cheung AU - Jian Lou BT - Asian Conference on Machine Learning DA - 2016/02/25 ED - Geoffrey Holmes ED - Tie-Yan Liu ID - pmlr-v45-Cheung15 PB - PMLR DP - Proceedings of Machine Learning Research VL - 45 SP - 205 EP - 220 L1 - http://proceedings.mlr.press/v45/Cheung15.pdf UR - https://proceedings.mlr.press/v45/Cheung15.html AB - Proximal average (PA) is an approximation technique proposed recently to handle nonsmooth composite regularizer in empirical risk minimization problem. For nonsmooth composite regularizer, it is often difficult to directly derive the corresponding proximal update when solving with popular proximal update. While traditional approaches resort to complex splitting methods like ADMM, proximal average provides an alternative, featuring the tractability of implementation and theoretical analysis. Nevertheless, compared to SDCA-ADMM and SAG-ADMM which are examples of ADMM-based methods achieving faster convergence rate and low per-iteration complexity, existing PA-based approaches either converge slowly (e.g. PA-ASGD) or suffer from high per-iteration cost (e.g. PA-APG). In this paper, we therefore propose a new PA-based algorithm called PA-SAGA, which is optimal in both convergence rate and per-iteration cost, by incorporating into incremental gradient-based framework. ER -
APA
Cheung, Y. & Lou, J.. (2016). Proximal Average Approximated Incremental Gradient Method for Composite Penalty Regularized Empirical Risk Minimization. Asian Conference on Machine Learning, in Proceedings of Machine Learning Research 45:205-220 Available from https://proceedings.mlr.press/v45/Cheung15.html.

Related Material