Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper studies a method to speed up Newton-type optimization methods using randomized sketching techniques (specifically, leverage score sparsification-based sketching). 
main_review: Newton-type optimization methods are hampered by their expensive computational costs (primarily arising due to the need to compute an inverse Hessian in every iteration). To alleviate this cost, a possible solution path is to randomly sketch/embed (the factors of) the Hessian into a lower number of components. Several schemes following this path have been proposed, including subsampling-based sketches and Gaussian sketches. The former (subsampling) reduces computation but affects convergence, while the latter enjoy strong convergence rates but does not benefit costs.

This paper shows that sketching based on leverage-score sparsification ("LESS embedding") achieves nearly optimal computation, but also retains certain key moment properties of Gaussian sketches and therefore achieve matching problem-independent convergence rates. 

The paper is very well written and the contributions are clearly justified with theory and experiments.

Some comments:
- "convergence rate and computation costs are both nearly at their optimal values." Unclear what this means exactly. Are there known lower bounds, and if so, can the authors provide a citation? If not, this claim should be justified.  In any case, what does "nearly" mean in this claim? The mixed rate in Eq 4 may suggest the existence of better techniques. 
- I'm somewhat puzzled by the "T" parameter in Theorems 1,4 and Corollary 3.  Is T an arbitrary positive integer? Specifically, the sketch size depends on T, which is counter-intuitive (one would imagine a convergence result to be stated in terms of "for all t > T, XYZ holds").
- Consider increasing legend sizes in Fig 2 and 3, they are very difficult to parse.

---
Thanks for the responses, and good luck.
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper analyzes a recently proposed sketching transform (LESS) that has been suggested for Newton Sketch. LESS (originally proposed in [DLDM20]) is aimed to be between full Gaussian sketch and row sampling. It achieves that by sampling the Gaussian sketch, with a sampling scheme based on the leverage scores. In the context of Newton Sketch, Gaussian sketch has been shown to work well, but using is mostly useless since the sketch operation is as expensive as computing the Hessian. Other sketches (e.g. SRHT) reduce per iteration cost, but increase the number of iterations. With LESS, the authors show we can avoid this tradeoff for certain types of functions. 

The convergence rate the authors prove is linear (and not superlinear as one can hope from a second order method). But crucially, the rate is independent of the condition number.

The authors also consider the special case of ridge regression. 
main_review: Overall, I think this is a very good paper. It analyzes an important method (Newton Sketch), and shows how to use a specific sketch to make it more attractive. The paper is very nicely written.

I have several (mostly minor) comments:

1) Line 20: contrary to what this sentence and the next says, the paper does not handle any twice diff function, but only one that can be written as a finite sum of many simple functions. 

2) Theorem 1/4/10: I am confused about the role of epsilon. Does not seem that epsilon come into play in the various bounds in the theorem statement. Is it a parameter that is chosen, or is it fixed? If it is chosen: what does epsilon O(1/\sqrt{d}) mean?  If it is fixed: on what does the constant in O(1/sqrt{d}) depend?

3) Doesn't line 124-125 contradict remark 2? Remark 2 says the bound was known for Gaussian sketch, but line 125 says it was known only for the case of least squares.

4) Definition 2: can LESS requirements be stated with overestimates to leverage scores, with sampling size increased by how much severe the overestimate is? Such framing is common in literature that uses leverage score sampling, and will enabled defining LESS and LESS-uniform in a single definition. 

5) Condition 2: What does alpha=O(1) mean here?

6) What is the even Epsilon that the various results (Theorem 1/4/10) depend on? Is it possible to had a safeguard in the algorithm to check if the even holds, and if not, generate a new sketch?
limitations_and_societal_impact: No limitations and societal impact
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper considers using sketching to accelerate Newton's optimization method. It is argued in the paper that there exist some cases where the Hessian of the function to be optimized can be represented as A^\top A for a tall and skinny matrix A of size N \times d. The authors argue that if the cost of computing the matrix A is small and the complexity is dominated by the matrix multiplication time for computing A^\top A then approximating the Hessian with A^\top S^\top S A, for some sparse sketch matrix S, can accelerate Newton's method. The paper analyzes the convergence of the sketched Newton's method for a recently proposed sketching method known as LESS and proves a linear convergence rate (in expectation). 
main_review: The paper considers using sketching to accelerate Newton's optimization method. It is argued in the paper that there exist some cases where the Hessian of the function to be optimized can be represented as A^\top A for a tall and skinny matrix A of size N \times d. The authors argue that if the cost of computing the matrix A is small and the complexity is dominated by the matrix multiplication time for computing A^\top A then approximating the Hessian with A^\top S^\top S A, for some sparse sketch matrix S, can accelerate Newton's method. The authors mainly focus on a sketch matrix S which is recently proposed and is known as LESS. The LESS is a data-dependent sketch that (roughly speaking) is an average of d independent sampling matrices, where each sampling matrix samples the rows of A according to their leverage scores. The paper analyzes the convergence of the sketched Newton's method and proves a linear convergence rate (in expectation). 

