A lasso-based sparse knowledge gradient policy for sequential optimal learning

Yan Li, Han Liu, Warren Buckler Powell

Research output: Contribution to conferencePaper

2 Scopus citations

Abstract

We propose a sequential learning policy for noisy discrete global optimization and ranking and selection (R&S) problems with high dimensional sparse belief functions, where there are hundreds or even thousands of features, but only a small portion of these features contain explanatory power. Our problem setting, motivated by the experimental sciences, arises where we have to choose which experiment to run next. Here the experiments are time-consuming and expensive. We derive a sparse knowledge gradient (SpKG) decision policy based on the ℓ1-penalized regression Lasso to identify the sparsity pattern before our budget is exhausted. This policy is a unique and novel hybrid of Bayesian R&S with a frequentist learning approach. Theoretically, we provide the error bound of the posterior mean estimate, which has shown to be at the minimax optimal √slog p/n rate. Controlled experiments on both synthetic data and real application for automatically designing experiments to identify the structure of an RNA molecule show that the algorithm efficiently learns the correct set of nonzero parameters. It also outperforms several other learning policies.

Original languageEnglish (US)
Pages417-425
Number of pages9
StatePublished - Jan 1 2016
Event19th International Conference on Artificial Intelligence and Statistics, AISTATS 2016 - Cadiz, Spain
Duration: May 9 2016May 11 2016

Conference

Conference19th International Conference on Artificial Intelligence and Statistics, AISTATS 2016
CountrySpain
CityCadiz
Period5/9/165/11/16

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence
  • Statistics and Probability

Fingerprint Dive into the research topics of 'A lasso-based sparse knowledge gradient policy for sequential optimal learning'. Together they form a unique fingerprint.

  • Cite this

    Li, Y., Liu, H., & Powell, W. B. (2016). A lasso-based sparse knowledge gradient policy for sequential optimal learning. 417-425. Paper presented at 19th International Conference on Artificial Intelligence and Statistics, AISTATS 2016, Cadiz, Spain.