Stochastic extra-gradient based alternating direction methods for graph-guided regularized minimization

Qiang LAN; Lin-bo QIAO; Yi-jie WANG

doi:10.1631/FITEE.1601771

Your Location：

Home >

Browse articles >

Stochastic extra-gradient based alternating direction methods for graph-guided regularized minimization

Regular Papers | Updated：2022-05-19

- Stochastic extra-gradient based alternating direction methods for graph-guided regularized minimization
- 图引导正则最小化的随机超梯度的交替方向方法
- Frontiers of Information Technology & Electronic Engineering Vol. 19, Issue 6, Pages: 755-762(2018)
- Affiliations：
  
  College of Computer, National University of Defense Technology, Changsha 410073, China
  National Laboratory for Parallel and Distributed Processing, National University of Defense Technology, Changsha 410073, China
- Author bio：
  
  [ "Qiang LAN, E-mail: lanqiang_nudt@163.com" ]
  Lin-bo QIAO, E-mail: qiao.linbo@nudt.edu.cn
  [ "Yi-jie WANG, E-mail: wwyyjj1971@vip.sina.com" ]
- Funds：
- DOI：10.1631/FITEE.1601771
  CLC： TP311
- Received：03 December 2016，
  
  Revised：2018-;6-;7，
  
  Published：2018-06
- Accepted：
Scan QR Code
Qiang LAN, Lin-bo QIAO, Yi-jie WANG. Stochastic extra-gradient based alternating direction methods for graph-guided regularized minimization[J]. Frontiers of Information Technology & Electronic Engineering, 2018, 19(6): 755-762.
DOI：

Qiang LAN, Lin-bo QIAO, Yi-jie WANG. Stochastic extra-gradient based alternating direction methods for graph-guided regularized minimization[J]. Frontiers of Information Technology & Electronic Engineering, 2018, 19(6): 755-762. DOI： 10.1631/FITEE.1601771.

摘要

提出并比较额外梯度交替方向的几种随机变体方法，称为带拉格朗日函数（SEGL）的随机超梯度交替方向法和带增广拉格朗日函数（SEGAL）的随机超梯度交替方向法。这些方法由两个大规模凸目标函数组成，可最小化图形引导的优化问题。机器学习中一些重要应用遵循图导引优化公式等作为线性回归、逻辑回归、Lasso结构化扩展以及结构化正则化逻辑回归的原则。通过融合逻辑回归和图形引导正则化回归，在几类数据集上进行了试验。试验结果表明所提算法优于其他竞争算法，且在实际应用中，SEGAL比SEGL性能更好。

Abstract

In this study

we propose and compare stochastic variants of the extra-gradient alternating direction method

named the stochastic extra-gradient alternating direction method with Lagrangian function (SEGL) and the stochastic extra-gradient alternating direction method with augmented Lagrangian function (SEGAL)

to minimize the graph-guided optimization problems

which are composited with two convex objective functions in large scale. A number of important applications in machine learning follow the graph-guided optimization formulation

such as linear regression

logistic regression

Lasso

structured extensions of Lasso

and structured regularized logistic regression. We conduct experiments on fused logistic regression and graph-guided regularized regression. Experimental results on several genres of datasets demonstrate that the proposed algorithm outperforms other competing algorithms

and SEGAL has better performance than SEGL in practical use.

关键词

Keywords

references

S Azadi , , , S Sra . . Towards an optimal stochastic alternating direction method of multipliers . . Int Conf on Machine Learning , , 2014 . . p.620 - - 628 . . . .

S Boyd , , , N Parikh , , , E Chu , , , 等 . . Distributed optimization and statistical learning via the alternating direction method of multipliers . . Found Trends Mach Learn , , 2011 . . 3 ( ( 1 ): ): 1 - - 122 . . DOI: 10.1561/2200000016 http://doi.org/10.1561/2200000016 . .

C Cortes , , , V Vapnik . . Support-vector networks . . Mach Learn , , 1995 . . 20 ( ( 3 ): ): 273 - - 297 . . DOI: 10.1023/A:1022627411411 http://doi.org/10.1023/A:1022627411411 . .

