Streaming Algorithms For $\ell_p$ Flows and $\ell_p$ Regression
Authors: Amit Chakrabarti
Jeffrey Jiang
David Woodruff
Taisuke Yasuda
Venue: ICLR 2025 Spotlight (2025)
Keywords: Regression
Streaming
Online algorithms
Flows
Primary area: optimization
TL;DR: We give new streaming algorithms for underconstrained regression when we see the columns one at a time, and obtain related results for flows.

Abstract: We initiate the study of one-pass streaming algorithms for underdetermined $\ell_p$ linear regression problems of the form
  $$
      \min_{\mathbf A\mathbf x = \mathbf b} \lVert\mathbf x\rVert_p \,, \qquad 
      \text{where } \mathbf A \in \mathbb R^{n \times d} \text{ with } n \ll d \,,
  $$
  which generalizes basis pursuit ($p = 1$) and least squares solutions to
  underdetermined linear systems ($p = 2$). We study the column-arrival
  streaming model, in which the columns of $\mathbf A$ are presented one by one in a
  stream. When $\mathbf A$ is the incidence matrix of a graph, this corresponds to an
  edge insertion graph stream, and the regression problem captures $\ell_p$
  flows which includes transshipment ($p = 1$), electrical flows ($p = 2$), and
  max flow ($p = \infty$) on undirected graphs as special cases. Our goal is to
  design algorithms which use space much less than the entire stream, which has
  a length of $d$.

  For the task of estimating the cost of the $\ell_p$ regression problem for
  $p\in[2,\infty]$, we show a streaming algorithm which constructs a sparse
  instance supported on $\tilde O(\varepsilon^{-2}n)$ columns of $\mathbf A$
  which approximates the cost up to a $(1\pm\varepsilon)$ factor, which
  corresponds to $\tilde O(\varepsilon^{-2}n^2)$ bits of space in general and
  an $\tilde O(\varepsilon^{-2}n)$ space semi-streaming algorithm for
  constructing $\ell_p$ flow sparsifiers on graphs. This extends to $p\in(1,
  2)$ with $\tilde O(\varepsilon^{2}n^{q/2})$ columns, where $q$ is the H\"older
  conjugate exponent of $p$. For $p = 2$, we show that $\Omega(n^2)$ bits of
  space are required in general even for outputting a constant factor
  solution. For $p = 1$, we show that the cost cannot be estimated even to an
  $o(\sqrt n)$ factor in $\mathrm{poly}(n)$ space.

  On the other hand, if we are interested in outputting a solution $\mathbf
  x$, then we show that $(1+\varepsilon)$-approximations require $\Omega(d)$
  space for $p > 1$, and in general, $\kappa$-approximations require
  $\tilde\Omega(d/\kappa^{2q})$ space for $p > 1$. We complement these lower
  bounds with the first sublinear space upper bounds for this problem, showing
  that we can output a $\kappa$-approximation using space only
  $\mathrm{poly}(n) \cdot \tilde O(d/\kappa^q)$ for $p > 1$, as well as a
  $\sqrt n$-approximation using $\mathrm{poly}(n, \log d)$ space for $p = 1$.

