第5回 物理工学科教室談話会(講師:Prof. Yuji Nakatsukasa / 中務 佑治 氏)

日時: 11/2(金) 15:00-
場所: 工学部6号館1階103号室(大会議室)
講師: Prof. Yuji Nakatsukasa / 中務 佑治 氏
所属: Nat. Inst. Informatics / 国立情報学研究所
題目: Monte Carlo integration: variance reduction by function approximation / モンテカルロ積分への関数近似論アプローチ

Classical algorithms for numerical integration (quadrature/cubature) proceed by approximating the integrand with a simple function (e.g. a polynomial), and integrate the approximant exactly. In high-dimensional integration, such methods quickly become infeasible due to the curse of dimensionality.
A common alternative is the Monte Carlo method (MC), which simply takes the average of random samples, improving the estimate as more and more samples are taken. The main issue with MC is its slow “sqrt(variance/#samples)” convergence, and various techniques have been proposed to reduce the variance.
In this work we reveal a numerical analyst’s interpretation of MC: it approximates the integrand with a constant function, and integrates the constant exactly. This observation leads naturally to MC-like methods that combines MC with (high-dimensional) function approximation theory, including polynomial approximation, sparse grids and low-rank approximation. The resulting method can be regarded as another variance reduction technique for Monte Carlo. We also discuss methods that improve the approximation quality as more samples are taken, and thus can converge faster than 1/sqrt(#samples).
Talk will be in English.
紹介教員:山地 洋平 特任准教授、今田 正俊 教授(ともに物理工学専攻)