X Gao , , , B Jiang , , , S Zhang . . On the information-adaptive variants of the ADMM: an iteration complexity perspective . . J Sci Comput , , 2017 . . 76 ( ( 1 ): ): 327 - - 363 . . DOI: 10.1007/s10915-017-0621-6 http://doi.org/10.1007/s10915-017-0621-6 . .

T Hastie , , , R Tibshirani , , , J Friedman . . The Elements of Statistical Learning: Data Mining, Inference, and Prediction . . Springer-Verlag, New York, USA , , 2001 . . .

CJ Hsieh , , , MA Sustik , , , IS Dhillon , , , 等 . . BIG & QUIC: sparse inverse covariance estimation for a million variables . . Advances in Neural Information Processing Systems , , 2013 . . p.3165 - - 3173 . . . .

R Johnson , , , T Zhang . . Accelerating stochastic gradient descent using predictive variance reduction . . Advances in Neural Information Processing Systems , , 2013 . . p.315 - - 323 . . . .

T Lin , , , S Ma , , , S Zhang . . An extra-gradient-based alternating direction method for convex minimization . . Found Comput Math , , 2015 . . 17 ( ( 1 ): ): 35 - - 59 . . DOI: 10.1007/s10208-015-9282-8 http://doi.org/10.1007/s10208-015-9282-8 . .

T Lin , , , L Qiao , , , T Zhang , , , 等 . . Stochastic primaldual proximal extra-gradient descent for compositely regularized optimization . . Neurocomputing , , 2018 . . 273 516 - - 525 . . DOI: 10.1016/j.neucom.2017.07.066 http://doi.org/10.1016/j.neucom.2017.07.066 . .

H Ouyang , , , N He , , , L Tran , , , 等 . . Stochastic alternating direction method of multipliers . . Int Conf on Machine Learning , , 2013 . . p.80 - - 88 . . . .

LB Qiao , , , BF Zhang , , , JS Su , , , 等 . . A systematic review of structured sparse learning . . Front Inform Technol Electron Eng , , 2017 . . 18 ( ( 4 ): ): 445 - - 463 . . DOI: 10.1631/FITEE.1601489 http://doi.org/10.1631/FITEE.1601489 . .

T Suzuki . . Dual averaging and proximal gradient descent for online alternating direction multiplier method . . Int Conf on Machine Learning , , 2013 . . p.392 - - 400 . . . .

R Tibshirani . . Regression shrinkage and selection via the Lasso . . J R Stat Soc Ser B , , 1996 . . 1 267 - - 288 . . . .

R Tibshirani , , , M Saunders , , , S Rosset , , , 等 . . Sparsity and smoothness via the fused Lasso . . J R Stat Soc Ser B , , 2005 . . 67 91 - - 108 . . DOI: 10.1111/j.1467-9868.2005.00490.x http://doi.org/10.1111/j.1467-9868.2005.00490.x . .

H Wang , , , A Banerjee . . Online alternating direction method (longer version) . . arXiv Preprint, 1306.3721 , , . .

JF Yang , , , XM Yuan . . Linearized augmented Lagrangian and alternating direction methods for nuclear norm minimization . . Math Comput , , 2013 . . 82 ( ( 281 ): ): 301 - - 329 . . DOI: 10.1090/S0025-5718-2012-02598-1 http://doi.org/10.1090/S0025-5718-2012-02598-1 . .

P Zhao , , , J Yang , , , T Zhang , , , 等 . . Adaptive stochastic alternating direction method of multipliers . . Int Conf on Machine Learning , , 2015 . . p.69 - - 77 . . . .

W Zhong , , , JT Kwok . . Fast stochastic alternating direction method of multipliers . . Int Conf on Machine Learning , , 2013 . . p.46 - - 54 . . . .

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

Matrix-valued distributed stochastic optimization with constraints

Related Author

Zicong XIA

Yang LIU

Wenlian LU

Weihua GUI

Related Institution

Key Laboratory of Intelligent Education Technology and Application of Zhejiang Province, Zhejiang Normal University

School of Mathematical Sciences, Zhejiang Normal University

School of Mathematical Sciences, Fudan University

School of Automation, Central South University

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