Published as a conference paper at ICLR 2025
STREAMING ALGORITHMS FOR lp FLOWS AND lp REGRESSION
Amit Chakrabarti
Jeffrey Jiang
Department of Computer Science
Department of Computer Science
Dartmouth College
Dartmouth College
Hanover, NH 03755, USA
Hanover, NH 03755, USA
ami t. chakrabartt @da wtw.uth...c.e
jeffrey. jiangedde a rtmouth..du
David P. Woodruff
Taisuke Yasuda
Department of Computer Science
Department of Computer Science
Carnegie Mellon University Pittsburgh, PA 15213, USA dwoodrufêcs, cmu. edu
Carnegie Mellon University
Pittsburgh, PA 15213, USA taisukey@co cmu. edu
ABSTRACT
We initiate the study of one-pass streaming algorithms for underdetermined lp linear regression problems of the form
min |<01pp Az=b
where A E gand with < d,
which generalizes basis pursuit (p 1) and least squares solutions underdeter- mined linear systems (p=2), 2). We study the column-arrin arrival streaming model, in which the columns of A and then the vector b presented When A is the incidence matrix of graph, this corresponds to an edge insertion graph stream, and the regression problem captures l flows which includes trans- shipment (p- = 1), electrical flows (p = 2), and max flow (p co) undirected graphs as special cases. Our goal to design algorithms which use space much less than the entire stream, which has length of d. For the task of estimating the cost of the Ep regression problem for p E [2) we show streaming algorithm which constructs a sparse instance supported on Ō columns of which approximates the cost up to a (1+t) factor, which corresponds Ō bits of space in general and an Ō(E -2)) space semi-streaming algorithm for constructing lp flow sparsifiers on graphs. This extends p e (1,2) with ((E2ne/2) columns, where q the Hölder conjugate exponent of p. For p 2, we show that 2(nn) bits of space are required in general even for outputting a constant factor solution. For p= = we show that cost cannot estimated even to an o( vn) factor (n)y(n) space. On the other hand, if we are interested in outputting solution then we show that (I + apprrooxxiiaii require ((d) space for p > 1, and general, -Baappoxiisaiinns require (dd/329) space for p >> We complement these lower bounds with the first sublinear space upper bounds for this problem. showing that we can output a Baaaprrximmation using space only poly(n)- (oly())-((dBB9)) for 1, as well as /n-approximation using poly logd) space for ((d/B9)
by one in stream.
INTRODUCTION
When faced with an underdetermined linear system Ax = for an x d matrix A and a dndiimenson vector b, common approach towards obtaining useful solutions is to seek vector [x],....xx] that minimizes some measure of cost. A popular choice to minimize the least squares cost of æ,, i.e., the & norm of in which case the exact minimizer be written in closed form as

---

Published as a conference paper at ICLR 2025
argmin
Another well-studied choice is to minimize the { norm of æ, also known as basis pursuit (Chen et al., 2001), which gives rise to sparse solutions æ and has been popularized in the literature of compressed sensing and sparse recovery.
The minimum & and l2 norm solutions when A, b are training data and labels, respectively, have been of interest to understanding the double descent phenomenon: when machine learning models exhibit multiple phases of decreasing risk (or expected loss) as model complexity increases (Hastie et al., 2022; Bartlett et al., 2020; Li & Wei, 2021). Less theory is developed about regression models in this underconstrained regime as it diverges from the traditional bias-variance U-shape risk curve. Following this framework. these interpolating models should contain very high risk as drastically "overfits" to train data. Nonetheless, the aforementioned works demonstrate both empirical and theoretical results about the extraordinary ability of these minimum norm interpolators to generalize well on unseen data. This motivates their study in models for processing large data sets.
When A is the incidence matrix of graph with n vertices and d edges, i.e., = A-,,-
whenever e is an edge from a vertex a to v. then solutions to the linear system Ax = b correspond to flows that respect a given set of flow conservation constraints or demands specified by the vector b. In this case, the problem
min 1ell b
is known as the p-norm flow problem and has applications to graph clustering (Liu & Gleich, 2020; Fountoulakis et al., 2020), network science (Kalantari et al., 2008), and captures transshipment (p = 1), electrical flows (p- = 2), and max flow (p = oo) as special cases. In general, problem (1) is known as the lp regression problem, and algorithms for solving it, both for graphs and for general matrices, have recently been topic of intense study (Bubeck et al., 2018; Ene & Vladu, 2019; Adil et al., 2019b;a; Adil & Sachdeva, 2020; Adil et al., 2021; Jambulapati et al., 2022; 2024).
It is useful to generalize problem (1) by associating weight ej with each column j jE [d]. This captures p-norm flows with associated capacities. In this setting, we wish to solve the optimization problem given by
min ||C-'alle Ar-b b
for C = unless xy= O.
ca). cf 0 for some j [d], then we say the objective ||C-!z=lpp is infinite,
In many underdetermined linear systems, the number d of columns of A far exceeds the number n of rows. In this regime, it may be unreasonable to store the entire matrix A in memory to solve the 6p regression problem. This motivates streaming model of computation for this problem, in which the algorithm only accesses a small portion of the input at a time in a stream of updates, and the goal is solve the problem using memory that is much smaller than the length d of the stream. In this work, we study the column- column-arrival arrival streaming model, defined below.
Definition 1.1 coolumn-arrival streaming model). Consider an instance of problem (2) given by C (Cu..(c....,c)) E idddd A E Raad and b E R... We say that this instance is presented in a colunn-arrive arrival stream we receive d 1 updates in a stream in an arbitrary order, where each update consists of either a pair (al.c) consisting of a column a of A and an associated weight cj, or the vector b. In this work, we focus on algorithms which make only one pass through the data stream.
Special cases of the general streaming underdetermined lp regression problems have been studied by number of works in the literature of streaming algorithms. For p = 2, the work of Bartan & Pilanci (2023) gives an algorithm for estimating the cost of the regression problem by using sketching techniques. When A corresponds to the incidence matrix of graph, this model corresponds to an edge insertion graph stream (McGregor, 2014), and the corresponding graph streaming problems for transshipment (Becker et al., 2021), electrical flows (Kelner& & Levin, 2013; Kapralov et al., 2014; Cohen et al., 2016), and max flow (Assadi et al., 2019) have received much attention in the literature. The literature on graph streaming problems related to the max flow problem, such as reachability (Guruswami & Onak, 2013; Assadi & Raz, 2020; Chen et al., 2021) and maximum bipartite matching (Feigenbaum et al., 2005; McGregor, 2005; Ahn & Guha, 2013; Crouch & Stubbs, 2014; Paz & Schwartzman, 2017; Assadi et al., 2017; Kapralov, 2021) is even more vast.
In the study of streaming algorithms, we are typically interested in minimizing the space used by the algorithm. In our algorithms, we will allow for A to take real values and bound the space complexity
2

---

Published as a conference paper at ICLR 2025
in terms of the number of columns of A stored and additional words of space, and also give bit complexity bounds when the entries of A are bounded integers. In our lower bounds, we will prove bit complexity lower bounds in the latter complexity model.
1.1 OUR CONTRIBUTIONS
We design streaming algorithms for problem (2), handling a wide range of parameter settings. We also prove several corresponding lower bounds. We consider both the cost estimation problem, where the desired output is real number that approximates the minimum lp norm, as well as the harder vector-valued problem, where the desired output is an approximate minimizer vector æ. We work in the setting n & d. In stating our results, we use the notations O(-) and (2(-) to suppress factors polylogarithmic in n and d.
1.1.1 ESTIMATING THE MINIMUM COST
For the most basic setting of problem (1), where p = 2, there is well-known closed form expression for the minimizer vector: x= = M where M == AA Therefore, the minimum cost can be computed in O(n²) words of space, assuming real arithmetic. The method is straightforward: maintain the matrix M exactly, using the fact that each stream update-i.e., each new column of A- makes a rank-1 additive update M. At the end of the stream, return the solution A M- 16122 (b M 1///2
Notice that the space bound O(n²) is sublinear for d= (()). quadratic dependence on n is optimal, even for returning a constant-factor approximation to the minimum cost. This essentially settles the streaming complexity of lp regression for p However, it is unclear how these results generalize to the setting of * 2, when no closed form solutions are available for problem (I).
w We shall eventually prove that this
Our algorithms for more general E (1, oo] provide approximations to the cost of ép regression, up (1++ E) factor. They are based on the streaming construction of a notion of flow sparsifiers, which we define as follows.
Definition 1.2 (Flow sparsifier). Let C Iaddd d be diagonal matrix, A E Raxd and b R" Let p E po). Then, diagonal matrix S is a B-approximate Ep flow sparsifier with sparsity nnz(S) if S min C s B min
min A==b
Az=b ||C
A==b
In the graph setting, when A is the incidence matrix of a graph, notion of flow sparsifier corresponds to a weighted subgraph whose lp flow cost approximates that of the original graph. This generalizes the notion of spectral sparsifiers (Spielman & Teng, 2011), which correspond to the case = 2. Note that this differs from another line of work on "flow sparsifiers" that focuses on vertex sparsification for preserving the cost of flows when there are only small number of terminals of interest (Leighton & Moitra, 2010; Andoni et al., 2014; Krauthgamer & Mosenzon, 2023; Chen & Tan, 2024), whereas we construct edge sparsifiers with general vectors b, similar to a notion of flow sparsifiers used in Sherman (2013); Kelner et al. (2014).
Due to the work of Cohen et al. (2016), it is known how to construct electrical flow sparsifiers even in an online fashion, that is, the sparsifier can be constructed in one pass over an insertion stream of edges with the guarantee the edges are only ever kept and never thrown away.
To state the space requirements of our algorithm in full generality, we need the following notion of an online condition number (Cohen al., 2016; Woodruff & Yasuda, 2022).
Definition 1.3 (Online condition number). Let A Raxd Then, the online condition number (A) is defined as x 0l (A)) := |A| max /f ||A ||. where A, denotes the x j submatrix A formed by its first j columns, A, denotes the Moore Penrose pseudoinverse of this matrix, and ||-Il denotes the matrix 2-norm.
This brings us main algorithmic result for constructing Ep flow sparsifiers, in particular solving the cost estimation version of problem (2).
Theorem Let p (1) and let q = pp(p-1 1) E (1) be its Hölder conjugate exponent. There is algorithm that reads A E Randd and the diagonal matrix C Raddd in column-arriva stream
3

---

Published as a conference paper at ICLR 2025
(Definition 1.1) and, with probability least 1 8, outputs a (1 [1++)-appoxximat flow sparsifier (Definition 1.2). Furthermore, the algorithm stores at most columns of AC, with
s= m
log(d, x (AC),110)
and at most (np) additional words of space if A has real entries, and
s == O 0 m,xx 1oly
and most O logd) bits of additional space if AC has integer entries bounded by + poly (d). Furthermore, the columns of AC are stored in an online fashion, that is, the columns are selected irrevocably and are not thrown away throughout the stream.
A polylogarithmic dependence on the online condition number is typical of results in the literature of online numerical linear algebra, and is known to be necessary in general (Cohen et al., 2016) For p [2. se], our algorithms store only Ö()-2n) columns of A, which corresponds to an 2n) space algorithm-i.e.. a "semi-streaming" algorithm--n the setting of ép flows on undirected graphs. Theorem 1 generalizes results on spectral sparsification in the semi-streaming setting (Kelner & Levin, 2013; Kapralov et al., 2014; Cohen et al., 2016), which corresponds to the case of p= 2. We also note that Theorem separates the space complexity of max flow on undirected graphs from that on directed graphs. Indeed, on directed graphs, even the reachability problem, which is a special case of directed max flow, requires an almost quadratic (n) bits of space (Guruswami & Onak, 2013; Assadi Raz, 2020; Chen et al., 2021), even with multiple passes.
We now turn to lower bound results. These results all have the following structure. Suppose that there exists a aolival streaming algorithm for problem (1) that uses at most bits of space and, with probability at least 2/3, outputs a "good estimate" c to the cost min Ar=b | Then, in particular, there must exist randomized algorithms d and L such that, for any A E gaxd e produces an at-most-B- B-bit message M = s/ (A) so that, for any E RR, L outputs the good estimate H (M, b) function of M and b. The proofs of our lower bounds apply this more relaxed setting, effectively allowing an unlimited amount of space to process the columns of A as they are streamed in and only enforcing a space limitation before b is revealed.
First, we consider the algorithmically "easy" case of problem (1), when = 2. We remarked above that the folklore On"²) )-space algorithm optimal in its dependence on n. Formally, we establish the following result.
O-sa)espace
Theorem Fix p= 2. There is an absolute constant a > such that any column-arrives streaming algorithm that, with probability at least 2/3, computes a (1 + apprroooxinitioonn to the cost of problem (1) requires Q(n²) bits of space.
Next, we consider p p= in problem (1). In this case, the Hölder conjugate q = and thus Theorem 1 does not give (1 + aaappoxxiniiio algorithm. We show that this is inherent by proving the following lower bound.
Theorem 3. Fix p= 1 and let D 1 be arbitrary. There is a constant CD O such that any column-arrival streaming al algorithm that, with probability at least 2/3, computes an estimate with S min Am=bl bbll>>/) || < (Vn/CD) requires 2(nP) bits of space. This result applies even when all entries of the impul matrix A lie in (+1}.
In other words, for p 1, there is no poly(n) space algorithm for estimating the cost of & regression, even up to a factor of ol (i). In contrast, we shall soon present nearly matching algorithm that uses just O(n) poly log d bits of space to output an actual solution vector x E Rd that achieves a vn-factor approximation.
Finally, one can take p 0 in problem (1), with the natural interpretation that ||0||o nnz( This setting does not admit sublinear space solution, even with as small as 2, which we note below.
Theorem 4. Fix p 0 and take = 2. Any column-arrived streaming algorithm that, with probubility at least 2/3. outputs a 2-approximation to the cost minimum cost in problem (1) requires 2(d) bits of space.
Table summarizes the above results both upper and lower bounds for estimating the cost of ép regression.
4

---

be restricted to Published as a conference paper at ICLR 2025
Range of
Distortion
Space complexity (bits of space)
Reference
p=2
Onn)) Ō
Folklore
p E (2,00]
(1+E)
Theorem
p (1,2)
(1+E)
Ō 0(E-21/221) 319/211)
Theorem
p=2
(1+8)
Q((
Theorem 2
p=1 nvnn
n=(1)
Theorem 3
p=0
2
Q(d)
Theorem 4
Table 1: Space complexity of estimating the cost of e, regression, with q = p/ 1)
1.1.2 OUTPUTTING A GOOD SOLUTION
The streaming algorithm for Ep flows mentioned in Section 1.1.1 only output a scalar, approximating the cost of the regression problem. More generally, with small tp norm that satisfies Ax = b. At first glance, this may feel like asking for too much: after all, d-dimensional, which would seem to necessitate at least (2(d) space, thus precluding any sublinear space streaming algorithm. However, for p 1, one of the primary reasons for solving the to identify sparse solutions æ, which require much less than d space to specify. Furthermore, it may be possible to specify solutions in less than d space if we allow for some large distortion (i.e., approximation factor) the solution, say d0.1.
would want actual solution vector x Rd
basis pursuit problem Ae ||| 1
Thus, it is worth to look for algorithms that can output solution vector æ. especially if we allow for approximation errors as large as poly(n.d), d). We do design such an algorithm. Before discussing it, we bring up couple of related lower bounds that algorithm. Our lower bounds hold even in the very special setting
prove; these serve to set the context for the
= I, so the matrix A becomes row vector a and the vector becomes scalar b. Furthermore, the entries of {+1} and the scalar b on the right-han hand side of problem (1) can be fixed to d.
As with the lower bounds in Section 1.1.1, the next two lower bounds hold in the more relaxed setting where a can be processed by randomized algorithm a using unlimited space, resulting in B-bit message M a (a). Another randomized algorithm S must then produce good output vector a = 3 (M), based on M, succeeding with high probability. Clearly, this setting is a relaxation of a column-arrival streaming algorithm that uses B bits of space.
Theorem 5. Let E oo] and let q= p/ E [1,00) be its Hölder conjugate exponent. Let e E (0, / (8q)) and d E N. Any randomized algorithm that computes a B-bit summary of a E { from which e Rd can be produced such that, with probability at least 2/3, we have (a, .) = d and | < (1 E) min x) x) = requires B (2d).
In other words, for > 1, there is no algorithm using less than d space that can output a (1 + +)-- approximate solution for E S 1/(8q).
We also obtain a lower bound in the setting of large distortions, showing that for a B-factor approxi- mation, the streaming algorithm must use at least ( bits of space, provided that B < d. In particular, for 1, it is in fact not possible to output a solution in poly(n, logd) space unless the approximation factor at least poly(d).
Theorem 6. Let p E (1] and let q pppp-10pp111 1) (1,,o) be its Hölder conjugate exponent. Let B be a distortion parameter such that (B log logdd33 = cd for sufficiently small universal constant c. Then any randomized algorithm that computes a B-bit summary of a E [+1]d from which &t E TRd can be produced such that, with probability least 1-1/O(B1ogdy) we have (a, and || < B min I| requires B ((d/ (o))
We prove both of these lower bounds in Section 4. The high-accuracy lower bound of Theorem follows from relatively simple reduction one-pass streaming lower bounds for the INDEX com- munication problem (Kremer et al., 1995). On the other hand, Theorem 6 is our most technically advanced lower bound result, requiring additional techniques in order to extract information about from a B apapprooeetee solution for large B. In particular, our lower bound argument involves classify- ing the entries of B -papproxi solution x according to their contribution towards partitioning
5

---

Published as a conference paper at ICLR 2025
the coordinates into comparable classes. We then apply conditioning additional short string of advice to construct an estimator that extracts many bits of information about the input a from the solution æ.
Turning to upper bounds, we give a new algorithm for the general lp regression problem (2) that runs in a strongly sublinear d''S2(1) amount of space and outputs a solution vector achieving d'-2(1) distortion. Furthermore, in the of I, algorithm outputs solution with distortion most vn with space complexity poly(n, logd), which explains why the lower bounds of Theorems 5 and do not apply when p
Below, we write A to denote the n x |S] submatrix of A with columns indexed by S [d].
Theorem 7. Let p E [1, so] and let q q= pp 1) E [1, be its Hölder conjugate exponent. There is an algorithm that reads A E Rnxd and the diagonal matrix C' E Rdddd in a column-arrival stream and stores subset A and entries of C for 1, such that
most ((sd/ /Bd/BB) columns of A and entries of C.ror p >> 1, and O(s) columns of
B min A b
-C-lallp:
when p 2 2,
min
||C ||01 20pp S
min 1/1-1/2 1/B
||
allps when p 2,
(3)
===
Aw=b
n 1/2
min
C C pp
when p 1,
AC has real entries, and == O(nlogd) if AC is an integer matrix with entries bounded in absolute value by poly(d). Furthermore, the columns of AC are stored in an online fashion, that the columns are selected irrevocably and are not thrown away throughout the stream.
where s ((nnloodxx
As the statement of the above theorem suggests, our algorithm is based on column subset selection approach. fact outputs sparse solution that approximately solves the l, regression problem. Furthermore, the trade-off between the approximation factor B and the sparsity of this solution improves as + which affirms the intuition that minimizing the Ep norm for p closer to yields sparser solutions. Our algorithm uses the idea of well-conditioned spanning sets, which is subset of the columns of A such that all other columns can be written as a linear combination this subset with small coefficients, and we show that such subsets in fact be constructed in streaming fashion by using a streaming Löwner-John ellipsoid algorithm of Woodruff & Yasuda (2022).
Table 2 summarizes our upper and lower bounds for the problem of outputting solution vector.
Range of p
Distortion
Space complexity (bits of space)
Theorem
E (1, oo]
(1+E)
②2dd)
Theorem 5
p [1,00]
B
(dd/B2g)
Theorem 6
E (2,
B
n² (ddBB))
Theorem 7
(1,2) p
n! n//p11/2B
n² o(d/Ba)
Theorem 7
1/2
n² Polyooy
Theorem 7
Table 2: Space complexity of outputting a solution vector for lp regression, with q : pp(p
1.2 OPEN QUESTIONS
We have initiated the study of equality-constraie there are number of natural questions that remain unresolved. Our first question on closing the gap between our upper and lower bounds for streaming é, regression algorithms that output an approximate solution with large distortion. We conjecture that our lower bound is tight and raise the question of tightening the upper bound.
norm minimization in the streaming setting, and
Question 1.4. Is there a column-arrive streaming algorithm which outputs a solution å satisfying A b and || E B min Am=bl zl1p using space most poly(n). O.dd B

---

Published as a conference paper at ICLR 2025
Furthermore, in this work, we have focused the setting of one-pass algorithms, and we leave the question of studying algorithms and lower bounds for multi-pas pass algorithms for future work.
Question 1.5. What is the space complexity of p regression in the column-arrival streaming model for algorithms that make multiple passes over the data stream?
Lastly, our study has been mostly focused on the setting of Ep regression, and we have left open the possibility of obtaining better algorithms and lower bounds in the more specific setting of &p flows on undirected graphs. For instance, we already know that our lower bound of Theorem 3 can be circumvented by using streaming algorithms for constructing spanners (Althöfer et al., 1993; Feigenbaum et al., 2008; Baswana, 2008).
Question 1.6. What is the space complexity of Ep flows on undirected graphs in the edge insertion graph streaming model? What about for multi-pas algorithums?
2 FLOW SPARSIFIERS VIA ONLINE LEWIS WEIGHT SAMPLING
this section, we establish our first algorithmic result (Theorem 1). Our starting point for constructing Cp flow sparsifiers is the following duality lemma, we provide proof in Section B for completeness.
Lemma 2.1 (Strong duality for lp regression). Let p E [1, ,0), 9= p/ - E (1, and C, and b be an instance of problem (2) such that Az = b is feasible. Then
min Az=b
|C-|xx1|
max |CCA |CATv s1
y b.
Proof of Theorem 1. Suppose S E Rdxd is diagonal matrix with |CCA (1,t))i yll simultaneously for every y TR. (This notion of bg norm preservation for a subspace is known as an bg subspace embedding.) From the above duality lemma, it follows that modified dual problem with capacities SC approximates the original dual up to EI factor. To be precise,
max y b E1 5
max yd b.
|SCA
|CA |CATNl
In turn, by applying strong duality on both sides, we have that
min Aw=b
|| || -|1p (1 e) Au |C
That is, the Ep flow problem with capacities SC approximates the one capacities C.
remains to construct sparse reweighting matrix such that ||CAA ( CAA yllp simultaneously for every E TR. This can be done via random sampling technique known as tp Lewis weight sampling (Cohen & Peng, 2015; possible to construct S with
Woodruff & Yasuda, 2023a), which shows that
nnz (S) m
In fact, this construction can be done even in the streaming setting via online E Lewis weight sampling (Woodruff Yasuda, 2023a), up to small overhead, which is a factor polylogarithmic parameters. To make this precise, we recall result of Woodruff & Yasuda (2023a) on constructing 4p subspace embeddings: they show how to obtain the guarantee |S = (1 + e) Byyll for every E IR" when E dg is presented in a row-arrival stream. Fortunately, this corresponds to column-arrival stream for A when B = AT, Their result, translated into a column-arrival setting, is as follows.
some natural
Fact 2.2 (Online Ep Lewis weight sampling, Theorem 3.8 of Woodruff & Yasuda (2023a)). Let 9 E oo). Let A E Band Then, there column-arrival streaming algorithm which, with probability at least 1 1 8, outputs sampling matrix S which stores at most s rows such that for all y E RR" SAA y (1 E)]l yl1 with
s = O 2n maxmm111/2))
log(d ko Ol (A),1/8)
and at most O additional words space if A has real entries, and s= 0 max (La/2) ) logylog(d,1/6
and On logd) bits of additional space has integer entries bounded by + poly(d).
7

---

Published as a conference paper at ICLR 2025
Combining the above result with the duality-based derivation of eq. (4), obtain claimed algorithm for constructing Ep flow sparsifiers. This completes the proof of Theorem
Remark 2.3. We note that for Ep regression for pe E s0), our duality- approach for estimating the regression cost is also compatible with the turnstile streaming model, in which the matrix A undergoes entrywise updates of the form A(i, - A(i, j) + A for some update which can be positive or negative. Indeed, long line of work has established algorithms for recovering sketch Á such that ||A y = (1 + E)]l A ylly simultaneously for every y E R using only (nly (1,,,e,.logg logd) bits of space (Sohler& & Woodruff, 201 Meng Mahoney, 2013; Woodruff & Zhang, 2013; Wang & Woodruff, 2019; Li et al., 2021; Woodruff & Yasuda, 2023b; Mai et al., 2023; Munteanu & Omlor, 2024). is also possible to get strongly sublinear space for p E (1 (i.c., E (2, s0)) (Woodruff & Zhang, 2013). Unfortunately, these techniques yield dense approximations and thus typically do not give subquadratic space algorithms in the setting of graph streams.
Remark 2.4. If we give up the requirement that the columns are selected in an online fashion, then we can in fact remove the log XOL (A) dependence from this result by using the werge-and-reduce technique to compute lp subspace embeddings (c.f. Braverman et al. (2020)).
OUTPUTTING A GOOD SOLUTION IN SUBLINEAR SPACE
Here, we prove our second algorithmic result (Theorem 7). Recall that Al denotes the x |S] submatrix of A with columns indexed by S C [d].
3.1 STREAMING WELL-CONDITIONES SPANNING SUBSETS
We first note that the online John ellipsoid algorithm of Woodruff & Yasuda (2022) can be used to design streaming algorithm for identifying small subset of rows such that every other row be written as linear combination of the subset with small coefficients.
Definition 3.1 (Well-conditioned spanning subsets). Let E Raxd, Then, a subset S [d] of columns of a well-conditioned spanning subset if for every j e [d], there exists y E [R()) such that A 1 y = al and y S1.
Algorithms for computing well-conditioned spanning subsets have been studied by Knuth (1985); Woodruff & Yasuda (2023b); Bhaskara et al. (2023). The following result gives an efficient construc- tion of well-conditioned spanning subsets in a column-arrival stream.
Lemma 3.2 (Streaming well-conditioned spanning subsets). Let S C [d] be constructed in a column-
arrival stream by adding the column a' to S whenever (a (A ())) ()T))aa al 2 1. Then, S is cenl-conditioned spanning subset. Furthermore, [S] = Onloog(())))) (dx (A))) where k KoL (A) is the online condition number of A (see Definition 1.3), and [S] (nlogd) if A is an integer matrix with entries bounded by poly(d).
Proof. The bound on the size of is given by Woodruff & Yasuda (2022) using bounds on sum of online leverage scores (Cohen et al., 2016) so it remains to argue the correctness, which is inspired by an argument of Woodruff & Yasuda (2023b). If j S, then we can simply take y to the standard
basis vector corresponding to this index. Otherwise, we have that (a (A (A)(AA) )) a < 1, which
means that y = (A al is set of coefficients such that A a with & norm at most 1. O
The following lemma uses well-conditioned spanning subsets to sparsify linear combinations.
Lemma 3.3 (Sparsifying linear combinations). Let p os) Let C Idddd be a diagonal matrix, A E Raad, and let S C [d] be well-conditioned subset of the columns of AC. Then, for every Rd. there is E Rd such that supp(z) C. Ax Az, and
dd' (d'-1/p||=<))
when p > 2,
|| <
1/1p-1/ 1/2 1/p | when 2
Proof. We may assume that d 2 n, since otherwise we can take 2 = x. By the definition of well- conditioned spanning subsets, we write A =
-Y === AISY where A denotes the
8

