Summary
The paper studies algorithms to efficiently sample a row from a matrix $A = U_1 \odot U_2 \odot ... \odot U_N$ with probability proportional to the leverage scores of $A$.
Here, $B \odot C$ denotes the _Khatri-Rao_ product of $B$ and $C$, or the column-wise kronecker-product of the columns of $B$ and $C$.
In particular, this means that $A$ has a small number of columns $R$, but has an exponential number of rows $\prod_{j=1}^N |I_j|$ (where $U_j \in \mathbb{R}^{|I_j| \times R}$).
This exponential blowup in the number of rows of $A$ in the core computational focus on this paper, as well as several related papers in the area.
This paper's technical contribution is in proposing a data structure that can preprocess $U_1, ..., U_N$ such that a row of $A$ can be sampled with probability proportional to its leverage score.
This data structure's space complexity matches the sizes of the input, and at query time it takes only $O(NR^2 \log \max \\{I_j, R\\})$ amortized time per row sampled.
This new data structure is based on "binary-tree inversion sampling", a binary search algorithm that can help sample from distributions efficiently, and is used to speed up a computational bottleneck in a known approach to sample leverage scores from Khatri-Rao products.
Theoretical results demonstrate the correctness of this algorithm, and experiments demonstrate the effectiveness of this algorithm.
Strengths
The paper is well written, nicely motivated, pretty easy to understand, has a clear presentation of the subproblem it speeds up, and provides good context relative to existing work in the area (afaik; I'm no expert in tensor algorithms).
**Originality and Quality:** A fine line needs to be drawn here, and this is the subtlest point of my review. Per the authors' account, existing work in leverage score sampling from Khatri-Rao products exists and provides nice results. A good example is Theorem 3.1 from this paper, which is an adaptation of an observation made by prior work about a particular way to compute the leverage scores of $U_1 \odot ... \odot U_N$. The core of this paper is taking Theorem 3.1 and finding a faster way to compute it's right hand side. This means that the prior work gave much of the framework for around paper's proposed algorithm, and we can sorta think of this paper's contribution as finding a novel way to compute a subroutine more quickly.
That said, the approach to computing the subroutine is novel and interesting. I've not seen prior work in this area use a binary-tree in such a way. There's clearly a good deal of effort put into the math (though I only verified bits and pieces of the appendix). The paper very much stands as sufficiently original, but I want to be clear that the originality lands firmly in section 3.1 of the paper -- how to efficiently sample following this framework that existed in prior work.
**Clarity:** The paper is well written. I have only a couple mild gripes about writing and presentation (listed later in the "Questions" section), and I feel that I understood all the big ideas of this paper.
**Significance:** This paper feels well motivated, and the improvement to sample a row with runtime that depends logarithmically on the number of rows in $A$ is quiet strong and interesting. The experiments suggest that this truly is a state-of-the-art algorithm for a meaningful suite of metrics. I do have some gripes with the presentation of the experiments, which undercuts my confidence in the experimental evidence a smidge, but I think this both not essential and can be easily corrected.
Weaknesses
The weaknesses are few and far between in this paper. A couple section lack a bit of clarity, like how the big-Oh rates for some of the downstream tensor algorithms are insufficiently explained. These are issues that can easily be fixed for a camera-ready version of the paper.
Out of these mild gripes, there are three that do stand out a bit:
1. Several experiments lack confidence intervals. This muddies the story of the algorithm's empirical efficacy, especially in Figure 3, where it feels very confusing to see the error of the green curve in the left figure jump up significantly.
2. In a few place, discussion of big-Oh runtime isn't fully explained. For instance, I don't understand how the complexity of STS-CP was derived on Table 1 (appendix A.1). More details are in the "Questions" section.
3. The last paragraph from section 3.2 takes the core technical ideas and is supposed to summarize the algorithm. However, it instead introduces some new notation and makes me wonder if it's actually summarizing an algorithm or if it's instead trying to briefly explain some of the deeper technical edgecases the algorithm has to handle. Either way, it's pretty confusing of a paragraph for me to read, and undercuts my confidence in understanding the full algorithm.
None of these are serious gripes, and call all be fixed with mild updates to the presentation. So I'm still very positive on this paper!
Questions
I don't really have deep concerns to ask about here. I'll just enumerate a long list of minor typos and confusions.
1. Why use (afaik) non-standard notation, like having $d$ be the dimension (number of cols) of A, or $p_i$ be the probability of sampling row $i$, or $m$ or $c$ or $s$ being the number of sampled rows?
1. [Line 30] As someone familiar with leverage scores, I was surprised not to see a log appear in the sample complexity of leverage score sampling. I'd make it into a $\tilde O$.
1. [Lines 49 and 52] Line 49 says that the applications mainly deal with dense inputs. Line 52 says that the most practical benefit is on sparse matrices. These aren't necessarily statements that are at-odds, but it does feel like a bit of whiplash to read these statements back-to-back. The argument on lines 279-280 would be good to add here.
1. [Line 55] Do you have any understanding of why your algorithm which boasts a new and much smaller big-Oh term has 2% slower runtime?
1. [Table 1] I dunno how you came to the complexity-per-iteration here. As a reader, I felt like I should be able to pattern-match between Theorem 1.1 and Table 1 to understand the complexity of STS-CP, but I really couldn't make them line up.
1. [Line 131] "is **a** distinct"
1. [Line 132] "There" not "Here"
1. [Line 194] Get rid of the square on $[0,1]^2$
1. [Line 132] Explicitly argue why $F=1$ is affordable space-wise now, but was too expensive in the setting at the start of section 3.2
1. [Line 241] What is $Z_j$?
1. [Figures 2,3,5] Add confidence intervals
1. [Figure 4] Swap the x and y axis. It's hard to read with fit being on the x-axis. Add some space between the subplots -- they're real strange shoved together like that, making it harder to read.
1. [Line 344] Well... STS-CP does have an oscillating error pattern on Amazon too. Maybe mention it? Eh, I'm sorta torn here.
1. [Algo 6, line 5] Missing a period in $1,..,N$
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.