# Adaptive Sampling for Convex Regression

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Aug 2018.

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

- [Problem Dependent View on Structured Thresholding Bandit Problems](https://mlsanity.com/paper/2106.10166/) (2021)
- [An Efficient Minimax Optimal Estimator For Multivariate Convex Regression](https://mlsanity.com/paper/2205.03368/) (2022)

## Abstract (arXiv)

In this paper, we introduce the first principled adaptive-sampling procedure for learning a convex function in the L_∞ norm, a problem that arises often in the behavioral and social sciences. We present a function-specific measure of complexity and use it to prove that, for each convex function fstar, our algorithm nearly attains the information-theoretically optimal, function-specific error rate. We also corroborate our theoretical contributions with numerical experiments, finding that our method substantially outperforms passive, uniform sampling for favorable synthetic and data-derived functions in low-noise settings with large sampling budgets. Our results also suggest an idealized "oracle strategy", which we use to gauge the potential advance of any adaptive-sampling strategy over passive sampling, for any given convex function.