An Efficient Finite Difference Approximation via a Double Sample-Recycling Approach

• URL: http://arxiv.org/abs/2405.05638v1
• Date: Thu, 9 May 2024 09:27:18 GMT
• Title: An Efficient Finite Difference Approximation via a Double Sample-Recycling Approach
• Authors: Guo Liang, Guangwu Liu, Kun Zhang,
• Abstract summary: We propose a double sample-recycling approach in this paper. Pilot samples are recycled to estimate the optimal perturbation. generating new samples leads to an efficient finite difference estimator.
• Score: 6.054123928890574
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Estimating stochastic gradients is pivotal in fields like service systems within operations research. The classical method for this estimation is the finite difference approximation, which entails generating samples at perturbed inputs. Nonetheless, practical challenges persist in determining the perturbation and obtaining an optimal finite difference estimator in the sense of possessing the smallest mean squared error (MSE). To tackle this problem, we propose a double sample-recycling approach in this paper. Firstly, pilot samples are recycled to estimate the optimal perturbation. Secondly, recycling these pilot samples again and generating new samples at the estimated perturbation, lead to an efficient finite difference estimator. We analyze its bias, variance and MSE. Our analyses demonstrate a reduction in asymptotic variance, and in some cases, a decrease in asymptotic bias, compared to the optimal finite difference estimator. Therefore, our proposed estimator consistently coincides with, or even outperforms the optimal finite difference estimator. In numerical experiments, we apply the estimator in several examples, and numerical results demonstrate its robustness, as well as coincidence with the theory presented, especially in the case of small sample sizes.

Related papers

• Enhanced Derivative-Free Optimization Using Adaptive Correlation-Induced Finite Difference Estimators [6.054123928890574]
  We develop an algorithm designed to enhance DFO in terms of both gradient estimation efficiency and sample efficiency. We establish the consistency of our proposed algorithm and demonstrate that, despite using a batch of samples per iteration, it achieves the same convergence rate as the KW and SPSA methods.
  arXiv  Detail & Related papers  (2025-02-28T08:05:54Z)
• In-Context Parametric Inference: Point or Distribution Estimators? [66.22308335324239]
  We show that amortized point estimators generally outperform posterior inference, though the latter remain competitive in some low-dimensional problems. Our experiments indicate that amortized point estimators generally outperform posterior inference, though the latter remain competitive in some low-dimensional problems.
  arXiv  Detail & Related papers  (2025-02-17T10:00:24Z)
• Derivative-Free Optimization via Finite Difference Approximation: An Experimental Study [1.3886390523644807]
  Derivative-free optimization (DFO) is vital in solving complex optimization problems where only noisy function evaluations are available through an oracle. Two classical iteration approaches are Kiefer-Wolfowitz (KW) and simultaneous perturbation approximation (SPSA) algorithms. This paper conducts a comprehensive experimental comparison among these approaches.
  arXiv  Detail & Related papers  (2024-10-31T18:07:44Z)
• Optimal convex $M$-estimation via score matching [6.115859302936817]
  We construct a data-driven convex loss function with respect to which empirical risk minimisation yields optimal variance in the downstream estimation of the regression coefficients. Our semiparametric approach targets the best decreasing approximation of the derivative of the derivative of the log-density of the noise distribution.
  arXiv  Detail & Related papers  (2024-03-25T12:23:19Z)
• Leveraging Self-Consistency for Data-Efficient Amortized Bayesian Inference [9.940560505044122]
  We propose a method to improve the efficiency and accuracy of amortized Bayesian inference. We estimate the marginal likelihood based on approximate representations of the joint model.
  arXiv  Detail & Related papers  (2023-10-06T17:41:41Z)
• A Mean Field Approach to Empirical Bayes Estimation in High-dimensional Linear Regression [8.345523969593492]
  We study empirical Bayes estimation in high-dimensional linear regression. We adopt a variational empirical Bayes approach, introduced originally in Carbonetto and Stephens (2012) and Kim et al. (2022). This provides the first rigorous empirical Bayes method in a high-dimensional regression setting without sparsity.
  arXiv  Detail & Related papers  (2023-09-28T20:51:40Z)
• DF2: Distribution-Free Decision-Focused Learning [53.2476224456902]
  Decision-focused learning (DFL) has recently emerged as a powerful approach for predictthen-optimize problems. Existing end-to-end DFL methods are hindered by three significant bottlenecks: model error, sample average approximation error, and distribution-based parameterization of the expected objective. We present DF2 -- the first textit-free decision-focused learning method explicitly designed to address these three bottlenecks.
  arXiv  Detail & Related papers  (2023-08-11T00:44:46Z)
• Scalable method for Bayesian experimental design without integrating over posterior distribution [0.0]
  We address the computational efficiency in solving the A-optimal Bayesian design of experiments problems. A-optimality is a widely used and easy-to-interpret criterion for Bayesian experimental design. This study presents a novel likelihood-free approach to the A-optimal experimental design.
  arXiv  Detail & Related papers  (2023-06-30T12:40:43Z)
• Learning Unnormalized Statistical Models via Compositional Optimization [73.30514599338407]
  Noise-contrastive estimation(NCE) has been proposed by formulating the objective as the logistic loss of the real data and the artificial noise. In this paper, we study it a direct approach for optimizing the negative log-likelihood of unnormalized models.
  arXiv  Detail & Related papers  (2023-06-13T01:18:16Z)
• Data-Driven Influence Functions for Optimization-Based Causal Inference [105.5385525290466]
  We study a constructive algorithm that approximates Gateaux derivatives for statistical functionals by finite differencing. We study the case where probability distributions are not known a priori but need to be estimated from data.
  arXiv  Detail & Related papers  (2022-08-29T16:16:22Z)
• Efficient CDF Approximations for Normalizing Flows [64.60846767084877]
  We build upon the diffeomorphic properties of normalizing flows to estimate the cumulative distribution function (CDF) over a closed region. Our experiments on popular flow architectures and UCI datasets show a marked improvement in sample efficiency as compared to traditional estimators.
  arXiv  Detail & Related papers  (2022-02-23T06:11:49Z)
• Learning to Estimate Without Bias [57.82628598276623]
  Gauss theorem states that the weighted least squares estimator is a linear minimum variance unbiased estimation (MVUE) in linear models. In this paper, we take a first step towards extending this result to non linear settings via deep learning with bias constraints. A second motivation to BCE is in applications where multiple estimates of the same unknown are averaged for improved performance.
  arXiv  Detail & Related papers  (2021-10-24T10:23:51Z)
• Heavy-tailed Streaming Statistical Estimation [58.70341336199497]
  We consider the task of heavy-tailed statistical estimation given streaming $p$ samples. We design a clipped gradient descent and provide an improved analysis under a more nuanced condition on the noise of gradients.
  arXiv  Detail & Related papers  (2021-08-25T21:30:27Z)

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.