{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/115553"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/115553","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Topics in high-dimensional linear bandits and approximate Bayesian sampling","abstract":"Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2024-05-01","abstract_html":"Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2024-05-01","abstract_has_math":false,"creators":["Li, Ke"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Statistics","degree_department":null,"school":null,"contributors":["Narisetty, Naveen N","Yang, Yun","Liang, Feng","Fellouris, Georgios"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2022,"date_issued":"2022-05","date_published":"2022-05","updated_at":"2026-07-22T22:24:54Z","subjects":["contextual linear bandit","high-dimensional statistics","variable selection","Bayesian inference","generative model","optimal transport"],"languages":["en","eng"],"rights":["Copyright 2022 Ke Li"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2142/115553","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Narisetty, Naveen N","Yang, Yun","Liang, Feng","Fellouris, Georgios"]},{"key":"dc:creator","label":"Author","values":["Li, Ke"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2022-05","2022-04-18"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Statistics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["contextual linear bandit","high-dimensional statistics","variable selection","Bayesian inference","generative model","optimal transport"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en","eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2022 Ke Li"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://hdl.handle.net/2142/115553"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2024-05-01","The student, Ke Li, accepted the attached license on 2022-04-15 at 16:47.","The student, Ke Li, submitted this Dissertation for approval on 2022-04-15 at 17:07.","This Dissertation was approved for publication on 2022-04-18 at 16:29.","DSpace SAF Submission Ingestion Package generated from Vireo submission #17716 on 2022-11-11 at 12:05:52","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."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Topics in high-dimensional linear bandits and approximate Bayesian sampling"]}]}],"canonical_facts":{"dc:contributor":["Narisetty, Naveen N","Yang, Yun","Liang, Feng","Fellouris, Georgios"],"dc:creator":["Li, Ke"],"dc:date":["2022-05","2022-04-18"],"dc:description":["Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2024-05-01","The student, Ke Li, accepted the attached license on 2022-04-15 at 16:47.","The student, Ke Li, submitted this Dissertation for approval on 2022-04-15 at 17:07.","This Dissertation was approved for publication on 2022-04-18 at 16:29.","DSpace SAF Submission Ingestion Package generated from Vireo submission #17716 on 2022-11-11 at 12:05:52","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."],"dc:format":["application/pdf"],"dc:identifier":["https://hdl.handle.net/2142/115553"],"dc:language":["en","eng"],"dc:rights":["Copyright 2022 Ke Li"],"dc:subject":["contextual linear bandit","high-dimensional statistics","variable selection","Bayesian inference","generative model","optimal transport"],"dc:title":["Topics in high-dimensional linear bandits and approximate Bayesian sampling"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Statistics"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:54Z"}