Reproduce “Approximate Selection with Guarantees using Proxies” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Daniel Kang, Edward Gan, Peter Bailis, Tatsunori Hashimoto, Matei Zaharia
Kang et al. from Stanford University developed novel algorithms for approximate selection queries that provide statistical accuracy guarantees for identified record sets while efficiently utilizing limited budgets for expensive oracle labels. Their SUPG system prevents catastrophic failures common in prior methods and achieves up to 30x higher recall or precision for the same cost.
Key insights
- Statistical accuracy guarantees are essential and achievable for approximate selection, transforming 'best-effort' approaches into reliable tools for high-stakes applications.
- Importance sampling, especially with weights proportional to the square root of the proxy confidence, dramatically improves the efficiency of oracle budget usage.
- Existing approximate query processing methods without statistical bounds can catastrophically fail to meet targeted accuracies, especially under model drift, highlighting the necessity of guarantees.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.