Linear and Kernel Classification in the Streaming Model: Improved Bounds for Heavy Hitters
Year: 2022

Abstract:
We study linear and kernel classification in the streaming model. For linear classification, we improve upon the algorithm of [1], which solves the `1 point query problem on the optimal weight vector w∗ ∈ R in sublinear space. We first give an algorithm solving the more difficult `2 point query problem on w∗, also in sublinear space. We then give an algorithm which solves the related `2 heavy hitter problem on w∗, in sublinear space and running time. Finally, we give an algorithm which can deterministically solve the `1 point query problem on w∗, with sublinear space, improving upon that of [1]. For kernel classification, if w∗ ∈ R p is the optimal weight vector classifying points in the stream according to their p-degree polynomial kernel, then we give an algorithm solving the `2 point query problem on w∗ in poly( log d ε ) space, and an algorithm solving the `2 heavy hitter problem in poly( log d ε ) space and running time. Note that our space and running time is 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 = Θ(log T )). Our algorithms for kernels are in fact a special case of a more general algorithm we give for low-rank tensor inputs.

text: p
is the optimal weight vector classifying points in the stream according to their pth-degree polynomial kernel, then we give an algorithm solving the `2 point query problem on w∗ in poly(p log dε ) space, and an algorithm solving the `2 heavy hitter problem in poly(p log dε ) space and running time. Note that our space and running time is 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 = Θ(log T )). Our algorithms for kernels are in fact a special case of a more general algorithm we give for low-rank tensor inputs.

