论文标题
从结构化样品中优化覆盖功能
Optimization from Structured Samples for Coverage Functions
论文作者
论文摘要
我们重新审视样品（OPS）模型的优化，该模型研究了直接从样本数据中优化目标函数的问题。先前的结果表明，我们无法使用多个多物种形式的许多独立样本获得$ \ {s_i，f（s_i）\} _ {i = 1}^t $（Balkanski等，2017）的许多独立样本，即使覆盖范围功能是$（1-- pm pm pem abal），这些sampe（即使这些sampe），我们也可以使用这些Sampe（BADIS），即大多数函数值可以通过高概率就可以很好地学习。在这项工作中，为了避免OP的不可能结果，我们提出了一个更强的模型，称为“结构化样本（OPS）的优化”，以覆盖功能，其中数据样本编码了功能的结构信息。我们表明，在对样本分布的三个一般假设下，我们可以设计有效的OPSS算法，以实现最大覆盖范围问题的恒定近似值。我们进一步证明了这些假设下的恒定下限，这在不考虑计算效率时会很紧。此外，我们还表明，如果我们删除了三个假设中的任何一个，则最大覆盖范围问题的OPS没有恒定的近似。
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 - ε)$-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.
