Computing Approximate $\ell_p$ Sensitivities
This work addresses a bottleneck in dimensionality reduction for regression by enabling faster sensitivity approximations, which is incremental but improves practical efficiency for data analysis tasks.
The paper tackles the problem of efficiently approximating ℓ_p sensitivities, which are important for dimensionality reduction in regression, by providing algorithms that compute approximations with reduced computational cost, such as an O(n/α) algorithm for ℓ_1 sensitivities and O(√d) for total sensitivity, and experimentally shows that real-world datasets often have lower total sensitivity than theoretical bounds.
Recent works in dimensionality reduction for regression tasks have introduced the notion of sensitivity, an estimate of the importance of a specific datapoint in a dataset, offering provable guarantees on the quality of the approximation after removing low-sensitivity datapoints via subsampling. However, fast algorithms for approximating $\ell_p$ sensitivities, which we show is equivalent to approximate $\ell_p$ regression, are known for only the $\ell_2$ setting, in which they are termed leverage scores. In this work, we provide efficient algorithms for approximating $\ell_p$ sensitivities and related summary statistics of a given matrix. In particular, for a given $n \times d$ matrix, we compute $α$-approximation to its $\ell_1$ sensitivities at the cost of $O(n/α)$ sensitivity computations. For estimating the total $\ell_p$ sensitivity (i.e. the sum of $\ell_p$ sensitivities), we provide an algorithm based on importance sampling of $\ell_p$ Lewis weights, which computes a constant factor approximation to the total sensitivity at the cost of roughly $O(\sqrt{d})$ sensitivity computations. Furthermore, we estimate the maximum $\ell_1$ sensitivity, up to a $\sqrt{d}$ factor, using $O(d)$ sensitivity computations. We generalize all these results to $\ell_p$ norms for $p > 1$. Lastly, we experimentally show that for a wide class of matrices in real-world datasets, the total sensitivity can be quickly approximated and is significantly smaller than the theoretical prediction, demonstrating that real-world datasets have low intrinsic effective dimensionality.