Optimal Subsampling with Influence Functions
Subsampling is a common and often effective method to deal with the computational challenges of large datasets. However, for most statistical models, there is no well-motivated approach for drawing a non-uniform subsample. We show that the concept of an asymptotically linear estimator and the associated influence function leads to asymptotically optimal sampling probabilities for a wide class of popular models. This is the only tight optimality result for subsampling we are aware of as other methods only provide probabilistic error bounds or optimal rates. We also show that these optimal weights can differ depending on whether the task is parameter estimation or prediction. Furthermore, for linear regression models, which have well-studied procedures for non-uniform subsampling, we empirically show our optimal influence function based method outperforms previous approaches even when using approximations to the optimal probabilities.
The paper presents a sampling methodology for statistical estimation tasks, in which the weight of a sample (to be included in final estimation) is determined by the sample's Gateaux derivative. The authors point out that Gateaux derivatives are defined for several estimators of note, and that asymptotically characterize estimate errors for so-called asymptotically linear estimators, which is also a very broad class. The authors then propose a probabilistic sampling method in which samples are included with a probability proportional to the norm of the gateaux derivative, and show that this is optimal, in that it minimizes the trace of the variance of the estimator under certain conditions. They then proceed to apply this method to least squares estimation, GLMs, and quantile regression, on all of which estimation leads to improved performance (both in estimation and prediction) compared to alternative methods for subsampling.  This is an interesting, solid contribution, that addresses a fundamental problem. On the negative side, the paper is unpolished/somewhat written in a rush, and is not appropriately positioned with respect to related work. This seems a significant drawback when dealing with a topic as fundamental as sampling.  To begin with, the related work (there is no dedicated section) is very sparse, citing mostly TCS papers; what is the state of the art in sampling in statistics literature? Have gateaux derivatives been used before for this purpose? How does the present work relate to other  uses of gateaux derivatives in statistics and estimation in particular?   On a similar vein, the paper mentions several results, presumably already known without any citations or context whatsoever. Asymptotically linear estimators are an example. Clearly, gateaux derivatives for the specific estimation tasks in Section 4 must also have been derived before, and although the discussion of the resulting sampling methods is interesting, again credit for this is due. Similarly, competing sampling methods are sometimes vaguely disparaged as "only provid(ing) probabilistic or rate guarantees". What are the competing methods, and what is the exact formulation of their probabilistic and rate guarantees?  Given the broad array of estimators termed to be asymptotically optimal, one would expect more examples listed and evaluated (beyond the usual LSE and GLS). The same holds for competing sampling methods.  Finally, the theoretical statement (Theorems 1 and 2) and their preamble are too dense, making it difficult to assess the breadth and applicability of the conditions required  for the theorems to hold.  ---Added post-rebuttal--- I appreciate the authors' detailed response, and the explanation of the lack of work in statistics on subsampling. If some of these comments could make it to the paper, that would be great. --------------------------------