March  2020, 2(1): 1-17. doi: 10.3934/fods.2020001

Stochastic gradient descent algorithm for stochastic optimization in solving analytic continuation problems

1. 

Department of Mathematics, Florida State University, Tallahassee, Florida, USA

2. 

Center for Nanophase Materials Sciences, Oak Ridge National Laboratory, Oak Ridge, Tennessee, USA

* Corresponding author: Feng Bao

Published  February 2020

Fund Project: The first author is supported by NSF grant DMS-1720222

We propose a stochastic gradient descent based optimization algorithm to solve the analytic continuation problem in which we extract real frequency spectra from imaginary time Quantum Monte Carlo data. The procedure of analytic continuation is an ill-posed inverse problem which is usually solved by regularized optimization methods, such like the Maximum Entropy method, or stochastic optimization methods. The main contribution of this work is to improve the performance of stochastic optimization approaches by introducing a supervised stochastic gradient descent algorithm to solve a flipped inverse system which processes the random solutions obtained by a type of Fast and Efficient Stochastic Optimization Method.

Citation: Feng Bao, Thomas Maier. Stochastic gradient descent algorithm for stochastic optimization in solving analytic continuation problems. Foundations of Data Science, 2020, 2 (1) : 1-17. doi: 10.3934/fods.2020001
References:
[1]

F. Bao, Y. Tang, M. Summers, G. Zhang, C. Webster, V. Scarola and T. A. Maier, Fast and efficient stochastic optimization for analytic continuation, Physical Review B, 94 (2016), 125149. doi: 10.1103/PhysRevB.94.125149.  Google Scholar

[2]

S. Fuchs, T. Pruschke and M. Jarrell, Analytic continuation of quantum monte carlo data by stochastic analytical inference, Physical Review E, 81 (2010), 056701. doi: 10.1103/PhysRevE.81.056701.  Google Scholar

[3]

A. Georges, G. Kotliar, W. Krauth and M. J. Rosenberg, Self-consistent large-n expansion for normal-state properties of dilute magnetic alloys, Physical Review B, 1988, page 2036. Google Scholar

[4]

A. GeorgesG. KotliarW. Krauth and M. J. Rosenberg, Dynamical mean-field theory of strongly correlated fermion systems and the limit of infinite dimensions, Reviews of Modern Physics, 68 (1996), 13-125.  doi: 10.1103/RevModPhys.68.13.  Google Scholar

[5]

S. F. Gull and J. Skilling, Maximum entropy method in image processing, IEE Proceedings F, 131 (1984), 646-659.  doi: 10.1049/ip-f-1.1984.0099.  Google Scholar

[6]

M. Jarrell and J. Gubernatis, Bayesian inference and the analytic continuation of imaginary- time quantum monte carlo data, Physics Reports, 269 (1996), 133-195.  doi: 10.1016/0370-1573(95)00074-7.  Google Scholar

[7]

Q. Li, C. Tai and W. E, Stochastic modified equations and dynamics of stochastic gradient algorithms I: Mathematical foundations, Journal of Machine Learning Research, 20 (2019), Paper No. 40, 47 pp.  Google Scholar

[8]

A. S. MishchenkoN. V. Prokof'ev and A. Sakamoto, Diagrammatic quantum monte carlo study of the fröhlich polaron, Physical Review B, 62 (2000), 6317-6336.  doi: 10.1103/PhysRevB.62.6317.  Google Scholar

[9]

D. NeedellN. Srebro and R. Ward, Stochastic gradient descent, weighted sampling, and the randomized kaczmarz algorithm, Mathematical Programming, 155 (2016), 549-573.  doi: 10.1007/s10107-015-0864-7.  Google Scholar

[10]

N. V. Prokof'ev and B. V. Svistunov, Spectral analysis by the method of consistent constraints, Jetp Lett., 97 (2013), 649-653.  doi: 10.1134/S002136401311009X.  Google Scholar

[11]

A. Sandvik, Stochastic method for analytic continuation of quantum monte carlo data, Physical Review B, (1998), 10287–10290. Google Scholar

[12]

I. Sato and H. Nakagawa, Convergence analysis of gradient descent stochastic algorithms, Proceedings of the 31st International Conference on Machine Learning, (2014), 982–990. Google Scholar

[13]

O. Shamir and T. Zhang, Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes, Proceedings of the 30th International Conference on Machine Learning, 2013, p28. Google Scholar

[14]

A. Shapiro and Y. Wardi, Convergence analysis of gradient descent stochastic algorithms, Journal of Optimization Theory and Aplications, 91 (1996), 439-454.  doi: 10.1007/BF02190104.  Google Scholar

[15]

