小批量随机块坐标下降算法

doi:10.15960/j.cnki.issn.1007-6093.2022.01.001

Abstract

Abstract:

We study the mini-batch stochastic block coordinate descent algorithm (mSBD) for a class of problems, i.e., structured stochastic optimization problems (where "structured" means that feasible region of the problem has a block structure and the nonsmooth regularized part of the objective function is separable across the variable blocks), widely used in machine learning. We give the basic mSBD and its variant according to solving non-composite and composite problems respectively. For the noncomposite problem, we analyze the convergence properties of the algorithm without the assumption of uniformly bounded gradient variance. For the composite problem, we obtain the convergence of the algorithm without the usual Lipschitz gradient continuity assumption. Finally, we verify the effectiveness of mSBD by numerical experiments.

Key words: block coordinate descent, stochastic approximation, stochastic (composite) optimization, Hölder continuity, nonsmooth, nonconvex optimization

CLC Number:

O221.2

Jia HU, Tiande GUO, Congying HAN. Mini-batch stochastic block coordinate descent algorithm[J]. Operations Research Transactions, 2022, 26(1): 1-22.

Figures/Tables 3

References 38

1	Tibshirani R . Regression shrinkage and selection via the lasso[J]. Journal of the Royal Statistical Society: Series B (Methodological), 1996, 58 (1): 267- 288. doi: 10.1111/j.2517-6161.1996.tb02080.x
2	Shevade S K , Keerthi S S . A simple and efficient algorithm for gene selection using sparse logistic regression[J]. Bioinformatics, 2003, 19 (17): 2246- 2253. doi: 10.1093/bioinformatics/btg308
3	Sra S , Nowozin S , Wright S J . Optimization for Machine Learning[M]. Cambridge: MIT Press, 2012.
4	Bottou L , Curtis F E , Nocedal J . Optimization methods for large-scale machine learning[J]. SIAM Review, 2018, 60 (2): 223- 311. doi: 10.1137/16M1080173
5	Zeng J, Lau T T K, Lin S, et al. Global convergence of block coordinate descent in deep learning[C]//International Conference on Machine Learning, 2019: 7313-7323.
6	Li J, Fang C, Lin Z. Lifted proximal operator machines[C]//Proceedings of the AAAI Conference on Artificial Intelligence, 2019: 4181-4188.
7	Luo Z Q , Tseng P . Error bound and convergence analysis of matrix splitting algorithms for the affine variational inequality problem[J]. SIAM Journal on Optimization, 1992, 2 (1): 43- 54. doi: 10.1137/0802004
8	Tseng P , Yun S . A coordinate gradient descent method for nonsmooth separable minimization[J]. Mathematical Programming, 2009, 117 (1): 387- 423.
9	Wright S J . Accelerated block-coordinate relaxation for regularized optimization[J]. SIAM Journal on Optimization, 2012, 22 (1): 159- 186. doi: 10.1137/100808563
10	Beck A , Tetruashvili L . On the convergence of block coordinate descent type methods[J]. SIAM Journal on Optimization, 2013, 23 (4): 2037- 2060. doi: 10.1137/120887679
11	Leventhal D , Lewis A S . Randomized methods for linear constraints: convergence rates and conditioning[J]. Mathematics of Operations Research, 2010, 35 (3): 641- 654. doi: 10.1287/moor.1100.0456
12	Nesterov Y . Efficiency of coordinate descent methods on huge-scale optimization problems[J]. SIAM Journal on Optimization, 2012, 22 (2): 341- 362. doi: 10.1137/100802001
13	Richtárik P , Takáč M . Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function[J]. Mathematical Programming, 2014, 144 (1): 1- 38.
14	Shalev-Shwartz S , Tewari A . Stochastic methods for $ \ell$₁-regularized loss minimization[J]. The Journal of Machine Learning Research, 2011, 12, 1865- 1892.
15	Kurdyka K. On gradients of functions definable in o-minimal structures[J]//Annales de l'institut Fourier. 1998, 48(3): 769-783.
16	Łojasiewicz S . Une propriété topologique des sous-ensembles analytiques réels[J]. Les équations aux dérivées partielles, 1963, 117, 87- 89.
17	Xu Y , Yin W . A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion[J]. SIAM Journal on Imaging Sciences, 2013, 6 (3): 1758- 1789. doi: 10.1137/120887795
18	Xu Y , Yin W . A globally convergent algorithm for nonconvex optimization based on block coordinate update[J]. Journal of Scientific Computing, 2017, 72 (2): 700- 734. doi: 10.1007/s10915-017-0376-0
19	Kleywegt A J , Shapiro A , Homem-de-Mello T . The sample average approximation method for stochastic discrete optimization[J]. SIAM Journal on Optimization, 2002, 12 (2): 479- 502. doi: 10.1137/S1052623499363220
20	Robbins H , Monro S . A stochastic approximation method[J]. The Annals of Mathematical Statistics, 1951, 22, 400- 407. doi: 10.1214/aoms/1177729586
21	Ghadimi S , Lan G . Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization I: A generic algorithmic framework[J]. SIAM Journal on Optimization, 2012, 22 (4): 1469- 1492. doi: 10.1137/110848864
22	Ghadimi S , Lan G . Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization II: Shrinking procedures and optimal algorithms[J]. SIAM Journal on Optimization, 2013, 23 (4): 2061- 2089. doi: 10.1137/110848876
23	Ghadimi S , Lan G . Stochastic first-and zeroth-order methods for nonconvex stochastic programming[J]. SIAM Journal on Optimization, 2013, 23 (4): 2341- 2368. doi: 10.1137/120880811
24	Ghadimi S , Lan G , Zhang H . Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization[J]. Mathematical Programming, 2016, 155 (1-2): 267- 305. doi: 10.1007/s10107-014-0846-1
25	Lan G . An optimal method for stochastic composite optimization[J]. Mathematical Programming, 2012, 133 (1): 365- 397.
26	Nedic A , Lee S . On stochastic subgradient mirror-descent algorithm with weighted averaging[J]. SIAM Journal on Optimization, 2014, 24 (1): 84- 107. doi: 10.1137/120894464
27	Nemirovski A , Juditsky A , Lan G , et al. Robust stochastic approximation approach to stochastic programming[J]. SIAM Journal on Optimization, 2009, 19 (4): 1574- 1609. doi: 10.1137/070704277
28	Xu Y , Yin W . Block stochastic gradient iteration for convex and nonconvex optimization[J]. SIAM Journal on Optimization, 2015, 25 (3): 1686- 1716. doi: 10.1137/140983938
29	Dang C D , Lan G . Stochastic block mirror descent methods for nonsmooth and stochastic optimization[J]. SIAM Journal on Optimization, 2015, 25 (2): 856- 881. doi: 10.1137/130936361
30	Zhao T, Yu M, Wang Y, et al. Accelerated mini-batch randomized block coordinate descent method[C]//Advances in Neural Information Processing Systems, 2014: 3329-3337.
31	Johnson R, Zhang T. Accelerating stochastic gradient descent using predictive variance reduction[C]//Advances in Neural Information Processing Systems, 2013: 315-323.
32	Nesterov Y . Introductory Lectures on Convex Optimization: A Basic Course[M]. New York: Springer Science & Business Media, 2003.
33	Lei Y , Hu T , Li G , et al. Stochastic gradient descent for nonconvex learning without bounded gradient assumptions[J]. IEEE Transactions on Neural Networks and Learning Systems, 2019, 31 (10): 4394- 4400.
34	Ying Y , Zhou D X . Unregularized online learning algorithms with general loss functions[J]. Applied and Computational Harmonic Analysis, 2017, 42 (2): 224- 244. doi: 10.1016/j.acha.2015.08.007
35	Rockafellar R T . Convex Analysis[M]. Princeton: Princeton university press, 2015.
36	Grimmer B . Convergence rates for deterministic and stochastic subgradient methods without Lipschitz continuity[J]. SIAM Journal on Optimization, 2019, 29 (2): 1350- 1365. doi: 10.1137/18M117306X
37	Robbins H, Siegmund D. A convergence theorem for non negative almost supermartingales and some applications[M]//Optimizing Methods in Statistics. Pittsburgh: Academic Press, 1971: 233-257.
38	Beck A , Teboulle M . A fast iterative shrinkage-thresholding algorithm for linear inverse problems[J]. SIAM Journal on Imaging Sciences, 2009, 2 (1): 183- 202. doi: 10.1137/080716542

