Nested Expectations with Kernel Quadrature

• URL: http://arxiv.org/abs/2502.18284v1
• Date: Tue, 25 Feb 2025 15:19:10 GMT
• Title: Nested Expectations with Kernel Quadrature
• Authors: Zonghao Chen, Masha Naslidnyk, François-Xavier Briol,
• Abstract summary: Existing algorithms, such as nested Monte Carlo or multilevel Monte Carlo, are known to be consistent but require a large number of samples at both inner and outer levels to converge.<n>We propose a novel estimator consisting of nested kernel quadrature estimators.
• Score: 6.531113005552847
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper considers the challenging computational task of estimating nested expectations. Existing algorithms, such as nested Monte Carlo or multilevel Monte Carlo, are known to be consistent but require a large number of samples at both inner and outer levels to converge. Instead, we propose a novel estimator consisting of nested kernel quadrature estimators and we prove that it has a faster convergence rate than all baseline methods when the integrands have sufficient smoothness. We then demonstrate empirically that our proposed method does indeed require fewer samples to estimate nested expectations on real-world applications including Bayesian optimisation, option pricing, and health economics.

Related papers

• Non-linear Quantum Monte Carlo [1.237454174824584]
  Quantum computing provides a quadratic speedup over classical Monte Carlo methods for mean estimation.<n>We propose a quantum-inside-quantum Monte Carlo algorithm that achieves such a speedup for a broad class of non-linear estimation problems.
  arXiv  Detail & Related papers  (2025-02-07T17:13:27Z)
• A Specialized Semismooth Newton Method for Kernel-Based Optimal Transport [92.96250725599958]
  Kernel-based optimal transport (OT) estimators offer an alternative, functional estimation procedure to address OT problems from samples. We show that our SSN method achieves a global convergence rate of $O (1/sqrtk)$, and a local quadratic convergence rate under standard regularity conditions.
  arXiv  Detail & Related papers  (2023-10-21T18:48:45Z)
• Parallelized Acquisition for Active Learning using Monte Carlo Sampling [0.0]
  Recent attention has been directed towards the use of emulators of the posterior based on Gaussian Process (GP) regression. We show how to generate a Monte Carlo sample of the posterior using almost-embarrassingly parallel sequential samplers. The resulting nearly-sorted Monte Carlo sample is used to generate a batch of candidates ranked according to their sequentially conditioned acquisition function values.
  arXiv  Detail & Related papers  (2023-05-30T17:57:34Z)
• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  Inspired by regularization techniques in statistics and machine learning, we study complementary composite minimization. We provide novel excess risk bounds, both in expectation and with high probability. Our algorithms are nearly optimal, which we prove via novel lower complexity bounds for this class of problems.
  arXiv  Detail & Related papers  (2022-11-03T12:40:24Z)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  We propose a novel method named Multi-block-probe Variance Reduced (MSVR) to alleviate the complexity of compositional problems. Our results improve upon prior ones in several aspects, including the order of sample complexities and dependence on strongity.
  arXiv  Detail & Related papers  (2022-07-18T12:03:26Z)
• Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization [61.26619639722804]
  We propose a conditional gradient method (CGM) for minimizing convex finite-sum objectives formed as a sum of smooth and non-smooth terms. The proposed method, equipped with an average gradient (SAG) estimator, requires only one sample per iteration. Nevertheless, it guarantees fast convergence rates on par with more sophisticated variance reduction techniques.
  arXiv  Detail & Related papers  (2022-02-26T19:10:48Z)
• Smooth Nested Simulation: Bridging Cubic and Square Root Convergence Rates in High Dimensions [10.596607712009128]
  We propose a new method to exploit the smoothness of the conditional expectation as a function of the multidimensional conditioning variable. Asymptotic analysis shows that the proposed method can effectively alleviate the curse of dimensionality on the convergence rate as the simulation budget increases.
  arXiv  Detail & Related papers  (2022-01-09T08:32:00Z)
• Accelerated, Optimal, and Parallel: Some Results on Model-Based Stochastic Optimization [33.71051480619541]
  We extend the Approximate-Proximal Point (aProx) family of model-based methods for solving convex optimization problems. We provide non-asymptotic convergence guarantees and an acceleration scheme for which we provide linear speedup in minibatch size. We show improved convergence rates and matching lower bounds identifying new fundamental constants for "interpolation" problems.
  arXiv  Detail & Related papers  (2021-01-07T18:58:39Z)
• Learning Minimax Estimators via Online Learning [55.92459567732491]
  We consider the problem of designing minimax estimators for estimating parameters of a probability distribution. We construct an algorithm for finding a mixed-case Nash equilibrium.
  arXiv  Detail & Related papers  (2020-06-19T22:49:42Z)
• Unbiased MLMC stochastic gradient-based optimization of Bayesian experimental designs [4.112293524466434]
  The gradient of the expected information gain with respect to experimental design parameters is given by a nested expectation. We introduce an unbiased Monte Carlo estimator for the gradient of the expected information gain with finite expected squared $ell$-norm and finite expected computational cost per sample.
  arXiv  Detail & Related papers  (2020-05-18T01:02:31Z)
• Distributionally Robust Bayesian Quadrature Optimization [60.383252534861136]
  We study BQO under distributional uncertainty in which the underlying probability distribution is unknown except for a limited set of its i.i.d. samples. A standard BQO approach maximizes the Monte Carlo estimate of the true expected objective given the fixed sample set. We propose a novel posterior sampling based algorithm, namely distributionally robust BQO (DRBQO) for this purpose.
  arXiv  Detail & Related papers  (2020-01-19T12:00:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.