Almost Linear Constant-Factor Sketching for $\ell_1$ and Logistic Regression
Authors: Alexander Munteanu
Simon Omlor
David Woodruff
Venue: ICLR 2023 poster (2023)
Keywords: regression
sketching
data streams
logistic regression

Abstract: We improve upon previous oblivious sketching and turnstile streaming results for $\ell_1$ and logistic regression, giving a much smaller sketching dimension achieving $O(1)$-approximation and yielding an efficient optimization problem in the sketch space. Namely, we achieve for any constant $c>0$ a sketching dimension of $\tilde{O}(d^{1+c})$ for $\ell_1$ regression and $\tilde{O}(\mu d^{1+c})$ for logistic regression, where $\mu$ is a standard measure that captures the complexity of compressing the data. For $\ell_1$-regression our sketching dimension is near-linear and improves previous work which either required $\Omega(\log d)$-approximation with this sketching dimension, or required a larger $\operatorname{poly}(d)$ number of rows. Similarly, for logistic regression previous work had worse $\operatorname{poly}(\mu d)$ factors in its sketching dimension. We also give a tradeoff that yields a $1+\varepsilon$ approximation in input sparsity time by increasing the total size to $(d\log(n)/\varepsilon)^{O(1/\varepsilon)}$ for $\ell_1$ and to $(\mu d\log(n)/\varepsilon)^{O(1/\varepsilon)}$ for logistic regression. Finally, we show that our sketch can be extended to approximate a regularized version of logistic regression where the data-dependent regularizer corresponds to the variance of the individual logistic losses.

Published as a conference paper at ICLR 2023
ALMOST LINEAR CONSTANT-FACTOR SKETCHING FOR l, AND LOGISTIC REGRESSION
Alexander Munteanuu & Simon Omlor
David P. Woodruff'
Faculty of Statisties TU Dortmund University
Department of Computer Science
Carnegie Mellon University
44227 Dortmund, Germany
Pittsburgh, PA 15213, USA
al elexander... munt
de
dwoodruf@cs. cmu. edu
s simon. omlor @ www-ddoootddooooooo de
ABSTRACT
We improve upon previous oblivious sketching and turnstile streaming results for L and logistic regression, giving a much smaller sketching dimension achieving (11) approximation and yielding an efficient optimization problem in the sketch space.
Namely, we achieve for any constant > 0 a sketching dimension of (c)+to) for l regression and (sdd+t) for logistic regression, where is standard measure that captures the complexity of compressing the data. For & fi-regression sketching dimension is near-linear and improves previous work which either required 22oog d)) approooxiitaooon with this sketching dimension, or required a larger poly(d) number of rows. Similarly, for logistic regression previous work had worse poly(ud) factors in its sketching dimension. We also give a tradeoff that yields 1 + e approximation in input sparsity time by increasing the total size to (og(n)/e)))) Finally, we show that our sketch can be extended to approximate a regularized version of logistic regression where the data dependennndent regularizer corresponds the variance of the individual logistic losses.
for &ι and (jul (s)( ((L/e) for logistic regression.
INTRODUCTION
We consider logistic regression in distributed and streaming environments. key tool for solving these problems is distribution over random oblivious linear maps S E RR"x" which have the property that, for a given n x d matrix X, where we assume the labels for the rows of X have been multiplied into X, given only SX one can efficiently and approximately solve the logistic regression problem. The fact that does not depend on X what referred to as S being oblivious, which is important in distributed and streaming tasks since
can choose S without first needing to read the input data. The fact that S' is linear map is also important for such tasks, since given Sx(() and Sx one can add these to obtain S(X (1) + X x2)).. which allows for positive or negative updates to entries of the input in a stream, or across multiple servers in the arbitrary partition model of communication. see, c.g., (Woodruff 2014) for a discussion of data stream and communication models.
An important goal is to minimize the sketching dimension r of the sketching matrix S, as this translates into the memory required of streaming algorithm and the communication cost of a distributed algorithm. At the same time, one would like approximation factor that one obtains via this approach to be as small as possible. Specifically we develop and improve oblivious sketching for the most important robust linear regression variant, namely E regression, and for logistic regression, which is a generalized linear model of high importance for binary classification and estimation of Bernoulli probabilities. Sketching supports very fast updates which is desirable for performing robust and generalized regression in high-velocity data processing applications. for instance in physical experiments and other resource constraint settings, cf. (Munteanu et al. 2021 Munteanu] (023).
We focus the case where the number of data points is very large, i.e., n > d. In this case, applying a standard algorithm directly is not a viable option since it is either too slow or even becomes impossible when it requires more memory than can afford. Following the sketch & solve paradigm

---

Published as a conference paper at ICLR 2023
(Woodrufi 2014), our goal is in a first step to reduce the size of the data without losing too much information. Then, in a second step, we approximate the problem efficiently on the reduced data.
Sketch & solve principle:
1. Calculate a small sketch SX of the data X.
2. Solve the problem 3 = argmin, ((SX3) using a standard optimization algorithm.
The theoretical analysis proves that the sketch in the first step is calculated in such a way that the solution obtained in the second step is good approximation to the original problem, i.., that f(x 3) S C argming f (X33) holds for small constant factor C 2 1.
1.1
OUR CONTRIBUTIONS
For logistic regression our goal is to achieve an O D(ppaapproinnaation with an efficient estimator in the sketch space and smallest possible sketching dimension in terms of p and d, where μ p(X)
-0,05o (z,00
8uP340 Es,s<o ||
is data dependent parameter that captures the complexity of compressing the
data for logistic regression, Definition 2.1 As byproduct of our algorithms, we also obtain algorithms for f1-regression. We note that the parameter ja is necessary only for logistic regression, ie., for sketching E e-rregresioo, we set Ja 1. We summarize our contributions as follows:
1) We significantly improve the sketch of Munteanu et al. 2002]. More precisely we show with minor modifications in their algorithm but major modifications in the analysis that the size of the sketch be reduced from roughly O(u² dd d to (od for any > 0, while preserving (1) approximation to either the logistic or & loss.
2) We show that increasing the sketching dimension to (udlog(n)/=))0 00//)) is sufficient to obtain a 1 + approximation guarantee.
3) We show that our sketch can also approximate variance-based regularized logistic regression within an (1) factor if the dependence n in the sketching dimension is increased to n n2.5+ for any e > 0. We also give an example corroborating that the CountMi n-sketch that we use needs at least (m55 rows to achieve an approximation guarantee below log (μ).
1.2 RELATED WORK
Data oblivious sketching Data oblivious sketches have been developed for many problems in computer science, see (Phillips) 2017 Munteanu 2023) for surveys. The seminal work of Sarlós (2006) opened up the toolbox of sketching for numerical linear algebra and machine learning problems, such as linear regression and low rank approximation, ef. (Woodruff) 2014). We note that oblivious sketching is very important obtain data stream algorithms in the turnstile model (Muthukrishnan) 2005) and there is evidence that linear sketches are optimal for such algorithms under certain conditions eLi al. 2014 Ai al.) 2016). The classic works & regression have been generalized to other Lp norms (Sohler & Woodruff 2011 Woodruff & Zhang 2013) by combining sketching as fast but inaccurate preconditioner and subsequent sampling to achieve the desired (1 + E) appppooxinnaoo bounds. Those works have been generalized further to so-called M-estimators, i.e. Huber (Clarkson & Woodrufi 2015a) or Tukey regression loss (Clarkson al., 2019), that share nice properties such symmetry and homogeneity leveraged in previous works on E, norms.
L regression Specifically for é the first sketching algorithms used random variables drawn from 1 1-stable (Cauchy) distributions to estimate the norm (Indyk] 2006). It is possible to get concentration and a (1 + =) -approximmation in near-linear space by using a median estimator. However, in a regression setting this estimator leads to non-convex optimization problem in the sketch space. Since we want to preserve convexity to facilitate efficient optimization the sketch space, we focus on sketches that work with an & estimator for solving the & regression problem in the sketch space in order to obtain a constant approximation for the original e problem. With this restriction, it is possible obtain contraction bound with high probability so as union bound over net, but similar results are not available for the dilation. Indeed, subspace embeddings for the & norm have
'The tilde notation suppresses any polylog( udd eb even if no higher order terms appear. This allows us to specified in Theorems 1-3.
focus the main parameters and their improvement. The exact
2

---

