  While machine learning models are typically trained to solve prediction
problems, we might often want to use them for optimization problems. For
example, given a dataset of proteins and their corresponding fluorescence
levels, we might want to optimize for a new protein with the highest possible
fluorescence. This kind of data-driven optimization (DDO) presents a range of
challenges beyond those in standard prediction problems, since we need models
that successfully predict the performance of new designs that are better than
the best designs seen in the training set. It is not clear theoretically when
existing approaches can even perform better than the naive approach that simply
selects the best design in the dataset. In this paper, we study how structure
can enable sample-efficient data-driven optimization. To formalize the notion
of structure, we introduce functional graphical models (FGMs) and show
theoretically how they can provide for principled data-driven optimization by
decomposing the original high-dimensional optimization problem into smaller
sub-problems. This allows us to derive much more practical regret bounds for
DDO, and the result implies that DDO with FGMs can achieve nearly optimal
designs in situations where naive approaches fail due to insufficient coverage
of the offline data. We further present a data-driven optimization algorithm
that inferes the FGM structure itself, either over the original input variables
or a latent variable representation of the inputs.