heading: 1 Introduction
text: We consider logistic regression, and more generally, linear classification, in the streaming model. In our setting, we are given a dataset consisting of T examples (xt, yt), where t ∈ [T ], xt ∈ Rd, yt ∈ {−1, 1}. The examples arrive one by one, and moreover, the nonzero coordinates of each example xt arrive one by one. Our goal is to estimate the weights w∗ ∈ Rd of the optimal linear classifier for these examples. Here, w∗ := argminw∈Rd 1 T ∑T t=1 `(ytw Txt) + λ 2 ‖w‖ 2 2 where ` is a loss function satisfying certain conditions described in Section 1.3 — the prototypical example of ` that we consider is the logistic regression loss function — and λ controls the strength of the `2 regularization. Finally, we assume that d is very large, and we therefore wish to 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 a network, as well as in machine learning problems with many features. Machine learning problems with a very large number of features arise in many natural language processing tasks, for example — one motivation for [1], the precursor to our work, is that the use of n-gram features when analyzing text data can lead to a very large memory cost. 1 Our goal, and that of [1], is to find features which are the most useful for classification — as pointed out in [1], previously known sketches for compressing classifiers do not achieve this goal.
Formally, we consider the following problems in this work:
1In [1] it is mentioned that in an experiment on the dataset of [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 (NeurIPS 2021).
Problem 1 (`p Point Query, for p = 1, 2). Let ε ∈ (0, 1). At any time t ∈ [T ] in the stream, given an arbitrary query i ∈ [d], the goal is to output ŵi such that |ŵi − w∗,i| ≤ ε‖w∗‖p. Problem 2 (`2 Heavy Hitters). Let ε ∈ (0, 1). At any time t ∈ [T ] in the stream, the goal is to output a list L ⊂ [d] of size at mostO( 1ε2 ) such that L contains all indices i ∈ [d] such that |w∗,i| ≥ ε‖w∗‖2.
Interpretability is one of the main motivations for the above problem formulations — as argued by [1], 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 `1 point query — to see why, note that in the worst case, ‖w∗‖1 can be larger than ‖w∗‖2 by a √ d factor. Thus, for instance, if an algorithm uses poly(ε−1 log d) space to solve `1 point query, then it will use at least dO(1) space to solve `2 point query (by replacing with / √ d), which is far too large in streaming settings.

heading: 1.1 Our Contributions
text: `2 point query and heavy hitters (via a reduction to turnstile `2 point query and heavy hitters) We give efficient algorithms for solving `2 point query and `2 heavy hitters. In the approach of [1], a single Countsketch matrix [3] is used to maintain a sketch zt of the weights. zt is updated by online gradient descent according to zt+1 ← (1−ληt)zt−ηtyt`′(ytzTt Rxt)Rxt, where R is a Countsketch matrix scaled by 1/ √ s, where s is the column sparsity of R — by [4], R is a Johnson-Lindenstrauss (JL) transform if s is chosen to be large enough. To estimate the coordinates of w∗, the recovery procedure of [3] is applied to √ sz, where z = ( ∑T t=1 zt)/T . In addition, [1] only obtains the `1 point query guarantee, since the JL property of R is only applied to show that R preserves the inner products between e1, e2, . . . , ed.
To resolve both of these issues, we decouple the JL matrix from the point query/heavy hitters sketch, i.e., we use a JL matrix R, and a separate sketch S for `2 point query/heavy hitters in the well-studied turnstile streaming model. First, we maintain zt, which is updated using online gradient descent as in [1]. In addition, we maintain an additional vector ŵt ∈ Rd, which is updated according to ŵt+1 ← (1− ληt)ŵt − ηtyt`′(ytzTt Rxt)xt. The motivation for this update is that it is essentially the online gradient descent update wt+1 ← (1 − ληt)wt − ηtyt`′(ytwTt xt)xt we would perform without any sketching, but we replace `′(ytwTt xt) with ` ′(ytz T t Rxt) due to space constraints. We do not have enough space to explicitly maintain ŵt, but since the updates to ŵt are additive, we can still give it as the input to a turnstile streaming algorithm for `2 point query/heavy hitters. We show that ŵT = 1T ∑T t=1 ŵt is close to w∗ in `2 norm, and thus it suffices to solve `2 point query and `2 heavy hitters on ŵT . In summary, we give algorithms for `2 point query and heavy hitters with O(ε−2 log(dT/δ)) space and 1− δ success probability. Deterministic `1 point query In addition, we show that `1 point query can be solved deterministically, and with space complexity O(ε−2 log(d)), which is smaller than the O(ε−4 log3(d/δ)) space complexity of [1]. 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 [5]. To obtain a deterministic algorithm, we replace the Countsketch matrix used by [1] with an ε-incoherent matrix. Here, an ε-incoherent matrix R ∈ Rs×d is one whose columns are almost orthonormal, meaning that for all i 6= j, |〈Ri, Rj〉| ≤ ε, and all columns of R have `2 norm 1. Matrices that are ε-incoherent were previously applied to streaming problems by [6], and can be constructed deterministically. To improve on the space complexity of [1], we change the recovery procedure: to estimate w∗,i, we simply compute 〈Ri, z〉 where z is the compressed weight vector, rather than applying the Countsketch recovery procedure of [3].
`2 point query (via a combined JL/point query sketch) Inspired by our deterministic `1 point query algorithm, we provide an alternative algorithm for `2 point query, for which the space complexity has a smaller dependence on 1/λ. 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 `2 point query sketch directly, using a different `2 point query recovery procedure. Our procedure does not involve any median based operations. Instead, to estimate w∗,i given the compressed weight vector z, we simply compute 〈Ri, z〉. Recall that [1] multiplies the sketching matrix R by √ s in order to perform the recovery procedure of [3] — our new procedure also avoids this rescaling, and thus achieves a space complexity of O(ε−2 log(dT/δ)) up to problem-dependent parameters. The space complexity of this algorithm has a smaller dependence on 1/λ compared to our `2 point query
algorithm discussed above. In addition, we use online gradient descent regret bounds to show that the estimation error of our algorithms involves a term that is proportional to 1
T 1/4 . Thus, for the error
to be at most ε‖w∗‖2 or ε‖w∗‖1, T must be at least a certain value. Our `2 point query algorithm using a combined JL/point query sketch requires T to grow as 1λ4 , as opposed to our `2 point query algorithm which makes a black-box reduction to the turnstile model, which requires T to grow as 1λ8 .
The main idea of this algorithm is the observation that if w∗ is the optimal weight vector, then 〈Rw∗, Rei〉 is a good estimate of 〈w∗, ei〉 = w∗,i — this motivates our query procedure. Note that this fact is implicit in the guarantees of a JL matrix. This recovery procedure has also been used for turnstile `1 point query by [6] (which motivated our deterministic `1 point query algorithm above). The same recovery procedure was also used by [7], 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 `2 point query for linear classification. Note that for `2 point query in the turnstile model, it is preferable to use Countsketch (Countsketch is also used by [1]), since for an update to a single coordinate, the update time with Countsketch is O(log(1/δ)), while the update time when using a sparse JL matrix [4] is O(ε−1 log(1/δ)). However, in the context of linear classification, we find that using a JL matrix with the recovery procedure 〈Rw∗, Rei〉 ≈ w∗,i reduces the space complexity by a factor of poly(ε−1 log(d/δ)), as long as T = O(d). This is because the sketching matrix already needs to be a JL matrix in order to preserve certain inner products. In this case, using the Countsketch recovery procedure requires scaling z by a factor of √ s where s is the column sparsity of R, which in turn requires increasing the accuracy parameter ε of R in order to solve `2 point query (or `1 point query).
Worst-case data order guarantees For all of our algorithms, we do not make assumptions on the order of the xt, unlike [1]. In [1] the pairs in the set {(x1, y1), . . . , (xT , yT )} are required to arrive in the stream in a uniformly random order. The following is given in [1] 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 a 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 1 of [8] (which is used by [1]) we can use an argument from first principles based on online gradient descent regret bounds.
Classification with tensor inputs We consider a variant of linear classification where the inputs xt and the weight vector w∗ are p-th order tensors (i.e., are vectors in Rd p
) and moreover, the xt have rank at most k, meaning xt = ∑k i=1 x (i,1) t ⊗ x (i,2) t ⊗ . . .⊗ x (i,p) t , where the x (i,j) t ∈ Rd. This is motivated by applications of tensor regression, for instance in neuroimaging [9, 10], where the covariates have a tensor product structure. Furthermore, the xt may be of low rank in applications — for instance, in the case p = 2, [9] mentions that in [10], tensor regression is performed after principal component analysis is first performed on the xt. In such a setting, we wish to obtain `2 point query and heavy hitters algorithms with at most a polynomial dependence on log d and 1/ε, and moreover a polynomial dependence on p. To achieve this, we use tensor sketching techniques of [11], which develops a sketching matrix M ∈ Rm×dp , where m = poly(ε−1p log d), such that M is a JL matrix, and Mx⊗p can be computed very efficiently for x ∈ Rd (specifically, in poly(ε−1p log d) · nnz(x) time), without explicitly forming x⊗p. Thus, for `2 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 `2 heavy hitters, our algorithm is as follows: (1) for each mode i ∈ [p], we determine the coordinates j ∈ [d] which contribute more than an ε fraction of the `2 norm of w∗ — in other words, we want to find all j ∈ [d] such that ‖w∗(:, . . . , :, j, :, . . . , :)‖2 ≥ ε‖w∗‖2, where w∗(:, . . . , :, j, : , . . . , :) consists of those coordinates of w∗ which have index j in the ith mode. This gives us a list Li ⊂ [d] of size at most O(1/ε2), for each i ∈ [p]. (2) Then, we find the (at most O(1/ε2)) indices (i1, . . . , ip) of w∗ in [d]p such that |w∗(i1, i2, . . . , ip)| ≥ ε‖w∗‖2. We do step (2) using the Li, by inductively constructing prefixes of these coordinates, one mode at a time. For each i ∈ [p], we build an auxiliary data structure which can estimate ‖w(j1, . . . , ji, :, . . . , :)‖2 for any prefix (j1, . . . , ji) of length i — this is also done by using the sketching matrix of [11]. Both our `2 point query and `2 heavy hitters algorithms for pth-order tensor inputs have poly(ε−1p log(dT/δ)) space and query time, and poly(ε−1p log(dT/δ)) ∑ nnz(x(i,j)t ) update time, up to problem-dependent parameters.
When the inputs are pth order tensors of low rank, our `2 point query and heavy hitters algorithms for tensor inputs give significant savings in update time when compared to standard `2 point query/heavy hitters algorithms. To see why, note that when the xt are rank-k tensors, the update to ŵt (defined above) is ŵt+1 ← (1 − ληt)ŵt − ηtyt`′(ytzTt Mxt) ∑k i=1 x (i,1) t ⊗ x (i,2) t ⊗ . . . ⊗ x (i,p) t . Using a standard `2 heavy hitters algorithm on ŵt requires explicitly forming x (i,1) t ⊗ x (i,2) t ⊗ . . .⊗ x (i,p) t — if the x(i,j)t are dense, then standard `2 heavy hitters algorithms would require at least d p update time, as opposed to our algorithm, which only has poly(ε−1p log(dT/δ)) · kd update time — even when p = 2, if k is small, then this is a significant improvement.
Kernel classification Kernel logistic regression (KLR) is a well-known classification method in the field of statistical learning, see e.g., [12] 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 x⊗pt to predict yt — thus, this is a special case of the setting where xt is a tensor of rank at most k, discussed above. As in [11], we can approximate the Gaussian kernel via a Taylor expansion, using a polynomial kernel of degree O(log T ). Note that if (i1, i2, . . . , ip) is an index in [d]p and (j1, j2, . . . , jp) is a re-ordering of (i1, i2, . . . , ip), then one may want to consider xi1 . . . xip and xj1 . . . xjp to be the same feature. To get around this, suppose (i1, i2, . . . , ip) has a Hamming distance of at most c from the set of indices of the form (i, i, . . . , i) and it is an ε-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 ε/pc/2, (i1, i2, . . . , ip) will be detected as a heavy hitter. An interesting open question is whether this can be done in poly(ε−1p log(dT/δ)) space even when c is equal to p. We leave this question to future work.
Experiments We empirically compare both of our algorithms for `2 point query with the WM-Sketch algorithm of [1], 2 where all three algorithms are restricted to certain memory budgets, following the setup of [1]. Our `2 point query algorithm that makes use of a combined JL/point query sketch leads to improved performance in estimating w∗ compared to the WM-Sketch algorithm, with significantly improved performance for a larger memory budget on the RCV1 dataset [13], though the WM-Sketch algorithm performed better than our black-box reduction-based `2 point query algorithm. For smaller memory budgets, these two algorithms appeared to have similar weight recovery performance on the RCV1 dataset, but our other `2 point query algorithm using a black-box reduction to turnstile `2 point query had much lower error in recovering the top weights.
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 RCV1 dataset [13], which we divided into a training and testing half — we obtained a weight vector w ∈ Rd by using online logistic regression on the training half, and computed the accuracy when using wK for linear classification on the testing half (where wK is the 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 93.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 zTR instead of w∗ where R is a sparse JL matrix and z is the average iterate of sketched online logistic regression: if L = 1T ∑T t=1 `(ytw T ∗ xt) and L̂ = 1 T ∑T t=1 `(ytz
TRxt), then |L∗ − L̂| ≤ ε‖w∗‖2 as long as R has O(ε−2H2 log(dT/δ)) rows (up to problem dependent parameters) and T is a certain value. We give full details in Appendix E. Finally, we note that in a stream, finding `2 heavy hitters in the turnstile model requires min( √ d/ε, log(1/δ)/ε2) 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.
2We use the implementation by the authors of [1] at https://github.com/stanford-futuredata/ wmsketch. Our implementations of our `2 point query algorithms are also based on their code.

heading: 1.2 Related work
text: 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., [15]. Of particular relevance to this work is the CountSketch algorithm of [3] for finding `2 heavy hitters. We note that [16, 17] improve the memory of the algorithm of [3] by a logarithmic factor, but do not handle negative updates, which may arise in our setting. We also need deterministic algorithms for finding `1 heavy hitters, and we use the algorithms of [6] which use -incoherent matrices, and improve upon the earlier work of Ganguly [18]. We note that the CountMin algorithm of [19] also achieves the `1 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 Classification/Regression The work that is most closely related to ours is [1], which solves `1 point query on w∗ in the streaming model, and achieves O(ε−4 log3(d/δ)) space up to problem-dependent parameters. Unlike [1], we give an algorithm with provable guarantees for finding the at most ε−2 heavy hitters in sublinear time, and we solve the stronger `2 point query and heavy hitters problems in addition to `1 point query.
Another related work with a somewhat different focus from ours is MISSION [20]. 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 to a Countsketch data structure — then, Countsketch is used to select the 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 βt to a k-sparse vector β∗, while in the analyses of our `2 point query/heavy hitters algorithms, we desire/show convergence in `2 norm of ŵT to w∗ up to additive error ε‖w∗‖2 for a potentially dense w∗. Our gradient updates are thus different, as we perform the update ŵt+1 ← (1− ληt)ŵt − ηt`′(ytzTt Rxt)xt, i.e. our update does not involve truncation by taking the top k estimates from Countsketch. We also note that [20] gives a theoretical analysis in the setting where the xt have i.i.d. Gaussian entries, and yt = xTt β
∗ + w, where w is Gaussian noise and β∗ is a k-sparse vector, while we do not assume the inputs/noise are Gaussian.
One more work [21] proposes the BEAR algorithm, which is a sketched version of the online L-BFGS algorithm. The setting of [21] is similar to ours — this work aims to estimate the top coordinates of the weight vector and achieve the `2 point query guarantee. The proof of Lemma 3 in [21], 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 to 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 `2 heavy hitters algorithms with a small overhead in space/update time and no overhead in query time — fast query time can be useful when the xt, 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.

heading: 1.3 Preliminaries
text: As in [1], we are given a loss function `, training examples {(xt, yt)}t∈[T ], λ > 0, and w∗ := argminw∈Rd 1 T ∑T t=1 `(ytw Txt) + λ 2 ‖w‖ 2 2. We use online gradient descent regret bounds, specifi-
cally Theorem 3.1 of [22]. We use a learning rate of ηt = D/(G √ t), where D is an upper bound on ‖w∗‖2 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) ` is convex, β-smooth, and H-Lipschitz. (2) For all t ∈ [T ], ‖xt‖2 ≤ 1. (3) There exists a constant τ > 0 independent of T such that ‖w∗‖2 ≥ τ .
The last assumption above is not explicitly made in [1], but in Theorem 2 of [1], one of the hypotheses is that T is at least 1/‖w∗‖21 (omitting other dependencies). Since w∗ itself may depend on
x1, x2, . . . , xT , and thus T , we explicitly make this assumption to prevent circularity. This assumption is necessary for making use of online gradient descent regret bounds, to ensure ‖w∗‖2 does not decrease faster than the average regret.

heading: 2 `2 Point Query and Heavy Hitters
text: First, we define a “sketched” loss function L̂(z) = 1T ∑T t=1 `(ytz TRxt) + λ 2 ‖z‖ 2 2 as in [1]. Here, R is a sparse Johnson-Lindenstrauss matrix — let us recall the properties of sparse JL matrices:
Theorem 2.1 (Sparse JL Matrices [4]). Let d ∈ N, and ε, δ ∈ (0, 1). Then, there exists a distribution on matrices S ∈ Rk×d, where k = Θ(ε−2 log(1/δ)) and S has s = Θ(ε−1 log(1/δ)) nonzero entries per column, such that for any x ∈ Rd, with probability 1− δ, (1− ε)‖x‖2 ≤ ‖Sx‖2 ≤ (1 + ε)‖x‖2.
If z∗ := argmin L̂(z), then z∗ is a compressed version of w∗ in the following sense:
Theorem 2.2 (Batch Setting). Let ε, δ ∈ (0, 1), and suppose ` is β-smooth and ‖xt‖2 ≤ 1 for all t. Definew∗ = argminL(w) and z∗ = argmin L̂(z). IfR is a sparse JL matrix withO(ε−2 log(dT/δ)· β/λ) rows, then with probability 1− δ over R, ‖z∗ −Rw∗‖2 ≤ ε‖w∗‖2.
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 1 of [1]. The main difference is that [1] only shows that ‖z∗ −Rw∗‖2 ≤ ε‖w∗‖1. This is because they only apply the JL property of R to approximately preserve inner products between the vectors e1, e2, . . . , ed. To prove Theorem 2.2, we modify their analysis by also using the JL property of R to additionally show that the inner products 〈xt, w∗〉 and 〈ei, w∗〉 are well-approximated by 〈Rxt, Rw∗〉 and 〈Rei, Rw∗〉 respectively, for all i ∈ [d], and t ∈ [T ]. Our algorithm proceeds by a reduction to standard `2 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 a vector v ∈ Rn. Updates are of the form (i,∆) where i ∈ [n] and ∆ ∈ R, signifying that vi is incremented by ∆. For `2 point query in the turnstile model, queries i ∈ [d] should be answered with an estimate v̂i of vi such that |v̂i − vi| ≤ ε‖v‖2. For `2 heavy hitters in the turnstile model, queries should be answered with a list L of length O(1/ε2) containing all i ∈ [d] such that |vi| ≥ ε‖v‖2. Theorem 2.4 (Turnstile `2 Point Query [3], Theorem 2 of [23], Lemma 1 of [24]). There is an algorithm for turnstile `2 point query with space complexity O(ε−2 log(1/δ)), update time O(log(1/δ)) and query time O(log(1/δ)), and success probability 1− δ. Theorem 2.5 (Turnstile `2 Heavy Hitters [25]). There is an algorithm for turnstile `2 heavy hitters with O(ε−2 log n) space complexity, O(log n) update time and O(ε−2poly(log n)) query time, and success probability 1− 1/poly(n).
The key new idea of Algorithm 1 is that we implicitly maintain a vector ŵt ∈ Rd which is updated according to ŵt+1 ← (1 − ληt)ŵt − ηtyt`′(ytzTt Rxt)xt. Note that ŵt is an approximation to wt ∈ Rd which is obtained by the standard update wt+1 ← (1 − ληt) − ηtyt`′(ytwTt xt)xt. We cannot maintain ŵt explicitly, but we give it as input to the linear sketch which we refer to as A in Algorithm 1. 3 For `2 point query, A is a Countsketch matrix, and for `2 heavy hitters it is Expander Sketch [25]. In our QUERY procedure in Algorithm 1, we apply the query procedure of A to AŵT , where ŵT = 1T ∑T t=1 ŵt. This is justified since ŵT is a good approximation to w∗:
Theorem 2.6 (Approximating w∗ with ŵT ). Let ε, δ ∈ (0, 1). Suppose all of the assumptions in Definition 1.1 hold. Suppose R is a sparse JL matrix with O(λ−2ε−2β2 log(dT/δ) max(1, β/λ)) rows. If ŵt is updated according to ŵt+1 ← (1−ληt)ŵt−ηtyt`′(ytzTt Rxt)xt, and ŵt = 1T ∑T t=1 ŵt, then ‖ŵT − w∗‖2 ≤ ε‖w∗‖2 as long as T ≥ Ω(max((β4H4)/(λ8ε4τ4), H4/(λ4ε4τ4))). Theorem 2.7 (`2 Point Query and Heavy Hitters for Linear Classification). Suppose ε, δ ∈ (0, 1), all of the assumptions in Definition 1.1 hold, and T ≥ Ω(max((β4H4)/(λ8ε4τ4), H4/(λ4ε4τ4))).
3Here, A is a linear sketch meaning that, if Av is itself considered a vector, then Av is a linear map in terms of v. Thus, the update ŵt+1 ← (1− ληt)ŵt − ηtyt`′(ytzTt Rxt)xt can be implicitly done in sublinear space.
Algorithm 1 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 `2 point query or `2 heavy hitters. At denotes the contents of the sketch at time step t, and A denotes the sketch containing the average of the contents of A1, . . . ,AT . Since A is a linear sketch, A can be maintained using only a constant factor more space than that needed to store At. Here, QUERY denotes the query procedure of A, that is, the query procedure described in Theorem 2.4 for `2 point query and Theorem 2.5 for `2 heavy hitters. Note that we can skip the step used in [1] where zt+1 is projected onto an `2 unit ball, since even without projection, ‖zt+1‖2 ≤ O(H/λ) by the triangle inequality and induction.
function INITIALIZATION() R ∈ Rk×d is a sparse JL matrix with k = O(ε−2 log(dT/δ) ·max(1, β/λ)) rows. z1 ∈ Rk is set to 0 ∈ Rk. The contents of the sketch A are set to 0 ∈ Rd. end function
function UPDATE(xt, yt) zt+1 ← (1− ληt)zt − ηtyt`′(ytzTt Rxt)Rxt Rescale the contents of A by (1− ληt). For each nonzero coordinate i ∈ [d] of xt, update A according to
(i,−ηtyt`′(ytzTt Rxt)xt,i)
end function
function QUERY() A ← 1T ∑T t=1At
Return QUERY(A) end function
For `2 point query, Algorithm 1 has O(λ−2ε−2β2 log(dT/δ) max(1, β/λ) + ε−2 log(1/δ)) space complexity, O(λ−1ε−1β log(dT/δ) max(1, √ β/λ) + log(1/δ)) · nnz(xt) update time, O(log(1/δ)) query time, and success probability 1 − δ. For `2 heavy hitters, Algorithm 1 has O(λ−2ε−2β2 log(dT/δ) max(1, β/λ) + ε−2 log d) space complexity, O(λ−1ε−1β log(dT/δ) max(1, √ β/λ) + log d) · nnz(xt) update time, O(ε−2poly(log d)) query time, and success probability 1− 1/poly(d)− δ.
The proofs of Theorems 2.6 and 2.7 are given in the supplementary. Note that the query times are simply those of CountSketch [3] / ExpanderSketch [25] respectively.

heading: 3 Deterministic `1 Point Query and a Second Algorithm for `2 Point Query
text: We now give a simple deterministic algorithm for `1 point query with sublinear space. The algorithm is based on that of [1]. However, the sketching matrix R is now an ε-incoherent matrix:
Theorem 3.1 (ε-Incoherent Matrices [6]). Let n ∈ N and ε > 0. Then, there exists a matrix A ∈ Rm×n, where m = O(ε−2 min(log n, (log n/(log log n + log 1/ε))2)), such that for all i ∈ [n], ‖Ai‖2 = 1, and for all distinct i, j ∈ [n], 〈Ai, Aj〉 ≤ ε. Moreover, A can 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).
We first analyze the algorithm in the batch setting, showing that ‖RT z∗ − w∗‖∞ ≤ ε‖w∗‖1, 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 [1] (here we assume ‖xt‖1 ≤ γ as in [1]): Theorem 3.2 (Analysis of `1 Point Query on w∗ with Incoherent Matrix). Suppose all of the assumptions in Definition 1.1 hold, ‖xt‖1 ≤ γ for all t ∈ [T ], and there exists some constant θ > 0 independent of T such that ‖w∗‖1 ≥ θ. If R and z are defined as in Algorithm 2, with R being an incoherent matrix, then ‖RT z − w∗‖∞ ≤ ε‖w∗‖1, as long as T ≥ Ω(H4(1 + √ εγ)4/(λ4ε4θ4)).
Algorithm 2 Algorithm for `1 point query and `2 point query. For `1 point query, R is an incoherent matrix with O(ε−2 log d ·max(1, γ2β/λ)) rows, while for `2 point query, R is a sparse JL matrix with O(ε−2 log(dT/δ) max(1, β/λ)) rows.
1: function INITIALIZATION() 2: R ∈ Rk×d is defined as in the caption. 3: z1 ∈ Rk is initially set to 0. 4: end function
5: function UPDATE(xt, yt) 6: zt+1 ← (1− ληt)zt − ηtyt`′(ytzTt Rxt)Rxt 7: end function
8: function ESTIMATE-WEIGHTS(i) 9: zT ← 1T ∑T t=1 zt
10: return RTi zT 11: end function
If R is instead a sparse JL matrix with O(ε−2 log(dT/δ) max(1, β/λ)) rows, Algorithm 2 gives an `2 point query algorithm. Note that for `2 point query, the space complexity of Algorithm 2 has a better dependence on λ compared to Algorithm 1. Theorem 3.3 (`2 Point Query using only a JL Matrix). Let ε, δ ∈ (0, 1), and suppose all of the assumptions in Definition 1.1 hold. If R and z are defined as in Algorithm 2, with R being a sparse JL matrix, then ‖RT z − w∗‖∞ ≤ ε‖w∗‖2 with probability 1− δ, as long as T ≥ Ω(H4/(λ4ε4τ4)).

