Coresets for Estimating Means and Mean Square Error with Limited Greedy Samples
This work addresses the challenge of reducing sampling costs in data-intensive applications like graph analysis and sensor networks, offering a scalable solution with theoretical guarantees, though it appears incremental as it builds on coreset and greedy methods.
The paper tackles the problem of efficiently estimating function means and mean square error when full data sampling is costly by introducing a greedy coreset selection algorithm for graphs, which provably bounds estimation error and demonstrates faster empirical convergence than random selection and clustering methods on tasks like semi-supervised node classification and sensor placement.
In a number of situations, collecting a function value for every data point may be prohibitively expensive, and random sampling ignores any structure in the underlying data. We introduce a scalable optimization algorithm with no correction steps (in contrast to Frank-Wolfe and its variants), a variant of gradient ascent for coreset selection in graphs, that greedily selects a weighted subset of vertices that are deemed most important to sample. Our algorithm estimates the mean of the function by taking a weighted sum only at these vertices, and we provably bound the estimation error in terms of the location and weights of the selected vertices in the graph. In addition, we consider the case where nodes have different selection costs and provide bounds on the quality of the low-cost selected coresets. We demonstrate the benefits of our algorithm on the semi-supervised node classification of graph convolutional neural network, point clouds and structured graphs, as well as sensor placement where the cost of placing sensors depends on the location of the placement. We also elucidate that the empirical convergence of our proposed method is faster than random selection and various clustering methods while still respecting sensor placement cost. The paper concludes with validation of the developed algorithm on both synthetic and real datasets, demonstrating that it outperforms the current state of the art.