The Space Complexity of Approximating Logistic Loss

Authors: gregory  dexter
petros  drineas
rajiv  khanna
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-12 22:57:36

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.

Main paper: 
 introduction: 
 Logistic regression is an indispensable tool in data analysis, dating back to at least the early 19th century. It was originally used to make predictions in social science and chemistry applications [14, 15, 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. At a high level, the (binary) logistic 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 a linear combination of one or more predictor variables.Formally, logistic regression aims to find a parameter vector β ∈ R d that minimizes the logistic loss, L(β), which is defined as follows:EQUATIONwhere X ∈ R n×d is the data matrix (n points in R d , with x T i being the rows of X) and y ∈ {-1, 1} n is the vector of labels whose entries are the y i . Due to the central importance of logistic regression, algorithms and methods to improve the efficiency of minimizing the logistic loss are always of interest [7, 10, 9] .The prior study of linear regression, a much simpler problem that admits a closed-form solution, has provided ample guidance on how we may expect to improve the efficiency of logistic regression. Let us first consider how a data structure that approximates ℓ 2 -regression loss may be leveraged to design efficient algorithms for linear regression. Let D(•) : R d → R be a data structure such that:(1 -ϵ)∥Ax -b∥ 2 ≤ D(x) ≤ (1 + ϵ)∥Ax -b∥ 2 .Then, for, say, any ϵ ∈ (0, 1 /3)x = argmin x∈R d D(x) ⇒ ∥Ax -b∥ 2 ≤ 1 + ϵ 1 -ϵ • min x∈R d ∥Ax -b∥ 2 ≤ (1 + 3ϵ) • min x∈R d ∥Ax -b∥ 2 .That is, a data structure that approximates the ℓ 2 -regression loss up to ϵ-relative error may be used to solve the original regression problem up to 3ϵ-relative error. This is particularly interesting when D(•) has lower space complexity than the original problem or can be minimized more efficiently.Practically efficient data structures satisfying these criteria for linear regression have been instantiated through matrix sketching and leverage score sampling [16] . There is extensive work exploring constructions of a matrix S ∈ R s×n , where given a data matrix A ∈ R n×d and vector of labels b ∈ R n , we may solve the lower dimensional problem x = argmin x∈R d ∥SAx -Sb∥ 2 to achieve the guarantee ∥Ax -b∥ 2 ≤ 1+ϵ 1-ϵ • min x∈R d ∥Ax -b∥ 2 for a chosen ϵ > 0. Under conditions that guarantee that s ≪ n, we can achieve significant computational time and space savings by following such an approach. An important class of matrices S ∈ R s×n that guarantee the above approximation are the so-called ℓ 2 -subspace embeddings which satisfy:(1 -ϵ)∥Ax -b∥ 2 ≤ ∥S(Ax -b)∥ 2 ≤ (1 + ϵ)∥Ax -b∥ 2 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. [10, 11] 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 to linear regression, these works present an efficient data structure L(•) such that (1 -ϵ)L(β) ≤ L(β) ≤ (1 + ϵ)L(β).(EQUATIONWe call L(•) an ϵ-relative error approximation to the logistic loss. Prior work on coreset construction for logistic regression critically depends on the data complexity measure µ y (X), which was first introduced in [10] , and is defined as follows. Definition 1. (Classification Complexity Measure [10] ) For any X ∈ R n×d and y ∈ {-1, 1} n , letµ y (X) = sup β̸ =0 ∥(D y Xβ) + ∥ 1 ∥(D y Xβ) -∥ 1 ,where D y is a diagonal matrix with y as its diagonal, and (D y Xβ) + and (D y Xβ) -denote the positive and the negative entries of D y Xβ respectively.Specifically, these methods construct a coreset by storing a subset of the rows indexed by S ⊂ {1 . . . n} such that |S| = Õ(d•µy(X) ϵ 2) and generating a set of weights {w i } i∈S such that each w i is specified by O(log nd) bits [9] . The approximate logistic loss is then computed as:EQUATIONis an ϵ-relative error approximation to L(β). We see that µ y (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.We briefly summarize our contributions in this work; see Section 1.3 for notation.• We prove that any data structure that approximates logistic loss up to ϵ-relative error must use Ω( d ϵ 2 ) space in the worst case on a dataset with constant µ-complexity (Theorem 1). • We show that any coreset that provides an ϵ-relative error approximation to logistic loss requires storing Ω( d ϵ 2 ) rows of the original data matrix X (Corollary 2). Thereby, we prove that analyses of existing coreset constructions are optimal up to logarithmic factors in the regime where µ y (X) = O(1).• We prove that any data structure that approximates logistic loss to relative error must take Ω(d • µ y (X)) space, thereby showing that the dependency on the µ-complexity measure is not an artifact of using mergeable coresets which the prior work [17] had relied on (Theorem 3). • We provide experiments that demonstrate how prior methods that only approximate µ y (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 to logistic loss and these guarantees are tight in the worst case (See Appendix D).Prior work has explored the space complexity of data structures that preserve ∥Xβ∥ p for β ∈ R d , particularly in the important case where p = 2. Lower bounds for this problem are analogous to our 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β∥ 2 . A more recent example in this line of work is [6] , which provides space complexity lower bounds for general data structures that preserves ∥Xβ∥ p for general p ∈ 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 al. [10] . Mai et al. [7] used Lewis weight sampling to achieve an Õ(dµ y (X) 2 • ϵ -2 ). The work of Woodruff and Yasuda [17] later provided an online coreset construction containing Õ(dµ y (X) 2 •ϵ -2 ) points as well as a coreset construction using Õ(d 2 µ y (X) • ϵ -2 ) points. Finally, Munteanu and Omlor [9] recently proved an Õ(dµ y (X) • ϵ -2 ) size coreset construction. Our work is complementary to the above works, since it highlights the limits of possible compression of the logistic regression problem while maintaining approximation guarantees to the original problem.We assume, without loss of generality, that y i = -1 for all i = 1 . . . n. Any logistic regression problem with (X, y) defined above can be transformed to this standard form by multiplying both X and y by the matrix -D y . Here D y ∈ R n×n is a diagonal matrix with i-th entry set as y i . The logistic loss of the original problem is equal to that of the transformed problem for all β ∈ R d . Let M i denote the i-th row of a matrix M. We denote as X the matrix formed by stacking x i as rows. We will use Õ(•) and Ω(•) to suppress logarithmic factors of d, n, 1/ϵ, and µ y (X). Finally, let[n] = {1, 2, ..., n}.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.• The answer NA means that the abstract and introduction do not include the claims made in 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 to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
space complexity lower bounds: 
 In this section, we provide space complexity lower bounds for a data structure L(•) that satisfies the relative error guarantee in eqn. 2. We use the notations as specified in Section 1. Additionally, we require throughout this section that the entries of X can be specified in O(log nd) bits.Our first main result is a general lower bound on the space complexity of any data structure which approximates logistic loss to ϵ-relative error for every parameter vector β ∈ R d on a data set whose complexity measure µ y (X) is bounded by a constant. As a corollary to this result, we show that existing coreset constructions are optimal up to lower order terms in the regime where µ y (X) = O(1).Our second main result shows that any data structure providing a ϵ 0 -constant factor approximation to the logistic loss requires Ω(µ y (X)) space, where ϵ 0 > 0 is constant. Both of these results proceed by reduction to the INDEX problem [6, 8] (see Section A.2), where we use the fact that an approximation to the logistic loss can approximate ReLU loss under appropriate conditions.Consider the ReLU loss:EQUATIONOur lower bound reductions hinge on 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 proofs omitted from the main text in Appendix B. Lemma 2.1. Given a data set X ∈ R n×d and B ⊂ R d such that inf β∈B R(β; X) > 1, if there exists a data structure L(•) that satisfies:(1 -ϵ)L(β) ≤ L(β) ≤ (1 + ϵ)L(β) for all β ∈ B,then there exists a data structure taking Õ(1) extra space such that:(1 -3ϵ)R(β) ≤ R(β) ≤ (1 + 3ϵ)R(β) for all β ∈ B.2.1 Lower bounds for the µ y (X) = Θ(1) regimeWe lower bound the space complexity of any data structure that approximates logistic loss to ϵ-relative error. Recall that the running time of the computation compressing the data to a small number of bits and evaluating L(β) for a given query β is unbounded in this model. Hence, Theorem 1 provides a strong lower bound on the space needed for any compression of the data that can be used to compute an ϵ-relative error approximation to the logistic loss, including, but not limited to, coresets.At a high level, our proof operates by showing that a relative error approximation to logistic loss can be used to obtain a relative error approximation to ReLu regression, which in turn can be used to construct a relative error ℓ 1 -subspace embedding. Previously, Li et al. [6] lower bounded the worst case space complexity of any data structure that maintains an ℓ 1 -subspace 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.e., µ y (X) = O(1). Lemma 2.2. There exists a matrix X ∈ R n×d such that µ y (X) ≤ 4 and any data structure that, with at least 2/3 probability, approximates R(β; X) up to ϵ-relative error requires Ω( d ϵ 2 ) space, provided that d = Ω(log 1/ϵ), n = Ω(d/ϵ 2 ), and 0 < ϵ ≤ ϵ 0 for some small constant ϵ 0 . Furthermore, R(β; X) > 3∥β∥ 1 for all β ∈ R d .Using Lemma 2.1, we can extend this lower bound on the space complexity to approximate ReLU loss to logistic loss. Theorem 1. Any data structure L(•) that, with at least 2/3 probability, is an ϵ-relative error approximation to logistic loss for some input (X, y), requires Ω d ϵ 2 space in the worst case, assuming that d = Ω(log 1/ϵ), n = Ω dϵ -2 , and 0 < ϵ ≤ ϵ 0 for some sufficiently small constant ϵ 0 .Proof. By Lemma 2.2, there exists a matrix X such that any data structure that approximates the ReLU loss up to ϵ-relative error requires the stated space complexity. LetB = {β ∈ R d | ∥β∥ 1 = 1}Then, by Lemma 2.2, inf β∈B R(β; X) ≥ 3. Therefore, by Lemma 2.1, any (1 + ϵ) factor approximation to the logistic loss for the matrix X provides a (1 + 3ϵ)-factor approximation to R(β; X) for β ∈ B. Since R(β) = ∥β∥ 1 • R( β /∥β∥1), we can extend this guarantee to all β ∈ R d . By Lemma 2.2, any data structure that provides such a guarantee requires the stated space complexity, and, finally, L(•) requires the stated complexity.From the above theorem, we can derive a lower bound on the number of rows needed by a coreset that achieves an ϵ-relative error approximation to the logistic loss (see eqn. 3 for specification of a coreset). Corollary 2. Any coreset construction that, with at least 2/3 probability, satisfies the relative error guarantee in eqn. 2 must store Ω( d ϵ 2 ) rows of some input matrix X, where µ y (X) = O(1).Proof. Using the previous theorem, there exists a matrix X ∈ R n×O(log n) such that, assuming that n = Ω(ϵ -2 ) and ϵ is sufficiently small, any data structure that approximates the logistic loss up to relative error on X must use Ω( 1 /ϵ 2 ) bits in the worst case. (Recall that Ω(•) suppresses log n factors.)If the data structure stores entire rows of X while storing a total of Ω( 1 ϵ 2 ) bits, then it must store at leastΩ 1 ϵ 2 • 1 log n = Ω 1 ϵ 2 rows of X in total.Recall that the proof of Theorem 1 proceeds by showing that a relative error approximation to the logistic loss can be used to solve the INDEX problem. If we have d independent instances of the matrix X, i.e., X (1) , X (2) , ...X (d) , then we may create the matrixY =       X (1) 0 . . . 0 0 X (2) . . . 0 . . . . . . . . . 0 0 0 • X (d)       .Note that any relative error approximation to the logistic loss on Y would allow relative error approximation to the logistic loss on each of the individual X (i) , i = 1 . . . d matrices, thus allowing one to 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 Ω ( d /ϵ 2 ).If the data structure is restricted to store entire rows of X (i) , then recall that we must store Ω( 1 /ϵ 2 ) rows of X (i) . 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 /ϵ 2 ) rows of Y.The work of Munteanu and Omlor [9] showed that sampling Õ d•µy(X) ϵ 2rows of X yields an ϵ-relative error coreset for logistic loss with high probability. Hence, Corollary 2 implies that the coreset construction of Mai et al. [7] is of optimal size in the regime where µ y (X) = O(1). However, Theorem 1 only guarantees that coresets are optimal up to a d factor in terms of bit complexity. An interesting future direction would be closing this gap by either proving that coresets have optimal bit complexity or showing approaches, like matrix sparsification, could achieve even greater space savings.In this section, we provide a space complexity lower bound for a data structure achieving a constant ϵ 0 -relative error approximation to logistic loss on an input X with variable µ y (X). We again assume y i = -1 for all i ∈ [n] without loss of generality.The proof depends on the existence of a matrix M ∈ {-1, 1} n×log 4 n that has nearly orthogonal rows. From M, we can construct the matrix X such that µ y (X) = O(n) and a 2-factor approximation to ReLU loss on X can solve the size n 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 i to denote the i-th row of M. Lemma 2.3. Let n = 2 p for n ∈ N. There exists a matrix M ∈ {-1, 1} n×k such that k = log 4 n and |⟨M i , M j ⟩| ≤ 4 log 2 n for all i ̸ = j.We now use the previous lemma to construct a matrix X such that a 2-factor approximation to ReLU loss on X requires Ω(d • µ y (X)) space.Lemma 2.4. Let n = 2 p for n ∈ N and assume that log 4 (n/2) > 16 log 2 n. Then, there exists a matrix X ∈ R n×k such that k = O(log 4 n) and µ y (X) = O(n) such that any data structure R(•) that, with at least 2/3 probability, satisfies (for a fixedβ ∈ R d ) R(β) ≤ R(β) ≤ 2R(β)and requires at least Ω(n) bits of space.Proof. Our proof will proceed by reduction to the INDEX problem. Let y i ∈ {0, 1} for all i = 1 . . . n /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 to ReLU loss on some data set X.M ∈ {-1, 1} n/2×k ′ specified in Lemma 2.3, where k ′ = log 4 (n/2). Let M ∈ R n/2×k ′ such that Mi * = Mi * if y i = 1 and Mi * = 1 /2 • M i * otherwise.In words, we multiply the i-th row of M by one ifEQUATIONwhere µ > 0 will be specified later.Suppose we want to query y i . Let β = [ Mi , -4 log 2 n] T . We will show that Mj β < µ • 8 log 2 n for all j ̸ = i by considering three cases:Case 1 (j ≤ n/2; j ̸ = i): In this case, Mj β = ⟨ Mi , Mj ⟩ -4 log 2 n. By Lemma 2.3, ⟨ Mi , Mj ⟩ ≤ ⟨M i , M j ⟩ < 4 log 2 (n/2), hence we can conclude this case.Case 2 (j > n/2; j ̸ = 2i): Here,X j β = -µ⟨ Mi , Mj ⟩ + 4µ log 2 n. Since |⟨ Mi , Mj ⟩| ≤ |⟨M i , M j ⟩| < 4 log 2 n, X j β < µ • 8 log 2 n, so we conclude the case.Case 3 (j = 2i): In this case, X j β = -µ⟨ Mi , Mi ⟩ + 4µ log 2 n. Since -µ⟨ Mi , Mi ⟩ is negative, we conclude the case.The above cases show that X j β < µ • 8 log 2 n when j ̸ = i. Therefore,R(β) ≤ n • µ • 8 log 2 n + ReLU(X i β) and R(β) ≥ ReLU(X i β).We next show that the bit y i will have a large effect on R(β). If y i = 0, then,X i β = ⟨ Mi , Mi ⟩ = 1 4 ∥M i ∥ 2 2 -4 log 2 n < 1 4 • log 4 (n/2), since Mi ∈ R log 4 (n/2). On the other hand, if y i = 1, then,X i β = ∥ Mi ∥ 2 2 -4 log 2 n = log 4 (n/2) -4 log 2 n > 3 4 log 4 (n/2),where we used our assumption that log 4 (n/2) > 16 log 2 n. Therefore, ify i = 0, R(β) ≤ 1 4 • log 4 n + n • 8µ log 2 n. By setting µ = log 2 n 2 6•n , we find that R(β) < 3 8 log 4 (n/2). On the other hand, ify i = 1, then R(β) > 3 4 log 4 n/2. Therefore, a 2-factor approximation to R(β) is able to decide if y i equals zero or one. By reduction to the INDEX problem, this implies that any 2-factor approximation to R(β) must take at least Ω(n) space (see Theorem 6). Now we must just prove that µ y (X) = O(n). We will use the following inequality [13] . For any two length n sequences of positive numbers, a r , r = 1 . . . n and b r , r = 1 . . . n,n r=1 a r n r=1 b r ≤ max r=1...n a r b r ,where the maximum is taken over an arbitrary fixed ordering of the sequences. Let us define these two sequences as follows for a fixedβ ∈ R d . For i ∈ 1 . . . n /2, if X i β > 0, let a i = X i β and b i = -1 • X 2i β. If X i β < 0, let a i = X 2i β and b i = -1 • X i β.We can disregard the case where X i β = 0, since this will not affect the sums of the sequences. Given such sequences, we get:∥(Xβ) + ∥ 1 ∥(Xβ) -∥ 1 = r a r r b r ≤ max r a r b r ≤ 1 µ .The last inequality follows sinceX 2i β = -µ • X i β for i = 1 . . . n /2. Hence, we conclude that µ y (X) = µ -1 = O(n).The above theorem proves that a constant factor approximation to R(•) requires Ω(µ y (X)) space.We now extend this result to logistic loss. Theorem 3. Let n ≥ n 0 (for some constant n 0 ∈ N) be a positive integer. There exists a global constant ϵ 0 > 0 and a matrix X ∈ R n×k such that any data structure L(•) that, with at least 2/3 probability, satisfies (for a fixed β ∈ R d ):(1 -ϵ 0 )L(β; X) ≤ L(β; X) ≤ (1 + ϵ 0 )L(β; X)and requires at least Ω(d • µ y (X)) bits of space.Proof. The space complexity lower bound holds even if L(•) approximates R(•) only on the values of β used to query the data structure in the proof of Lemma 2.4. Define this set asB = {[ Mi , -4 log 2 n] T ∈ R k ′ | i = 1 . . . n /2}, where M is used to construct X in eqn. 5. Since R(β) ≥ X i β, we get R(β) ≥ ∥ Mi ∥ 2 2 -4 log 2 n ≥ log 4 (n/2) 4 -4 log 2 n.Therefore, R(β) ≥ 1 for all n ≥ n 0 , where n 0 is some constant in N. By Lemma 2.1, the space complexity of a data structure that achieves(1 -ϵ)L(β) ≤ L(β) ≤ (1 + ϵ)L(β)for a fixed β ∈ B must be at least the space complexity of a data structure achievingR(β) ≤ R(β) ≤ (1 + 3ϵ) (1 -3ϵ) R(β)for β ∈ B. We can now solve for ϵ by setting (1+3ϵ) /(1-3ϵ) = 2. Therefore, from Lemma 2.4, we conclude that there exists a constant ϵ 0 > 0 such that any data structure providing an ϵ 0 -relative approximation to the logistic loss requires at least Ω(n) = Ω(µ y (X)) space.Finally, applying the argument used in Corollary 2 of constructing a matrix Y, we achieve anΩ(d • µ y (X)) lower bound.While prior work has show that mergeable coresets must include Ω(d • µ y (X)) points to attain a 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 β ∈ R d with a specified probability. The proof of the lower bound in [17] relies on constructing a 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, a mergeable coreset that compresses A can be used to 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 is applied to X.3 Computing the complexity measure µ y (X) in polynomial timeWe present an efficient algorithm to compute the data complexity measure µ y (X) of Definition 1 on real data sets, refuting an 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 on real-world data sets would help guide further improvements to coreset construction for logistic regression.Prior work conjectured that µ y (X) was hard to compute and presented a polynomial time algorithm to approximate the measure to within a poly(d)-factor (see Theorem 3 of Munteanu et al. [10] ). We refute this conjecture by showing that the complexity measure µ y (X) can in fact be computed efficiently via linear programming, as shown in the following theorem. The specific LP formulation for computing a vector β * such that µ y (X) =∥(DyXβ * ) -∥1 ∥(DyXβ * ) + ∥1is given in eqn. ( 9) in the Appendix. Theorem 4. If the complexity measure µ y (X) of Definition 1 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 µ y (X) using the method provided by Munteanu et al. [10] . We will empirically compare how prior methods of estimating the complexity measure compare to our exact method in Section 4.Question: Does the paper discuss the limitations of 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 µ y (X) for real datasets as an open direction.Guidelines:• The answer NA means that the paper has no 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 (e.g., independence assumptions, noiseless settings, model well-specification, 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 a few datasets or with a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to 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 fairness. • 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 acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
theory assumptions and proofs: 
 Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [Yes] Justification: Code and instructions to reproduce our results are provided in the supplementary material.Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
experiments: 
 We provide empirical evidence verifying the algorithm of Section 3 to exactly computes the classification complexity measure µ y (X) of Definition 1. We compare our results with the approximate sketching-based calculation of Munteanu et al. [10] .In order to estimate µ y (X) for a dataset using the sketching-based approach of Munteanu et al. [10] , we create several smaller sketched datasets of a given full dataset of size n × d (n rows and d columns). We then use a modified linear program along the lines of Munteanu et al. [10] . These new datasets are created so that they have number of rows n ′ = O(d log(d/δ)), for various values of δ ∈ [0, 1], so that with probability at least 1 -δ, the estimated µ y (X) will lie between some lower bound (given by t, the optimum value of the aforementioned linear program) and an upper bound (given by t • O(d log d)). In order to solve the modified linear programs, we make use of the OR-tools 1 .Synthetic data: We create the synthetic dataset as follows. First, we construct the full data matrix X ∈ R n×d by drawing n = 10, 000 samples from the d-dimensional Gaussian distribution N (0, I d ) with d = 100. We generate an arbitrary β ∈ R d with ∥β∥ 2 = 1 and generate the posterior p(y i |x i ) = 1/(1 + exp(-β ⊤ x i + N (0, 1))). Finally, we create the labels y i for all i = 1 . . . n by setting y i to one if p(y i |x i ) > 0.5 and to -1 otherwise.Using the full data matrix A = D y X, we create several sketched data matrices having a number of rows equal to n ′ = O(d log(d/δ)). We choose δ so that n ′ ∈ {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 (FastL1Basis [1] ) for sketching. The algorithm is meant to ensure that the produced sketch identifies ℓ 1 well-conditioned bases for A, which is a prerequisite for using the subsequent linear program to estimate µ y (X). (See Section C for details).The results are presented in Figure 1a . 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 µ y (X) on the sketched matrix using the linear program of Theorem 4. We also show the corresponding upper and lower bounds on µ y (X) of the full data set as estimated by the well-conditioned basis hunting approximation proposed by Munteanu et 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 d log(d/δ). 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 Figure 1 : Simulated data results for exact computation of µ y (X) (Theorem 4) using the full data (Exactfull), sketched data (ExactSketched) vs the approximate upper (ApprSketchedUpper) and lower bounds (ApprSketchedLower) as suggested by Munteanu et al. [10] (see Section C). The results clearly show that the upper and lower bounds can be very loose compared to our exact calculation of the complexity measure µ y (X) .for each value of n ′ . Figure 1a shows that the exact computations on sketched matrices are close to the actual µ y (X) of the full data matrix, while the upper and lower bounds as proposed by Munteanu et al. [10] can be fairly loose.Real data experiments: To test our setup on real data, we make use of the sklearn KDDcup dataset. 2 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 negative. To create various sized subsets for exact calculation, we subsample from positives and negatives so that they are in 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 of over 400k constraints, we subsample 16384 data points and use its µ as proxy for that of the full dataset (referred to as ExactFull. For such a large subsample, the error bars are small. We compare against sketching and exact µ calculations for smaller subset (See Figure 1b for the results). 
future work: 
 Our work shows that existing coresets are optimal up to lower order factors in the regime where µ y (X) = O (1) . A clear open direction would be proving a space complexity lower bound that holds for all valid values of ϵ and µ y (X). Additionally, there is still a d factor gap between existing upper bounds [9] and our lower bounds (Theorems 1 and 3) in the regime where ϵ is constant and the complexity measure varies or the complexity measure is constant and ϵ varies respectively.Another interesting direction would be to explore whether additional techniques can further reduce the space complexity in approximating logistic loss compared to coresets alone. While Theorem 1 shows that the size of coreset constructions are essentially optimal, it 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 1 is sparse, and so existing matrix sparsification methods would save this d factor here.We also note that our first lower bound (Theorem 1) only applies to data structures providing the the "for-all" guarantee on the logistic loss, i.e., with a given probability, the error guarantee in eqn.( 2) holds for all β ∈ R d . It would be interesting to know if it could strengthened to apply in the "for-each" setting as Theorem 3 does, where β ∈ R d is arbitrary but fixed.Finally, it would be useful to gain a better understanding of the complexity measure µ y (X) in real data through more comprehensive experiments using our method provided in Theorem 4. In particular, subsampling points of a data set may create bias when computing µ y (X).In this section, we list some useful results from prior work.We use the following formulation of Hoeffding's inequality.Theorem 5 (Theorem 2 in [4] ). Let X 1 , . . . , X n be independent random variables with m i ≤ X i ≤ M i , 1 ≤ i ≤ n. Then, for any t > 0,P n i=1 (X i -E[X i ]) ≥ t ≤ 2 exp -2t 2 n i=1 (M i -m i ) 2 .Both Theorem 1 and Theorem 3 rely on a reduction to the randomized INDEX problem. We define the INDEX problem as a data structure as done in [6] .The INDEX data structure stores an input string y {0, 1} n and supports a query function, which receives input i ∈ [n] and outputs y i ∈ {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 6. (see [8] ) In the INDEX problem, suppose that the underlying string y is drawn uniformly from {0, 1} n and the input i of the query function is drawn uniformly from [n]. Any (randomized) data structure for INDEX that succeeds with probability at least 2/3 requires Ω(n) bits of space, where the randomness is taken over both the randomness in the data structure and the randomness of s and i.Proof for Lemma 2.1Proof. Let R min = inf β∈R d R(β). We now prove that a data structure, L(•), which approximates logistic loss to relative error can be used to construct an approximation to the ReLu loss, R(•), by R(β) = 1 t • L(t • β) for large enough constant t > 0. To show this, we start by bounding the approximation error of the logistic loss for a single point. First, we derive the following inequality when r > 0:1 t log(1 + e t•r ) -r = 1 t log(e rt ) + log 1 + e rt e rt -r = 1 t • log 1 + 1 e rt ≤ 1 t • e rt . Therefore, if x T i β > 0, then | 1 t log(1 + e t•x T i β ) -x T i β| < 1 t•e t•x T i β .Next, we consider the case where r ≤ 0, in which case ReLu(r) = 0. It directly follows that 0 ≤ 1 t log(1 + e t•r ) ≤ e t•r t . Therefore,| 1 t • log(1 + e t•r ) -max{0, r}| ≤ 1 t • e t•|r| ≤ 1 t .We use these inequalities to bound the difference in the transformed logistic loss and ReLu loss as follows:EQUATIONTherefore, if we set t * = n ϵ•Rmin(β) , thenEQUATIONfor all β ∈ B. We can then show that L(•) can be used to approximate R(•) by applying the triangle inequality, the error guarantee of L(•) and eqn. 7. For all β ∈ B:1 t * • L (t * • β) -R(β) ≤ 1 t * • L (t * • β) - 1 t * • L (t * • β) + 1 t * • L (t * • β) -R(β) ≤ ϵ • 1 t * • L (t * • β) + ϵR(β) ≤ ϵ • R(β) + R(β) - 1 t * • L (t * • β) + ϵR(β) ≤ ϵ • R(β) + ϵ 2 • R(β) + ϵ • R(β) ≤ 3ϵR(β).Note that we can set R min to one and achieve the same error guarantee, since inf β∈B R(β) > 1.Therefore, storing t * takes O(log n ϵ ) space.Proof for Lemma 2.2Proof. We will first lower bound the space needed by any data structure which approximates ReLu loss to ϵ-relative error. Later, we will show that this implies a lower bound on the space complexity of any data structure f (•) for approximating logistic loss.Let R(•) approximate R(•) such that R(β) ≤ R(β) ≤ (1 + ϵ)R(β) for all β ∈ R d .We can rewrite R(β) as follows:R(β) = n i=1 max{0, x T i β} = n i=1 1 /2 • x T i β + 1 /2 • |x T i β| = 1 2 1 T Xβ + 1 2 ∥Xβ∥ 1 .We next use the fact that R(β) ≤ ∥Xβ∥ 1 to get|R(β) -R(β)| = | 1 2 1 T Xβ + 1 2 ∥Xβ∥ 1 -R(β)| ≤ ϵR(β) ⇒ | 1 2 1 T Xβ + 1 2 ∥Xβ∥ 1 -R(β)| ≤ ϵ∥Xβ∥ 1 .We can store 1 T X exactly in O(d) space as a length d vector. We define a new data structure H(•) such that H(β) = 2 R(β) -1 T Xβ, and, using the above inequality, H(β) satisfies:|∥Xβ∥ 1 -H(β)| ≤ 2ϵ∥Xβ∥ 1 ,for all β ∈ R d . Therefore, H(β) is an ϵ-relative approximation to ∥Xβ∥ 1 after adjusting for constants and solves the ℓ 1 -subspace sketch problem (see Definition 1.1 in [6] ). By Corollary 3.13 in [6] , the data structure H(•) requires Ω d ϵ 2 bits of space if d = Ω(log 1/ϵ) and n = Ω dϵ -2 . Therefore, we conclude that any data structure which approximates R(β) to ϵ-relative error for all β ∈ R d with at least 2/3 probability must use Ω d ϵ 2 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 ϵ-relative error approximations to ∥Aβ∥ 1 require the stated space complexity. We next show that, µ y (A) ≤ 4. The construction of A is described directly above Lemma 3.10. This matrix A is first set to contain all 2 k unique k length vectors in {-1, 1} k for some value of k. Each row of A is then re-weighted: specifically, the i-th row of A is re-weighted by somey i ∈ [2 √ k, 8 √ k].For any vector β ∈ R d , ∥(Aβ) + ∥ 1 ≤ 4 • ∥(Aβ) -∥ 1 by the following argument. For an arbitrary i ∈ [n], let A i = y i • v where {±1} k . Then there exists a unique j ∈ [n] such that A j = -1 • y j • v, and so A j β < 0. Furthermore, since y j ≥ 2√ k and y i ≤ 8 √ k, |Aiβ| |Aj β| ≤ 4.By applying this argument to each row of A where A i β > 0, we conclude that ∥(Aβ) + ∥ 1 ≤ 4 • ∥(Aβ) -∥ 1 , and hence µ y (X) ≤ 4.Finally, we show that R(β; X) is lower bounded in this construction. Given any vector β ∈ R d , there exists a row of X such that X ij • β j ≥ 0 for all j ∈ {1 . . . d}, that is, the j-th entry of X i has the same sign as β j in all non-zero entries of β. Therefore,X i β = y i • ∥β∥ 1 . Since y i ≥ 3 √ k, we conclude that R(β; X) ≥ 3∥β∥ 1 .Proof. Let A ∈ {-1, 1} n×k be a random matrix where each entry is uniformly sampled from {-1, 1} in independent identical trials. Let {R r } r∈[k] be independent Rademacher random variables. Then,P(|⟨A i , A j ⟩| ≥ t) = P | k r=1 R r | ≥ t ≤ 2 exp -t 2 2k ,where the last step follows from applying Hoeffding's inequality. There are fewer than n 2 tuples (i, j) ∈ {1 . . . d} × {1 . . . d} such that i ̸ = j. Therefore, by an application of the union bound,P(|⟨A i , A j ⟩| ≥ t for all i ̸ = j) ≤ n 2 • 2 exp -t 2 2k .Setting t = 4 √ k • log n, we see that the right side of the inequality is less than one whenever n > 1. Therefore, there must exist a matrix M satisfying the specified criteria.Proof. We now derive a linear programming formulation to compute the complexity measure in Definition 1. Note that we flip the numerator and denominator from Definition 1 without loss of generality. Let β * ∈ R d be: 3β * = argmax ∥β∥2=1 ∥(D y Xβ) -∥ 1 ∥(D y Xβ) + ∥ 1 ⇒ µ y (X) = ∥(D y Xβ * ) -∥ 1 ∥(D y Xβ * ) + ∥ 1The second line above uses the fact that the definition of µ y (X) does not depend on the scaling of β.If C is an arbitrary positive constant, then there exists a constant c > 0 such that:c • β * = argmax β∈R d ∥(D y Xβ) -∥ 1 such that ∥(D y Xβ) + ∥ 1 ≤ C = argmax β∈R d ∥D y Xβ∥ 1 such that ∥(D y Xβ) + ∥ 1 ≤ C.Again, ∥(DyXβ * ) -∥1 /∥(DyXβ * ) + ∥1 is invariant to rescaling of β * , so we may assume that c is equal to one without loss of generality. We now reformulate the last constraint as follows:∥(D y Xβ) + ∥ 1 = n i=1 max{[D y Xβ] i , 0} = n i=1 1 2 [D y Xβ] i + 1 2 |[D y Xβ] i | = 1 2 1 T D y Xβ + 1 2 ∥D y Xβ∥ 1 .Therefore, the above formulation is equivalent to:β * = argmax β∈R d ∥D y Xβ∥ 1 such that 1 2 1 T D y Xβ + 1 2 ∥D y Xβ∥ 1 ≤ C = argmin β∈R d 1 T D y Xβ such that ∥D y Xβ∥ 1 ≤ C.3 For notational simplicity, we assume β * is unique, but this is not necessary.Next, we replace D y Xβ with a single vector z ∈ R n and a linear constraint to guarantee that z ∈ Range(D y X). Let P R ∈ R n×n be the orthogonal projection to Range(D y X). Then,z * = argmin z∈R d 1 T z (8)such that ∥z∥ 1 ≤ C and (I -P R )z = 0.Next, we solve this formulation by constructing a linear program such that [z + , z -] ∈ R 2n corresponds to the absolute value of the positive and negative elements of z, namelyEQUATIONsuch that1 T n (z + + z -) ≤ C and (I -P R )(z + -z -) = 0 and z + , z -≥ 0.Observe that this is a linear program with 2n variables and 4n constraints. After solving this program for z * + and z * -, we can compute z * = z * + -z * -. From this, we can compute β * by solving the linear system z * = D y Xβ * , which is guaranteed to have a solution by the linear constraint (I-P R )z * = 0.After solving for β * , we can computeµ y (X) = ∥(D y Xβ * ) -∥ 1 ∥(D y Xβ * ) + ∥ 1 ,thus completing the proof.For completeness, we reproduce the linear program of Munteanu et al. [10] [Section A] to estimate the complexity measure µ y (X):min n i=1 b i s.t. ∀i ∈ [n] : (U β) i = a i -b i ∀i ∈ [d] : β i = c i -d i d i=1 c i + d i ≥ 1 ∀i ∈ [n] : a i , b i ≥ 0 ∀i ∈ [d] : c i , d i ≥ 0.Here, U is ℓ 1 -well-conditioned basis [2] of the matrix D y X. Because of the well-conditioned property, µ can be estimated to be within the bounds:1 t ≤ µ y (X) ≤ poly(d). 1 t ,where t = min ∥β∥1=1 ∥(U β) -∥ 1 , and recall that d is the number of columns of X. Munteanu et al. [10] designed the above linear program to solve for t. However, note that trivially the LP as it is written could be trivially solved with ∀ic i = d i =⇒ β i = 0 =⇒ a i = b i = 0, which unfortunately gives t = 0 always trivially. To get around this problem, we modify the above program as follows:min n i=1 b i s.t. ∀i ∈ [n] : (U β) i = a i -b i ∀i ∈ [d] : h i = c i -β i ∀i ∈ [d] : h i = d i + β i ∀i ∈ [d] : c i ≤ M v i ∀i ∈ [d] : d i ≤ M (1 -v i ) d i=1 h i ≥ 1 ∀i ∈ [n] : a i , b i ≥ 0 ∀i ∈ [d] : c i , d i , h i ≥ 0 ∀i ∈ [d] : v i ∈ {0, 1}Here, M is a sufficiently large value as is often used for Big-M constraints4 in linear programs. The variable h i simulates the |β i |, and is set according to the binary variable v i which decides which one of c i or d i is 0. Further, note that i h i ≥ 1 is equivalent to i h i = 1 here since scaling down the norm of β can only bring the optimization cost down. To solve the optimization problem, we use the Google OR-tools and the wrapper pywraplp with the solver SAT which can handle integer programs since the above program is no longer a pure linear program because of the binary variables v i .Here, we provide a very simple data structure that provides an additive error approximation to the logistic loss. While the method is straightforward, we are unaware of this approximation being specified in prior work, and it 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 L(β) up to a √ n∥X -X∥ 2 ∥β∥ 2 additive error. The factor ∥X -X∥ 2 ∥β∥ 2 is the spectral norm (or two-norm) error of the low-rank approximation and we also prove that this bound is tight in 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 of low-rank approximations via sketching, sampling, and direct methods [5] . We show that a spectral approximation provides an additive error guarantee for the logistic loss and that this guarantee is tight on worst-case inputs.Theorem 7. If X, X ∈ R n×d , then for all β ∈ R d , |L(β; X) -L(β, X)| ≤ √ n∥X -X∥ 2 ∥β∥ 2 .Proof. To simplify the notation, let s = Xβ and d = (X -X)β. We can then write the difference in the log loss as:|L(β; X) -L(β, X)| = n i=1 log 1 + e x T i β + λ 2 ∥β∥ 2 2 - n i=1 log 1 + e xT i β + λ 2 ∥β∥ 2 2 = n i=1 log 1 + e si 1 + e si+di ≤ n i=1 log 1 + e si 1 + e si-|di| = n i=1 log 1 + e si 1 + e -|di| e si ≤ n i=1 log 1 e -|di| 1 + e si 1 + e si = n i=1 |d i | = ∥d∥ 1 . Therefore, we can conclude that |L(β; X) -L(β; X)| ≤ ∥d∥ 1 ≤ √ n∥d∥ 2 ≤ √ n∥ X -X∥ 2 ∥β∥ 2 .We note that Theorem 7 holds for any matrix X ∈ R n×d that approximates X with respect to the spectral norm, and does not necessitate that X has low-rank. We now provide a matching lower-bound for the logistic loss function in the same setting. Theorem 8. For every d, n ∈ N where d ≥ n, there exists a data matrix X ∈ R n×d , label vector y ∈ {-1, 1} n , parameter vector β ∈ R d , and spectral approximation X ∈ R n×d such that:|L(β; X) -L(β; X)| ≥ (1 -δ) √ n∥X -X∥ 2 ∥β∥ 2 ,for every δ > 0. Hence, the guarantee of Theorem 7 is tight in the worst case.Proof. To prove the theorems statement, we first consider the case of square matrices (d = n). In particular, first consider the case where d = n = 1, where X = [x] and X = [x + s], in which case ∥X -X∥ 2 = s. Then,lim x→∞ L([1]; [x + s]) -L([1]; [x]) = lim x→∞ log(1 + e x+s ) -log(1 + e x ) = sWhich shows that for β = [1] and x with large enough magnitudeL(β; X) -L(β; X) = (1 - δ)∥X -X∥ 2 . Next, let X = x • I n , X = (x + s) • I n , and β = 1 n . Then for all i ∈ [n], x T i β = x and x T i β = x + s. Therefore, lim x→∞ L(β; X) -L(β; X) = lim x→∞ n i=1 log(1 + e x+s ) -log(1 + e x ) = sn. Since ∥X -X∥ 2 = ∥s • I∥ 2 = s. ∥β∥ 2 = √ n, lim x→∞ L(β; X) -L(β; X) = sn = √ n∥X -X∥ 2 ∥β∥ 2Hence, we conclude the statement of the theorem for the case where d = n. To conclude the case for d ≥ n, note that √ n∥X -X∥ 2 ∥β∥ 2 does not change if we extend X and X with columns of zeroes and extend β with entries of zero until X, X ∈ R n×d and R d . This procedure also does not change the loss at β, hence we conclude the statement of the theorem. 
experimental setting/details: 
 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes] Justification: We do not provide a 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 in the core of the paper to a 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, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [Yes] Justification: We provide error 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 error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.• 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 or the standard error of the mean. Justification: We follow all of the relevant ethical guidelines.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: While we expect our work to benefit the development of methods for logistic regression, our work is far upstream from any applications, and hence it is not possible to productively consider broader impact.Guidelines:• 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 negative 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 a 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 as 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. • If 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). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: Our work is not related to any of these mentioned areas. Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to 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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make a 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 is used and, if 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.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
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/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was 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. 
crowdsourcing 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 as 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 in the supplemental material is fine, but if the main contribution 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. 
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 an equivalent approval/review based on the requirements of your country or institution) were obtained?Answer: [NA] Justification:Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Depending on 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.• We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to 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.38th Conference on Neural Information Processing Systems (NeurIPS 2024).https://developers.google.com/optimizationsklearn.datasets.fetch_kddcup99() provides an API to access this dataset.SeeLinear and Nonlinear Optimization (2nd ed.). Society for Industrial Mathematics 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.

- The experiments could have been conducted on more diverse datasets, including real-world applications beyond synthetic and KDDCup datasets. 

- The paper introduces a new method to compute the complexity measure µy(X). Including more detailed explanations would be useful.
questions: questions: -
limitations: limitations: Yes. Authors mention that more comprehensive experiments in computing $\mu_y(X)$ for real datasets as an open direction.
paper_summary: paper_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.
strength_weakness: strength_weakness: N/A. The reviewer is not familiar with space complexity area.
questions: questions: A minor issue, the font of the paper seems different from other papers.
limitations: limitations: Yes.
paper_summary: paper_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.

There 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.
strength_weakness: strength_weakness: * 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.
* the $\Omega(\mu)$ bound is only from a $\Omega(n)$ bound for some case where $\mu \approx n$
questions: questions: * any chance the two bounds can be combined to a $\Omega(d\mu/\epsilon^2)$ bound?
* if not then do you think $O(d(\mu+1/\epsilon^2))$ might be possible?
* 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}$?
* 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: limitations: see above
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: questions: Are there wider classes of functions that the approach for showing coreset lower bounds here can generalize to?
limitations: limitations: yes

Comments: title: thank you
comment: Thank you, I appreciate the additional comments.
> I think Woodruff, Yasuda, 2023 had a more 'natural' way of providing LB for different values of $\mu$ rather than padding with zeros which you might want to consider

Regarding Woodruff/Yasuda 2023: Is the reviewer referring to the extension of the $\mu = n$ case to $\mu < n$ for the $\Omega(\mu)$ bound using Woodruff/Yasuda 2023 rather than our padding technique? We agree that this is indeed worth exploring. However, it is not obvious to us (at least within this short time window) whether this is possible. We will keep thinking about this and we very much appreciate the reviewer's suggestion. Just as a final note, this would not alter the final bounds and our method is also valid and correct.

> your comment regarding $\Omega(d(\mu + \frac{1}{\epsilon^2}))$ is clearly straightforward from the two bounds. Actually, I was asking whether you believe in an $O(d(\mu + \frac{1}{\epsilon^2}))$ upper bound (in case there are principled difficulties for achieving $\Omega(d\mu/\epsilon^2)$)

From our perspective, it still seems feasible that an $\Omega(d\mu/\epsilon^2)$ lower bound holds and the difficulty stems from technical complexity in combining the two reductions smoothly.
 
One intuitive insight related to our proofs is that the parameter $\mu$ describes how much better an $\epsilon$-relative error approximation to ReLU loss (which can be approximated by logistic loss) is than an $\epsilon$-relative error approximation to an $\ell\_1$-norm on worst case vectors in absolute terms. This is because $||(\mathbf{X}\beta)^+||\_1$ can be approximately $1/\mu$ of $||\mathbf{X}\beta||\_1$. However, this relation cannot hold for all vectors $\beta \in \mathbb{R}^d$ simultaneously. This cannot be immediately combined with the L1-norm lower bound, but may be useful to note in pursuing either an $O(d(\mu + 1/\epsilon^2))$ upper bound or $\Omega(d\mu/\epsilon^2)$ lower bound.
I thank the authors for their response. I have updated my scores by 1.
Thank you for these clarifications and further details. My opinions on the paper are unchanged.
Thank you for the rebuttal, I like the paper and will keep my score, which is already on the positive side.

Two more comments on your rebuttal:
* I think Woodruff, Yasuda, 2023 had a more 'natural' way of providing LB for different values of $\mu$ rather than padding with zeros which you might want to consider
* your comment regarding $\Omega(d(\mu + \frac{1}{\epsilon^2}))$ is clearly straightforward from the two bounds. Actually, I was asking whether you believe in an $O(d(\mu + \frac{1}{\epsilon^2}))$ **upper** bound (in case there are principled difficulties for achieving $\Omega(d\mu/\epsilon^2)$)
Thanks, I will keep my scores.
Dear reviewers,

Thank you for taking the time to review the paper. Notice that the discussion period has begun, and will last until August 13 (4 more days).

During this time your active participation and engagement with the authors is very important, and highly appreciated. Specifically, please _read the responses_, _respond to them early on in the discussion_, and **discuss points of disagreement**.

Thank you for your continued contributions to NeurIPS 2024.

Best, Your Area Chair.