Importance Sampling via Local Sensitivity

Given a loss function F:X rightarrow R^+ that can be written as the sum of losses over a large set of inputs a1,ldots, an, it is often desirable to approximate F by subsampling the input points. Strong theoretical guarantees require taking into account the importance of each point, measured by how much its individual loss contributes to F(x). Maximizing this importance over all x ∈ X yields the sensitivity score of ai. Sampling with probabilities proportional to these scores gives strong guarantees, allowing one to approximately minimize of F using just the subsampled points. Unfortunately, sensitivity sampling is difficult to apply since (1) it is unclear how to efficiently compute the sensitivity scores and (2) the sample size required is often impractically large. To overcome both obstacles we introduce local sensitivity, which measures data point importance in a ball around some center x0. We show that the local sensitivity can be efficiently estimated using the leverage scores of a quadratic approximation to F and that the sample size required to approximate F around x0 can be bounded. We propose employing local sensitivity sampling in an iterative optimization method and analyze its convergence when F is smooth and convex.