名称	样本数	维数
E2006-tfidf	16087	150360

[1]	XU Zi, ZHANG Huiling. Optimization algorithms and their complexity analysis for non-convex minimax problems [J]. Operations Research Transactions, 2021, 25(3): 74-86.
[2]	Hongwu LI, Min XIE, Rong ZHANG. A proximal gradient method for nonsmooth convex optimization problems [J]. Operations Research Transactions, 2021, 25(1): 61-72.
[3]	MIAO Xiaonan, GU Jian, XIAO Xiantao. A cubic regularization method for solving nonsmooth equations [J]. Operations Research Transactions, 2019, 23(2): 17-30.
[4]	JIAN Jinbao, LAO Yixian, CHAO Miantao, MA Guodong. ADMM-SQP algorithm for two blocks linear constrained nonconvex optimization [J]. Operations Research Transactions, 2018, 22(2): 79-92.
[5]	LIANG Na, DU Shouqiang. Nonsmooth Newton method for solving symmetrical tensor absolute value equations [J]. Operations Research Transactions, 2017, 21(3): 95-102.
[6]	CHEN Yuanyuan, GAO Yan, LIU Zhimin, DU Shouqiang. The smoothing gradient method for a kind of special optimization problem [J]. Operations Research Transactions, 2017, 21(2): 119-125.
[7]	ZHANG Yong, YE Wanzhou. An algorithm for elastic l_2-l_q regularization [J]. Operations Research Transactions, 2016, 20(4): 11-20.
[8]	ZHANG Qingye, GAO Yan. A hybrid bundle method for nonsmooth convex optimization [J]. Operations Research Transactions, 2016, 20(2): 113-120.
[9]	HAN Yanli, GAO Yan. Determining the discriminating domain for linear differential games based on viability theory [J]. Operations Research Transactions, 2016, 20(1): 105-111.
[10]	LI Lihua, GAO Yan, WANG Gexia. Non-smooth optimality conditions for a class of dynamic systems with variable structure [J]. Operations Research Transactions, 2013, 17(3): 65-72.
[11]	ZHAO Kequan, YANG Xinmin. Characterizations of the solution set for a class of nonsmooth optimization problems [J]. Operations Research Transactions, 2012, 16(3): 109-118.
[12]	GAO Yan. A Newton Method for a Nonsmooth Nonlinear　Complementarity　Problem [J]. Operations Research Transactions, 2011, 15(2): 53-58.

Mini-batch stochastic block coordinate descent algorithm

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 3

References 38

Related Articles 12

Recommended Articles

Metrics

Comments