The Space Complexity of Approximating Logistic Loss
Authors: Gregory Dexter
Petros Drineas
Rajiv Khanna
Venue: NeurIPS 2024 poster (2024)
Keywords: logistic regression
data structure
space complexity
approximation algorithm
Primary area: optimization

Abstract: We provide space complexity lower bounds for data structures that approximate logistic loss up to $\epsilon$-relative error on a logistic regression problem with data $\mathbf{X} \in \mathbb{R}^{n \times d}$ and labels $\mathbf{y} \in \\{-1,1\\}^d$. The space complexity of existing coreset constructions depend on a natural complexity measure $\mu_\mathbf{y}(\mathbf{X})$. We give an $\tilde{\Omega}(\frac{d}{\epsilon^2})$ space complexity lower bound in the regime $\mu_\mathbf{y}(\mathbf{X}) = \mathcal{O}(1)$ that shows existing coresets are optimal in this regime up to lower order factors. We also prove a general $\tilde{\Omega}(d\cdot \mu_\mathbf{y}(\mathbf{X}))$ space lower bound when $\epsilon$ is constant, showing that the dependency on $\mu_\mathbf{y}(\mathbf{X})$ is not an artifact of mergeable coresets. Finally, we refute a prior conjecture that $\mu_\mathbf{y}(\mathbf{X})$ is hard to compute by providing an efficient linear programming formulation, and we empirically compare our algorithm to prior approximate methods.