heading: 4 Low Rank Tensor Classification and Kernel Classification
text: We next consider `2 point query and heavy hitters in the case where xt ∈ Rd p 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 a JL matrix which can be quickly applied to outer products of vectors [11]: Theorem 4.1 (Recursive Tensor Sketch — Follows from the Proof of Theorem 2 of [11]). Let n, p, d ∈ N, ε, δ > 0. Then, there is a random matrix R ∈ Rm×dp , with m = Θ(ε−2p log(1/εδ)3), such that for x, y ∈ Rdp , PrM [|〈Rx,Ry〉 − 〈x, y〉| ≥ ε‖x‖2‖y‖2] ≤ 1− δ and for x1, x2, . . . , xp ∈ Rd, R(x1 ⊗ x2 ⊗ . . .⊗ xp) can be computed in poly(ε−1p log(1/δ)) ∑p i=1 nnz(xi) time. 4
This immediately gives us an algorithm for `2 point query, since in Algorithm 2, R can be replaced by any JL matrix. Note that the query procedure can be done in poly(p log(dT/δ)/ε) time (up to problem-dependent parameters), since for i = (i1, . . . , ip) ∈ [d]p, Ri = R(ei1 ⊗ . . .⊗ eip) can be computed in poly(p log(dT/δ)/ε) 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 ε, δ ∈ (0, 1) and suppose all of the assumptions in Definition 1.1 hold. Let R be the JL matrix of Theorem 4.1, with poly(ε−1p log(dT/δ)(1 + β/λ)) rows, and suppose T ≥ Ω(H4/(λ4ε4τ4). Then, with probability 1 − δ, ‖RT z − w∗‖∞ ≤ ε‖w∗‖2. Thus, there is an algorithm for `2 point query on w∗ with space complexity and query time poly(ε−1p log(dT/δ)(1 + β/λ)), and update time poly(ε−1p log(dT/δ)(1 + β/λ)) ∑k i=1 ∑p j=1 nnz(x (i,j) t ) ≤ kdpoly(ε−1p log(dT/δ)(1 + β/λ)).
Next we consider `2 heavy hitters on w∗ ∈ Rd p
. To simplify the problem, we reduce to the setting where we are given v ∈ Rdp and v is given updates of the form v ← v + x1 ⊗ . . .⊗ xp (where we are given x1, . . . , xp). This reduction is valid by Theorem 2.6, since updates to ŵt are of this form. Our algorithm for this setting is shown in Algorithm 3, with the following guarantees:
4R(x1 ⊗ x2 ⊗ . . . ⊗ xp) can be computed in one pass over the nonzero entries of x1, x2, . . . , xp: by the construction of [11], R is essentially a tree of sketching matrices, with 2p− 1 nodes. At the base of this tree are matrices R1, . . . , Rp, which can be separately applied to x1, . . . , xp respectively — from this point, only poly(ε−1p log(d/δ)) space is needed to finish the computation.
Theorem 4.3 (Tensor `2 Heavy Hitters Algorithm). Let ε, δ ∈ (0, 1). Let v ∈ Rd p
, which can be incrementally updated by a rank-1 tensor. Then, Algorithm 3 returns a list containing all (i1, i2, . . . , ip) ∈ [d]p such that |v(i1, . . . , ip)| ≥ ε‖v‖2. The space complexity is poly(ε−1p log(d/δ)), the query time is poly(ε−1p log(d/δ)), and the time needed for the update v ← v + x, for a rank-1 tensor x = x1 ⊗ . . .⊗ xp, is poly(ε−1p log(d/δ)) ∑p j=1 nnz(xj).
Theorem 4.3 implies that, by adapting Algorithm 1, but with R being the JL matrix of Theorem 4.1 instead of a sparse JL matrix, we can get an algorithm for heavy hitters in the linear classification setting, where the xt are rank-k tensors, and with space and time complexity polynomial in p:
Theorem 4.4 (Tensor Classification `2 Heavy Hitters). Let ε, δ ∈ (0, 1). Suppose all assumptions in Definition 1.1 hold, and T ≥ Ω(max((β4H4)/(λ8ε4τ4), H4/(λ4ε4τ4))). Then, there is an algorithm for `2 heavy hitters on w∗ with space complexity poly(ε−1p log(dT/δ)(1 + β/λ)), query time poly(ε−1p log(d/δ)), and update time poly(ε−1p log(dT/δ)(1 + β/λ)) ∑k i=1 ∑p j=1 nnz(x (i,j) t ) ≤ kd · poly(ε−1p log(dT/δ)(1 + β/λ)).
As corollaries, we give results for heavy hitters for kernel classification in the supplementary.

heading: 5 Point Query Experiments
text: We compare Algorithms 1 and 2 (where R is a JL matrix for Algorithm 2) with the algorithm of [1].
Datasets: We use the following datasets (which were also used in [1]): RCV1 [13], KDD Cup 2010 Algebra [27] (we use a transformed version due to [28]), and the malicious URL dataset of [29].
Parameters: We perform online logistic regression λ ∈ {10−3, 10−4, 10−5}. Each algorithm is subject to a memory constraint M ∈ {2KB, 4KB, 8KB, 16KB, 32KB}. For Algorithm 2 and the algorithm of [1], the dimensions of the JL/Countsketch matrices for a particular memory constraint are given by the corresponding row in Table 1 of [1] (noted in [1] to be the best performing configurations for Countsketch). For Algorithm 1, which uses a JL matrix and a separate Countsketch matrix, we also use the same configuration for both matrices, but with the width divided by 2.
Error Metric: We compare the algorithms in terms of how well they recover the top weights of w∗. We use a similar relative error metric to that used in Subsection 7.2 of [1]. To estimate how well one of the three algorithms recovers the top K weights, we let wK be the K-sparse vector whose entries are the K largest estimated coordinates obtained by this algorithm. We let wm∗ be the m-sparse vector whose entries are the m largest coordinates of w∗, for any m. Then, we use ‖wK −wD∗ ‖2/‖wK∗ −wD∗ ‖2 as our metric, where D = 512 K. This is similar to the metric used in [1] (that is, ‖wK −w∗‖2/‖wK∗ −w∗‖2) — we use wD∗ 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 of w∗, we use the weight vector that is obtained by online logistic regression for these experiments — this was also done by [1] in their experiments.
Results: Here we show a few plots on the RCV1 dataset in Figure 5, with λ = 10−5 — all plots are in the supplementary. With a memory budget of 16 KB, when K = 120, Algorithm 2 gives an improvement of roughly 15% over the algorithm of [1], which in turn performs better than Algorithm 1. With memory budgets of 2 KB and 4 KB, Algorithm 1 has the best performance.
Algorithm 3 Algorithm for `2 heavy hitters (i.e., without classification) where the input is v ∈ Rd p which is updated according to v ← v + x, where x = x1 ⊗ . . .⊗ xp. For ease of presentation, we do not distinguish between a sketch S : Ra → Rb (i.e., S ∈ Rb×a) and its contents Sv ∈ Rb (for v ∈ Ra). We make use of a standard `2 heavy hitters data structure ONEMODESKETCH(i), whose size has a logarithmic dependence on 1/δ — while such a dependence is not stated by [25] (which achieves the optimal space complexity for `2 heavy hitters), we use the dyadic trick, which still has sublinear time and space complexity — see Theorem 1 of [26]. Require: ε, δ ∈ (0, 1) Ensure: Return a list L ⊂ [d]p with |L| ≤ O(1/ε2) containing all i ∈ [d]p such that |vi| ≥ ε‖v‖2.
function INITIALIZATION() — For each i ∈ [p], COMPRESSOTHERMODES(i) : Rdp−1 → Rpoly(p log(d/δ)) is the sketch of [11], with ε = O(1). — For each i ∈ [p], ONEMODESKETCH(i) : Rd·poly(p log(d/δ)) → Rpoly(log(d/δ)/ε) is a usual `2 heavy hitter data structure (such as that of [25]) with accuracy ε′ = εpoly(p log(d/δ)) .
— For each i ∈ [p− 1], COMPRESSSUFFIX(i) : Rdp−i → Rpoly(p log(d/δ)) is the sketch of [11] with p− i in place of p and ε = O(1). — For each i ∈ [p− 1], PREFIXPOINTQUERY(i) : Rdi·poly(p log(d/δ)) → Rpoly(p log(d/δ)/ε) is the sketch of [11] with the first i input modes being d-dimensional and the last mode being poly(p log(d/δ)) dimensional, with accuracy ε′ = εpoly(p log(d/δ)) . PREFIXPOINTQUERY (p)
from Rdp to Rpoly(p log(d/δ)/ε) is simply the sketch of [11]. end function
// Here we allow x to be a rank-1 tensor without loss of generality. The case where x is a rank-k // tensor is the same, except the update time increases by a factor of k. function UPDATE(x = x1 ⊗ . . .⊗ xp)
— For each i ∈ [p], update ONEMODESKETCH(i) by
xi ⊗ COMPRESSOTHERMODES(i)(x1 ⊗ . . .⊗ xi−1 ⊗ xi+1 ⊗ . . .⊗ xp)
— Update PREFIXPOINTQUERY(p) by xt. For i ∈ [p− 1] update PREFIXPOINTQUERY(i) by
x1 ⊗ . . .⊗ xi ⊗ COMPRESSSUFFIX(xi+1 ⊗ . . .⊗ xp)
function QUERY() — For each i ∈ [p], find all εpoly(p log(d/δ)) -heavy hitters (j, k) ∈ [d]× [poly(p log(d/δ)] from ONEMODESKETCH(i). — Collect a list Li of length at most poly(ε−1p log(d/δ)), of coordinates j ∈ [d] such that (j, k) was returned by ONEMODESKETCH(i) in the previous step, for some k ∈ [poly(p log(d/δ))]. Note that Li contains all coordinates in the ith mode potentially comprising an ε fraction of ‖w∗‖2. — L← L1 // initial list of prefixes of heavy hitters — L← top O(1/ε2) elements of L according to JL-based point query on PREFIXPOINTQUERY(1). for i = 2, . . . , p do
— L′ ← L× Li = {((j1, j2, . . . , ji−1), j) | (j1, . . . , ji−1) ∈ L, j ∈ Li}. — L← top O(1/ε2) elements of L′ according to JL-based point query on PREFIXPOINTQUERY(i).
end for Return L end function
Acknowledgments and Disclosure of Funding
D. Woodruff was supported by NSF CCF-1815840, Office of Naval Research grant N00014-18-12562, and a Simons Investigator Award.

Review summaries:
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. 

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*.  The 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. 

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.    This model was introduced in a SIGMOD 2018 paper.  This paper:  - improves bounds under the l_1 model, including a deterministic option  - provides new poly(dimension) bounds in the l_2 model  - removes assumption that data is random ordered, it allows adversarial order  - extends to polynomial and kernel SVM classifiers

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.  What 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.  In 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.  A 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.  The results are also extended to tensor and kernel regression.