---

Published as a conference paper at ICLR 2025
columns of A indexed by S and Y is an |S] x d matrix of coefficients with ((C)))-\ee)))) for every column E [d]. Then, Az A 1 YE x padding the vector Y with zeros gives vector that is supported on S. Furthermore,
|C -0
= 11lp= -
Σ ((C)))-' ( 1p/y||
triangle incquality
||>||| S max (1/pp11111/221000 d'11/p|/=11>>
Remark 3,4. For E (1,2) the n1/p11/2 factor in the distortion in Lemma 3.3 can be improved by using constructions of lp volumetric spanners, which give an analogue of well-conditioned spanning sets that bound the Ep norm of the coefficients rather than the &2 norm (Bhaskara et al., 2023).
However, this requires larger (n subset size S and we do not have good streaming algorithms for constructing these objects. Thus, we do not incorporate this trade-off for the sake of simplicity.
3.2 SPACE-DISTORTIES TRADE-OFES VIA BLOCKING
By combining the results of Lemmas 3.2 and 3.3, we immediately obtain an On logd) space algorithm with poly(n,d) distortion. To prove Theorem 7, we will now show how to apply this in blockwise fashion to obtain smooth trade-off between the space complexity and the distortion.
Proof of Theorem 7. For a block size parameter B = min (9,d) 2 n, suppose that run the well- conditioned spanning subset algorithm of Lemma 3.2 in each of the O(d/B) blocks of B columns. This algorithm stores Ossd/ B) columns, we store most columns for each of the d /B blocks. Let S denote the set of stored columns, and let x arg A== >=lpp- For the b-th block, let (a*)² denote the restriction of x" to the b-th block of columns. Then by Lemma 3.3, A(x A for some (ft) that is supported the columns stored by the algorithm and satisfies
||C (+)"lp S { [BI-1/0 C (x=" )
when 2 2,
-/11/--1/2 B1///p|/CCCCC (x*)))lpp when < 2.
By concatenating these solutions across the O(d/B) blocks, we obtain a solution that is supported on the columns stored by the algorithm, satisfies A&e b. and satisfies equation 3.
4 LOWER BOUNDS
Due to space constraints, the proofs of most of our lower bound results (Theorems 2, 3, 4, and 5) are given in Section C. However, we give the proof of Theorem here, as it is technically the most interesting and illustrates several important ideas. We first state several standard facts from information theory, which can be found in, e.g.. Cover & Thomas (2001).
Definition 4.1. Let Y,Y,Z be random variables supported on sets L.3, 2 with probability laws Ex.Py.Pu Pz. respectively. Then, the entropy of is defined as H(X)= = Eve æ Px (x) log2 px(x] and the conditional entropy of Y given X is defined as H(Y X) == Ee ye Px (x) Py x=x (y) py
The mutual information between X and Y is defined as I(X:V)= = H()) H(Y x) and the conditional
mutual information between X and Y given Z is defined as I Z) H(Y Z) H(Y (Z.
Fact 4.2. For random variables X and Y, we have H(),Y) = H(X) + H( X) = H(Y) + +H(X (Y) Fact 4.3 (Chain rule). For random variables .X. and Y, we have H( Y)
EL HXx) (Y,X,)), where Xzj denotes the random variables {Xy: :f j [d). j <
Fact 4.4. Let X be a random variable supported on K. Then, H(X) S [g with equality achieved when X distributed uniformly on L.
Fact 4.5 (Data processing inequality). Let X,Y be random variables supported on X. y and let f: - 2. be a function. Let Z f(Y). Then, I(x;Y) > 1(x;
N.
Fact 4.6 (Fano's 's inequality). Let X, Y be random variables supported on X. and let f: y + T
be a function. Let & = f(y) and let E denote the event that X + 8. Then, H(X IY)= < (rr(E))
[r log(122 1) where H2, (x) == -xlog, - (1 - -x) (1- - x) is the entropy of a Bernoulli random variable with parameter x [0,1]
9

---

Published as a conference paper at ICLR 2025
Next prove our lower bound for large approximation factors.
Theorem 6. Let p E (1,00] and let q- pp(p - be its Hölder conjugate exponent. Let B be a distortion parameter such that (B logd) = cd for sufficiently small universal constant Then any randomized algorithm that computes a B-bit summary of a E { from which & E R.. can be produced such that, with probability at least 1 1 logd)", we have (a. and
| S B - requires (dd/(Blogd))
Let a E [=1]d be random sign vector. Suppose that Alice constructs a message M as function of a, sends the message to Bob, and Bob constructs x such that (a, = d with || I B 8-min (a.))= | Since we can take x = a, the optimal solution must have bp norm at most d'/r.
Proof.
We will lower bound the length of the message M by obtaining lower bound on the mutual information I (( between Alice's 's random vector a and Bob's ' solution á. Indeed, the entropy of the message (M) lower bounds the length of the message, and we have I(;;a) I (M; < (MM) by the data processing inequality.
Let y be obtained by rounding the entries of & to the nearest integer, that (a. 2 d/2 and y takes on at most K = OB /d distinct values. Now consider partitioning K] into [logz K] groups, where the f-th group given by C2 {k [K] : 2 S k S 2 By averaging, there is group l such that Exec,. de Tinga KT
_ dx 2 TTong2 KT Note that there must be at least - d/(2 logg2
[ K1) S | 2B"d
coordinates belonging the class Cr+, so we must have that (2 Jlgg2 K
and thus we have that 2 S = (Bog)))
For each & E [K], let G5 C [d] denote the subset of coordinates for which yy E {+t), let o denote the restriction of y G2, and let d, = y²). Let D (sign(d)) Then, I(t:a) a) = I(: a + (); - I ( D a) 2 1(0;a D) - H() 2 a( D) - L. Furthermore, we have
d
a( D) 2 Iiy;a D) Σ Iy::a a.j. = Σ H(a D)- (0)-H(o H(a, D))
j=1
2 H(a D)
Σ H(a D.
(6)
By Fact 4.2, the first term is bounded by H(a -)=H(a) H(D) H a) 2 L so it remains the bound the latter term. We do this by constructing an estimator à for a and then applying Fano's inequality. Our estimator à is given by å sign(de) sign(y;) if the j-th coordinate has value - < L, and a random sign otherwise. We will now bound Pr # aj}.
For each k, let Je be the number of coordinates j j G2 such that å = aj- We then have |de (a.g*) k- (Ja- (lGg) (4) k- (2), (Gl) so the probability that â = aj for a coordinate
EE GR is 4 C = 1 + 14
x| Then, conditioned on the success of the algorithm and a choice of the G3
and de, the probability that á a is x 4/- which equals
G d
del
1 1 Σ
de
Σ
2k G
-
2k
dL
Σ
|dal
2
2
2L logg K
2
O(Blogd
KEC
Then overall, we have that
Pr[ay # #a 1
(++ O loggd
2 + O(Blogdy
(ogdd/
By Fano's inequality (Fact 4.6), then have that H(a; (.) H₂ Hr + a;l) < 1 1/O(Blogd)4 Now plugging into eq. (6) gives that I( (D) d (d- (ld 2(d/ / (B 10g - L and thus I(x 2 2(d/(B (B)ldg))2)) 2L Q(d/(B (Bgd/(loogd))) logd)²1) for L small enough as required by the theorem hypothesis. Thus, the length of the message M sent by Alice must be at least ((d/() logd)2²) bits, which concludes the proof.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
We thank the anonymous reviewers for useful feedback improving the presentation of this work. Part of this work done while D. Woodruff was at the Simons Institute for the Theory of Computing. D. Woodruff also acknowledges Simons Investigator Award, NSF CCF-2335412, and Office of Naval Research award number N000142112647
BIBLIOGRAPHY
P.-.. Absil, A. Edelman, and P. Koev. On the largest principal angle between random subspaces. Linear Algebra Appl., 414(1):288-29)))) 294, 2006. ISSN 0024-3795, doi: l0.1016/j.laa.0000 2005. 10.004. URL https::tp///... //ooi. .rg. 1ttp//1..111..// 6/6/ laa 2005. 10. 004. C.3
Deeksha Adil and Sushant Sachdeva. Faster p- p-norm minimizing flows, via smoothed q-norm problems. In Shuchi Chawla (ed.), Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, Jamuary 5-8, 2020, pp. 892-910 SIAM, 2020. doi: 10.1 137/ 1.978 161 1975994.44 URL wwwphtttph... http:///oo.ooo/g/..//oo/o 1137 11t.:///.711111199911111
Deeksha Adil, Rasmus Kyng, Richard Peng, and Sushant Sachdeva. Iterative refinement for fp- norm regression. In Timothy M. Chan (ed.), Proceedings of the Thirtieth Annual ACM-SIAM Symposium Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pp. 1404-1424. SIAM, 2019a. doi: 10. 10.1117/44 9781 0w1.17881111111 61117141197588 86.
977177999981119998886 URL https: htt.//ooooooo org/
Deeksha Adil, Richard Peng, and Sushant Sachdeva. Fast, provably convergent IRLS al- gorithm for p-norm linear regression. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' d'Alcéé-Buc, Emily B. Fox, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 14166-14177, 2019b. URL https: http:/ppoceeeng..eeeeeee/ neurips cc/paper/2019/ 73877 fb2 (0ee22dd5545511800 Abstrratbbttttt.b.a.eee..aaaaaae html.
hash/4 4ashh46c7cbbo
Deeksha Adil, Brian Bullins, Rasmus Kyng, and Sushant Sachdeva. Almost-liness lineer-iiee weighted f--norm solvers in slightly dense graphs via sparsification. In Nikhil Bansal, Emanuela Merelli, and James Worrell (eds.), 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference), volume 198 of LIPlcs, pp. 9:1-9:15. Schloss Dagstuhl- Leibniz-Zentrum für Informatik, 2021. doi: 10.4230/LIPcssICALL 2021.9. URL https: doi org/ 10. 4230 LLIILIIIIIII Ics. ICALP 2021.4022
Kook Jin Ahn and Sudipto Guha. Linear programming in the semi-streaming model with application to the maximum matching problem. Inf. Comput. 222:59- 79, 2013. doi: 10.10161.11.2012100000 iic.j......... 2012. 10. 6.
URL https: http://oooooooooooooooo/ooooooo wwtp:o//./...........
Ingo Althöfer, Gautam Das, David P. Dobkin, Deborah Joseph, and José Soares. On sparse spanners of weighted graphs. Discret. Comput. Geom., 9:81-100 1993. doi: 10.10077/F02188308. URL
https: /tte:///dooii htttps://doi..rg/100// org/10.... 1 1.2
Alexandr Andoni, Anupam Gupta, and Robert Krauthgamer. Towards (1 + ()) flow spar- sifiers. Chandra Chekuri (ed.), Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pp. 279-293. SIAM, 2014. doi: 10. 13771.977811119744002 9781 61 973142734222 20. 1.1.1
URL https: //t::///oo.. wwr.
Sepehr Assadi and Ran Raz. Near-quadratic lower bounds for two-pass graph streaming algorithms. In Sandy Irani (ed.), 61st IEEE Anmual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pp. 342-353. IEEE, 2020. doi: 10. 10//F004000000 2020.00040. URL https::t///......... /ooi org/ 11 1109/ F009///CC4400 000 2020. 2 00040. 1, 1.1.1
Sepehr Assadi, Sanjeev Khanna, and Yang Li. On estimating maximum matching size in graph streams. In Philip N. Klein (ed.), Proceedings of the Twenty- Annual ACM-SIAM Symposium Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19. pp.
11

---

Published as a conference paper at ICLR 2025
SIAM, 2017. doi: 1137/1.9781611
URL https::/aoi.org/////
113..
Sepehr Assadi, Yu Chen, and Sanjeev Khanna. Polynomial pass lower bounds for graph streaming algorithms. In Moses Charikar and Edith Cohen (eds.), Proceedings of the 51 Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pp. 265-276 ACM, 2019. doi: 10.114573313276.336333 URL https: http::::/dooo.og///00/ 1145/3313 331 3316361....11. 6361.
Burak Bartan and Mert Pilanci. Distributed sketching for randomized optimization: Exact characteri- zation, concentration, and lower bounds. JEEE Trans. Inf. Theory, 696)):850-3387, 2023, doi: 10. 1.110/99..2222392455599 URL https::/ wwg/1o..... 1109/1109/III11 2023.
Peter L Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. volume 117, pp. 30063-30070. National Acad Sciences, 2020.
Surender Baswana. Streaming algorithm for graph spanners single pass and constant processing time per edge. Inf. Process. Lett., 106(3):110-114 2008. doi: 10. 1.016/..P1..007.1..000 URL htttps:/doo..rre/
10..1111000 1016 wtt.e/...ppp...... ipp.. 001. 1.2
Ruben Becker, Sebastian Forster, Andreas Karrenbauer, and Christoph Lenzen. Near-optimal approximate shortest paths and transshipment in distributed and streaming models. SIAM J. Comput,, 50(3):815 856, 2021. doi: 10.1137/19M1286955 URL
#137/19M12888
Aditya Bhaskara, Sepideh Mahabadi, and Ali Vakilian. Tight bounds for volumetric spanners and ap- plications. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine (eds.), Advances in Neural Information Processing Systems 36: Annual Conference Neu- ral Information Processing Systems 2023, NeurlPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023. URL ht.h: http://pappprseee nips. ec acc/pappr__iii falerrfflee/ppe petaprr/2233. 02292652670752daffff 77555522227777555011101310 oat.:aaee....ttt1110.0aooaaaaaaa Contraact-Cooffeeeee.hhtttt
3.1, 3.4
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 61st IEEE Anmual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pp. 517-528. IEEE, 2020. doi: 10.1 URL htwph:tt////o..... //oi: org / 00/0009/00CCC500 67000 2020 0 00055. 2.4
Sébastien Bubeck. Michael B. Cohen, Yin Tat Lee, and Yuanzhi Li. An homotopy method for ép regression provably beyond self-concordance and in input-sparsity time. In Ilias Diakonikolas, David Kempe, and Monika Henzinger (eds.), Proceedings of the 50th Annual ACM SIGACT Symposium Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pp. 1130-1 137. ACM, 2018. doi: 10. 15/1144511887453318888 2145/3188745 3188776.
URL https: /wi. oro/ol/g///ooooo 10.
Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Zhao Song, and Huacheng Yu. Almost optimal super-constant-pel streaming lower bounds for reachability. Samir Khuller and Virginia Vassilevska Williams (eds.), STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pp. 570-583. ACM, 2021, doi: 10. (0..1445/3403255345111 1.1.1
URL https:ttt////.... /tt////oii.oo org 1145 3406325 3451038.
Scott Shaobing Chen, David L. Donoho, and Michael A. Saunders. Atomic decomposition by basis pursuit. SIAM Rev, 43(1):129-159, 2001. doi: 10. 10.1157/500661144507776666 URL https: / /ww.iiiiii////////// http//ooooogg///////////o wrr.
Yu Chen and Zihan Tan. On (1 + =)-approximate flow sparsifiers. In David P. Woodruff (ed.), Proceedings the 2024 ACM-SIAM Symposium Discrete Algorithms. SODA 2024, Alexandria. VA. USA, January 7-10, 2024, pp. 1568-1605 SIAM, 2024. doi: 10.1133//998816111999922... 63. 1.1.1
URL wttpt:ttt//c.......
/ /oo. .org 113//11111111111111
12

---

Published as a conference paper at ICLR 2025
Michael B. Cohen and Richard Peng. Lp row sampling by lewis weights. In Rocco A. Servedio and Ronitt Rubinfeld (eds.), Proceedings of the Porty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pp. 183-192. ACM, 2015. doi: 10. 141144//774633927446666 URL https::////........ //d./oi../// wwd.doooroooo wwg//r/ggoooo. /ergg///0/ 1 A
27466777 2,
Michael B. Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng, and Aaron Sidford. Uniform sampling for matrix approximation. In Tim Roughgarden red.), Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS 2015, Rehovot, Israel, January 11-13, 2015, pp. 181-199 ACM, 2015. doi: 10.1145/2688073.268888 https:/ / //w.//doioo////// , www.oogg//oooo 114. 688073888333 268733226681111 A
URL
Michael B. Cohen, Cameron Musco, and Jakub Pachocki. Online row sampling. In Klaus Jansen, Claire Mathieu, José D. P. Rolim, and Chris Umans ( Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2016, September 7-9, 2016, Paris, France, volume 60 of LIPIcs, pp. 7:1-7:18. Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2016. doi: D..430/LLPPcss -AIIIO--RANNOONN RANDOM URL https: /doi. org/10. .00...23330 4230
APPROX- RANDOM, 201 2016.7.111...0 ... 1,11, 1.1.1, 3,
Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. Wiley, 2001. ISBN 9780471062592. doi: 10.1002/0471200611. URL httts:://doi.rgoge
0471200611. 4
Michael Crouch and Daniel M. Stubbs. Improved streaming algorithms for weighted match- ing, via unweighted matching. In Klaus Jansen, José D. P. Rolim, Nikhil R. Devanur, and Cristopher Moore (eds.), Approximation, Randomization, and Combinatorial Optimization. Al- gorithms and Techniques, APPROX/RANDON 2014, September 4-6, 2014, Barcelona, Spain, volume 28 of LIPIcs, pp. 96-104. Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2014. doi: WE2.0OLIPICS.APPRRO AAPPROX-RANDOM.CO. RANDOM.2014.96. URL https: dog.ooo//o..0 /2/p//00..33///// LIPICS APPROX- RANDOM. 2014. 96.
Petros Drineas, Michael W. Mahoney, and Muthukrishnan. Sampling algorithms for & regression and applications. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, Miami, Florida, USA, January 22-26, 2006, pp. 1127-1136. ACM Press, 2006. URL http: / /ttplaac..cmm///////////////...a arg. wwt.atiittiic/c www.eeeieiiiiieeeeeeeeeeeeeeeeee
htt.:aaooo...mmmm1110000050101.1 11096822...1 A
Alina Ene and Adrian Vladu. Improved convergence for L and l. regression via iteratively reweighted least squares. Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pp. 1794-1801, PMLR, 2019. URL htwp:htt///tc htttt::/pproceedingg
mlr, www.sppeesssvve.. /ttp99///eeee html.
Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. On graph problems in a streaminr model. Theor. Comput. Sci., 348(2-3):00--211 2005, doi: 10.1016/J.TCS.200
URL attps:://do wttp:/ooo.111111./.......
wtt.//ttc...... 2005. 09. 013.
Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. Graph distances in the data-stream model. SIAM J. Comput., 1709-1777-1 2008. doi: 10.1137/ 070683155, URL attps::/don www.:0...rrr1..... 11.11.1.11111 113771706831153 1.2
Kimon Fountoulakis, Di Wang, and Shenghao Yang. p-norm flow diffusion for local graph clustering. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 3222-3232. PMLR, 2020. URL http:// http::/procediigg/ mmrr. wtt..ppess/vve /vls9//11//////// wwrl199ffuunn html.
Mina Ghashami, Edo Liberty, Jeff M. Phillips, and David P. Woodruff. Frequent directions: Simple and deterministic matrix sketching. SIAM J. Comput., 4566):1762-1792. 2016. doi: 10.1137/ 15M1009718. URL https:
1137 5M1 009718.
C.3
13

---

Published as a conference paper at ICLR 2025
Venkatesan Guruswami and Krzysztof Onak. Superlinear lower bounds for multipass graph pro- cessing. In Proceedings of the 28th Conference on Computational Complexity CCC 2013, K.lo Alto, California, USA. 5-7 June, 2013, pp. 287-298. IEEE Computer Society, 2013. doi: 10.1 109/CCC.201..37. URL https: /doi. org.grgggg.o C 1109 /tc.///ccc.... 2013.7....3. 1, 1.1.1
Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. volume 50, pp. 949. NIH Public Access, 2022.
Arun Jambulapati, Yang P. Liu, and Aaron Sidford. Improved iteration complexities for overcon- strained p-norm regression. In Stefano Leonardi and Anupam Gupta (eds.), STOC '22: 54th Annual ACM SIGACT Symposium Theory of Computing, Rome, Italy, June 20 24, 2022, pp. 529-542. ACM, 2022. doi: 10.1145/351993333519 3519935. 3519971.
URL pentts://do) .or./oogggoo.. 1
Arun Jambulapati, James R. Lee, Yang P. Liu, and Aaron Sidford. Sparsifying generalized linear models. In Bojan Mohar, Igor Shinkar, and Ryan O'Donnell (eds.). Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024, pp. 1665-1675. ACM, 2024. doi: 10.1145/36 (1019966688200664666666 URL https: //doi . org 10. 114 11111//333 /4445/36188 8260 364 9684.
Mchdi Kalantari, Masoumeh Haghpanahi, and Mark A. Shayman. A p-norm flow optimization problem in dense wireless sensor networks. INFOCOM 2008. 27th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Com- munications Societies, 13-18 April 2008, Phoenix, AZ, USA, Pp. 341-345. IEEE, 2008. doi: 10.1109//FFCOMM.20888 77. URL https: /tt.//oiiio/// www.oogg/ooooooo 1t.//11.1111911 9 INFOCOM. 2008 77.
Michael Kapralov. Space lower bounds for approximating maximum matching in the edge arrival model. In Dániel Marx (ed.), Proceedings of the 202/ ACM-SIAM Symposium on Discrete Algo- rithms, SODA 2021, Virtual Conference, January 10 13, 2021, pp. 1874-1893, SIAM, 2021 doi: 10.1137/1.97866 1976465. URL https::pp//..m 112.
Michael Kapralov and Kunal Talwar. On differentially private low rank approximation. In Sanjeev Khanna (ed.), Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium Discrete Algorithmss, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pp. 1395 1414. SIAM, 2013. doi: 10. 111111/19781111191110.... 97816119788 1 101. C.3
URL https: //t:///doo org/ 10 1137/1.
Michael Kapralov, Yin Tat Lee, Cameron Musco, Christopher Musco, and Aaron Sidford. Single pass spectral sparsification in dynamic streams. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pp. 561-570. IEEE Computer Society, 2014. doi: 10.1 10.1109/FOCS 201 4.66. URL https: / /ooi org/10. 1109 1109/POCS 2014 4. 66. 1, 1.1.1
Jonathan A. Kelner and Alex Levin. Spectral sparsification in the semi-streaming setting. Theory Comput. Syst. 53(2):243-262, 2013. doi: 10. 0..0077/500224-11-999966 URL httpp://d/// org/ 00//110.10 1007 /tt////022222 9396-1. 1.1.1
Jonathan A. Kelner, Yin Tat Lee, Lorenzo Orecchia, and Aaron Sidford. An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations. In Chandra Chekuri (ed.), Proceedings of the Twenty-Fiin -iint Anmual ACM-SIAM Symposium on Discrete Algorithums, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pp. 217-226. URL httpp:://dd .er.i.orggo100
SIAM, 2014. doi: 10. 9781 00211973422220 . 16. 1.1.1
Donald E Knuth. Semi-optimal bases for linear dependencies. Linear and Multilinear Algebra, 17 (1):1-4, 1985. 3.1
Robert Krauthgamer and Ron Mosenzon. Exact flow sparsification requires unbounded size. In Nikhil Bansal and Viswanath Nagarajan (eds.), Proceedings of the 2023 ACM-SIAM Symposium Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, pp. 2354-2367.
14

---

Published as a conference paper at ICLR 2025
SIAM, 2023. doi:
URL httpsttttto..ooogo//
9781611977551 ch91. 1.1.1
Ilan Kremer, Noam Nisan, and Dana Ron. On randomized one-round communication complexity. In Frank Thomson Leighton and Allan Borodin (eds.), Proceedings of the Twenty-Sevens Annual ACM Symposium on Theory of Computing, 29 May-I June 1995, Las Vegas, Nevada, USA, pp. 596-605. ACM, 1995. doi: 10. 40.1144522505882225277 URL https: / /ooi www.do..ror//..o.o 225058. 225277. 1.1.2
Frank Thomson Leighton and Ankur Moitra. Extensions and limits to vertex sparsification. In Leonard Schulman (ed.), Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pp. 47-56. ACM, 2010. doi: 10. 1145/1806689, 1806698. URL htttttss///i...oo wtwppooo.ooo.ooooo 1 1145/1145/1 1006889.6...88 1806698. 1.1.1
Yi Li, David P. Woodruff, and Taisuke Yasuda. Exponentially improved dimensionality reduction for & Subspace embeddings and independence testing. Mikhail Belkin and Samory Kpotufe (eds.), Conference on Learning Theory, COLT 2021, 15-19 August 2021, Boulder, Colorado, USA, volume 134 of Proceedings of Machine Learning Research, pp. 3111-3195. PMLR, 2021. URL http::/proceedeee
.mlr. a2eess/v34//10
html. 2.3
Yue Li and Yuting Wei. Minimum &n-rrrm interpolators: Precise asymptotics and multiple descent. 2021. 1
Meng Liu and David F. Gleich. Strongly local p p-norm-cut algorithms for semi-supervised learning and local graph clustering. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria- Florina Balcan, and Hsuan-Tien Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020. URL https: /tattts::/prccceeeeee http://pooceeeenn.ccee neurips.u.p...... cc htppppppp///////////// www.eeeertttaeeeeaaattt.....ee.e www.-bbbstttttteo.o...aaaeee .tml..
Tung Mai, Alexander Munteanu, Cameron Musco, Anup Rao, Chris Schwiegelshohn, and David P. Woodruff. Optimal sketching bounds for sparse linear regression. In Francisco J. R. Ruiz, Jennifer G. Dy, and
van de Meent (eds.), International Conference on Artificial Intelligence and Statistics, 25-27 April 2023, Palau de Congressos, Valencia, Spain, volume 206 of Proceedings of Machine Learning Research, pp. 11288-11316. PMLR, 2023. URL https::/prroeeeteeee http://poooeenngss////e/. milrppress v200 mwa33aa..aa//aammmmmmmmmmmmma33. html. 2.3
Andrew McGregor. Finding graph matchings in data streams. In Chandra Chekuri, Klaus Jansen, José D. P. Rolim, and Luca Trevisan (eds.), Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, 8th International Workshop Approximation Algo- rithms for Combinatorial Optimization Problems, APPROX 2005 and 9th InternationalWorksshhe on Randomization and Computation, RANDOM 2005, Berkeley, CA, USA, August 22-24, 2005, Proceedings. volume 3624 of Lecture Notes in Computer Science, pp. 170-181. Springer, 2005. doi: 10.1007/115384622__11 URL https: doii wrt.rrggl/0.. 1010100111112211111 00d.../00/....00/13333663333131
Andrew McGregor. Graph stream algorithms: a survey, SIGMOD Rec., 43(1):9-00, 2014. doi: 10.1 10.1145526776922.2276666 URL htttp::/ddo.org//// 1ttp://1.1111/22266113 2t2.2277662.22699..
Xiangrui Meng and Michael W. Mahoney, Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum (eds.), Symposium on Theory of Computing Conference, STOC'I3, Palo Alto, CA, USA, June 144, 2013, pp. 91-100. ACM, 2013. doi: 10. 011114/2288608244886865 URL https: //doi. org 10 0. 1 2 888888688888 2488621. 2.3
Alexander Munteanu and Simon Omlor. Turnstile ép leverage score sampling with applications. In Proceedings of the 41st International Conference on Machine Learning, ICML 2024, Proceedings of Machine Learning Research. PMLR, 2024. 2.3
Udaya Parampalli, Xiaohu Tang, and Serdar Boztas. On the construction of binary sequence families with low correlation and large sizes. IEEE Trans. Inf. Theory, 19()):1022-188) 2013. 10. 1 109/TTTT2012.221199 URL https: http//di..r///// 1ttpg//0..10//1//11 22129222222222222222222222222222 99919 8
doi:
15

---

Published as a conference paper at ICLR 2025
Ami Paz and Gregory Schwartzman. A (2 &) = appproxximtaoo for maximum weight matching in Annual ACM-SIAM Symposium Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pp. 2153-2161. SIAM, 2017. doi: 1777711978111999979888888 140. URL https: //ooi org/ 10. 1137/1, 9781 61 77277778.. 1...1140. 140.
the semi-streaming model. In Philip N. Klein (ed.), Proceedings of the
Anup Rao and Amir Yehudayoff. Communicattion complexity and applications. Cambridge University Press. Cambridge, 2020. ISBN 978-1-108-49998-5, C.I
Jonah Sherman. Nearly maximum flows in nearly linear time. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pp. 269. IEEE Computer Society, 2013. doi: 10.1109/FOCS.2013333 URL hetps://doi.
org/ 10. 1109/FOCS 2013.32122 36. 1.1.1
Christian Sohler and David P. Woodruff. Subspace embeddings for the Inoor with applications. In Lance Fortnow and Salil P. Vadhan (eds.), Proceedings of the 43rd ACM Symposium Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011, I, pp. 755-764. ACM, 2011. doi: 1993733336
10.1145/199366..1 1993736. URL https:/ //wii/oiii.///////// ttt.doiooo/oo/oooooooooooooooooe 10. 1145/ 1991699936688 1...66...9366 2.3
Daniel A. Spielman and Shang-Hua Teng. Spectral sparsification of graphs SIAM Comput., 1004); 2011. doi: 10. 10.1137088074489X URL https: http://oo...rrr.oo 1137/ 08C74489X. 1.1.1
Ruosong Wang and David P. Woodruff. Tight bounds for lp oblivious subspace embeddings. In Timothy M. Chan (ed.), Proceedings of the Thirtieth Annual ACM-SIAM Symposium Dis- crete Algorithms, SODA 2019, San Diego, Califorria, USA, Jamuary 6-9, 2019, pp. 1825-1843. SIAM, 2019. doi: 10. 1117//.9778611119488..110 URL https:: ctttps://doi.ooee http:///.....0/11111111///1 9781611975482 110. 2.3
David P. Woodruff and Taisuke Yasuda. High-dimensional geometric streaming in polynomial space. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 November 3, 2022, pp. 732-743. IEEE, 2022. doi: 10. (0.1109/F0C554457..20 2022. 00075. URL https:: //l:////oo /ooiiiioo////o org /10. 1109 /TT.///C5555454 2022 00075. 5. 1.1.1, 1.1.2, 3.1,
3.1. C.3
David P. Woodruff and Taisuke Yasuda. Online Lewis weight sampling. In Nikhil Bansal and Viswanath Nagarajan (eds.), Proceedings of the 2023 ACM-SIAM Symposium on Dis- crete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, pp. 4622 4666. SIAM, URL https: ort...oo/00.11/7//
2023a. doi: 10. 00.1137/1.771161111 9781611977554 c51 2, 2.2,
David P. Woodruff and Taisuke Yasuda. New subset selection algorithms for low rank approximation: Offline and online. In Barna Saha and Rocco A. Servedio (eds.), Proceedings of the 55th Anmual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, URL https: /ttp:///oooo//o./
pp. 1802 1813. ACM, 2023b. doi: 10. 10.1145/35644463555511 1145/356422 3585100. 2.3, 3.1,
David P. Woodruff and Qin Zhang. Subspace embeddings and é reregression using exponential random variables. In Shai Shalev-Shwartz and Ingo Steinwart (eds.). COLT20113 The 26th Annual Conference on Learning Theory, June 12-14. 2013, Princeton University, NJ, USA, volume 30 of JMLR Workshop and Conference Proceedings, pp. 546-567. 567. JMLR.org, 2013. URL http: //proceeding ings mlr, presss vv30 /3330/30000001111 Moodzuff13 html. 2.3
16

---

Published as a conference paper at ICLR 2025
A PRELIMINARIES ON ONLINE SAMPLING AND CORESETS
The literature online sampling and coresets was initiated by the work of Cohen al. (2016). In the setting of online coresets, the input is an insertion-only stream of n vectors a; E IRd for i [n] which arrive at time. The goal is then randomly select subset of these vectors in online fashion, that is, at each time step i, we must irrevocably decide whether to keep or not. The selected subset called an online coreset or simply a coreset. The work of Cohen al. (2016) considered algorithms for outputting online coresets with the guarantee of an l subspace embedding.
Definition A.1. Let A Rand Then, linear map E g is E2 subspace embedding for A with distortion (1 EI+ if
for all x R.,
=
Note that a weighted subset r points, i... a coreset, can be represented by such linear map by taking the j-th row of S to be the weighted indicator for one of the и points. In the offline setting, i.c. when all the n vectors are known before hand as an n d matrix A, then can be constructed as coreset of size Ō 2d) using technique known as leverage score sampling (Drineas et al., 2006; Cohen et al., 2015). The work Cohen et al. (2016) then showed that this technique can fact be generalized to the online coreset setting, showing that S be constructed in the online setting with size of Ō( -d XOL, where OL is as defined in Definition 1.3.
In the present work, require online constructions of lp subspace embeddings, rather than l subspace embeddings.
Definition A.2. Let A E Rxxd and [1, Then, a linear map S E R is an lp subspace embedding for A with distortion (1+8) if
for all x Rd.
SAAI| - (1+
Analogous constructions for this setting were obtained by the work of Woodruff & Yasuda (2023a), which generalized technique known Ep Lewis weight sampling Cohen & Peng (2015) to the online setting. We refer to Cohen et al. (2016) and Woodruff & Yasuda (2023a) for additional details.
B DUALITY
We prove Lemma 2.1. Consider the primal objective given by
min ||| æ1pp-
Az=b
We write the constraint as a Lagrangian optimization problem as
meld R= min max || || <1lp + (b- Ax).
Now if Az = b is feasible, then by strong duality, this is equivalent to
max min || 'llpp + (b Az) ye w63d
max min yER" wERd ||C +y b y Ax.
Note that
min xx- y Ax = min =gRd
|| Tolll-yyTACCE ACC--12
melea
[-00,
when
CAA y1l >
0,
when CA 41l4 $1. 1.
Thus, the dual problem is given by
max
b.
|IA 1
17

---

Published as a conference paper at ICLR 2025
C LOWER BOUND PROOFS
C.I. PRELIMINARIES
We will the one-way communication lower bound for the INDEX problem. It is known that if Alice has uniformly random binary string with d bits and Bob has uniformly random index j e [d] then in order for Bob correctly output the j-th bit of Alice's string, Alice must send at least (2 bits (Rao & Yehudayoff, 2020).
C.2 LOWER BOUNDS FOR OUTPUTTING A GOOD SOLUTION
We first prove our lower bound for outputting (1 + E--fccoor approximate solution.
Theorem 5. Let p E (1, oo] and let 9 p/
[1, be its Hölder conjugate exponent. Let
E (0, (/8)) and d E N. Any randomized algorithm that computes B-bit summary of a E {+1] from which & E Idd can be produced such thut, with probability at least 2/3, we have (a, = d and |@@|p < (1 + E) min =a))|==)) requires B = Q)d).
Proof. By standard error reduction techniques, may assume that the minimization algorithm succeeds with probability at least 9/10. Now let a E {=1]d be random sign vector. Since we can take a, we obtain that
min x 1p S d
(a.x)
Therefore, a correct (1 + appproxxitttelyy optimal solution & must have || S (1 ((1++ddde E) Fur- thermore, the number J of coordinates j [d] such that sign(i,) a, satisfies
d= (a, k)
| (1 + Ma
where the second step above follows from Hölder's inequality. Thus, 2 d/(1+ 2 d/(1+2222)
It follows that, for a random index E [d], Pr(sign($j) = =ayl 1/(1 + 2qE). By union bound, it follows that if Alice, given input a, were to send the algorithm'' 's B-bit summary message Bob, it would enable Bob to correctly solve the INDEX problem on this instance with probability at least 1 (1 - 1/(1 + 2qe)) - 1/10 2 2/3. Therefore, = Q
Remark C.1. The above lower bound instance fails for p 1 since for 1, we can choose optimal I-sparse solution by maintaining the largest element in the vector a.
C.3 LOWER BOUNDS FOR ESTIMATING THE COST
We now turn to the problem of estimating the minimum cost of the basic l, regression problem, i.e. problem (1), As promised, we obtain lower bounds handling the cases É 1,,].
When p O, we have the following.
Theorem 4. Fix p 0 and take n = 2. Any column-arrived streaming algorithm that, with probability
at least 2/3, outputs a 2-approximation to the cost minimum cost in problem (1) requires Q)d) bits of space.
Proof sketch. It is not hard to show that for this version of the problem, there is no sublinear-space algorithm for approximating the optimal objective value small constant factor. Indeed, even with n = 2, obtaining a better than 2-approximation requires (2(d) space, because the problem requires us to determine whether or not vector parallel to appears among the columns of A. If the stream presents the columns of A prior to b, one can then give reduction from the standard INDEX communication problem to the (approximate) fo-norm minimization problem.
When p 1, we show that estimating the cost of the regression problem even to factor of o(vn) not possible using poly(n) space. This fact is intimately related to the fact that the dual of the & regression problem involves an f... constraint set, and resembles a lower bound argument of Woodruff & Yasuda (2022).
We the following result from coding theory.
18

---

Published as a conference paper at ICLR 2025
Theorem 8 (Parampalli et al. (2013)). For any D Z I and n a set S S [= and a constant Cp dependent only on which satisfy (1) |S| = =nn, and (2) for any 5,I S such that s # (s.t)] S Cnyn
2 - for some integer k, there exists
Using the above result, we show the following lower bound for estimating the cost of 4 regression. Theorem 3. Fix p = 1 and let D 21 1 be arbitrary. There is a constant CD > O such that any column-arrival streaming algorithm that, with probability at least 2/3, computes an estimate with S. Ax-Aa=blle 11 < (Vn/CD)) requires 22n")) bits of space. This result applies even when all entries of the input matrix A lie in {=1}.
Proof. Let S be the set constructed in Theorem 8. We will show that estimating the cost to sufficiently small distortion solves an INDEX instance on (S] = n² items.
We associate bit strings of length n² with subsets of S. To solve the INDEX problem, consider the following protocol. First, Alice constructs a matrix A by taking the columns to be the vectors of the subset A C S associated with the input bit string. Alice then sends the message M constructed from the matrix A to Bob. Finally, Bob takes b to be the vector of S associated with the input index j and uses b and the message M to output an estimate
c to the regression cost min Am=b||>||11
Note that the dual problem is max max y1a y b. If b is element of Alice's subset A C S, then for any dual feasible we have - || y/ S. 1. By strong duality, there is primal optimal solution æ such that ||œ||| = y b S 1, so the optimal solution is at most 1. On the other hand, if b is not an element of Alice's subset A C S, then we have that A bl-- S Cnvã so y = b/CD witnesses primal value of at least /n/Co- Thus, approximation the cost within factor of vn/Co will allow Bob to solve the INDEX problem.
When p = 2, which is the "easiest" case of the regression problem, we show that estimating the optimal objective value of the problem given by eq. (1) to a small constant factor requires 22nn)) space. Recall that O(n²) is the space required for storing and maintaining AAT: doing so enables us to compute the optimum exactly.
Theorem Fix p 2. There is an absolute constant a a>>0 such that any column-arrival streaming algorithm that, with probability at least 2/3, computes a (1 + apprrooxxiiioooon to the cost of problem (1) requires Q(n²) bits of space.
Proof. We will use the fact that there exists a collection (PI,..., Pm of size 2 exp()(n²2) such that (1) each P. is an n n orthogonal projection matrix onto an n/2-dimensional subspace, and (2) for all i * j. we have || P; Pjll2 2 1. which proven in Kapralov & Talwar (2013, Section 5.2) using a result of Absil et al. (2006) (see also Ghashami et al. (2016, Theorem 4.1)).
For each i, let Q: = P. + I. We claim that if A is taken to be one of these matrices Q. then a cost-approximating algorithm must be able to tell apart the m distinct choices Q; by solving the regression problem on various choices of b; by standard information-theoretie arguments it must therefore use 2(logm)) m) = 2(n²) bits of space, if it succeeds with probability at least 2/3.
To prove this claim, we show that for all + j. there exists a suitable vector such that the costs corresponding to A = Q, and A A= Q, differ by at least some absolute constant, whereas each of these costs is at most O(1). Since the optimum cost is given by min Ar- b|1==113 b" (AAT)- bb this is equivalent to showing that
Since P. is an orthogonal projection, we can show that
= - Indeed, let P, = UAUT be the eigendecomposition of P,, where A is diagonal matrix with n/2 ones. Then
Q.Q. = () -
3P, +I U3A +)U" and (3A + T) 3A) 4I 4/ so by rotating back to the U basis and dividing by 4. (Q.Q, -1=-,)--U0(
12A 2A4+I-9A- 32 -
AAUU = - This then gives I[(QQQ,) (Q (Q)Q)) =1|-=-1---- ||(- (P Pj) 2 2 3
16
which establishes eq. (7) and completes the proof.
19


Reviews:
[{"review_id": "WXHUOnI89P", "reviewer": "Reviewer_Rniw", "summary": "The paper gives upper bounds and lower bounds for streaming underdetermined $\\ell_p$ linear regression in the column arrival model. The results apply both to the value of the best fit, and to the actual solution. There are various results, depending on the value of $p$ and the approximation guarantees. The arguments use duality and sparsification.", "questions": "None", "limitations": "", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper explores the full range of values of $p$.", "weaknesses": "The methods rely substantially on past work.", "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": "", "extra_scores": {}}, {"review_id": "bmvEKsc68Q", "reviewer": "Reviewer_SDMB", "summary": "The paper initiates the study of $p$-norm regression in the one-pass streaming setting. They consider the underdetermined setting $\\min_{Ax=b} \\|x\\|_p$ where $A$ has size $n\\times d$, $n<<d$, receives $d$ column updates. They consider $p\\in [1,\\infty)$. When we consider instances graphs, these updates correspond to edge insertions. \n\nThe first result is an algorithm for “p-norm flow sparsifier” in $O(n^2)$ space which is a general version of graph sparsifiers which minimize the $\\ell_p$-norm. This algorithm follows from using the online lewis weight sampling algorithm of Woodruff and Yasuda’22 on the dual problem. The other algorithmic result deals with giving a tradeoff between the size of the sparsifier and objective error when the goal is to maintain the entire solution vector x. The first algorithm only maintains the objective value.\n\nThe paper also presents several information theoretic lower bounds which match these upper bounds. They also give some extra lower bounds for the case of $p=2$.", "questions": "1. Can the authors add a comparison with what is known in online algorithms in the corresponding settings?\n2. The tables in the paper, that give the lower and upper bounds for different settings, can these be split in a different way so that its easier to contrast the lower and upper bounds for all settings? This would also make clear what settings are still unknown.", "limitations": "", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The paper studies an important problem and makes a significant amount of progress in the new direction of streaming algorithms for regression. They also leave some good open questions in the paper. The techniques are also quite simple and use previous works quite well. The main technical core is the lower bound part, which is of independent interest.", "weaknesses": "It seems like there are too many ideas and previous results used in the paper. Would be useful to have some more preliminaries in the appendix or somewhere.", "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": "", "extra_scores": {}}, {"review_id": "iEs4H9rest", "reviewer": "Reviewer_fogf", "summary": "The $\\ell_p$ regression $\\min_{\\mathbf{Ax} = \\mathbf{b}} ||\\mathbf{x}||_p$ is a fundamental problem in machine learning, data science, and numerical linear algebra. When $p = 2$, it is the classical linear regression problem and has a closed-form solution $\\mathbf{x}^* = \\mathbf{A}^\\top (\\mathbf{A}\\mathbf{A}^\\top)^{-1} \\mathbf{b}$. The general $\\ell_p$ regression has been well-studied, in particular, when $\\mathbf{A}$ is the vertex-edge incidence matrix, it is the $\\ell_p$-norm flow problem, which corresponds to transshipment, Laplacian solver, and maximum flow if $p = 1, 2$, and $\\infty$ respectively. This paper considers the scenario that the matrix $\\mathbf{A} \\in \\mathbb{R}^{n \\times d}$ has $n \\ll d$, which leads to the linear system $\\mathbf{Ax} = \\mathbf{b}$ being underdetermined. In this case, it is impractical to store all the $d$ columns of $\\mathbf{A}$, which motivates the usage of the column-arrival streaming model. In addition, there are two kinds of solutions to $\\ell_p$ regression: (1) $\\textit{cost estimation}$ that approximates the optimal $\\ell_p$ norm; (2) $\\textit{vector-valued}$ that approximates the optimal solution $\\mathbf{x}^*$. For the first kind, this paper achieves space complexity $\\widetilde{O}(\\epsilon^{-2} n^{\\ 1+max\\\\{1, p/2(p-1)\\\\}})$, which is $\\widetilde{O}(\\epsilon^{-2} n^2)$ when $p > 2$, and also gives lower bounds for $p = 0, 1, 2$. For the second kind, this paper also provides lower bounds and upper bounds for different values of $p$.", "questions": "(1) In Theorem 1, Line 153, should \"$s$ rows\" be \"$s$ columns\"? At Line 164, should the second $\\widetilde{O}(\\epsilon^{-2} n)$ be $\\widetilde{O}(\\epsilon^{-2} n^2)$? Please verify that.     \n(2) In Theorem 1, when $p \\to 1$, like $p = 1.1$, $q = p/(p-1)$ would be a large constant. In this case, could you discuss the behavior of the proposed algorithm? If it is indeed a non-trivial issue, could you give a brief analysis or comment in this paper on $p \\to 1$?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "(1) This paper researches the general $\\ell_p$ regression problem under the column-arrival streaming model, while the existing work only considers the special case, like $p = 2$ or $\\mathbf{A}$ is the vertex-edge incidence matrix.  \n(2) For general $p$, this paper establishes both lower and upper bounds on space complexity for the two kinds of solutions: cost estimation and vector-valued problems. These new results strengthen the paper's contributions.  \n(3) This paper has an extensive set of references and a comprehensive summary of the related work.", "weaknesses": "The $p$-norm flow problem defined in (1) (Line 61) is not exact. The correct one should be $\\min_{\\mathbf{Ax} = \\mathbf{b}} ||\\text{diag}(\\mathbf{w}) \\cdot \\mathbf{x}||_p$. To be specific, when $p = 1$ and $\\mathbf{w}$ is the cost vector, then it is a transshipment problem; when $p = 2$ and $\\mathbf{w} = \\mathbf{r}^{1/2}$, where $\\mathbf{r}$ is the resistance vector, then it is reduced to a Laplacian solver; when $p = \\infty$ and $\\mathbf{w} = \\mathbf{c}^{-1}$, where $\\mathbf{c}$ is the capacity vector, then it is the maximum flow problem.      \n\nBy this formulation, it is the same as formulation (2). As a special case, when $\\mathbf{A}$ is a vertex-edge incidence matrix in the graph streaming problem, there is some existing work (Line 91-97) on transshipment, electrical flow, maximum flow, etc. Could you compare this work with their results?", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Spotlight)