Computing Approximate $\ell_p$ Sensitivities

Summary

The authors propose randomized algorithms to approximate $\ell_p$ sensitivity functions for $p \in [1,\infty)$, which extend leverage scores beyond the $\ell_2$ norm. The functions they consider are: 1. Estimating all sensitivities, 2. Estimating total sensitivity, and 3. Estimating maximum sensitivity. They provide different types of approximations for each task. For task 1, they give an additive error, constant factor approximation. For task 2, they give a relative error, $(1+O(\gamma))$ approximation ($\gamma \in (0,1)$). And for task 3, they give a constant factor relative error approximation. They demonstrate their algorithm initially for $\ell_1$ and then generalize it to all $\ell_p$ norms with $p > 1$. They also prove a hardness result by reducing $\ell_p$ regression to $\ell_p$ sensitivity estimation. Additionally, they implement their algorithm to estimate all sensitivities on 2 existing datasets and compare the average and maximum approximation ratios with the theoretical results. The main techniques used in the algorithms involve hashing using Rademacher combinations, computing sensitivities with respect to subspace embeddings, splitting matrix rows based on leverage score intervals, and utilizing existing results for $\ell_\infty$ subspace embeddings.

Strengths

The problem of sensitivity estimation is useful for regression problems and has received limited attention for general $p$. Approximating total sensitivity is particularly significant in obtaining the sample complexity of learning arbitrary functions. The algorithms presented are an interesting combination of known results from sensitivity sampling framework and RNLA. Specifically, their result for approximating total sensitivity is interesting because the computational complexity does not depend polynomially on the number of rows of the matrix, which is usually very large. Finally, the analysis of the proposed algorithms is largely clear, helping to understand the guarantees of their algorithms. Overall, this paper is a significant contribution to the field of sensitivity sampling and dimensionality reduction.

Weaknesses

- Algorithm 4 does not appear to be significantly novel, except for integrating generalized sensitivity to an existing $\ell_\infty$ subspace embedding technique, but the task is coherent with the other tasks mentioned. - While the motivation for total sensitivity is clear, the authors have not motivated the problem of estimating maximum sensitivity. However, this might be because I am not familiar with it. - I noticed some typos, missing definitions.. In Algorithm 3, it is unclear where the vector of leverage scores $\tau(C)$ is being used. Additionally, $\omega$ is not defined, which I am assuming to be the matrix multiplication exponent.

Questions

I would like to understand the comparison between approximate $\ell_p$ sensitivities and Lewis weights. From what I understand, it is known that Lewis weights cover sensitivities, at least for $p \in [1,2]$. The authors mentioned that Lewis weights are a crude approximation to sensitivities, although Lewis weights are used as a subroutine to obtain subspace embedding in their proposed algorithms. I am curious to see the benefits that an additive error approximation to sensitivities have over Lewis weight sampling.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

It would be beneficial if the authors consider adding a section addressing the open problems and limitations.

Summary

The paper gives algorithms to compute, approximately, the individual sensitivity scores, total sensitivity and maximum sensitivity, for $\ell_p $ norms. The approximation for the individual sensitivity scores is additive while a relative error approximation is obtained for both total and maximum sensitivity. Calculating exact sensitivity scores often being a computationally expensive problem, the authors provide faster algorithms that use techniques of multiplication with Rademacher vectors and hashing. The authors also empirically validate their results on real datasets.

Strengths

Strengths of the paper 1) Methods of constructing coresets for various ML problems rely heavily on good approximation to sensitivity scores. As such the paper is important and will be of interest to the community. 2) Empirical Results for various values of $p$ which are not usually seen in literature.

Weaknesses

To me the main weakness appears to be with the writing and clarity of the paper (may be because of space constraints) and also to an extent comparison and discussion with some related works. Here I list out some of the questions/ suggestions that I have: 1) The authors mention Lewis weights as crude over approximation to sensitivity scores for $\ell_p$. However, another way to sample rows for $\ell_p$ subspace embeddings is using the row norms of a well-conditioned basis. The authors have not discussed much from the area. It would be interesting to compare if for some well-conditioned basis, the row norms correspond to some approximation of sensitivity scores. 2) In all the algorithms the authors rely on constructing SA which is an $\ell_1$ subspace embedding. There is good amount of work on $\ell_1$ subspace embeddings using 1-stable Cauchy random variables, exponential random variables etc. It has not been compared with. It would be useful to give a table that compares these methods in terms of time, approximation factors and no. of rows required etc. also how is SA calculated in this work and what is the time taken for it? Please clarify. 3) Also, algorithm 2 requires computation of leverage scores of A. Are they calculated exactly in which case the time required will be $O(nd^2)$ and if they are also approximated, how does the approximation factor figure in your guarantees? 4) The implications of the lower bound are not clarified. Please elaborate. 5) It would be useful to give some motivation as to why maximum of the sensitivity scores is important. Overall, the paper uses some known techniques in Randomized numerical linear algebra literature to calculate the approximations to $\ell_p$ sensitivities. However improved writing, better clarification of exact contributions and comparison with existing literature will strengthen it.