I was wondering if the authors could demonstrate that the assumption that the Hessian is in the form of A^\top A holds in any popular ML problem besides linear regression. For instance, is the Hessian for Logistics regression in this form?

My main concern is that the paper does not discuss at all why they had to choose LESS for sketching the Hessian and not other sketches such as subsampled randomized Hadamard transform, OSNAP, or Countsketch. The only advantage of LESS compared to other sketches is having a small inversion bias. More specifically, sketching the Hessian using LESS and then inverting the sketched matrix can achieve an error (or bias) of \eps = 1/\sqrt{d} as opposed to a constant error. It is not clear at all why a constant error like \eps = 1/100 would not suffice for the convergence proof. 
Any sketch matrix that satisfies the subspace embedding property with some constant error parameter like \eps = 1/100 would spectrally approximate the Hessian and thus can be used to spectrally approximate the inverse Hessian up to a multiplicative (1 \pm \eps) factor. It seems to me that this is enough for the convergence proof and there is no need for having \eps = 1/\sqrt{d}. 
Note that the convergence rate in Theorem 1 and 4 are (d/m * (1+\eps))^T. The 1+\eps factor does not matter here and as long as m is a constant factor larger than d, a linear convergence rate can be established. Can the authors please explain why it is crucial to have  \eps = 1/\sqrt{d}?
limitations_and_societal_impact: My main concern is that the paper does not discuss at all why they had to choose LESS for sketching the Hessian and not other sketches such as subsampled randomized Hadamard transform, OSNAP, or Countsketch. The only advantage of LESS compared to other sketches is having a small inversion bias. More specifically, sketching the Hessian using LESS and then inverting the sketched matrix can achieve an error (or bias) of \eps = 1/\sqrt{d} as opposed to a constant error. It is not clear at all why a constant error like \eps = 1/100 would not suffice for the convergence proof. 
Any sketch matrix that satisfies the subspace embedding property with some constant error parameter like \eps = 1/100 would spectrally approximate the Hessian and thus can be used to spectrally approximate the inverse Hessian up to a multiplicative (1 \pm \eps) factor. It seems to me that this is enough for the convergence proof and there is no need for having \eps = 1/\sqrt{d}. 
Note that the convergence rate in Theorem 1 and 4 are (d/m * (1+\eps))^T. The 1+\eps factor does not matter here and as long as m is a constant factor larger than d, a linear convergence rate can be established. Can the authors please explain why it is crucial to have  \eps = 1/\sqrt{d}?
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This work proposes a Sketched Newton method based on sparsified random Gaussian matrix. The authors provide a precious convergence analysis by a careful characterization of the first and second moment of the inverse sketched Hessian. The authors also provide empirical studies to validate the efficiency of the proposed method.
main_review: The theory is well presented and the intuition behind is well explained. 

Major questions/concerns:
1. Is the work assumes the matrix $A_f(x)$ that encodes the second-order information of f given? How to obtain such encoding for a general function f efficiently?
2. As the authors argued in Section 1.2, compared to existing approaches using SRHT or Count-Sketch, the proposed Newton-LESS wins by a $Clogd$ factor, where $C$ is a non-negligible constant. Authors should compare the proposed approach with these methods as baselines in empirical studies in addition to random Gaussian and vanilla Newton.
3. Can the authors provide more insights about the matrix Q, which plays a crucial role in the analysis?
limitations_and_societal_impact: The authors addressed them.
review_title: null

Meta-review: The reviewers all appreciated the improved benefits of the new dimensionality reduction scheme over existing methods for achieving subspace embeddings. There was initially some confusion about why existing methods could not achieve similar results, as well as to which second order optimization methods the method could be applied to, but these were clarified well in the rebuttal, and all authors were in agreement and enjoyed reading this paper. 
Decision: Accept (Spotlight)