More Like this

1. Systematically Differentiating Parametric Discontinuities

   https://doi.org/10.1145/3450626.3459775  

   Bangaru, Sai Praveen; Michel, Jesse; Mu, Kevin; Bernstein, Gilbert; Li, Tzu-Mao; Ragan-Kelley, Jonathan (August 2021, ACM transactions on graphics)

   Emerging research in computer graphics, inverse problems, and machine learning requires us to differentiate and optimize parametric discontinuities. These discontinuities appear in object boundaries, occlusion, contact, and sudden change over time. In many domains, such as rendering and physics simulation, we differentiate the parameters of models that are expressed as integrals over discontinuous functions. Ignoring the discontinuities during differentiation often has a significant impact on the optimization process. Previous approaches either apply specialized hand-derived solutions, smooth out the discontinuities, or rely on incorrect automatic differentiation. We propose a systematic approach to differentiating integrals with discontinuous integrands, by developing a new differentiable programming language. We introduce integration as a language primitive and account for the Dirac delta contribution from differentiating parametric discontinuities in the integrand. We formally define the language semantics and prove the correctness and closure under the differentiation, allowing the generation of gradients and higher-order derivatives. We also build a system, Teg, implementing these semantics. Our approach is widely applicable to a variety of tasks, including image stylization, fitting shader parameters, trajectory optimization, and optimizing physical designs. 

   more » « less
2. A Uniform Error Bound for Stochastic Kriging: Properties and Implications on Simulation Experimental Design

   https://doi.org/10.1145/3682059  

   Chen, Xi; Zhang, Yutong; Xie, Guangrui; Zhang, Jingtao (July 2024, ACM Transactions on Modeling and Computer Simulation)

   In this work, we propose a method to construct a uniform error bound for the SK predictor. In investigating the asymptotic properties of the proposed uniform error bound, we examine the convergence rate of SK’s predictive variance under the supremum norm in both fixed and random design settings. Our analyses reveal that the large-sample properties of SK prediction depend on the design-point sampling scheme and the budget allocation scheme adopted. Appropriately controlling the order of noise variances through budget allocation is crucial for achieving a desirable convergence rate of SK’s approximation error, as quantified by the uniform error bound, and for maintaining SK’s numerical stability. Moreover, we investigate the impact of noise variance estimation on the uniform error bound’s performance theoretically and numerically. We demonstrate the superiority of the proposed uniform bound to the Bonferroni correction-based simultaneous confidence interval under various experimental settings through numerical evaluations. 

   more » « less
3. Convergence Analysis of Deterministic Kernel-Based Quadrature Rules in Misspecified Settings

   https://doi.org/10.1007/s10208-018-09407-7  

   Kanagawa, Motonobu; Sriperumbudur, Bharath K.; Fukumizu, Kenji (January 2019, Foundations of Computational Mathematics)

   This paper presents convergence analysis of kernel-based quadrature rules in misspecified settings, focusing on deterministic quadrature in Sobolev spaces. In particular, we deal with misspecified settings where a test integrand is less smooth than a Sobolev RKHS based on which a quadrature rule is constructed. We provide convergence guarantees based on two different assumptions on a quadrature rule: one on quadrature weights, and the other on design points. More precisely, we show that convergence rates can be derived (i) if the sum of absolute weights remains constant (or does not increase quickly), or (ii) if the minimum distance between design points does not decrease very quickly. As a consequence of the latter result, we derive a rate of convergence for Bayesian quadrature in misspecified settings. We reveal a condition on design points to make Bayesian quadrature robust to misspecification, and show that, under this condition, it may adaptively achieve the optimal rate of convergence in the Sobolev space of a lesser order (i.e., of the unknown smoothness of a test integrand), under a slightly stronger regularity condition on the integrand. 

   more » « less
4. Improving sampling accuracy of stochastic gradient MCMC methods via non-uniform subsampling of gradients

   https://doi.org/10.3934/dcdss.2021157  

   Li, Ruilin; Wang, Xin; Zha, Hongyuan; Tao, Molei (January 2021, Discrete & Continuous Dynamical Systems - S)

   Many Markov Chain Monte Carlo (MCMC) methods leverage gradient information of the potential function of target distribution to explore sample space efficiently. However, computing gradients can often be computationally expensive for large scale applications, such as those in contemporary machine learning. Stochastic Gradient (SG-)MCMC methods approximate gradients by stochastic ones, commonly via uniformly subsampled data points, and achieve improved computational efficiency, however at the price of introducing sampling error. We propose a non-uniform subsampling scheme to improve the sampling accuracy. The proposed exponentially weighted stochastic gradient (EWSG) is designed so that a non-uniform-SG-MCMC method mimics the statistical behavior of a batch-gradient-MCMC method, and hence the inaccuracy due to SG approximation is reduced. EWSG differs from classical variance reduction (VR) techniques as it focuses on the entire distribution instead of just the variance; nevertheless, its reduced local variance is also proved. EWSG can also be viewed as an extension of the importance sampling idea, successful for stochastic-gradient-based optimizations, to sampling tasks. In our practical implementation of EWSG, the non-uniform subsampling is performed efficiently via a Metropolis-Hastings chain on the data index, which is coupled to the MCMC algorithm. Numerical experiments are provided, not only to demonstrate EWSG's effectiveness, but also to guide hyperparameter choices, and validate our non-asymptotic global error bound despite of approximations in the implementation. Notably, while statistical accuracy is improved, convergence speed can be comparable to the uniform version, which renders EWSG a practical alternative to VR (but EWSG and VR can be combined too). 

   more » « less
5. Adaptive importance sampling for extreme quantile estimation with stochastic black box computer models

   https://doi.org/10.1002/nav.21938  

   Pan, Qiyun; Byon, Eunshin; Ko, Young Myoung; Lam, Henry (August 2020, Naval Research Logistics (NRL))

   Abstract Quantile is an important quantity in reliability analysis, as it is related to the resistance level for defining failure events. This study develops a computationally efficient sampling method for estimating extreme quantiles using stochastic black box computer models. Importance sampling has been widely employed as a powerful variance reduction technique to reduce estimation uncertainty and improve computational efficiency in many reliability studies. However, when applied to quantile estimation, importance sampling faces challenges, because a good choice of the importance sampling density relies on information about the unknown quantile. We propose an adaptive method that refines the importance sampling density parameter toward the unknown target quantile value along the iterations. The proposed adaptive scheme allows us to use the simulation outcomes obtained in previous iterations for steering the simulation process to focus on important input areas. We prove some convergence properties of the proposed method and show that our approach can achieve variance reduction over crude Monte Carlo sampling. We demonstrate its estimation efficiency through numerical examples and wind turbine case study. 

   more » « less