Topics in high-dimensional linear bandits and approximate Bayesian sampling

Li, Ke

Permalink

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

Description

Title

Topics in high-dimensional linear bandits and approximate Bayesian sampling

Author(s)

Li, Ke

Issue Date

2022-04-18

Director of Research (if dissertation) or Advisor (if thesis)

• Narisetty, Naveen N
• Yang, Yun

Doctoral Committee Chair(s)

• Narisetty, Naveen N
• Yang, Yun

Committee Member(s)

• Liang, Feng
• Fellouris, Georgios

Department of Study

Statistics

Discipline

Statistics

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

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

Abstract

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{\alpha+1}{2}}T^{\frac{1-\alpha}{2}}+\log T\big)$, for the cumulative regret, in terms of horizon $T$, dimension $d$ and a margin parameter $\alpha\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 $\alpha$ 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_1$-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^2 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.

Graduation Semester

2022-05

Type of Resource

Thesis

Copyright and License Information

Copyright 2022 Ke Li

Owning Collections