Stochastic gradient descent for linear inverse problems in Hilbert spaces
HTML articles powered by AMS MathViewer
- by Shuai Lu and Peter Mathé;
- Math. Comp. 91 (2022), 1763-1788
- DOI: https://doi.org/10.1090/mcom/3714
- Published electronically: December 22, 2021
- HTML | PDF | Request permission
Abstract:
We investigate stochastic gradient decent (SGD) for solving full infinite dimensional ill-posed problems in Hilbert spaces. We allow for batch-size versions of SGD where the randomly chosen batches incur noise fluctuations. Based on the corresponding bias-variance decomposition we provide bounds for the root mean squared error. These bounds take into account the discretization levels, the decay of the step-size, which is more flexible than in existing results, and the underlying smoothness in terms of general source conditions. This allows to apply SGD to severely ill-posed problems. The obtained error bounds exhibit three stages of the performance of SGD. In particular, the pre-asymptotic behavior can be well seen. Some numerical studies verify the theoretical predictions.References
- Rajendra Bhatia, Matrix analysis, Graduate Texts in Mathematics, vol. 169, Springer-Verlag, New York, 1997. MR 1477662, DOI 10.1007/978-1-4612-0653-8
- Léon Bottou, Frank E. Curtis, and Jorge Nocedal, Optimization methods for large-scale machine learning, SIAM Rev. 60 (2018), no. 2, 223–311. MR 3797719, DOI 10.1137/16M1080173
- Susanne C. Brenner and L. Ridgway Scott, The mathematical theory of finite element methods, 3rd ed., Texts in Applied Mathematics, vol. 15, Springer, New York, 2008. MR 2373954, DOI 10.1007/978-0-387-75934-0
- John B. Conway, A course in functional analysis, 2nd ed., Graduate Texts in Mathematics, vol. 96, Springer-Verlag, New York, 1990. MR 1070713
- J. H. Curtiss, A theoretical comparison of the efficiencies of two classical methods and a Monte Carlo method for computing one component of the solution of a set of linear algebraic equations, Symposium on Monte Carlo methods, University of Florida, 1954, John Wiley and Sons, Inc., New York, 1956, pp. 191–233. MR 78748
- Carl de Boor, A practical guide to splines, Applied Mathematical Sciences, vol. 27, Springer-Verlag, New York-Berlin, 1978. MR 507062, DOI 10.1007/978-1-4612-6333-3
- Heinz W. Engl, Martin Hanke, and Andreas Neubauer, Regularization of inverse problems, Mathematics and its Applications, vol. 375, Kluwer Academic Publishers Group, Dordrecht, 1996. MR 1408680, DOI 10.1007/978-94-009-1740-8
- George E. Forsythe and Richard A. Leibler, Matrix inversion by a Monte Carlo method, Math. Tables Aids Comput. 4 (1950), 127–129. MR 38138, DOI 10.1090/S0025-5718-1950-0038138-X
- Robert M. Gower and Peter Richtárik, Randomized iterative methods for linear systems, SIAM J. Matrix Anal. Appl. 36 (2015), no. 4, 1660–1690. MR 3432148, DOI 10.1137/15M1025487
- Per Christian Hansen, Regularization Tools version 4.0 for Matlab 7.3, Numer. Algorithms 46 (2007), no. 2, 189–194. MR 2358249, DOI 10.1007/s11075-007-9136-9
- Bernd Hofmann and Peter Mathé, Analysis of profile functions for general linear regularization methods, SIAM J. Numer. Anal. 45 (2007), no. 3, 1122–1141. MR 2318806, DOI 10.1137/060654530
- Alexey F. Izmailov, Vladimir G. Karmanov, and Alexey A. Tretyakov, Regularization of linear approximate schemes by the gradient descent, SIAM J. Numer. Anal. 39 (2001), no. 1, 250–263. MR 1860724, DOI 10.1137/S0036142999364522
- Bangti Jin and Xiliang Lu, On the regularizing property of stochastic gradient descent, Inverse Problems 35 (2019), no. 1, 015004, 27. MR 3884601, DOI 10.1088/1361-6420/aaea2a
- Bangti Jin, Zehui Zhou, and Jun Zou, On the convergence of stochastic gradient descent for nonlinear ill-posed problems, SIAM J. Optim. 30 (2020), no. 2, 1421–1450. MR 4099813, DOI 10.1137/19M1271798
- Malvin H. Kalos and Paula A. Whitlock, Monte Carlo methods, 2nd ed., Wiley-Blackwell, Weinheim, 2008. MR 2503174, DOI 10.1002/9783527626212
- Barbara Kaltenbacher, Andreas Neubauer, and Otmar Scherzer, Iterative regularization methods for nonlinear ill-posed problems, Radon Series on Computational and Applied Mathematics, vol. 6, Walter de Gruyter GmbH & Co. KG, Berlin, 2008. MR 2459012, DOI 10.1515/9783110208276
- Sanjiv Kumar, Mehryar Mohri, and Ameet Talwalkar, Sampling methods for the Nyström method, J. Mach. Learn. Res. 13 (2012), 981–1006. MR 2930630
- Junhong Lin and Lorenzo Rosasco, Optimal rates for multi-pass stochastic gradient methods, J. Mach. Learn. Res. 18 (2017), Paper No. 97, 47. MR 3714260
- Peter Mathé and Sergei V. Pereverzev, Discretization strategy for linear ill-posed problems in variable Hilbert scales, Inverse Problems 19 (2003), no. 6, 1263–1277. MR 2036530, DOI 10.1088/0266-5611/19/6/003
- Peter Mathé and Sergei V. Pereverzev, Geometry of linear ill-posed problems in variable Hilbert scales, Inverse Problems 19 (2003), no. 3, 789–803. MR 1984890, DOI 10.1088/0266-5611/19/3/319
- R. Plato and G. Vainikko, On the regularization of projection methods for solving ill-posed problems, Numer. Math. 57 (1990), no. 1, 63–79. MR 1043802, DOI 10.1007/BF01386397
- Herbert Robbins and Sutton Monro, A stochastic approximation method, Ann. Math. Statistics 22 (1951), 400–407. MR 42668, DOI 10.1214/aoms/1177729586
- Ulrich Tautenhahn, On the asymptotical regularization of nonlinear ill-posed problems, Inverse Problems 10 (1994), no. 6, 1405–1418. MR 1306812, DOI 10.1088/0266-5611/10/6/014
- Y. Zhao, P. Mathé, and S. Lu, Convergence analysis for asymptotical regularization and Runge-Kutta integrators under variational source conditions, CSIAM Trans. on Appl. Math., 1 (2020), pp. 693–714.
Bibliographic Information
- Shuai Lu
- Affiliation: School of Mathematical Sciences, Fudan University, 200433 Shanghai, People’s Republic of China
- MR Author ID: 759390
- ORCID: 0000-0002-1208-1421
- Email: slu@fudan.edu.cn
- Peter Mathé
- Affiliation: Weierstraß Institute for Applied Analysis and Stochastics, Mohrenstraße 39, 10117 Berlin, Germany
- Email: peter.mathe@wias-berlin.de
- Received by editor(s): July 7, 2021
- Received by editor(s) in revised form: October 24, 2021
- Published electronically: December 22, 2021
- Additional Notes: The first author was supported by NSFC (No.11925104), Science and Technology Commission of Shanghai Municipality (19XD1420500, 21JC1400500).
- © Copyright 2021 American Mathematical Society
- Journal: Math. Comp. 91 (2022), 1763-1788
- MSC (2020): Primary 47A52; Secondary 65F22, 65C05
- DOI: https://doi.org/10.1090/mcom/3714
- MathSciNet review: 4435947