# Optimization from Structured Samples for Coverage Functions

arXiv: https://arxiv.org/abs/2007.02738 · HTML: https://mlsanity.com/paper/2007.02738/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Jul 2020.

## Built on by (most cited first, 6 of 6)

- [Network Inference and Influence Maximization from Samples](https://mlsanity.com/paper/2106.03403/) (2021)
- [Benchmarking PtO and PnO Methods in the Predictive Combinatorial Optimization Regime](https://mlsanity.com/paper/2311.07633/) (2023)
- [Offline Learning for Combinatorial Multi-armed Bandits](https://mlsanity.com/paper/2501.19300/) (2025)
- [Unifying and Optimizing Data Values for Selection via Sequential Decision-Making](https://mlsanity.com/paper/2502.04554/) (2025)
- [Learning Submodular Sequencing from Samples](https://mlsanity.com/paper/2409.05265/) (2024)
- [Rethinking Learnability in Offline Data-driven Optimization](https://mlsanity.com/paper/2609.01493/) (2026)

## Abstract (arXiv)

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 Si, f(Si)i=1t (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.