Back to search

Boston University

Topics in Thompson sampling and sparse Bayesian machine learning

Abstract

dc:description.abstract

This dissertation explores high-dimensional Bayesian sparse machine learning, focusing on three main topics: Thompson sampling for dynamic pricing, algorithm unrolling models for inverse problems, and cyclical MCMC sampling. The primary objective is to analyze the algorithms and investigate theoretical and practical aspects of their performance. The dissertation is structured into four chapters: the first provides an introduction, and each of the remaining three addresses one of the topics. The first chapter is dedicated to the study of Thompson sampling, a Bayesian approach to multi-armed Bandit (MAB) problems, in the context of dynamic pricing. Dynamic pricing is a strategy to optimize product sales prices based on real-time information to maximize revenue. We analyze the behavior of Thompson sampling for dynamic pricing under high-dimensional settings when the noise distribution is misspecified. We show that under these settings, the cumulative regret of Thompson sampling at time t decomposes into a leading term measuring the mismatch of the posited noise distribution plus a remainder term that scales as O(\bar s_0^2 \log(d)\log(t)), where \bar s_0 is the underlying sparsity parameter. To mitigate the impact of the unknown noise distribution, we introduce a double-Thompson sampling algorithm that learns to select the best noise distribution among a finite set of candidates. We carry out extensive simulations to demonstrate the effectiveness of our algorithms. In the second chapter, we study inverse problems where the conditional distribution of the observation \bf y given the latent variable of interest \bf x (also known as the forward model) is known, and we have access to a data set in which multiple instances of \bf x and \bf y are both observed. We analyze the statistical complexity of the gradient descent network (GDN), an algorithm unrolling architecture driven by proximal gradient descent that effectively exploit the forward model to solve inverse problem. We show that the depth of unrolling needed for the optimal statistical performance of GDNs is of the order \log(n)/\log(\varrho_n^{-1}), where n is the sample size and \varrho_n is the convergence rate of the corresponding gradient descent algorithm. We also show that when the negative log-density of the latent variable {\bf x} has a simple proximal operator, then a GDN unrolled at depth D' can solve the inverse problem at the parametric rate O(D'/\sqrt{n}). Our results thus also suggest that algorithm unrolling models are prone to over-fitting as the unrolling depth D' increases. We provide several examples to illustrate these results. In the third chapter, we study a Markov Chain Monte Carlo (MCMC) framework, cyclical MCMC, which is recently proposed by \cite{Zhang2019CyclicalSG} to address the challenge posed by high-dimensional multimodal posterior distributions like those arising in deep learning. We show in this chapter that cyclical MCMC converges to the desired probability distribution in settings where the Markov kernels used are fast mixing and sufficiently long cycles are employed. However, in the far more common settings of slow mixing kernels, the algorithm may fail to produce samples from the desired distribution. We also show that cyclical MCMC typically estimates well the local shape of the target distribution around each mode, even when we do not have convergence to the target.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy
Level thesis:degree_level
doctoral
Discipline thesis:degree_discipline
Mathematics & Statistics
Grantor
Boston University
Year dc:date.issued
2025

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Liu, Xinru
Advisor dc:contributor.advisor
  • Atchade, Yves

Subjects

dc:subject × 1

Rights

dc:rights
Statement dc:rights
  • Attribution 4.0 International
Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/2144/53303

Chain of custody

source
Harvested from
Boston University
Base URL
open.bu.edu/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
related terms
citation

Liu, Xinru. Topics in Thompson sampling and sparse Bayesian machine learning. doctoral thesis, Boston University, 2025. https://hdl.handle.net/2144/53303