Questions

Please see weaknesses section.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

Please see weaknesses section.

Summary

This paper proposes a randomized algorithm for efficiently approximating the $\ell_p$ sensitivities, with a constant approximation parameter guaranteed.

Strengths

This paper presents several novel randomized algorithms for approximating $\ell_p$ sensitivities and related statistics, based on two key ideas: (1) Using subspace embeddings to efficiently approximate $\|Ax\|_p$ that avoids computing $Ax$ on the whole dataset (2) Randomly hashing the dataset into small subsets and computing the sensitivities for each subset separately Given the above, this work provides efficient approximations of the sensitivities of all data samples, the total sensitivity, and the maximum one. The resulting algorithms are good contributions to the problem of estimating sensitivities that fill in the blank of computing $\ell_p$ sensitivities efficiently. The theoretical guarantees appear to be solid and correct, which is further verified by several experiments.

Questions

I am a bit confused about the definition of $\boldsymbol{S}$ in line 191, where the size of $\boldsymbol{S}$ is $r$ by $d$, should it be $r$ by $n$? Also, in lines 189 and 193 it is said $\boldsymbol{S}$ to be 'diagonal' while this seems to contradict its definition, please let me know if I miss anything.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

NA

Summary

Given a matrix $A \in \mathbb{R}^{n \times d}$ and $p \in (0, \infty)$, the $l_p$ sensitivity of a vector $a \in \mathbb{R}^d$ with respect to $A$ is defined as $\sigma_p(a) := \max_x |a^\top x|^p / |Ax|_p^p$. It is known that by sampling each row $a_i$ of $A$ with probability proportional to (an upper bound on) $\sigma_p(a_i)$, we can obtain a coreset of $A$ with respect to the $l_p$ loss. Therefore, estimating $\sigma_p(a_i)$ quickly is desirable. This work presents three fast approximation algorithms for $l_p$ sensitivities. The main focus is on the case where $p = 1$, so I will state the results specifically for that case: - An algorithm that provides an estimate $\tilde{\sigma}$ such that $\sigma_1(a_i) \leq \tilde{\sigma} \leq \sigma_1(a_i) + \alpha/n \mathfrak{S}_1(A)$, where $\mathfrak{S}_1(A)$ is the sum of $l_1$ sensitivities. The algorithm's running time is $O(n/\alpha (nnz(A) + d^\omega) + n)$, where $\omega$ is the matrix multiplication exponent. - An algorithm that provides an estimate $\tilde{\sigma}$ such that $\mathfrak{S}_1(A) \leq \tilde{\sigma} \leq (1 + \gamma)\mathfrak{S}_1(A)$. The running time of this algorithm is $O(\sqrt{d} (nnz(A) + d^\omega))$, significantly faster than the naive bound of $O(n (nnz(A) + d^\omega))$. - An algorithm that provides an estimate $\tilde{\sigma}$ such that $\max_i \sigma_1(a_i) \leq \tilde{\sigma} \leq \sqrt{d} \max_i \sigma_1(a_i)$. The running time for this algorithm is $O(d(nnz(A) + d^\omega))$, also faster than the naive bound. The authors showed that $l_p$ regression reduces to $l_p$ sensitivity calculation, implying that designing a fast algorithm for $l_p$ sensitivity requires a fast algorithm for $l_p$ regression. Experimental results are provided to validate the theoretical bounds.

Strengths

The algorithm effectively utilizes $l_p$ subspace embedding to enhance its speed. Additionally, the recursive approach employed for computing total sensitivity is intriguing.

Weaknesses

- There are reservations about the usefulness of Theorem 1.2. It is possible to estimate sensitivities in $O(n (nnz(A) + d^\omega))$ time, as indicated in Fact 2.4. This means that, to achieve a significant speedup, $\alpha$ needs to be a function of $n$, which then results in a substantial additive error. - The usefulness of Theorem 1.3 is unclear. Although the sum provides a bound on the coreset's size, it is not evident when one would solely desire the bound without the coreset itself. - Similarly, the usefulness of Theorem 1.4 is not clear.

Questions

- This is just a comment, but "additive error of $O(\alpha^p)$" should be "additive error of $\alpha^p/n \cdot \mathfrak{S}_p(A)$". - What is the meaning of the "$\rho$-factor subspace embedding" in Algorithm 2? Should it be "$\rho$-approximate subspace embedding"?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

The limitations are not clearly mentioned.