Improved Active Learning via Dependent Leverage Score Sampling

Thank you very much for the positive review of our work. We will fix the issue with the citation, and also take a closer look at the SXZ22 paper you reference. We think it would be very exciting to come up with a method that matches the O(d/epsilon) theoretical guarantee of Randomized BSS but also performs better than i.i.d. leverage score sampling in practice. We are honestly unsure if our pivotal sampling strategy could lead to such a method, as our improved bound for polynomial regression very strongly relies on additional structure in that problem.

Thank you for the supportive review and positive feedback.

A few reviewers asked about comparison to the Randomized BSS method from [Chen, Price, 2019] and we will consider elevating the experiment from the appendix and adding additional results. One thing we want to note is that Randomized BSS is quite complex, and involves several parameters that must be tuned well for the method to achieve low sample complexity. For the experiment in the appendix, we tuned these parameters optimally for one specific problem, and the method was able to slightly outperform leverage score sampling. However, our best general purpose implementation (with parameters fixed across different problems) performed worse than the baseline i.i.d. leverage score sampling, which is why we did not include the results to begin with. We are not aware of other implementations or experimental evaluations of the method. An exciting direction for future work is to find a method that matches the tighter theoretical guarantees of Randomized BSS (for general regression problems) while also outperforming i.i.d. leverage score sampling in practice.

Thank you for the supportive review and recognizing the methodological and theoretical contributions of the work. Reviewer hDW2 also asked about runtime, so I will paste the response below. We agree that the paper would benefit from increased discussion and experimental results on runtime.

We will also consider additional baselines. We did implement the randomized BSS method from [Chen, Price 2019], although found it was uncompetitive (there is an experiment in Appendix D). Another option would be to consider e.g. square root leverage scores sampling, which was discussed in “A Statistical Perspective on Algorithmic Leveraging” by Ma, Mahoney, Yu. We are not 100% sure what method the reviewer is referring to as “maximum leverage score sampling”. Do you mean the method from the paper “Provable Deterministic Leverage Score Sampling” by Papailiopoulos, Kyrillidis, and Boutsidis? That paper selects the rows in A with the largest leverage scores. While this method works well in many settings, it performs very poorly for polynomial regression and related “continuous” problems where nearby points typically have similar leverage scores. For example, for polynomial regression, maximum leverage score sampling would only select samples right near the edge of the interval or box that we are fitting the function over.

Comments on runtime to Reviewer hDW2: On average, we found that our PCA-based pivotal methods run in approximately 125% of the time of the baseline i.i.d. leverage score sampling method and the coordinate-wise splitting method runs in 114% of the time. So, the PCA method is slower, but the overhead is low overall.

The reason for the low-overhead is that PCA is being run on low-dimensional data points. E.g., for a degree s polynomials in q=2 dimensions, PCA is being run on q=2 dimensional points, even though the dimension of the polynomial regression problem is d = O(s^2) (in our experiments, d = 60+). Additionally, since the size of the PCA problems is decreasing by a factor of 2 at every step of the splitting method, the total runtime cost of constructing the pivotal sampling tree is roughly O(nq^2log n). Accordingly, we found that the complexity of our method was dominated by the cost of computing leverage scores for the matrix A, which naively takes O(nd^2). This cost is also incurred by naive i.i.d. sampling. We do note that faster algorithms for approximating leverage scores are well studied and can be used instead. See e.g., the paper “Fast approximation of matrix coherence and statistical leverage” by Drineas, Magdon-Ismail, Mahoney, and Woodruff, and follow-up work, which improves the cost to time O(nd + d^3).

Thank you for the accurate summary of our contributions and suggestions. We respond to specific comments below, but please let us know if you have any additional questions.

– The empirical evaluation lacks clarity regarding the improvements… We agree with the suggestion here. The 50% improvement can be seen most clearly in Appendix D, where Table 1 and Table 2 compare the number of samples needed to achieve a given level of error. We are tight on space, but will plan on moving at least one of these tables up to the main experiments section in the final version of the paper.

– It would be interesting to explore whether the pivotal sampling method has other implications for different norms. We think this is a really nice question for future work, especially given recent progress on understanding optimal sampling results for polynomial regression in various norms (see e.g. the cited work by [Meyer et al. 2023]). We would optimistically predict that we could similarly remove log(d) factors using tournament style methods like pivotal sampling, although the theoretical analysis will have to differ significantly. It would also be interesting to establish a general result like Theorem 1.1 for other norms, e.g. for lp norms, for which the optimal sampling probabilities are based on lp Lewis weights.

