Optimization from Structured Samples for Coverage Functions
  We revisit the optimization from samples (OPS) model, which studies the
problem of optimizing objective functions directly from the sample data.
Previous results showed that we cannot obtain a constant approximation ratio
for the maximum coverage problem using polynomially many independent samples of
the form $\{S_i, f(S_i)\}_{i=1}^t$ (Balkanski et al., 2017), even if coverage
functions are $(1 - \epsilon)$-PMAC learnable using these samples (Badanidiyuru
et al., 2012), which means most of the function values can be approximately
learned very well with high probability. In this work, to circumvent the
impossibility result of OPS, we propose a stronger model called optimization
from structured samples (OPSS) for coverage functions, where the data samples
encode the structural information of the functions. We show that under three
general assumptions on the sample distributions, we can design efficient OPSS
algorithms that achieve a constant approximation for the maximum coverage
problem. We further prove a constant lower bound under these assumptions, which
is tight when not considering computational efficiency. Moreover, we also show
that if we remove any one of the three assumptions, OPSS for the maximum
coverage problem has no constant approximation.
