Linear and Kernel Classification in the Streaming Model: Improved Bounds for Heavy Hitters
Authors: Arvind V. Mahankali
David Woodruff
Venue: NeurIPS 2021 Poster (2021)
Keywords: Linear classification
heavy hitters
kernel classification
streaming algorithms
sketching
tensors

Abstract: We study linear and kernel classification in the streaming model. For linear classification, we improve upon the algorithm of (Tai, et al. 2018), which solves the $\ell_1$ point query problem on the optimal weight vector $w_* \in \mathbb{R}^d$ in sublinear space. We first give an algorithm solving the more difficult $\ell_2$ point query problem on $w_*$, also in sublinear space. We also give an algorithm which solves the $\ell_2$ heavy hitter problem on $w_*$, in sublinear space and running time. Finally, we give an algorithm which can $\textit{deterministically}$ solve the $\ell_1$ point query problem on $w_*$, with sublinear space improving upon that of (Tai, et al. 2018). For kernel classification, if $w_* \in \mathbb{R}^{d^p}$ is the optimal weight vector classifying points in the stream according to their $p^{th}$-degree polynomial kernel, then we give an algorithm solving the $\ell_2$ point query problem on $w_*$ in $\text{poly}(\frac{p \log d}{\varepsilon})$ space, and an algorithm solving the $\ell_2$ heavy hitter problem in $\text{poly}(\frac{p \log d}{\varepsilon})$ space and running time. Note that our space and running time are polynomial in $p$, making our algorithms well-suited to high-degree polynomial kernels and the Gaussian kernel (approximated by the polynomial kernel of degree $p = \Theta(\log T)$).

