Topics in high-dimensional linear bandits and approximate Bayesian sampling

In this dissertation, we study the regret lower bound and propose algorithms for general high-dimensional linear problems and propose efficient generative models for Bayesian inference. In the first project, we consider the multi-armed bandit problem with high-dimensional features. First, we prove a minimax lower bound, \mathcal{O}\big((\log d)^{\frac{α+1}{2}}T^{\frac{1-α}{2}}+\log T\big), for the cumulative regret, in terms of horizon $T$, dimension $d$ and a margin parameter α\in[0,1], which controls the separation between the optimal and the sub-optimal arms. This new lower bound unifies existing regret bound results that have different dependencies on T due to the use of different values of margin parameter α explicitly implied by their assumptions. Second, we propose a simple and computationally efficient algorithm inspired by the general Upper Confidence Bound (UCB) strategy that achieves a regret upper bound matching the lower bound. The proposed algorithm uses a properly centered \ell₁-ball as the confidence set in contrast to the commonly used ellipsoid confidence set. In addition, the algorithm does not require any forced sampling step and is thereby adaptive to the practically unknown margin parameter. Simulations and a real data analysis are conducted to compare the proposed method with existing ones in the literature. In the second project, we propose an Upper Confidence Bound (UCB) based algorithm with variable selection. One main contribution of the project is that our proposed algorithm has feature (or variable) selection consistency in bandit settings and facilitates the construction of a confidence region for the true parameter vector. In particular, our proposed algorithm constructs a properly centered ellipsoid confidence set for selected features, and achieves a non-asymptotic regret bound of \mathcal O\big(\log² T +\log d\big) in terms of horizon $T$ and dimension $d$. We show through a matching minimax lower bound that our proposed algorithm is nearly optimal. Finally, we utilize regularized estimators such as SCAD and MCP as examples of variable selection methods and demonstrate the effectiveness of our proposed algorithm using synthetic and real datasets. In the third project, we propose an efficient sampling method, which borrows the ideas from generative models with techniques from the optimal transport theory, for Bayesian inference. Specifically, we construct a transport map that transforms a simple reference distribution into the target distribution. The new approach can produce independent and exact random samples from the target distribution while maintaining similar computational efficiency as variation approximation. In particular, we characterize the optimal transport maps separately for two common cases in Bayesian inference: 1. the target distribution is continuous; 2. the target distribution contains both discrete and continuous random variables. Finally, we use the characterizations of the optimal transport map to develop a finite approximation map family to construct rich posterior approximations.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Statistics

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2022

Author dc:creator

• Li, Ke

Contributors dc:contributor

• Narisetty, Naveen N
• Yang, Yun
• Liang, Feng
• Fellouris, Georgios

• contextual linear bandit
• high-dimensional statistics
• variable selection
• Bayesian inference
• generative model
• optimal transport

Statement dc:rights

• Copyright 2022 Ke Li

Language dc:language

en, eng

Handle dc:identifier

https://hdl.handle.net/2142/115553

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F115553