STORM: Sketch Toward Online Risk Minimization
Authors: Gaurav Gupta
Benjamin Coleman
John Chen
Anshumali Shrivastava
Venue: ICLR 2022 Submitted (2022)

Abstract: Empirical risk minimization is perhaps the most influential idea in statistical learning, with applications to nearly all scientific and technical domains in the form of regression and classification models.
The growing concerns about the high energy cost of training and the increased prevalence of massive streaming datasets have led many ML practitioners to look for approximate ERM models that can achieve low cost on memory and latency for training.
To this end, we propose STORM, an online sketching-based method for empirical risk minimization. STORM compresses a data stream into a tiny array of integer counters. This sketch is sufficient to estimate a variety of surrogate losses over the original dataset. We provide rigorous theoretical analysis and show that STORM can estimate a carefully chosen surrogate loss for regularized least-squares regression and a margin loss for classification. 
We perform an exhaustive experimental comparison for regression and classification training on real-world datasets, achieving an approximate solution with a size even less than a data sample.

Under review as a conference paper at ICLR 2022
STORM: SKETCH TOWARD ONLINE RISK MINIMIZA- TION
Anonymous authors Paper under double-bling review
ABSTRACT
Empirical risk minimization is perhaps the most influential idea in statistical learn- ing, with applications to nearly all scientific and technical domains in the form of regression and classification models. The growing concerns about the high energy cost of training and the increased prevalence massive streaming datasets have led many ML practitioners to look for approximate ERM models that can achieve low cost on memory and latency for training. To this end, we propose STORM, method for empirical risk minimization. STORM com- presses a data stream into a tiny array of integer counters. This sketch is sufficient to estimate variety of surrogate losses over the original dataset. We provide rigorous theoretical amalysis and show that STORM can estimate a carefully chosen surrogate loss for regularized least-squares regression and margin loss for classi- fication. We perform an exhaustive experimental comparison for regression and classification training real-world datasets, achieving approximate solution with size even less than a data sample.
online sketching-basee
INTRODUCTION
Empirical risk minimization (ERM) has been independently studied by the machine learning, statistics, and computer science communities. However, conventional ERM algorithms are becoming more expensive in terms of latency, memory, and energy due the need for accurate inference over rapidly increasing data volumes (He et al.) (2066] Vaswani et al., 2017). The net effect is an increase in storage costs of large data matrices (Guhaniyogi & Dunson 2015). network latency for personalized
and carbon emissions. There is growing need for approximation algorithms that can minimize the cost, memory, and energy associated with training and inference (Lin et al.) 2020; Motamedi et al. 2016). Additionally, there distinct advantages of training small memory local/personalizer device, as data is generally collected on these devices. This limits the data transfer big servers that consumes substantial resources (Bill Allcock (001] [u] 2013)
inferenceerroommenaatiooo
and minimizes the privacy vulnerabilities (Mendez Mena et al., (018)) Existing compression methods generally fall into two categories: sketching and sampling.
Linear Sketches: A large family of projection-based sketches uses ideas from compressed sensing, matrix factorization, and dimensionality reduction. A common theme is approximate the large N x d data matrix with smaller representation. For example, multiplication with a random #1 matrix yields a sketch that attains the information-theoretii lower bound for compressed linear regression (within constant factor) (Clarkson & Woodruff 2009). Random Gaussian, Hadamard, Haar, and Bernoulli sign matrices have also been used in this framework with varying degrees of theoretical and practical success (Dobriban & Liu 2019). The "sketch-and-solle
technique has also been extended to regression with the objective and several other linear problems (Sohler & Woodruff 201T). This framework cannot accommodate regularized objectives because the model is computed directly from a set of precomputed sufficient statistics.
Recent work by Shi & Phillips (2021) has shown that a matrix sketch based on the frequent directions method (Liberty, 2013] Ghashami et al. 2016) can be used for ridge regression. This algorithm
uses a sketch to approximate the most costly part of the ridge regression objective, X" x + AI. in a streaming setting. The memory is Oldd), where X Raxd and > 2. That is, the memory is linear in the dimensions, with a minimum size of (2d + 1) x floating precision that can be very large for high-dimensional data.

---

Under review as a conference paper at ICLR 2022
Coresets and Sampling: A reasonable strategy is extract core subset (or coreset) of points that efficiently represent the complete dataset. The coreset framework supports the approximation of loss function sums within a (1 + e) error margin. There coresets for important problems such as
(P ff-regression (Dasgupta et al. 2009) and logistic regression (Munteanu et al. 2018). Classification
objectives also admit small coresets (Har-Peled al. 2007 Tukan et al. 2020), do many other regularized ERM problems (Reddi et 2015). The problem is that many coresets require super- linear construction time. For example, many of the algorithms in the previous paragraph require k-means clustering, leverage scores, or multiple cycles through the dataset (Tukan et al. 2020 Munteanu et al.) 2018: Har-PPeled et al.) 2007). Coresets are also tricky to merge since it is not straightforward to decide which points to discard. As a result, composable and streaming coresets are an active area of research (Indyk et al. 20144] Karnin & Liberty 2019). Although leverage scores can be approximated online (Cohen et al. 2016), the process is computationally expensive and not well suited to edge devices. In many practical problems, random sampling is the only feasible sampling baseline that supports regularized ERM.
In this work, we propose a new sketching framework (STORM) that supports both regularization and streaming algorithms. Given an N N-point dataset D {x1 l/1 (x..)..N.. yN)] of d-dimensional examples observed in the streaming setting (Fiat 1998). the goal is to construct a small structure S that can estimate regression and classification loss over D. STORM consists of two main components, 1) STORM loss for regression and classification, 2) A tiny array of integer count values called STORM sketch. This array sufficient perform empirical risk minimization on STORM loss. In practice, our data structure allows for optimizations that are not possible with other methods. Specifically, our contributions are as follows:
1. We propose an online sketching algorithm (STORM) that can estimate special class of loss functions using only integer count values. Our sketch is appropriate for distributed data settings because it is small, embarrassingly parallel, and mergeable via addition.
2. We characterize the set of -TOORM--proximmabl loss functions. The price of efficient loss estimation is a restriction on the kinds of losses we can use. While we cannot directly estimate popular regression and classification losses, we construct surrogate losses for t regression and large margin classification.
3. We show how optimize models over STORM sketches. The count-based nature of our sketch makes gradient descent difficult, and black-box optimization techniques are of limited use in high-dimensional spaces. We propose an optimization algorithm that custom-tailored to our sketch.
4. We conduct rigorous empirical evaluation with ridge regression and classification. We show that our approach has better train/test loss performance and lower variance than sampling baselines in the low-memory, resource-constrainee computational regime. For some datasets, we can achieve strong performance with memory smaller than even one sample.
2 BACKGROUND
2.1 EMPIRICAL RISK MINIMIZATION
In the standard statistical learning framework, we are given a training dataset D = {(x,, yi) E D x )' of examples and asked select function h X + y that can predict y given æ. In this paper, we will present our algorithms for the data space X' = I2 and output space y = RR but most of our results hold generally for other metric spaces too. The learning problem is to select a hypothesis he (a function parameterized by 0) that yields good predictions, measured by loss function loss( (ho(x), (x)))) v). In empirical risk minimization (ERM), we select / to minimize the average loss on the training set.
Ô = arg min loss( (zz), y:) i=1
In the case of Linear regression, hx(x) = (0, x). For most applications, 0 is found using the least-squares or l loss: (oss(ho(x)) = [|ho(x) v112. The unconstrained ( loss is smooth and
2

---

Under review as a conference paper at ICLR 2022
strongly convex, with favorable convergence criteria. The parameter 0 is typically found using gradient descent or via a closed-form solution from the matrix formulation of the model y = X9. For our discussion, it will be important to express the loss in terms of the concatenated vector [x,, y:l:
i arg min ((xx, vel. 10, 1])) arg minlly x01
2.2 LOCALITY SENSITIVE HASHING
A Locality sensitive hash (LSH) function (I(x)) provides the same hash value for similar points with high probability. The notion of similarity is usually based on the distance measure of the metric space X. For instance, there are LSH families for the Jaccard (Broder 1997), Euclidean (Datar et al. 20044] Dasgupta et al. (011) and angular distances [Charikar] 2000 If we allow asymmetric hash constructions (i.e. (x1)
(x2).. 4 * 12). then X1 and X2 may collide based on other properties such as their inner product (Shrivastava & Li] 2014). Asymmetric LSH functions use one hash function (l,) for data and different function (12) for queries. To accommodate asymmetric functions, we use the following definition of LSH, Our definition is a strict generalization of the original definition from Indyk (1998) Indyk & Motwani (1998), which can be recovered by setting probability thresholds.
Definition 1. We say that a hash family F is locality with collision probability k(-,') if for any two points Xı and x2 in IR,, l(x1) = 1(x2) with probability k(x1, X2) under a uniform random selection of F.
The signed random projection (SRP) family for the angular distance (Goemans Williamson 1995: Charikar 2002) is an example of a symmetric LSH family. The SRP family is the set of functions (xx) sign(v w x), where (o, Ia). The SRP collision probability is
(xI, X2)
x(x1, =
cos
Xx la X2|12
The inner product hash Shrivastava & Li (2014) is an example of an asymmetric LSH. To get this hash function, replace X1 with X1, O, v Xx and X2 with X2, v X2 12
in the SRP function. This procedure essentially uses different hash functions for X1 and X2, since we augment x, (the data) in one way and x₂ (the query) in different way. The collision probability xx) is now a monotone function of the inner product (x1, X2). This construction implicitly assumes that X and X² are inside the unit sphere, but other hash functions do not require this assumption (Shrivastaval
& Li
2015 Neyshabur & Srebro 2015
Huang et al. 2018
RACE Sketch: The RACE sketch is 2D integer array S Z that we index using LSH functions (Coleman & Shrivastava 2020 Luo & Shrivastava 2018). Each row of S called an Array-of-Counts (ACE) data structure (Luo & Shrivastava 2018), and the entire sketch is set of R independent ACE repetitions (RACE). To construct a RACE H. sketch from a dataset D, we begin with an empty R B integer array and of R independent LSH functions {x)))xx.(xxx Each LSH function has the collision probability k(0, x). When an element x arrives from the data stream, we hash x to get different hash values. We increment row at location (xx) and repeat this process for all elements in the dataset.
To query the sketch with a query 9, we return the average value of (()) over the R rows. RACE sketches are interesting because they estimate the sum of LSH collision probabilities over the dataset with low variance for any query 0.
Theorem 1. Unbiased RACE Estimator,oolemnn & Shrivastava 2020 Let X = =Sii, (()). Then
Σ k(x,0)
var(X) S
kxxx 1 0) Σ
XED
XED
Regarddesss, often scale and center the dataset when using inner product hash functions in practice.
3

---

Under review as a conference paper at ICLR 2022
Repetition
Repetition 1And
Many Repetitions
more partitions
Counts:
2
Figure I: LSH counts are sufficient for learning regression lines and classification hyperplanes. Here, we show the partitions that correspond to several STORM repetitions (or rows). Since the regression line should lie inside brown) to identify regions that contain the normal to the regression line (regression hyper-plane in higher dimensions). Each STORM repetition prunes the space of eligible models, until are left with the small feasible sparse region (shown in orange). We gain the most information when the partition boundaries are orthogonal, which is nearly always true in high dimensions.
region, we sparsely-poplltee partitions (shown in
3 STORM
While collision probabilities have been well-studied in the context of improving near-neighbor search (Gionis et al.) 1999). we study them from a new perspective. Our goal is to compose useful loss functions from LSH collision probabilities and perform ERM on sketches. In this context, query the sketch with the parameter / to estimate the empirical risk. This requires some extensions to the RACE sketch.
Intuition To understand approach, consider the task presented in Figure We partition the data space into B random regions using Gaussian random hyperplanes. The count of points in each region gives an estimate of its density. We repeat this partitioning many times so that have good estimate of densely--opulated and model hyperplane passes through the dense regions. Our objective is to find & vector normal the optimal model hyperplane. This motivates to look for the sparsest region. STORM sketch (inspired from RACE) provides counts of data points in each partition. We will see that we can optimize over these counts to find a 0 that resides in the sparsest region. The main challenge is to design an L.SH function ((0) that has the minimal count when 0 good model. Next, we will talk about an appropriate hash function, STORM loss for regression and classification and, the STORM sketch for approximating the loss
regions. In the regression settings, the optimal
3.1 STORM SURROGATE LOSS FOR LINEAR REGRESSION
Since we query the STORM sketch with we must be able express (x)))) y) as loss(0, [x. (P.y] This condition is not limiting, but it does restrict our attention to hypothesis classes where 0 directly interacts with x and y a way that can be captured by an LSH function. Linear regression is the simplest example of such model. Here the 0 interacts with the data via the inner product {[A, -1], 111.1. x v)). The asymmetric hash function from Section 2.2 seems like a natural choice. However, the linear regression loss function monotone function of the absolute value of the inner product.
To obtain a surrogate loss with the correct dependence on {i0, [[0, [x, vl), observe that the collision probability of SRP (Section 2.2 is monotone decreasing if hash --x--) instead of [x. y). Thus, we can obtain function that is monotone in |[0, - -1], x y)>1 by adding together the collision proba- bility for [x, y] (which is monotone increasing) and for -X,- -yl (which is monotone decreasing). We call this LSH family "paired random projections" (PRP) because the method can be implemented by hashing both xx, y] and [-x, -y] with given SRP function and updating both locations in the sketch. When we query the vector [0. -1] with the same SRP funetion, STORM estimates the following collision probability/ surrogate loss for linear regression
1 (1 1 00, x v)) =
cos -l ((0 [x. (xx +
(1
cos fos--66 (- [x, n)))
4

---

Under review as a conference paper at ICLR 2022
where are free to choose any number of random hyperplanes p 2 2. The proposed loss is convex, unbiased and consistent. More info in section
Construction
PRP Sketch
model 0
A Algorithm 1 STORM Sketch creation
4 (xx)
Input: Dataset D Result: STORM sketch S Zxxx
41 (1xxx)
55
2
11
6
(0)
X;
12 )x.)).........
17
2+
2
00
7
4
R. (0))
0
for x E D do
data
(a(-x,)
1 B
2
: (0)
for r I...R do
1/ [xxx)-)-))
Increment S(r, (x)] end for end for
43 4x(x;;)
B 2
Figure 2: To construct STORM sketch, we initialize 2D array with R and B columns (buckets) in each row. The asymmetric LSH function 4, indexes row i of the sketch. We want best model hash into least count buckets. See Sections 3.3 for details.
3.2 STORM SURROGATE Loss FOR CLASSIFICATION
Consider linear hyperplane classifiers of the form ha(x) sign( (0,, [x. -1])). The most popular losses used to find 0 are cussification-calliaat calibrated, Bayes consistent, if the optimal hypothesis under the loss is the same as the Bayes optimal hypothesis. With these factors in mind, we propose Classification Random Projections (CRP) estimate the following loss function:
margin losses. A loss function is classification-
Theorem 2. Consider labels y E {-1,1}. The loss function g(0, [x, ul) for the linear hyperplane classifier is classification-calbbiee margin loss and is STORM-approximable
1 g00,(x, (x, v)) = 2 (1 (1- cos (-y((,,x))
P
-
By optimizing 0 in similar fashion to as with regression, we can train linear classifiers with STORM sketches. The LSH function that implements g(l,, 'x, ) is the asymmetric inner product (SRP) hash, but with the argument to the hash function multiplied by y (-1.
See the appendix for details and proof of theorems.
3.3 STORM SKETCH
We use asymmetric LSH functions to hash data points x and with different functions. Most LSH functions have positive definite collision probabilities. but asymmetric LSH functions allow much more flexibility. Our Paired Random Projections (PRP) hashing scheme premultiply the data vector by a [+1) to estimate a surrogate regression loss. Classification Random Projections (CRP) LSH premultiplies x with Figure our sketch process for PRP. Here we insert elements into the sketch with two SRP hashes, but only use one SRP for the query. In Section 3.1 and Section 3.2 we show that this sketch estimates surrogate loss for linear regression and classification.
Once we have a sketch and an appropriate hash function, we want to optimize the model parameter to minimize the STORM estimate of the empirical risk. Proposed optimization method is discussed in details in the next section.
3.4 OPTIMIZATION
Gradient descent traditionally used to find the best 0 for ERM problems. Unfortunately, our sketch consists of discrete integer counts that have neither an analytic gradient nor subgradient. However, following the intuition from Figure I we know that our surrogate loss tries to find the hyperparameter Ø in the sparsest region. This allows us to develop a specialized optimization heuristic that exploits the hyperplanes of the proposed hash to locate the minimum-riss 0 more effectively. Our surrogate objective is: i arg ming s(0, -1], [x, v)) arg ming E[S[T[[0) -1]))--
5

---

Under review as a conference paper at ICLR 2022
PRP sketch
Algorithm 2 Hyperplane-bast based stochastic gradient descent
8
2
11
6
Input: STORM sketch & Z Result: Model 0 Initialise 0g + 0d++
17
2
2
0
7
4
R
for 1..R do
8
5
2
7
12
Z, 2* binary(argmin S(:))-
B
end for
Labels (x)
A ggregaate all labels Z/s to Z and store it. for iterations 1 1...7 do
Labels
sign(w,0)
sign(w,0) D
random sample i
0010
sign (w:(w,))
Get random hyper-planes W, from the given seed. Update 8. = - n/ ||tan T,V 0) 2 2
0100
sign
Project last dimension of -1 end for
Select best / using validation set.
store: Rp RlogB bits
Figure 3: Left: Shows the algorithm for optimization the extracted labels of least count bins. Right: Figure that shows the further compression on the PRP sketch (works the same for CRP) by storing just the labels (Z) of least count buckets.
where S is the sketch and L = (1...p) is the hash function. This implies that 0 lies in region where most of the STORM partitions have lower count values (small values of S(z(0))) One could do brute-force minimization over all possible partitions and select model 0 in the winning partition, but this is computationally expensive. Instead, we use the stochastic gradient descent approach and transform our objective follows: g() >I' Sli, L.( -1]]
The gradient Vg(()= Σ
turns out that the individual minimization problem (for each tt sample), arg min, Sli, ( 1])] can also be written as arg ming ( -1]) Z.1.2. Here Z, E 10" represents the binary label vector of the minimum count bucket in row i.
Because we use SRP as the hash function, L, (Ø) = sign TVVTO 0). We now have the objective function in terms of 1 (W, 0) Z 12. This can be made diffrentiable by using tanh instead of sign function. Hence, the gradient update becomes
/++1 0² 1/V [W,] Z
This becomes the SGD over standard single layer neural net with tanh activation. (Refer to appendix for more details). Also, we can simply add any regularization term with this. In case of Ridge regression we have the following gradient update
gc+ 0 17 [tanh(W;
7,
2X0 -200
It is interesting to note that, need a single seed value for generation) and very cheap binary vectors Z E 1] 1R Rxp, The sketch size required is Rp R log B. Although this method (Algorithm (2) finds approximate gradients, find that the procedure works well in practice. Since we can regenerate the hyperplanes from random seeds, we only need to store the hash codes (Z) of the least populated buckets with this approach.
learning randomly generated hyperplanes (W,) (these only
THEORY: SKETCHABLE SURROGATE LOSS
We begin with formal description of the families of losses that STORM approximate.
Formally, a loss g(0, [a, vl) is -ppxiiaaero if there a hash function and a STORM sketch such that querying the STORM sketch with 0 yields unbiased estimator of g(,, [a. vl).
Using the compositional properties of LSH, we can approximate any sum and/or product of LSH collision probabilities using one STORM sketches. For example, estimate sums by

---

Under review as a conference paper at ICLR 2022
Surrogate loss
Classification Losses
PRP p-2
Logietic
PRP pm
PSP
Vgl0. (g.0
30
Expereetiaal
Zero-One Loss ifayes Octimali
STORM Less, P
<0,ixyy>>
Figure 4: (a) PRP Surrogate loss for different values of p. It is convex, but less sharp than the L2 loss. A key observation that p 4 produces the highest convexity among the family of PRP surrogate losses. (b)Plot of slope surrogate loss for different values of at ([0, - 11, 2)) 0.1. The surrogate loss has the steepest slope (and is thus easiest to optimize) near p = (c) Comparison of various classification-calibaate loss functions, including the STORM's CRP loss.
inserting elements with than LSH function (or using a second sketch). We estimate a product collision probabilities by combining multiple LSH outputs into a single hash code. Theorem formalizes this argument (we defer all proofs the appendix).
Theorem 3. The set of STORM- -aprooappox functions St contains all LSH collision probabilities and is closed under addition, subtraction, and multiplication.
Given the number of known LSH families, the flexibility of asymmetrie LSH and the closure of S under addition and multiplication, Theorem 3 suggests that Sy, is an expressive space of functions. remains for us to show that St, contains useful losses for machine learning problems.
Theorem 4. When 2 2, the PRP collision probability g(10, -1], s [x, y) lis a convex surrogate loss for the lineur regression objective such that
arg min g(0, - -1], [x, vl) arg minlly -x0]
0
Check Figure (a). A detail proof is given in the Appendix.
We analyse, how the sketch size affects the PRP/CRP loss estimation from the STORM sketch. Consider the following Axiom
Let ZR. be R i..dd random variables with mean E| lA and variance S o². Divide the R variables into groups so that each group contains m R/g elements, and take the empirical average within each group. The median-of-ment estimate ğ is the median of the group means. If g 8 (1/8) and m R/g, then the following statement holds with probability 1 1- ò.
AA - 1-14l
1/5
VR.
This proof is given in Alon et al. 1999) as the proof Theorem 2.1 (which is a slightly more general version of the statement above). From the variance result from Theorem [ and median of means estimate of the PRP/CRP loss from STORM sketch, we state the following-
Theorem 5. Let (0) is the median of means estimate on the STORM sketch, with R rows, then with probability more than 1 -
EXED / Vk(x, 8)
lg(0) g(0)1=
Vlog(1/8)
VR
Where ExED Vk((x,) 8) is the collision probability of the hash function use.
4.1 PARAMETERS
Number of hash functions (p): The parameter p the number of PRP/CRP hash hyperplanes that creates 2 partitions. Larger is good for more resolution of the space, but it also leads to many buckets with few/zero counts. (Figure[[aa) shows that higher p makes the loss surface flatter near the optimal region). Figure (b) shows that setting p as 4 maximizes the gradient of the surrogate loss near the minima, and we find that in practice too (Refer Appendix). It is also efficient because for p = 4, B is only 16. Also, we need fewer rows in the sketch to optimize g(0, [x, y)) when is strongly convex.
7

---

Under review as a conference paper at ICLR 2022
Table 1: Each dataset has N entries and d features. The datasets are taken with Open Commons share-alike license and Creative Commons Attribution License. The dimension in bracket represent the effective datasct dimension after random Fourier feature mapping.
Dataset
N
d
Size
Туpe
Diahetes (Efron et al.
2004)
442
10
17KB
Patient records
Boston [Harrssn & Rubinteld 1978
500
13
25KB
Housing price
Meat (Jowder al.
1997)
239
123 (615)
114KB
Mid-IR spectra
Soil Corwin 2019
679
127 (635)
336KB
Sensor data
Gas Vergara al.
2012)
13910
129
6.8MB
Sensor data
Fruit (Holland et al.
1998)
983
235 (1175)
902KB
Mid-IR spectra
UIndoorLoc Porres-Sospedra et al. 2014)
21048
529
42MB
Localization
Australian (Dua & Graif 2017)
690
14
37KB
Financial data
Mnist (Lecin et al.
1998
60000
784
179MB
Image data
Number of repetitions (R): The square root of collision probability v k(x, 0) I 1 always. Hence, in the worst case the value of EXED Vk(xx 8) N. For lØ(0) 9()) S C Cloo((1/)), we need number of sketch rows R < O(N²) (Using the Theorem 5p. The worst-case O(N2) situation happens when every point in the dataset has maximum loss. Practical modeling situations typically have small fraction of points for which the training loss is small. experiments, we vary the number of rows and see the change in Mean Square Error (MSE).
5 EXPERIMENTS
Experiment setup:
We use PRP and CRP with p (most optimal, check Figure 4b)) to create the sketch and we vary the number of repetitions to show the memory tradeoff. We have used a variety of datasets. Refer table T
All models are trained and evaluated with a fixed 80/20 train/test split. We average over 100 runs for our baselines and sketches, where each run has an independently constructed sketch or random sample. Thus, our average is over the random LSH functions used to construct the sketch and the stochastic gradient descent instances. We use the hyperplane optimization heuristic for regression and derivative- free (Conn et al.. 2009) gradient descent for classification. To run the code we used our personal laptop with 17-8750H processor, 2.2 GHz base frequency and 9MB cache size.
Ridge Regression: We evaluate our method on ridge regression, which penalizes 0 to avoid the double descent and over-fitting problem (Nakkiran) 2019). To implement this model, we simply add ||0112 to the STORM objective function. The gradient updates take place as described in Section 3.3 but with an added regularization term. For regularized ERM in our computational setting, random sampling and Frequent direction sketch is the only reasonable baseline. Coresets for ridge regression exist, but canmot be constructed in the streaming setting. Also, Frequent direction based sketch takes space much more than STORM and random samples for higher-dimensing Hence a direct comparison is made for the low dimensional- Diabetes and Boston housing dataset. 5 shows the results of comparison focused mostly sub-kB region. We find that STORM achieves a lower MSE in the low-memory regime. In particular, for the gas, soil, fruit, and indoor datasets, STORM produces reasonable model using less memory than even a single sample. Finally, the STORM results have a substantially smaller variance (typically 2x), which is a critical factor in practice. Additional plots and sanity check on a 2D synthetic data is available in the appendix.
data (near d > 100).
STORM for Non-linear Objectives: STORM supports regularized linear regression and classifica- tion. With this formulation, a non -inerr model can be trained with feature mapping such as random Fourier features (Rahimi & Recht 2008). To achieve a non-linear boundary the mapping is done to higher dimension space. Practically this 3 times the original dimensions. Since STORM does well with nigh-dimensional datasets, often requiring less memory than single sample, we expect good performance using figh-dimmnsione feature transformations. Figure 5 last row demonstrate the mean square error (MSE) with the size of sketch variables required for linear regression.
Linear classification: We run the linear classification on datasets from the libsvm repository. We compare against a linear SVM trained comparison for the "Australian credit" (Dua & Graff 2017) and the popular MNIST (Lecun et al. 1998) dataset.
random sample of the dataset. Figure 5] shows this
8

---

Under review as a conference paper at ICLR 2022
NSE
Meat test MSE
STORM Ridge
STORM Ridge
STORN Ridge
Hear Leaxt R5 fidgo FURjage
Hean
Mean
Loast Rldige
Leest Ridge
Nadgo
R5 Rllge
FORkige
MSE
MSSE
05
Size (Kllobvtes)
Size (Kilobvtes)
Size (Kllobvtes)
Soil test MSE
ges test MSE
Fruit test MSE
STORM Ridge
Mean
flcge
RS Nage
STORM- Ridge
Mean
Ridge
INdge
STORN Ridge
0:31
Mean
Radge
642
Raage
(Kilobytes)
Size (Kilobvtes)
Size (Kilobvtes)
Indoor test MSE
Australian
MNIST (0/1)
3.50
SEGRM Pedge
Accuracy
Acturacy
Heon
Lewsr Sq Rirge RS- Sidge
3.25
455-
GVMN
0.5
03
050
Size (Kilobytes)
Size (KB)
Size (cB)
Hest test USE
Soll RFF test MSE
Frui RFF tes: MSE
0.355
Hale
0.29
Rige
0.33
R.dge
0.338
Vidge
S10 Happe
MSE
1.379
Ridge
0.00
0.240
Ridge
0.79
036
Size (Kilobytes)
Size (Kilobytes)
Size (Kilobytes)
Figure 5: First 7 plots and last row represents MSE vs memory budget for ridge regression. The shaded region represents one standard deviation. The baselines are vanilla least-square ridge regression (Least Sq. Ridge) using SGD, mean of the training set labels (Mean), Random sampling ridge regression (RS- Ridge), and Frequent direction streaming sketch (FD Ridge) (Shi & Phillips 2021). STORM takes memory less than even single sample and hence can perform risk minimization where even random sampling cannot possibly help. Some of the high dimension data like Fruit shows this predominantly. The last plots of 3rd row represents classification comparing STORM with random sampling. last row we feature transform the data using the Random Fourier Transform (Rahimi & Recht (2008). For each experiment, we scale the number of features 5 times its original size. All results are calculated over 100 runs.
6 DISCUSSION
STORM is a scalable framework to solve regularized ERM problems. It is a memory-efficien framework that supports regularization and streaming, as long as the loss function can be described using LSH collision probabilities. The sketch provides compression ranging from 1/50 to 1/ /10000 of the original size and can take size effectively even less than sample. Additionally, our approach is appealing because it performs well in high dimensions, which can be prerequisite for feature transformations such as random Fourier features (Rahimi & Recht 2008). We expect that STORM be extended to work for important tasks such kernel classifiers and kernel ridge regression. This will greatly expand the modeling options for applications like distributed learning via ERM on edge devices.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. Journal of Computer and system sciences,
1999.
John Bresnahan Ann L.. Chervenak Ian Foster Carl Kesselman Sam Meder Veronika Nefedova Darey Quesnel Steven Tuecke Bill Allcock, Joe Bester. Secure, efficient data transport adn replica management for high-performance data-intensive computer, 2001.
Andrei Broder. On the resemblance and containment of documents. IEEE Compression and Complexity of Sequences, 1997.
Moses Charikar. Similarity estimation techniques from rounding algorithms. STOC, 2002.
Kenneth L Clarkson and David P Woodruff. Numerical linear algebra in the streaming model. In Proceedings of the the forty-first annual ACM symposium on Theory of compuling, pp. 205-214, 2009.
Michael B Cohen, Cameron Musco, and Jakub Pachocki. Online row sampling. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2016.
Ben Coleman, Anshumali Shrivastava, and Richard Baraniuk. Race: Sub-linear memory sketches for approximate near-neighbor search on streaming data. arXiv preprint arXiv: 1902.v999000000000 066877 2019.
Benjamin Coleman and Anshumali Shrivastava. Sub-linear race sketches for approximate kernel density estimation on streaming data. In Proceedings of the 2020 World Wide Web Conference. International World Wide Web Conferences Steering Committee, 2020.
Andrew R Conn, Katya Scheinberg, and Luis N Vicente. Introduction to derivative-free optimization, volume 8. Siam, 2009.
Dennis Corwin. Compilation of literature using apparent soil electrical conductivity with geophysical techniques to measure soil properties. Mendeley Data, 2019.
Anirban Dasgupta, Petros Drineas, Boulos Harb, Ravi Kumar, and Michael W Mahoney. Sampling algorithms and coresets for {ell_p regression. SIAM Journal on Computing, 3865):000--0778, 2009.
Anirban Dasgupta, Ravi Kumar, and Tamas Sarlos. Fast locality-sensitive hashing. KDD, 2011.
Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab Mirrokni. Locality sensitive hashing scheme based on p-stable distributions. Symposium on Computational Geometry, 2004.
Edgar Dobriban and Sifan Liu. Asymptotics for sketching in least squares regression. In Advances in Neural Information Processing Systems, pp. 3670-3680, 2019.
Dheeru Dua and Casey Graff. Australian credit card data set (acr), UCI machine learning repository, 2017. URL http://arrcchiveeeee ics www.cci.e. edu/ml
Bradley Efron, Trevor Hastie, lain Johnstone, and Robert Tibshirani. Least angle regression. Annals of Statistics, 2004.
Amos Fiat. Online algorithms: The state of the art (lecture notes in computer science). 1998.
Mina Ghashami, Edo Liberty, Jeff M Phillips, and David P Woodruff. Frequent directions: Simple and deterministic matrix sketching. SIAM Journal on Computing, 45(5):1762-1792 2016.
Aristides Gionis, Piotr Indyk, Rajeev Motwani, et al. Similarity search in high dimensions via hashing. In Vidb, volume 99, pp. 518-529, 1999.
Michael Goemans and David Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. ACM, 1995.
Rajarshi Guhaniyogi and David Dunson. Bayesian compressed regression. Journal of the American Statistical Association, 2015.
10

---

Under review as a conference paper at ICLR 2022
Sariel Har-Peled, Dan Roth, and Dav Zimak. Maximum margin coresets for active and noise tolerant learning. IJCAL, pp. 836-844 841, 2007.
David Harrison and Daniel Rubinfeld. Hedonic prices and the demand for clean air. Environ. Economics and Management, 1978.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
JK Holland, EK Kemsley, and RH Wilson. Use fourier transform infrared spectroscopy and partial least squares regression for the detection of adulteration of strawberry purees. Journal of the Science of Food and Agriculure, 1998.
Qiang Huang, Guihong Ma, Jianlin Feng, Qiong Fang, and Anthony K. H. Tung. Accurate and fast asymmetric locality-sensitive hashing scheme for maximum inner product search. Proceedings Knowledge Discovery Data Mining, KDD 18, pp. 1561-1570, New York, NY, USA, 2018. Association for Computing Machinery. ISBN 4503555555 doi: 00.1145/3219881932299777 UtLpttts:://ao. 0tt.://001100000000011111 3219819 3911
of the 24th ACM SIGKDD International Conference
Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality. In Proceedings of the thirtieth anmual ACM symposium on Theory of computing. pp. 604 613, 1998.
Piotr Indyk, Sepideh Mahabadi, Mohammad Mahdian, and Vahab S Mirrokni. Composable core-sets for diversity and coverage maximization. In Proceedings of the 33rd ACM AGGMOD-SIGAC, SIGART symposium on Principles of database systems, pp. 100-108, 2014.
Al Jowder, EK Kemsley, and RH Wilson. Mid-infrared spectroscopy and authenticity problems in selected meats: a feasibility study. Food Chemistry, 1997.
Zohar Karnin and Edo Liberty. Discrepancy, coresets, and sketches in machine learning. volume 99 of Proceedings of Machine Learning Research, pp. 1975-1993, Phoenix, USA, 25-28 Jun 2019. PMLR. URL httte:::/p/oooeeddinne
www.m.rr..rree..mmmmmmmmmmmm.eee http:/ssswv///aaannana 9a html
Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2288-2324, 1998. doi: 10. 77.7799...76791.
Edo Liberty. Simple and deterministic matrix sketching. New York, NY, USA, 2013. Association doi: 10.11457448575524876633 URL
for Computing Machinery. ISBN 9781450321747.
htttps://do..zrg wttp:////....1111216777555222222
Lin, Wei-Ming Chen, Yujun Lin, John Cohn, Chuang Gan, and Song Han. Mcunet: Tiny deep learning iot devices, 2020.
Chen Luo and Anshumali Shrivastava. Arrays of (locality-sensitive) count estimators (ace); High- speed anomaly detection via cache lookups. WWW, 2018
Diego Mendez Mena, Ioannis Papapanagiotou, and Baijian Yang. Internet of things: Survey on security. Information Security Journal: A Global Perspective. 27(3) Apr 2018. ISSN 1939-3547 doi: 10.10880113933555 2018.. 1458228. COLLett:/// //xp doi http://xdoooooo/////////o 19393555. 201 8. 1458258
Mohammad Motamedi, Daniel Fong, and Soheil Ghiasi. Fast and energy-efficient enn inference on iot devices, 2016.
Alexander Munteanu, Chris Schwiegelshohn, Christian Sohler, and David Woodruff. On coresets for logistic regression. In Advances in Neural Information Processing Systems, pp. 6561-6570, 2018.
Prectum Nakkiran. More data can hurt for linear regression: Sample-wise double descent. arXiv preprint arXiv: 19/2.002/ 2019.
11

---

Under review as a conference paper at ICLR 2022
Behnam Neyshabur and Nathan Srebro. On symmetric and asymmetric Ishs for inner product search. In Proceedings of the 32nd International Conference on International Conference on Machine Learning Volume 37, ICML' 15, pp. 1926-1934. JMLR.org, 2015.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. Advances in neural information processing systems, pp. 1177-1184, 2008.
Sashank J Reddi, Barnabás Póczos, and Alexander J Smola. Communication efficient coresets for empirical loss minimization. In UAI, pp. 752-761, 2015.
Benwei Shi and Jeff Phillips. A deterministic streaming sketch for ridge regression. International Conference Artificial Intelligence and Statistics, pp. 586-594. PMLR, 2021.
Anshumali Shrivastava and Ping Li. Asymmetric Ish (alsh) for sublinear time maximum inner product search (mips). In NIPS, 2014.
Anshumali Shrivastava and Ping Li. Improved asymmetric locality sensitive hashing (alsh) for maxi- mum inner product search (mips). In Pruceedings of the Thirly-First Conference on Uncertainty in Artificial Intelligence, 15, pp. 812-821, Arlington, Virginia, USA, 2015. AUAI Press. ISBN 9780996643 108.
Christian Sohler and David P Woodruff. Subspace embeddings for the 11 norm with applications. In Proceedings the forty-third annual ACM symposium Theory of computing, pp. 755-764, 2011.
Joaquin Torres-Sospedra, Raul Montoliu, Adolfo Martinez-Uso, Tomar Arnau, Joan Avariento, Benedito-Bordonau Mauri, and Joaquin Huerta. Ujiindorlocc: new multi muilti-biildin and multi- floor database for wlan fingerprint-basse indoor localization problems. Proceedings of the Fifth International Conference on Indoor Positioning and Indoor Navigation, 2014.
Murad Tukan, Cenk Baykal, Dan Feldman, and Daniela Rus. On coresets for support vector machines. arXiv preprint 402:v:200..06469, 2020.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need, 2017.
Alexander Vergara, Shankar Vembu, Tuba Ayhan, Margaret Ryan, Margie Homer, and Raman Guerta. Chemical gas sensor drift compensation using classifier ensembles. Sensors and Actuators B: Chemical, 2012.
Kunjie Xu. Performance modeling of bittorrent pecr-to-peer file sharing networks, 2013.
12

---

Under review as a conference paper at ICLR 2022
A APPENDIX
A.1 PROOF OF THEOREMS
Theorem I. Unbiased RACE Estimator Let X (li,4,(0) Then
B| Σ 1(x,0) var(X) =
Σ vk(xx,00 0)
Proof: The proof is detailed in Coleman(2019) Coleman et al. (2019) and Luo(2018) 88) Luo & Shrivas tava 2018).
Theorem 3. The set of STORM -rroR-aaproxiimall functions SL contains all LSH collision probabilities and is closed under addition, subtraction, and multiplication.
It is straightforward to that STORM can approximate ExED k(x, v) as long as there is an LSH function with the collision probability k(z, y). To prove the theorem, it is sufficient to show that given two LSH collision probabilities ki (I, y) and k2(2, y). STORM sketches can approximate the following two functions
(1) = Σ (z, + k2,,
f2(1) = Σ ki (x, (22,,) FED
FED
Note that one can always write a product of (weighted) sums (En Wn (Ic, y)) (Em Wmiki (I, y)) the sum of (weighted) products Σn,. Wn (2r, kim (2r v)- Therefore, the previous two situations ensure that the set is closed under addition, subtraction and multiplication.
Addition and Subtraction: Because of the distributive property of addition,
Σ k1 () k2 RDD
Σ (x( = Σ k2(2,)) RED
RED
One can then construct a STORM sketch S₁ for the (1 y) summation and a second STORM sketch S2 for (2 y) summation. We can estimate any linear combination of k (z. y) and (2 y) by with a weighted sum of S₁ and S2.
To approximate sums over the product & (I. (2, y). we rely LSH hash function compositions. Suppose we have an LSH function (x) with collision probability kn (z. y) and (2(z) with (2 y). Consider the hash function 1(x) injective (or unique) mapping from Z > Z. An example of such a mapping is the function (a, pivl where pı and p2 coprime. Since the mapping is injective, this means that 1(x) = (()) only when (xx) = (v) and (xx) = 1z(v). Therefore, Pr[[(z) = [(v)] = (z)
Multiplication:
(2=), 12(4)) where x (a, b) is an
(((()) 12())]
Make the choice of the LSH functions 1 and l2 independently, so that the probability factorizes
(r) 4 (x))Pr/((()) (x))] ki (1 (2x,)))))) y)
Therefore, (2()))
construct STORM sketch for the product using the LSH function 1(x:
Theorem 4. When p 2 2, the PRP collision probability g(10, 11,, [x, v)) convex surrogate loss for the linear regression objective such that
arg min ((0, - -1], |x, vl) = arg min -annllyxxx xxx x6|
0
Proof: For the surrogate ERM problem to have the same solution as the linear regression ERM problem, it is sufficient to show two things: that the surrogate loss is convex and that the global minima of the surrogate loss and the linear regresssion loss appear in the same location. The surrogate loss (C(B, x, 7)) is
o(10, - (x, v)) = (11 1- cos ((10, -1], [1,[x,10 m)))
1 (11 1 cos (-((0, - -1]. [x, v1>)
- 2
π
13

---

Under review as a conference paper at ICLR 2022
Surrogate loss
Prst Feet
Sed teet
L2
0.45
g-d g
11380 14L
01/00
g(0,(xx0)
0602
3
330 6575
-0.5 0.00
375 1.20
0.0
1.0
8.5
<B.jxyya
Figure Left: Surrogate regression loss (STORM regression loss) for different values p. It has the highest convexity near 4. Right two: Mcan square error with varying sketch size with different on two real world datasets. We observe that p=3,4 works the best.
For the sake of notation, we will put = [0, -2,.11,b- b [x, vl. and
(a, b) = (1 cos '(10, - (x),,x))))x)
1 2 bb) L(a, b) = [ b)2d
We will use the fact that
b
vef(a,b) V.f(a.))-Vofla.-b x =
(a. b)l
Location of Minima: The minimum of the surrogate loss is same the minimum for least squares linear regression. Using the chain rule, the gradient of the surrogate loss is
VaC(a, p (f b)- "- f(a, -b)""1)
2T /1 (aa b)l2
When p = 1, the gradient is always zero. When p 2 2. the derivative is zero when (a, b) ((0, 11] xx v)) 0 because that is where f(a, b) f(a, b).. Thus, the surrogate loss has the same minimizer as the least squares loss.
Convexity: At index (i,j), the Hessian of the surrogate loss is
a daj
δ b. (f(a,, (f(a,,)"~ 1 f(a, -b)--) da,"
C2 b)l(s)
b)]; [V)
2x /1 ((a, b)
Thus, the Hessian
V.C(a,b) bv_, pf(a, b). pf(a, -b)--1 2x (a, b)l²
The gradient
V. pf(a. - pf(a, -b)p-1
2n 2T (a, b)12
plp - 1)f((a b)0-
p(p 1),((a -b)--
V Vaf(a.b) +
Vof(a, -b)
2T 2T - ((a, b)1²
2T / (a, b)(2
+ (pf(a, b)p pf(a, 1b)--1) V.
2 2T - ((a, b)12
Simplifying, we obtain
bTb p(p- (a, b)n 2 p(p - 1)f(a, -b)-~
+ (a, b) pf(a, b)p-1 + pf -b)--1 (1-18 (1-((a, b))3)3/2
2T
क ( b)
14

---

Under review as a conference paper at ICLR 2022
Classification Losses
4.0
Hinge Loss
3,
Logistic Loss
Exponential Loss
3.0
One (Bayes Optimal)
2.5
STORM Loss, P
15-
05
0.0
-1.00
-0.75
-0.50
-0.25
0.75
1.00
Figure 7: Comparison of various classification-caliiatee loss functions, including the STORM classification loss.
Which gives the following expression for the Hessian
ViC(a, b) = b"
where
1 (p(p 1)f(a, b)p-2 -p(p 1)5(a, -b)-- + (a, b) (/.(ba + ppf(a. bb)-1 (a, b) ?)3/2
p(a.b) b)
2T
x(1 (a, 2)
for p 2 2 p(a, b) > V(a, b) E (-1, Hence, the Hessian is positive semidefinite and the function is convex in a. Also note that the function is convex in since the restriction of the last dimension of a to 1 is the restriction of a convex function to a convex set. Refer Figure a].
Theorem 2. Consider labels y 1-1, The loss function g [x, vl) for the linear hyperplane margin loss and is STORM-approximaba
classifier is classification-calibee
g(0, [x. y]) 2 (1 (1- π
cos ((y((,x))
Proof. First, we show that the loss cuasiffcation-caliirie Then, we show that the loss can be estimated using STORM.
Loss Maasification-Calireaa (tt) to be caasification-calibran is for ((t)) < 0 at = O. Here, f = yh(x,, where h(x)) is the model. For linear hyperplane classifier, h(x)) (f, x). The loss is therefore
A necessary and sufficient condition for conve loss function
1 cos (-t) P
1
Φ(t) = 2"
π
@(t) is convex when 2 2 for the same reasons discussed in the proof of Theorem 4. Note that the simple asymmetric LSH for the inner product that have used throughout the paper requires t RE [-1,1]. The derivative is
1 cos cros--((-s) (-1)
dt ( 2
TVI
2 For non-convex @tt), ), the sufficient conditions are more complicated. Thheee are other asymmetric inner product ISH functions without this requirement, and in practice one usually scales the data make the condition true.
15

---

Under review as a conference paper at ICLR 2022
At the origin, di d(t) is -1/TT. Therefore, the loss is classification calibrated. Figure 7 b) compares our STORM surrogate classification loss against popular margin losses.
Loss is STORM-ApproXimable where we premultiply x by yy The collision probability under this LSH function is
Consider the asymmetric LSH function for the inner product
k(0,x) x) = (1
(10,-1/3 -yx))
cos
as desired.
Theorem 5. Let g(0) is the median of means estimate on the STORM sketch, with R rows, then with probability more than 1
lØ(0) g(0))s 6 EXED vk(x, 0)
Vlog(1/8)
VR
Proof. Consider the following axiom-
Let Zi.... R be R i...d random variables with mean E μ and variance S o². Divide the R variables into groups that each group contains R/g elements, and take the empirical average within each group. The median-of-meant estimate ja is the median of the group means. If g 8log(1/6) and R/g, then the following statement holds with probability 1 5.
1/0
VR R
This proof is given in Alon et al. 1999) the proof of Theorem 2.1 (which is slightly more general version of the statement ahove).
Now, et Z(g) be the median means estimate constructed using the R unbiased estimators of the sketch with R rows. Then with probability 1- 8,
EXED Vk(x, Vlog(1/5)
lō(0) ,(0)}s 6
VR
From Theorem 1, we know that a S EXED V 0)
Substituting this variance bound into the given Lemma proves the theorem.
Required number of repetitions: The square root of collision probability / (xx 0) < always. Hence, in the worst case the value of ExED Vk(x, 8) is N. For lØ(0) g(0)l Collog(1/8), we need number of sketch rows R = ((N)).
SGD convergence and sketch size for hyperplane based method: Assuming that 1) g(0) bounded below, 2) The gradient is L-Lipschiz continuous and 3) the gradients bounded as
E (0)1² < o², with constant step size n will get the error (g(0,) g(0")) bounded by ((1/t) + +O))
For simplistic assumption that we are drawing a new sample every time the total number of steps equivalent to the number of repetitions R in the sketch. Hence the error at the end of the iteration will be bounded in terms sketch size by (()RR) + O()).
A.2 EXPERIMENTS
A.2.1 EXPERIMENT ON 2D SYNTHETIC DATASET
We plot the estimated parameter from the STORM on 2D synthetic data (Train: 1600 points, Test: 400 points) generated from Gaussian distribution. Refer Figure
16

---

Under review as a conference paper at ICLR 2022
Syethdi: (ra1600
Spctodic (1w1600
Sydtedk 1U0RE clss
2.33
STORM
STORM
233
-32
13
1.0 -.7
259
0225
035
3.0
123
x1
X1
Figure 8: (a) Regression with linear model. (b) regression with linear model and Random Fourier feature Rahimi & Recht (2008) mapping, and (c) classification STORM losses on synthetic 2D datasets.
A.2.2 NON LINEAR REGRESSION ON SYNTHETIC DATA:
kytthatic 0001000
oyttetk ded)
sytthdic 1600
STORM
STORM
STORM
34
20
com pression
6600
-35
compression
X compression
2560
-035 -009
-0.25
0.0
X0
4.50
-2.2 -035
-123 -5.75
+2.9
10.35
0.09
0.5
Figure 9: The random Fourier feature maps the input dimension to a higher dimension for linear model training. Here map it to 10 dimension space and project back the solution in 2D. The figure shows the learnt model with different STORM sketch sizes. On the given synthetic data, STORM achieves compression of 1/256 times to
1/ /6660 times.
Algorithm 3 Zero order gradient descent
Input: STORM sketch RRx constructed with
gas test RMSE
PRP. number of queries to approximate the gradient, step size 7 and sphere size σ)
Result: Linear regression parameter 0
Result: Initialise fu <- d
STORM Zero Order
for number of iterations n = I,...N do (v1, 02 Uk random vectors the a-sphere centered
RMSE
Compressed
Least Sq Ridge
{51, .5x = { Query (1t) Quorys(uul)
10:1
Approximate gradient ((0) mean 82, .5.) Update 0,, f (f))
Project last dimension of onto the constraint
Size (Kilobytes)
end for
Figure 10: Left:: Shows the algorithm for zero order gradient descent. Right: The compressed PRP sketch (which uses Hyperplane based gradient descent) is Rp bits in size. And on a experiment with real data we found out that it give acceptable model with very less sketch size.
A.2.3 COMPARISON WITH ZERO ORDER GRADIENT DECENT
We perform derivative-fo free optimization Conn et al. 2009) here on the original STORM sketch. Here, the black-box access the loss function of interest (or its sharp approximation) is sufficient. For the descent algorithm, initialize 0 zeros in d dimensions. The additional dimension
17

---

Under review as a conference paper at ICLR 2022
due to querying the sketch with (8, -1] rather than [0]. We compute the approximate gradient by querying the sketch with equidistant points in ball around 0 and update the parameter. After each iteration, we project the last dimension of 0 back onto the constraint 02+1 -1 This takes It B size, with an additional factor of sketch cell bit precision. Hence it is more memory intensive than the hyper-plane based stochastic gradient descent algorithm. Refer the figure below.
A.2.4
NON-REGULARISED LINEAR REGRESSION
airfoil (d 9, N 1.5k)
autos (d 26, N 159)
10'
10a
STORN
Handom Sampling
Opoial
MSE
Nean
MSE
10-4-
10-1
SIUIM
Random Sampling
Leverage Samcting
10
Optimal
10t
Memory (bytes)
Memory (bytes)
Figure 11: Here, we report the mean square error for our method without any regularization, when compared with baselines at a variety of memory budgets.
observe double-descent phenomenon for sampling baselines, explaining the peak near the intrinsic dimensionality of the problem. This sample-wise double descent behavior was recently proved for linear regression by Nakkiran (2019). STORM does not experience the double descent curve in practice because the entire dataset (not just subsample) is used to minimize the loss. We perform favorably against baselines in memory regimes affected by double descent and STORM performs competitively in other memory regimes. We also observe that the & found using STORM converges to the optimal 0 under least-squares ERM. The datsets use are taken from UCI repository.
In Figure 11
18


Reviews:
[{"review_id": "zAQGcSBJEfM", "reviewer": "Reviewer_MTPW", "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": "Here is the detailed comments.\n\n----------------------------pros\n1. Overall, I think this paper is well-written. \n2. In experiments, the proposed method STORM achieves promising performance although the datasets and models are simple.\n3. Theoretical analyses are provides to justify the use of sketching to estimate the surrogate loss with high probability.\n\n----------------------------cons\n1. The technique novelty is limited since previous work (Coleman & Shrivastava, 2020) has used LSH to approximate kernel density estimation on streaming setting. \n2. For the proposed STORM, there are so many approximations --- sketching be LSH, surrogate loss function approximate the original loss, and heuristic approximate optimization problems. Besides, it is specialized for the linear model. Thus, these features makes it complex and not general for other problems and models. \n2. Why to prefer an asymmetric LSH over the symmetric one? Please give more specific explanations in the online learning setting.\n3. Why to use these surrogate loss function? Although authors give intuitive explanation, more formal theoretical supports might be better. Moreover, in my opinion, the proposed surrogate loss function can also be used in the original data without sketching. Experiments can be done to see whether it is specified for this problem and can justify the effectiveness and efficiency of LSH sketching more fairly by comparing them.\n4. This paper lacks theoretical analysis about generalization and the convergence property of the heuristic optimization algorithms.\n5. It also lacks the experimental results in the streaming setting w.r.t. the time step.\n\n----------------------------Minor comments \n\nThis paper seems a bit rushed since there are many typos. For example, in Sec. 2.1, the head of the second line should not be $\\mathcal{D}$.  Besides, the reference format seems strange.", "summary_of_the_paper": "This paper considers the online risk minimization setting. To reduce the memory cost and accelerate training, this paper proposes a new sketching algorithm (i.e. STORM) based on the locality sensitive hashing (LSH) technique, which mainly includes two steps -- sketching and training. In particular, it provides two STORM surrogate losses for linear regression and classification, respectively. Besides, it also provide theoretical analysis to justify the use of sketching to estimate the surrogate loss with high probability. Experimental results illustrate the effectiveness and efficiency of STORM over other baselines.", "summary_of_the_review": "Overall, I think, while the novelty is limited, the proposed method is complex with many non-clear approximations, which makes it not general. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "lwI3mSWVyf1", "reviewer": "Reviewer_7LQM", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "# Quality and Clarity\n\nThe paper is clearly written, with very few typos (listed below). Nice intuitions are regularly given, and I especially liked the \"Intuition\" paragraph in Section 3. Good writing!\n\nThe problem of approximate ERM with low memory is theoretically compelling, and I _like the idea_ of finding approximate ERM solutions using less memory than a single sample, but I don't understand when this memory constraint is actually realistic? When can a machine compute hash functions for the all data, but cannot store a single sample (or $O(1)$ samples) in memory? I ask because the experiments are not evidently compelling, but they do use very very little space. So, when is this extreme setting compelling?\n\n# Theoretical Basis\n\nThere are some odd points in the theory given behind their algorithm and data structure:\n- Other than using non-standard hashing functions, what distinguishes the STORM sketch from the RACE sketch? They seem the exact same to me.\n- Theorem 4 shows that the STORM optimum recovers the Least Squares optimum for the linear regression problem. You also use STORM for classification; do you have any theory to justify why STORM should work for classification?\n- Theorem 5 has this $\\sum_{x \\in \\mathcal D} \\sqrt{k(x,\\theta)}$ term. How should I interpret this? It is just the standard deviation of the RACE sketch? Why not just upper bound this by $N$ in the numerator? When is this numerator much smaller than $N$?\n  - Also, is this reuslt\n- Theorem 5 mentions the Median-of-means estimate, which is formally defined in the appendix, but I would recommend adding it into the body of the paper. Why is estimator mentioned, if it doesn't seem like you use it in the experiments or optimization? Do you use median-of-means in the optimization or experiments?\n- Is the choice of $\\tanh$ on page 6 totally heuristic?\n\nMy *review of the theoretical results* and data structure design is that the results are believable and seem correct, but lack technical novelty. Some of this (e.g. Thm 5) is not obviously distinct from prior work (e.g Thm 1's variance). Some of what I would like to see is not shown (e.g. correctness of using $\\tanh$, classification version of Thm 4). Weak overall.\n\n# Experimental Evidence\n\nThe experimental evidence continues to be a bit confusing. I don't really understand why this is showing that STORM is a good model in practice. There are 12 plots showing statistical error vs. amount of memory used, but very few of these plots tell a compelling story:\n_In the following, I refer to plots in the left-to-right then top-to-bottom order, so the \"4th plot\" refers to the first plot on the second row._\n- Plots 2, 3, 4, 5, 6, 7, 9, 10, 11, and 12 suggest that as memory capacity increases, STORM does *not* approach the true solution. Instead, the variance gets small while the bias remains large.\n- Plots 3, 4, 6, 7, 10, and 12 even further show that STORM returns a model whose error is closer to a naive mean than an actual Least Squares solution.\n- Plots 8 and 9 don't have a benchmark to show what is achievable with unbounded memory. Plot 9 is fine, since near-perfect accuracy is possible, but plot 8 sees maximum accuracy 0.75, and it's not obvious this is competitive with a larger memory model.\n- Plots 1 and 2 don't have legible y-axes. There's too few written ticks, and for some reason only these two plots are on a log/log scale.\n\nSo, it seems that experimentally, STORM uses very little space to be slightly better than computing a naive mean of the data. I don't see how this is compelling, especially since I'm not clear why the restriction on the memory has to be so intense. As far as I am aware, 1 Mb of data is very very cheap today, so what's the utility of working on the order of kilobytes if the error of the model is so huge?\n\n_My conclusions / overall review is in the \"Summary of the Review Section\"_\n\n--- \n## Minor Notes\n- Use `\\citep{...}` instead of `\\cite{...}` when adding a citation that doesn't naturally flow in the grammar. This is (e.g.) most of the citations you use in the introduction.\n- [Page 1, end of \"Linear Sketches\" paragraph] Why is it that sketching cannot accommodate regularization? If we can approximate $\\|Ax-b\\|$ for all $x$, then we can also approximate $\\|Ax-b\\| + \\|x\\|$, right?\n\n1. [Page 1, end of first paragraph]: The \"Bill Allcock (2001)\" citation seems weird. The citation in the references also seems formatted wrong. Should this be \"Breshanan et al\"?\n1. [Page 3, first line of section 2.2]: It should be \"A locality sensitive hash (LHS) function\" not \"A Locality sensitive hashing function\" (capitalization, and \"hash\" is more common than \"hashing\" but that one's personal preference)\n1. The Section 3 Intuition block is written _really_ nicely. Props.\n1. [Page 4, bottom equation]: $p$ isn't defined, and it's not intuitive at all that some parameter should be floating in the exponent.\n1. [Page 5, Thm 2 equation]: Same as above\n1. [Page 6, in the sentence \"We now have the...\"]: The left $\\|$ symbol is missing in the inline math.\n1. [Page 7, Thm 5]: Should be \"Let $\\hat g(\\theta)$ be the\" instead of \"Let $\\hat g(\\theta)$ is the\"\n1. [Page 8, end of Figure 5 caption]: Specify _here_ that you increase the feature space to attempt to linearize the problem, not just to introduce spurious dimensionality (which is kinda how it reads as is)\n1. [Page 9, Table 1 caption, last sentence]: \"The dimensions in brackets\" not \"The dimension in bracket\"", "summary_of_the_paper": "The paper considers approximately computing ERM problems for real data, with an emphasis on regression and classification, in the *very low space* regime (most experiments are below 1Kb). This is done my maintaining a standard locality sensitive hashing table, but with specialized hash functions that allow for computing a surrogate for common regression and classification ERM objectives. \n\nDue to the extreme space constraint, optimization is done with a heuristically characterized SGD. A significant amount of experiments is presented.", "summary_of_the_review": "The paper has weak theoretical and experimental components. The theory doesn't obviously show anything new of sufficient generality. The data structure appears to be the same as in prior work on LSH. The experiments suggest that using the STORM estimator is only slightly better than returning the mean of your data.\n\nI don't see the strengths of this paper anywhere. I got more and more confused about this paper the more I read.\n\nIt's well written, but I don't see the substance beneath the nice writing.", "strength_and_weaknesses": "", "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": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "TC45aTgqfIO", "reviewer": "Reviewer_8LGD", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths: \n-Impact: The proposed flexible method reduces the scale of data set and the dependence of model training on hardware performance, which may be helpful for distributed learning in the future.\n-Experiment: The author has done relatively sufficient comparative experiments, including classification and regression under linear and nonlinear conditions with several datasets.\n-Writing: Overall, the manuscript is well-written and addressing a relevant problem by proposing an interesting learning method suited to edge devices.\n-Reproducibility: Key resources (e.g., proofs, code, data) are available and key details (e.g., proofs, experimental setup, parameters selection) are sufficiently well-described for competent researchers to confidently reproduce the main results.\n\nWeekness:\n-Experiment: Important details missing, which can help the paper quality significantly. Including the MSE and accuracy criteria, time complexity and space complexity of different methods should also be discussed. During inference, is the proposed approach less computational expensive than baseline approaches? It would be worth reporting the run-time (e.g in seconds) or computational complexity or number of learnable parameters.\n-Parameters: The proposed approach STORM is heavily based on some of the hyper-parameters, for instance, p, there is no empirical evidence that how the performance of the model will vary by changing p. Besides, the value of p is different for different datasets. Ablation experiments are helpful to validate the robustness of the selected value for p instead of the two regression experiments for discussing P values with similar datasets in Fig. 6\n-Description: In general, there is a lack of detailed explanation of replicates and statistical methods used in the study.\n-Performance: Although this edge computing method reduces the dependence on hardware, the reduction of accuracy seems to have a great impact from the experimental results in this paper. Can it be compared with more similar methods to highlight the advantages of this paper? Some results in Figure 5 are worse than the benchmark method. Is it necessary to have some discussion?", "summary_of_the_paper": "In this paper, the authors focus on reducing the cost of conventional ERM training and propose a new framework, STORM, which integrates the approaches of locality sensitive hashing and sketches. Besides, the authors use specific optimization algorithms to solve that this framework can’t be directly applied to popular classification and regression tasks. The experimental results prove that the proposed procedure can achieve better results compared to the baselines in the operational environment of low performance and low memory.", "summary_of_the_review": "The paper contributes some new ideas to reduce the compuation complexity of ERM. The experimental evaluation on STORM is adequate, and the results convincingly support the computaion strategy  of locality sensitive hashing and sketches.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made 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": "AByNuVWmyaI", "reviewer": "Reviewer_yRcK", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper proposes an online sketching algorithm (STORM) for empirical risk minimization(particularly for linear regression loss functions), which only needs to save the integer count values in the sketch. Particularly, it uses the local-sensitive hash functions to divide the space into several regions and save the integer counts values over the regions for the data points. Then, the author shows that how the count values related to a class of the surrogate losses for the $\\ell_2$ loss and how to evaluate a hypothesis $h_\\theta$ using such sketch, and how to optimize the $\\theta$. Finally, the author gives an empirical evaluation with ridge regression and classification. \n\nOverall, I think the method the paper proposes is interesting and the author provides the corresponding analysis. The paper is well-written and easy to follow up. The empirical results also show the advantage of this method.  However, I have the following concerns/questions:\n\n(1) The conclusion section and the experiments are focusing on the regularized ERM problems, while most of the theoretical analysis seems to be for the non-regularized version. Is the analysis still hold for the regularized ERM case?\n\n(2) The related-work section of the linear sketch seems to be incomplete and inaccurate. In my understanding, the Sketch-and-Solve technique also holds for the ridge regression for the case when $n >> d$, see, e.g., the Theorem~16 of [1](this paper also studies the case when $n << d$, but it seems can not be supportive for the streaming setting). I think it should be added to the experiments as a baseline, if I do not have some misunderstandings.\n\n(3) I am a little confused about the theoretical advantage of this method. In my understanding, for the case when $n >> d$ the linear sketch can get a good approximation in roughly $O(d^2)$ space, while STORM needs $O(N^2)$. Hence the advantage of the STORM is for the case when $n << d$. Is the above statement correct?\n\n(4) I am curious about the empirical comparison for the non-regularized version, and I think it can be a good supportive part(not necessary), because the theoretical analysis also holds in this case, and we will have more baselines at this time.\n\nReference:\n\n[1] Haim Avron, Kenneth L. Clarkson, David P. Woodruff. Sharper Bounds for Regularized Data Fitting.", "summary_of_the_paper": "The paper proposes an online sketching algorithm (STORM) for empirical risk minimization(particularly for linear regression loss functions), which only needs to save the integer count values in the sketch. The author also gives an empirical evaluation with ridge regression and classification. ", "summary_of_the_review": "As stated in the previous section, I think the method this paper proposes is interesting, while there are still some perspectives that can be further improved. Hence currently I tend to vote a 5 for this paper. I am willing to raise the score if I have some misunderstandings or some of the concerns can be addressed.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made 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": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposed a sketching algorithm for empirical risk minimization (ERM) for linear regression and classification. The technique is based on LSH with non-standard hash functions. The reviews indicate that the paper is well written and easy to follow. However, there are several concerns raised regarding its quality. A major one regards the novelty of the paper. 

MTPW: “The technique novelty is limited since previous work (Coleman & Shrivastava, 2020) has used LSH to approximate kernel density estimation on streaming setting.“, 7LQM: “My review of the theoretical results and data structure design is that the results are believable and seem correct, but lack technical novelty.” “Other than using non-standard hashing functions, what distinguishes the STORM sketch from the RACE sketch?”

An additional concern is a claim of weak experimental evidence. There seems to be a need for more thorough experiments isolating different components rather than the system as a whole, and in addition the bottom line results provide only a slight lift over a naive baseline (7LQM:  “The experiments suggest that using the STORM estimator is only slightly better than returning the mean of your data.”). 

Whether it is the case that the techniques should be improved or that these concerns could be addressed by improving the presentation of the paper, the conclusion is that the paper now is not ready to be published.
Decision: Reject