Linear and Kernel Classification in the Streaming Model: Improved Bounds for Heavy Hitters
Arvind Mahankali
David P. Woodruff CMU
CMU
amahanka@andrew. cmu edu
dwoodruf@cs cmu,
Abstract
We study linear and kernel classification in the streaming model. For linear clas- sification, improve upon the algorithm of [1], which solves the & point query problem on the optimal weight vector w. E Rd in sublinear space. We first give algorithm solving the more difficult & point query problem on w. also sublinear space. We then give an algorithm which solves the related lz heavy hitter problem on u... in sublinear space and running time. Finally, we give an algorithm which can deterministically solve the & point query problem on ws, with sublinear space, improving upon that [. For kernel classification, w. E IR"" is the optimal weight vector classifying points in the stream according their ndh -de-ree polynomial kernel, then we give an algorithm solving the & point query problem on w. in poly( (llodd) space, and an algorithm solving the lg heavy hitter problem in poly( (flood) space and running time. Note that our space and running time is polynomial in making our algorithms well-suited to high-degree polynomial kernels and the Gaussian kernel (approximated by the polynomial kernel of degree (log 7)). Our algorithms for kernels are in fact special case of a more general algorithm we give for low-rank tensor inputs.
Introduction
We consider logistic regression, and more generally, linear classification, in the streaming model. In our setting, we are given dataset consisting of T' examples (æx, Wr), where / E [T], E Rd E 1), The examples arrive one by one, and moreover, the nonzero coordinates of each example x, arrive one by one. Our goal is to estimate the weights w, I2d of the optimal linear classifier for these examples. Here, w, := argmin Σn Ely xx) + 3 wll2 where is loss function satisfying certain conditions described Section 1.3 the prototypical example of l that we consider is the logistic regression loss function - and X controls the strength of the & regularization. Finally, we assume that is very large, and therefore wish estimate the weights of w. in space that is sublinear in d. This is important both in settings with devices with limited memory constraints, such as routers or sensors on network, as well as in machine learning problems with many features. Machine learning problems with very large number of features arise in many natural language processing tasks, for example- - one motivation for [], the precursor to our work. is that the use of n-gram features when analyzing text data can lead to very large memory cost. Our goal, and that of M. is to find features which are the most useful for classification - as pointed out in II previously known sketches for compressing classifiers do not achieve this goal.
Formally, consider the following problems in this work:
In is mentioned that in an experiment on the dataset 2 "we recorded 47M unique word pairs that co-occur within 5-word spans of text... ... [requiring] approximately 560MB of memory."
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Problem 1 (ep Point Query, for p 1 1, Let E 1). At any time t E [T] in the stream, given an arbitrary query i E [d] the goal to output w; such that |ut w.,sl S E ||l,llpp
Problem 2 (lg Heavy Hitters), Let E (0, At any time t E [T] in the stream, the goal is to outpur a list L [d] of size at most O such that L contains all indices i [d] such that |wa,s| 2 e|lw>| auulll2-
Interpretability is one of the main motivations for the above problem formulations - as argued by D. finding the largest weights in w. is equivalent to determining which features are the most important in classification. Also, note that &2 point query is strictly more difficult than e point query to see why, note that in the worst case, ||x, || can be larger than || 2l2 by a vd factor. Thus, for instance, if an algorithm uses poly(= log d) space to solve & point query, then it will use at least dd(1) space to solve &g point query (by replacing with e/ /d), which is far too large in streaming settings.
1.1 Our Contributions
le point query and heavy hitters (via a reduction to turnstile & point query and heavy hitters) We give efficient algorithms for solving & point query and lg heavy hitters. In the approach of M. single Countsketch matrix [3] is used to maintain a sketch 2, of the weights. 24 is updated by online gradient descent according to 2++1 -1-\m% 2+ 32 (y+2 Rx, Rx,, where R a Countsketch matrix scaled by 1/v5, where s is the column sparsity of R- by [4]. R is a Johnson-Lindenstraul (JL) transform if is chosen to be large enough. To estimate the coordinates of w.,, the recovery procedure of 33 is applied to /sz, where = (Σi= 20/TT. In addition, [ only obtains the L point query guarantee, since the JL property of R is only applied to show that R preserves the inner products between C1, e edd
To resolve both of these issues, we decouple the JL matrix from the point query/heavy hitters sketch, i.e, we a JL matrix R, and separate sketch S for l2 point query/heavy hitters in the well-studied turnstile streaming model. First, we maintain ž2, which is updated using online gradient descent as in M. In addition, we maintain an additional vector Wi Rd, which is updated according to Wi++1 t (1 - >1// ww "Wwe (vi Roy)a, The motivation for this update is that it is essentially the online gradient descent update W1+1 + (1 ) - -nyye (ya x1)xx, we would perform without any sketching, but we replace E' "y( 24) with 2 RXx) due to space constraints. We do not have enough space explicitly maintain Wi, but since the updates W; are additive, we can still give it as the input to turnstile streaming algorithm for & point query/heavy hitters. We show that Wy = + Σ Wi is close to w. in &g norm, and thus it suffices to solve lg point query and le heavy hitters on WT. In summary, we give algorithms for &g point query and heavy hitters with O(s log(dT)
space and 1 ô success probability.
Deterministic & point query In addition, we show that & point query can be solved determin- istically, and with space complexity log=)))((d): which smaller than the O(==1 log"(d/))) (d/3)) space complexity of []]. Deterministic sketches are useful as they allow for inputs to be chosen as a function of past responses of the sketching algorithm, and thus provide adversarial robustness [J. To obtain a deterministic algorithm, we replace the Countsketch matrix used by MI with an e-incoherent matrix. Here, an E-incoherent matrix R E Rexd is one whose columns are almost orthonormal, meaning that for all i # j. (R,, R2) S E, and all columns of R have lg norm 1. Matrices that are e-incoherent were previously applied to streaming problems by [6), and can be constructed deterministically, To improve on the space complexity of [I) we change the recovery procedure: to estimate W.,i. we simply compute (R,, z) where z is the compressed weight vector, rather than applying the Countsketch recovery procedure of 3
le point query (via a combined JL/point query sketch) Inspired by our deterministic l point query algorithm, we provide an alternative algorithm for & point query, for which the space complexity has smaller dependence on 1/A. We observe that the sparse JL transform of 4 can be used not only to preserve norms with high probability (i.e., to satisfy the JL lemma) but also to provide an lg point query sketch directly, using a different Eg point query recovery procedure. Our procedure does not involve any median based operations. Instead, to estimate w.,; given the compressed weight vector z, we simply compute (R,, z). Recall that [1 multiplies the sketching matrix by / in order to perform the recovery procedure of 3 our new procedure also avoids this rescaling, and thus achieves space complexity of (( -2 (dg(dd/8) up to problem-dependent parameters. The space complexity of this algorithm has smaller dependence on 1/2 compared to our &g point query

---

algorithm discussed above. In addition, we use online gradient descent regret bounds to show that the estimation error of our algorithms involves term that is proportional to -iス.. Thus, for the error to be at most e||w,lll or Ell [/.. 1. T must be at least a certain value. Our l2 point query algorithm 1 using a combined JL/point query sketch requires T to grow as xa as opposed to our &g point query algorithm which makes black-box reduction to the turnstile model, which requires T to grow as xs-
The main idea of this algorithm the observation that if w. is the optimal weight vector, then (Rw,, Re;) is a good estimate of (w., eq) = W.,i this motivates our query procedure. Note that this fact is implicit the guarantees of a JL. matrix. This recovery procedure has also been used for turnstile & point query by [ (which motivated our deterministic & point query algorithm above). The same recovery procedure was also used by 771 in the context of distributed differentially private heavy hitters. To our knowledge, our work is the first to use this idea in the setting of & point query for linear classification. Note that for l2 point query in the turnstile model, it is preferable to use Countsketch (Countsketch is also used by (I), since for an update to single coordinate, the update time with Countsketch is O(log(1/o)) while the update time when using a sparse JL matrix [4) is 1og_// log(L/6)). However, in the context of linear classification, we find that using a JL matrix with the recovery procedure (Rw,, Re,) x W.,, reduces the space complexity by a factor of poly(e-1 (o/ddd)), as long as T = (d). This is because the sketching matrix already needs to be JL matrix in order to preserve certain inner products. In this case, using the Countsketch recovery procedure requires scaling& 2 by a factor of V where 8 is the column sparsity of R. which in turn requires increasing the accuracy parameter 8 of R in order to solve l2 point query (or & point query).
Worst-case data order guarantees For all of our algorithms, we do not make assumptions on the order of the Tú, unlike [. In [ the pairs in the set {z11 v1)...., (IT, seryyr)) yr)} are required to arrive in the stream in a uniformly random order. The following is given in [ as a heuristic explanation: "we believe this condition is necessary to avoid worst-case adversarial orderings of the data points since the WM-Sketch update at any time step depends on the state of the sketch itself, adversarial orderings can potentially lead to high error accumulation ... Intuitively, it seems reasonable to expect that we would need an 'average case' ordering of the stream in order to obtain similar recovery guarantee to the batch setting." It is perhaps surprising then that we are able to entirely remove this assumption. We do this by showing that instead of using Corollary can use argument from first principles based on online gradient descent regret bounds.
[8] (which is used by (I) we
Classification with tensor inputs We consider a variant of linear classification where the inputs Ie and the weight vector w. are p-th order tensors (i.e., are vectors in R and moreover, the z have rank at most k meaning F = > Ft is motivated by applications of tensor regression, for instance in neuroimaging [9 10] where the covariates have a tensor product structure. Furthermore, the x, may be of low rank in applications
(f.2) @ .... @ xt (1.9) where the x (8-1) e Rd. This (6.1) @ z
for instance, in the case 2, [9] mentions that in [00, tensor regression is performed after principal component analysis is first performed on the x4. In such a setting, we wish to obtain & point query and heavy hitters algorithms with most a polynomial dependence a polynomial dependence on p. To achieve this, we use tensor sketching techniques of [I], which develops a sketching matrix M e mmddd where m = poly(s ppllss"pppooooa d). such that M is a JL matrix, poly
log d and 1/e, and moreover
and Sp can be computed very efficiently for x E Rd (specifically,
d) nnz(x) time), without explicitly forming SP. Thus, for & point query. we can use M in the same way we use the sparse JL matrix of 4 in the combined JL/point query sketch above.
For le heavy hitters, our algorithm is as follows: (1) for each mode i E [p]. we determine the coordinates j [d] which contribute more than an e fraction of the &g norm of w - in other words, we want to find all E [d] such that [|,,, (:........ .. i, ......:)lll
:)ll2 2| 2 </|w,|12. where w:........... .....:) consists of those coordinates of w. which have index j in the 5th mode. This gives us a list L, [d] of size at most O(1/e²), for each i E [p]. (2) Then, we find the (at most O(1/e2)) indices (i....., ip) of w. in [d]" such that |w. (i1, i2,................ fp)] 2 ll. We do step (2) using the Li, by inductively constructing prefixes of these coordinates, one mode at time. For each i (p). we build an auxiliary data structure which can estimate [lw[ji,.... :iss, "isi.....:))
for any prefix (i,.....i of length this is also done by using the sketching matrix of M. Both our lg point query and lg heavy hitters algorithms for pd -oderr tensor inputs have poly(= "p pllog (dT))))))) space and query time, and poly(s -'p lo)(dT/8)) Σ nnz(a(())) update time, up to problem-dependent parameters.
3

---

When the inputs are nt order tensors of low rank, our ly point query and heavy hitters algorithms for tensor inputs give significant savings in update time when compared to standard la point query/heavy hitters algorithms. To see why, note that when the 22 are rank-k tensors, the update to w. (defined
above) is wt-1 < (1 An) "evel (vt=t Mxr)) E (1,1) (1.2)
(t.p). Using
.... @ Fi
standard l heavy hitters algorithm on ūy requires explicitly forming sr!" (1.1) @ a
(1.2)
@ xz (6.P)
if the ott (1.3) are dense, then standard &2 heavy hitters algorithms would require at least d update time,
as opposed to our algorithm, which only has poly(s "p log(dT/6)) kdd update time - even when p = 2, if k is small, then this is a significant improvement.
Kernel classification Kernel logistic regression (KLR) is well-known classification method in the field of statistical learning, see e.g., [2] and its many citations. We obtain the first results for finding the large weights of a classifier in the kernel space for the polynomial and Gaussian kernels. A succinct summary of the classifier, such as its list of heavy hitters with their approximate values, is especially important for kernel classification, since the dimension of the kernel space can be much larger than d, and in the case of the Gaussian kernel, even infinite. In this setting, for the polynomial kernel, classification is done using =t to predict y/- - thus, this is special case of the setting where 24 is a tensor of rank at most k. discussed above. As in [II] we can approximate the Gaussian kernel via a Taylor expansion, using polynomial kernel of degree Olog T). Note that if (ii, -2,,..... kpp) is an index in [d]" and (2,, ....................... ......p Jp) is re-ordering of (i1, -2,-.. dp), then one may want to consider Tú ... Fi, and In ... ...Wi, Wi, to be the same feature. To get around this, suppose (i1, ig. .2....,,.. .,2p) and it is an E-heavy hitter when ignoring permutations (formally defined in the appendix). Then, if we apply our algorithms from the low-rank tensor setting with an accuracy of e e/pp/2, (ii, i2,,..,. ip) will be detected as heavy hitter. An interesting open question is whether this can be done in poly(=""plogg) /5)) space even when c is equal to p. We leave this question to future work.
has a Hamming distance of most from the set of indices of the form (i, (i.......)) i)
Experiments We empirically compare both of our algorithms for le point query with the WM-Sketch algorithm of M. F where all three algorithms are restricted to certain memory budgets, following the setup of M. Our le point query algorithm that makes use of combined JL/point query sketch leads to improved performance estimating w. compared to the WM-Sketch algorithm, with significantly improved performance for a larger memory budget the RCVI dataset [33, though the WM-Sketde algorithm performed better than our black-box reduction- memory budgets, these two algorithms appeared have similar weight recovery performance on the RCVI dataset, but our other l2 point query algorithm using a black-box reduction to turnstile & point query had much lower error in recovering the top weights.
lz point query algorithm. For smaller
Using the Top Weights or Compressed Classifiers for Classification Here we give additional motivation for estimating the top weights of w., or applying sketching to classifiers. We performed an experiment on the RCVI dataset (I3), which we divided into a training and testing half we obtained weight vector E Rd by using online logistic regression on the training half, and computed the accuracy when using w. for linear classification on the testing half (where w is the K- K-sparse vector whose entries are the top K entries of w). One noteworthy result of this experiment is that when K = 400, the accuracy on the testing half is 98.9%, while the full weight vector w (which has 41130 nonzero coordinates) achieves 95.7% accuracy. The full details of these experiments are given in Appendix F We do acknowledge that there are no theoretical guarantees for using only the top K weights for K < d, and there may be datasets where using the top K weights of w,, may not lead to good performance unless K is very large. We give theoretical guarantees for using a compressed classifier, that is, using E" R instead of w. where R is a sparse JL matrix and is the average iterate of sketched online logistic regression: if L = + Σi= E(grw xx) and L = + E E(yz=" Ra.:),
then L._ - Σ < =|| <llw=l2 as long as R has O( (8)) rows (up to problem dependent parameters) and is a certain value. We give full details in Appendix D Finally, we note that in a stream, finding Eg heavy hitters in the turnstile model requires min( v l///.//o////6///// log(1/6)/=²) space, by Theorem 4.3 of [14]. In particular, estimating all the coordinates would require poly(d) space, meaning that if we wish to obtain sublinear space complexity in our setting, it is reasonable to expect that we cannot do better than estimating the heavy hitters, without additional assumptions.
2 We use the implementation by the authors of (1] at /tetps://githin wmsketch Our implementations of our la point query algorithms also based on their code.
4

---

1.2 Related work
Turnstile Point Query and Heavy Hitters There is a large body of work on finding the heavy hitters in a data stream. For a survey, see, e.g.. [[3]. Of particular relevance to this work is the CountSketch algorithm of [3 for finding & heavy hitters. We note that [T6] I7 improve the memory of the algorithm of [3] by logarithmic factor, but do not handle negative updates, which may arise in our setting. We also need deterministic algorithms for finding & heavy hitters, and we use the algorithms of [6] which use e-incoherent matrices, and improve upon the earlier work of Ganguly [8]. We note that the CountMin algorithm of [1]] also achieves the & heavy hitter guarantee, though it is randomized, while here we seek a stronger deterministic guarantee. Indeed, for randomized algorithms, we can achieve the stronger &2 heavy hitter guarantee.
Point Query and Heavy Hitters for Classiiication/Regressii lated to ours is [. which solves E point query on w, in the streaming model, and achieves space up to grobeem-depnddet parameters. Unlike M. we give an algorithm with provable guarantees for finding the at most s-2 heavy hitters in sublinear time, and we solve the stronger & point query and heavy hitters problems in addition e point query.
The work that is most closely re-
O( OlE-Ioog
(d/8)) (dg")(())
Another related work with a somewhat different focus from ours is MISSION [2]]. The MISSION
algorithm finds a k-sparse solution for least-squares regression in low space, using Countsketch. [20] modifies the SGD algorithm: in each iteration, a uniformly random training example is selected and the SGD update is given top k features, and the vector with these k non-zero coordinates is used for the next SGD update. MISSION focuses on convergence of the iterates 3 k-sparse vector f while in the analyses of our l point query/heavy hitters algorithms, we desire/show convergence in ég norm of Wy w. up to additive error e|[w,|12 for potentially dense w.. Our gradient updates are thus different, as we perform the update Wi+1 + (1 (1- An yxr - n/ (y(," Rx, ).r, i.e. our update does not involve truncation by taking the top k estimates from Countsketch. We also note that (20) gives theoretical analysis in the setting where the x, have i.i.d. Gaussian entries, and J/: = x 3 + w, where we is Gaussian noise and 1 is a k-sparse vector, while we do not assume the inputs/noise are Gaussian.
Countsketch data structure then, Countsketch is used to select the
One more work 21 proposes the BEAR algorithm, which is a sketched version of the online L-BFGS algorithm. The setting of [2I] is similar to ours turs-this this work aims to estimate the top coordinates of the weight vector and achieve the & point query guarantee. The proof of Lemma 3 in (11. that BEAR minimizes a "sketched" version of the loss function, appears to rely on the claim that MISSION minimizes this sketched loss function - however, as noted above, MISSION instead aims find an optimal k-sparse weight vector. We also note that (21] does not propose/analyze an algorithm for recovering all the heavy hitters for the optimal weight vector in sublinear time, while we show how this can be done using turnstile fa heavy hitters algorithms with small overhead in space/update time and no overhead query time- - fast query time can be useful when the Vt, and therefore the gradient updates, are sparse.
Other Works on Sketching for Classification We also note that there are a number of other (less closely related) works which use sketching for linear classification - we compare to these works in Appendix A
To our knowledge, our work is the first to consider linear classification with tensor inputs, and kernel classification, in the streaming model, with the goal of recovering the top weights of these classifiers.
1.3 Preliminaries
As in D. we are given a loss function É, training examples {(1,, Beeee A O, and w. := argminwERt + Et= ((yewTaz) xx) + 2 2//w We use online gradient descent regret bounds, specifi- cally Theorem 3.1 of (2). We use a learning rate of 1)₁ = D/GVV,, where is an upper bound on ||w-|12 and G is an upper bound on the norm of the gradient (D and G are discussed further in the supplementary material). The following assumptions hold throughout the paper:
Definition 1.1 (Running Assumptions). (1) l is convex, 8-smooth, and H H-Lipschitz. (2) For all t e [T], | < 1. (3) There exists a constant T > 0 independent T such that [.,. ll2 2 T.
The last assumption above is not explicitly made in 0. but in Theorem of (. one of the hy- potheses is that T is at least 1/ w/|l,,11 (omitting other dependencies). Since w. itself may depend on
5

---

T1, .2....,, 2r, and thus T, we explicitly make this assumption to prevent circularity. This assump- tion is necessary for making use of online gradient descent regret bounds, to ensure ||w,ll2 does not decrease faster than the average regret.
2
Eg Point Query and Heavy Hitters
First, we define a "sketched" loss function Σ(z) = +I Uy== Rx,) + 1 as in M. Here, R is a sparse Johnson--Lnneestrauus matrix llet let recall the properties of sparse JL matrices:
Theorem 2.1 (Sparse JL Matrices 4 Let d E N. and E, å E (0.1), 1). Then, there exists a distribution
on matrices S E R &xd, where k = ( 2 log(1/0)) and S has = O(s 1og(1 /5)) nonzero entries
per column, such that for any x E Rdd with probability 1 - 6, (1 - =)]|=||2 - ||5x||2 S (1 + e|||=||2-
=. := argmin [()), then 2, is compressed version of w, in the following sense: Theorem 2.2 (Batch Setting). Let 5, E (0, 1), and suppose E is B-smooth and ||xe|2 S for all t. Define w. = argmin [ww) and z. argmin T(2).. If is sparse JI. matrix with O( 2og((") 18). 3/A) rows, then with probability 1 - 5 over R 2| Rw. 2l I E||wall2.
The proof of Theorem 2.2 is in the appendix. It uses a primal-dual argument that is similar to the one used to prove Theorem I of M. The main difference is that [ only shows that ||z, - -R, /la, S el[w,]|1- This is because they only apply the JL property of R to approximately preserve inner products between the vectors e1, , Cd- To prove Theorem [2.]] we modify their analysis by also using the JL property of R to additionally show that the inner products (Iz, w.) and (c,, w.) are well-approximated by (Re,, Rw.)) and (Re;, Rw.) respectively, for all E [d]. and & E (7].
Our algorithm proceeds by a reduction to standard & point query and heavy hitters, in the turnstile streaming model. Let us recall the definition of the turnstile streaming model, and the best known results for these two problems in the turnstile model.
Definition 2.3 (Turnstile Streaming Model). In the turnstile streaming model, the input is vector V E TR. Updates are of the form (i, A) where E [n] and A E R. signifying that vs is incremented by A. For 82 point query in the turnstile model, queries i E [d] should be answered with an estimate th of such that ( - vzl S. e||vi|2 For E2 heavy hitters in the turnstile model, queries should be
answered with a list L of length (1/=²² containing all E [d] such that |uz] 2 e||u||22
Theorem 2.4 (Turnstile lg Point Query 3), Theorem 2 of [23] Lemma 1 of (24). There is an algo-
rithm for urnstile E2 point query with space complexity O D(e02(log(1////11 log(1/5)), update time ((log(188)
and query time (llo(1/8)) and success probability
5.
Theorem 2.5 (Turnstile & Heavy Hitters (25)). There is an algorithm for turnstile Eo heavy hitters
with O( 2 n) space complexity, O(log n) update time and O(E D(=="poly(log n)) query time, and success probability 1 11111ppppt 1/poly(n).
The key new idea of Algorithm according to Wi+1 < (1- Ar7 Wi - myye (312 Ræ,) Note that we is an approximation to u. E R which obtained by the standard update Wt+1 < (1 Xnk) - n.ye (y,w," xx 2,) We cannot maintain Wy explicitly, but we give it as input to the linear sketch which we refer to A in Algorithm For &2 point query, A is a Countsketch matrix, and for E heavy hitters is Expander
1 is that we implicitly maintain a vector Wi E Rd which is updated
Sketch (25] l. In our QUERY procedure in Algorithm 1 we apply the query procedure of A to AWr, where WT
+ D
-l Wy. This is justified since WT is a good approximation to w.:
Theorem 2.6 (Approximating w. with wT). Let e, E (0, 1). Suppose all of the assumptions in Definition 1.1 hold. Suppose R. is sparse JL matrix with O(x-2 -e --2223 log(dT (8) max(1,3/A) rows. If Wi is updated according to Witi + (1-2n) W 2 RY.) and we = 7 Et Wi
then w.ll2 S e||w. ll2 as long as T 1(max((8' )/(8 6477), H ((A(((++>)))
Theorem 2.7 (l, Point Query and Heavy Hitters for Linear Classificatton). Suppose s, E (0, 1), all of the assumptions in Definition I.I holdd and T 2 Mmax(( (X*++)) ", H, (()))+))
Here, A is a linear sketch meaning that, if Av is itself considered a vector, then Au is a linear map in terms of Thus, the update weti + (1 Any w nyy ll (vr of Ræ, Ja can be implicitly done in sublinear space.

---

Algorithm In this algorithm, we give our black-box reduction to &2 point query or heavy hitters. Here, A denotes a linear sketching data structure for l2 point query or Eg heavy hitters. A denotes the contents of the sketch time step 1, and A denotes the sketch containing the average of the contents of AI,.... Ar. Since A is linear sketch, A can be maintained using only constant factor more space than that needed to store A₁. Here, QUERY denotes the query procedure of A, that is, the query procedure described in Theorem 2.4 for point query and Theorem 2..5 for lg heavy hitters. Note that we can skip the step used in [1] where 2++1 is projected onto an lz unit ball, since even without projection, || S ((H/A) by the triangle inequality and induction.
function INITIALIZATION!
R E Rxxd is sparse JL matrix with = O( (lo(dd max(1, 3/2)) rows.
21 E E is set to E R²
The contents of the sketch A are set to 0 E E2.
end function
function UPDATE ye)
Zt+1 < (1 - ) mwh ll ( Rx, Rrx)Rrr
Rescale the contents of A by (1 Xmp))
For each nonzero coordinate E [d] of Mt, update A according
(i, 7.3e 2f Rx,)
end function
function QUBRY()
A + + E A
Return QUERY (A) end function
For l2 point query, Algorithm has 2 (TT /8) max(1, + log2 space complexity,
(ogg=dd max(1, /B/)) + log(1/8)) nmz(ax) update For l heavy hitters, Algorithm 1 has 0 log(dT/o) (1xx(1,//A) + logg space complexity, O(X-2--18 log(dT /5) max(1, (3/X) + log d) nnz(x;) update time, Ole=2poly(lg d)) query time, and success probability 1/poly(d) 8.
time, ((18g(1/8)) query time, and success probability
The proofs of Theorems 2.6 and 2.7 are given in the supplementary. Note that the query times Ex ExpanderSketch (25 respectively.
simply those of CountSketch 3
3 Deterministic Ł Point Query and a Second Algorithm for &g Point Query
We now give a simple deterministic algorithm for & point query with sublinear space. The algorithm is based on that of 11. However, the sketching matrix R is now e-incoherent matrix:
0. Then, there exists matrix A E Rmxx where m = Oe min(log n. (log n/ /log log n + log 1//))>>)),, such that for all E [n]. || 1, and for all distinct i,j E [n], (A,, S c. Moreover, A be constructed deterministically in poly(n) time. A does not need to be stored explicitly, and each column can be generated on demand in low space (we describe this in the supplementary).
Theorem 3.1 (s-Inccherent Matrices (6). Let E N and
We first analyze the algorithm in the batch setting, showing that || - w. Il S <el|w- S.w.ll1. and then using online gradient descent regret bounds to show that the same is true for z. Our analysis of this algorithm is similar to 1 however, using the recovery procedure in Algorithm 2 leads to an improved space complexity compared to (here we assume | S y as M):
Theorem 3.2 (Analysis of é Point Query on w. with Incoherent Matrix). Suppose all of the assumptions in Desinition I.I hold, | S for all E (T], and there exists some constant 0 > O independent T such that [.wll 2 If R and are defined as Algorithm 2 with R being an incoherent matrix, then ||=T Wolloo S <e]lwell l1, as long T 2 (2(H+*(L + Ven)* ((X)(()))))))
7

---

Algorithm 2 Algorithm for l point query and &2 point query. For E point query, R is an incoherent matrix with OE 2 llog d max(1, 7 3/A)) rows, while for &g point query, R a sparse JL matrix with O(= loog( dT//)) max(1, 8/X)) rows.
1: function INITIALIZATION()
2: R. E Rxxd is defined in the caption.
3: 21 E I2th is initially set to O.
4: end function
5: function UPDATE(#t, (1))))
6: -t++1 <- (1 - X²))== Miltel (yeat Rxx) Roc
7: end function
8: function (STIMATE-WEIGHHSS()
9:
2T + +E +
10: return R4. 2T
11:
end function
If R' is instead sparse JL matrix with O O( log(dT/6) max(1, rows, Algorithm 2 gives an l2 point query algorithm. Note that for la point query, the space complexity of Algorithm 2 has better dependence on À compared to Algorithm
Theorem 3.3 (&z Point Query using only JL Matrix). Let E, (0,1), and suppose all of the assumptions (.. hold. If R and E are defined as in Algorithm 2 with R being sparse JL matrix, then || w. S E|[w,l12 with probability 1 - 8, as long as T 2 Q(H* (()
4 Low Rank Tensor Classification and Kernel Classification
We next consider lg point query and heavy hitters in the case where I2 E Rdd is a pth order tensor, of rank at most k and is provided as the sum of k rank-1 tensors. This is motivated by polynomial kernel classification as well as other applications in classification with tensor inputs mentioned above. Our main tool will be JL matrix which can be quickly applied to outer products of vectors [1:
Theorem 4.1 (Recursive Tensor Sketch - Follows from the Proof of Theorem 2 of [T]. Ler n. p. d N, 5 > O. Then, there is random matrix R E m= with
O pplog(1/ea
such that for 2, y E Idd PrMll(ER Ry) (z. v) =|| Il [ I 1 ö and for æ1, 22,... Tp
Rd, R(x1 X x2 x & xx)) can be computed in p log (1/0)) Σ nnz(z;) time.
This immediately gives us an algorithm for Eg point query, since Algorithm 2 can be replaced by any JL matrix. Note that the query procedure can be done in poly log(dl /5) time (up to problem-dependent parameters), since for = (i,,.... ip) E [d]e, R, = R(ei, .... & ei,)) can be computed in poly(r (p log /5)/)) time. For completeness, we explicitly give the pseudocode for this algorithm in the supplementary the guarantees of this algorithm are stated below:
Theorem 4.2 (Tensor Classification Point Query). Let e, 8 E (0.1) 1) and suppose all of the assump- tions in Definition hold. Let R be the JL matrix of Theorem 4.1 with poly(s-1play *plog(dT/8)) B/A)) rows, and suppose T 2 2(H (X*==t))
Then, with probability
8, |R"
w. welloo el[w>|ll. Thus, there is an algorithm for & point query w. with space complex- ity and query time poly(E (olyE="'log(dde (og((d/)))) + 3/))), and update time (ills=pplo(([@88) 8/X)) Σ. E mmn((x()))) I kapoly(= "aapi/==ppppp(dII1 (log(d//5)(11 (/A)))
Next we consider & heavy hitters on w. E d To simplify the problem, we reduce to the setting where we are given E Rd and is given updates of the form v < u + 21 @ ... & Fp (where we are given ........ pp). Our algorithm for this setting is shown in Algorithm with the following guarantees:
This reduction is valid by Theorem 2.6 since updates to are of this form.
+ *R(z) @ T2 ... @ 2p)) can be computed in one pass over the nonzero entries of 21, ....... Tpi by the construction of [1I. R is essentially a tree of sketching matrices, with 2p- - nodes. At the base of this tree are matrices R. ...,, RP, which can be separately applied to æ1,..., Ep respectively - from this point, only pooge"' (d/o) space is needed to finish the computation.

---

Figure 1: Blue Algorithm green Algorithm [1 and red is the algorithm of M1. We show the median of 5 trials, with error bars showing the smallest and largest relative errors across those trials.
2
Theorem 4.3 (Tensor l2 Heavy Hitters Algorithm). Let e, E (0, Let E Re, which can be incrementally updated by a rank-1 tensor. Then, Algorithm 3 returns a list contain- ing all (i,,22,...,,7 poly(e pogg(d//)) the query time is poly(e poly(e-"plog(d plog(d/0)), and the time needed for the update v f- v +. for rank-1 tensor x = x1 0 .... @ Tp. is polyle "plog(d/6)) En nnz(sr))
[d]e such that [o(i1...., :p2) 2 El|u|12- The space complexity is
Theorem 4.3 implies that, by adapting Algorithm 1 but with R being the JL matrix of Theorem instead of a sparse JL matrix, we can get an algorithm for heavy hitters in the linear classification setting, where the are rank-k tensors, and with space and time complexity polynomial in p.
Theorem 4.4 (Tensor Classification & Heavy Hitters). Let e, 5 E (0. 1). Suppose all assumptions Then, there is an algo- rithm for lg heavy hitters on w, with space complexity poly(e plog(dd (5) (3/2)), query time poly( log(d/6)), and update time kd poly(s-'ploll plog (1) + B/A)).
in Definition
1.1 hold, and T 2 M[max ((3 ((/H/////// H*) (A*) "),""),H² (()
(log(dT//)(( /6) + 3/ A)) Σ Ei nnz(a (8.5)) S
As corollaries, we give results for heavy hitters for kernel classification in the supplementary.
5 Point Query Experiments
We compare Algorithms
D and
(where R is JL matrix for Algorithm 2 with the algorithm of [.]
Datasets: We use the following datasets (which were also used [): RCVI 13, KDD Cup 2010 Algebra 27
(we a transformed version due to (28), and the malicious URL dataset of [29].
Parameters: We perform online logistic regression À E (10-3, 10-4, 10-5). Each algorithm subject to memory constraint M E {2 KB 4 4KB, 8 KB, 16 KB, 32 KB). For Algorithm 2
and the algorithm of [[] the dimensions of the JL/Countsketch matrices for a particular memory constraint are given by the corresponding row in Table 1 of ( (noted in M to be the best performing configurations for Countsketch). For Algorithm|] I which uses a JL matrix and a separate Countsketch matrix, also use the same configuration for both matrices, but with the width divided by 2.
We compare the algorithms in terms of how well they recover the top weights of w.. We use similar relative error metric to that used in Subsection 7.2 of []] To estimate how well one of the three algorithms recovers the top K weights, we let w be the K-sparse vector whose entries are the K largest estimated coordinates obtained by this algorithm. We let with be the m-sparse vector whose entries are the m largest coordinates of w., for any m. Then, we use wPl), 12 in M (that is, I|w - w. 22/ I| w. w+1l2)= - we use _ instead since this omits the smaller weights and might therefore better measure how well the algorithms recover the larger weights. We also note that in place w., we use the weight vector that is obtained by online logistic regression for these experiments this was also done by [I] in their experiments.
Error Metric:
w|w - -w:"l ww.'ll//|lu
metric, where D 512 > K. This is similar to the metric used
Here we show a few plots on the RCVI dataset Figure 5 with = 10-5 all plots are in the supplementary. With memory budget of 16 KB, when K = 120, Algorithm gives an improvement of roughly 15% over the algorithm of [ which in turn performs better than Algorithm I With memory budgets of 2 KB and KB, Algorithm I has the best performance.
Results:

---

Algorithm 3 Algorithm for & heavy hitters (i.e., without classification) where the input is R which is updated according to v 4- V + 2, where I æ1 @ @ Tp. For ease of presentation, we do not distinguish between a sketch 5 IR + TR (i.e., S E R Rxxa) and its contents Sv E IR (for v E R²). We make use of standard f2 heavy hitters data structure ONEMODESKETCH
whose
size has logarithmic dependence 1 while such a dependence is not stated by [25] (which achieves the optimal space complexity for &g heavy hitters), we use the dyadic trick, which still has sublinear time and space complexity see Theorem of [26].
Require: E E 1) Ensure: Return a list c. [d]" with |1| S O(1/=²) containing all E [d] such that loy E||0/|22
function INTTIALIZ.ATION)))
For each i E [p). COMPRESSOTIIERMOISS" Rd - peodypplog(//0)) is the sketch of
with O(1).
For each i [p). ONEMODESKETCH Reppoy(ppoog(d10) Ruoly(logtd/0))/s) is a usual
2 heavy hitter data structure (such that of (25) with accuracy s' poly(p logd/))
For each E [p- 1]. COMPRESSSUFFIX (1) RddP (pplb(plogdd/6))) is the sketch of with i in place of and = O(1).
[d (oly(plog(d/8)) p log (d/6)/e) is the sketch [1] with the first input modes being d-dimensional and the last mode being poly(plog(d//)) dimensional, with accuracy e' boly(poo(//88)) PREFIXPOINTQUERY"
For each i [p 1]. PREFIXPOINTQUERY
from Rdd Rpoly (pgg((/)))) simply the sketch of
end function
// Here allow to be lank-1 tensor without loss of generality. The case where is rank-k tensor is the same, except the update time increases by a factor of function UPDATE(2: T1
xpp)
For each
[p), update ONEMODESKETCH (5) by
@ COMPRESSOTHERRMODES (x1 @ 1 & 2i+1 .... xp)
Update PREFIXPOINTQUERY' by 2, For E update PREHXPOINTQUERY by
21 2 ... COMPRESSSUFAIX(EL. 8 .....0 xp)
function QUBRY()
[d] x [poly(plog(d/d) from For each i E [p], find all (ol((1log(//8)) heavy hitters (j, k)
ONEMODESKETCH
Collect a list L, of length at most poly(e-1p pogg(d/))) of coordinates j E [d] such that (i, k) was returned by ONEMODESKETCH in the previous step, for some
k E (plly(p log(d/o))) Note that L, contains all coordinates in the 7th mode potentially comprising an fraction of [|.., ||2-
L. < L1 // initial list of prefixes of heavy hitters
I. - top O(1/e²) elements of I, according to Jasee point query
PREFXXOINTQUERYY!!
for
i 2 2...., do
-L'+Lx L, = ((.i. Ji- 1),3) (f1....,ji-1) E L,j E L.). - L + top 0(1/=²) elements of L' according to JL-based point query on
PREFIXPOINTQUERY")
end for Return L end function
10

---

Acknowledgments and Disclosure of Funding
D. Woodruff was supported by NSF CCF-1815840, Office of Naval Research grant N00014-18-1-
2562, and Simons Investigator Award.
References
[1] Kai Sheng Tai, Vatsal Sharan, Peter Bailis, and Gregory Valiant. Sketching linear classifiers over data streams, In Gautam Das, Christopher M. Jermaine, and Philip A. Bernstein, edi- tors, Proceedings of the 2018 International Conference on Management Data, SIGMOD Conference 2018, Houston, TX, USA, June 10-15, 2018, pages 757-772. ACM, 2018.
[2] Ciprian Chelba, Tomás Mikolov, Mike Schuster, Qi Ge, Thorsten Brants, and Phillipp Koehn. One billion word benchmark for measuring progress in statistical language modeling. CoRR, abs/ 1 131.3033 2013.
[3] Moses Charikar, Kevin C. Chen, and Martin Farach-Colton. Finding frequent items in data streams, Theor. Comput. Sci., 312(():3-15, 2004.
[4] Daniel M. Kane and Jelani Nelson. Sparser jorisoo-lindeesttrauae transforms. J. ACM, 61(1):411- 4:23, 2014.
[5] Omri Ben-Eliezer, Rajesh Jayaram, David P. Woodruff, and Eylon Yogev. A framework for adversarially robust streaming algorithms. SIGMOD Rec., 50(1);6-13, 2021.
[6] Jelani Nelson, Huy L. Nguyên, and David P. Woodruff. On deterministic sketching and streaming for sparse recovery and estimation. In Anupam Gupta, Klaus Jansen, José D. P. Rolim, and Rocco A. Servedio, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithmss and Techniques 15th International Workshop, APPROX 2012, and 16th International Workshop. RANDOM 2012, Cambridge, MA. USA, August 15-17, 2012. Proceedings, volume 7408 of Lecture Notes in Computer Science, pages 627-638. Springer, 2012.
[7] Justin Hsu, Sanjeev Khanna, and Aaron Roth. Distributed private heavy hitters. In Artur Czumaj. Kurt Mehlhorn, Andrew M. Pitts, and Roger Wattenhofer, editors, Automata, Languages, and Programming 39thh International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part I, volume 7391 of Lecture Notes in Computer Science, pages 461-472. Springer, 2012.
[8] Ohad Shamir. Without- sethout-replacement sampling for stochastic gradient methods: Convergence results and application distributed optimization. CoRR, abs/1603.00570, 2016.
[9] Hua Zhou, Lexin Li, and Hongtu Zhu. Tensor regression with applications in neuroimaging data analysis. Journal of the American Statistical Association, 108(502) 552, 2013. PMID: 24791032.
[10] Brian S. Caffo, Ciprian M. Crainiceanu, Guillermo Verduzco, Suresh Joel, Stewart Mostofsky, Susan Spear Bassett, and James J. Pekar. Two-stage decompositions for the analysis of functional connectivity for fmri with application to alzheimer's disease risk. Neurolmage, 51(3):1140 1149, 2010.
[11] Thomas Ahle, Michael Kapralov, Jakob BT Knudsen, Rasmus Pagh, Ameya Velingker, David P Woodruff, and Amir Zandieh. Oblivious sketching of high-degree polynomial kemnlss. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 141-160. SIAM, 2020.
[12] Zhu and Trevor Hastie. Kernel logistic regression and the import vector machine. Journal of Computational and Graphical Statistics, 14(1):185-205 2005.
[13] David Lewis, Yiming Yang, Tony G. Rose, and Fan Li. RCV1: A new benchmark collection for text categorization research. J. Mach. Learn. Res., 5:361-397, 2004.
11

---

[14] Akshay Kamath, Eric Price, and David P. Woodruff. A simple proof of a new set disjointness with applications to data streams. In Valentine Kabanets, editor, 36th Computational Complexity Conference, CCC 1, July 20-23, 2021, Toronto, Ontario, Canada Viriual Conference), volume 200 of L.Plcss pages 37:1-37:24. Schloss Dagstuhl- Leibniz-Zentrum für Informatik, 2021.
[15] David P Woodruff. New algorithms for heavy hitters in data streams. arXiv preprint 1003v:1603.01733, 2016.
[16] Vladimir Braverman, Stephen R Chestnut, Nikita Ivkin, and David P Woodruff. Beating countsketch for heavy hitters in insertion streams. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 740-753, 2016.
[17] Vladimir Braverman, Stephen R Chestnut, Nikita Ivkin, Jelani Nelson, Zhengyu Wang, and David P Woodruff. Bptree: an & heavy hitters algorithm using constant memory. In Proceedings of the 36th ACM JJGMOD-SIGACT-SIE pages 361-376, 2017.
Symposium on Principles of Database Systems,
[18] Sumit Ganguly and Anirban Majumder. Cr-precis: A deterministic summary structure for update data streams. In IntErnational Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies, pages 48-59. Springer, 2007.
[19]
Shanmugavelayutham Muthukrishnan. Data streams: Algorithms and applications. Now Publishers Inc, 2005.
[20] Amirali Aghazadeh, Ryan Spring, Daniel LeJeune, Gautam Dasarathy, Anshumali Shrivastava, and Richard G. Baraniuk. MISSION: ultra lcrge-scale feature selection using count-sketches. In Jennifer G. Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmmsssun Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pages 80-88. PMLR, 2018.
[21] Amirali Aghazadeh, Vipul Gupta, Alex DeWeese, O. Ozan Koyluoglu, and Kannan Ramchan- dran. Bear: Sketching bfgs algorithm for ultra-high dimensional feature selection in sublinear memory, 2020.
[22] Elad Hazan. Introduction to online convex optimization. CoRR, abs/1909.05207, 2019
[23] Anna C. Gilbert and Piotr Indyk. Sparse recovery using sparse matrices. Proc. IEEE, 98(6):937~ 947, 2010.
[24] Hossein Jowhari, Mert Saglam, and Gábor Tardos. Tight bounds for ip samplers, finding duplicates in streams, and related problems. Maurizio Lenzerini and Thomas Schwentick, editors, Proceedings of the 30th ACM SIGMOD- --S-AI--AIGGGART Symposium Principles of Database Systems, PODS 2011, June 12-16, 2011, Athens, Greece, pages 49-58. ACM, 2011.
[25] Kasper Green Larsen, Jelani Nelson, Huy L. Nguyen, and Mikkel Thorup. Heavy hitters via cluster-preserving clustering. In Irit Dinur, editor, IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyalt Regency, New Brunswick, New Jersey, USA, pages 61-70. IEBE Computer Society, 2016.
[26] Daniel M. Kane, Jelani Nelson, Fly Porat, and David P. Woodruff. Fast moment estimation in data streams in optimal space. In Lance Fortnow and Salil P. Vadhan, editors, Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011, pages 745-754. ACM, 2011.
[27] J. Stamper, A. Niculescu-Mizil, S. Ritter, G. Gordon, and K.R. Koedinger. Algebra 2008- 2009. challenge data set from kdd cup 2010 educational data mining challenge. Find it at http://pslcdatashop.ww wwtpt/sshoowp.......e..ee
[28] Hsiang-Fu Yu, Hung-Yo Yi Lo, Hsun-Ping Hsieh, Jing- Kai Lou, Todd G. McKenzie, Jung Wei Chou, Po-Han Chung. Chia-Hua Ho, Chun-Fu Chang, Yin- Wei, Jui- Yu Weng, En-Syu Yan, Che-Wei Chang, Tsung-Ting Kuo, Yi-Chen Lo, Po Tzu Chang, Chieh Po, Chien-Yure Wang, Yi-Hung Huang, Chen-Wei Hung, Yu-Xun Ruan, Yu-Shi Lin, Shou-De Lin, Hsuan-Tiee Lin, and Chih-Jen Lin. Feature engineering and classifier ensemble for kdd cup 2010. In JMLR Workshop and Conference Proceedings, 2011. To appear.
12

---

[29] Justin Ma, Lawrence K. Saul, Stefan Savage, and Geoffrey M. Voelker. Identifying suspicious urls: an application of large-scale online learning. Andrea Pohoreckyj Danyluk, Léon Bottou, and Michael I.. Littman, editors, Proceedings of the 26th Annual International Conference on Machine Learning, ICMI. 2009, Montreal, Quebec, Canada, June 14-18, 2009, volume 382 of ACM International Conference Proceeding Series, pages 68 6-88... ACM, 2009.
[30] Kilian Q. Weinberger, Anirban Dasgupta, John Langford, Alexander J. Smola, and Josh At- tenberg. Feature hashing for large scale multitask learning. In Andrea Pohoreckyj Danyluk, Léon Bottou, and Michael L. Littman, editors, Proceedings of the 26th Annual International Conference on Machine Learning. JCML 2009, Montreal, Quebec, Canada, June 14-18, 2009, volume 382 of ACM International Conference Proceeding Series, pages 1113-1120 ACM, 2009.
[31] Qinfeng Shi, James Petterson, Gideon Dror, John Langford, Alex Smola, Alex Strehl, and S. N. Vishwanathan. Hash kernels. In David van Dyk and Max Welling, editors, Proceedings of the Twelth International Conference on Artificial Intelligence and Statistics, volume 5 of Proceedings of Machine Learning Research, pages 496-503, Hilton Clearwater Beach Resort, Clearwater Beach, Florida USA, 16-18 Apr 2009. PMLR.
[32] Lior Kamma, Casper Benjamin Freksen, and Kasper Green Larsen. Fully understanding the hashing trick. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett, editors, Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS
2018, December 3-8, 2018, Montréal, Canada, pages 5394-5404, 2018.
[33] Ryan Spring, Anastasios Kyrillidis, Vijai Mohan, and Anshumali Shrivastava. Compressing gradient optimizers via count-sketches. Kamalika Chaudhuri and Ruslan Salakhutdinov. editors, Proceedings of the 36th International Conference on Machine Learning. volume 97 of Proceedings of Machine Learning Research, pages
PMLR, 09-15 Jun 2019.
[34] Robert Calderbank, Sina Jafarpour, and Robert Schapire. Compressed learning: Universal sparse dimensionality reduction and learning in the measurement domain. Technical report, 2009.
[35] Alexander Munteanu, Simon Omlor, and David P. Woodruff. Oblivious sketching for logistic regression. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 7861-76617777777 38711 PM 2021.
[36] Sébastien Bubeck. Convex optimization: Algorithms and complexity. Found. Trends Mach. Learn., 8(3-4):231-357, 2015.
[37] D. Sivakumar. Algorithmic derandomization via complexity theory. In Proceedings of the Thiry-Fourde Annual ACM Symposium on Theory of Computing, STOC page 619-626, New York, NY, USA, 2002. Association for Computing Machinery.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments...
13

---

(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] We included the code in the supplemental material. Instructions for downloading the datasets we used and reproducing the results are in the README files.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See the paragraph titled "Parameters" in Section 5 of the main paper.
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [No]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] Our code for our experiments is largely based that of [. mentioned in the footnote the bottom of page 4. We cite the datasets we used at the beginning of Section 5.
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material or URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "Y0xK890YSj4", "reviewer": "Reviewer_6Mw1", "summary": "The focus of this paper is one linear and kernel classification in a streaming setting with limited working memory. I will focus on linear classification in this summary. Given a loss function l and a set of training samples {(x_t,y_t)}_{t=1}^T, the goal is to find the vector w minimizing $(1/T) \\sum_{t=1}^T l(y_t w^T x_t) + \\lambda\\|w\\|_2^2$. The twist is that this must be done using sublinear memory. Here sublinear is also in d - the number of features. Thus the optimal vector w cannot even be stored in memory.\n\nWhat one does instead is to use techniques from streaming algorithms to extract the large coordinates of w, hoping that most of w is captured in a few coordinates of large magnitude. Formally, the setup is that training data arrives in a streaming fashion, with each item in the stream representing a coordinate of an x_t along with y_t. So we only see one single coordinate at a time.\n\nIn a standard streaming setting, one can use classic sketches such as the CountSketch to compute a small-memory representation of a given vector w, while allowing finding the heavy hitters (coordinates of magnitude at least $\\varepsilon \\|w\\|_2$) efficiently. The tricky part in the problem considered in this paper, is to simultanously find the small coordinates AND figure out what the optimal solution w is.\n\nA standard solution to linear classification with various loss functions, is to use online gradient descent. This however requires maintaining the current vector of parameters w. This is too expensive here, and the main idea in the work is to sketch w using one of the classic sketches for turnstile streaming heavy hitters / point queries. One can then \"simulate\" gradient descent via a gradient descent on the parameters in the sketch.\n\nThe results are also extended to tensor and kernel regression.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "To summarize my impression of the paper, I find that the most questionable part is the motivation for studying this problem. How often do you really have so many features that you do not have sufficient memory to store them? And more importantly, when you do, how often are the coordinates of the optimal solution w collected on a few coordinates of very large magnitude? In particular this last point is not even discussed in the paper. If there are no eps-heavy hitters in w, then the heavy-hitters guarantees are meaningless. The paper also does not include experiments that show whether this happens on some real-life data sets. Instead the experiments only focus on the ratio between the quality of the solution found by the new algorithm and the solution found by a previous algorithm. Which I agree is an important experiment. But another very interesting value to know would be the ratio $\\|w^K - w*\\|_2/\\|w*\\|_2$ on practical data sets. It is not clear at all whether this number is close to 1 or to 0. If it is very close to 1, then the heavy hitters seems a bit meaningless.\n\nThe above being said, I think the solution is a clean combination of known techniques from turnstile streaming. It elegantly uses linearity of the turnstile streaming sketches and combines it nicely with gradient descent. The writing of the paper is pretty dense and there are also some places where notation is not introduced (like in the main algorithm, there is an A_t which is never defined, and one has to guess that QUERY(A_T) inside QUERY is a call to a sketch's query algorithm). There are also a number of polynomial dependencies on H lambda eps tau that are pretty nasty from a practical point of view.\n\nAll in all, the paper combines standard techniques from streaming to solve a low-space version of a fundamental problem. I'm not completely convinced of the importance of the problem, and the one experiment shown in the paper is not super-convincing. I thus find that the paper fall a bit short of the bar for NeurIPS.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "VEG9yB7hRa-", "reviewer": "Reviewer_pGAj", "summary": "The current work deals with linear classification in the streaming, limited space model. The assumption is that the available space is both o(n) and o(d), where n = #data points and d = dimension. The goal is to be able to answer two different types of queries about the weight vector-- either to return a vector that is close to the original weight vector in l2 norm, or to return estimates of any coordinate of the weight vector. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "\n\nPrevious work has dealt with returning the weight vector estimate where the error is bounded by the L1 norm. The broad structure of the current algorithm is similar -- using a sketch (namely CountSketch) matrix to maintain an estimate of the weight vector, which is updated with the arrival of each point, and then to apply an (existing) recovery procedure in the CountSketch matrix. \nThere are other results that show that SGD and L-BFGS can be run on sketched data-- while the authors do comment on MISSION, the differences are not entirely clear to me yet. The updates are different, using online gradient descent updates rather than SGD updates, and that reflects in the guarantees, but that does not seem to be the core novelty of the paper. \n\n\nThe main novelty in this work, which allows for the new bounds, is to separate out the two matrices used for sketching -- one is used for storing the weight vector and the other to create a sketch for the incoming points. It is interesting that this simple change (plus its analysis) enables better guarantees. Beyond this observation, most of the techniques are reused from existing work. \n\nThe experiments are too brief. The error metric is not exactly the one on which the bound has been proven -- that would be | w-hat_T - w*|_2. However, the authors use a metric that has been used before. Point queries are not empirically evaluated. \n\nThere are a number of LateX issues that need to be addressed. \n------------\nPost rebuttal: Thanks for the answers to the questions. I have upgraded my score. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No negative societal impact. \n\nLimitations are discussed above.\n", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "NEeFGpRtYU9", "reviewer": "Reviewer_PPCJ", "summary": "The submission is a follow up paper on prior works on performing online gradient descent in sketch space.   The premise here is that the dimension d is very large and therefore we do not want to maintain the parameters vector w* explicitly.   We may only want to know the heavy hitter entries of the vector or to be able to query for values at particular indices (with error of the order of a fraction of the norm).  The approach is to use sketches to \"update\" w*.\n\nThe submission improves over prior work using a “plug and play” approach of taking known results and methods from the streaming literature and applying them in the online gradient descent context. ", "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": "Strength: Natural problem that  was already highlighted in prior work and the submission improves over the results. \n\nWeaknesses:\nThe paper presentation is not easily accessible to people not familiar with the particular prior streaming literature. \n\nThe solution is essentially a simply plug and play taking prior tools from streaming, adopted to the online gradient descent framework and the parameters vectors w*.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "I did not identify ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "7adx62FFOs", "reviewer": "Reviewer_LYkE", "summary": "This paper tackles a very basic problem in machine learning, linear (and polynomial, and kernel) classification in the streaming model.  Such learned models can be represented as a coefficients vector w.  The task studied in this paper is to approximately identify the largest coefficients in the optimal coefficient vector w.  \n\nThis model was introduced in a SIGMOD 2018 paper.  This paper:\n - improves bounds under the l_1 model, including a deterministic option\n - provides new poly(dimension) bounds in the l_2 model\n - removes assumption that data is random ordered, it allows adversarial order\n - extends to polynomial and kernel SVM classifiers", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "If one accepts the model as important, these are sizable improvements.  They are achieved by layering many recent techniques on this setting.  The ideas do not appear entirely new (from a techniques point of view), but the application of them is nonetheless non-trivial and varied.  \n\nHowever, I am not enthusiastic about the model.  It perpetuates the fallacy that high-weight coefficients are the most important elements of a model.  This may not be true if variables are not properly normalized (if that is even possible).  For instance, the even more involved Shapley values are not necessarily as powerful as often claimed (https://arxiv.org/abs/2002.11097).  \nFor instance, the paper does not make any claims about how well the compressed model approximates the loss function or generalizes to new data under any assumptions.  \n\nHence, while I like the technical improvements provided in this work, I am skeptical of the overall premise.  ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "As this is a theory paper, the authors do not really engage with this aspect.  It mostly removes limitations from prior work.  \n\nAs mentioned I am concerned with the focus on explainability by high weights -- but more a modeling issue than a serious societal one rooted in this paper.  ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers largely agreed that the paper provides a clear improvement over prior work on the problem of learning "heavy-hitter" weights. The reviewers initially debated the value of the problem studied by the authors, and were concerned it might be of limited interest. However, the author response did a good job of further justifying the setting studied. 
Decision: Accept (Poster)