×

zbMATH — the first resource for mathematics

A stochastic trust region method for unconstrained optimization problems. (English) Zbl 1435.90094
Summary: In this paper, a stochastic trust region method is proposed to solve unconstrained minimization problems with stochastic objectives. Particularly, this method can be used to deal with nonconvex problems. At each iteration, we construct a quadratic model of the objective function. In the model, stochastic gradient is used to take the place of deterministic gradient for both the determination of descent directions and the approximation of the Hessians of the objective function. The behavior and the convergence properties of the proposed method are discussed under some reasonable conditions. Some preliminary numerical results show that our method is potentially efficient.
MSC:
90C15 Stochastic programming
90C26 Nonconvex programming, global optimization
90C55 Methods of successive quadratic programming type
65K05 Numerical mathematical programming methods
Software:
Pegasos
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Mokhtari, A.; Ribeiro, A., A quasi-Newton method for large scale support vector machines, Proceedings of the International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2014
[2] Bottou, L.; Le Cun, Y., On-line learning for very large data sets, Applied Stochastic Models in Business and Industry, 21, 2, 137-151 (2005) · Zbl 1091.68063
[3] Bottou, L., Large-scale machine learning with stochastic gradient descent, Proceedings of the COMPSTAT’2010, Physica-Verlag/Springer
[4] Mokhtari, A.; Ribeiro, A., A dual stochastic DFP algorithm for optimal resource allocation in wireless systems, Proceedings of the 14th Workshop on Signal Processing Advances in Wireless Communications (SPAWC 2013)
[5] Ribeiro, A., Ergodic stochastic optimization algorithms for wireless communication and networking, IEEE Transactions on Signal Processing, 58, 12, 6369-6386 (2010) · Zbl 1392.94424
[6] Nemirovski, A.; Juditsky, A.; Lan, G.; Shapiro, A., Robust stochastic approximation approach to stochastic programming, SIAM Journal on Optimization, 19, 4, 1574-1609 (2009) · Zbl 1189.90109
[7] Shalev-Shwartz, S.; Srebro, N., SVM optimization: Inverse dependence on training set size, Proceedings of the 25th International Conference on Machine Learning
[8] Shalev-Shwartz, S.; Singer, Y.; Srebro, N., Pegasos: primal estimated sub-gradient solver for svm, Proceedings of the 24th International Conference on Machine Learning (ICML ’07)
[9] Zhang, T., Solving large scale linear prediction problems using stochastic gradient descent algorithms, Proceedings of the twenty-first international conference on Machine learning
[10] Schmidt, M.; Le Roux, N.; Bach, F., Minimizing finite sums with the stochastic average gradient, Mathematical Programming, 162, 5, 1-30 (2017) · Zbl 1358.90073
[11] Konecny, J.; Liu, J.; Richtarik, P.; Takac, M., Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting, IEEE Journal of Selected Topics in Signal Processing, 10, 2, 242-255 (2016)
[12] Zhang, L.; Mahdavi, M.; Jin, R., Linear convergence with condition number independent access of full gradients, Advances in Neural Information Processing Systems, 980-988 (2013)
[13] Birge, J. R.; Chen, X.; Qi, L.; Wei, Z., A stochastic Newton method for stochastic quadratic programs with resource, pp. 113-141, Ann Arbor, Mich, USA: University of Michigan, Ann Arbor, Mich, USA
[14] Mokhtari, A.; Ribeiro, A., Regularized Stochastic BFGS algorithm, Global Conference on Signal and Information Processing IEEE, 62, 23, 6089-6104 (2014) · Zbl 1394.94405
[15] Toint, P. L., Global convergence of a class of trust-region methods for nonconvex minimization in Hilbert space, IMA Journal of Numerical Analysis (IMAJNA), 8, 2, 231-252 (1988) · Zbl 0698.65043
[16] Byrd, R. H.; Schnabel, R. B.; Shultz, G., A trust region algorithm for nonlinearly constrained optimization, SIAM Journal on Numerical Analysis, 24, 5, 1152-1170 (1987) · Zbl 0631.65068
[17] Sun, W.; Yuan, Y., Optimization Theory and Methods. Nonlinear Programming (2006), New York, NY, USA: Springer, New York, NY, USA
[18] Nocedal, J.; Wright, S. J., Numerical Optimization (1999), New York, NY, USA: Springer, New York, NY, USA · Zbl 0930.65067
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.