R. N. Silver, J. E. Gubernatis, D. S. Sivia and M. Jarrell, Spectral densities of the symmetric anderson mode, Physical Review Letters, 1990, 496–499. Google Scholar

[16]

R. Strack and D. Vollhardt, Dynamics of a hole in the t-j model with local disorder: Exact results for high dimensions, Physical Review B, 1992, 13852. Google Scholar

[17]

L. Wu, C. Ma and W. E, How sgd selects the global minima in over-parameterized learning: A dynamical stability perspective, NeurIPS 2018, 2018, 8289–8298. Google Scholar

[18]

Y. Zhang, P. Liang and M. Charikar, A hitting time analysis of stochastic gradient langevin dynamics, Conference on Learning Theory, 2017, 1980–2022. Google Scholar

show all references

References:
[1]

F. Bao, Y. Tang, M. Summers, G. Zhang, C. Webster, V. Scarola and T. A. Maier, Fast and efficient stochastic optimization for analytic continuation, Physical Review B, 94 (2016), 125149. doi: 10.1103/PhysRevB.94.125149.  Google Scholar

[2]

S. Fuchs, T. Pruschke and M. Jarrell, Analytic continuation of quantum monte carlo data by stochastic analytical inference, Physical Review E, 81 (2010), 056701. doi: 10.1103/PhysRevE.81.056701.  Google Scholar

[3]

A. Georges, G. Kotliar, W. Krauth and M. J. Rosenberg, Self-consistent large-n expansion for normal-state properties of dilute magnetic alloys, Physical Review B, 1988, page 2036. Google Scholar

[4]

A. GeorgesG. KotliarW. Krauth and M. J. Rosenberg, Dynamical mean-field theory of strongly correlated fermion systems and the limit of infinite dimensions, Reviews of Modern Physics, 68 (1996), 13-125.  doi: 10.1103/RevModPhys.68.13.  Google Scholar

[5]

S. F. Gull and J. Skilling, Maximum entropy method in image processing, IEE Proceedings F, 131 (1984), 646-659.  doi: 10.1049/ip-f-1.1984.0099.  Google Scholar

[6]

M. Jarrell and J. Gubernatis, Bayesian inference and the analytic continuation of imaginary- time quantum monte carlo data, Physics Reports, 269 (1996), 133-195.  doi: 10.1016/0370-1573(95)00074-7.  Google Scholar

[7]

Q. Li, C. Tai and W. E, Stochastic modified equations and dynamics of stochastic gradient algorithms I: Mathematical foundations, Journal of Machine Learning Research, 20 (2019), Paper No. 40, 47 pp.  Google Scholar

[8]

A. S. MishchenkoN. V. Prokof'ev and A. Sakamoto, Diagrammatic quantum monte carlo study of the fröhlich polaron, Physical Review B, 62 (2000), 6317-6336.  doi: 10.1103/PhysRevB.62.6317.  Google Scholar

[9]

D. NeedellN. Srebro and R. Ward, Stochastic gradient descent, weighted sampling, and the randomized kaczmarz algorithm, Mathematical Programming, 155 (2016), 549-573.  doi: 10.1007/s10107-015-0864-7.  Google Scholar

[10]

N. V. Prokof'ev and B. V. Svistunov, Spectral analysis by the method of consistent constraints, Jetp Lett., 97 (2013), 649-653.  doi: 10.1134/S002136401311009X.  Google Scholar

[11]

A. Sandvik, Stochastic method for analytic continuation of quantum monte carlo data, Physical Review B, (1998), 10287–10290. Google Scholar

[12]

I. Sato and H. Nakagawa, Convergence analysis of gradient descent stochastic algorithms, Proceedings of the 31st International Conference on Machine Learning, (2014), 982–990. Google Scholar

[13]

O. Shamir and T. Zhang, Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes, Proceedings of the 30th International Conference on Machine Learning, 2013, p28. Google Scholar

[14]

A. Shapiro and Y. Wardi, Convergence analysis of gradient descent stochastic algorithms, Journal of Optimization Theory and Aplications, 91 (1996), 439-454.  doi: 10.1007/BF02190104.  Google Scholar

[15]

R. N. Silver, J. E. Gubernatis, D. S. Sivia and M. Jarrell, Spectral densities of the symmetric anderson mode, Physical Review Letters, 1990, 496–499. Google Scholar

[16]

R. Strack and D. Vollhardt, Dynamics of a hole in the t-j model with local disorder: Exact results for high dimensions, Physical Review B, 1992, 13852. Google Scholar

[17]

L. Wu, C. Ma and W. E, How sgd selects the global minima in over-parameterized learning: A dynamical stability perspective, NeurIPS 2018, 2018, 8289–8298. Google Scholar

[18]