– If the running time is a major concern in large-scale systems or datasets, it isn’t clear if a PCA-based approach is always feasible. We will plan on adding some discussion on runtime to the final version of the paper. We can also add some basic experimental results. On average, we found that our PCA-based pivotal methods run in approximately 125% of the time of the baseline i.i.d. leverage score sampling method and the coordinate-wise splitting method runs in 114% of the time. So, the PCA method is slower as the reviewer notes, but the overhead is low overall.

The reason for the low-overhead is that PCA is being run on low-dimensional data points. E.g., for a degree s polynomials in q=2 dimensions, PCA is being run on q=2 dimensional points, even though the dimension of the polynomial regression problem is d = O(s^2) (in our experiments, d = 60+). Additionally, since the size of the PCA problems is decreasing by a factor of 2 at every step of the splitting method, the total runtime cost of constructing the pivotal sampling tree is roughly O(nq^2log n). Accordingly, we found that the complexity of our method was dominated by the cost of computing leverage scores for the matrix A, which naively takes O(nd^2). This cost is also incurred by naive i.i.d. sampling. We do note that faster algorithms for approximating leverage scores are well studied and can be used instead. See e.g., the paper “Fast approximation of matrix coherence and statistical leverage” by Drineas, Magdon-Ismail, Mahoney, and Woodruff, and follow-up work, which improves the cost to time O(nd + d^3).

• Can the main theorem be stated in terms of the parameter D_inf? This is a good suggestion, and we will plan on doing so, as well as adding explicit constants as the reviewer suggestions. The final sample complexity will be c*(d log d)(1/D_inf^2) + (d/epsilon)(1/D_inf).

Finally, we thank the reviewer for suggestions on experiments to add, and will consider the random permutation method as a baseline. We actually did implement the [Chen, Price 2019] method, and include one experiment in the appendix (Figure 8,c). We spent quite a bit of time optimizing the choice of constants in that method. We were ultimately able to beat i.i.d leverage score sampling, but only by a little bit. The method requires notably more samples than pivotal sampling.

Thank you for the thoughtful response. We respond below to your questions about the connection of our results to prior work. Please let us know if you have any additional questions.

The first Lemma asked about, Lemma B.1, is not our result, but rather a result we use from [Kaufman et al., 2022]. This lemma is a strong generalization of prior matrix Bernstein inequalities (including the one cited by the reviewer) because prior matrix Bernstein bounds only apply when Y_1, …, Y_n are sampled independently. Lemma B.1 applies to non-independent sampling distributions (like pivotal sampling) as long as the distribution is homogenous and satisfies the l_infinity independence guarantees. [Kaufman et al., 2022]’s result is the culmination of a line of work on relaxing the independence requirement. For example, prior work in [Kyng, Song, 2018] proved matrix concentration inequalities for non-independent strongly Rayleigh distributions, which is a subset of l_infinity independent distributions. Similarly, approximate matrix-multiplication results were known for independent sampling, but not for dependent distributions. Our main technical contribution in proving Theorem 1.1 is to show that approximate matrix-multiplication can also be generalized to the case when sampling is dependent, but satisfies l_infinity independence. This proof is on Page 14 and 15 of the appendix. Combining with the existing results from [Kaufman et al., 2022] establishes Theorem 1.1. Finally, we stress that some sort of correlation (non-independence) between samples is necessary to produce a spatially well-balanced distribution.

The contribution of Theorem 1.2 differs from that of Theorem 1.1 because the result of Theorem 1.2 (which is specialized to fitting polynomials) has sample complexity O(d) instead of O(dlogd). Independent leverage score sampling requires O(dlogd) samples for fitting degree d polynomials, so Theorem 1.2 shows a concrete setting where pivotal sampling gives a provably stronger bound (i.e., it eliminates a log d). To prove this bound, we cannot use matrix concentration inequalities at all (even those of [Kaufman et al., 2022]) since these bounds inherently involve a log d factor. So, we instead prove the required subspace embedding guarantee “from scratch” using tools from polynomial approximation theory. For example, one ingredient of the proof is that we establish a tighter non-asymptotic bound relating the leverage scores for polynomial regression to the Chebyshev density (Theorem C.3).