# American Institute of Mathematical Sciences

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. Georges, G. Kotliar, W. 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. Mishchenko, N. 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. Needell, N. 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. Georges, G. Kotliar, W. 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. Mishchenko, N. 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. Needell, N. 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
Example 1. True spectrum
Example 1. (a) FESOM samples; (b) FESOM estimation
Example 1. Estimated spectrum learned from FESOM samples
Example 2. True spectrum
Example 2. (a) FESOM estimation; (b) Estimated spectrum learned from FESOM samples
Example 2. Comparison between SGD and MaxEnt
True spectrum
Example 3. Estimations for the spectrum
Example 3. Spectrum with fine feature in positive frequency region
Example 3. (a) MaxEnt estimation for $A_2$; (b) Comparison of MaxEnt in estimating $A_1$ (red) and $A_2$ (blue)
Example 3. (a) SGD estimation for $A_1$; (b) SGD estimation for $A_2$
 [1] Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023 [2] J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008 [3] Diana Keller. Optimal control of a linear stochastic Schrödinger equation. Conference Publications, 2013, 2013 (special) : 437-446. doi: 10.3934/proc.2013.2013.437 [4] Seung-Yeal Ha, Dongnam Ko, Chanho Min, Xiongtao Zhang. Emergent collective behaviors of stochastic kuramoto oscillators. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 1059-1081. doi: 10.3934/dcdsb.2019208 [5] María J. Garrido-Atienza, Bohdan Maslowski, Jana  Šnupárková. Semilinear stochastic equations with bilinear fractional noise. Discrete & Continuous Dynamical Systems - B, 2016, 21 (9) : 3075-3094. doi: 10.3934/dcdsb.2016088 [6] Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024 [7] Shangzhi Li, Shangjiang Guo. Permanence and extinction of a stochastic SIS epidemic model with three independent Brownian motions. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2693-2719. doi: 10.3934/dcdsb.2020201 [8] Xianming Liu, Guangyue Han. A Wong-Zakai approximation of stochastic differential equations driven by a general semimartingale. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2499-2508. doi: 10.3934/dcdsb.2020192 [9] Nhu N. Nguyen, George Yin. Stochastic partial differential equation models for spatially dependent predator-prey equations. Discrete & Continuous Dynamical Systems - B, 2020, 25 (1) : 117-139. doi: 10.3934/dcdsb.2019175 [10] Longxiang Fang, Narayanaswamy Balakrishnan, Wenyu Huang. Stochastic comparisons of parallel systems with scale proportional hazards components equipped with starting devices. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021004 [11] Bin Pei, Yong Xu, Yuzhen Bai. Convergence of p-th mean in an averaging principle for stochastic partial differential equations driven by fractional Brownian motion. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 1141-1158. doi: 10.3934/dcdsb.2019213 [12] Shihu Li, Wei Liu, Yingchao Xie. Large deviations for stochastic 3D Leray-$\alpha$ model with fractional dissipation. Communications on Pure & Applied Analysis, 2019, 18 (5) : 2491-2509. doi: 10.3934/cpaa.2019113 [13] Shanjian Tang, Fu Zhang. Path-dependent optimal stochastic control and viscosity solution of associated Bellman equations. Discrete & Continuous Dynamical Systems - A, 2015, 35 (11) : 5521-5553. doi: 10.3934/dcds.2015.35.5521 [14] Xiaohu Wang, Dingshi Li, Jun Shen. Wong-Zakai approximations and attractors for stochastic wave equations driven by additive noise. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2829-2855. doi: 10.3934/dcdsb.2020207 [15] Vieri Benci, Sunra Mosconi, Marco Squassina. Preface: Applications of mathematical analysis to problems in theoretical physics. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : i-i. doi: 10.3934/dcdss.2020446 [16] Tuan Hiep Pham, Jérôme Laverne, Jean-Jacques Marigo. Stress gradient effects on the nucleation and propagation of cohesive cracks. Discrete & Continuous Dynamical Systems - S, 2016, 9 (2) : 557-584. doi: 10.3934/dcdss.2016012 [17] Matthias Erbar, Jan Maas. Gradient flow structures for discrete porous medium equations. Discrete & Continuous Dynamical Systems - A, 2014, 34 (4) : 1355-1374. doi: 10.3934/dcds.2014.34.1355 [18] Andrea Cianchi, Adele Ferone. Improving sharp Sobolev type inequalities by optimal remainder gradient norms. Communications on Pure & Applied Analysis, 2012, 11 (3) : 1363-1386. doi: 10.3934/cpaa.2012.11.1363 [19] Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399 [20] Abdulrazzaq T. Abed, Azzam S. Y. Aladool. Applying particle swarm optimization based on Padé approximant to solve ordinary differential equation. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2021008

Impact Factor:

## Tools

Article outline

Figures and Tables

[Back to Top]