Y. Zhang, P. Liang and M. Charikar, A hitting time analysis of stochastic gradient langevin dynamics, Conference on Learning Theory, 2017, 1980–2022. Google Scholar

Figure 1.  Example 1. True spectrum
Figure 2.  Example 1. (a) FESOM samples; (b) FESOM estimation
Figure 3.  Example 1. Estimated spectrum learned from FESOM samples
Figure 4.  Example 2. True spectrum
Figure 5.  Example 2. (a) FESOM estimation; (b) Estimated spectrum learned from FESOM samples
Figure 6.  Example 2. Comparison between SGD and MaxEnt
Figure 7.  True spectrum
Figure 8.  Example 3. Estimations for the spectrum
Figure 9.  Example 3. Spectrum with fine feature in positive frequency region
Figure 10.  Example 3. (a) MaxEnt estimation for $ A_2 $; (b) Comparison of MaxEnt in estimating $ A_1 $ (red) and $ A_2 $ (blue)
Figure 11.  Example 3. (a) SGD estimation for $ A_1 $; (b) SGD estimation for $ A_2 $
[1]

Predrag S. Stanimirović, Branislav Ivanov, Haifeng Ma, Dijana Mosić. A survey of gradient methods for solving nonlinear optimization. Electronic Research Archive, 2020, 28 (4) : 1573-1624. doi: 10.3934/era.2020115

[2]

Zhenzhen Wang, Tianshou Zhou. Asymptotic behaviors and stochastic traveling waves in stochastic Fisher-KPP equations. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020323

[3]

Lorenzo Zambotti. A brief and personal history of stochastic partial differential equations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 471-487. doi: 10.3934/dcds.2020264

[4]

Siyang Cai, Yongmei Cai, Xuerong Mao. A stochastic differential equation SIS epidemic model with regime switching. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020317

[5]

Xuhui Peng, Rangrang Zhang. Approximations of stochastic 3D tamed Navier-Stokes equations. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5337-5365. doi: 10.3934/cpaa.2020241

[6]

Yahia Zare Mehrjerdi. A new methodology for solving bi-criterion fractional stochastic programming. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020054

[7]

Yueyang Zheng, Jingtao Shi. A stackelberg game of backward stochastic differential equations with partial information. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020047

[8]

Reza Chaharpashlou, Abdon Atangana, Reza Saadati. On the fuzzy stability results for fractional stochastic Volterra integral equation. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020432

[9]

Christian Beck, Lukas Gonon, Martin Hutzenthaler, Arnulf Jentzen. On existence and uniqueness properties for solutions of stochastic fixed point equations. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020320

[10]

Giuseppina Guatteri, Federica Masiero. Stochastic maximum principle for problems with delay with dependence on the past through general measures. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020048

[11]

Yangrong Li, Shuang Yang, Qiangheng Zhang. Odd random attractors for stochastic non-autonomous Kuramoto-Sivashinsky equations without dissipation. Electronic Research Archive, 2020, 28 (4) : 1529-1544. doi: 10.3934/era.2020080

[12]

Pengyu Chen. Non-autonomous stochastic evolution equations with nonlinear noise and nonlocal conditions governed by noncompact evolution families. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020383

[13]

Lin Shi, Xuemin Wang, Dingshi Li. Limiting behavior of non-autonomous stochastic reaction-diffusion equations with colored noise on unbounded thin domains. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5367-5386. doi: 10.3934/cpaa.2020242

[14]

Fathalla A. Rihan, Hebatallah J. Alsakaji. Stochastic delay differential equations of three-species prey-predator system with cooperation among prey species. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020468

[15]

Vieri Benci, Sunra Mosconi, Marco Squassina. Preface: Applications of mathematical analysis to problems in theoretical physics. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020446

[16]

Wenmeng Geng, Kai Tao. Large deviation theorems for dirichlet determinants of analytic quasi-periodic jacobi operators with Brjuno-Rüssmann frequency. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5305-5335. doi: 10.3934/cpaa.2020240

[17]

Alberto Bressan, Sondre Tesdal Galtung. A 2-dimensional shape optimization problem for tree branches. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020031

[18]

M. S. Lee, H. G. Harno, B. S. Goh, K. H. Lim. On the bang-bang control approach via a component-wise line search strategy for unconstrained optimization. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 45-61. doi: 10.3934/naco.2020014

[19]

Mohammed Abdulrazaq Kahya, Suhaib Abduljabbar Altamir, Zakariya Yahya Algamal. Improving whale optimization algorithm for feature selection with a time-varying transfer function. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 87-98. doi: 10.3934/naco.2020017

 Impact Factor: 

Metrics

  • PDF downloads (279)
  • HTML views (590)
  • Cited by (0)

Other articles
by authors

[Back to Top]