Stochastic gradient descent for linear inverse problems in Hilbert spaces

Lu, Shuai; Mathé, Peter

doi:10.1090/mcom/3714

Stochastic gradient descent for linear inverse problems in Hilbert spaces
HTML articles powered by AMS MathViewer

by Shuai Lu and Peter Mathé HTML | PDF

Math. Comp. 91 (2022), 1763-1788 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; Chapman and Hall, Ltd., London, 1956, pp. 191–233. MR 0078748
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.