Reproduce “Improved Active Learning via Dependent Leverage Score Sampling” 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
Atsushi Shimizu, Xiaoou Cheng, Christopher Musco, Jonathan Weare
Researchers at New York University developed an active learning method for agnostic linear regression that combines leverage score sampling with a spatially-aware pivotal sampling strategy. This approach generates more evenly distributed samples while maintaining theoretical guarantees, achieving up to a 50% reduction in required samples for scientific computing tasks and proving an optimal O(d/epsilon) sample complexity for polynomial regression.
Key insights
- Sampling algorithms that use leverage score marginals and satisfy a weak 'one-sided L-infinity independence' condition (like pivotal sampling) can achieve the same O(d log d + d/epsilon) sample complexity as independent leverage score sampling in the general case.
- For polynomial regression over an interval, the proposed pivotal sampling method achieves an improved, optimal sample complexity of O(d + d/epsilon) by leveraging the specific structure of polynomial leverage scores.
- Spatially-aware dependent sampling can effectively combine strong theoretical guarantees with the practical benefit of generating spatially well-distributed samples, bridging a gap in active learning.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.