Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The proposed problem is to estimate the euclidean length of matrix rows, and the authors propose a solution using fewer queries than requires by the JL-transform. This is done in the "matrix-vector query model", where access to the target matrix A is indirect, and only via queries of the form Ax for any vector x. The authors suggest an algorithm based on the Hutch++ algorithm, and give some claims of optimality. Results are derived for estimating Frobenius norms, inter-row distances, and statistical leverage scores.
strengths_and_weaknesses: Strengths: Rigorous approach to several interesting mathematical problems.

Weaknesses: The authors fail to argue that this paper has sufficient (in fact, any) ties to other machine learning applications. In my opinion the paper is out of scope for this conference, and seems more suited to a cs theory conference. The matrix-vector sample model is also quite limited, and in general I'm also unsure of how much this is a contribution this paper makes over those of the Hutch++ algorithm. The results seem incremental.

Minor concern: The statement of the JL lemms is not precise, as the lemma itself relates to distances and the statement relates to norms. It is true that norms imply distances, but only if the transform is linear, and only if one takes the input set to be all difference vectors, which is a larger set. 
questions: What is the main algorithmic contribution above the Hutch++ algorithm? 

Can you further elaborate on the import of Lemma 3, and what it means for the optimality of Theorem 2?

--------------------------------

Following the author rebuttal, and explanation on contribution above the Hutch++ algorithm, I've raised my score to 5. 

Concerning the statement of the JL lemma: Your Definition 1 relates to the norm of the input vectors. JL relates to the distance between the input vectors. This isn't the same, and the latter can be maintained without the former. 
limitations: N/A
review_title: null

final_score: 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.
review_content: summary: The authors provide a dimensionality reduction techniques that is more optimized towards certain data than the traditional JL. Specifically speaking, while JL is known to be optimal when dealing with data with no decay, it is not the optimal method when dealing with datasets that admit exponential or even linear decay. In this paper, the authors provide a technique inspired by the Hutch++ algorithm that deals with such instances of data.
strengths_and_weaknesses: * Strengths:
    1) The paper seems sound theoretically, which hinges upon using delicate and interesting lemmata and theorems.
    2) The experimental section (regardless of using only synthetic data), shows that JL is indeed not optimal for the case where data admits linear/exponential decay.

* Weaknesses:
    1) The writing of the paper is somewhat hard to follow, especially around the proof sketches.
    2) The experimental section only accounts for synthetic data. Is it possible to add an experiment that includes real-world data? This will indeed highlight the applicabilities of your approach.
questions: The results stated in the paper seem sound and are contributing. However, a valid question that usually pops up among practitioners who aim to use dimensionality reduction to boost the performance of their work, are matrices with linear decay/exponential decay common in the field of data science, i.e., how often we get to actually deal with such data that admits such properties?

In addition, is it possible to use some variant of your analysis when dealing with lewis weights?

Finally, please make sure that the main manuscript is at most 9 pages, while the current version of the paper can be refered to as the supplementary material.
limitations: The authors clearly stated the limitations of their work.
review_title: null

final_score: 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.
review_content: summary: The authors give an algorithm to approximate the pairwise Euclidean distances of row vectors of any given matrix. This algorithm improves the bounds of typical Johnson-Lindenstrauss estimators in a few specific settings:
- When achieving the same Frobenius norm-wise accuracy, less matrix-vector queries are required;
- When achieving the same element-wise accuracy less matrix-vector queries are required;
- The algorithm given is as least as accurate as the standard Johnson-Lindenstrauss techniques, when given matrices with flat spectrums.
strengths_and_weaknesses: The paper is well written and structured. The algorithms are well presented, but the authors tend to omit details. The main results, that is Theorems 1,2,3 and 5, show that the techniques of the authors are improvements of the Johnson-Lindenstrauss techniques for their specific use-case. The presentation of proofs is overall good, with a few minor inconveniences. The proofs, that are omitted from the paper and are part of the Appendix, are at least sketched, so the reader gets an idea of the proof. Also enough text is given to follow the structure of the paper.

Because of the notation, sometimes the math is hard to read/follow (see the proof sketch of Corollary 1 for example, also Alg1 as placeholder for the output is suboptimal).

The paper is well written, besides some minor issues with the notation. The result is interesting and a real improvement for the cases presented. 
questions: Suggestion: improve notation, try to include more details 
limitations: No potentially negative societal impact in sight.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: For the Johnson Lindenstrauss transform we can embed $n$ points in $O(\log(n)\epsilon^{-2})$ dimensional space such that we have at most $\epsilon$ distortion. This paper instead look at the problem of having an embedding that only preserves the norm of the data points instead of the metric. The paper does this so that the dimension of the new space only has an $\epsilon^{-1}$ dependence. The goal is that doing it via such an embedding is faster than just computing the norm of the row. 

The paper then presents two applications including computing the metric. 
strengths_and_weaknesses: **Post Rebuttal**

I thank the authors for their response. Their response does help clarify my questions about applications and the matrix multiplication. 

In light of this I raise my score. 

**Strengths**

I think the problem is very interesting and I like the proof techniques as well. 

The algorithm is theoretically motivated and the results are theoretically proved. 

The improvement over the JL is empirically demonstrated. 

**weaknesses**

While the paper does present two applications. I am left unclear as to where this problem shows up in practice (even though the problem is interesting). 

The cost of matrix multiplication has not been discussed and this is crucial to the viability of the method.  

I am not sure if this the best fit for a the machine learning community. Maybe the theoretical CS community might appreciate this more (SODA, FOCS, STOC etc). 
questions: So for context, the reason we like the JL transform is because we can compute it quickly (i.e. faster than doing regular matrix multiplication) [1]. However, the key idea there is the fact that we can do the transform using a Fourier transform and sparse matrices. 

However, in this paper, we are using a Gaussian matrix. So the matrix multiplication for $AS$ in Algorithm 1 step 2 is multiplying a $n \times d$ matrix by a $d \times m$ matrix where $m \le d \le n$. My understanding is that the best rate for this is still $O(m^{\omega-2}dn)$ where $\omega \ge 2$ is the exponent for square matrix multiplication (i.e. multiply two $n\times n$ matrices in time $O(n^\omega)$. However, that is old. Looking for more new results I found [3] which shows that for multiplying an $n \times n^\alpha$ matrix with a $n^\alpha \times n$ matrix can be done in $O(n^{2+\epsilon})$ for any $\epsilon > 0$. Hence I am not sure if that matrix multiplication can be done faster than $O(nd)$ which is the time taken to compute the true norms. 

Even otherwise with step taking $O(nm^2)$ we need $m \le \sqrt{d}$. 


[1] THE FAST JOHNSON–LINDENSTRAUSS TRANSFORM AND APPROXIMATE NEAREST NEIGHBORS∗
NIR AILON† AND BERNARD CHAZELLE‡
[2] Knight, Philip A., Fast rectangular matrix multiplication and QR decomposition, Linear Algebra Appl. 221, 69-81 (1995). ZBL0827.65044.
[3]  Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor by François Le Gall† Florent Urrutia


limitations: Yes.
review_title: null

Meta-review: metareview: All reviews for this paper were positive, albeit with a varying level of enthusiasm. Reviewers found the problem, the results (both theoretical and experimental) and the techniques (very) interesting. The main concerns were whether the paper is a good fit for the conference (given that dimensionality reduction is more of a machine learning tool rather a machine learning problem per se) and lack of experiments on real data. But ultimately, the positives significantly outweighed the negatives.
confidence: Certain
Decision: Accept