DMS Colloquium: Jungeum Kim

Speaker: Dr. Jungeum Kim (University of Chicago)

Title: Computational Complexity of Bayesian CART

Abstract: The success of Bayesian inference with MCMC depends critically on Markov chains reaching the posterior distribution reasonably fast. A host of theoretical results exist showing inferential validity of posteriors for Bayesian non-parametrics procedures (such as Gaussian processes or BART). However, convergence properties of MCMC algorithms that simulate from such ideal inferential targets are not always available. This work focuses on the Bayesian CART algorithm which forms a building block of Bayesian Additive Regression Trees (BART). We derive upper bounds on mixing times for typical posteriors under various proposal distributions. Exploiting the wavelet representation of trees, we provide sufficient conditions for Bayesian CART to mix well (polynomially) under certain hierarchical connectivity restrictions on the signal. We also derive a negative result showing that Bayesian CART (based on simple grow and prune steps) cannot reach deep isolated signals in faster than exponential mixing time. To remediate myopic chain exploration, we propose Twiggy Bayesian CART which attaches/detaches entire twigs (not just single nodes) in the proposal distribution. We show polynomial mixing of Twiggy Bayesian CART without assuming that the signal is connected on a tree. This talk is based on a joint work with Veronika Rockova at the University of Chicago Booth School of Business

Short Bio: Jungeum Kim is a Principal Researcher working with Professor Rockova at the University of Chicago Booth School of Business. She received her Ph.D. degree at Purdue University under the supervision of Dr. Xiao Wang. She studied three important problems in modern deep learning in her dissertation: adversarial robustness, dimensional reduction for visualization (manifold learning), and partially monotonic function modeling. She has also worked on generative models, such as generative adversarial networks, variational autoencoder, and energy-based models. Before her Ph.D., she received her Master's and Bachelor's degree at Seoul National University under the supervision of Dr. Hee-seok Oh and worked on robust PCA.

Faculty host: Guanqun Cao