Sublinear time methods with statistical guarantees
(Holger Dette and Axel Munk)
Exploiting the fact that in a given sample observations typically carry a different amount of statistical information, sublinear time methods are developed for central estimation problems in the common linear model, accompanied by statistical performance guarantees. Optimal subsampling strategies are designed for data reduction, allowing for computationally tractable estimates of the parameter in massive data sets, and adaptive variants of binary segmentation are developed which shall perform multiple change-point detection even in sublinear time.