Non-convex optimization problems with multiple local optima are frequently encountered in machine learning. Graduated optimization algorithm (GOA) is a popular method for obtaining the global optima of non-convex problems by minimizing a sequence of locally strong convex functions that smooth the original non-convex problem with increasing approximation. Recently, GradOpt, a GOA-based algorithm, has demonstrated remarkable theoretical and experimental results. However, to optimize problems consisting of both convex and non-convex parts, GradOpt considers the entire objective function as a single non-convex function, leading to significant gaps between the smoothed and original functions. In this study, we propose two new algorithms: SVRG-GOA and PSVRG-GOA. They gradually smooth the non-convex part of the problem and then minimize the smoothed function using either the stochastic variance reduced gradient (SVRG) or proximal SVRG (Prox-SVRG) method. Both the algorithms are proven to have lower iteration complexity (O (1/ɛ)) than GradOpt (O (1/ɛ2)). Some tricks, such as larger shrinkage factor, projection step, stochastic gradient, and mini-batch skill are also applied to accelerate convergence of the proposed algorithms. Experimental results illustrate that two new algorithms with similar performance can converge to the "global" optima of a non-convex problem comparatively faster than GradOpt or non-convex Prox-SVRG.
Allen-ZhuZ. and HazanE., Variance reduction for faster nonconvex optimization, In Proceedings of The 33rd International Conference on Machine Learning, 2016, pp. 699–707.
2.
AmeliK., AlfiA. and AghaebrahimiM., A fuzzy discrete harmony search algorithm applied to annual cost reduction in radial distribution systems, Engineering Optimization48(9) (2016), 1529–1549.
3.
ArabA. and AlfiA., An adaptive gradient descent-based local search in memetic algorithm applied to optimal controller design, Information Sciences299 (2015), 117–142.
BlakeA. and ZissermanA., Visual reconstruction, MIT Press, 1987.
6.
ChangC.-C. and LinC.-J., LIBSVM: A library for Support Vector Machines, 2011.
7.
ChenL. and ZhouS., Sparse algorithm for robust LSSVM in primal space. Neurocomputing, (2017), 10.1016/j.neucom.2017.10.011
8.
DefazioA., BachF. and Lacoste-JulienS., SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives, In Advances in Neural Information Processing Systems, 2014, pp. 1646–1654.
9.
DonohoD.L., Compressed sensing, IEEE Transactions on Information Theory52(4) (2006), 1289–1306.
10.
DuchiJ.C., BartlettP.L. and WainwrightM.J., Randomized smoothing for stochastic optimization, SIAM Journal on Optimization22(2) (2012), 674–701.
11.
FengY., YangY., HuangX., MehrkanoonS. and SuykensJ.A., Robust support vector machines for classification with nonconvex and smooth losses, Neural Computation28(6) (2016), 1217–1247.
12.
GargH., Solving structural engineering design optimization problems using an artificial bee colony algorithm, Journal of Industrial and Management Optimization10(3) (2014), 777–794.
13.
GargH., A hybrid PSO-GA algorithm for constrained optimization problems, Applied Mathematics and Computation274 (2016), 292–305.
14.
GuyonI., Sido: A phamacology dataset, 2008.
15.
HazanE., LevyK.Y. and Shalev-ShwartzS., On graduated optimization for stochastic non-convex problems, In Proceedings of The 33rd International Conference on Machine Learning, 2016, pp. 1833–1841.
16.
IvazK. and BeiranvandA., Inexact steepest descent algorithm for obtaining t-best approximation in a fuzzy normed space, Journal of Intelligent & Fuzzy Systems30(5) (2016), 2999–3005.
17.
JohnsonR. and ZhangT., Accelerating stochastic gradient descent using predictive variance reduction, In Advances in Neural Information Processing Systems, 2013, pp. 315–323.
18.
KatsaggelosA.K., Digital image restoration, Springer Publishing Company, Incorporated, 2012.
19.
LaporteL., FlamaryR., CanuS., DéjeanS. and MotheJ., Nonconvex regularizations for feature selection in ranking with sparse svm, IEEE Transactions on Neural Networks and Learning Systems25(6) (2014), 1118–1130.
20.
LeiL. and MingD., Research of direction-of-arrival estimation in fewer snapshots based on niche artificial bee colony algorithm, Journal of Intelligent & Fuzzy Systems32(5) (2017), 3475–3485.
21.
LiH. and LinZ., Accelerated proximal gradient methods for nonconvex programming, In Advances in Neural Information Processing Systems, 2015, pp. 379–387.
22.
LiuD., ShiY., TianY. and HuangX., Ramp loss least squares support vector machine, Journal of Computational Science14 (2016), 61–68.
23.
MontavonG., BraunM.L. and MÃllerK.-R., Kernel analysis of deep networks, Journal of Machine Learning Research12(Sep) (2011), 2563–2581.
24.
NitandaA., Stochastic proximal gradient descent with acceleration techniques, In Advances in Neural Information Processing Systems, 2014, pp. 1574–1582.
25.
PahnehkolaeiS.M.A., AlfiA., SadollahA. and KimJ.H., Gradient-based water cycle algorithm with evaporation rate applied to chaos suppression, Applied Soft Computing53 (2017), 420–440.
26.
PanX. and XuY., Two effective sample selection methods for support vector machine, Journal of Intelligent & Fuzzy Systems30(2) (2016), 659–670.
27.
PowellM.J.D., Restart procedures for the conjugate gradient method, Mathematical Programming12(1) (1977), 241–254.
28.
RakhlinA., ShamirO. and SridharanK., Making gradient descent optimal for strongly convex stochastic optimization. arXiv preprint arXiv:1109.5647, 2011.
29.
ReddiS.J., HefnyA., SraS., PoczosB. and SmolaA., Stochastic variance reduction for nonconvex optimization, In Proceedings of The 33rd International Conference on Machine Learning, 2016, pp. 314–323.
30.
ReddiS.J., SraS., PoczosB. and SmolaA.J., Proximal stochastic methods for nonsmooth nonconvex finite-sum optimization, In Advances in Neural Information Processing Systems, 2016, pp. 1145–1153.
31.
SchmidtM., Le RouxN. and
BachF., Minimizing finite sums with the stochastic average gradient, Mathematical Programming162(1-2) (2017), 83–112.
32.
Shalev-ShwartzS. and Ben-DavidS., Understanding machine learning: From theory to algorithms, Cambridge University Press, 2014.
33.
Shalev-ShwartzS. and ZhangT., Stochastic dual coordinate ascent methods for regularized loss minimization, Journal of Machine Learning Research14(Feb) (2013), 567–599.
34.
Shalev-ShwartzS. and ZhangT., Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization, In ICML, 2014, pp. 64–72.
35.
SivaranjaniP. and SenthilA., Kumar, Hybrid particle swarm optimization-firefly algorithm (hpsoff) for combinatorial optimization of non-slicing vlsi floorplanning, Journal of Intelligent & Fuzzy Systems32(1) (2017), 661–669.
36.
WangK. and ZhongP., Robust non-convex Least Squares loss function for regression with outliers, Knowledge-Based Systems71 (2014), 290–302.
37.
WuY. and LiuY., Robust truncated hinge loss support vector machines, Journal of the American Statistical Association102(479) (2007), 974–983.
38.
XiaoL. and ZhangT., A proximal stochastic gradient method with progressive variance reduction, SIAM Journal on Optimization24(4) (2014), 2057–2075.
39.
YangX., TanL. and HeL., A robust Least Squares Support Vector Machines for regression and classification with noise, Neurocomputing140 (2014), 41–52.
40.
YuilleA.L. and RangarajanA., The concave-convex procedure, Neural Computation15(4) (2003), 915–936.
41.
ZhangT., Solving large scale linear prediction problems using stochastic gradient descent algorithms, In Proceedings of the Twenty-First International Conference on Machine Learning, 2004, p. 116. ACM.
