Explicit error bounds for randomized Smolyak algorithms and an application to infinite-dimensional integration

Duration: 39 mins 43 secs

Share this media item:

Embed this media item:

<iframe width="_width_" height="_height_" src="https://sms.cam.ac.uk/media/2925096/embed" frameborder="0" scrolling="no" allowfullscreen></iframe>

Choose size:

About this item

Available Formats

About this item

Description:	Gnewuch, M Thursday 21st February 2019 - 11:00 to 11:35


Created:	2019-02-21 16:17
Collection:	Approximation, sampling and compression in data science
Publisher:	Isaac Newton Institute
Copyright:	Gnewuch, M
Language:	eng (English)


Abstract:	Smolyak's method, also known as hyperbolic cross approximation or sparse grid method, is a powerful %black box tool to tackle multivariate tensor product problems just with the help of efficient algorithms for the corresponding univariate problem. We provide upper and lower error bounds for randomized Smolyak algorithms with fully explicit dependence on the number of variables and the number of information evaluations used. The error criteria we consider are the worst-case root mean square error (the typical error criterion for randomized algorithms, often referred to as ``randomized error'') and the root mean square worst-case error (often referred to as ``worst-case error''). Randomized Smolyak algorithms can be used as building blocks for efficient methods, such as multilevel algorithms, multivariate decomposition methods or dimension-wise quadrature methods, to tackle successfully high-dimensional or even infinite-dimensional problems. As an example, we provide a very general and sharp result on infinite-dimensional integration on weighted reproducing kernel Hilbert spaces and illustrate it for the special case of weighted Korobov spaces. We explain how this result can be extended, e.g., to spaces of functions whose smooth dependence on successive variables increases (``spaces of increasing smoothness'') and to the problem of L_2-approximation (function recovery).

Abstract:

Smolyak's method, also known as hyperbolic cross approximation or sparse grid method, is a powerful %black box tool to tackle multivariate tensor product problems just with the help of efficient algorithms for the corresponding univariate problem. We provide upper and lower error bounds for randomized Smolyak algorithms with fully explicit dependence on the number of variables and the number of information evaluations used. The error criteria we consider are the worst-case root mean square error (the typical error criterion for randomized algorithms, often referred to as ``randomized error'') and the root mean square worst-case error (often referred to as ``worst-case error''). Randomized Smolyak algorithms can be used as building blocks for efficient methods, such as multilevel algorithms, multivariate decomposition methods or dimension-wise quadrature methods, to tackle successfully high-dimensional or even infinite-dimensional problems. As an example, we provide a very general and sharp result on infinite-dimensional integration on weighted reproducing kernel Hilbert spaces and illustrate it for the special case of weighted Korobov spaces. We explain how this result can be extended, e.g., to spaces of functions whose smooth dependence on successive variables increases (``spaces of increasing smoothness'') and to the problem of L_2-approximation (function recovery).

Available Formats

Format	Quality	Bitrate	Size
MPEG-4 Video	640x360	1.94 Mbits/sec	578.38 MB	View	Download
WebM	640x360	544.38 kbits/sec	158.42 MB	View	Download
iPod Video	480x270	522.14 kbits/sec	151.89 MB	View	Download
MP3	44100 Hz	249.75 kbits/sec	72.74 MB	Listen	Download
Auto *	(Allows browser to choose a format it supports)