Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update
Authors: Michal Derezinski
Jonathan Lacotte
Mert Pilanci
Michael W. Mahoney
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Second-order methods
Newton Sketch
Optimization
Random Matrix Theory
Least Squares

Abstract: In second-order optimization, a potential bottleneck can be computing the Hessian matrix of the optimized function at every iteration. Randomized sketching has emerged as a powerful technique for constructing estimates of the Hessian which can be used to perform approximate Newton steps. This involves multiplication by a random sketching matrix, which introduces a trade-off between the computational cost of sketching and the convergence rate of the optimization. A theoretically desirable but practically much too expensive choice is to use a dense Gaussian sketching matrix, which produces unbiased estimates of the exact Newton step and offers strong problem-independent convergence guarantees. We show that the Gaussian matrix can be drastically sparsified, substantially reducing the computational cost, without affecting its convergence properties in any way. This approach, called Newton-LESS, is based on a recently introduced sketching technique: LEverage Score Sparsified (LESS) embeddings. We prove that Newton-LESS enjoys nearly the same problem-independent local convergence rate as Gaussian embeddings for a large class of functions. In particular, this leads to a new state-of-the-art convergence result for an iterative least squares solver. Finally, we substantially extend LESS embeddings to include uniformly sparsified random sign matrices which can be implemented efficiently and perform well in numerical experiments. 

Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update
Michal Dereziński Department of Statistics
Jonathan Lacotte
Department of Electrical Engineering
University of California, Berkeley mderezin@berkeley edu
Stanford University
lacotte@stanf aaraaaordd... edu
Mert Pilanci
Michael W. Mahoney ICSI and Department of Statistics University of California, Berkeley mmahoney@stat, berkeley edu
Department of Electrical Engineering Stanford University pilanci@ss aatancistaaffooo wwn.oodd.ooommmomoomooo edu
Abstract
In second-order optimization, a potential bottleneck can be computing the Hessian matrix of the optimized function every iteration. Randomized sketching has emerged as a powerful technique for constructing estimates of the Hessian which can used perform approximate Newton steps. This involves multiplication by a random sketching matrix, which introduces a trade-off between the computational cost of sketching and the convergence rate of the optimization algorithm.
theoretically desirable but practically much too expensive choice is to use a dense Gaussian sketching matrix, which produces unbiased estimates of the exact Newton step and which offers strong show that the Gaussian sketching matrix can be drastically sparsified, significantly reducing the computational cost of sketching, without substantially affecting its convergence properties. This approach, called Newton-LESS. is based on recently introduced sketching technique: LEverage Score Sparsified (LESS) embeddings. local
convergence guarantees. We
We prove that Newton-LESS enjoys nearly the same mooblem-indepentn convergence rate Gaussian embeddings, not just up to constant factors but even down to lower order terms, for a large class of optimization tasks. In particular, this leads to new state-of-the-e convergence result for an iterative least squares solver. Finally, we extend LESS embeddings to include uniformly sparsified random sign matrices which can be implemented efficiently and which perform well numerical experiments.
Introduction
Consider the task of minimizing wwice-differentaalle convex function f .dd R:
find x"
-argmin fxx).
xER*
One of the most classical iterative algorithms for solving this task is the Newton's method, which takes steps of the form X++1 = #4 -2 [x,,), and which leverages second-order information in the d d Hessian matrix 2 fxx:) to achieve rapid convergence, especially locally approaches the optimum x". However, in many settings, the cost of forming the exact Hessian is prohibitively expensive, particularly when the function given as a sum of > components, i.c., fxx
En (x).. This commonly arises in machine learning when f represents the training loss over
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Sampling
non-zero per row S
Compotational Cost
LESS
d non-zeros per row of
Convergence Rate
Gaussian
non-zeros per row of S
Sampling
LESS
Gaussian
Sketch Density
Figure 1: The effect of the density of m sketching matrix S applied to an d matrix A (with d. m < n) on the convergence rate of Newton Sketch and the computational cost of constructing the Hessian estimate. LESS embeddings "interpolate" between Sub-Same Lub-Sampled Newton methods and Gaussian Newton Sketches, achieving a "sweet spot" the computation-pet per---eeee-iioonnn versus number-of-iterations tradeoff.
dataset elements, as well as solving semi-definite programs, portfolio optimization, and other tasks. In these contexts,
represent the Hessian via decomposition /² A (x) A (x), where (x) is a tall n x d matrix, which can be easily formed, and the main bottleneck is the matrix multiplication which takes (ndd)) arithmetic operations. To avoid this bottleneck, many randomized second-order methods have been proposed which use Hessian estimate in place of the exact Hessian (e.g.. [BCNN11, EM15, ABH17, RKM19]). This naturally leads to a trade-off between the per-iteration cost of the method and the number of iterations needed to reach convergence. We develop Newton-LESS a randomized second-orde method which eliminates the computational bottleneck while minimizing the convergence trade-offs.
important family of approximate second-order methods is known as the Newton Sketch [PW17]
X,+1 X, (o (3x) ((A)()))) fV)())
(1)
where is the step size, and S, is a random m x n sketching matrix, with m < n. that is used reduce A (Rt) to small m d sketch 5 This brings the complexity of forming the Hessian down (md?) time plus the cost of forming the sketch.
Naturally, sketching methods vary in their computational cost and they can affect the convergence rate, so the right choice of S, depends on the computation-conwe spectrum are the so-called Sub-Sampled Newton methods [RKM19, XRKM17, YXRKM18), where S, simply selects random sample of m rows of (x) (e.g.. sample of data points in training set) to form the sketch. Here the sketching cost is negligible, since S, is extremely sparse, but the convergence rate can be highly variable and problem-dependen.. On the other end, we have what will refer to as the Gaussian Newton Sketch, where S, is a dense matrix with i.i.d. scaled Gaussian entries a.. Gaussian embedding). While the O(mnd) cost of performing this sketch limits its practical appeal, Gaussian Newton Sketch has a number of unique and desirable properties [LP19]] enjoys strong problem-independeen convergence rates; produces unbiased estimates of the exact Newton update (useful in distributed settings); and admits analytic expressions for the optimal step size.
trade-off. On one end of this
natural way to interpolate between these two extremes is to vary the sparsity s of the sketching matrix S,, from = non-zero element per row (Sub-Sampling) (Gaussian embedding). with the sketching complexity ((mds). Motivated by this, we ask:
non-zero elements
Can sparsify the Gaussian embedding, making its sparsity closer to that of Sab-Sampling, without suffering any convergence trade-offs?
In this paper, provide affirmative answer this question. We show that it is possible to drastically sparsify the Gaussian embedding so that two key statistics of the sketches, namely first
For a more detailed discussion of other sketching techniques that may not fit this taxonomy, such as the Subsampled Randomized Hadamard Transform and the CountSketch, see Section 1.2.

---

and second inverse moments of the sketched Hessian, are nearly preserved in very strong sense. Namely, the two inverse moments of the sparse sketches can be upper and lower bounded by the corresponding quantities for the dense Gaussian embeddings, where the upper/lower bounds are matching not just up to constant factors, but down to lower order terms (see Theorem 6). We use this to show that the Gaussian Newton Sketch can be sparsified to the point where the cost of sketching is proportional to the cost of other operations, while nearly preserving the convergence rate (again, down to lower order terms; see Theorem 1). This is illustrated conceptually in Figure 1, showing how the sparsity of the sketch affects the per-iteration convergence rate as well as the computational cost of the Newton Sketch. We observe that while the convergence rate improves density, it eventually flattens out, On the other hand, the computational cost stays largely flat until some point when it starts increasing at linear rate. As result, there is a sparsity regime where achieve the best of both worlds: the convergence rate and the computational cost are both nearly at their optimal values, thereby avoiding any trade-off.
increase the
To establish our results, we build upon a recently introduced sketching technique called LEver- age Score Sparsified (LESS) embeddings [DLDM21]. LESS embeddings use leverage score tech- niques [DMIMW 2a] to provide carefully-construccte to produce
(random) sparsification pattern. This is used embedding with d non-zeros per row of S, (as opposed to for dense matrix), so that the cost of forming the sketch (Xx) matches the cost of constructing the Hessian estimate, i.e )md)² (see Section 2). [DLDM21] analyzed the first inverse moment of the sketch to show that LESS embeddings retain certain unbiasedness properties of Gaussian embeddings. In our setting. this captures the bias of the Newton Sketch, but does not capture the variance, which is needed to control the convergence rate.
Contributions. In this paper, we analyze both the bias and the variance of Newton Sketch with LESS embeddings (Newton-LESS; see Definition 2 and Lemma 7), resulting in a comprehensive convergence analysis. The following are our key contributions:
1. Characterization of the second inverse moment of the sketched Hessian for a class of sketches including sub-Gaussian matrices and LESS embeddings;
2. Precise problem-ing indllmm-ideeeneentt local convergence rates for Newton-LESS, matching the Gaussian Newton Sketch down to lower order terms;
3. Extension of Newton-LESS regularized minimization tasks, with improved dimension- independent guarantees for the sketch sparsity and convergence rate;
4. Notable corollary: Best known global convergence rate for an iterative least squares solver, which translates to saate-of-the-ee numerical performance.
1.1
Main results
As our main contribution, show that, under standard assumptions on the function fx), Newton- LESS achieves the same despite drastically smaller per-iteration cost.
local convergence rate as the Gaussian Newton Sketch,
Theorem 1. Assume that f(x) is (a) self-concordant, or (b) has a Lipschitz continuous Hessian. Also, let H f(x" be positive definite. There is neighborhood U containing x* such that if No E U, then Newton-LESS with sketch size m Cdlog(dT /8) and step size Pt = d. satisfies: me
XT
x
1/T
d
for (=
E3
Re
XD
where Eg X is expectation conditioned on an event that holds with 1 5 probability, VV Mv, and a Re, b means that (a - bl S eb.
|v|l
Remark 2. The same guarantee holds for the Gaussian Newton Sketch, but it is not known for any fast sketching method other than Newton-LES LESS (see Section 1.2). The alternative assumptions of self-concordance and Lipschitz continuous Hessian are standard in the local convergence analysis of the classical Newton's 's method, and they only affect the size of the neighborhood U (see Section 4). Global convergence of Newton-LESS follows from existing analysis of the Newton Sketch [PW17).
The notion of expectation F. allows us to accurately capture the average behavior of randomized algorithm over moderate (i.c., polynomial in d) number of trials even when the true expectation
3

---

is not well behaved. Here, this guards against the (very unlikely. but non-zero) possibility that the Hessian estimate produced by sparse sketch will be ill-conditioned.
To illustrate this result in a special case (of obvious independent interest), we provide a simple corollary for the least squares regression task, i.e., f(x) 2 || bll Importantly, here the
convergence rate of ( d y holds globally. Also, for this task we have 2 x - x x* - f(x) - f(x*),
so the convergence can be stated in terms of the excess function value. To our knowledge, this is the best known convergence guarantce for a fast iterative least squares solver.
Corollary 3. Let f(x) = 1 AI bll² for A E Raadd and b E I. Then, given any Xo E Rd,
Newton-LESS with sketch size m 2 Cd (og((T/)) and step size pt = 1 m
d
satisfies:
f(xx) f(xx)
1/T
d for c= 0 .aa)
Es
f(xo) f(x*)
m
Prior to this work, a convergence rate of ( d. was known only for dense Gaussian embeddings, and only for the least squares task [LP11]. On the other hand, our results apply generally as the standard local convergence analysis of the Newton's 's method, and they include a broad class of sketches. In Section 3, we provide general structural conditions on randomized sketching matrix that are needed to enable our analysis. These conditions are satisfied by a wide range of sketching methods, including all sub-Gaussian embeddings (c.g.. using random sign entries instead of Gaussians), the original LESS embeddings, and other choices of sparse random matrices (see Lemma 7). Moreover, we develop an improved local convergence analysis of the Newton Sketch, which allows us to recover the precise convergence rate and derive the optimal step size. In Appendix D, we also discuss a distributed variant of Newton-LESS, which takes advantage of the near- sear-unbiasedness properties of LESS embeddings, extending the results of [DLDM21].
The performance of Newton-LEES Namely, suppose that function f can be decomposed as follows: f(x) = fx(x) + g(x), where g(x) has a Hessian that is easy to evaluate (e.g., Ig-regularization, g(x) = 2 |xx 1). this case, a modified variant of the Newton Sketch has been considered, where only the fo component is sketched:
be further improved for regularized minimization tasks.
X = X - 14 (A (x,) S7 S,A,A, (xt) + (3) -
(2)
where, again, we let A (x) be an n X matrix that encodes the second-ord order information in fo at X. For example, in the case regularized least squares, f(x) = |A - bbI² + > A f (x) A and (x) = AI for all x. We show that the convergence rate of both Newton-LESS and the Gaussian Newton Sketch can be improved in the presence of regularization, by replacing the dimension d with an effective dimension det- This can be significantly smaller than d when the Hessian of fo at the optimum exhibits rapid spectral decay or is approximately low-rank:
2 || we have
dan = (o((V
d.
Theorem 4. Assume that fo and J are (a) self-concordunt, or (b) have a Lipschitz. continuous Hessian. Also, let V fo(xx)) be positive definite and let 4² V²g(x*) be positive semidefinite. with H = fx**). There is a neighborhood U containing x* such that if Xo E U, then Regularized dat satisfies:
Newton-LESS (2), with sketch size m 2 C'den log(denT and step size ft = m
X1
x
1/T
dell
(1+c) for c= c=0( Vdlan
E5
Remark The same guarantee holds for the Gaussian Newton Sketch. Unlike in Theorem 1, here we can only obtain upper- bound the local convergence rate, because the exact rate may depend on the starting point Xa (see Section 4). For regularized least squares, f(x) = | bi2² + 2 |
the above convergence guarantee holds globally, i.e., U = Rd, Note that deff can be efficiently estimated using sketching- based trace estimators [ACWI6, CEM+15)
Finally, our numerical results show that Newton-LESS can be implemented very efficiently on modern hardware platforms, improving on the optimization cost over not only dense Gaussian embeddings, but also state-of-ther thte---rtth--tttteee sketching methods such as the Subsampled Randomized Hadamard Transform, as well as other first-order and second-order methods. Moreover, we demonstrate that our theoretical predictions for the optimal sparsity level and convergence rate are extremely accurate in practice.

---

1.2 Related work
LEverage Score Sparsified (LESS) embeddings were proposed by [DLDM21] as a way of addressing the phenomenon of inversion bias, which arises in distributed second-order methods [WRKXMI8, DM19, DBPM20, GGD Their results only establish the near-un caar-unbissedeess of Newton-LESS iterates (i.e., that x[x++1] R Xt+1), but they did not provide any improved guarantees on the convergence rate. Also, their notion of LESS embeddings is much narrower than ours, and so it does not capture Regularized Newton-LESS or uniformly sparsified sketches (LFSS-uniforr).
Convergence analysis of the Newton Sketch [PW17, LP19, LLDP20] and other randomized second- order methods [BCNNII, BCNW12, EMIS, RKM19] has been extensively studied in the ma- chine learning community, often using techniques from Randomized Numerical Linear Algebra (RandNLA) [DM16, DM21J. Some of the popular RandNLA methods include the Subsampled Randomized Hadamard Transform (SRHT, [AC09]) and several variants of sparse sketches, such as the CountSketch [CW17, MM13] and OSNAP [NN13, Coh16]. Also, row sampling based on Leverage Scores [DMM06, AM15] and Determinantal Point Processes [Der19, DCV19, DM21] has been used for sketching. Note that CountSketch and OSNAP sparse sketches differ from LESS embeddings in several ways, and in partieular, they use fixed number of non-zeros per column of the sketching matrix (as opposed to per row), so unlike LESS, their rows are not independent. While all of the mentioned methods, when used in conjunction with the Newton Sketch, exhibit similar per-iteration complexity as LESS embeddings (see Section 2). their existing convergence analysis is fundamentally limited: The best known rate is (C'log d m _ which is worse than our result of (T) by factor of C' Colog d, where C > 1 is non-negligible constant that arises in the measure concentration analysis.
In the specific context of least squares regression where f(x) = = |1Ax - bll the Hessian A A remains constant, and an alternative strategy is to keep the random sketch SA fixed at every it- eration. Many efficient randomized iterative solvers are based on this precondition-and-sol proach [RT08, AMTIO, MSM14]: form the sketch SA, compute an casy-to-invert square-root matrix H of A S SA and apply an iterative least squares solver to the preconditioned objective minz 3 A - bll?, e.g., Chebyshev iterations or the preconditioned conjugate gradient. In con- trast to the Newton Sketch, these methods do not naturally extend to more generic convex objectives for which the Hessian matrix changes at every iteration. Also, similarly as the Newton Sketch, their convergence guarantees are limited to (C' lo'log d _ )T when used in conjunction with fast sketching methods such as SRHT, OSNAP, or leverage score sampling.
ap-
2 Preliminaries
Notation. We let || \l/M = Vv. We define a Re b to mean Ja bl S cb, whereas a = b means that |a - bl c, and C. denotes a large absolute constant. We use Eg to denote expectation conditioned on E, and for a E (0, 1), we use Es as a short-hand for: "There is an event & with probability least 1 8 s.t. Eg ... Let pd and psd mean positive definite and positive semidefinite. Random variable X is sub-Gaussian if Pr[ [ Z () S exp(-cl²) for all L 2 O and some c = 2(1).
We next introduce some concepts related to LEverage Score Sparsified (LESS) embeddings. We start with the notion of statistical leverage scores [DMIMW 12a]. which are importance weights assigned to the rows of a matrix A E Rn The definition below for leverage scores is somewhat more general than standard definitions, because it allows for a regularized leverage score, where the regularization depends a d x d matrix C. When C is scaled identity matrix, this matches the definition of ridge leverage scores [AM15].
Definition (Leverage scores). For given matrices A E RRax and psd C E Rxdxd we define the ith leverage score 4(A, C) as the squared norm of the ith row U AH-2, 2 where = A A C assumed to be invertible. The effective dimension of A (given C) is defined as deft = 4A,
tr(UTU), whereas the coherence of A (given C) is = des max; ((A, C) E [1, der
Next, we define a class of sparsified sub-Gaussian sketching matrices which will be used in our results. This captures LESS embeddings, as well as other sketching matrices that are supported by the analysis. To that end, we define what we call a sparsifier, which an n-dimensional random vector& & that specifies the sparsification pattern for one row of the m sketching matrix S.
5

---

Definition 2 (LESS embeddings). Let t1. tg be sampled i..dd from a distribution (pi,.... Pn)) where by = - is a (p, s-saassifff A (p. s)-spriiified sub-Gaussian sketch is a random matrix S that consists of ii.d. row vectors distributed as e. (x =),, where denotes the entry-wise product, has i.i.. mean zero, unit variance and mub-Gaussian entries, and is some constant. For given matrices A E Raxd and psd C E Rdxd, we focus on two variants of Leverage Score Sparsified embeddings:
Then, the random vector E = -VV (V.,,.... "....... V sp..
1. LESS. We assume that Pt L1/2 (A, C)/dan and let F2//2 dent. For C and d, we recover the LESS embeddings proposed by (DLDM21).
2. LESS-uniforta uniform. We simply let Pt = 1/n (denoted as asp- = unif). This avoids the preprocessing needed for approximating the 1, (A, C), but we may need larger s to recover the theory.
Computational cost. To implement LESS, we must first approximate (i.e., there is no need to compute exactly [DMIMW (2 the leverage scores of A. This can be done in time O(nnz( A) log n- d log d) by using standard RandNLA techniques [DMIMW12) 12, CW17) 17], where nnz(A) (A) is the number of non-zero entries in A and it is bounded by nd. Since the prescribed sparsity for LESS satisfies O(d), the sketching cost is at most O(mde). Thus, the total cost of constructing the sketched Hessian with LESS is O (mnz(4 (A) log n + mdd), which up to logarithmic factors matches other sparse sketching methods such as leverage score sampling (when implemented with approximate leverage scores [DMIMW 12))), CountSketch, and OSNAP. In comparison, using the SRHT leads to O(nd log m + md²) complexity. since this method does not take advantage of data sparsity. Note that, in practice, the computational trade-offs between sketching methods are quite different, and significantly hardware-dependent (see Section 5). In particular, the cost of approximating the leverage scores in LESS embeddings can be entirely avoided by using LESS- uniformm Here, the total cost of sketching is O(mds), but the sparsity of the sketch that is needed for the theory depends on A and C. Yet, in Section 5, we show empirically that this approach works well even for d.
3 Equivalence between LESS and Gaussian Embeddings
In this section, we derive the basic quantities that determine the convergence properties of the Newton Sketch, namely, the first and second moments of the normalized sketched Hessian inverse. Our key technical contribution is a new analysis of the second moment for wide class of sketching matrices that includes LESS embeddings and sub-Gaussian sketches.
Consider the Newton Sketch update in (2), and let A, x, x'. Denoting H, V2
gi (X), and using Pt --4 ge to denote the exact Newton direction with step size μ4x simple calculation shows that:
I. - A 12 23, H QH P. + P. H H.Q........
(3)
where Q = H2 (A fo (3.) "TT)""TSSAA, (R,) V2x( -H. From this, we have that the expected decrease in the optimization error is determined by the first two moments of the matrix Q, i.e., E [[ and E " In the unregularized case, i.e., g(x) = 0, these moments can be derived exactly for the Gaussian embedding. For instance if we let S, be an m X n matrix with i.i.d standard normal entries scaled by dm-d-1 then we obtain that:
E Q I,
E EQ1
(m (m-1)(m--1) R (m- m3
T
I,
m-d
for (l/d). This choice of scaling for the Gaussian Newton Sketch ensures that each iterate X is an unbiased estimate of the corresponding exact Newton update with the same step size, i.c., that E[x = x, + Pt. For most other sketching techniques, neither of the two moments is analytically tractable because of the bias coming from matrix inversion. Moreover, if we allow for regularization, e.g. (x) A
n |||| then even the Gaussian embedding does not enjoy tractable formulas for the moments of Q However, using ideas from asymptotic random matrix theory, [DLDM21] showed that in the unregularized case, the exact Gaussian formula for the first moment holds approximately for sub- Gabsiin sketches and LESS embeddings: Es Q] xg I. This implics near- unbiiasdasss of

---

the unregularized Newton-LESS iterates relative to the exact Newton step, but it is not sufficient to ensure any convergence guarantees.
In this work, we develop a general characterization of the first and second moments of Q for a wide class of sketching matrices, both in the unregularized and in regularized settings. For the sake of generality, we will simplify the notation here, and analyze the first and second moment of Q = H (A STSA + C) for some matrices A E Raxd and C E TRddd such that A A + C = H. In the context of Newton Sketch (2), these quantities correspond to A A (x,) and C = V (Xx). Also, as shorthand, we will define the normalized version of matrix A as U A 2. The following are the two structural conditions that need to be satisfied by sketching matrix to enable our analysis.
The first condition is standard in the sketching literature. Essentially, it implies that the sketching matrix S produces useful approximation of the Hessian with high probability (although this guarantee is still far too coarse by itself to obtain our results).
Condition 1 (Property of random matrix S). Given U R2dd the m n random matrix satisfies ST SU - U U|| S 1) with probability 1 - 5.
This property is known the subspace embedding property. Subspace embeddings were first used by [DMM06], where they were used in a data- aata- context to obtain relative-error approximations for l regression and low-rank matrix approximation [DMM08]. Subsequently, data-oblivious subspace embeddings were used by [Sar06] and popularized by [Woo14]. Both data-aware and data- oblivious subspace embeddings can be used to derive bounds for the accuracy of various algorithms [DM16, DM18].
For our analysis, it is important to assume that S has i.i.d. row vectors csT, where c is appropriate scaling constant. The second condition is defined as a property of those row vectors, which makes them sufficiently similar to Gaussian vectors. This is a relaxation of the Restricted Bai-Sillersteein condition, proposed by [DLDM21], which leads to significant improvements in the sparsity guarantee for LESS embeddings when the Newton Sketch is regularized.
Condition 2 (Property of random vector s). Given E Raad, the n-dimensional random vectors s satisfies Varls T UBUTs] < a Lr(UB²UT) ) for all p.s.d. matrices B and some = O(1)
Given these two conditions, we ready derive precise non-asymptotic analytic expressions for the first two moments of the regularized sketched inverse matrix, which is the main technical contribution of this work (proof in Appendix A).
Theorem 6. Fix A and assume that C is psd. Define H ATA+ + C Cnd U AH- Let S consist of m. i.i.d. rows distributed as Tm-da ST, where Elss"] = In and der = ur(U U). Also,
let den = tr((UT (U?)). Suppose that the matrix consisting of the first m/3 rows of S scaled by v3 satisfies Condition I w.r.. foror 17 S 1/2 and probability 1 8/3, where 8 < 11/m². Suppose also that s satisfies Condition 2 w.r.f. U. If m 2 (den)) then, conditioned on event E that holds with
probability 8, matrix Q H (ATASS ST SA + C) - satisfies QQ I|| S O(r) and:
E5 - I|| < O ded
Es [Q2] (I
- UTUI < 0 VdLe
dew
m dea
Theorem shows that, for wide class of sketching matrices, we can approximately write EQQ = I and [[ ~ I+++++ d5 UTU, with the error term scaling as O( ydl In the case of the first moment, this is relatively straightforward generalization of the unregularized formula for the Gaussian case. However, for the second moment this expression is considerably more complicated, including not one but two notions of effective dimension, den a deft. To put this in context, in the unregularized case, m
m-d
dur i.e. C = O, we have derr = der = d and U = I, so we get m-dar
U m--
I, which
matches the second moment for the Gaussian sketch (up to lower order terms).
In the case of the first moment, the proof of Theorem follows along the same lines as in [DLDM21]. using a decomposition of E q that is based on the Sherman -oorinnnoooorooon rank-one update of the inverse. This approach was originally inspired by the analysis of Stieltjes transforms that are used to establish the limiting spectral distribution in asymptotic random matrix theory (e.g., [BS10, CD11)), and applied to sketching by [DLIMM2,, DLDM21]. Our key contribution lies in deriving the bound for the second moment, which requires substantially more elaborate decomposition of E[Q"
7

---

In the following lemma, we establish that the assumptions of Theorem 6 are satisfied not only by Gaussian, but also sub-Gaussian and LESS embedding matrices (proof Appendix C).
Lemma' 7. Fix A and assume that C is psd. Let S be sketching matrix with m i..d rows distributed s". Then, S satisfies Conditions and as long as one of the following holds:
as /m-da
1. Sub- s is an i..dd sub-Gaussian random vector and m 2 O(dat + log(1/6))/n?+
2. LESS: 8 is a (p, daas-sssrriifed i.i.d. sub-Gaussian random vector with 11/2 4(A, /e and m 2 Cdett log(den/ (es(dd//////1 /
3. LESS :esS--niform; s is a (unif, sdan)--parsiffee i..dd sub-Gaussian random vector, where T is the coherence of A, i.e., dar
n. max; (:(A, C), and m 2 Cddn log(den/6)//g)
4 Convergence Analysis for Newton-LESS
In this section, we demonstrate how main technical results can be used to provide improved convergence guarantees for Newton-LEESS (and, more broadly, any sketching methods that satisfy the conditions of Theorem 6). Here, we will focus on the more general regularized setting (2), where we can only show an upper bound on the convergence rate (Theorem 4). The unregularized result (Theorem 1) with matching upper/lower bounds follows similarly.
To start, we introduce the standard assumptions on the function f. which are needed to ensure strong local convergence guarantees for the classical Newton's 's method [BV]
Assumption 8, Function f RRd - R has a Lipschitz continuous Hessian with constant L, iee. [[v fx')l' s L
|x x'I for all x, E RR..
Assumption 9. Function f dRd + IR is self-concordan i.e., for all x E Rd, the function ((t) f(x + tx') satisfies: (+))()) S (1))
Only one of those two assumptions needs to be satisfied for our analysis to go through, and the choice of the assumption only affects the size of the neighborhood around the optimum x" for which our local convergence guarantee is satisfied. To clarify this, below we give an expanded version of Theorem (proof in Appendix B).
Theorem 10 (Expanded Theorem 4). Ler Ho = fo(xx) be pd and C = V2g(x') be psd. Define dar = tr(H, and d=ff Hr(HHHHH')) for H Ho + C. Assume one of the following:
1. fo and f satisfy Assumption 8, and U fx ||x Amin is the smallest eigenvalue of Ho;
x" 11
v n2
(Amin 33/2 /3/2/D}, where
2. fo and satisfy Assumption 9, and U {x ||x x*11
1|e
S m
Then, Newton Sketch (2) starting from Ny E U, using any Sifrrm Lemma (i.e, sub- Gaussian, LESS, or LEESS LESS-unnffom) with replaced by 5/T, and step size fit = m+dda dea"
det
satisfies:
X
1/T
der (1 6)) delt
der (1 c), for == (=0(/ Vdlam
E,8
S
m + delt
Note that, compared to Theorem 4, here we present a slightly sharper bound which uses both types of effective dimension, dar S den, that are present in Theorem 6. The statement from Theorem is recovered by replacing der with den in the step size and the bound. The key step in the proof of the result is the following lemma, which uses Theorem 6 to characterize the Newton Sketch iterate X,41 in terms of the corresponding Newton iterate X++1- Note that this result holds globally for arbitrary
X, and without the smoothness assumptions on f. Recall that we let A = x; - x" denote the error residual at step
Lemma 11. Fix H, (xx( and let X be the Newton Sketch iterate with S, as in Lemma 7. the exact Newton step X++1 X, p.H, g: is a descent direction, i.e., A4t1l|HH S || | I|H
where A4t1 = X++1 x", then
Es A ++ 112. = |1
den(Re) mxdd((x))
|x 201 + (( A
8

---

Importantly, the second term on the right-hand side uses the norm || ( which is different than the norm ||- ||,, used for the remaining terms. As result, in the regularized setting, it is possible that the second term will be much smaller than the last term (the approximation error). This prevents us from obtaining a matching lower-bound for the convergence rate of Regularized Newton-LESS. On the other hand, when g(x)
then fo f and we obtain matching upper/lower bounds.
The remainder of the proof of Theorem 10 is essentially a variant of the local convergence analysis of the Newton's 's method. Here, note that typically, would set the step size to 14 1 and would expect superlinear (specifically, quadratic) convergence rate. However, for Newton Sketch, convergence is a mixture of línear rate and superlinear rate, where the linear part is due to the approximation error in sketching the Hessian. Sufficiently close to the optimum, the linear rate will dominate, and this is what we focus in our local convergence analysis. The key novelty here is that, unlike prior work, we strive to describe the linear rate precisely, down to lower order terms. As key step, we observe that the convergence of exact Newton with step size Mr < 1, letting A+t1 X(+1 x", given by:
| (1 me) PI +4(A4+1 (1-P))A) ( ge):
(4)
lineur rale
superlinear rale
where recall that A, = X, x" corresponds to the previous iterate, and = V (Xx).. Here, (1 (1-pe) p2) represents the linear convergence rate. The superlinear term vanishes near the optimum x", because of the presence of H ge. which (under the smoothness assumptions on ƒ) vanishes at the same rate as || Interestingly, with this precise analysis, the superlinear term does not have a quadratic rate, but rather a 3/2 rate. Entering (4) into the guarantee from Lemma 11, we obtain that the local rate of Newton Sketch can be expressed as (1-14 -1, + der
m- ub: and minimizing this expression over 14, we obtain the desired quantities from Theorem 10. Finally, we note that while the norms and effective dimensions in the above exact calculations are stated with respect to the Hessian H, at the current iterate Xt, these can all be approximated by the corresponding quantities computed using the Hessian at the optimum x" (as Theorem 10), relying on smoothness of f.
(a) High-coherence synthetic data
(b) Musk dataset
(c) CIFAR dataset
(d) WESAD dataset
Figure 2: LESS- unnS-un embeddings: convergence rate of the Newton Sketch for least squares regression and wall-clock time of forming SA versus row density, with sketch size m Sd. The results were averaged over 100 trials and error bars show twice the empirical standard deviation.
Numerical Experiments
We evaluated our theory on range of different problems, and we have found that the more precise analysis that our theory provides describes well the convergence behavior for range of optimization problems. In this section, we present numerical simulations illustrating this for regularized logistic regression and least squares regression, with different datasets ranging from medium to large scale: the CIFAR-10 dataset, the Musk dataset, and WESAD [SRD* + 18]. Data preprocessing and implemen- tation details, as well as additional numerical results for least squares and regularized least squares, can be found in Appendix E.
We investigate first the effect of the row density of LLESS-unifome embedding on the Newton Sketch convergence rate and on the time for computing the sketch SA for least squares regression, In Figure 2, we report these two performance measures versus the row density. (This the empirical analog for real data of Figure 1). Note that here we also consider a synthetic data matrix with high- coherence, which aims to more challenging for uniform sparsifier. Remarkably, our prescribed row density of d non-zeros per row offers an excellent empirical trade-off: except for the CIFAR-10

---

64:
AGO
CO
AGD
AGD
BPS5
DFGS
NO LCSS Jrb
RD RESLESS untar
SANTT
HS
SAIT
HD DEUIT
Vial dook time
Wall clock time
Wall clock time
(a) WESAD dataset
(b) CIFAR- -1 dataset
(c) Musk dataset
380-
us
76-
LESS Jriom
Couuslan
ShIT
RAS
Vallt clock time
Wel (lD0
25
CPU
CPU
Figure 3: Top plots show the convergence of Newton Sketch (NS) and baselines for logistic regression. We use sketch size m d/2 for NS. In the bottom plots, we report the CPU and GPU wall-clock times to reach a 10-6 accurate solution for NS with different sketching methods.
dataset, for which random row sampling performs equally well to Gaussian embeddings, we observe that one can drastically decrease the row density without significantly impairing the convergence rate.
Next, in Figure 3, we investigate a minimization task for the regularized logistic regression loss. Namely, given data matrix A Ra with rows a, target vector b {=1)" and regularization parameter À > 0, the goal is to solve:
min 1 Σ XERd
log(1 + exp(-bxaa x)) |
For each dataset, we choose the value of among (10-) on hold out validation set. For CIFAR-10 and Musk, we pick X 10-1 For WESAD, we pick 10-5 We plot the error versus wall-clock time for the Newton Sketch with LESS-uniform, Gaussian, Subsampled Randomized Hadamard Transform (SRHT) and Random Row Sampling (RRS) matrices, and we compare it with two standard second-order optimization baselines: Newton's method and BFGS. We also included three first-order baselines: Gradient Descent (GD), Accelerated GD (AGD), and Stochastic GD (SGD), observing much worse performance. Based on the top plots in Figure 3, conclude that Newton-LESS (i.e., NS LESS uniform) offers significant time speed-up ups over all baselines.
j |
0.....8) 8} that minimizes the error
Finally, we compare wall-clock time on different hardwares (CPU versus GPU) for the Newton Sketch reach 10-6-accurate solution (see Appendix E for hardware details). From Figure (bottom plots), we conclude the following: first, when switching from CPU to GPU for WESAD and CIFAR-10, Gaussian embeddings become more efficient than SRHT, despite a worse time complexity, by taking better advantage of the massively parallel architecture; second, Random Row Sampling performs better than either them, despite having much weaker theoretical guarantees; and third, LESS-uniform is more efficient than all three other methods, both CPU and GPU hardware platforms, observing a significant speed-up when switching to the parallel GPU architecture.
Conclusions
We showed that, when constructing randomized Hessian estimates for second-order optimization, we can get the best of both worlds: the efficiency of Sab-Sampiig methods and the precision of Gaussian embeddings, by using sparse sketching matrices known as LEverage Score Sparsified (LESS) embeddings. Our algorithm, called Newton-LESS, enjoys both strong theoretical convergence guarantees and excellent empirical performance on number of hardware platforms. An important future direction to explain the surprising effectiveness of the simpler LESS-uniform method, particularly high-coherence matrices, which goes beyond the predictions of our current theory.
10

---

Acknowledgements
We would like to acknowledge DARPA, IARPA, NSF, and ONR via its BRC on RandNLA for providing partial support of this work. MP and JL were partially supported by the National Science Foundation under grants IIS- 183-183,,7, sions do not necessarily reflect the position or the policy of our sponsors, and no official endorsement should be inferred.
203-3003300 and the Army Research Office. Our conclu-
References
[ABH17] Naman Agarwal, Brian Bullins, and Elad Hazan. Second-order stochastic optimiza- tion for machine learning in linear time. Journal of Machine Learning Research, 18(116):1-40, 2017.
[AC09] Nir Ailon and Bernard Chazelle. The fast Johnson-Linneesstrauss transform and approximate nearest neighbors. SIAM Journal on computing, 39(1)330-3322, 2009.
[ACWI6] Haim Avron, Kenneth L Clarkson, and David P Woodruff. Sharper bounds for regularized data fitting, arXiv preprint 16X.v::611..0222.. 2016.
[AM15] Ahmed El Alaoui and Michael W. Mahoney. Fast randomized kernel ridge regression with statistical guarantees. In Proceedings of the 28th International Conference on Neural Information Processing Systems, pages 775-783, December 2015.
[AMTI0] Haim Avron, Petar Maymounkov, and Sivan Toledo. Blendenpik: Supercharging lapack's 's least-squares solver. SIAM Journal on Scientific Computing, 32(3):1217- 1236, 2010.
[BCNN1I] Richard H Byrd, Gillian M Chin, Will Neveitt, and Jorge Nocedal. On the use of stochastic hessian information in optimization methods for machine learning. SIAM Journal on Optimization, 21 21()9777-9955, 2011.
[BCNW12] Richard H Byrd, Gillian M Chin, Jorge Nocedal, and Yuchen Wu. Sample size selection in optimization methods for machine learning, Mathematical programming. 134(1):127-155, 2012.
[BS10] Zhidong Bai and Jack W Silverstein. Spectral analysis of large dimensional random matrices, volume 20. Springer, 2010.
[BV04] Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
[CD11] Romain Couillet and Mrouane Debbah. Random Matrix Methods for Wireless Communications. Cambridge University Press, USA, 2011.
[CEM+15) 15] Michael B Cohen, Sam Elder, Cameron Musco, Christopher Musco, and Madalina Persu. Dimensionality reduction for k-means clustering and low rank approximation. Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 163-172, 2015.
[Coh16] Michael Cohen. Nearly tight oblivious subspace embeddings by trace inequalities. In Proceedings of the twenty-seventh annual ACM-SIAM symposium Discrete algorithms,, pages 278-287. SIAM, 2016.
[CW17] Kenneth L. Clarkson and David Woodruff. Low-rank approximation and regression in input sparsity time. J. ACM, 63(6):54:1554:55, January 2017.
[DBPM20] Michal Dereziński, Burak Bartan, Mert Pilanci, and Michael W Mahoney, Debiasing distributed second order optimization with surrogate sketching and scaled regular- ization. In Advances in Neural Information Processing Systems, volume 33, pages 6889-6899, 2020.

---

[DCV19] Michat Dereziñski, Daniele Calandriello, and Michal Valko. Exact sampling of determinantal point processes with sublinear time preprocessing. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d Alché-Buc, E. Fox, and R. Garnett, editors, Advances Neural Information Processing Systems 32, pages 11542-11554. 2019.
[Der19] Michal Derezinski. Fast determinantal point processes via distortion- feeet inter- mediate sampling. In Proceedings of the 32nd Conference on Learning Theory, 2019.
[DIDM21] Michal Dereziński, Zhenyu Liao, Edgar Dobriban, and Michael W Mahoney. Sparse sketches with small inversion bias. In Proceedings of the 34th Conference on Learning Theory, 2021.
[DLLM20] Michat Derezióski, Feynman Liang, Zhenyu Liao, and Michael W Mahoney. Pre- cise expressions for random projections: Low-rank approximation and randomized Newton. In Advances in Neural Information Processing Systems, volume 33, pages 18272-18283, 2020.
[DM16] Petros Drineas and Michael W. Mahoney. RandNLA: Randomized numerical linear algebra. Communications of the ACM, 59:80-90, 2016.
[DM18] P. Drineas and M. W. Mahoney. Lectures on randomized numerical linear algebra. M. W. Mahoney, C. Duchi, and A. C. Gilbert, editors, The Mathematics of Data, IAS/Park City Mathematics Series, pages 1-48. AMS/IAS/SIAM, 2018.
[DM19] Michat Dereziński and Michael W Mahoney. Distributed estimation of the inverse hessian by determinantal averaging. In Advances in Neural Information Processing Systems 32, pages 1401-11411. Curran Associates, Inc., 2019.
[DM21] Michat Derezinski and Michael W Mahoney. Determinantal point processes in randomized numerical linear algebra. Notices of the American Mathematical Society, 68(1):34-45, 2021.
[DMIMW 12]] Petros Drineas, Malik Magdon-Ismail, Michael W. Mahoney, and David P. Woodruff. Fast approximation of matrix coherence and statistical leverage. J. Mach. Learn. Res., 13(1):34553356, December 2012.
[DMIMW12]] Petros Drineas, Malik Magdon-Ismail, Michael W Mahoney, and David P Woodruff. Fast approximation of matrix coherence and statistical leverage. The Journal of Machine Learning Research, 13(1):3475-3506, 2012.
[DMM06] Petros Drineas, Michael W Mahoney, and S Muthukrishnan. Sampling algorithms for E2 regression and applications. In Proceedings of the seventeenth annuul ACM-SIAM symposium on Discrete algorithm, pages 1127-1136. 2006.
[DMM08] Petros Drineas, Michael W. Mahoney, and S. Muthukrishnan. Relative-error CUR matrix decompositions. SIAM J. Matrix Anal. Appl., 30(2):844-881, September 2008.
[EM15] Murat A Erdogdu and Andrea Montanari. Convergence rates of sub-sampled Newton methods. Advances in Neural Information Processing Systems, 28:3052-3060, 2015.
[GGD+21] Vipul Gupta, Avishek Ghosh, Michal Dereziński, Rajiv Khanna, Kannan Ramchan- dran, and Michael Mahoney. LocalNewton: Reducing communication bottleneck for distributed learning. arXiv preprint arXiv:2105.07330, 2021.
[KL17] Vladimir Koltchinskii and Karim Lounici. Concentration inequalities and moment bounds for sample covariance operators. Bernoulli, 13(1):110-133) 2017.
[LLDP20] Jonathan I Lacotte, Sifan Liu, Edgar Dobriban, and Mert Pilanci. Limiting spectrum of randomized Hadamard transform and optimal iterative sketching methods. In Conference on Neural Information Processing Systems, 2020.
12

---

[LP19] Jonathan Lacotte and Mert Pilanci. Faster least squares optimization. arXiv preprint arXiv:1911.02677 2019.
[MM13] Xiangrui Meng and Michael W. Mahoney. Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression. In Proceedings of the Forty-fifth Annual ACM Symposium on Theory of Computing, STOC '13, pages 91-100, New York, NY, USA, 2013. ACM.
[MSM14] Xiangrui Meng, Michael A Saunders, and Michael W Mahoney. LSRN: A parallel iterative solver for strongly over-or underdetermined systems. SIAM Journal Scientific Computing, 36(2):C95-CC C118, 2014.
[MZ20] Shahar Mendelson and Nikita Zhivotovskiy. Robust covariance estimation under
L1 L2 norm equivalence. Annals of Statistics, 4803):1648-1664, 2020.
[NN13] Jelani Nelson and Huy L Nguyên. Osnap: Faster numerical linear algebra algo- rithms via sparser subspace embeddings. In 2013 ieee 54th annual symposium on foundations of computer science, pages 117-126. IEEE, 2013.
[PW17] Mert Pilanci and Martin J Wainwright. Newton sketch: A near linear-time optimiza- tion algorithm with linear-quadratic convergence. SIAM Journal on Optimization, 27(1):205-245, 2017.
[RKM19] Farbod Roosta- Khosss-an and Michael W. Mahoney. Sub-Sampled Newton methods. Math. Program., 174(1-2):295 226.,29,2222--- March 2019.
[RT08] Vladimir Rokhlin and Mark Tygert. A fast randomized algorithm for overdetermined linear least-squares regression. Proceedings of the National Academy of Sciences, (05(36:13212--3311 2008.
[RV13] Mark Rudelson and Roman Vershynin. Saanson-rright inequality and sub-gaussian concentration. Electronic Communications Probability, 18, 2013.
[Sar06] Tamas Sarlos. Improved approximation algorithms for large matrices via random projections. In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS '06, pages 143-152, Washington, DC, USA, 2006. IEEE Computer Society.
[SRD+ 18] Philip Schmidt, Attila Reiss, Robert Duerichen, Claus Marberger, and Kristof Van Laerhoven. Introducing wesad, multimodal dataset for wearable stress and affect detection. In Proceedings of the 20th ACM international conference on multi- modal interaction, pages 400-408, 2018
[Trol1] Joel A Tropp. Improved analysis of the subsampled randomized Hadamard transform. Advances in Adaptive Data Analysis, 3(01002): 15-126, 2011.
[Tro12] Joel A. Tropp. User-friendly tail bounds for sums of random matrices. Foundations of Computational Mathematics, 12(4):389-433 434, August 2012.
[Tro15] Joel A Tropp. An introduction to matrix concentration inequalities. Foundations and Trends in Machine Learning, 8(1-2):1-230, 2015.
[Woo14] David P Woodruff. Sketching tool for numerical linear algebra. Foundations and Trends in Theoretical Computer Science, 10(1-2):1-17,, 2014.
[WRKXM18] Shusen Wang, Farbod Khoosaan,,,,,nni, Peng Xu, and Michael W Mahoney. GI- ANT: Globally improved approximate Newton method for distributed optimization. Advances in Neural Information Processing Systems 31, pages 2332-2342. 2018
[XRKM17] Peng Xu, Farbod Roosta- Khorasann, and Michael Mahoney. Newton-type methods for non-convex optimization under inexact hessian information. Mathematical Programming. August 2017.
[YXRKM18) Z. Yao, P. Xu, F. Roosta- Khorasani, and M. W. Mahoney. Inexact non-convex Newton-type methods. Technical report, 2018. Preprint: arXiv: arXiv:1802.0699 802.06925.
13


Reviews:
[{"review_id": "hdz7WoaVg_-", "reviewer": "Reviewer_1HfP", "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). ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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). \n\nI 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?\n\nMy 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. \nAny 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}. \nNote 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}?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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. \nAny 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}. \nNote 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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "VlFgVmGqtzI", "reviewer": "Reviewer_Stjd", "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. \n\nThe 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.\n\nThe authors also consider the special case of ridge regression. ", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nI have several (mostly minor) comments:\n\n1) 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. \n\n2) 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?\n\n3) 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.\n\n4) 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. \n\n5) Condition 2: What does alpha=O(1) mean here?\n\n6) 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?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No limitations and societal impact", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "FpgfLDIy5s2", "reviewer": "Reviewer_nNxo", "summary": "The paper studies a method to speed up Newton-type optimization methods using randomized sketching techniques (specifically, leverage score sparsification-based sketching). ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nThis 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. \n\nThe paper is very well written and the contributions are clearly justified with theory and experiments.\n\nSome comments:\n- \"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. \n- 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\").\n- Consider increasing legend sizes in Fig 2 and 3, they are very difficult to parse.\n\n---\nThanks for the responses, and good luck.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "1oxzFKQgVgv", "reviewer": "Reviewer_WJXY", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The theory is well presented and the intuition behind is well explained. \n\nMajor questions/concerns:\n1. 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?\n2. 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.\n3. Can the authors provide more insights about the matrix Q, which plays a crucial role in the analysis?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors addressed them.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

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)