Top

Journal of Computer and Systems Sciences International

Published in:

01-01-2021 | COMPUTER METHODS

Stochastic Gradient Method with Barzilai–Borwein Step for Unconstrained Nonlinear Optimization

Authors: L. Wang, H. Wu, I. A. Matveev

Published in: Journal of Computer and Systems Sciences International | Issue 1/2021

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The use of stochastic gradient algorithms for nonlinear optimization is of considerable interest, especially in the case of high dimensions. In this case, the choice of the step size is of key importance for the convergence rate. In this paper, we propose two new stochastic gradient algorithms that use an improved Barzilai–Borwein step size formula. Convergence analysis shows that these algorithms enable linear convergence in probability for strongly convex objective functions. Our computational experiments confirm that the proposed algorithms have better characteristics than two-point gradient algorithms and well-known stochastic gradient methods.

previous article Algorithm of Multidimensional Data Transmission Using Extremal Uniform Hypergraphs

next article Methodology of the Construction of Computational Scenarios for Modeling Extreme States in Living Systems

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

K. Chaudhuri, C. Monteleoni, and D. Sarwate, “Differentially private empirical risk minimization,” J. Mach. Learn. Res., No. 12, 1069–1109 (2011).

H. Robbins and S. Monro, “A stochastic approximation method,” Ann. Math. Stat. 22, 400–407 (1951).MathSciNetCrossRef

Yu. E. Nesterov, “A method for solving a convex programming problem with a convergence rate O(1/k ²),” Dokl. Akad. Nauk SSSR 269, 543–547 (1983).MathSciNet

A. A. Gaivoronskii, “Nonstationary stochastic programming problems,” Cybernetics 14, 575–579 (1978).MathSciNetCrossRef

B. T. Polyak, “New method of stochastic approximation type,” Autom. Remote Control 51, 937–946 (1990).MathSciNetMATH

L. Xiao and T. Zhang, “A proximal stochastic gradient method with progressive variance reduction,” SIAM J. Optimiz. 24, 2057–2075 (2014).MathSciNetCrossRef

R. L. Roux, M. Schmidt, and F. Bach, “A stochastic gradient method with an exponential convergence rate for finite training sets,” Adv. Neural Inform. Process. Syst. 4, 2663–2671 (2012).

S. Shalevshwartz and T. Zhang, “Stochastic dual coordinate ascent methods for regularized loss minimization,” J. Mach. Learn. Res. 14, 567–599 (2013).MathSciNetMATH

R. Johnson and T. Zhang, “Accelerating stochastic gradient descent using predictive variance reduction,” in Proceedings of the 26th International Conference on Neural Information Processing Systems, Lake Tahoe, NV, USA, 2013, pp. 315–323.

10.

J. Barzilai and J. M. Borwein, “Two-point step size gradient methods,” IMA J. Numer. Anal. 8, 141–148 (1988).MathSciNetCrossRef

11.

C. Tan, S. Ma, Y. H. Dai, and Y. Qian, “Barzilai–Borwein step size for stochastic gradient descent,” in Advances in Neural Information Processing Systems 29, Ed. by D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, and R. Garnett (Curran Assoc., New York, 2016), pp. 685–693.

12.

M. Raydan, “On the Barzilai and Borwein choice of steplength for the gradient method,” IMA J. Numer. Anal. 13, 321–326 (1993).MathSciNetCrossRef

13.

Y. Dai, J. Yuan, and Y. X. Yuan, “Modified two-point stepsize gradient methods for unconstrained optimization,” Comput. Optimiz. Appl. 22, 103–109 (2002).MathSciNetCrossRef

14.

Y. X. Yuan, “Step-sizes for the gradient method,” Am. Math. Soc. 42, 785–796 (2008).MathSciNetMATH

15.

X. B. Jin, X. Y. Zhang, K. Huang, and G. G. Geng, “Stochastic conjugate gradient algorithm with variance reduction,” IEEE Trans. Neural Networks Learn. Syst. 30, 1360–1369 (2018).MathSciNetCrossRef

16.

Y. Nesterov, Introductory Lectures on Convex Optimization: A Basic Course (Kluwer Academic, Dordrecht, 2004).CrossRef

17.

www.csie.ntu.edu.tw/ cjlin/libsvmtools/datasets/. Accessed June 6, 2020.

Title: Stochastic Gradient Method with Barzilai–Borwein Step for Unconstrained Nonlinear Optimization
Authors: L. Wang
H. Wu
I. A. Matveev
Publication date: 01-01-2021
Publisher: Pleiades Publishing
Published in: Journal of Computer and Systems Sciences International / Issue 1/2021
Print ISSN: 1064-2307
Electronic ISSN: 1555-6530
DOI: https://doi.org/10.1134/S106423072101010X

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 1/2021

On Quick Action in the Problem of Controlling the Vertical Position of a Pendulum by the Movement of its Base

Methodology of the Construction of Computational Scenarios for Modeling Extreme States in Living Systems

On the Parameter Selection of a Query Flow Control System Using the Probabilistic Pushing Out Mechanism

A New Run Algorithm for Solving the Continuous Linear-Quadratic Optimal Control Problem with Unseparated Boundary Conditions

Algorithm of Multidimensional Data Transmission Using Extremal Uniform Hypergraphs

Study of Lidar Controlled Road Scanning Systems for Unmanned Cars

Premium Partner