Published as a conference paper at ICLR 2023
(cd) dilation (Woodruff & Zhang 2013 Li et al. 2021 Wang & Woodruff 2022). A 1 dilation is
only known to be possible when mapping to exp ((T/))) dimensions (Brinmman & Charikar 2005 )
even for single vectors as in [Indyk] 2006). We thus focus obtaining an ((1) approximation this
paper. Previous work had either larger (log(d)) distortion or larger poly (d) factors (Ind 2006
Sohler & Woodruff 2011). There exists (1 + >)aprooximatio algorithm (Sohler & Woodruff
2011) for turnstile data streams, running two sketches in parallel: one for preconditioning and another that performs é --ro--samlling from the sketch (Andoni et al.] 2009). However, has a worse poly(dloog()) update time and sketching dimension, see (Sohler & Woodruff 2011 Theorem 13), An advantage of our sketch is that it uses only random {0. 1) entrries which have better computational and implicit storage properties (Alon et al. 1986 1999; Rusu & Dobra 2007). More importantly, our approach works simultaneously for both, & and logistic regression. For the latter no near-linear sketching dimension was known to be possible since sketches for & cannot preserve the sign of coordinates, which is crucial for any multiplicative error on the asymmetric logistic loss.
Generalized linear models (GLMs) It is important to extend the works on linear regression to more sophisticated and expressive statistical learning problems, such as generalized linear models (McCullagh & Nelder 1989). Unfortunately, taking this step led to impossibility results. Namely, approximating the regression problems on a succinct sketch for strictly monotonic functions such as logistic loss (Munteanu al. 2018 or heavily imbalanced asymmetric functions such as Poisson regression loss (Molina et al. 2018) allows one to design a low-communication protocol for the INDEXING problem that contradicts its ((n) bit randomized one-way communication complexity (Kremer et al. 1999). This implies an (2(n) sketching dimension for these problems. To circumvent this worst-case limitation for logistic regression, Munteanu et al.) (2018) introduced a natural data dependent parameter j that can be used to bound the complexity of compressing data for logistic and probit regression (Munteanu et al. (022). This also led to the very first oblivious sketch for logistic regression (Munteanu et al. [ with a polylogarithiic number of rows for mild data. We improve this by giving, the only near- near-linear sketching dimension in d and μe for logistic regression. The previous best sketching dimension obtained by Lewis weight sampling (Mai et al. 202T), required (1²²d) and crucially their sketch is not oblivious so cannot be implemented in a turnstile data stream, with positive and negative updates to the entries of the input point set. For lower bounds, an (d) dependence is immediate since mapping fewer than d dimensions contracts non-zero vectors in the null-space of the sketching matrix to zero. An (14 lower bound is immediate from Munteanu et al. (2018) and was recently generalized by Woodruff & Yasuda 20033 to more natural settings.
Variance- based regularization Regularization techniques have been proposed in the literature for many purposes, such as reducing the effective dimension of statistical problems or limiting their expressivity to avoid overfitting. Regularization was also proposed to relax the logistic regression problem. In an extreme setting where the regularizer dominates the objective function, the contribu- tions of data points do not differ significantly. The problem then becomes easy to approximate by uniform subsampling (Samadian et al. 2020). To address the bias-variance tradeoff in machine learn- ing problems in more meaningful way and to provably reduce the generalization error of models, Maurer& & Pontil 22099) proposed to add a data- dettaddeenddnt variance-based regularization. Since this results in non-conver optimization problem even for convex objectives, Duchi & Namkoong (2019); Yan et al. (2020) used optimization tricks to reformulate a convex variant with additional parameters that can be integrated into standard hyperparameter tuning. Interestingly, this data-dependent regular- ization - in contrast to standard regularization - does not relax the sketching problem but makes it more complicated, requiring in the case of logistic regression a combination of & and & geometries to be preserved. We show that our sketch can deal with both simultaneously.
1.3 OUR TECHNIQUES
Our main motivation is to reduce the large dependence on the parameters of the oblivious sketching algorithm of Munteanu et al. (202)) Their sketch consists of Ollog n) levels that take subsamples at exponentially decreasing rate, and apply a CountMin-skette to each subsample to compress ( dilation bounds. Our
to roughly size ( (μ/=)") which gives (1 - E) contraction but only O(1
new methods significantly improve over their sketching dimension for obtaining (1 -) contraction
bounds. The large dependence on came from adapting the analysis of Clarkson & Woodruff (0155)
bb an argument in the proof of Lemma 7 of Sohler & Woodruff 2011). cf. WWodduff 2021 Problem l).
'The exact constant was not specified but overcounting their parameters gives at best 8-approximation.
3

---

Published as a conference paper at ICLR 2023
to work for the asymmetric logistic loss function. This required to rescale e' e/μ translate the estimation error of e'I|=|]a to an error of e|læ* 1I1. where the latter quantity sums only over the positive entries of z. We avoid this by noting that we can oversample the elements by factor of J to capture sufficiently many elements to approximate the required e e||=+|] ||1 error directly. However, the analysis of the so-called heavy hitter requiress f elements to be perfectly isolated when hashing them into buckets, which requires μ² buckets to succeed with good probability. To obtain linear dependence on μu, we sacrifice some sparsity in our sketching matrix. Instead of hashing to a single bucket at each level, we hash each element multiple times. The best known trade-off between sketching dimension and sparsity is due to [Cohen (016) for the Count-sketch. We adapt the technique to our CountMin-ssettr collisions by summing the elements instead of taking a random sign combination. This brings the dependence on down to quasi-linear. The dependence on d and & also benefit from this technique but at this point, our analysis still requires a dl dependence. This comes from nceding to separate the heavy hitters from other large coordinates for all vectors in net of exponential size in d. To bring the dependence on down to near-linear we densify our sketch to roughly O( pd log(n)) non-zeros per column, which separates the heavy hitters almost entirely and yields our result.
we hash each element to roughly O log(ud/E)) buckets and resolve
We also improve the dilation bounds from a factor of 2 8 to a 2-approximation: previous analyses were conducted by bounding the expected contribution of weight classes Wa = {i 2- < z < 2-9} to the different levels in our sketch. A simple bound of O(log n) was improved to (()) by a Ky-Fan norm argument, which cuts off elements that have low redundant contribution. We reverse the perspective and ask for each level h, which weight classes are well represented? This allows us conduct more fine-grained analysis: we define intervals QA = [g(2), [()) and
Qn S Q/ (1(1), q(44] and quantify their size depending on the number of buckets, such that weight classes q É Q% do not contribute at all, q E Q, make a nog-neglig contribution, and q E Qn are additionally well-approximated. It is thus desirable to choose the number of buckets in such a way that 141//Qu) s 1. Moreover, we ask how the intervals in consecutive levels overlap. It turns out that slightly increasing the number of buckets in each level to (jud²) allows us to show that each q appears only in most two consecutive levels (in expectation) which yields 2-approximation Indeed, the argument can be continued by raising the size of the sketch to any power of & E N, resulting in an expected contribution in at most (1 + 1/k) levels, which yields a (L aaproxxaaatiii using (odlog( log(n)) (n)/=) rows. An exponential dependence on 1/s is best known for beacchhin--sseee estimators of the l norm (Indyk) 2006 Li et al. 2021) that embed into lower-dimensional& f,, and our sketch can be used as such an estimator for & as a special case.
Finally, as a corollary and important application of our results, we obtain similar oblivious sketching bounds for a variance- regulaarzed version of logistic regression, see Section [.2] combines aspects of the E geometry of the sum of logistic losses with the f2 geometry that appears in the sum of squared logistic losses. The analysis very similar to the standard logistic regression loss but requires redefining the weight classes in terms of squared values 2i and converting between the two norms, which introduces roughly another O /r)--ffttrr. Previous work on data reduction methods for generalized linear models that work for different l, losses were either based on sampling (Muntcanu et al. 2022) or worked only for symmetric functions such as norms (Clarkson & Woodrutt (2) However, an oblivious sketch for our loss function requires preserving the signs of elements which is not possible with previous sketching methods. Relying on the CountMi n-sketch as in (Munteanu al., 2021) ) thus seems necessary. For this choice we show that an additional ((Vn)-factoo is unavoidable and hereby we corroborate the tightness of our analysis.
PRELIMINARIES AND MAIN RESULTS
For é, regression, we consider as inputs a data matrix X gaxd and a target vector Y " The task is to find / E argmingges [| - YlI.. We note that up to constants, this corresponds to minimizing the negative log- ligeliiid of standard linear model Y = X33 + 1 with Laplace noise distribution 7. L(0. 1) for all i E [n]. Our goal will be to design an oblivious linear sketching matrix S such that the sketch X' = S S[x, Y] is significantly reduced in its number of rows and solving the compressed & regression problem in the sketch space yields an 0(1) approximation to the same problem on the original large data.
ti... the coordinates of z with largest & leverage score
4

---

Published as a conference paper at ICLR 2023
Up slight modifications, this sketch will also allow us to approximate logistic regression within constant factor. For logistic regression, assume that we are given a data set Z = {Z1..... Zn. with 2 E I for all i [n], together with set of labels Y {V1..... Vn with y/: E (-11,11 1] for all i E [n]. In logistic regression the negative log-likelihood (McCullagh & Nelder 1989) is of the form ((3 = Σ In(1 +
which, from a learning and optimization perspective, is the objective function that we would like to minimize. For r E R we set E(r) In(1 + exp(r)) to simplify notation. Then we have that E( y12,3). We also include a variance-basee
regularization as proposed in (Maurer & Pontil 2009 Duchi & Namkoong] 2019) Yan et al., (020) to decrease the generalization error. We view our data set as n realizations of a random variable (2, y), where each (zx, yi) is drawn i.i.d from an unknown distribution D. Then the expected value of the negative log- bogllikelhhodd (on the empirical sample) for any fixed 3 equals B(E(-W/ v28)) = 72 ( 2, Y). The variance given by
C( Z.
B({(-yz3))) B(E(-yz3))² = 1 Ei= E (
E ((-),,,8))
We also introduce a regularization hyperparameter À E Rzo. Then our objective minimize
E(((-y=3)) + Var Var(e(- (((-))))))
2
As 2; and y/ always appear together, we set vi = zi Further we set X E R to be the matrix with row vectors 2; for i E [n]. For technical reasons we include a weight vector w E R7 into the objective. Then our goal is to find 3 E IRd minimizing
(x _
x Σ wyL(=, + 3 - wr((x,3))*
The unweighted case corresponds to choosing to be the vector containing only I's, in which case we set (( = (X
We also note that f(x 2 トト (xx33) since the variance term is non-negative. Next, observe that mingeR* Bx S f(0) = {(0) ln). In our analysis we investigate functions E(r) and E(r)?. Further we split/ f into three functions (X x E (x.3), (x 2m E ((, and fx(XB) ( E=,,(,,,))
(XB))
In contrast to the & regression problem, a data reduction for f or even f1 where the sketch size is r n cannot be obtained in general. There are examples where no sketch of size r = o(n/ log n) exists, even for an arbitrarily large but finite error bound (Munteanu et al.) 2018). If we require the sketch to be a subset of the input, the bound can be strengthened ( (Tolochinsky
al.. 2022). Those impossibility results rely on the monotonicity of the loss function and thus extend to the function f studied in this paper. To get around these strong limitations, Munteanu et al. (2018) introduced a parameter fı natural notion for parameterizing the complexity of compressing the input matrix X for logistic regression. It was recently adapted for p-generalized probit regression (Munteanu et al. 2022). We work with a similar generalization given in the following definition.
Maaattinn,,uutaanuu
Definition 2.1. Let X E Raxd be any matrix and let p E (1). We define
En, |
(x( sup (ER
Ev 12,3p"'
We say that X is j-complex max (x), <
Our goal is to construct slightly relaxed version of a sketch that suffices to obtain a good approxi- mation by optimizing in the sketch space:
Definition 2.2. Given datasel (X, w), a subset V C Cd,, a and e > 0. A weak weighted (V, a, (u,e)--sn skketch C = (X', w') for J is a matrix X' E Brxd together with a weight vector w E R
such that it holds simultaneously that: For all B E V we have
(X' 3) 2 (1 (1-=)ffu(X (X(3)
and 3 E V minimizing fo it holds that
(x' 8*) < (X.3")
Further for any B E TRd V it holds that
(x' > min fwr (X'3). BEV
5

---

(1 + as), and Published as a conference paper at ICLR 2023
We note that sketch satisfying the definition for V === is known in the literature lopsided embedding (Sohler & Woodruff 2011] Clarkson & Woodrufi] 2015b, Feng et al. (021). We denote by nnz(X) ) the number of non con-zero entries of X. Our main results are the following:
For ( regression, where the objective is || - Yl11. we have
Theorem 1. Lef X RRad and let Y E IR.. Lel e, 0 and let > 1. Then there distribution over sketching matrices S E R and a corresponding weight vector w E R', for which X' S[X, Y] can be computed in T time in single pass over a turnstile data stream such that (X', w) is a weak weighted (Re ,0, (k-kech for & E1-regression with failure probability at most P. where
(x))n())))((()), and 1. D(dl+oln(n)) 3+()) for any constant 1 2 0, T
a 1+ and P are constant,
2. 0( (0
32dlnfn)
( y T O(nz (X)), a (1 + as), and
P P== 8
For logistic regression where the objective function is only fi(X,)), we have
Theorem 2. Let 1 12 c > be any constant. Let X E Raxd be a p-complex matrix for bounded f E O((dlgg (n)))). Let E, 0 and let > 1. Then there is distribution over sketching matrices S E grx" and corresponding weight vector w E IK, for which X' = SX can be computed in T time in a single pass over a turnstile data stream such that (X,w)) is weak weighted (R. a. =)-sttcc for fi with failure probability at most P, where
1. -(pdd 1n(n)2+44) 4c,, T O(ud (nnnnn)nnnn)))))) (X)), and a 1 1+ 1 and P are constant.
e
2. = 0
2² 1n(n))2²
32du 32du In(n)²
@Ad
eta 11t=", T = ((nnz(X))
de p = 8
gb
+
Note that setting 8-1 and substituting with eō in the second item yields a (1++) approximation with probability at least - 26.
For the variance- based regularization, where consider the full objective function f(X we have Theorem 3. Let X E nx be a jı-compeex matrix for bounded μ < n. Let e, > 0, let a > Then there is distribution over sketching matrices
and set V (X3 fi(33) < ln(2)( S Tx and a corresponding weight vector w E IK", for which X' = SX can be computed in T time in single pass over turnstile data stream such that (X', w) a weak weighted (V, a, E,,E) e)-sketch for f with failure probability at most P. where
r (( 0.34 pd pn (n) max (d. In(n), 1,0-_,111111101 _8-1,11 + d= 1n())
Vi for aobbttaryy constant de
1 12c> 0, T O(nnz(X)), a = 1+ c. and P 8 5+1
We note that for generality of our results we specify a tradeoff between our dl+c dependence and an arbitrarily large constant approximation error 1 1 1/c. We stress that specific parameterizations yield strictly improved results over previous work. For instance we improve the 2 8-approximation of (Munteanu et al. 2021) within Ö(H7 d8) to 2-approximation within (uud²) by choosing 1. We further improve several lopsided & + embedding results factor of where previous approximations gave only Od d) (Sohler& & Woodruff 2011). Olog d) (Woodruff 2021 or 2 8
(Clarkson & Woodruff (015a) or gave only non-convex estimators the sketch space (Backurs et al.
2016) along with larger superlinear dependencies on d.
Technical description of the sketch Our contributions lie mainly in the improved and refined theoretical analyses. The sketching matrices of Theorems 1-3 are the same as in (Munteanu et al.) 2021) up to small but important algorithmic modifications specified in the textual description below, and in pseudo-code, see Algorithm in the appendix. The sketching matrix consists of O(log n) levels. In each level we take a subsample of all rows é E [n] at a different rate and hash the sampled items uniformly to small number of buckets. All items that mapped to the same bucket are summed up. This corresponds to a CountMin sketch (Cormode & Muthukrishnan, 2005) applied to the subsample taken at each level. More specifically, we will use the following parameters:

---

Published as a conference paper at ICLR 2023
bm: the number of levels,
NA the number of buckets at level h,
Ph: the probability that any element x; is sampled at level
As we read the input, we sample each element I; for each level h S f.m with probability Ph- The sampling probabilities are exponentially decreasing, i.e., Pt. x 1/8/ for some E R with b > 1. The weight of any bucket at level h is set to 1 1/pn. At level hm. we have Ph... x It thus corresponds to a small uniform subsample and the number of buckets is equal to the number of rows that are sampled, i.e., N, == N,... R riPh...
rppu- At level 0 we sample all rows, i.e., Po = 1 and the number of buckets is either the same as for the levels h E (0, hm) ) or less. Consequently level is standard Count Min sketch of the entire data. All levels h (0. hm) have the same number of buckets N₁, = NN. For obtaining subquadratic dependence on J4, d in item 1 of Theorems and 2, the sketch level 0 is densified, which means that each element is hashed to a number of > 1 buckets. The idea of the sketching algorithm is that for each fixed / E Rd we partition the coordinates of X into weight classes depending on their contribution the objective function. Each level approximates well a certain range of weight classes if their total contribution is large enough. For example the highest level h.n. will cover all the elements in small weight classes and the lowest level 0 will capture the so so-called heavy hitters that appear rarely but have a significant contribution to the objective. Another algorithmic change randomizing the size of the sketch level O, which is crucial for obtaining a (1 + apaapooxximtionn For the exact details we refer to the analysis and Assumption A.
3 HIGH LEVEL DESCRIPTION OF OUR NOVEL ANALYSIS
Several details of the analysis, such as assumptions on the parameters, technical lemmas, and proofs deferred to the appendix. We start by splitting the functions Si and f2 into multiple parts:
Lemma 3.1. It holds that (x B) = Em, | + Ei= E( (1=)2) and similarly we have
that (x2(X)) Ex,800 |r, + 2 ((
(=,
|x, + Σ. ((-(2r,1)).
This can be used in the following way: if all & make only small contributions then uniform sampling performs well. This is not the case for all parts of f but it holds for some 'small' parts of that appear in the splitting introduced in Lemma 3.1
Next we deal with the remaining 'large' parts of f. We will first analyze the approximation for single B. To this end fix 3 E Rdd and set X,3. Our goal is to approximate ||= := Ei 2i where =* E Rgo is the vector that we get by setting all negative coordinates of to O. We assume w.l.o.g. that ||0||]
We can do this since u + || ||1 is absolutely homogeneous. In order to prove that (S2) ([S2)+11 ||1 approximates || 1|1 well, we define weight classes: given E N we set W E [n] 2 E (2- (0---1,-99). )). Our analysis applies with slight adaptations to & regression preserving ||~||| for the residual vector X33 Y. The analysis is entirely in the appendix due to the page limitations. We give high level description for preserving 2| 111 needed for logistic loss.
Contraction bounds We set gm = loog2 ("(+t() (In(n)) since n 2 max(ju,--1 J.. We say that W is important if ||Wtt || 2 E' == uam and set Q" {q S Qm. W is important ). The idea is that the remaining weight classes can only have small contributions to || so it suffices to analyze Q*. To prove the contraction bound for 2, i.e., that [S22)=]] 2 (1 - ce)]|=+1] holds for absolute constant c, it suffices to show that the contributions of important weight classes are preserved. For a bucket B we set G(B) = Σ&EB žj and G+ (B) level h, there exists an 'inner' interval Qn = (2), qu (3) such that if W for q E Qn. is important, then there exists a subset W C W such that each element of W is sampled at level h and such that Σiew; G(B,) 2 (1 - =)]lW; Ph. where B, is the bucket at level h containing 2, Since the weight of all buckets at level h is equal to P% we have that the contribution of W is indeed at least (1 E) e)| [|, The choice of our parameters then guarantees that U N and thus for any important weight class there is at least one level where it is well represented. Finally, we construct a net of size |Nll
max( 0}. In fact, we show that for each
We ensure that the contraction bound holds for each fixed net point 2 E N2. with failure probability at most 5 which will dominate- among other [N.
exp(O((log(n))
parameters the size of our sketch. By union bound, the contraction result holds for the entire net
7

---

Published as a conference paper at ICLR 2023
with probability at least 1 - 8. The net is sufficiently fine, such that we can conclude the contraction bound by relating all other points = = X3 E R" to their closest net point.
Dilation bounds We will also show that the expected contribution of any weight class is at most 2||Wat II1 or even less. To this end we increase the number of buckets NN and apply a random shift at level 0, i.e., we choose the number of buckets at level 0 randomly. We investigate again each level separately and prove that for each level h there exists an 'outer' interval Qj = Ig (1), 9n (4) such that for any q & Qi the weight class Wg makes no contribution level h at all. More specifically we show that no element of W, contains only elements of o appears at level & for q < qu. (1) and that for any bucket B at level h that UQ>0x(1) Wg it holds that G(B) S O.
Then we show that if N is large enough it holds that for each q N there are most two levels h such that Q/ and that the expected contribution of any weight class at any level is bounded by 1|W:ll I11. We conclude that the expected contribution of any weight class at most 2/|Wa Increasing the size of N increases the size of the 'inner' interval [q, 9n (3)] =: Qn C Q/2 while the size of Q/ remains (almost) unchanged such that 1/ / approaches 1. As consequence, this also decreases the number of indices q E that appear in two intervals of the form Q/ More precisely, we show that for each & E N we can increase N in such a way that only 1/k fraction of the weight classes appear in two of those intervals. Note that all weight classes that appear only in a single 2% have an expected contribution of [| [12 Recall that all indices This is handled by applying random shift, implicitly setting (3) randomly in appropriate way such that the expected contribution of any weight class W is bounded by at most (1 + 1/b)]] Il1.
7 Ila-
considered level O.
Extension to variance-basee regularized logistic regression We show that our algorithm also approximates the variance well under the assumption that roughly (x(3)) S (2).). We stress that this assumption does not rule out the existence of good approximations. Indeed, even the minimizer is contained as observed in the preliminaries, since we have that mingeaa ((X S f(0) = (0) = I2)).. Focusing on a single = = X 3, we need to show that Σnz,> 2 is approximated well, which is done very similarly to the analysis for Σiz 2; sketched above, but with several adaptions to account for the squared loss function. We note that the increased sketching dimension in terms of /n comes from the inter norm inequality ||ك||| S /nili=rlle Lemma F. 14 the appendix shows that this dependence not be avoided using the FountMin-sketeh It does not rule out other methods that may allow lower sketching dimension. We stress that other known standard sketches do not work for asymmetric functions since they confuse the signs of contributions leading unbounded errors for our objective function or plain logistic regression, see (Munteanu et al. 2021).
4 EXPERIMENTS
We implemented our new sketching algorithm into the framework of Munteanu et al. (0021 3 Pseudocode can be found in Appendix G.. The crucial difference is that at level of our sketch, each element gets mapped to multiple buckets instead of only one. Sketch (old) denotes the sketch used in (Munteanu et al. T02T) and is highlighted in red in the plots. Sketchs is the sketch where each entry is mapped to E 12, 5, 10) buckets level O. Each sketch was run with 40 repetitions for various target sizes. world benchmark data was downloaded automatically by the Python scripts: the Covertype data consists of 581, 012 cartographic observations of different forests with 54 features. The Webspam data consists of 350, 000 unigrams with 127 features from web pages. The Kddcup data consists of 494, 021 network connections with 41 features. On the real-world data we see in Figure [ slightlly improved performances over the previous sketch for Covertype and Webspam. On the Kddeup data we see slightly weaker performance. We also see that increasing the sparsity parameter too much results in a worse performance, which is especially true for X > 0 (partly in the appendix). This indicates that the variance term is large for Kddeup and the /nn dependence dominates the sketching size necessary to decrease the error in the squared variance-regularizall term. We created a synthetic data set that has multiple heavy hitters for the sake of showing the benefits of the new sketch. A detailed description of our construction can be found in Appendix G along with intuition why it is complicated for the old sketch, while our new sketch can handle it much better. The data set consists of n 40, 000 points and the dimension is d 100. We see in Figure I (bottom left) that the increase in the number of buckets each elements is hashed to improves
"code available at https:://///.... httttp::///gitbb..cooo///o www.. http:///w00etttt..oosossssttttta logeg
vi
8

---

Published as a conference paper at ICLR 2023
Covertype A
Webspam,
Kédcup.
100
5:0
Skitch (o40
Shath (ok)
1m6-
Skittlc Skitolo Skeolit
Sketti
Skettlo
1/0
Skerh11
100
15000
20000
2003
2000
Covertype À 0.1
Webspam, A 0.1
Kdócup, A= 0.1
1/1
22
200
Skech (44)
Seeth (14)
Swech (ok)
1.44
Skitel
Skittic
Skita
Skitolo
Skittl
Swidl
Sketcht
Skethh1
Swetch2
100
1.2
1/0
1091
10:30
1690)
20003
2043
3.00
1900
12:00
11:00
1000
19000
20000
20000
00/30
40000
Synthetic data
Synthesic data
Webspam
Suerk
Skarch (cid)
Caucty
Skutc2
medin appounmatt
Skatchs
Sketch1
0000
1323
2000
3000
300C
3000
4000
3.59
modian sampiinng time (6)
0.15
01:00
0.25
0.50
1.0
2500
5000
7000
1000
13300
15300
Figure 1: Comparison of median approximation ratios of the old sketch vs. the new sketch with various settings for the sparsity 8 E {2, 5, 10} as well as for the regularization parameter À E (0,.1) .13 for real-world benchmark data (rows 1-2). Comparison of median approximation ratios and sketching times (row 3, left, middle) for our synthetic data. Comparison to the Cauchy sketch (row 3, right).
from approximation ratios between 7 and 8 for the old sketch to 3 or even 2 approximations for the modified sketches. The sketching times are only slightly increased for larger values of s, allowing for fast processing time (bottom middle). We omitted the time plots for the other data sets and parameterizations since the general picture is consistently as expected: Sketchs is almost times slower than Sketch (old). We added another comparison between our Sketch and the Cauchy sketch for an & regression problem (bottom right). We see that the new sketch, using any degree of sparsity E {2, 10), outperforms the Cauchy sketch by a large margin in terms of approximation factor (while being a lot faster to apply than the dense matrix multiplication). More plots and discussion can be found in Appendix G We also discuss stochastic gradient descent (SGD) together with supporting experiments in Appendix G While SGD performs well on real-worke data (though not better than sketching), it suffers from arbitrarily bad errors when applied to our synthetic data.
5 CONCLUSION
We obtain significantly improved bounds on the number of rows that are sufficient for obliviously sketching logistic regression p-complex data up an (1) factor. Our bounds are almost linear in terms of the dimension d and a data dependent complexity parameter μ that bounds the complexity of data reduction techniques for logistic regression and related loss functions. Our results are achieved by modifying the sketching approach Munteanu et al. (202T). which allows a change of perspective and facilitates a fine- ane-grained analysis of the contributions of single levels in the sketch. As a result, we also develop the first oblivious sketch for obtaining a (1 + >>-approximation albeit with an exponential dependence on 1/E which is likely to be required for our estimator due to corresponding hardness results on sketching & norms. We also extend the analysis to work for a variance-baa based regularized version of logistic regression which combines the E and l2 related loss functions and is of great practical relevance for reducing generalization error in statistical learning. It remains challenging open question whether we can further reduce the upper bounds to or below O(jd) or increase the lower bounds from 2(p + d) to or above R(Hd). It would be interesting to study our sketching techniques under assumptions such as sparsity that allow to get below linear sketching
dimension (Mai et al. 2023

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENTS
We thank the anonymous reviewers for their valuable comments. We thank Tim Novak for helping with the experiments. Alexander Munteanu & Simon Omlor were supported by the German Research Foundation (DFG), Collaborative Research Center SFB 876, project C4 and by the Dortmund Data Science Center (DoDSc). David P. Woodruff was partially supported by Simons Investigator Award and by the Office of Naval Research (ONR) grant 100014-18-1-2566
REFERENCES
Yuqing Ai. Wei Hu, Yi Li, and David P. Woodruff. New characterizations in turnstile streams with applications. In 31st Conference on Computational Complexity (CCC), pp. 20:1-20::00 2016.
Noga Alon, László Babai, and Alon Itai. A fast and simple randomized parallel algorithm for the maximal independent set problem. J. Algorithms, 7(4):567-583) 1986.
Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. J. Comput. Syst. Sci., 58(1 (8(1):137-147, 1999.
Alexandr Andoni, Khanh Do Ba, Piotr Indyk, and David P. Woodruff. Efficient sketches for earth- mover distance, with applications. In 50th Annual IEEE Symposium on Foundations of Computer Science, (FOCS), pp. 324-330, 2009.
Arturs Backurs, Piotr Indyk, Ilya P. Razenshteyn, and David P. Woodruff. Nearly-optimal bounds for sparse recovery in generic norms, with applications k-median sketching. In Proceedings of the 27th Anmual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 318-337, 2016.
Sergei Bernstein. On modification of Chebyshev's inequality and of the error formula of Laplace. Ann. Sci. Inst. Sav. Ukraine, Sect. Math, 1(4):38-49, 1924.
Bo Brinkman and Moses Charikar. On the impossibility dimension reduction in f, J. ACM, 52(5): 766-788, 2005.
Herman Chernoff. A measure of asymptotic efficiency for tests of hypothesis based on the sum of observations. The Annals of Mathematical Statistics, pp. 493-507, 1952.
Kenneth L. Clarkson and David Woodruff. Sketching for M-estimators: A unified approach to robust regression. In Proceedings of the 26th Annual ACM-SIAM Symposium Discrete Algorithms (SODA), pp. 921-939, 2015a.
Kenneth L. Clarkson and David P. Woodruff. Input sparsity and hardness for robust subspace approximation. In Venkatesan Guruswami (ed.), IEEE 56th Annual Symposium on Foundations of Computer Science, (FOCS), pp. 310-329, 2015b.
Kenneth L. Clarkson, Ruosong Wang, and David P. Woodruff. Dimensionality reduction for tukey regression. In Proceedings of the 36th International Conference on Machine Learning, (ICML), pp. 1262-1271, 2019.
Michael B. Cohen. Nearly tight oblivious subspace embeddings by trace inequalities. In Proceedings of the Seventh Annual ACM-SIA SMMM Symposium Discrete Algorithms (SODA), pp. 278- 287, 2016.
Graham Cormode and S. Muthukrishnan. An improved data stream summary: the count-min sketch and its applications. Algorithms, 55(1):58-77 -5:5585,555 2005.
John C. Duchi and Hongseok Namkoong. Variance-based regularization with convex objectives. J. Mach. Learn Res., 20:68:1-68:55, 2019.
Zhili Feng, Pranceth Kacham, and David P. Woodruff. Dimensionality reduction for the sum-of- distances metric. In Proceedings of the 38th International Conference on Machine Learning, (ICML), pp. 3220-3229, 2021.
Piotr Indyk. Stable distributions, pseudorandom generators, embeddings, and data stream computation. J. ACM, 5303)3007-33,, 2006.
10

---

Published as a conference paper at ICLR 2023
Ilan Kremer, Noam Nisan, and Dana Ron. On randomized one-round communication complexity. Computational Complexity, 8(1):21-45 1999.
Yi Li, Huy L. Nguyen, and David Woodruff. Turnstile streaming algorithms might as well be linear sketches. In Symposium on Theory of Computing. (STOC), pp. 174-183, 2014.
Yi Li, David P. Woodruff, and Taisuke Yasuda. Exponentially improved dimensionality reduction for
l Subspace embeddings and independence testing. Conference on Learning Theory (COLT), pp. 3111-1999 2021.
Tung Mai, Cameron Musco, and Anup Rao. Coresets for classification simplified and strengthened. In Advances in Neural Information Processing Systems 34 (NeurIPS), pp. 11643-11654 2021.
Tung Mai, Alexander Munteanu, Cameron Musco, Anup B. Rao, Chris Schwiegelshohn, and David P. Woodruff. Optimal sketching bounds for sparse linear regression. In Proceedings of the 26th International Conference on Artificial Intelligence and Statistics (AISTATS), 2023.
Andreas Maurer and Massimiliano Pontil. Empirical Bernstein bounds and sample-variance penaliza- tion. In Proc. of the 22nd Conference Learning Theorry (COLT), 2009.
P. McCullagh and J. A. Nelder. Generalized Linear Models. Chapman & Hall, London, 1989.
Alejandro Molina, Alexander Munteanu, and Kristian Kersting, Core dependency networks. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI), pp. 3820- 3827. AAAI Press, 2018.
Alexander Munteanu. Coresets and sketches for regression problems data streams and distributed data. In Machine Learning under Resource Constraints, Volume 1 Fundamentals, pp. 85-98. De Gruyter, Berlin, Boston, 2023.
Alexander Muntcanu, Chris Schwicgelshohn, Christian Sohler, and David P. Woodruff. On coresets for logistic regression. In Advances Neural Information Processing Systems 31, (NeurIPS), pp- 6571, 2018
Alexander Munteanu, Simon Omlor, and David P. Woodruff. Oblivious sketching for logistic regression. In Proceedings of the 38th International Conference on Machine Learning (ICML), pp. 7861-7871,
Alexander Munteanu, Simon Omlor, and Christian Peters. p-Generalized probit regression and scalable maximum likelihood estimation via sketching and coresets. In Proceedings of the 25th International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 2073-2100, 2022.
S. Muthukrishnan. Data streams: Algorithms and applications. Found. Trends Theor. Comput. Sci., 1 (2), 2005.
Jeff M Phillips. Coresets and sketches. In Handbook of Discrete and Computational Geometry, pp. 1269-1288 Chapman and Hall/CRC, 3rd edition, 2017.
Florin Rusu and Alin Dobra. Pseudo-random number generation for sketch-based estimations. ACM Transactions on Database Systems, 32(2):1-48, 2007.
Alireza Samadian, Kirk Pruhs, Benjamin Moseley, Sungjin Im, and Ryan R. Curtin. Unconditional coresets for regularized loss minimization. In The 23rd International Conference Artificial Intelligence and Statistics, (AISTATS), pp. 482-492, 2020.
Tamás Sarlós. Improved approximation algorithms for large matrices via random projections. In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, (FOCS), pp. 143 152,24 2006.
Christian Sohler and David P. Woodruff. Subspace embeddings for the 4--ormm with applications. In Proceedings of the 43rd ACM Symposium on Theory of Computing, (STOC), pp. 755-764, 2011.
Elad Tolochinsky, Ibrahim Jubran, and Dan Feldman. Generic coreset for scalable learning of monotonic kernels: Logistic regression, sigmoid and more. In International Conference on Machine Learning, (ICML), pp. 21520-21547, 2022.

---

Published as a conference paper at ICLR 2023
Ruosong Wang and David P. Woodruff, Tight bounds for { oblivious subspace embeddings. ACM Trans. Algorithms, (111):::1-8:222 2022.
David P. Woodruff. Sketching as tool for numerical linear algebra. Found. Trends Theor. Comput.
Sci., 10(1-2)11-157, 2014.
David Woodruff. Problem set solution), 2021.
http://www wwww cs. cmu.edui Solu- cs. cmu http:////aaaa////////////a//////
afs/cs/us wtt.c///sseeeeeeeeeeeeeeeee.eeee www.dwuf
tion:
http://wwin http://www.cs.cm.
15859 fa fll-ffll2222 www.221/w3oooutttiotco
pdf
Accessed: 5-18-2022.
David P. Woodruff and Taisuke Yasuda. Online Lewis weight sampling. In Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, (SODA), pp. 4622-4666, 2023.
David P. Woodruff and Qin Zhang. Subspace embeddings and ep-regression using exponential random variables. In The 26th Annual Conference on Learning Theory, (COLT), pp. 546-567, 2013.
Yan Yan, Yi Xu, Lijun Zhang, Xiaoyu Wang, and Tianbao Yang. Stochastic optimization for non- convex inf inf-projection problems. In Proceedings of the 37th International Conference on Machine Learning, (ICML), pp. 10660, 2020.
12

---

Published as a conference paper at ICLR 2023
A OMITTED DETAILS FROM SECTION 2
For technical reasons we make the following assumption: Assumption A.1. We assume that:
M, Am = min iiEN
I
121n(n)
(1)
bN
N 2 32m] 1+c antt h 1//e//
um
(2)
Ng
18H1
b
(3)
32m
1IIn0 O(dIn(n))
(4)
64pmm
Pu 2
(5)
c2n
Here e some constant used in the proof of Theorem Since we want our sketch to have fewer than rows we will also assume that = - 8- We also assume that E S 1/4.
We will further use the following probability tools:
Proposition A.1. [Bernstein's 's Inequality] /hequality/(Berrsteli Berrstein 1924) Let Xi...., Xu be independent zero- mean random variables. Suppose that [X,] it holds that
S M holds almost surely for all i. Then, for all positive I
P Σ Ex.2
exxp
[X Mi
i=1
Proposition A.2 (Chernoff bound (Chernoff
1952)). ) Let X
Ei= X,, where X; = with Pi, and all X, independent. Let μ E[X)=
probability p; and X; O with probability
E. Ps. Then for all ô E [0, 1] it holds that
P([X - 1l 2 5p) - 2exp(-8'
and for any 8 1 it holds that
P(X - 41 2 kp) <
Lemma A.3. Let y be binomially distributed random variable with parameters n.p. Let n' e N. Then if n' 2 pn we have that
P(ly - pml > n') S exxp (-n'/3)
Else if rd epn we have that
P(ly - pm| > n') < 2 exp (-en' /3)
Proof of Lemma A.3 Note that Rly) = pn. Using the Chernoff bound we get that if n' 2 pm
P(yy pn| > n²) < (exp(_(n'/np))ng)
exx((-n' /3)).
If nn' =Epn the Chernoff bound implies that
P(y - pn| > n < 2exp(-e = cxp (-en') /3)
3.1 in the main body splits the objective into "large" and 'small' parts which we handle separately.
Lemma
Proof of Lemma 3.1
Note that for E R it holds that
{(r) = In (1 + +e) = -n +()
In (e +1) In(ee)) ((-r)
Now the first equation follows immediately by E(x,8) 2;3 + ((-2;3)) = |r, f(- 11;;31
for v;3 > and f(2,3) = {(-(xg))) for r. < O. Further we have that (z,3 + E( (2,)))))²
(x,8)² + 20(-=2,)x,,
3) Thus the second equality follows by substituting ((r33) with 1 + 2 ([-1(x,6)]aa (1 + E( (1122,3))2 = (z,3)² + 28( (1,,,,),,8 + ((-x,3)² for x3 and
(( 54 2 for 2,, 0.
13

---

Published as a conference paper at ICLR 2023
B ESTIMATING THE SMALL PARTS OF f
We can bound the 'small' parts using the following lemma:
Lemma B.1. For arbitrary E [n] it holds that ((-1x;11) 1 and also 20(-12;;8))
8(- T <
Proof. First observe that ((-122,3)) - ((0) = ln( < 1, proving the first part of the lemma.
Next note that
1toxp(-11;00 1
((-1x;3)) In(1 + (x,(-11,,31))
1 dt
1 dt exp((-1x,8)).
Using that In(t)= & |t| for all t 0 we conclude that
{( (1-1x,)))a & exp(In((a;;))) [x,,3]) S c
Now combining everything we get that
26(- [r, + ((-12;;31) 2 12 33
Next we note that the optimal value of f(X is bounded from below:
Lemma B.2. (Munteanu et al. 2021 For all B E Rd it holds that nf(XB) 2 nfi(X3) >
(1 + In(n)) = Ω ( (I(4m(
2p
We use the previous two lemmas to show that our sketch approximates the given parts of f well enough with high probability. To this end, we set 91 (t) ((-1t)). g2(() 28(-1t + ((-12t)) and g() = (t) + Atz(t).
Lemma B.3. Given any 8 E Rd with failure probability at most exp( (xxp(-m1) the event En holds that
wrg(d Σ g(x;3) S max Σ g(x:3)
2p <c(())).
Proof of Lemma B.3
The total weight of all buckets in a level less than hm is at most Aiman b
b-1 1-b hmax 1-b-1
6p Now let k (1,2)- For [n], consider the random variable X; = (x,))) z; at level km. and X; = 0 otherwise. Then we have
E
E
X
(2))(2x) Pu Σ (rr8))
Further we have X; < by Lemma B.I
holds that
E
Σ
x?
Pagk (2,) 2 S Pa
3g(x,3) 3E.
We set
L = Pa max Σ gu (a,8),
2 E.
21
By Assumption
A.1
we have that Pu
>
64pm; e"n
Thus, using Bernstein's inequality we get that
LE2L2/8
e.
X;
E
2
S exp
2
3E +
1=1
14

---

Published as a conference paper at ICLR 2023
E
exp
32
E2 Pun/
S exp
64
S exp( (mm]).
Using the union bound for k = 1 and ls = 2 yields that
n
P
Σ ((2388)
max
Σ g((r))
S 2 2exp(-mi)
241
By Lemma B.2 we have ((X3) 2 n. It also holds that f(X3) 2 Ei= g(x:3). We thus conclude
2/
that E max Ex=1 0(x;8), 2a S 3
C ESTIMATING THE LARGE PARTS ||2||1 AND || 111
Lemma C.I. It holds that Eneqr [ 2 (1 -=2=||=+111 ||1-
Proof of Lemma
C.1 First note that
Σ 2,<2-00
24 Sn n
E/(H + 1). (x+t)am
(u 1)m
Second note that) Egsam 2g QEQ || I|1
S qm
S _ + 1). By the p-condition we have
that || 1 $ /||2+11 11 and thus we get that
|| + ||| $1 $11= + +||2*11a Consequently,
|| 2 141 and EgEq- [W lla 2 || 1|a
2
2 (1 2x) 2 111
(x+1)
C.I ANALYSIS FOR A SINGLE LEVEL
Fix h E [0, N. First consider the number of elements at a fixed level h. We can view it as a binomial random variable with parameters n and Ph since the probability for any row to appear level is
Pa. Since we fix h in this subsection, we set M Mn. PAR, Ph M and N No. We set
Eg |ail
U C [n] to be the set of elements that are sampled at level h. We also set μ En,3 |.l S p.
This and the following subsection are dedicated to proving the existence of bounds qu (1), qu (2). qu (3) and gr. (4) as described in the high level overview, Section More precisely we show the following:
Lemma C.2. With probability at least 1 - 6__ the weight classes W for q 2 (4) _== 2N In(N In(N and S (1) logz( phinae have zero contribution
1og2(12 1) == loga(
pe
to En GB)), Le., for any bucket B we have ExYB,, 2s S where I, = (i [m] 2, Wa. E (IM,N)(1), (1), Further, with failure probability at most cxp(-I(m))) there
exists, for each log2( 89mpt )) =: ((M,N) (2) S $ S (MMNN) == logg Ne²), a set W such that cxp
Eiew; G(B,) 2 (1 (1 M. It thus holds that
Mgmmihh
(2).)( (1) = logg
e38
N
(3) (2) = logg
log2(1)
32m1
81n(NNbm/00
(4) (3) = logg
g
If N- M then we set (3) (4) 00. If M n then we set (1)
(2) = O. We set (i) ((Ma.N))(1) for
(1,2,3,4 4) and Qn (2n(2), qn (3) to be the
15

---

Published as a conference paper at ICLR 2023
well-approximated weight classes, and R, [9x,()), (1)) to be the relevant weight classes at level h.
We further define the following threshold and set:
71 3m1
V == {i E [n] | 2 m
Here Y1 is the 'set of large elements'. We set By to be the set of all buckets at level h. Recall that my IK is lower bound the negative logarithm of the failure probability, which will need later when union bounding over all failure probabilities. Also recall that G(B) = ΣieB 2 is the sum of all rows a bucket B. The following lemma yields the inner bounds, i.e., bounds for qu (2) and gu (3), which are the weight class indices that are well represented by U. The first two items show that there are at most eN buckets at level / that either contain large element or have large sum of small contributions. The third item shows that if W,, has sufficiently many elements, then there exists large subset W where each element is in a bucket with no other large entry such that [[W; la is close |[W [1 M The fourth item shows that Ex,w; G(B,) is close to [[ I|1. "
Lemma C.3. The following hold:
1) MYnUI eN/2 with failure probability at most exp(-ma)
Then (B] 2 (1 - N) with failure probability 2) Let B = ( E Ba EiEBi 1z, Ax)
at most exp( m11):
3) Assume that q 2 logz( 8a and that W important or [W 2 8m1E 2 p=! Etp
Then with failure probability most exp(-m1) there exists W C. W n B such that [Wa 2 (1 (1- (| p and each element of W is in a bucket in B containing no other element Y1:
q
4) Ifq S logg( holds that Liew; G(B,) 2 (1 e)IlW
Ne² 4p
and W as in 3) exists, then with failure probability at most exp(- oxp(-m1)
Proof. 1) Note that |Yd] S since |||||1 1 and that view ( NU] binomial random variable with parameters |Y] and p M Thus, the expected number of elements of Y1 at level h is bounded by |Yil-
3m1 s since >
12m1 (see Assumption A.1 Thus, we get by
Lemma A.3 that
eN\
< P K P <. < P(KNU |X1 3m1)
Y 12 P
2
< exp exp(-3mmm (-3m1/3) < exp( -m
2) For E E T | Y1 we set X; = | i E U and X; = 0 otherwise. Since Eigr |z2| S ||=||| = 1
we have that IE ((EiTT X₂) = p- Σver | I p. Since all 'large elements' are in Y1 we have that X, < m for all E [n] and thus
Σ
< Σ
prllil = Pm pn Σ
|z|| S pm1.
GET
NET
SET
NET
Using Bernstein's inequality get
P
Σx:
Σ
2p
< exp
p²/2 pn//3
S exp
(-P P (-37)
-ep((mm)
pn +
This implies that Eier X, < 2p with failure probability at most exp(-m)) Now if ΣieT X; $ 2p then there can be most 2/2
NN
buckets B with G(B Yi) 2 4.
16

---

Published as a conference paper at ICLR 2023
3) First note that if q 2 logz( (8 (1 is important then 2 1 2 | q..... which =pp
9nH, 2 8m1==2 .pp.. Assume that all entries of Y1 \ W have been assigned and let B' be the buckets of B with no elements from Yi \ W. By 1) and 2) there are least N) buckets in B'. For 2, E W consider the random variable that takes the value Z, = 2, otherwise. Set Z Ex,ew, Zz We have Z- = 2; if element is sampled at level and sent to a bucket in B', which happens with probability at least p We thus have for the expected value of Z that
implies that | 2 2"
i UBE B and Z,
(1-9)N
N = (1 E)p.
B()) 2 (1 - s)p 1 1I 2 (1 s)p 2pp-2-91..10 - 2 (1 e) 2- 8m1s=
2 -3m1E
Further, the maximum value of any Z; is 2 and the probability that Zi 2₁ is upper bounded by Consequently, the variance of is bounded by
Σ B(Z
S
Σ A,EWT
pzd 22
Σ
pa: 2 (Z).
NEWT
2,W,,
Using Bernstein's inequality we get that
P(Z < (1- I1w s P(Z E(Z) > =B(Z))
B22222222
exp
2 (-) 2 +2-
-EP
exp
3-2
< exp (-m1).
We set W = {2; E W Z, = =
4) By 2) and 3) we have that any entry 2 W is a bucket B with Eje layl s 2. Thus,
4p we have for 2 N
that EjeB, 23 2 4p 2 (1 5)2ç. Now we conclude
Σ G(B,) Σ (1 -) = W1
KW
iE
Note that if all buckets contain only a single element then we can remove the condition S logz( Ne²) Hence, we can set NJ (3) = g(M.N) (4) oc if N = -M (respectively, h = hm)).
4p
For the outer bounds, i.e., the borders of the interval of weight classes that can have non-negligible contribution to U, we need the following parameters defining the set of small elements:
pEa
72 = 3N Nax 0)
Y2 = (i E [n]
|2,|| < 72)
We further set E to be the expected value of an entry chosen uniformly at random from Yg.
Lemma C.4. The following hold:
1) E < -e/n, then for any bucket B that contains only elements of Y2, we have G(B)
Eien nen"* 2i 0 with failure probability at most 8
Nhmaee
2) U contains no element with 2, 2 phaase withfailum probability most
u.d Tynax
Proof. 1) First consider a single bucket B containing only elements of Yz. For E [n], let X, be random variable that attains the value X, = 2; if B and X; 0 otherwise. The expected value
17

---

Published as a conference paper at ICLR 2023
of G(B) EiE(n) X
E'
:=
E
N- Further, we have that
E
Σ
x?
Σ KEY2
|2 = 72
N
N
VEln
since all X; are bounded by 72 by assumption. Thus, applying Bernstein's inequality yields
-1211//2 12 K + 72 12 E'1/3
P(G(B)> > 0) P
Σ
X; - F 21
S exp
iE(n)
- D/(N)
S exp
272(p/ 272(p/ + 1/3)
E pppP/(())
S exp
272(5 1 + 1/3)
pP(NN)
S exp
372
Nmmax 8
S exp
N Nhmax
2) Recall that Σx>0 24 S 1/pz- Thus, there are at most
entries with 2, 2 M Magas The
expected number of those entries in U is thus at most the probability of at least one entry with z;
Tmaxx which also upper bounds being contained in U.
Mhama 7
Afeaa
nd
Putting both lemmas together get all bounds gn (i) except (2),, which will be handled in the next subsection.
C.2 HEAVY HITTERS
In this subsection we will analyze the level containing all entries. Our goal is to show that we indeed set (2) 0 in Lemma C.2 Let U be before and assume that M Let
Qn = {q E Qo [Wal 2 8m) where Qo {q S logz( Aimiim (mm1)) }}. We set H Ugequ W, to be the class of heavy hitters.
u E Rg denote the vector whose coordinates u, denote the i-th fi-leverage scores, i.e., [r.9]
Ue max Eye(J [",
Lemma C.5. (Munteanu et al. 2021 If u; the k-th largest coordinate of u, then for z in the subspace spanned by the columns of X it holds that [zyl S El|z|12. Further, it holds that Σi= Us S d.
5² Lemma C.6. Let Y3 l 2 73) and Nı YYs where 73 8amums Further, for j Ys let C, = (B) EiEBIO us 2 eyst. Then for all j E Y3 we have that (Cy) bounded by
N₂ = d(eys)-1. Further if N 2 N2N-811 for E (0, then with probability 1 - 2k, each
member of Y3 is in a bucket in Bo NC
Proof. Since by Lemma C.5 it holds that Σ U; S d, there can be at most d mra N₂ buckets B with ELEB "; 2 e"13 In particular this implies that |C,1 < N2. The probability of any element of j E Y3 getting assigned
bucket in Cj is at most N < A. Using union bound the probability that any clement j E Yg is assigned to a bucket in B, \ C, is at most K.
We apply Lemma C.6 with x = 6. We denote by E, the event that all coordinates in j E Yg are in bucket in Bn C-- By Lemma C..ma|C.6 & holds with probability least o for an appropriate
18

---

Published as a conference paper at ICLR 2023
N No N2 51d thus by Lemma C.5 we have E Y3. It remains to show that the remaining entries in the buckets containing heavy hitter only have a small contribution.
O d' de'
d L For any entry 2; E we have 2; 2 73 and
Lemma C.7. Assume & holds. Then for any 2; E we have G(B,) 2 (1 8)
Proof. Let 2, H. Note that by Lemma C.5
Y3. By we have that Σ 4j S EYS S E2
We conclude that
G(B,) 2
1 Es12
Σ
Σ
2 EZi 2 -))
JEBA()
JEBA(
C.3
CONTRACTION BOUNDS FOR SINGLE POINT
We set Un. to be the rows 2; sampled at level h. Combining previous subsections we get the following lemma:
Lemma C.8. Assume that & holds. Denote by 2 the i-th row of S n'. Then with failure probability at most (2hm + 2mm hmm it holds that
Σ
wirk 2 (1-43)[(X8)1In
KEW kEW
Proof. By Lemma
C.3
and Lemma
C.7
we have that for each important weight class W there exists I lI For E QH we can set W 4
subset W C Un with
lww G(B,)
W
Then using Lemma
C.T
we get
W44
Σ Ph Σ G(B,)
i(20
9EQ*
iEW;
2 Σ (1 E) w,;
9EQ*
2 (1 - 21 - +> 2 (x)=)))(
C.4 DILATION BOUNDS
Given 3 Rd and X3 set Z, Zo(3) 2 (.1,..., 2n to be the set of the (1- largest entries ordered by absolute value. In other words, we remove the En smallest entries. Similarly we set Z1 (B) C be the set of the (1- 22)n largest entries. Again we assume that ||=||| Our next goal is to show that if (() is small then >x, remains negative even if we remove the smallest entries. Here small means negative with large absolute value. This shows that the assumption of Lemma C.4 1) is fulfilled.
Lemma C.9. f(X < (1 10-22 20) then it holds that
Σ
2 (1 +
Σ 2,20
ad
2, 2,E 2.E2,. <0
entry of Zn removed. We denote by f the function f restricted |Zi| entries, i.e., f(X Ex,ex, ((x;8). Since l is always larger than 0, removing 2en entries can only reduce f. We thus have that
Proof. Let X, denote the matrix X where the columns corresponding
f(0) (1 22) > f(XB) f(Z) > f(Zz).
Now consider the function d(r) = f(r -x)). Note that the derivative of Φ at zero is given by d
o' (0) Σx,xx कमा 3z3 Σx,ez, 2,. Since f is convex also convex. In particular this
19

---

Published as a conference paper at ICLR 2023
means that f(X f() implies d0()) O. Thus it must hold that Σ,, 2,,22, < 0, equivalently,
EneZ |zc| >
Σ 2, e, .2,30 |2//. Since all entries in Zo 11 less than equal any entry
in Zo. we have that
Σ
a 2 (1++)
Σ |zd|-
2, <0
4=0
The following lemma gives us an upper bound on the expected value of G G*).
Lemma C.10. for all S hm - it holds that q(M,N.) (4) < Ne4a)N and No 2 No, then the expected contribution of any weight class W is at most k- [
Proof. Consider any weight class W For any level h it follows by Lemma C.2 that if q [9(,, N.) (1), N.,,, (4)] then W has zero contribution at level h, i.e. either there are no elements of W level h or we have W C Y2 and for any bucket B of level h it holds that Eigrin 2 S At any level the expected contribution of W is bounded by Ph Eiew! Ph = || 11. This upper bound would be tight if all entries of were positive. Hence, the expected contribution of W upper bounded by the number of levels with q E (1),, (1), (CM.NN)) Since ((M.N (1)
and ([M.NN (4) are monotonically increasing in h, it follows that if ((M.Na(4)) (MM++N (1)
then any q be contained in at most k intervals of the form [M(M, No) (1); N.) (4)), concluding the lemma. See Figure 2 for an illustration.
If the green and the blue block do not tonch i.c. if (d- (3)a(3).
then the expected coatrbution of wiight class moot twine Its original contribuion.
Figure 2: Illustration of Lemma C.10 and Lemma C.I1
Lemma C.10 can be used to show that the expected contribution of any weight class to G+ (Z) is at most twice its total weight:
Lemma C.11. If we choose N, N max NN; 2018m y In( NN(N /8)m Kmm for all i [hm]] and
g-2g M; solving the equation 9(M..1,)) (3) ((M..N) (2) then the expected contribution of any weight class W is at most W 111-
Proof. We set (5) = N.M,N.) (z). We first show that ((++)((1) (:) can be expressed using the terms q:+1(3) (3) q++1 (2), (2) - (+))(1)) and (4)(4) - (3)), which are the same for each i if the number of buckets each level identical, i.e., for all S hgg holds that N, N,. Observe that
(1+2)(1) (4) g:+2 (2) 9-2((1) (2)((2 - (9:(3) + g4( (3))
(:)2 (3) (2)+((2) (1)2 (4:(4) (3))
q:+1 (3) (2) (2)+((2) (1+ (q.(4) q. (3))
Figure 2 iillustrate those three terms. Using Lemma C.2 we can bound the sum of the two subtracted terms by
88m e38
8 Inn( (In(NNir Nom
(2)+((2) - (1)) + (q:(4) - (3() = logg
+ loga
e
64mm In(Nhm 18) 88)mmmmm
loga
E78
20

---

Published as a conference paper at ICLR 2023
By Lemma C.2 we have that 9b+1(3) 94+1 (2) 2 loga
Ne
Thus, combining both equations
32m p4m
get that
Ne
64m In( ( qra
((++2) (1) (4))) logg
log2
32m 1M
676
No
logz
2048m (Nhm 1 am hm
If N 2 2048m N /6)9 2m Aim then we have ((++))(1) (4) 2 0 and thus by Lemma C.10 the
e128 expected contribution of any weight class W is at most 2 2 111-
N 2048m Inf Nhm /6)g Am we have the following adaptation the lemma:
1/(k-1)
Lemma C.12. for some & E N we choose N, = N 2 32m (64m, In(NNm Nom 1 18 Pom.
6
for all i E [hm],, and M; solving the equation ((M,,I.N) = (2), then the expected contribution of any weight class W is at most &|IW:l1.
Proof. We generalize the proof of Lemma C.11 We can substitute g(++k)) (1) (:(4) as follows:
((++) q:(4)= = ((i+x) (1) (2) (3) (4) + ((1+)) (2) (2)- (3)
= q(i+t) (2) - (3(3 (1(+t)) (()+) (4((4) (3)))
q(i+k-1) (3) (1+1(22) (2)++)((2 (()+) (a((4) (3))
k-1
A(+t)) (3) - 9 (2) - (((++))(2) - 46- (1)) - (q:(4) - (3)).
The difference to the proof of Lemma C.11 is the telescoping sum. We have that
NE
loga (( 32m pdgm
N
Σ (3) (2) (k: 1) logg
32m y pmm
1/(k-1)
Thus if N p2m
64m3 In(Nhm, Mo(Nhhm/8)amkkl fmmm
we have that E ((++)) (2++((2)) 2
c/8
64m; In(Nhm 16)mmm
log2
Further note that (2++((2) 2:+2 (1)) (g:(4) (3)) -log2 641m, In(N 1 (8) Nem
before.
8
We conclude that (((+)) (1) - (4) > 0. Consequently, applying Lemma C.10 finishes the proof. O
Next we want to show how we can reduce the expected contribution of all weight classes below 2| 112. To this end we first increase the number of buckets at each level so as to get
N
la loga (64m, In(N (8)
loga
>
12mppqm
e²8
Note that the expected contribution any important weight class W+ is at least ||W*+ I| Moreover, the above choice ensures that all but a k-th fraction of weight classes have expected contribution of exactly | I|a, and only the remaining k-th fraction has a larger expected contribution that crucially is still bounded by 2 11 Then the last step is to add random shift so that the probability of each weight class W+ for having an expected contribution of 2 W 1 is at most
4. To simplify notation we set N = 32m, p9m and N2 64m; In(n]qm. and assume that 2 A hm/6. cb
27
Lemma C.13. Let y = for some K E N. Assume that No is chosen uniformly at random from - for any i > 0. Then
NO). ..... NO/>) N(//) where N = N2 N Further let N; N = N N1k+1 the expected contribution of any weight class W+ is at most (1 +>]l
21

---

Published as a conference paper at ICLR 2023
Proof. First note that
Ne
log2
log2
loogg(//// - loge (Ng*) 2
32m1 pugm
855
This shows that the relation of weight classes that are relevant on two levels to the weight classes that are relevant on only one level which is the maximal length of a block [g)- qs (4)]. Hence, for each E N there can be only one i such that g relevant two levels. This implies that the expected contribution W is at most R-1
k. By choosing Ny at random we introduce shift by i logg 1ogg([V2 (N2)).
|
W = (1 I
C.5 NET ARGUMENTT
To get a weak weighted sketch we need the contraction bounds not just for single solution but for all / E IRd. For now we ignore the variance regularization and focus only on /ı, i.e. on plain logistic regression. We first show that if the distance of two vectors v, v' R is small then (f(()) (v() is also small.
Lemma C.14. For any e' E R" with |/ r'Il1 S E it holds that (fi(e) - f((')) s..
Proof. Since (v)
c" +1 we get that
(f(()) -i Σ (e(us) E(v\) Σ In vll ||u v
which proves the lemma.
Lemma C.15. Assume that for 3 E Rd it holds that (X' -1 S Then any 3r E Rd
with XX 1|| < e/thm hm) it holds that (X(33') (1(X3)) 3e.
X/
Proof. It holds that (B = - |
8hm [ (B11 S E since for each
i E [n] there are at most hm columns j such that Si * 0 and each entry of S is bounded by a
Thus, using the triangle inequality and applying Lemma C. yields
(x(()') - fi & - f((x)) + (x(X'))))))))))))))))) ((x3) + (((X)) - (xx3)
Lemma C.16. There exists a net N C Rd
of size [W = exp (O (n())))) such that for any point
y E Rd with |Xyll nu there exists point E N such that \| Xyyl11 S
phrmmax hmm
Proof. We set
N= { -= ===v-- v
druubhamen hm
2d with |/u||oo
(6)
db hm
Then for any E IR with ||xyll S nu the point Xy abfio frm.
Xyl
is in N and
abd hi
(d d''nub h2n
it holds that [Xy Xyll1 s d ab Nm exp (O(dn(nn).
Further we have IN I
bam Bon.
L
Combining Lemma C.15 and Lemma C.16 we get:
Lemma C.17. There exists net N Id with |N| exp (OdIn(n))) such that if (X'
(x < = holds for any 3 E N, then for any 3' E Id with | & nu it holds that (X'())) ((X3')) 3e.
22

---

Published as a conference paper at ICLR 2023
C.6 CONSTANT FACTOR APPROXIMATION CHANGES
To prove the first part Theorem 2 we need one more tweak in level O. Since we only aim to achieve constant factor approximation with constant probability we can assume that and ò are constant.
Heavy hitters alternative version
There is another way of handling heavy hitters. Using it we reduce the sketch size at the cost of running time. The idea is that each row gets sampled multiple times. More precisely, we replace level 0 by the following sketch: At level 0 we map each element to 8m/9m/4/ rows. Technically are getting rid of heavy hitters this way. To compensate the fact that each element appears multiples times, we the weight of buckets of level wp 1/8.
C.7 PROOF OF THEOREM 2
We are now ready to prove Theorem
Proof of Theorem 2 If B = as 1 2. approximation, then we get the dilation bounds for free
since (X' ln( = (x Otherwise let 3 be the minimizer of (X Note that 3
satisfies the assumption of Lemma C.9
1) We constants 1/8 and 1/8.
We use the alternative approach for handling heavy hitters and define M; and N; as in Lemma C.12 for some constant 1: 1 and set hm = min (1 M; S N).
9 By Lemma C.12 the expected contribution of any weight class is most ks| & 1|1. Thus using
Markov's ' inequality we can bound f1 & (X with probability for any a E N. In other words, it is constant with constant probability. By our choice of M, and Ng the contraction bounds hold for any X33 with failure probability at most (2hm + 2gm + 2 by combining Lemma C.8 and Lemma B.3 Setting mi (n)))()) and using Lemma C.17 we get that the contraction bounds hold for all S Rd with @| < nus. We note that the contraction bounds can be extended to any Fd since fx( || |X > np. We refer to (Munteanu et al. 2021) for details. Further note that (2) < (3).. and thus hm I logg (2 (In(z)). The number of buckets each level is N 32m1 agm... (6am; ln( N N0hm/50mm.... Am )s. We specify the number (1/8)*
(1/8)*
r of rows of SX, which is r = N. Since hm 4m = (ln(n)) and m. = (dln(n)) we get that
r = =O(ud++ In(n) (2))))))). The running time of our algorithm is Opud (nnn)n(nnnn (n(n)nnn(()) since each row
x; gets assigned to (pd (n))) buckets.
2¹) Before proving the second part we show that with O(" at In(n)" and T Onnzz(X)) we e12
can get an approximation factor a = 1+ (1+ + z)a and failure probability of P = 8 + 1 There are only few differences compared to the proof of the first part: instead of Lemma C.12 we use Lemma
Hence we need the number of buckets to be
N = max No 2048m3 In (N hmm (0) hm
2048m2 (uNhm)) 18) hm
g128
g128
Consequently have that r N . O " "nf""" Since every row gets assigned to O(1) buckets the running time is O(nnz(X)). Now assume that the contraction bound holds for 9*. Then Y fi (SXB8)) (1 (Xf33 is positive random variable with expected value at most (1 eXf(( and thus using Markov's inequality gives us that Y > a(1 + +) (X33*) holds a. Hence it follows that Si.. (SX3*) & (x(33) + a(1 +x)f(( with failure probability at most
with probability most !
2) The proof is again similar to 2'). The only difference is that we use Lemma C.13 instead of Lemma
C.I1 Hence the number of buckets at each level bounded by N max(Ng Ní- -N Thus
0( d Am 2 zmm? 32du In(n)² (nn)) 1+t
hm N
23

---

Published as a conference paper at ICLR 2023
D APPROXIMATING ||X - -
The sketching algorithm the same as before and also the analysis very similar to the previous part. We start with fixed point (X,-Y) where 3' (3, E R' and analyze Sz. Again assume that ||=||| = 1. Instead of weight classes W we use weight classes W, = {i E [n] | E ( ). Since we are only dealing with absolute values, which are symmetric, we no longer need to parameterize by ns. We continue when setting μ in those bounds to be 1. We will only slightly change 9% (3) since we will need another trick prove the second outer bound g (4).
the same definitions for (n(1), qh (2) and 2h (3)
D.1 DILATION BOUNDS FOR &
For approximating & we need different approach for qu (4) when bounding the contribution of small entries each level. The idea is use a Ky-Fan norm argument remove the smallest contributions from the { fnorrm. At fixed level h we put B, to be the set of buckets at level h and B3, to be the set of buckets with the p2 I NN largest entries with respect to |G(B] where
hm
qr,(3) (3) == In(mnn eN N=² }). We further define
2hm
(hh)=
Σ G(B)
BEB
Since Upe(a, (2).1%, (3) Wi contains most p29. (3) elements, have that K(h) 2 [ Will: Cp Nu }.
We
d (4) = In( 3Nhm in Nhmn/ Set Y2 = Y2(h) = (i [n] | 72 == N 5
Lemma D.1. With failure probability most T.. it holds that for any bucket B at level h we have
that
Σ BEB
1xi & max
P. |22ll (irall)
+ -
N N
hmm
Proof. Fix a bucket B at level h. For i Y2 let X; = if B and X; 0 otherwise. Then have E. B(Eiey, X2) 211lh Further we have E(Eier, X?) Eier, & . S
Pap Eiey, |Za E. We set max(E, (E,
E
Then using Bernstein's 's inequality get that
Nhm
22/22 E2E + E/3
P( x; ) 2) Sxxp
KEY
-22/2
S exp
72 72A/3
< exp
372
PE
S <exp
3N
8
< exp (- (1)) 5
N
Lemma D.2. With failure probability at most â it holds that
Σ
Σ
S
Proof. Using the union bound over the event from Lemma D.I over all Nhm buckets, using that
|B, S /2/2 and max(2 ||2211,, (1Yall
2 get that
Trm
Σ
eN
2p
< 8
S
2hm N
hm
KEY:(NUUBCE))
B
24

---

Published as a conference paper at ICLR 2023
holds for every level h with failure probability at most 8. Summing up over all levels get Eneh.. Ueer, 2 S E.
We have the following lemmas using similar proofs as in the previous section:
Lemma D.3. for some k E N we choose N;- = N 2 eu
32m
(64m, In(N 181gmm ii
1/(k-1)
208
for all i [lmm] and M, solving the equation 91A5_11,,) = Q(M,.N)) then the expected contribution of any weight class Wg is at most (I: + +
Here the additional comes from Lemma D.I
We set No = No- NY 32 Bm and No¹
Gimm In(NNon /5)gm km and assume that n 2 h / Ea8
Lemma D.4. Let 7 = < for some k E N. Assume that No is chosen uniformly at random from N(), N(1/>) where N No No Further let N; N = No No for any i > O. Then
the expected contribution of any weight class Wg is at most (1 w)
D.2 NET ARGUMENT
For B RR++1 set 9n (B) = 1I(, -Y)3 and 92(3) || 35
Lemma D.5. Assume that for 3 E IR it holds that |nn (3) 92()) S e. Then for any 3' e Ied
with [ X 8 111 S e/(h/m hmm) it holds that 191 (8') (2( S 3e.
Proof. It holds that | 8)1l ||X - 81)l Vmm hm | - 8111 S 8 since for each i E [n] there are at most Am columns j such that Sig # 0 and each entry of S is bounded by ddm..
Also note that (v) - g (v')ll Il1 S || - o'll1 holds for any two vectors u, o' E Rd+11 Thus, using
the triangle inequality yields
1g1 (B') < (32) g2 + (g) 91 (0)1 + (1) (3')
Seta + S 3E.
Lemma D.6. There exists net N C. Rd with [N] exp (O( such that if [1 92 { (B) holds for any B E N then for any 3' E Id++1 it holds that 1gr (3") 92(3')) S 35g (3").
Proof. We set
N { 8=
db hm | E zd with ||u||oo S
6
Then holds that for any 3 E Rd+1 with Φ1 (3) the point (X,-
dl Rrm
(X, 3)
db3-m is in N and it holds that II(x, - 3) 1| S d. ag hmm Blmmmmm
Usiin Lemma D.5 it holds
2d
that 1 (B') (2(()) - 3s < 38g1 (5). Further we have WI S
(dbhim tem
exp (dd(((())()))
Now for any r e Et and 9 e Id+ with 91 (3) 1 we have that (91(1 g2(rB)] = (8)1 (3)( = r|g (B) (B) < 3er.
E SKETCHING VARIANCE-BASED REGULARIZED LOGISTIC REGRESSION
In this section we show that our algorithm also approximates the variance well under the assumption that roughly (X S (2).. We stress that this assumption does not rule out the existence of good approximations. Indeed, even the minimizer is contained as observed in the preliminaries, since we have that minger 3(x < (0)
(0) = In(2). Again we focus on single = X
first. What remains to show is that Σiaso =? is approximated well. We set H(2) = Σm_ 2?
(x) = E Eie 2 and k(y) = H (E). By μ-complexity we get that Hx)x) 2 H[z) We define w2 (i e mn] h(2)) (2-9-1,2") and W; {i |m]
y²
- (2-9-1, 1,12. As the argument
25

---

Published as a conference paper at ICLR 2023
is almost the same in the section before, we will only note the differences. We will also the same definition of importance, i.e., a weight class W2 is important H (W2) 2 qmm Similar
to the previous analysis we have that if W2 important then |W?1 2 9mp With those adapted definitions we proceed by adapting the main lemmas of Section [that finally yield Theorem 3
Lemma E.1. For any E W there exists of S (q 1)/2 In(n)/2 such that W7.
Proof. It well known that ||=||| S 21222
We conclude that
2 (a- 2-
|=||
vn 1=
2
ni
Now taking the logarithm proves the lemma.
Contraction bounds Recall that:
'1 3m1
Y1 = {i E [n|] |2: 2 7
Ex,50 of
Here Yi is the set of 'large elements'. We redefine
Ex,e0 2/
Lemma E.2. The following hold:
1) VInU eN/2 with failure probability most exp(-m:1)
1p Then [B| 2 (1 - s/2)N with failure probability 2) Let B = {B BR EieByn 1 at most exp(- mx)(
3) Assume that q 2 logz( ( ) )) and that W is important or that [Wal 2 8m118 pp
Then with failure probability at most exp(-m1) there exists W C W n B such that [Wa Il 2 - other element Yi;
(1 e)
p and each element of W is in a bucket in B containing no
4) Ifg S logg(
q as in 3) exists, then with failure probubility at most exp(- -m1) it holds that Liew: G(B.) 2 (1 e)IlW?
2
and
/ripp
The proof is verbatim the proof of Lemma C33 For the 4th part we use Lemma to reduce the
problem to the weight class W This causes an additional term of 1 in the logarithm of (s,M, N).
v
We also have a change in (M, N). More precisely we need two additional factors of E in 72:
M
= 2n In(NnnnNn (MNNaaxx
Y2 = fi E [n]
| I 12}: Set of small elements;
Y²t {i E [n]
|zi| < 72, z. S 0}: Set of small negative elements;
Y = {i E [n]
2/ < 72. 2 0}: Set of small positive elements;
Further we set A Ex.20 Zis A' Ex,e, |z,|, A1 = [zi| and A2 = A 2
Lemma E.3. Af > A(1 + E) then for any bucket B that contains only elements of Y2 we have that M.
G(B) Σie S Nn (- A2) with failure probability at most Nhans
Proof. Let X; be the random variable attaining value 2; if E B and 0 otherwise, for i [n]. The expected value for G(B) Exe(n) X; is E'
M
(A'
A1). Further have that
AN
M
M
724 < M
E
x?)
<
Σ
nN
nN
nN
RE
m
1EY2
KYY2
26

---

Published as a conference paper at ICLR 2023
since all X, are bounded by 72 by assumption. Applying Bernstein's 's inequality thus yields
-Ea ///121/2
P(G(B)> >) P
Σ
E' 2 2
exp
7/2 (2.M/(NN) E72 131/33
1e(m]
- (/N21/22
exp
72(M/ + +E/3)
M/(nN)/2
exp
725 '(A' A1) + 1133)
MM(nN)
exp
27/2
N N
exp
In
8
N Nhmax
Note that EE' Σ e.
(A' A1) se. WN
M
M A and thus |B(EE( X?) + eE' S
(-A'+
AN
nN
A1 + EA)
aN (-A2).
M
Our main lemma thus changes to:
A. the weight classes W for q 2 (4) Lemma E.4. With probability at least 1
log2( (152(72) = logz( 2N 2NNin(Nhmm88) and q S (1) log2( nd_ have zero contribution to ΣB (B),,, iee, for any bucket B we have EzEBy 24 I where I, = {i E [n] 2, e Further, with failure probability at most exp(-m1). for each Nne?
Me*
W.. E (1),,)())) ((MM (4))-
84mamin) =: (2) I I (3) = loga log2( (ndmiya)) there exists W such that loga( 6SM
Eiew; G(B,) 2 (1 [2= M. Thus holds that:
8qm m2 hm e
9(M,N) (2) - (1), = =log2
5
9(M,N) (3) (2) -log2
loga(b)
32m pM Vn
8 /8/R)
9(.N) (4) (3) 1log2
g
If N M then we set (3) (4) (2) = O. We set (1) 9(M, NN,, for (1,2,3, 4} and Q₁ (qn (2), qn (3) to be the well-approximated weight classes and Rs. [gn (1), (4)) to be the relevant weight classes at level h. Note that (1) and (2) stay the same as before.
If then
(1,,N(
(1)
Heavy hitters The important changes to note here are that we need to replace Lemma C.5 with an appropriate lemma for the Ez-leverage scores and there is an additional factor 1 in 74. We further redefine Up to be the lz-leverage scores.
vn.
Lemma E.S. (Clarkson & Woodruf] 2015a) If u; is the k-th largest ln-leverage score, then in the subspace spanned by the columns of holds that 2 < d Σ 23. Further holds that E U4 =
The lemma follows as in the case of é leverage scores by using an orthonormal basis.
We then apply Lemma C.6 and Lemma E.5 as before: set N, dr. and N₂ = dr. - where 7/ f0mm and 744 Vimi Further let Y; (resp. Y4) be the set of coordinates with the N₂ (resp. N₂. largest leverage scores. We denote by Eg the event that all coordinates in Yg are in a bucket with other member of Y4. By Lemma & holds with probability least 1 for appropriate
27

---

Published as a conference paper at ICLR 2023
= N N1 N26 O - For any entry 2p E H we have Ep 2 " and thus by Lemma C.5 we have p E Y3 and for any entry & Yı we have 2p "Y 74. It remains to show that the remaining entries the buckets containing a heavy hitter only have a small contribution. To this end we use Bernstein's inequality. For coordinate p [n] we denote by Bp the bucket at level 0 that contains p.
de'
Lemma E.6. Assume & holds. Then for any 2i E we have G(B,) 2 (1 E)22.
Contraction bounds for single point
Lemma E.7. Assume that Eg holds. Denote by z the i-th row of SXB for i E n'. Then with failure probability most (2hm + 2mm)e mh holds that
w 2 (1 (1-)))
VER 200
Here the constant before the increases for the following reason: assume that for some 2; >> 0 have || 2 (1 -3 then it holds that BB 2 (1- 6z)
Dilation bounds Here we have to cope with the additional factor of vn. Recall that we choose M, solving the equation ILM, (,,, Ny) (2) then it holds that
((++)) (4) q:+1 (3) (2) (#++(22) (1)2(1)) (q:(4) (3)).
We now have
Ne
91+1(3) (++1(2) = looge
32 /rmmmmgmmm
and
64m,, In In(Nhm/ (mmm
(2)+((2) - (++((1) (9:(4) - (3)) loga
Vn
Further there is a change in Lemma as we have to deal with possible overhead coming from the square function. We set R {i|2 24 (1) 2, > 2 gu (4) to be the set relevant (positive) elements and WR {2 i R).
Lemma E.8. -E=1 2i 00 and for all i < hm - 1 it holds that (4) < 9(Ma (14 and No 2 N₁, then the expected contribution of any weight class Yi is at most k [|
Proof. Fix a level h and a bucket B at level h. Recall that ΣIER 2i S A2 = A A1 =
Ex v4(4) 2,. Note that by Lemma E.3 we have that EierinB I pa(-Az) Let Z, be the random variable where Z, = 2; if E R is assigned to B and 0 otherwise. Then the expected value
N
of Z ma Σm_ Z is N Ag. Thus it holds that
max(2 Pn( (m) Ab)y3) 3²)
([mmax(((B)))))) SE
(max(2 2 -(())²)
Var(Z) - ||Rll
Lemma C.II and Lemma C.12 can be adapted as follows:
Lemma E.9. we choose N; N ( y82gmimmn 0.75 for all E [/mm]] and M; solving
the equation ((M (3) = (2) then the expected contribution of any weight class W is at
most W|l,-
Proof. The proof uses different idea as before: since N large enough, we only need 2 levels.
More precisely want to achieve M2 N. By our choice of M2 this means
8qmjm118 = ((N.N) (2) ((n,N) (3) = logg
Nne²
loga
3
4m
28

---

Published as a conference paper at ICLR 2023
equivalently
N 32qm umm
32qm 0.75
22.
Lemma E.10. for some k N we choose N, 32m 32mn1ugm u (6âm) Infa)) bm vu 1/(k-1)
for
all i E [Rmm] and Mr solving the equation ((M.1..))33) = N),, then the expected contribution of any weight class Wg is at most k k|[
The proof is the same as for Lemma C.12
Net Argument
Lemma E.11. For any v. d' E R with 1| 1/111 S E it holds that (fz(v) f2(0') S (fi(e) + E)E.
Proof. We have that (e)(x)
e²+l -((v) S f(v). Further since ((()) I 1 we have that for any [0, 1] holds that [e(v -1) {(v)] - (l(v) + t)e. Thus we get that
c"
1 le(2z)2 e(1)) [e((v) +c) (fi(u) +Ej
lf2(t) - f2(0')
which proves the lemma.
Lemma E. Assume that for 3 E Rd it holds that -2 S Then any 3r Rd
with XB X331 1|1 S e/(h hm) it holds that fx(33')) (2 1 : + 2(x
Proof. It holds that - = -=>_))==s=X((_-->>--00= 11) < 6 nm X - 81 S since for each
i E [n] there are at most hm columns j such that Si, * 0 and each entry of bounded by b Thus, by the triangle inequality and applying Lemma E. yields
12((8') - (2(X' BO) < 12((' -2 + - f2(X3))
< (Xi(' + +)eb Am + (fi + < 2(11
Combining Lemma C.16 and Lemma E.12 we get:
Lemma E.13. There exists net N Rd with [ exp (x))((n(())) such that if (f1((('' fi(x8) < E holds for any 8 E N then for any 8y Rd with [1 I np it holds that
(f2() fa(X33') S ((f((X,))) f1(
Proof of Theorem 3 The proof of Theorem 3 works the proof of Theorem 2 replacing the old lemmas with the new ones.
E LOWER BOUND
We note that the increased sketching dimension terms of /n comes from the inter norm inequality ||>||| S /n|larl|z and from more subtle details of the sketch. Lemma F. shows that there is no way to get around factor of /n using the CountMi n-sketch. The proof gives an example where /n attained even for obtaining superconstant (in μ1) approximation. It does not rule out the existence of some other method that allows lower sketching dimension. For example Count-sketch is known to work for & and & norms simultaneously within polylogarithmic size (Clarkson & Woodruff 2015a). But we stress that the standard sketches from the literature do not work for asymmetric functions since they confuse the signs of contributions leading to unbounded errors for our objective function or even for plain logistic regression, see (Munteanu et al. (02T).
Lemma 14 There exists a p-complex data example X where our sketch with of o(yn) rows fails to approximate f. Specifically, if X = it holds for the optimizer B E argminggas [(SX) B) that ((x wll((p)2) mingene f(X
29

---

Published as a conference paper at ICLR 2023
Proof. Fix μ > 10 and consider the following data
Zg = (v
1,n n
34 = (-1) for E
1
n fa
22 = (1) for i > n
As the example is 1-dimensional we only need to check the ratio for /3 = and 3 = -1 in order to compute μ as multiplying with a scalar does dot not change the ratio between the sum of all positive points and the sum of all negative points. Also note that the ratio is inverted for 3 = -1 thus if the ratio is positive for 3 = 1 we do not need to check it for 3 = -1. Note that for 3 = 1 and 2 = X
holds that Σx.0 2 /n j
and Σ 2, |2,|
n(1 1) /n + if is sufficiently large. We
thus have have
11 1 12
(x(
I =
vn +
n(1 1 R n. Consequently we Further we have that Σ2,00 2/ = n n 2 S 2n and Ex |2 get that
(2(X)= = n 22<
(1- #
Since d = 1 this proves that our our example is 2p1-oomlexx Note that the following four facts hold for any level h:
If for some we have that ph < 1/b then with probability 1/b row zo is not sampled at level h. In particular this implies that 3o only present level 0 with high probability, i.e.
probability at least Enm Ph S 3:
If no is in bucket with 3 2/11(11 3) elements then with high probability G(Bo)= s 0:
If Nu
< Ph < then with high probability G(B) < 0 for any bucket at level h since the
p-1 n negative elements cancel all positive rows;
If h = hm then roughly a=1 Nu are -1 and Nu are 1.
All of these follow from the Chernoff bounds using Lemma A.3 Thus if N, < vn/3 then X' = SX mimics the instance X {=o), i.e. the instance with point xp removed, as Zo is only appearing at level 0 where it is canceled by the other points. More precisely X' consists of roughly n' a
copies of the point -1 and n'' µ copies of the point 1. After multiplying with the weights we are back to roughly n at times the point -1 and times the point 1. To keep the presentation simple we only consider the instance X' = -XX {aro)). The proof works the same for other sketched instances that we obtain using the above facts. Consider the function
(X'r)')) = (n
7) ().(((())+))
1h 1
n ((r) = n (n.E(-r)+ nr
1
Thus, we have f((X')) ((-r) + E. Using that {(r) < r + f all r > 0 we get
"((X'r) (X'r)
(x [i(X')))2
Sn. (((-() + nr
n(r 1)2 /
n ") E( 2r-
+ (n
n(r + 1)2
snn 1( ((-r)
+ p
+
30

---

Published as a conference paper at ICLR 2023
Using that {(-r) S e it holds that
+r+1) 1)2 1
f(X'r) S 2e
+
Taking the derivative we get
((('r) S -2 + + 2(r + +1)
1
1
which is 0 if and only if r = - In ( + In(2) = 2((n(())) This implies that for F argmin,ex (Xrr we have that F (((n(1u)). Now consider our original loss function f(Xi).
Here we have that
nf(Xr) = nfi(Xr) + > - - fi(r)) 2 n +(-))+ nr + (vn.r))
1=1
2
In particular we have that ((x)) 2(In(u)9). However for r minimizing s(Xr) we have that nf((rr $ f() = (n( = 0(1..
31

---

Published as a conference paper at ICLR 2023
F ADDITIONAL EXPERIMENTAL RESULTS
Covertype
Wehspam
Kádcup. = 0
116
Shithh
Shetch rol0)
Skatpi
Skatte
Skitt0 Skoth02
1/0
SksthdD
1/0
100
Indiond Obe
indaced dis
Covertype, 0.1
Webspam, 0.1
Kddcup, 0.1
1.00
5.0
130
Skitch (14)
Skith ((k)
Sarthh (ok)
1/N-
Shattl
Skart
Soadd
Swertd
Stecchl
Stechh2
Sweth12
1o0-
1n0-
20003
200
reluond doe
inacedd dis
Covertype, 0.5
Webspam, 0.5
Kddcup, A= 0.5
1.10
100
Skerch (o40
Sterch (0k))
Sterch (ok)
Skeoic
Skethh
53
Suechh
Saert
Swertd
Skeriil
Sbech11
Swethi2
1oc-
1.0
10:00
15000
10000
1000
15.00
1500
55a00
20000 10300
Covertype,
Webspam,
Kódcup A
Skarch
Sterch
Slarch (ok))
1.17
Skird2
2,5
Sherd0
Slerch
Skitole
Shirdl
Skeadhd
SkotolD
Shezth22
Skadh02
2001
30000
15030
20000
2002
3000
T540
12300
15000
30000
13300
20.40
20000
30000
20300 40200
Synthetic data
Synthetic data
mew.reeeeeoo atto
Sketch (old)
Sketcc55
S1osc
1200
20.01
ondaned
20001
10:00
42:00
median
0.30
0:20
0.25
11:00
Figure 3: Comparison of the median approximation ratios of the old sketch versus the sketch with various settings for the sparsity E {2, 5, 10) as well as for the regularization parameter 10 5, }} for different real-world benchmark data (top, middle). Comparison of median approximation ratios (bottom left) and sketching times (bottom right) for our synthetic data.
32

---

Published as a conference paper at ICLR 2023
G ADDITIONAL MATERIAL
Comment on stochastic gradient descent (SGD) and supporting experiments SGD does not work in the turnstile data stream setting (where positive and negative updates are allowed), and is inherently sequential. In contrast, oblivious linear sketching allows for simple handling of turnstile data streams and distributed or parallel computations, which we motivate in our paper.
Our bounds are multiplicatiive error guarantees that are relative to the optimal loss f(X Known regret or generalization results for SGD bound the probability of misclassification P(y,z, < 0) E. which allows to ignore few highly important (and expensive) points and give an additive error on the BSGD)
loss [ - f(X (oPr)] S B. Here B depends on properties of f. X, and on the distance of
an initial guess 3o to the optimal solution ||3 - -OOPII- Thus B cannot be charged uniformly for the optimal loss, and instead can be arbitrarily large.
The reason SGD and online gradient descent do not work in our setting is that they miss (in most iterations) highly important points when there are only few of them (this is also the issue with uniform sampling). This pointed out in previous related work, c.g., (Munteanu et al. 2018 Section C) and (Munteanu et al. [222]] Section 6), who constructed synthetic data with only 2 out of n such important points and additionally demonstrated empirically how bad SGD can perform even on mild data with J
Below add SGD to our empirical results on real world data. SGD performs quite well, though not better than sketching. The reported performance of SGD is the median approximation ratio over 21 independent repetitions of one full pass over the data, to be baseline comparable to the sketches. We note that plotting the iteration-wise error would make the results for SGD look much worse.
For our synthetic data (described in detail below), instead of out of heavy points (as in previous work), we have (d)) out of n heavy points. Since SGD misses those in most batches, the instance looks separable to SGD in almost all iterations. although the original instance is inseparable. This results in approximation ratios around 15 000 (note the logarithmic scale on the vertical axis). In contrast, our sketch and the previous sketch give small constant approximations.
Covertype, À=
Webspam, À
1.06
2.0
SGD
modiar apptosmmation ratio
SGD
1.01
Sketch (old)
1.8
Sketch (old)
Sketch2
Sketch2
1.00
Sketchh
1.6
Sketch5
Sketch11
1k
1.00
1.4
1.01
1.2
1.00
5000
10000
13000
1.0
2500
10000
12500
15000
reduced sine
reduced sire
Kddcup, x =
Synthetic data, À = 0
SGD
modiian apprasimttion ratio
10
SGD
8
Skotch (old)
Skatch (old)
Sketch2
10%
Sketch2
Sketch5
Skeechh
Skottch10
10P
10000
15000
20000
25000
30000
$5000
40000
1000
1500
2000
2500
3000
3500
4000
reduced
reduced
Figure 4: Median approximation ratios for plain logistic regression (A 0). SGD is compared the old sketch as well as the new sketch with various settings for the sparsity E (2, 5, 10} on different real-world benchmark data, and on our synthetic data.
33

---

Published as a conference paper at ICLR 2023
Added experiments for & reregssssionn We implemented the Cauchy sketch (Indyk 2006; Sohler & Woodruff] 2011] Woodruff] 2021) that simply consists of ii.d. standard Cauchy entries. The sketching matrix then multiplied by the data matrix and the sketched & regression problem is solved. The plots show the median approximation ratio over 21 repetitions for each target size of the sketch. We see that the new sketch, using any degree of sparsity 8 {2, 5, 10), outperforms the Cauchy sketch by a large margin in terms of approximation factor (while being a lot faster to apply than the dense matrix multiplication).
Covertype
Webspam
1.3
1.1
median approximation tonii ratio
Cauchy
median approcination ratlo
Cauchy
Sketch2
Sketch2
1.3-
Skerth55
Sketch5
Sieetch10
Sketch10
1.2
1.1
1.1
1.0
1.0
5000
10000
15000
20000
2500
5000
7500
10000
12500
15000
reduced size
reduced size
Kddcup
1.5
median approxination ratio
Cauchy
1.4
Sketch2
Sketch5
1.3
Sketch10
1.2-
1.0
10000
15000
20000
25000
30000
35000
40000
reduced size
Figure 5: Comparison of the median approximation ratios for frrrggession of the Cauchy sketch sketch with various settings for the sparsity {2, 5, 10) for different real-world benchmark data.
Synthetic data set The synthetic data set consists of 2n = 40 000 data points. The dimension of the data points is d 100.
There are (n - n/10 2d) points of the form (-1, - 11,,,...,, -1). The optimization of focuses on these points.
(n/10) points are the form (1, 1, 1). These points are only added to obtain clean plots. If they are omitted, then the gap between the optimal 3 on the original data and the optimal 3 on a bad sketch or uniform sample becomes worse, and "wiggly""
d points are of the form (-n, -,, ..... -n). They are oriented in the same direction as the first set of points. They will mostly be ignored in the optimization since there are only few of them, but they can cancel the following heavy hitters.
For each E [d]. we add one vector of the form (n e;), where is ith standard basis vector. These points are the heavy hitters pointing away from most other points. For any good relative error sketch, it is crucial to preserve all of them;
We add n times the point (0, .0.....), 0). These points are needed to ensure that the instance works in labeled setting (to be natural data set for logistic regression).
The labels of all points unequal to the all zero vector are set to 1. All zero vectors are assigned the label -1
34

---

Published as a conference paper at ICLR 2023
The idea behind this instance is as follows: if the sketch maps any point of the form (n eq) into the same bucket as (-n, -n,... -n) -vector, then the instance will become almost separable, so the sketch will have cheap solution, meaning that there exists some 3 such that the logistic loss on the sketch low. However, on the original instance, the logistic loss of the same 3 will be large due to the loss associated with (n e,).3. This implies large approximation ratio. For small sketch sizes, the old sketch has relatively high probability for this bad event to happen, when hashing each point into single bucket. Our new sketch will likely preserve all points the form (n ex) on most the multiple sub levels. This preserves the cost even if our sketch size is small (almost linear).
Pseudocode of our sketching algorithm Algorithm | jimplements the first step of the sketch & solve paradigm for approximating logistic or & regression. The changes in comparison with (Munteanu al. 2021 are highlighted in red.
Algorithm I Oblivious sketching algorithm for logistic regression.
Input: Data X E Rexd number of rows k N hm + No, parameters > 1, 2 where = 8. N' some N' E N;
Output: weighted Sketch C = (X', w) E laxd with k rows.;
1: for = 0...... Nm do
> construct levels O,... hm of the sketch
2: initialize sketch X
E RN Xxd at level h; 3: initialize weights wi 6th 1 E R at level h;
4: set wh ma. draw random number B; E [N']:
adapt weights on level to sparsity s >> sketch the data b> densify level
5: for = 1.. do
6: for s...s do
7:
8:
add x; to the ((1 ()) N' + B,)-th row of X6:
9:
assign 2, to level E [1, Am 1] with probability gF:
10: draw a random number B, E [N]:
add x; to the B,-th row of X/;:
add x; uniform sampling level hm with probability Pho.. 5m
13: Set X' = (Xg, XI.... X hmm
14: Set w = (wo, Wi.... Whm)
return C = w)):
35


Reviews:
[{"review_id": "iOsqsvkOJC", "reviewer": "Reviewer_yfhf", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "The paper considers the problem of using sketching techniques for logistic regression. It builds on the previous work of Munteanu et al.'21 which developed an approach to sketch n datapoints in d dimensions to poly(\\mu,d,log n) weighted datapoints (in d dimensions) such that solving the logistic regression problem on the smaller dataset gives a log(n) approximation to the function value obtained by the solution on the original dataset. Here, \\mu is a data-dependent parameter which captures the complexity of sketching. Though Munteanu et al.'21 obtain a poly(\\mu,d,log n) sized sketch, the polynomial dependence on d is not optimal. The current paper closes this gap and shows that a sketching dimension only slightly superlinear in d suffices to obtain a constant approximation to the logistic regression problem. Similar approximation results are also obtained for the L1 loss. The improvement comes from a small modification in the algorithm, and a much tighter analysis. The modification in the algorithm is to hash each element to multiple buckets instead of a single bucket in the CountMin Sketch.\n\nThe paper validates the algorithm via similar experiments as in Munteanu et al.'21. The proposed algorithm generally performs better than the previous approach in the experiments.\n\n", "summary_of_the_review": "In summary, I think this paper has a good contribution and achieves tight bounds for a natural problem. But especially for a venue like ICLR where much of the audience may be unfamiliar with the developments for this problem, it is important for the paper to be written and presented such that familiarity with prior work is not as essential. The paper falls short on this regard, and I would place it below the acceptance threshold for this reason.", "strength_and_weaknesses": "Strengths:\n\nThe proposed algorithm is a simple modification of the previous approach, but comes with much stronger guarantees and achieves better results in practice.\n\nWeaknesses:\n\nMy main concern is that the paper is not written in a way such that it can really be self-sufficient without reading and understanding Munteanu et al.'21 and related literature. This makes the contribution harder to evaluate and makes it appear to be not as significant. There are several issues in the writing and discussion of the setup:\n\n1. To begin with, a much better job needs to be done to motivate the problem. Since the goal is to solve the logistic regression problem without storing all the datapoints, why is SGD/online gradient descent not the right approach? It would only require memory linear in dimension, even better than the proposed approach. It comes with regret guarantees too, are those sub-optimal compared to the approximation ratios which the paper obtains?\n\n2. Various approaches have been proposed to sketch solutions to linear classification problems, such as \"Linear and Kernel Classification in the Streaming Model: Improved Bounds for Heavy Hitters\", \"Sketching Linear Classifiers over Data Streams\", \"Random Projections for Classification: A Recovery Approach\", \"Finding needles in compressed haystacks\", \"Compressed Classification from Learned Measurements\", how do the sketches in these paper compare with the proposed approach? It appears to me that these papers compress the dimensionality d of the datapoints, whereas the current paper compresses the number of datapoints n, but some more discussion of the pros and cons would be useful to situate the work better.\n\n3. The discussion of related work is often that as well organized. For e.g. Sec 1.2 on L1 regression combines various discussions of the current paper with previous approaches in a way which makes it a bit hard to follow the thread.\n\n4. The paper would benefit from an algorithm box with a detailed description of the algorithm (perhaps also pointing out the part where the algorithm differs from Munteanu et al.'21).\n\n5. Similarly, it is nice that the authors included Section 3 on the proof overview, but I found it hard to follow without first going through Munteanu et al.'21.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "EyIPGOoFYp", "reviewer": "Reviewer_bsu6", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper improves upon previous oblivious sketching and turnstile streaming results for $\\ell_1$ and logistic regression, achieving constant factor approximation, and an efficient algorithm in the sketched space. They demonstrate:\n\n1. Based on a modification of Munteanu et al. (2021) (with significant change of the analysis), they are able to achieve an $O(1)$-factor approximation algorithm with sketch size $\\tilde{O}(\\mu d^{1+c})$ for any $c > 0$, for the problem of logistic regression. Here $\\mu$ is a data-dependent parameter which captures the complexity of compressing the data for logistic regression. \n\n2. To obtain a $1+\\epsilon$ guarantee, they demonstrate that a sketch size of $(\\mu d \\log(n)/\\epsilon)^{O(1/\\epsilon)}$ is sufficient. \n\n3. They show that their sketch can also approximate variance-based regularized logistic regression\nwithin an $O(1)$ factor if the dependence on $n$ in the sketching dimension is increased to $n^{0.5+c}$ for\nany $c > 0$.\n\nThe authors then experimentally demonstrate the performance of their algorithms in comparison to prior work, with performance usually better, and just a little worse than prior work on one benchmark dataset. \n\n\n\n", "summary_of_the_review": "I think this is a good paper and vote to accept it. The paper produces a clear improvement over prior work, building off the work while complementing it with a significant change of analysis. ", "strength_and_weaknesses": "Strengths: \n1. This is an interesting paper with a clear improvement over prior work. \n2. The analysis involves several new ideas.   \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "4mBswUbJU49", "reviewer": "Reviewer_mC84", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper presents oblivious sketches for logistic regression with significantly improved sketching sizes both in terms of $d$- the dimension of the data and $\\mu$ the measure of complexity of compressing the data. The paper also gives sketches for the $\\ell_1$ regression and variance regularized logistic regression. Theoretical claims are supported by empirical evaluations on both real and synthetic data.", "summary_of_the_review": "Overall, the paper is more of theoretical nature and will be of great interest to the researchers working in the \"sketch and solve\" paradigm. Also, logistic regression being a very important problem in machine learning, the paper would be of interest to broader community too. I recommend an accept", "strength_and_weaknesses": "Strengths:\n1. Vast improvements in oblivious sketching dimension for logistic regression compared to previous works.\n2.  Sketch for variance regularized logistic regression\n3. Empirical evaluations\n\nWeakness:\n\nThe only weakness I feel is that the paper may be difficult to read for those who are unfamiliar with the related works. There are a few points I mention in the section below which might help improving the clarity", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster