Dynamic Least-Squares Regression
Authors: Binghui Peng
Shunhua Jiang
OMRI WEINSTEIN
Venue: ICLR 2022 Submitted (2022)
Keywords: Least squares regression
dynamic algorithm

Abstract: In large-scale supervised learning, after a model is trained with an initial dataset, a common challenge is how to exploit new incremental data without re-training the model from scratch. Motivated by this problem, we revisit the canonical problem of dynamic least-squares regression (LSR), where the goal is to learn a linear model over incremental training data. In this setup, data and labels $(\mathbf{A}^{(t)}, \mathbf{b}^{(t)}) \in \mathbb{R}^{t \times d}\times \mathbb{R}^t$ evolve in an online fashion ($t\gg d$), and the goal is to efficiently maintain an (approximate) solution of $\min_{\mathbf{x}^{(t)}} \| \mathbf{A}^{(t)} \mathbf{x}^{(t)} - \mathbf{b}^{(t)} \|_2$ for all $t\in [T]$. Our main result is a dynamic data structure which maintains an arbitrarily small constant approximate solution to dynamic LSR with amortized update time $O(d^{1+o(1)})$, almost matching the running time of the static (sketching-based) solution. By contrast, for exact (or  $1/\mathrm{poly}(n)$-accuracy) solutions, we show a separation between the models, namely, that dynamic LSR requires $\Omega(d^{2-o(1)})$ amortized update time under the OMv Conjecture (Henzinger et al., STOC'15). Our data structure is fast, conceptually simple, easy to implement, and our experiments demonstrate their practicality on both synthetic and real-world datasets.

Under review as a conference paper at ICLR 2022
DYNAMIC LEAST-SQUARES REGRESSION
Anonymous authors Paper under double-blind review
ABSTRACT
In large-scale supervised learning, after a model is trained with an initial dataset, common challenge is how to exploit new incremental data without re-training the model from scratch. Motivated by this problem, we revisit the canonical problem of dynamic least-squares regression (LSR), where the goal is to learn a linear model over incremental training data. In this setup, data and labels (A (4), (()) E 2xd 'R' evolve in an online fashion (t >> d). and the goal is to ef- ficiently maintain an (approximate) solution of min (A)x)(()) - b for all E [T'. Our main result is dynamic data structure which maintains arbitrarily small constant approximate solution to dynamic LSR with amortized update time Odd +o)),, almost matching the running time of the static breeching-baseeee so- lution. By contrast, for exact (or 1/ poly(a))aacuurayy) solutions, we show sepa- ration between the models, namely, that dynamic LSR requires ((dd-o((1) amor- tized update time under the OMv Conjecture (Henzinger et al., STOC'15) Our data structure is fast, conceptually simple, easy to implement, and our experiments demonstrate their practicality on both synthetic and real- datasets.
INTRODUCTION
The problem of least-squares regression (LSR) dates back to Gauss 1821 (Stillr 198 18,, and the backbone of statistical inference (Hastie et al. 2001). signal processing Rabiner & Gold 1975). convex optimization (Bubeck 2013). control theory (Chuil 1990) and network routing (Lee & Sidford 2014 Madry 2013). Given overdetermined (n >> d) linear system A Raxd b IR" the goal is to find the solution vector x that minimizes the mean squared error (MSE)
min XER"
||Ax bll2-
Among many other loss functions (e.g., , (p) that have been studied for linear regression, fz-regression has been the most popular choice as is at the same time robust outliers, and admits high- accuracy efficient solution.
The computational task of least-squares regression arises naturally in high-dimensional statisties and has been the central of focus. The exact closed-forn solution is given by the well-known Normal equation x* (AT AA A b. which requires (nnd) time to compute using naive matrix- multiplication, or O (ndd-11 z ( time using fast matrix-multplication (FMM) (Strassen
1969 for the current FMM exponent of w 2.37 (e Gall 2014 Alman Williams 2021).
Despite the elegance and simplicity of this closed-for form solution, in practice the latter runtime is often too slow, especially in modern data analysis applications where both the dimension of the feature space (d) and the size of datasets (n) are overwhelmingly large. A more modest objective in attempt to circumvent this computational overhead, to seek an e-accurate solution that satisfies
|| Ax
bll2 < (1+ min ||Ax- xE2d
This was the primary motivation behined the development of the sketch-and-solve paradigm, where the idea is to first compress the matrix into one with fewer (~~ d/e²) rows and then compute the standard LSR solution but over the smaller matrix. A long line of developments on this framework culminates in algorithms that run in close input-sparsttn sparsity time (Sarlos) 2006 Clarkson Woodrufi] 2017 Nelson & Nguyēn, 2013 Chepurko et al. 202T). In particular, a direct application of sketch- and-solve yields algorithm runs in Ó(nnz A]e + d²) which is near optimal in the "low
In this paper use Ö(-) to hide polylogarithmic terms, and we Oz(-) hide poly de terms.

---

Under review as a conference paper at ICLR 2022
precision" regime (c 1/ poly(log d)). Interestingly, when combined with more sophisticated ideas of preconditioning and (conjugate) gradient descent, the runtime of this algorithm in terms of the error e can be further improved to ((nuz(A) (A) log(1/e) + d²), which yields a high precision algorithm, i.e., it can efficiently solve the problem to within polynomial accuracy 1/ poly
Dynamic least-squares In many real-world scenarios of the aforementioned applications, data is evolving in an online fashion either by nature or by design, and such upplications require maintaining adaptively, where rows of the data matrix and their corresponding lahels (A(t), (t) b())
the solution [
arrive one-by-one incrementally. This is known as the dynamic least-squares regression problem.
The origins of dynamic least-squares regression was in control theory of the 1950's (Plackett 1950),
in the context of dynamical linear systems. In this setup, the data matrix [A (9, (+) corresponds to the set of measurement and it evolves in an online (incremental) fashion, and the goal is to efficiently maintain the (exact) solution to a noisy linear system b == x9)x(1 + g(t) without recomputing the LSR solution from scratch. The recursive least-squares (RLS) framework and the celebrated Kalman filter (Kalman| 1960) provide a rather simple update rule for maintaining an exact solu- tion for this problem, by maintaining the sample covariance matrix and using Woodburry's 's identity (which assert that an incremental update to [A (1), b(o] translates into a rank- update to the sample covariance matrix), and hence each update can be computed in (d²) time (Kalman 1960).
Beyond this classic motivation for dynamic LSR, more timely motivation comes from modern deep learning applications: Most neural networks need to be frequently re-trained upon arrival on new training data, in order to improve prediction accuracy, and it is desirable to avoid recomputing weights from scratch. This problem of efficient incremental training of DNNs has been studied before in elastic machine learning (Liberty al., 2020) and in the context of continual learning (Parisi et al.] 2011)p. Our work sheds light on this question by analyzing the minimal computational resources required for & mosimiininizttion.
Despite the rich and versatile literature on static LSR, the understanding of the dynamic counterpart was so far quite limited: The previous best known result requires (dd) amortized update time (by a direct application of the Woodbury identity). The basic questions we address in this papers are:
Is it possible to achieve faster update time for maintaining an exact solution? How about small- approximate solution - Is it then possible to achieve amortized (dd) or even input-sparsin time?
In this paper, we settle both of these questions and present an essentially complete characterization of the dynamic complexity of LSR.
1.1 OVERVIEW OF OUR RESULTS
Our first result is a negative answer to the first question above of maintaining exact (or polynomial- accuracy) LSR solutions in the dynamic setting We prove that Kalman's approach is essentially optimal, assuming the popular Online Matrix-Vector (OMv) Conjecture (Hezzinger et al. 2015
Theorem 1.1 (Hardness of exact dynamic LSR, informal). Assuming the OMy Conjecture, any dynamic algorithm that maintains an e 1/ poly (d)ppppoxiimate solution for the dynamic LSR problem over T = (d) iterations, must have ((L amortized update time per iteration.
Theorem separates the static and the dynamic complexities of the exact LSR problem: As men- tioned above, the static problem can be solved by batching rows together using FMM in time O(Td=-1), whereas the dynamic problem requires ((Td²) by Theorem 1.1 Indeed, the impli- cation Theorem is stronger, it also separates the static and dynamic complexity of approximate LSR problem under the high precision regime, it asserts that a polylogarithmic dependence on the precision (i.e. d poly (log(())))/)) on update time is impossible (assuming OMv), in sharp contrast to the static case.
We next focus on an approximate version of this classic online problem, dynamic E-LSR, where the goal is to efficiently maintain, during all iterations t E [T]. an c-approximate solution under incremental row-updates to A (f) and labels b(t), where efficiency is measured by the amortized
"This conjecture postulates that multiplying fixed x matrix A with an online matrix B, column-by by- column (A (AB), requires d3-o(1) time, in sharp contrast to the batch setting where this can be done using FMM in d & d time. See Section
2

---

Under review as a conference paper at ICLR 2022
update time for inserting new row. A natural complexity benchmark for this dynamic problem is the aforementioned best static sketch-and-solve solution, which for n T is ((nz (A (T)) + d=) = ((nz((A)))) for >> d. Our main result is a provably efficient and practical dynamic data structure, whose total running time essentially matches the complexity of the offline problem:
Theorem 1.2 (Main result, informal version of Theorem 3.I. For any accuracy parameter e > O, there is randomized dynamic data structure which, with probability at least 0.9, maintains approximate solution to the dynamic LSR problem simultaneously for all iterations I. E [T]. with total update time
O unz( 2 A (T) log(T)++ = log logg())).
Theorem almost matches the fastest static aketching-based solution, up to polylogarithmic terms and the additive FMM term. When T >> d, this theorem shows that amortized update time of our algorithm is (ld+)))))
1.2 RELATED WORK
Sketching and sampling The least squares regression as a fundamental problem has been exten- sively studied in the literature. A long line of work (Ailon & Chazelle, 2006 Clarkson & Woodruff
2017 Nelson & Nguyēn, 2013 Avron et al. 2017 Cohen et al. 2015 Woodrufi] [214 2021 have
focused on using dimension reduction technique (sketching or sampling) speedup the computation
task, culminates into algorithms that run in Ó(nnz(A) ( log(1/c) + d=) time (Clarkson & Woodduff]
2017 See Appendix A for detailed discussions.
Regression in online, streaming, and sliding window models Least-squares regressions have also been studied in various computational models, though the focus of these models are generally not the (amortized) running time. Our algorithm uses techniques developed by Cohen et al. 2020), where they study the regression problem in the online model, with the goal of maintaining a spec- tral approximation of data matrix in the online stream. Their algorithm only needs to store (z(d) rows but the amortized running time is still ((d²) (see Section 3.1 for detailed discussions). In the streaming model, the main focus is the space complexity, and a direct application of random
Gaussian sketch or count sketch reduces the space complexity to O and it is shown to be tight Clarkkson Woodruff 2009). Recent work of (Braverman et al. 2020) studies regressions and other numerical linear algebra tasks in the sliding window model, where data come in an online stream and only the most recent updates form the underlying data set. The major focus of a sliding window model is still the space complexity, and there is amortized running time guarantee.
Disparity from online learning Our work crucially differs from online learning literature (Hazan) 2019), in that the main bottleneck in online nggett-inimizztioon and bandit problems is information- theoretic, whereas the challenge in our loss minimiziinn problem is purely computational. See Appendix A for detailed discussions.
PROBLEM FORMULATION
In a dynamic least-squares regression problem, initially, we are given a matrix ( E Re together with vector (0)) R At the t-th step, new data of form ((a()),, 300) e Rd x R arrives, and the goal is to maintain an e-approximate solution. A formal description is provided below, where assume no d I for simplicity (see Remark 2.3
Definition 2.1 (Dynamic least-squares regression). Let d E N and E [0,1) )) be two fixed parame- ters. We say an algorithm solves e-approximate dynamic least squares regression if
The data structure is given a matrix A (0) E [dd+1)xd and vector (()) E Bd+1 in the preprocessing phase.
For each iteration E [T) the algorithm receives updates (*) Rd and g E R. Define (t) : (AA(-))) [1)] E R(d+t+1)xd to be A (t-1) appended with a new row (T. and b(t) := [(b(-ii)T,, - E Rd+r+1 to be (tt-1) appended with a new entry z0)) After this update, the algorithm outputs an e-approximate solution x(1) E Rd:
(1) (()) I (1+ min | (1( (0)x= (00)
XER2
3

---

Under review as a conference paper at ICLR 2022
We write [0 T] = 10.1...., and for any t [0 T], denote M b(y] ( We make the following assumptions.
[A(0)
Assumption 2.2. We assume 1. Each data have bounded l2 norm, i.e,, Vi E [T+d+1] the i-th row of M satisfies [M..) 1l2 S D. 2. The initial matrix M has full rank, and its smallest singular value is bounded by aa+1(M(0)) 2 a for some polynomially small a E (0,1).
Remark 2.3. We remark that these assumptions are essentially w.l.o.g. for the following reasons: 1. Real world data inherently have bounded Eg norm, and in upplications like machine learning, data often normalized. 2. We can assume the initial matrix A (0) has d 1 rows because brute-forcely adding these d + 1 initial rows would only take O(ds) time, and this is within our desired total running time of O.(nz((AA (22) + dd). 3. To satisfy the assumption that a 1
(M( 2 a for some polynomially small o, we could let the initial matrix M = a Iu+1. This is equivalent to adding small regularization term of ||x||2 and this incurs only polynomially small additive error.
DYNAMIC E-LSR DATA STRUCTURE
In this section, we provide approximation algorithm for the dynamic least squares regression. Notably, our algorithm maintains an c-approximate solution near input sparsity time.
Theorem 3.1 (Data structure for dynamic least squares regression). Let O. d. T E N. There ex- ists a randomized algorithm for dynamic least-squares regression (Algorithm 0 With probability least 0.9, the algorithm maintains an e-approximation solution for all iterations t [T] and the total update time over T iterations
most O nuz( A (2) log(T)) +e - 68 logo (TD/o)). Our data structure uses at most O(c-2 2dd looo (TD(())) space.
Notations We use superscript (1) to denote the matrix/veetor/scaler maintained by the data structure at the end of the t-th iterations. In particular, the superscript (0) represents the variables after the preprocessing step. For any matrix A E Raxd
[n] we define its leverage score T(A) E RR as T; (A) := a (A A)'a, We define the generalized leverage score (same as Cohen al. 2015 of A nxd with respect to another matrix B E TR ((A)) a. ( B)Ja. For more properties of the leverage scores see Section B.T
3.1 TECHNIQUE OVERVIEW
Our approach is formally described in Algorithm we first overview the ideas behind it.
From high level view, approach follows the online row sampling framework (Cohen et al., 2013 2020) Braverman et al., 2020): When a new row arrives, we sample and keep the new row with probability proportional to the (approximated version of) online leverage score
rd+++1 (M (m(*) ( ((M ((1))))mmm
(*-1)
The sampled matrix is spectral approximation to the true data matrix. We maintain an approximate least-squares regression solution using this sampled matrix.
Naively computing the online leverage score takes ((d²) time. In order to accelerate this computa- tion, we use two approximations:
1. Similar to Cohen et al. (020). we compute the online leverage scores with respect to the sampled matrix instead of the true data matrix. However, this idea alone still not enough to achieve sub- sub-quadratic time.
2. We use a JL-embedding
8 trick (Spiclman & Srivastaval 2011) to compress the size of the d x d matrix to x e x d. In this way, in each iteration it only takes (d) time to compute the approximate online leverage score.
We further use an inductive analysis to bound the overall error (Lemma 3.4
Finally, we adopt a similar strategy as Cohen et al. (020) to prove that sampling according to the approximate online leverage score still keeps at most O (d) sampled rows (Lemma B.7p. Whenever a row is sampled, it takes (d)²) time to update the maintained matrices using Woodburry identity.
Hence, the amortized update time of the sampled rows is (dPP/T) =(d) when T > d.
JJohnson-I Brohsson-Lindenstraasss indenntrruss (II.) Lemma shows a way to embed high-dimensional vectors to low-dimensional space while preserving the distances between the vectors. A rigorous statement is shown in Lemma B.4
4

---

Under review as a conference paper at ICLR 2022
Remark 3.2 (Difference from sketching Eketehing-based solutions). Our approach crucially differs from the sketching baasedinn-baeddddd solutions, which do not provide any speedup over the direct application of Wood- burry identity (O(d)) time per iteration). A sketching- saaringg-beedddd solution maintains a sketched matrix SM (R.))) where S is sketching matrix (e.g. SRHT (Ailon & Chazelle 2006) or Count Sketch (Clarkson & Woodrufi 2017g) that mixes the rows of M. When a new row of M arrives, at least one row of the sketched matrix SM needs be updated, in contrast our sampling-base approach where the sampled malrix is not updated in most of the iterations.
Implementation We explain the detailed implementation of our algorithm. At the beginning of the t-th iteration, a sampling matrix D (t-1) is derived based on the online leverage score, and the sub- sampled matrix N((-)) = M maintains a spectral approximation on the column space of (t-1)) [A (t-1), b( Let (t-1)) denote the number of sampled rows. To obtain spectral approximation, we maintain the approximate covariance matrices ( = ((N((=1) ((- and ( (( The online leverage score 7(1) of a new row m (4) = ((a!9)T, (()
can be approximated as [[B((=)m((( we left-multiply by a JL matrix (t-11) and maintain proxy (t = (((-)) with the guarantee that B (t(+)1 m|/2 [B((11) for any E Rd+1 with high probability.
efficiently compute the leverage score of a new row,
When a new row m (1) is inserted at the 1-th iteration, we sample it via the approximate online leverage score (Line g of SAMPLE)). We only perform update the new row is sampled. In that case, we renew the JL matrix and perform series of careful updates on all the variables
that we maintain (See UPDATEMEMBERS). To obtain the final solution x()) Rd we solve
minxer [DD(t) A 1 which has the closed-form solution of x(1) G u(t)
and can be efficiently maintained by taking G(t) (D())))())))) (()) = (A (()))))))))
Rdxd and
Algorithm PREPROCESS (A, b, T)
I: M + b)
MM ((d+))((4+1
Algorithm SAMPLE (m)
2: I
I: + |B m |
# Spectral approximation
2: p + min (e)3((())2e-)) log(1/6),
3: 8 + d+1
4: N M
B 5: H ((N) N) D H(D(-))
3: V + 1/v0 with probability p, and +
otherwise
6: B
D B
JJL approximation.
7: 8 0(1/T2), + O log (T)))
Algorithm UPDATEMRMBERS (m)
8: J JL(,,,,,,) JL matrix E Rixs
Update spectral approximation
9: B
> B R kx(+1)
1: f +1
10: G (A D
#Maintain solution
b G E Rdxd
2: AH + I+m Hm/p
Hmm H/2
b
Rdd b Rd
3: + HHAH
4: B < [BB N-AH) H H-mm /pl
x
5: N [NT, _m//]]
# Update JL approximation
6: J (,,,
Algorithm UPDATE (a,
7: B
I: [a T
Rd+1
# #Update solution
2: P < SAMPLE(m)
D DVER R
8: G
Gaa G/p
D
T+a Ga/p
3: D 0
9: u u a/p
10: x - G
4: if then UPDATEMEMBERS(M)
5: return X
We outline the proof of Theorem 3.1 and defer the detailed proof to Appendix Cuue space limits.
5

---

Under review as a conference paper at ICLR 2022
3.2 CORRECTNESS
We show the correctness of our algorithm and prove maintains an c-approximate solution for all iterations with high probability. We start with dlosed-form formulas for all the variables we maintain.
Lemma 3.3 (Closed-form formulas). At the t-th iteration of Algorithm we have
1. ( = [A (9, b(o) E (R(++++1)x(++1))
2. D (t) E (B [(d+++1)(((+2+) is a diagonal matrix with s non-zero entries.
3. O ( Ss,,, E R x(d+)) where S(t) C [d + + 1] is defined as the set of
non-zero entries of (()).
4. H
E R((+1)x((+1)
5. B(O = H (d+(1))
6. B( J ( (kx((+1), where k = O logg))))))))
7. G ((A ( (D())
Rdddd
8. ( = (A ( ( ERC
9. x = ((A1)) (D (1) (A (A (1) ( E
The following lemma is key for our correctness analysis. It shows that we maintain a good approxi- mation on online leverage scores and a spectral approximation of ( throughout all iterations. Lemma 3.4 (Spectral approximation via leverage score maintenance). With probability at least 278,
32-Mi (() (1 (1-c) ddtt41 (M()) (0)) S (1 rdttt1 (M()), Vt (
M ((-1))
(2)
and
(D me (M (()), At E [0 T].
(3)
Proof Sketch. We prove by induction and show that with probability
216, Eq. 3 holds for all
E [0: and Eq. 2 holds for all t' E [t]. The base case holds trivially, as D I2+1. and therefore, (M))) 2 (M M()), Given the induction hypothesis upon 1, we proceed in the following three steps.
We first use the induction hypothesis to prove that [B (t-1)) (0)) a good estimate on the online leverage score, that
(t- (M()) (B(11) 191 S (1 + e)T Min (M")..
(1 e)7
We then use the JL lemma (Lemma B.4 to show that with probability covariance matrix
8, the sketched
|
(t-
m (+) returns good estimation ( ()(t+1)mm mn)) That is
(t-1) (1 - c)2 dd+t+1
(M
(+-)) m 1911 s + c)² -d+e+1 (M()..
((t
(4)
Finally, we wrap up the proof by proving the second part of induction. In particular, we show that conditioned on Eq. 4 holds, we have
(M (D())((()) Re (M()) M()) (())
The proof then follows by an union bound over failure events.
It is well known that spectral approximations of (M()))T T (t) give approximate solutions to least squares regressions (Woodruff 2014), so we have proved the correctness of our algorithm.
Lemma 3.5 (Correctness of Algorithm ا With probability at least 1 - O(1/T), in each iteration,
UPDATE of Algorithm outputs a vector x!
(t) E Rd such that
(+))) (t) S ())
min || (1) x (00
XER4

---

Under review as a conference paper at ICLR 2022
3.3 TIME ANALYSIS
Next, we bound the overall update time of our algorithm. We first compute the worst case update time of Algorithm 2 When y(() = 0, i.c., the t-th row is not sampled, the UPDATE procedure only needs to compute the approximate leverage score 7()) (SAMPLE, Algorithm and it takes O(k (9)) time. When u(t jf 0, i.e., the 1-th row sampled, the UPDATE procedure makes a call to UPDATEMEMBERS (Algorithm 4. and it takes Ol s(1) dd) time. Plugging in the value of k we have the following lemma.
Lemma 3.6 (Worst case update time). At the 1-th iteration of the UPDATE procedure (Algorithm
If 0, then UPDATE takes D(c-2log(T// nnz(al!)) time.
1f + 0, then UPDATE takes
time.
To bound the amortized update time, we need to bound the total number of sampled rows, and this is closely related to the sum of online leverage scores. Such an upper bound was already established by Cohen et al. (2220), here we present slightly generalized version of it.
Lemma 3.7 (Sum of online leverage scores, generalization of Theorem 2.2 of (Cohen et al. 2020 If the matrix ((T) satisfy Assumption 2.2 then
E M Tdttt1 (M S Oddlog(TD/oo)
Now we are ready to bound the amortized update time of our algorithm. Lemma 3.8 (Amortized update time). With probability at least 0.99, the total running time of UPDATE over T iterations is most 2
nnz(A (T) log(T) c logo (TD(o))
Sketch. this proof sketch we simplify the second term as d3 poly(c="oo(TTD/oo) The first term comes from the computation cost of querying leverage score, which takes O log(T/8). nnz(a ))) time in the f-th iteration even the t-th row is not sampled. The second term bounds the total update time for the sampled rows:
From Lemma 3.4 and Lemma 3.7 with high probability the sum of the approximate online leverage scores (1) are bounded by ((d)))(TD/oo)).
Using Markov inequality, the total number of sampled rows is bounded by
T
s(')) 0 ())) - log(1/8)
((0) < 0d 1olo-polyyc--- (ogy(c=)o((TDo))))
Since there are g(T) sampled rows, and for each sampled row we update data structure (og()))))) time, the total update time for sampled
members in S ( rows is
(T) polypp o log(D/o))
4 HARDNESS RESULT
We prove ((d2-o(1) amortized time lower bound for dynamic least squares regression with high precision, assuming the OMv conjecture. The OMy conjecture was originally proposed by Hen- Zinger al. (2155). and it is widely accepted in the theoretical computer science community.
Conjecture 4.1 (OMv conjecture, (Henzinger et al. 2015 Let d N,T = poly(d). Let 0 be any constant. B E (0, 1 is Boolean matrix. Vt E [T], a Boolean vector z(1) E 1J is revealed at the t-th step. We say an algorithu solves the OMy problem if it returns the Boolean matrix-vector product (t E a at every time step. The conjectures states that there is no al- gorithm that solves the OMv problem using (dly preprocessing time and O(d2") amortized running time, and has an error probability < 1/3.
7

---

Under review as a conference paper at ICLR 2022
The results in this section are all under the Word RAM model where the word size (log d)). Our main result is formally stated below.
Theorem 4.2 (Hardness of dynamic-least squares regression with high precision). Let d E E, poly(d), æリェ = 1/ poly (d), and let 7 > 0 be any constant. Assuming the OMv conjecture is true, any dynamic algorithm that maintains an t-approximate solution of the least squares regression requires at least (2dd -) amortized time per update.
Our lower bound is proved by first reducing the standard OMv conjecture for Boolean matrices to OMy-hardness for well-conditioned positive semidefinite (PSD) matrices over real numbers. Then use this new OMv-hardness result to prove our lower bound for dynamic least squares regression. We only provide a proof sketch here and detailed proof are delayed to Section
OMv-hardness for well-conditioned PSD matrix The OMv conjecture asserts the hardness of solving online Boolean matrix-ven vector product exactly. We extend it to solving online real-valued matrix product for well colditondt PSD matrices, while allowing polynomially small error.
Lemma 4.3 (Hardness of approximate real-valued OMv). Let d E N, poly(d). Let > 0 be any constant. Let H E R be a symmetric matrix whose eigenvalues satisfy S (H) ....
A (H) s 3. For any E [T], ( E R is revealed at the t-th step, and | S 1. Assuming the OMv conjecture is true, then there is no algorithm with poly(d) preprocessing time and O(d amortized running time that can return an (1/dd) yupprroiimiilat answer to Hz for all I, i.e.
vector y(t) Rd s.t. Ily(t) - Hz S and has an error probability S 1/3.
x in the OMv conjecture, we construct PSD Proof Sketch. Given Boolean matrix B E {0,
1]dxd
2
B
matrix H
E 2d22d2d We note that H is symmetric and S (H S X (H): S.
2I
Given binary OMv query vector (t),, we construct ((t) (0d, 20) E Idd Since has constant condition number, we can prove that rounding an appoxiappo answer ý R. H z (4) still gives the correct binary answer Bz
Reducing OMv dynamic least-squares regression We next wrap up the proof of Theorem 4.2 by reducing OMv to dynamic c-LSR.
Given a PSD matrix H and sequence of query (H2 YE= of the problem in Lemma 4.3, we reduce it to a dynamic e-LSR, where the initial A is such that T A =
Proof Sketch of Theorem
H-1 (this preprocessing step of the reduction takes ~ d= time), and the label is 0 for the initial d data. For each
[Z'. the incoming row (!)) is small scaled version of (4), ie, a()
(()) E Rdd, and the label is 1. Let x(() be the optimal solution at the f-th step, H(!) == ((A (0) A (2), the reduction complete via the following three steps:
PVT
(t) Step 1. (!) and x are close, i.e., x(1)= = x + + +0(-1))
Step 2. x()) x (t-1) recovers (t11)) (1) i.e., x(() (((-1) = (1)))) + 0 ((vTT)
Step 3. (t- is close to (a ic., H a) (a + O d''
TT))
In particular, let y(t) = (x - 1()- Step 2 and 3 directly implies ly Hz <
((1dd). This completes the proof.
EXPERIMENTS
Our method is most suitable for data distributions that are non-uniform. Indeed, if the data has low coherence (they are all similar to each other), then the naive uniform sampling is as good as leverage score sampling. We perform empirical evaluations on our algorithm over both synthetic and real-world datasets.
Synthetic dataset We follow the empirical study of (Dobriban & Liu 2019) and generate data from the elliptical model. In this model (!)) ())), where z (O, La) is random Gaussian vector, Σ Rdd is PSD matrix, and (0) is scaler. The label is generated as (())
8

---

Under review as a conference paper at ICLR 2022
(a x²) + w()))()), where x" Rd is a hidden vector and (O. 1) is standard Gaussian noise. This model has a long history in multivariate statistics, see e.g. (Martin & Maes 1979p In our experiments, we set Σ Ia for simplicity. In order to make the dataset non-trivial, we set ((() to be large (= VT) for a few (= d/ 10) iterations, and small (= 1) for the rest of the iterations. We set 7 400000 and d = 500.
Real-world dataset We use the VirusShare dataset from the UCT Machine Learning Repository P We select this dataset because it has large number of features and data points, and has low emros when fitted by a linear model. The dataset is collected from Nov 2010 to Jul 2014 by VirusShare (an online platform for malware detection). It has T 107888 data points and d 482 features.
Baseline algorithms We compare with three baseline methods. 1. Kalman's 's approach makes use of Woodburry identiy and gives exact solution. 2. The uniform sampling approach samples new 3. The row sampling approach samples new rows according to the exact
rows uniformly at random.
online leverage scores. (Cohen et al. 2020p
Our experiments are executed on an Apple M1 CPU with codes written in MATLAB. We repeat all experiments for at least 5 times and take the mean. On both datasets, initiate the model based on the first 10% of the data. The experiment results are formally presented in Figure | and more details can be found in Appendix E Our algorithm consistently outperforms baseline methods: Our algorithm runs faster when achieving comparable error rates.
105
sampiing
sampling
30'
Row sampligg
10*
wampling
Relative error
This paper
Relative error
10a
This paper
10-
10*
10rl
10-2
19n2
100 Running Time
Running Time
(a) Synthetic dataset
(b) VirusShare
Figure 1: Experiment results. The z-axis shows the running time (unit: seconds), and the y-axis
shows the relative error serr/eTsaa - 1). where err is the error of the particular approach, and errata is the error of the static Normal equation. The y-axis is log scale. For uniform sampling, take sampling probability p = 0.05, 0.1, 0.2, 0.5. For row sampling and our algorithm, we take the error parameter 0.1, 0.2, 0.5, 1. Kalman's approach has relative error of O.
6 CONCLUSION
We provide the first practical and provably fast data structure for dynamic least-squares regression, obtaining nearly tight upper and lower bounds for this fundamental problem. On the algorithmic side, we design e-approximation dynamic algorithm whose total update time almost matches the impul sparsity of the (online) matrix. On the lower bound side, we prove that it is impossible to maintain an exact (or even high-accuracy) solution with & d2-o(1) amortized update time under the OMy conjecture. As such, this result exhibits the first separation between the static and the dynamic LSR problems.
Our paper sets forth several interesting future directions. On the theoretical side, very interest- ing question is whether it is possible to reduce the additive term d of our algorithm to matrix- multiplication time d second open problem-of interest both theory and practice-is is whether it is possible to achieve input-sparsity amortized update time in the fully dynamic setting, i.c., when allowing both addition and deletion of data rows? Finally, it would be interesting to find connections between dynamic least-squares regression and incremental training of more complicated models, such dynamic Kernel-ridge regression and deep neural networks.
https://archiss iss. uci htddum/mmdaataattss...

---

Under review as a conference paper at ICLR 2022
REFERENCES
Thomas D Ahle, Michael Kapralov, Jakob BT Knudsen, Rasmus Pagh, Ameya Velingker, David P Woodruff, and Amir Zandieh. Oblivious sketching of high-degree polynomial kernels. In Pro- ceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 141-160. SIAM, 2020.
Nir Ailon and Bernard Chazelle. Approximate nearest neighbors and the fast johnson-lindenstruus transform. In Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pp. 557-563, 2006.
Josh Alman and Virginia Vassilevska Williams. A refined laser method and faster matrix multipli- cation. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 522-539. SIAM, 2021.
Haim Avron, Kenneth L Clarkson, and David Woodruff. Faster kernel ridge regression using sketching and preconditioning. SIAM Journal on Matrix Analysis and Applications, 38(4): 1116- 1138, 2017.
Christos Boutsidis, David Woodruff, and Peilin Zhong. Optimal principal component analysis in distributed and streaming models. In Proceedings of the forty-eiighh annual ACM symposium Theory of Computing, pp. 236-249,15 2016.
van den Jan Brand, Yin- Tat Lec, Danupon Nanongkai, Richard Peng. Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang. Bipartite matching in nearly-linear time on moderately dense graphs. In 2020 IEEE 61 Annual Symposium on Foundations of Computer Science (FOCS), pp- 919-930. IEEE, 2020a.
van den Jan Brand, Yin Tat Lee, Aaron Sidford, and Zhao Song. Solving tall dense linear programs in nearly linear time. In Proceedings of the 52nd Annual ACM SIGACT Symposium Theory of Computing (STOC), pp. 775-788, 2020b.
van den Jan Brand, Yin Tat Lee, Yang P Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang. Minimum cost flows, mdps, and L rrrerression in nearly linear time for dense instances. In Proceedings of the 53rd Annual ACM SIGACT Symposium Theory of Computing (STOC), pp. 859-869 2021a.
van den Jan Brand, Binghui Peng, Zhao Song, and Omri Weinstein. Training (overparametrizee)) neural networks in near- linear time. In /2th Innovations Theoretical Computer Science Con- ference (ITCS 2021), 2021b.
Vladimir Braverman, Petros Drineas, Cameron Musco, Christopher Musco, Jalaj Upadhyay, David P Woodruff, and Samson Zhou. Near optimal linear algebra in the online and sliding window models. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pp. 517-528. IEEE, 2020.
Sébastien Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning, 833-4):2113377, 2015.
Nadiía Chepurko, Kenneth I. Clarkson, Praneeth Kacham, and David P Woodruff. Near- optimal algorithms for linear algebra in the current matrix multiplication time. arXiv preprint
arXiv:2107.08090 2021.
Charles K. Chui. Estimation, control, and the discrete kalman filter (donald calin). SIAM Re- view, 32(3):93-494, 1990. doi: 10.1137/1032097. URL
1032097
Kenneth L Clarkson and David P Woodruff. Numerical linear algebra in the streaming model. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pp. 205-214, 2009.
Kenneth L Clarkson and David Woodruff. Low-rank approximation and regression in input spar- sity time. Journal of the ACM (JACM), 63(6):1-45 2017.
10

---

Under review as a conference paper at ICLR 2022
Michael B Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng, and Aaron Sidford. Uniform sampling for matrix approximation. In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science (ITCS), pp. 181-190. ACM, 2015.
Michael B Cohen, Cameron Musco, and Jakub Pachocki. Online sampling. Theory OF Com- puling, 16(15): 2020.
Edgar Dobriban and Sifan Liu. Asymptotics for sketching in least squares. In Proceedings of the 33rd International Conference on Neural Information Processing Systems, pp. 3675-3685, 2019.
Petros Drineas, Michael W. Mahoney, and S. Muthukrishnan. Sampling algorithms for 1 regression and applications. In Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm (SODA), pp. 1127-1136, 2006a.
Petros Drineas, Michael Mahoney, and S. Muthukrishnan. Subspace sampling and relative- error matrix approximation: Column-based methods. In Approximation, Randomization, and Combinatorial Optimization. (PPROX-RANDOM), pp. 316-326, 20066b.
Petros Drineas, Michael W. Mahoney, and S. Muthukrishnan. Subspace sampling and relative- error matrix approximation: Column-row-basee methods. In European Symposium on Algorithms (ESA), pp. 304-314, 2006c.
Trevor Hastie, Jerome H. Friedman, and Robert Tibshirani. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer Series in Statistics. Springer, 2001. ISBN 978- 14899-0519-2. doi: (0000//98-0-387-2110
URL https:://cc..ooo wttp://0011.00010100000000
778-0-387-2181
Elad Hazan. Introduction to online convex optimization. arXiv preprint a/Xiv:/909005207, 2019.
2019.
Monika Henzinger, Sehastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak. Unify- ing and strengthening hardness for dynamic problems via the online matrix-vecto multiplication conjecture. In Proceedings of the sorty-seventh annual ACM symposium on Theory of computing, pp. 21-30, 2015.
Shunhua Jiang, Zhao Song, Omri Weinstein, and Hengjie Zhang. A faster algorithm for solving general Ips. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 823-832, 2021.
William B Johnson and Joram Lindenstrauss. Extensions of lipschitz mappings into hilbert space. Contemporary mathematics, 26( (188-2206):,, 1984.
Rudolph Emil Kalman. A new approach to linear filtering and prediction problems. Journal of Basic Engineering, 8251):35-45, 1960.
François Le Gall. Powers of tensors and fast matrix multiplication. In Proceedings of the 39th international symposium on symbolic and algebraic computation, pp. 296-303, 2014.
Yin Tat Lee and Aaron Sidford. Path finding methods for linear programming: Solving linear programs in Ö(Vrank) iterations and faster algorithms for maximum flow. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pp. 424-433. IEEE, 2014.
Yin Tat Lee, Zhao Song, and Qiuyi Zhang, Solving empirical risk minimization in the current matrix multiplication time. Annual Conference on Learning Theory (COLT), 2019.
Edo Liberty, Zohar Karnin, Bing Xiang, Laurence Rouesnel, Baris Coskun, Ramesh Nallapati, Julio Delgado, Amir Sadoughi, Yury Astashonok, Piali Das, et al. Elastic machine learning algorithms in amazon sagemaker. Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, pp. 731-737, 2020.
Aleksander Madry. Navigating central path with electrical flows: From flows to matchings, and back. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS), pp. 253-262. IEBE, 2013.
Nick Martin and Hermine Maes. Multivariate analysis. Academic press London, 1979.

---

Under review as a conference paper at ICLR 2022
Xiangrui Meng and Michael W Mahoney. Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression. In Proceedings of the forty- forty-fifth annual ACM symposium Theory of computing, pp. 91-100, 2013.
Jelani Nelson and Huy Nguyên. Osnap: Faster numerical linear algebra algorithms via sparser subspace embeddings. In 2013 ieee 54th annual symposium on on foundations of computer science, pp. 117-126. IEEE, 2013.
Rasmus Pagh. Compressed matrix multiplication. ACM Transactions on Computation Theory (TOCT), 5(3):1117, 2013.
German Parisi, Ronald Kemker, Jose L. Part, Christopher Kanan, and Stefan Wermter. Continual lifelong learning with neural networks: A review. Neural Networks, 113:54-71, 2019.
R. L. Plackett. Some theorems in least squares. Biometrika, 37(1/2):14--17,, 1950. ISSN 00063444. URL http:://www jstor. wtw.oo.rggg/taae///332222
Lawrence R Rabiner and Bernard Gold, Theory and application digital signal processing. Engle- wood Cliffs: Prentice-Hall, 1975.
Ilya Razenshteyn, Zhao Song, and David Woodruff. Weighted low rank approximations with provable guarantees. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pp. 250-263, 2016.
Vladimir Rokhlin and Mark Tygert. A fast randomized algorithm for overdetermined linear least- squares regression. Proceedings of the National Academy of Sciences, (05(36):13222-12111 2008.
Tamas Sarlos. Improved approximation algorithms for large matrices via random projections. In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), pp. 143- 152. IEEE, 2006.
Daniel Spielman and Nikhil Srivastava. Graph sparsification by effective resistances. SIAM Journal on Computing, 4066):113-1926, 2011.
Daniel Spielman and Shang-Hus Teng. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, pp. 81-90, 2004.
Stephen M. Stigler. Gauss and the Invention of Least Squares. The Annals of Statistics, 9(3): 465-474 1981. doi: 10.1214/ao//1176645551 URL ottp::://oi.org/10..220
1176345451
Volker Strassen. Gaussian elimination is not optimal. Numerische mathematik, 13(4):354-356, 1969.
David Woodruff. very sketchy talk (invited talk). In 48th International Colloquium on Au- tomata, Languages, and Programming (ICALP 2021). Schloss Dagstuhl-Leibnin Zeettizi- Informatik, 2021.
Zentrum fuer
David Woodruff.
Sketching as a tool for numerical linear algebra. Foundations and Trends in Theoretical Computer Science, 10(1-2):1-157, 2014.
12


Reviews:
[{"review_id": "oMe_Sz11xGg", "reviewer": "Reviewer_X5Ds", "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": "# Quality and Clarity\n\nOverall, this paper was a joy to read. It's written clearly and is well organized. No lengthy proofs are given in the body of the paper; instead elegant and intuitive proof sketches are shown. As someone very familiar with this literature, these proof sketches were largely satisfying.\n\n# Experiments\n\nExperiments are present, but rather barebones, and arguably misleading at a couple points.\nThe experiments compare wall-clock time versus relative-error for various algorithms.\nWhile the algorithm proposed in the paper is clearly listed, the competing algorithms are not clearly described.\n> For example, when the Kalman algorithm is run, which LS subroutine is used? Does it take advantage of sparsity? How can I trust that the Kalman algorithm is run with good parameters if the code isn't even provided in the supplemental material?\n\nAdditionally, the plots in Figure 1 are misleading with respect to the runtime-vs-error guarantee of the Kalman algorithm:\n\n> The caption notes that the Kalman algorithm has zero error, which would be far below the $10^{-3}$ error shown on the plots. As drawn, the plots suggest that Kalman takes 2x the time for 1 order-of-magnitude improvement, while the caption suggests it's more like 14 orders-of-magnitude improvement (assuming \"error of 0\" means \"roughly machine epsilon\").\n\nThe papers is focused more on the theory, so I don't consider any of this a deal-breaker. But it should be acknowledged, and the authors should find a better way to compare Kalman against the other algorithms. Some concrete ideas are listed at the bottom of the review.\n\n# Technical Novelty and Significance\n\nThe originality and novelty of this paper is a bit nuanced. The idea of online leverage score sampling, as acknowledged by the paper, is not new. So, computational complexity is really the only part in focus. If $d$ is the dimension of the least square problem, then prior results on Dynamic Least Squares (DLS) used $O(d^2)$ amortized runtime per-update, while this paper has $O(d)$ amortized runtime per-update. \n\n### Lemma 3.4\n\nThis performance boost is achieved by approximating leverage scores with a Johnson–Lindenstrauss sketch. Peeling back the layers of the nice presentation, this seems to be the core of the technical contribution of the paper (mainly in Lemma 3.4, a bit in Lemma 3.7). The proof sketch is compelling, though I haven't reviewed the full proof; if I have time I'll make an update on that.\n\n### Lemma 3.7\n\nA possible second core technical contribution is in Lemma 3.7, bounding the sum of online leverage scores. Though, in my experience, I haven't seen many leverage score bounds depend on the good conditioning of the input matrix. My impression is that leverage score sampling is generally interesting _because_ it can avoid niceness assumptions on the input matrix. If the authors could comment specifically on why the good conditioning of $M$ is necessary, and if there's clear precedent in the literature, I would appreciate it.\n\n### Section 4\n\nA third contribution is the conditional lower bound. While I had not heard of the OMv conjecture, it is intuitive and the construction of the lower bound from the OMv conjecture is mostly elegant. Unfortunately, there is a frustrating point in the Proof Sketch of Theorem 4.2, where the vector $x^{(t)}$ is never clearly defined, so I am not totally clear how the reduction works. The proof is still believable though.\n\n### Overall \"Sufficiency\"\n\nIn my view, the technical contributions, ranked from most interesting to least interesting are:\n1. The JL Sketch for Leverage Scores\n2. The Lower Bound Reduction\n3. The sum-of-sensitivities bound\n\nThe proofs seem correct, and all three points may be relevant to future researchers, but it just isn't obvious to me that this is _sufficient_. Since I'm familiar with this area, and many of the proofs around leverage scores, I totally could see myself using any of the three points here, so I tend toward \"Marginally above accept threshold\".\n\nTo be clear about my _sufficiency_ concern, let me give some examples of what I might hope to see more of:\n1. I'm a little worried about the Assumption $2.2$, which ensures that the data isn't too messy. I don't think that I've seen any row-norm bounds in recently leverage score sampling papers. Not sure if I've seen these $\\sigma$ bounds either (though that's plausibly hidden by the $\\lambda$ parameter in $\\lambda$-ridge leverage score sampling).\n2. Move to ridge regression or KRR. If the JL trick also works there, that would be notably compelling, and feel like a stronger and more general theoretical guarantee. This may expand the scope a lot, so I might also lean towards bullet point three:\n3. The theory is rooted in the three above-discussed claims. The paper is largely about the algorithm itself though. Flesh out the experiments more.\n\n---\n# Extra Tidbits\n\n### Re: Experiments\nHere's some specific ideas on how to make Figure 1 a bit more honest:\n- Maybe remove the log-scale?\n- Maybe use an iterative LS algorithm that can trade-off runtime and accuracy, to compare against the proposed algorithm for a wider variety of time points?\n- Maybe just draw a vertical line at 224, where the Kalman algorithm achieves zero error?\n- Maybe break the y-axis and show that Kalman is much much lower, roughly around machine epsilon?\n\n### Lingering technical questions\n1. [Page 3, just before Section 1.2] Why is this $d^{1 + o(1)}$? I get that $nnz(A^{(T)}) = O(dT)$, but I don't see where the $o(1)$ term comes from.\n1. [Page 7, second-to-last sentence of the first paragraph]: I believe line 4 of `UpdateMembers` takes $O(s^2 d)$ time to compute $Hm$. Shouldn't this be added into the big-O notation here? How does this interact with the amortized runtime?\n\n### Typos and suggested edits\nI found a couple typos, but very few.\n1. [Top of page 3]: Right after \"$T \\gg d$\" add a citation\n1. [Page 3, third line of \"Sketching and Sampling\"]: \"have\" should be \"has\"\n1. [Page 4, second to last line of the page]: Should be \"the Woodbury Identity\" not \"Woodburry identity\" (spelling, capitalization, and missing \"the\").\n1. [Page 5, line 1 of Algorithm 1]: A and b should have superscripts\n1. [Page 6, first bullet point in the proof sketch]: $\\|B^{(t-1)}m^{(t)}\\|$ should have sub- and super-scripts.\n1. [Page 6, last bullet point of the proof sketch]: Consider giving some intuition why approximately preserving leverage scores implies that the spectral embedding holds, or cite a prior result which gives such an intuition? In particular, why is this a deterministic guaranteed conditioned on equation (4) holding?\n1. [Page 7, and maybe some other pages too]: What is $\\delta$? I assume it's a JL-parameter, but I think it's never defined.", "summary_of_the_paper": "The paper discusses _Dynamic Least Squares_: the problem where the rows of a overdetermined least squares problem are revealed incrementally, and an algorithm has to maintain an accurate solution to the least squares system as these rows are revealed.\n\nIn prior work, this problem has been studied in the context of space complexity, where tools like leverage score sampling minimize the number of rows an algorithm must store. In this work, the focus shifts to time complexity, where the authors focus on making those leverage score sampling algorithm more computationally efficient.\n\nThe algorithm provided is matched with a compelling conditional lower bound.\n\nSome experiments are provided.", "summary_of_the_review": "The paper discusses an interesting problem, taking an algorithm optimized for space complexity, and tuning it to also benefit time complexity.\n\nThe technical core of the paper certainly exists, but I'm uncertain if it is sufficient. I lean \"marginally above accept\" on this point, since I could see myself referring to results these in the future, but it's just not a lot. I like the lower bound quiet a bit.\n\nThe experiments are barebones, but if the theoretical contribution is sufficient, then that's something the authors can fix up for the camera-ready version.\n\nI'm particularly interested in discussing with other reviewers if the technical contributions are sufficient. I could easily be swayed either way.", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "muX9FfxJpF", "reviewer": "Reviewer_aakT", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "It seems the exposition is largely focused on the upper bound, which achieves input sparsity runtime by performing online row sampling and and then running a rank-one update procedure to the maintained solution each time a row is sampled. However, because the number of sampled rows is roughly $\\tilde{O}(d)$, I believe to get input sparsity runtime, it suffices to run the simpler algorithm of just running online row sampling and resolving the regression problem from scratch each time a row is sampled. The online row sampling algorithm uses input sparsity runtime and solving the regression problem from scratch on a matrix with size $\\tilde{O}$ rows up to $\\tilde{O}(d)$ times will use a lower order runtime. Thus it seems the main contribution of this paper is to improve the lower order runtime through the rank-one updates. Please let me know if I'm missing something.\n\nOn the other hand, I find the lower bound more compelling as it uses tools from fine-grained complexity that may not be as familiar to the sublinear algorithms community. The paper shows a reduction from the online matrix-vector conjecture, which essentially says that maintaining the product of a matrix and a vector whose entries are iteratively revealed requires roughly $\\Omega(d^2)$ update time. This lower bound thus shows linear regression problem is strictly harder in the dynamic setting than the static setting.\n\nThe paper also includes some experiments but the details are not entirely clear. For example, it was stated that the experiments were all repeated at least 5 times. Does Figure 1 then plot the mean relative error or the best relative error? Can you elaborate more on how you chose to implement online row sampling, e.g., how you chose to approximate the online leverage scores?\n\nMinor: Woodburry -> Woodbury in a few places\n\nPg. 8: scaler -> scalar", "summary_of_the_paper": "This paper consider linear regression in the dynamic setting with the goal of minimizing the amortized time of outputting a $(1+\\epsilon)$-approximate solution at all times and gives two main results. The first result is an input sparsity runtime algorithm that uses online row sampling while second result is a lower bound that shows that on average, $\\Omega(d^2)$ time is needed per operation. ", "summary_of_the_review": "In summary, I think the main result in this extended abstract is a lower-order term improvement over the naive algorithm and I found the analysis unnecessarily complicated in order to achieve this lower-order improvement over the naive algorithm (please correct me if I am wrong!). On the other hand, the lower bound shows a nice separation from the centralized setting and although not entirely surprising, the result is interesting to me from a theoretical perspective.\n\nPost-rebuttal update: I acknowledge that I have read the author response to my review. I also acknowledge that I did indeed misunderstand the significance of the upper bound with respect to the previous work. Specifically, because the JL-trick can only be applied to batches of $d$ rows, then it is not applicable in the dynamic setting in which the solution must be updated after each row. As I already thought the lower bound was of independent interest, I raise my score from 5 (weak reject) to 8 (accept).\n\nRegardless, I hope the authors will consider improving the presentation of the technical statements. In particular, Lemma 3.3 could either decrease the number of closed-form formulas or add intuition to some of the formulas. ", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "NdRnFxqLeyu", "reviewer": "Reviewer_Q1Nm", "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": "The upper bound largely imitates an earlier work by Cohen et al. The original work considers the ridge regression and thus (A^TA + lambda*I)^{-1} instead of a pure (A^T A)^{-1} in the regression. The algorithms and the proofs are all similar to Cohen et al.’s paper. But the result on the regression problem is nice.\n\nThe reduction in the proof of the lower bound is interesting and I like it, though the Online Matrix-vector conjecture feels a bit strong in its own formulation to me, which already places the regression problem in a good position for the reduction. The lower bound is a bit weak in the sense that it requires eps to be 1/poly(d), which is rather small.\n\nThe paper is well-written. The following is a few typo-level comments:\n- There are a few occurrences of ‘Woodburry’ instead of ‘Woodbury’.\n- Page 7, three lines above the title of Section 4: delete the “<=”. The big-O notation implies that.\n- page 8, proof sketch of Theorem 4.2, line 6: (A^T A)^{-2} should be (A^T A)^{-1}?", "summary_of_the_paper": "The paper considers solving the regression problem min_x |Ax-b|_2 in the online setting, where A in R^{n x d} and b in R^n are given row by row, one at each time. The main task is to maintain a good approximate solution x (meaning that |Ax-b|_2 <= (1+eps)*OPT) throughout this process, with the update time as small as possible. The paper shows that if there are T updates to A (the initial A may not be empty), the total update time will be O(eps^{-2} nnz(A) log T + poly(eps^{-1} d log T)). \n\nThe first term O(eps^{-1}nnz(A)log T) matches the runtime in a typical sketching algorithm up to the log T factor, while the second term poly(eps^{-1} d log T) is much better in the dependence on T than the runtime of a simple sketching algorithm, which would be poly(d/eps)*T. This means that the amortized cost of each update is much smaller when T >> d.\n\nThe paper also proves a lower bound of Omega(d^{2-o(1)}) amortized update time for T = poly(d) updates, assuming the Online Matrix-vector conjecture (which is on the amortized runtime of multiplying a matrix with a vector in the online setting).", "summary_of_the_review": "Although there is not significant technical innovation, this paper is a solid technical paper that solves a basic linear algebraic problem in the online setting and deserves to be published.", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "KDmgbX5P6xA", "reviewer": "Reviewer_yBkT", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The problem studied is very natural since data points are often not available at the same time. The solution mainly follows Cohen et al. (2020) with the difference in the leverage score computation, which is done using a matrix that results from applying the JL lemma. At a technical level this part is not extremely new. The lower bound is nice and not known to the best of my knowledge. The runtime improvement seems significant (both in theory and in practice), although the numerical experiments are limited (just 1 experiment with real data). The paper is well written in general.\n\nI have the following minor comments.\n\n-What is the main technical insight of this work compared to Cohen et al. (2020)? It seems that the authors of that paper considered the JL trick but in a different way using batched updates. What were they missing?\n\n-Woodburry -> Woodbury (everywhere)\n\n-page 2 grammar: \"which assert\", \"this papers\", \"the implication Theorem\"\n\n-page 3: \"Theorem 1.2 almost matches the fastest sketching-based solution\": I don't think it matches it, since it has an $\\epsilon^{-2}$ error dependence instead of $\\log 1/\\epsilon$.\n\n-page 3 grammar: \"have focused\"\n\n-page 8 \"scaler\"\n\n-page 9 \"identiy\"", "summary_of_the_paper": "This paper studies incremental least-squares regression, where the goal is to maintain an $(1+\\epsilon)$-approximate solution to $\\min_x \\left\\Vert Ax-b\\right\\Vert_2^2$ for some $A\\in\\mathbb{R}^{n\\times d}$, under row insertions to $\\begin{pmatrix}A & b\\end{pmatrix}$, while keeping the total runtime as low as possible. \n\nIt builds on a work of Cohen et al. (2020), where it is shown that if, upon insertion of a row, we only keep (a multiple of) it with probability roughly equal to its current leverage score (otherwise we discard it), then the total number of rows that will be inserted is only $\\widetilde{O}(d)$ and the matrix spectrally approximates the \"true\" matrix where all rows are kept. The main contribution of this paper is to make this algorithm faster, by improving the leverage score computation procedure. Instead of directly computing the leverage scores, the authors use the Johnson-Lindenstrauss lemma to be able to quickly approximate them. Then the main thing to be taken care of is maintaining certain dimension-reduced matrices that arise. In total the asymptotic amortized runtime goes down from $\\widetilde{O}(d\\cdot nnz(A))$ to $\\widetilde{O}(nnz(A))$. \n\nAdditionally, the authors give a negative result, which shows that, under the OMv conjecture, the amortized runtime is $\\Omega(d^2)$ if we require a high-precision solution ($\\epsilon=1/\\mathrm{poly}(d)$).\n\nThe theoretical result is accompanied by some synthetic and real experiments. In both, it seems that the runtime improvement is significant (e.g. up to 4x speedup in the real data when $\\epsilon=1$).", "summary_of_the_review": "A significant improvement of the theoretical runtime bound is given. Some of the technical content overlaps somewhat with previous work. The experiments show good results but are limited. The paper is well written. Therefore, I tend to acceptance.\n\n-----------------------------------------\n\nI thank the authors for the answers, they have answered my questions.", "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": "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": {}}]

Author rebuttal:

Meta-review: There wasn't enough enthusiasm to push this paper over the bar, based on no reviewer championing the paper (the one score above 6 was consulted and thought this was a fair assessment). The reviewers appreciated the contributions of the paper but felt that in terms of technical depth, there was a lot of overlap with prior work, and the statements of the results themselves were good but not exciting enough to convince the reviewers. Some suggestions for further improvement that came up were to try to extend this to update time for low rank approximation, which was an application that other work that built off of Cohen et al did, see, e.g., https://arxiv.org/abs/1805.03765 . Regarding presentation, it would be great if in a re-submission the authors handle the presentation concerns of some of the reviewers regarding the experiments.
Decision: Reject