The Space Complexity of Approximating Logistic Loss
Gregory Dexter Linkedln Corporation gdexter0 wateeerl@inneeee Linkedin..... com
Petros Drineas
Department of Computer Science
Purdue University
pdrineas ruu edu
Rajiy Khanna
Department of Computer Science
Purdue University
rajivak@purdue edu
Abstract
We provide space complexity lower bounds for data structures that approximate logistic loss up to c-relative error on logistic regression problem with data
X E Raxd and labels y E {-1,1] The space complexity of existing coreset constructions depend on natural complexity measure My (X). first defined in [IO].
We give (2 {) space complexity lower bound in the regime Hyy (X) O(1) that shows existing coresets are optimal this regime up to lower order factors. We also prove general f2(d Hy (X)) space lower bound when is constant, showing that the dependency on jty (X) is not artifact of mergeable coresets. Finally, we refute a prior conjecture that Hy (X) is hard to compute by providing an efficient linear programming formulation, and empirically compare algorithm prior approximate methods.
Introduction
Logistic regression is an indispensable tool in data analysis, dating back to at least the early 19th century. was originally used to make predictions in social science and chemistry applications [54 3), but over the past 200 years it has been applied to all data-driven scientific domains, from economics and the social sciences to physics, medicine, and biology. regression model is a statistical abstraction that models the probability of one of two alternatives or classes by expressing the log-odds (the logarithm of the odds) for the class as linear combination of one more predictor variables.
a high level, the (binary) logistic
Formally, logistic regression aims find a parameter vector B E RRd that minimizes the logistic loss, L(3), which is defined as follows:
((B) = Σ log(1 te vix(o))
(I)
where X RRd is the data matrix (n points in Rd, with x" being the rows X) and y E {-1, 13" the vector of labels whose entries the y:. Due to the central importance of logistic regression, algorithms and methods to improve the efficiency of minimizing the logistic loss are always of interest
9.
The prior study of linear regression, a much simpler problem that admits closed-form solution, has provided ample guidance on how may expect improve the efficiency of logistic regression. Let
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

us first consider how a data structure that approximates re-resressoon loss may be leveraged to design efficient algorithms for linear regression. Let (-): E - R be data structure such that:
(1 ()=x)]AAx - b - ((x) < + e bll2-
Then, for, say, any E (0, 1/3)
1
x
argmin D(x) + ||Ax - bll2 - XER
min xER
| bl12
- (1 3E) min XER
|Ax bll2-
That is, data structure that approximates the fy-regression loss up to e-relative error may be used to solve the original regression problem up to 3e-relative enror. This is particularly interesting when D(-) has lower space complexity than the original problem or can minimized more efficiently.
Practically efficient data structures satisfying these criteria for linear regression have been instantiated through matrix sketching and leverage score sampling [6]. There extensive work exploring constructions of matrix S E R where given data matrix A E Raxd and vector of labels R", we may solve the lower dimensional problem x argmin ||SAx Sb/12 achieve
1tc the guarantee ||Ax bll2 S I-r minxER= || | b122 for chosen e > O. Under conditions that guarantee that s < TI, we can achieve significant computational time and space savings by following such an approach. An important class of matrices S E =x*= that guarantee the above approximation are the so-called lz subssace embeddings which satisfy:
(1 -|Ax bll2 S ||S(Ax b)ll2 S (1+ l) -1Ax-bbjy bllz for all x R.d.
Despite the central importance of logistic regression in statistics and machine learning, relatively little is known about how the method behaves when matrix sketching and sampling are applied to its input. Munteanu et al. [T0] [[]] initiated the study of coresets for logistic regression. Meanwhile, Munteanu and Omlor [9] provide the current state-of-the-art bounds bounds on the size of a coreset for logistic regression. Analogously linear regression, these works present efficient data structure E(-) such that
(1 (1- (1-c)_()) S ((8) s ()+
We call É(-) c-relative error approximation to the logistic loss. Prior work on coreset construction for logistic regression critically depends on the data complexity measure Hy (X), which was first introduced in [10), and is defined as follows.
Definition 1. (Classification Complexity Measure (TO) For any X E Raxd and E (-1,1)", let
|| IDyx,)+ll
My (X) = sup
8&0 (6x
where Dy is a diagonal matrix with y as its diagonal, and (Dy and (Dy denote the positive and the negative entries of Dy respectively.
Specifically, these methods construct coresct by storing a subset of the rows indexed by S C (1...n} such that S Ö( (X) and generating set of weights hwiees such that each w; is specified by Ollog nd) bits 9 The approximate logistic loss is then computed
[(3) = Σ log(1 ( + e-xxx"
(3)
RES
is an e-relative error approximation to L(B). We see that My (X) is important in determining how compressible a logistic regression problem is through coresets, and prior has proven this dependency in coresets is necessary (17). Our work further shows this dependency is fundamental to the space complexity of approximating logistic loss by any data structure.
Our work advances understanding of data structures that approximate logistic loss to reduce its space and time complexity. Our results provide guidance on how existing coreset constructions may be improved upon as well as their fundamental limitations.

---

1.1 Our contributions
We briefly summarize our contributions this work; see Section 1.3 for notation.
We prove that any data structure that approximates logistic loss up to e-relative error must dataset with constant ji-omplexity (Theorem !
use (+) space in the worst
We show that any coreset that provides e-relative enror approximation to logistic loss requires storing (2 rows of the original data matrix X (Corollary 2). Thereby, prove that analyses of existing coreset constructions are optimal up to logarithmic factors in the regime where My (X) (1))
We prove that any data structure that approximates logistic loss to relative error must take lddd My (X)) space, thereby showing that the dependency the μ-complexity measure is not an artifact using mergeable coresets which the prior work 17 had relied on (Theorem
We provide experiments that demonstrate how prior methods that only approximate My (X) can be substantially inaccurate, despite being more complicated to implement than our method (see Section 4).
Finally, we prove that low rank approximations can provide a simple but weak additive error approximation logistic loss and these guarantees tight in the worst case (See Appendix
D
1.2
Related Work
Prior work has explored the space complexity of data structures that preserve | for B e R particularly in the important case where p = 2. Lower bounds for this problem are analogous to work and motivate our inquiry. An early example of such work is [12]. which lower bounds the minimum dimension of an "oblivious subspace embedding". a particular type of data structure construction that preserves |X A more recent example this line of work is ( which provides
space complexity lower bounds for general data structures that preserves | for general E N.
Recent work on the development of coresets for logistic regression motivates our focus on this problem. This line of work was initiated by Munteanu et [10. Mai al. 77 used Lewis weight sampling to achieve an (dduy(X)² e -²)) The work of Woodruff and Yasuda
later provided an online coreset construction containing O(duy (X)2.ee points as well as a coreset construction using (dd My (X) 2) points. Finally, Munteanu and Omlor [9] recently proved an Oddjy - size coreset construction. Our work is complementary to the above works, since highlights the limits of possible compression of the logistic regression problem while maintaining approximation guarantees to the original problem.
1.3 Notation
We assume, without loss of generality, that y; = -1 for all 1... Any logistic regression problem with (X,y) defined above can be transformed to this standard form by multiplying both X and by the matrix - Dy. Here Dy Raxx is diagonal matrix with i-th entry set as y;. The logistic loss of the original problem is equal to that of the transformed problem for all 3 E Rd Let M, denote the i-th row of a matrix M. We denote as X the matrix formed by stacking x; as rows. We will use Ó()) and f2(-) to suppress logarithmic factors of d, n, 1/c, and (X). Finally, let [n] = 21, n.)
2
Space complexity lower bounds
In this section, we provide space complexity lower bounds for data structure Σ(.) that satisfies the relative error guarantee in eqn. 2 We use the notations as specified in Section Additionally, we require throughout this section that the entries of X can be specified in Ollog nd) bits.
Our first main result general lower bound on the space complexity of any data structure which approximates logistic loss to e-relative error for every parameter vector 3 R2d on a data set whose
3

---

complexity measure (X) is bounded by a constant. As corollary to this result, we show that existing coreset constructions are optimal up to lower order terms in the regime where (X( O(1). Our second main result shows that any data structure providing a éo-constant factor approximation to the logistic loss requires ( (X)) space, where co > O is constant. Both of these results proceed by reduction the INDEX problem 6 (see Section A.2p. where we use the fact that an approximation to the logistic loss can approximate ReLU loss under appropriate conditions.
Consider the ReLU loss:
R(3;X) Σ max
(x,3 3,03.
Our lower bound reductions hinge the fact that a relative error approximation to logistic loss can be used to simulate a relative error approximation to ReLU loss under appropriate conditions. We capture this in the following lemma. We include all proof's omitted from the main text in Appendix
Lemma 2.1. Given a data set X E R=dd and B C Rd such that inf R(; > 1, if there exists a data structure E.) that satisfies:
(13) - ((3) S (1 (1+)) for all 3 E B,
then there exists data structure taking (11) extra space such that:
(1 (3) S R(3) S (1 Rc) for all B E B.
2.1 Lower bounds for the My (X) (1) regime
We lower bound the space complexity of any data structure that approximates logistic loss to e-relative error. Recall that the rumning time of the computation compressing the data to small number of bits and evaluating ((3) for given query 3 is unbounded in this model. Hence, Theorem provides strong lower bound on the space needed for any compression of the data that can be used to compute c-relative error approximation to the logistic loss, including, but not limited to, coresets.
At a high level, our proof operates by showing that relative error approximation to logistic loss can be used to obtain relative error approximation to ReLu regression, which in turn can be used to construct a relative error f1- --suubspace embedding. Previously, Li et al. [6] lower bounded the worst case space complexity of any data structure that maintains an & -sbsspcce embedding by reducing the problem to the well-known INDEX problem in communication complexity. Notably, the construction of X has complexity measure bounded by a constant, i.c., My (X) O(1).
Lemma 2.2. There exists matrix X Raxd such that Hy (X) < 4 and any data structure that, with least 2/3 probability, approximates R(3; ;3; X) up e-relative error requires (1 space, provided that d = Mlog 1/e), n = (2(dd22), and 0 < é S 6o for some small constant Eo-
Furthermore, R(3 > 3||B|| for all 3 E Rd. Using Lemma 2.1 we can extend this lower bound on the space complexity to approximate ReLU loss logistic loss.
Theorem 1. Any data structure E() that, with at least 2/3 probability, is an c-relative error approximation to logistic loss for some input (X,y), requires ś2 ($) space in the worst case, assuming that S2oogg 1/c), n á (dc and 0 < c CS co for some sufficiently small constant 69-
Proof. By Lemma 2.2 there exists a matrix such that any data structure that approximates the ReLU loss up to e-relative error requires the stated space complexity. Let
B ( Rdd
|| =}
Then, by Lemma 2.2 inf ses R(3 X) 3. Therefore, by Lemma 2.1 any (1 +e) factor approxima-
tion to the logistic Toss for the matrix provides a (1 + 3c)-factor approximation to R(3; X) for E B. Since R(3) || (1))) we can extend this guarantee to all 3 E IRd, By Lemma 2.2 any data structure that provides such guarantee requires the stated space complexity, and, finally. C() requires the stated complexity.

---

From the above theorem, we can derive lower bound on the number of rows needed by coreset that achieves an e-relative error approximation the logistic loss (see eqn. 3 for specification of coreset).
Corollary 2. Any coreset construction that, with at least 2/3 probability, satisfies the relative error guarantee in eqn. must store ( ( rows of some input matrix X, where My (X) (1).
Using the previous theorem, there exists matrix X E x=*xOllog such that, assuming that = ( 2) and is sufficiently small, any data structure that approximates the logistic loss up to relative error on X must use (2(1/²) bits in the worst case. (Recall that 92(-) suppresses log factors.)
Proof.
If the data structure stores entire rows of X while storing a total of ((+)) bits, then it must store at least
2
log
Tows of X in total.
Recall that the proof of Theorem proceeds by showing that relative error approximation to the logistic loss can be used to solve the INDEX problem. we have d independent instances of the matrix X. i... (()) (22)... ...g....,,, (d). then may create the matrix
X
X (2)
0
(())
Note that any relative eтrоr approximation to the logistic loss on Y would allow relative error approximation to the logistic loss each of the individual X()) i == 1... d matrices, thus allowing one solve d instances of the INDEX problem simultaneously. This implies that we can query any bit in each of the d index problems which solves an INDEX problem of size f (d/2).
If the data structure is restricted
entire of ((). then recall that must store (11122)
rows of X(a)- Therefore, we conclude that any coreset that achieves a relative error approximation to the logistic loss on Y with at least 2/3 probability must store ((d/e²) rows of Y.
rows of X yields an e-relative coreset for logistic loss with high probability. Hence, Corollary [ implies that the coreset construction of Mai et al. [7] is of optimal size in the regime where My (X) O(1). However, Theorem onll guarantees that coresets are optimal up to a factor terms of bit complexity. An interesting future direction would be closing this gap by either proving that coresets have optimal bit complexity showing approaches, like matrix sparsification, could achieve even greater space savings.
The work of Munteanu and Omlor
9 showed that sampling ò d (X) 2²
I
2.2 An (X)yy() lower bound
In this section, we provide space complexity lower bound for data structure achieving constant eo-relative error approximation to logistic loss on an input X with variable Jy (X). We again assume y; -1 for all E [ni without loss of generality.
The proof depends on the existence of matrix M 1]_1, n that has nearly orthogonal rows. From M, we can construct the matrix such that My (X) = O(n) and 2-factor approximation to ReLU loss on X can solve the size INDEX problem. By Lemma 2.1 and the lower space complexity bound for solving the INDEX problem, we prove the described lower bound for approximating logistic loss.
We begin by proving the existence of the matrix M. Recall that for any matrix M, we use M, to denote the i-th row of M.
5

---

Lemma 2.3. Let = 2"hh for E N. There exists matrix M E {-1, 1]axk such that h = log" and (M, M2)1 S 4log" n. for all i + j.
We now use the previous lemma construct a matrix X such that a 2-factor approximation ReLU loss on X requires (t(d Py (X)) space.
Lemma 2.4. Let n = 2" for n E N and assume that log (n/2) > 16 log" n. Then, there exists a matrix X E Ra*k such that k = Olog" n) and Hy (X) = (n)) such that any data structure R(-) that, with at least 2/3 probability, satisfies (for a fixed / E R
R(3) S R(3) S 2R(33
and requires at least (2()) bits of space.
Proof. Our proof will proceed by reduction to the INDEX problem. Let yi E {0, 1} for all i 1... ./2) represent an arbitrary sequence of n/2 bits. We will show how to encode the state of the n bits in a relative error approximation ReLU loss on some data set X.
First, let us start with the matrix M E {[1, (_1,1)"/2xx specified in Lemma 2.3 where k'' log'(n/2 (n/2). Let M R=/2xk' such that M,. M,, if y/ = 1 and M.. 1/2 M,, otherwise. words, we multiply the i-th row of M by one if = 1 and 1/2 if y; = 0. Next, let us construct the matrix X E 11
M 1
X
(5)
-u M
-p-
where y > 0 will be specified later.
Suppose we want to query y/. Let B = [M; -4 -loo n|[T. We will show that M,3 < u.d 11-88og 8log n for all j A i by considering three cases:
Case 1 (j S n/2; j i): In this case, M, 3 = (M, M,) - 4log n. By Lemma 2.3 (M,, M,) S
(M, M2) < (n/2). hence we can conclude this case.
Case 2 (j > n//; + 21): Here, x3
M,, M,) + 44 n. Since (M, M, <
(M,, M, < 4 log 2 x < μ 8 log n, so we conclude the case.
Case 3 (j 21): In this case, 3, -M,M, M.) log Since -H(M, M.) is negative, we conclude the case.
The above cases show that X < μ 8log" n when j # i. Therefore,
R(B) S μ. 8 llgg n + ReLU(X,3) and R(3) 2 ReLU(X,3).
We next show that the bit yı will have large effect on R(3). If y: 0, then, 1 4
log (n/2), 3 (M, M,) 1 M, 4 log" 2
since M, E glog (n/2), On the other hand, if y = 1, then,
3
X 3
JM, 12 log = log (og((nn2) (n/2) - 4 log" > log 4 (n/2),,
4
where used our assumption that log (n/2) 16 log" n. Therefore, if y 0, R(3) - log -".x we find that R(3) < 2 log' (n/2). On the other hand, if y; 1, log'(n/2)
8u log" n. By setting μ then R(B)= > 3 log" n/2. Therefore, a 2-factor approximation to R(3) is able decide if yı equals zero or one. By reduction to the INDEX problem, this implies that any 2-factor approximation to R(3) must take at least (()) space (see Theorem 6).
log2n
Now we must just prove that My (X) = (n). We will use the following inequality 13 For any two length sequences of positive numbers, a,, r 1... and b,,
Σ Or < max
Gr 2r=1 by I... by

---

where the maximum is taken over an arbitrary fixed ordering of the sequences. Let us define these two sequences as follows for a fixed 3 Rd For 1. n/2, if X,8 0, let a; X,8 and by -1 2. If x3 < 0, let a; X2, and by = -1.X;; We can disregard the case where X; 8 0, since this will not affect the sums of the sequences. Given such sequences, we get:
((x3)+Il E, ar (X (1 E, b,
ar
S max
br S -
The last inequality follows since X2,3 -u X,8 for i 1/2. Hence, conclude that My (X) = μ (n).
The above theorem proves that constant factor approximation to R(-) requires Di (X)) space. We now extend this result logistic loss.
Theorem 3. Let
no (for some constant no N) be a positive integer. There exists global constant co O and matrix X E B such that any data structure L(+) that, with least 2/3 probability, satisfies (for fixed B E R24;
(1- X) S [(3:X) S (1 co)
and requires at least ái(d My (X)) bits of space.
Proof. The space complexity lower bound holds even if 2(-) approximates R(-) only on the values of 3 used to query the data structure in the proof of Lemma 2.4 Define this set as
B (M, -lgg n)" E R
n/2),
where M is used to construct X in eqn.
Since R(3) 2 X,3, get
R(8)= 2 M 2 4lgg n 2 log (m/2) 4 log n.
4
Therefore, R(B) 2 1 for all 2 no, where no is some constant in N. By Lemma 2.1
the space
complexity of a data structure that achieves
(1 (1-e ()() s ((B) S (1 (1+
for fixed 8 E B must be at least the space complexity of data structure achieving
R(3) < R(B) < (1+ 3c)
(1 (1-3e) R(3)
for 3 E B. We can now solve for e by setting (1+3+)/(1 (3)) 2. Therefore, from Lemma 2.4 conclude that there exists a constant eo > O such that any data structure providing an eo-relative approximation to the logistic loss requires at least (2(n) = (x())(X)) space.
Finally, applying the argument used in Corollary of constructing matrix Y, we achieve an ②(d My (X)) lower bound.
While prior work has show that mergeable coresets must include R(d My (X)) points attain constant factor guarantee to logistic loss [17), our lower bound result holds for general data structures and applies even for data structure providing the weaker "for-each" guarantee, where the guarantee must hold for an arbitrary but fixed / E IRd with a specified probability. The proof of the lower bound in [17] relies on constructing matrix A that encodes n bits such that the i-th bit can be recovered by adding some points to A and performing logistic regression on the new matrix. Hence, mergeable coreset that compresses A can be used solve the INDEX problem of size n. Meanwhile, our proof does not require constructing a regression problem but rather allows recovering the i-th bit by only observing an approximate value of the ReLU loss at a single fixed input vector for a fixed matrix A. In addition to an arguably simpler proof, our approach needs weaker assumptions on the data structure. Therefore, our lower bound applies in more general settings, i.e., when sparsification applied to X.
7

---

3 Computing the complexity measure My (X) in polynomial time
We present an efficient algorithm to compute the data complexity measure Byy (X) of Definition on real data sets, refuting earlier conjecture that this measure was hard to compute [10]. The importance of this measure for logistic regression has been well-documented in prior work and further understanding its behavior real-world data sets would help guide further improvements coreset construction for logistic regression.
Prior work conjectured that My (X) was hard to compute and presented polynomial time algorithm to approximate the measure to within a poly(d)-faaee (d)-factor (see Theorem 3 of Munteanu et al. (00). We refute this conjecture by showing that the complexity measure My (X) can in fact be computed efficiently via linear programming, as shown in the following theorem. The specific LP formulation
for computing vector 3 such that By (X)
[(D, llx is given in eqn. (9) in the Appendix.
IID,
Theorem 4. If the complexity measure My (X) of Definition 7 is finite, it can be computed exactly by solving a linear program with 2n variables and 4n constraints.
We conclude the section by noting that prior experimental evaluations of coreset constructions in [10,7] relied on estimates of My (X) using the method provided by Munteanu et al. [10]. We will empirically compare how prior methods of estimating the complexity measure compare our exact method in Section 4
4 Experiments
We provide empirical evidence verifying the algorithm of Section B exactly computes the classi- fication complexity measure Hy (X) of Definition We compare our results with the approximate sketching-basee calculation of Munteanu et al. [TO].
In order estimate Pyy (X) for dataset using the sketching-based approach of Munteanu al. [10]. we create several smaller sketched datasets of given full dataset of size n x d (n rows and d columns). We then use modified linear program along the lines of Munteanu al. [10]. These new datasets are created so that they have number of rows n'' = Od (d/)), for various values 8 e [0, 1], so that with probability at least 1 6, the estimated py (X) will lie between some lower bound (given by f, the optimum value of the aforementioned linear program) and an upper bound (given by t Od d)). In order to solve the modified linear programs, we make use of the -R-tool
Synthetic data: We create the synthetic dataset as follows. First, we construct the full data matrix X E axd by drawing
10, 000 samples from the d-dimensional Gaussian distribution N N00, La) with d = 100. We generate an arbitrary / E Rd with ||61|2 = 1 and generate the posterior p(y, xx) = 1/(1 + exp( x; + (O, 1))). Finally, we create the labels y; for all i 1... n by setting y; to one if (x,) 0.5 and to - otherwise.
Using the full data matrix A X, we create several sketched data matrices having a number of rows equal to n = logg(g (d/)). We choose 8 so that n' E (512, 1024, 2048, 4096, 8192). These values of n' are chosen to be powers of two so that we can employ the Fast Cauchy Transform algorithm (F [FastLlBasis s (I) for sketching. The algorithm is meant to ensure that the produced sketch identifies E well-conditioned bases for A, which is a prerequisite for using the subsequent linear program to estimate My (X) (See Section C for details).
The results presented in Figure la For various values of n', including when n' = n 10, 000, which we deem to be the original data size, we show the exact computation of My (X) on the sketched matrix using the linear program of Theorem 4 We also show the corresponding upper and lower bounds on Hy (X) of the full data set as estimated by the well-conditioned basis hunting approximation proposed by Munteanu al. (10]. For the lower bound, we use the optimum value of the modified linear program as proposed in Munteanu et al. [10] and detailed in Section C We set the upper bound by multiplying the lower bound by dooo d 6). Note that this upper bound is conservative, and the actual upper bound could be a constant factor higher, since the guarantees of Munteanu et al. [10] are only up to a constant factor. The presented results are an average over 20 runs of different sketches
httpss//ddeeoooeessooolloco////o
8

---

Euuthhll
12-
App Shatonesllaee
Skaloneztioes
8000
(4,00)
6000
Apprslatetedd..om Apprileecnaeligee
4-
4000
2-
2000
0-
1024
2048
8192
1024
4096
8192
Number of sketchod rows
Number skutched rows
Simulated data
(b) XDDCup dataset
Figure 1: Simulated data results for exact computation of (X( (Theorem using the full data (Exactfull), sketched data (ExactSketched) the approximate upper as suggested by Munteanu
and lower bounds hxpprSketcheeloowe al. [10] (see Section().. The results clearly show that the upper and lower bounds can be very loose compared to our exact calculation of the complexity measure Hy (X)
for each value of n'. Figure la shows that the exact computations sketched matrices close to the actual My (X) the full data matrix, while the upper and lower bounds as proposed by Muntcanu et al. [TO] can be fairly loose.
To test our setup on real data, we make use of the sklearn KDDcup dataset | The dataset consists of 100654 data points and over 50 features. We only use continuous features which reduces the feature size to 33. The dataset contains 3377 positive data points, while the rest are negatíve. To create various sized subsets for exact calculation, we subsample from positives and negatives so that they are about equal proportion. For larger subsamples, we retain all the positives, and subsample the rest from the negative data points. Since the calculation of μ for the full dataset is intractable as it will require to solve an optimization problem subsample 16384 data points and use its μ proxy for that of the full dataset (referred to as Exact Full. For such large subsample, the error bars are small. We compare against sketching and exact calculations for smaller subset (See Figure for the results).
Real data experiments:
over 400k constraints,
5 Future work
Our work shows that existing coresets are optimal up to lower order factors in the regime where My (X) (1). clear open direction would proving a space complexity lower bound that holds for all valid values of and My (X). Additionally, there is still a d factor gap between existing upper bounds 9 and our lower bounds (Theorems and B} the regime where constant and the complexity measure varies or the complexity measure is constant and varies respectively.
Another interesting direction would be explore whether additional techniques can further reduce the space complexity in approximating logistic loss compared to coresets alone. While Theorem shows that the size of coreset constructions are essentially optimal, does not preclude reducing the space by a d factor by using other methods. In particular, the construction of X used in the proof of Theorem is sparse, and existing matrix sparsification methods would save this d factor here.
We also note that our first lower bound (Theorem I only applies to data structures providing the the "for-all" guarantee on the logistic loss, i.e., with given probability. the error guarantee in eqn. ( holds for all / E Rdd It would be interesting to know it could strengthened to apply in the "for-each" setting as Theorem does, where IRd is arbitrary but fixed.
Finally, it would be useful gain a better understanding of the complexity measure Myy (X) real data through more comprehensive experiments using method provided in Theorem In particular, subsampling points data set may create bias when computing My (X).
2 kakkearnncom datasets. fetch hecch_ddccup9991 provides API access this dataset.

---

Acknowledgments
We thank the anonymous reviewers for useful feedback on improving the presentation of this work. Petros Drineas and Gregory Dexter were partially supported by NSF AF 1814041, NSF FRG 1760353, and
Rajiv Khanna was supported by the Central Indiana Corporate Partnership AnalytiXIN Initiative.
References
[1] Kenneth L. Clarkson, Petros Drineas, Malik Magdon-Ismail, Michael W. Mahoney, Xiangrui Meng, and David P. Woodruff. The Fast Cauchy Transform and Faster Robust Linear Regression. Proceedings of the 24th Annual ACM- SIAM Symposium on Discrete Algorithms (SODA), 45(3):
466 0666-477,20 2013.
[2] K.L. Clarkson, P. Drineas, M. Magdon Magdon-Ismail, M.W. Mahoney, X. Meng, and D.P. Woodruff.
The fast Cauchy transform and faster robust linear regression. SIAM Journal on Computing, 45
(3), 2016.
[3] J.S. Cramer: The Origins of Logistic Regression. SSRN Electronic Journal, 2003.
[4] Wassily Hoeffding, Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13-30) 1963. ISSN 01621459, URL http
www. wtt.:/sttt.rrttaalooooo sttale/eeaesa2
[5] Kishore Kumar and Jan Schneider. Literature survey on low rank approximation of matrices.
Linear and Multilinear Algebra, 65 (5(11):2212-2244 2017.
[6] Yi Li, Ruosong Wang, and David P Woodruff. Tight bounds for the subspace sketch problem with upplications. SIAM Journal on Computing, 50(4):1287-1335 2021.
[7] Tung Mai, Cameron Musco, and Anup Rao. Coresets for classification dlasification-siiplifeeed and strength- ened. Advances in Neural Information Processing Systems, 34, 2021.
[8] Peter Bro Miltersen, Noam Nisan, Shmuel Safra, and Avi Wigderson. On data structures and asymmetric communication complexity. In Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, pages 103-111, 1995.
[9] Alexander Munteanu and Simon Omlor. Optimal bounds for lp sensitivity sampling via lz augmentation. arXiv preprint arXiv:2406.00322 2024.
[10] Alexander Munteanu, Chris Schwicgelshohn, Christian Sohler, and David Woodruff. On coresets for logistic regression. Advances Neural Information Processing Systems, 31, 2018.
[11] Alexander Munteanu, Simon Omlor, and David Woodruff. Oblivious sketching for logistic regression. In Proceedings of the 38th International Conference on Machine Learning, pages 7861-7871, 2021.
[12] Jelani Nelson and Huy L Nguyên. Lower bounds for oblivious subspace embeddings. In International Colloquium on Automata, Languages, and Programming, pages 883-894. Springer, 2014.
[13] Daniel A. Spielman. Spectral graph theory: Dan's 's favorite inequality, September 2018. URL /ttp/////61eeect0003330 .pdf
https: / //www. cs ya yall......... wwtpe/ew.//eeeeeeeeeeeee
[14] Pierre-François Verhulst. Notice sur loi que population poursuit dans son accroissement. Correspondance Mathématique et Physique, 10:1 10:113-121, 1838.
[15] Pierre- Frane-Franççis Verhulst. Recherches mathématiques sur la loi d'aceroissement de la population. Nouveaux Mémoires de l'Académie Royale des Sciences et Bellex-Lettres de Bruxelles, 18: 14-54, 1845.
[16] David P. Woodruff. Sketching as a Tool for Numerical Linear Algebra. Foundations and Trends in Theoretical Computer Science, 10(1-2):1-157, 2014.
[17] David P Woodruff and Taisuke Yasuda. Online lewis weight sampling. In Proceedings of the 2023 Annual SMAM Symposium on Discrete Algorithms (SODA), pages 4622-4666. SIAM. 2023.
10

---

A Preliminaries
In this section, we list some useful results from prior work.
A.1 Hoeffding's inequality
We use the following formulation of Hoeffding's 's inequality. Theorem 5 (Theorem 2 in [.) Let X1,..., Xn be independent random variables with m, S X, S
M, 1 S is n. Then, for any t > 0,
11 IP
-212
Σ
X; E(x+) 21) exxp
E
(M; - mm.)
A.2 INDEX problem
Both Theorem I and Theorem 3 rely reduction the randomized INDEX problem. We define the INDEX problem as data structure as done in (6]
Definition 2. (INDEX problem) The INDEX data structure stores an input string y E {0, 1 and supports a query function, which receives imput [n)] and oulputs y: {0, 1} which is the i-th bit of the underlying string.
The following theorem provides a space complexity lower bound for the INDEX problem.
Theorem (see (8)) In the INDEX problem, suppose that the underlying string y is drawn uniformly from {0, 1 and the input of the query function is drawn uniformly from [n). Any (randomized) data structure for INDEX that succeeds with probability at least 2/3 requires (2 bits of space, where the randomness taken over both the randomness in the data structure and the randomness of s and
B Proofs
Proof for Lemma 2.1
Proof. Let Rmin = inføeRe R(3). We now prove that data structure, ž(-), which approximates logistic loss to relative error can be used to construct an approximation to the ReLu loss, R(--), by R(3) 1 L(t 33) for large enough constant
0. To show this, start by bounding the approximation error of the logistic loss for single point. First, we derive the following incquality when > 0:
log(1 + t r (Iog(e") + log
1 (1+e* etee)
))
log (1+ grr
ert
t ert
Therefore, if xf > 0, then | log(1 [ +
x B1
Next, we consider the case where x
r S 0, in which case ReLu(r) = 0. It directly follows that < log(1 + + < dfir
T Therefore,
1 tl 7
log(1 + e*T) max r),
We use these inequalities to bound the difference in the transformed logistic loss and ReLu loss as follows:
t C(t
1 R(3) -(())
log(1 + xxx{,) max (0. 9)
log(1 + clx{00 - f n
(6)

---

Therefore, if we set t" Rmina (8) then
_-2 5- B) I (m) S CR(3),
for all B E B. We can then show that ((-) can be used to approximate R(-)) by applying the triangle inequality, the error guarantee of (-) and eqn. 7 For all / E B:
1 1 3)
- -)))
R(3)
1 tz (1" 8) 1
1
L(" B) + 10 [L 3) R((3 -)))
S c
-(- +))
L _(" -91) + ER(3)
Se R((3) + RR3) - 1
Se R(B) + R(3) + R(3) S Re
Note that we can set Rmin to one and achieve the same error guarantee, since inf R(3) > 1. Therefore, storing t" takes Olog " space.
Proof for Lemma 2.2
Proof. We will first lower bound the space needed by any data structure which approximates ReLu
loss to e-relative error. Later, we will show that this implies a lower bound on the space complexity of any data structure (()) for approximating logistic loss. Let R(-)) approximate R(-)) such that R(3) S R(3) s (1 + (3) for all [ E Rd. We can rewrite R(3)) as follows:
R(3) Σ max (0,
Σ
x/2
1/2
|x 3
1
1
1
1 2
X8611-
We next use the fact that R(3) S |X ||| to get
(( 1 1
X,8| - R((3) cR((B
1 , X33 1x3
1
|X3||= - RR(3)] S c|x,
We can store 1 1"X X exactly in (dd) space as a length d vector. We define new data structure H(--)
such that H(3) (R( 12x,3, and, using the above inequality, H(B) satisfies:
X - H(BB) < X:
for all 3 E Rd. Therefore, H((3) is an c-relative approximation to |X after adjusting for constants
and solves the fj-subspace sketch problem (see Definition 1.1 in (). By Corollary 3.13 in [6], the data structure H(()) requires ② { bits of space if d ?(log 1/c) and á (dc 2). Therefore, we conclude that any data structure which approximates R(B) to e-relative error for all 8 e Rd with least 2/3 probability must use á ( bits in the worst case.
The proof in (6) that leads to Corollary 3.13 proceeds by constructing a matrix A (X in our notation) and showing that e-relative error approximations to |A require the stated space complexity. We next show that, Py (A) < 4. The construction of A is described directly above Lemma 3.10. This matrix A is first set to contain all 2* unique & length vectors in 1 for some value of k. Each row of A is then weiighhte::: specifically, the i-th row of A is re-whithtted by some E [2Kk kk).
For any vector E Rd, (AA,8) || < 4 () lla by the following argument. For an arbitrary i [m], let A, = yi v where { [ R. Then there exists a unique E [n] such that A, = -1 y v, and so A, < 0. Furthermore, since Mj > 2 and < 8vk, A
[ < 4. By applying this
argument to each row of where A > O, we conclude that (| S 4. (1(A,8))l)) and hence My (X)= < 4.
12

---

Finally, we show that R X) is lower bounded in this construction. Given any vector 3 E R" there exists a row X such that X; B 2 for j E {1...d] d.. that is, the j-th entry of X, has the same sign as 8 in all non-zero entries of B. Therefore, X = || Since yi 2 3v k. we conclude that R(3 X) 3|
Proof of Lemma 2.3
Proof. Let A E [-1,1]nxk be random matrix where each entry is uniformly sampled from {-1,1} in independent identical trials. Let [Rr hre[s] be independent Rademacher random variables. Then,
k Σ
2 2k
P(K Aj)
R 21
S 2 exp
where the last step follows from applying Hoeffding's inequality. There fewer than n² tuples (i,j) E ( x (1...d) d} such that i Therefore, by an application of the union bound,
t2
P(KA,, A, 2 for all + S n² exp
2k
Setting f 4 log n, see that the right side of the inequality is less than one whenever 1. Therefore, there must exist matrix M satisfying the specified criteria.
Proof of Theorem
Proof. We now derive linear programming formulation to compute the complexity measure in Definition Note that we flip the numerator and denominator from Definition | without loss of generality. Let 3* E Rd 5
(DyxX.8) ||
3 argmax
(DyxX,)+
||
My
I[Dy
The second line above uses the fact that the definition of My (X) does not depend on the scaling of If O' is an arbitrary positive constant, then there exists constant 0 such that:
8 argmax
XB) ||a such that 1,)+ S
BER
argmax X such that [(D) BER
Again, (DyXx*" I1 is invariant rescaling of f may assume that is equal to one without loss of generality. We now reformulate the last constraint as follows:
(DD
max [D 133) 0}
D X "D,
2
i=1
-1
x3
D DyX3111
2
Therefore, the above formulation is equivalent
such that 1 1 1' Dy D,X3ll
8 argmax
DDy
BER
2
argmin 1 D3 X33 such that |D,xX8111 S
BeRd
For notational simplicity, assume 3* is unique, but this is necessary.
13

---

Next, we replace Dy with single vector E R" and linear constraint to guarantee that E Range(Dy Let P Rax= be the orthogonal projection to (ange Then,
z' = argmin 1'
(8)
zER
such that |z][1 S C and (I (I-Pn)z=00
Next, we solve this formulation by constructing a linear program such that [2+, 2_] E R corre- sponds the absolute value of the positive and negative elements of namely
z argmin (2+ - z_)
(9)
SER* such that 1 (2+ + z_) and (I- -z_)= and 24 2_ 2
Observe that this a linear program with 2n variables and 4n constraints. After solving this program for 7 and z_, can compute z' = z From this, compute 3 by solving the linear system z = X,8", which is guaranteed to have a solution by the linear constraint (I- PRIZ =
After solving for f*," we can compute
I(D,xX.*) (X)
I(DyX*+++
thus completing the proof.
C Modified linear program
For completeness, we reproduce the linear program of Munteanu et al. 10 [Setiion A] to estimate the complexity measure My (X):
min
Σ b;
1=1
s.t. Vi [n] (UB), b
Vi [d] 3, = C,
4 4+421
1=1
Vi [n] a, b,
Vi [d] G, dg 2 0.
Here, U is & d--well-conditioned basis 2 of the matrix D,X. Because the well-conditioned property, a can be estimated to be within the bounds:
My (X) poly
where min [I and recall that dl is the number of columns of X. Munteanu et al. 10 designed the above linear program to solve for However, note that trivially the LP as it is written could be trivially solved with Vic, = d; = 3, = a; = b; = 0, which unfortunately gives = 0 always trivially. To get around this problem. modify the above program follows:
14

---

min Σ bi
s.t. Vi E [n] (U3);
bi
6
3r
V [d] :1.: d, + B
Vi [d] :6 $ Mv;
E [d] : S M(1 Us)
Σ h4 21
Vi [n] a, b; 2
Vi [d] C, d, h4 2
vi [d] U 10
Here, M a sufficiently large value as is often used for Big-M constraints in linear programs. The variable h simulates the [3,], and is set according to the binary variable v, which decides which one of c; or d, is O. Further, note that Σ, h2 2 is equivalent to Σ, h; = here since scaling down the norm of can only bring the optimization cost down. To solve the optimization problem, Google OR-tools and the wrapper pywraplp with the solver SAT which can handle integer programs since the above program is longer pure linear program because of the binary variables w.
the
D Low rank approximation to logistic loss
Here, provide very simple data structure that provides additive error approximation the logistic loss. While the method is straightforward, we are unaware of this approximation being specified in prior work, and may be useful in the natural setting where the input matrix X has low stable rank.
We show that any low-rank approximation X of the data matrix X can be used to approximate the logistic loss function C(3) up to a /nlX X - X X |||11 additive error. The factor |[ - X | the spectral norm (or two-norm) eиrоr of the low-rank approximation and we also prove that this bound tight the worst case. Low rank approximations are commonly used to reduce the time and space complexity of numerical algorithms, especially in settings where the data matrix X is numerically low-rank or has a decaying spectrum of singular values.
Using low-rank approximations of X to estimate the logistic loss is appealing due to the extensive body work on fast constructions low-rank approximations via sketching, sampling, and direct methods (5). We show that a spectral approximation provides additive error guarantee for the logistic loss and that this guarantee tight on worst-case inputs.
Theorem 7. X, guxd, then all Rd.
[(3:X) - ((3,8) Vn X
X
|2
Linear and Nonlinear Optimization (2nd ed.). Society for Industrial Mathematics
'See
15

---

Proof. To simplify the notation, let s X, and d = (X X)5. We can then write the difference in the log loss as:
[C X) [(3,X)
log 1 ++ex10) - 11911
Σ log
[ (1+2210) + 1
1 c 1+ esttd:
log
n
1 e 6
log
+ e0
log
1 e ld c5
e-1led
1 ++e* ex
log
e d.
+ ebi
|d:] [||=]|]]]]-
Therefore, we can conclude that [(3; - (33 S [|dd|| S volld|12 S Vn X ||2
We note that Theorem holds for any matrix X Raad that approximates X with respect to the spectral norm, and does not necessitate that X has low-rank. We now provide matching lower-bound for the logistic loss function in the same setting.
Theorem 8. For every d, N where d 2 n. there exists a data matrix X E Ruxd, label vector E 1-11,1)" parameter vector B E Rdd and spectral approximation X E Iga such that:
[C X) L(B: X) 2 (1 - 8) - -
for every > 0. Hence, the guarantee of Theorem is tight in the worst case.
Proof. To prove the theorems statement, first consider the case of square matrices (d n). In particular, first consider the case where d n 1, where [x]] and X [x + s], in which case
X X 2 s. Then,
lim [(11); + 8)) [[[1](([]]))) [x]) +00
lim log(1 + c log + )=)== =8 x+
Which shows that for 3 [4] and with large enough magnitude L(3; X) [(3; = (1 8){{X X/12. Next, let X In, X + s) I, and 1,, Then for all E in], x² [3=1 and xf B x + s. Therefore,
lim L(3:X) L)3;X)= = lim x-500
[log(1 + c= log(1 + tc*)]
1=1
Since |X X1|2 = ||s 1 = s. ||81|2 = vn. lim L(3; x) L(B: X) =sn
Vn X X||2|18112
Hence, we conclude the statement of the theorem for the case where d = n. To conclude the case for 2 n, note that V - || does not change we extend X and with columns of zeroes and extend with entries of zero until X, X E axd and Rdd. This procedure also does not change the loss at B, hence we conclude the statement of the theorem.
16

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
We state our contributions in Section 1.1 and link to the results in the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We mention that we do not focus on lower order (logarithmic) factors in our theoretical analysis. Additionally, we point out more comprehensive experiments in computing (X) for real datasets as an open direction.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn asymptotic approximations only holding locally). ). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
17

---

Answer: [Yes]
Justification: We have rigorously derived all theoretical results and provided clear references to the results we depend in prior work.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proof' in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Code and instructions to reproduce our results are provided in the supplemen- tary material.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
18

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: Code and instructions reproduce our results are provided in the supplemen- tary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please the NeurIPS code and data submission guidelines (https://nips. cc/
public/ /ttd:/guuudeee/eeeuuumee ss son ollcc) for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See NeurlPS code and data submission guidelines (https
/ //nips. httccc/pbbb. http:/pllllgguui.oeo / SCops//oeeeSemmmeen ss onPol icyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We do not provide learning algorithm, so there are no data splits or training. Code and instructions to reproduce our results are provided in the supplementary material.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We provide eтror bars in are figures that are sufficient to show statistical significance of the observed behavior.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
19

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [No]
Justification: Our focus is primarily theoretical, and experiments do not require signifi- cant compute resources.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics httpl//wwwe...eee......oppooooee
Answer: [Yes]
Justification:
We follow all of the relevant ethical guidelines.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: While expect our work benefit the development of methods for logistic regression, our work is far upstream from any applications, and hence not possible to productively consider broader impact.
Guidelines:
20

---

The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negatíve societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g.. gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our work is not related any of these mentioned areas.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
We give proper attribution for the code we use from prior work.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
21

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paapersw haperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
We provide code with documentation in the supplementary material.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
22

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
23


Reviews:
[{"review_id": "atIlrgfgQa", "reviewer": "Reviewer_8cM9", "summary": "This paper establishes lower bounds on the space complexity for data structures approximating logistic loss with relative error, showing that existing methods are optimal up to lower order factors. It proves that any coreset providing an $(\\varepsilon)$-relative error approximation to logistic loss requires storing $(\\Omega(\\frac{d}{\\epsilon^2}))$ rows of the original data matrix. The paper also demonstrates that the dependency on the complexity measure $(\\mu_y(X))$ is fundamental to the space complexity of approximating logistic loss. Further an efficient linear programming formulation is provided to compute $(\\mu_y(X))$, refuting a prior conjecture about its computational difficulty.", "questions": "-", "limitations": "Yes. Authors mention that more comprehensive experiments in computing $\\mu_y(X)$ for real datasets as an open direction.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The paper introduces new space complexity lower bounds for data structures approximating logistic loss, which is a novel contribution in logistic regression. It also refutes a prior conjecture about the complexity measure \\mu_y(X) and provides an efficient linear programming formulation.\n\n- The paper is built upon existing work in the field. It provides rigorous theoretical proofs and empirical comparisons to prior methods, demonstrating the validity and effectiveness of the proposed approaches.\n\n- The paper is clearly written, with a structured presentation of the problem, contributions, and results. Definitions and notations are provided to aid understanding, and the inclusion of related work helps contextualize the contributions.", "weaknesses": "- The paper should clearly articulate how its contributions differ from existing works, especially those by Munteanu et al. and Mai et al. Highlighting specific improvements or unique approaches.\n\n- The experiments could have been conducted on more diverse datasets, including real-world applications beyond synthetic and KDDCup datasets. \n\n- The paper introduces a new method to compute the complexity measure µy(X). Including more detailed explanations would be useful.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The paper should clearly articulate how its contributions differ from existing works, especially those by Munteanu et al. and Mai et al. Highlighting specific improvements or unique approaches.\n\nOur work is complementary to the works of Munteanu et al. and Mai et al. Both of those papers primarily consider providing coreset constructions for logistic loss with _upper_ bounds on the number of sampled points for relative error guarantees. On the other hand, the primary contributions of our work are providing _space complexity lower bounds_ for approximating logistic loss as well as an exact and tractable method (as opposed to being  NP Hard to evaluate, which was previously conjectured) to compute the complexity parameter $\\mu$ that is present in both the upper bound of prior work and our lower bounds. \n\n\nThe reviewer is correct that Munteanu et al. does have an $\\Omega(n)$ space complexity lower bound when $\\mu$ is unbounded, but that lower bound is superseded by the more recent results of Woodruff and Yasuda. The latter paper provides a lower bound for coreset construction. We compare our work to their result and explain how our result is more general in the contributions section, as well as in lines 263-266. In the final version, we will also add additional explanation after lines 263-266 on how the reduction used in the lower bound of Woodruff and Yasuda differs from ours.\n\n> The experiments could have been conducted on more diverse datasets, including real-world applications beyond synthetic and KDDCup datasets.\n\nWe agree that further experiments on understanding the behavior of $\\mu$ in real datasets would be an interesting problem, and we note this direction in our future works section. However, our work is focused on theoretically understanding the space complexity of approximating logistic loss. A thorough experimental exploration of the behavior of $\\mu$ in real datasets would be an implementation-focused question and is not the main focus of this paper.\n\n> The paper introduces a new method to compute the complexity measure µy(X). Including more detailed explanations would be useful.\n\nWe will add a section in the appendix of the final version with more explicit details on computing $\\mu$ using the LP introduced in the proof of Theorem 4.", "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": "WXlXTWpsFo", "reviewer": "Reviewer_hULF", "summary": "The paper explores the space complexity lower bounds for data structures that approximate logistic loss with $\\epsilon$-relative error in logistic regression problems. The authors provide an $\\Omega(d/\\epsilon^2)$ space complexity lower bound for datasets with constant $\\mu$-complexity, demonstrating that existing coreset constructions are optimal within this regime up to lower order factors. They also establish a general $\\Omega(d \\cdot \\mu_y(X))$ space lower bound for constant $\\epsilon$, highlighting that the dependency on $\\mu_y(X)$ is intrinsic and not an artifact of mergeable coresets. Additionally, the paper refutes a prior conjecture regarding the difficulty of computing $\\mu_y(X)$ by presenting an efficient linear programming formulation. Empirical comparisons show that the proposed algorithm for computing $\\mu_y(X)$ is more accurate than prior approximate methods. These contributions enhance the understanding of the fundamental limits and efficiencies in approximating logistic loss, providing insights that can guide future improvements in coreset constructions and related data structures.", "questions": "A minor issue, the font of the paper seems different from other papers.", "limitations": "Yes.", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper provides an $\\tilde{\\Omega}(d/\\epsilon^2)$ space complexity lower bound when $\\mu_y(x) = O(1)$ and a general $\\tilde{\\Omega}(d\\cdot \\mu_y(x))$ assuming $\\epsilon$ is constant. Also, the paper refute a prior conjecture by providing a linear programming to compute $\\mu_y(x)$.", "weaknesses": "N/A. The reviewer is not familiar with space complexity area.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> A minor issue, the font of the paper seems different from other papers.\n\nThanks for pointing this out. We have fixed the issue.", "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": "c0HFWzIMcX", "reviewer": "Reviewer_9S9F", "summary": "The paper gives mainly lower bounds against any data compression for logistic regression parameterized by a complexity measure $\\mu$. They prove lower bounds $\\Omega(d/\\epsilon^2)$ as well as $\\Omega(d\\mu)$. Both are derived by reduction from the indexing indexing problem and a direct sum argument to extend the bounds by the d factor.\n\nThere are also new algorithms for computing $\\mu$ by a linear program, and additive error bounds for low rank approximation for logistic regression. I found the latter more interesting than the former but it is completely hidden in the appendix.", "questions": "* any chance the two bounds can be combined to a $\\Omega(d\\mu/\\epsilon^2)$ bound?\n* if not then do you think $O(d(\\mu+1/\\epsilon^2))$ might be possible?\n* any chance the $\\Omega(\\mu)$ bound can be generalized to hold for arbitrary (or some range of) $\\mu$, to give for instance $\\Omega(\\sqrt{n})$ when $\\mu = \\sqrt{n}$?\n* to apply the direct sum argument over the $d$ indexing problems on the block diagonal matrix, is it not needed to apply some sort of union bound over the failure probability of each of the d indexing instances? If yes, is this possible in your reduction while losing only a $\\log(d)$ factor or will the resulting bound only hold against 1/d failure probability?", "limitations": "see above", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* nearly tight lower bounds against data compression for logistic regression\n* hold against arbitrary data reduction techniques, not only coresets\n* well written paper", "weaknesses": "* state of the art discussion on upper bounds is slightly outdated: updating to the $O(d\\mu/\\epsilon^2)$ upper bounds https://arxiv.org/abs/2406.00328 will only strengten the contributions.\n* the $\\Omega(\\mu)$ bound is only from a $\\Omega(n)$ bound for some case where $\\mu \\approx n$", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> state of the art discussion on upper bounds is slightly outdated: updating to the $O(d\\mu/\\epsilon^2)$ upper bounds https://arxiv.org/abs/2406.00328 will only strengten the contributions.\n\nThank you for pointing out this new result. This Arxiv submission was made after NeurIPS deadline, so we were not aware of this paper. We will indeed update our paper to compare to this tighter upper bound. Indeed, this strengthens the contributions of our work and we appreciate your comment and suggestion.\n\n> the $\\Omega(n)$ bound is only from a $\\Omega(n)$ bound for some case where $\\mu \\approx n$\n\nOur proof of $\\Omega(\\mu)$ space complexity using $\\mu \\approx n$ immediately extends to all values of $\\mu \\lesssim n$  by the fact we can always pad $\\mathbf{X}$ with zeroes.\n\n\n> any chance the two bounds can be combined to a $\\Omega(d\\mu/\\epsilon^2)$ bound?\n\nWe believe that our two lower bounds will be informative for achieving an $\\Omega(d\\mu/\\epsilon^2)$ bound. However, we did not find a way to readily bridge this gap. Both lower bounds work by reduction to the $\\texttt{INDEX}$ problem, but in quite different ways. Intuitively, the difficulty is that the non-linearity of ReLU is used in the two proofs in different ways. Unfortunately, constructing a multiplicative trade-off between the two constructions is not straightforward.\n\n\n> if not then do you think $\\Omega(d(\\mu + \\frac{1}{\\epsilon^2}))$ might be possible?\n\nYes, this lower bound can be derived from our two provided lower bounds by the fact that any approximation to the logistic loss on a matrix $\\mathbf{C} = [\\mathbf{A}, \\mathbf{0}; \\mathbf{0}, \\mathbf{B}]$ must also provide an equally accurate approximation to the logistic loss of any query vector on either matrix $\\mathbf{A}$ or $\\mathbf{B}$. Hence, we obtain the lower bound you have mentioned by letting $\\mathbf{A}$ be constructed from Theorem 1 and $\\mathbf{B}$ be constructed from Theorem 3.\n\n\n> Any chance the $\\Omega(n)$ bound can be generalized to hold for arbitrary (or some range of) $\\mu$, to give for instance $\\Omega(\\sqrt{n})$ when $\\mu \\approx \\sqrt{n}$?\n\nBy using our construction and padding $\\mathbf{X}$ with zeroes as described above, the lower bound can be immediately extended to all $\\mu \\lesssim n$.\n\n\n> to apply the direct sum argument over the $d$ indexing problems on the block diagonal matrix, is it not needed to apply some sort of union bound over the failure probability of each of the $d$ indexing instances? If yes, is this possible in your reduction while losing only a $\\log(d)$ factor or will the resulting bound only hold against $1/d$ failure probability?\n\nSince we are going for a lower bound, the probabilistic nature of the guarantees actually works in our favor. A relative error approximation to the logistic loss on the diagonal block matrix $\\mathbf{Y}$ simultaneously provides the relative error guarantee to each of its blocks $\\mathbf{X}\\_{(1)}...\\mathbf{X}\\_{(d)}$. Therefore, obtaining a relative error approximation for $\\mathbf{Y}$ with probability $2/3$ requires that each $\\mathbf{X}\\_{(i)}$ is approximated with probability greater than $2/3$ ($2/3 = p^d$, where $p$ is the success probability of estimating $\\mathbf{X}\\_{(i)}$ to be precise).", "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": "oFxyQbvNKD", "reviewer": "Reviewer_iEdU", "summary": "This paper gives a d \\eps^{-2} bounds for coresets of points/labels that preserve logistical functions. Such a bound is similar to the bounds obtained in some recent upper bounds, and the paper experimentally verifies that a natural complexity measure is likely needed for constructing such coresets. The paper also gives an algorithm for estimating this complexity measure.", "questions": "Are there wider classes of functions that the approach for showing coreset lower bounds here can generalize to?", "limitations": "yes", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "Logistical functions are widely used in a multitude of learning tasks, and coresets have been studied for a variety of numerical/optimization problems.\n\nThe bounds shown are likely the right ones, and significantly demystifies the complexity measure.", "weaknesses": "The results doesn't cover the `for this solution' sparsification that's weaker than the 'for all' sparsfication, but is still sufficient in many applications. However, that version will likely require significantly different approaches.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The results doesn't cover the `for this solution' sparsification that's weaker than the 'for all' sparsfication, but is still sufficient in many applications. However, that version will likely require significantly different approaches\n\nThis is a great point, and we agree with the reviewer: it is not obvious how to prove the proposed quantification. This will probably require new approaches. In the final version, we will mention this as an open problem for future work.\n\n> Are there wider classes of functions that the approach for showing coreset lower bounds here can generalize to?\n\nYes, our bounds also apply to approximations of ReLU loss, as our proof operates by first showing that an $\\epsilon$-relative error approximation to logistic loss provides an $O(\\epsilon)$-relative error approximation to ReLU loss. It seems likely that our lower bound would apply to the class of “hinge-like loss functions” defined by Mai et al (Definition 7 in their paper).", "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:

Meta-review: This paper establishes lower bounds on the space complexity for data structures approximating logistic loss with relative error, showing that existing methods are optimal up to lower order factors.  

The reviewers acknowledge that this paper introduces new space complexity lower bounds for data structures approximating logistic loss, which is a novel contribution in logistic regression. It also refutes a prior conjecture about the complexity measure $\mu_y(X)$ and provides an efficient linear programming formulation. Additionally, the reviewers commend the paper for its clarity and quality of writing.

Overall, this paper makes novel contributions. Therefore, I recommend accepting it, with the suggestion that the authors address the new literature pointed out by Reviewer 9S9F in the final version.
Decision: Accept (poster)