The Space Complexity of Approximating Logistic Loss

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

This 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.

Are there wider classes of functions that the approach for showing coreset lower bounds here can generalize to?

Yes, 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).

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.

Thank 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.

the $\Omega(n)$ bound is only from a $\Omega(n)$ bound for some case where $\mu \approx n$

Our 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.

any chance the two bounds can be combined to a $\Omega(d\mu/\epsilon^2)$ bound?

We 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 $`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.

if not then do you think $\Omega(d(\mu + \frac{1}{\epsilon^2}))$ might be possible?

Yes, 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.

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}$?

By using our construction and padding $\mathbf{X}$ with zeroes as described above, the lower bound can be immediately extended to all $\mu \lesssim 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?

Since 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).

A minor issue, the font of the paper seems different from other papers.

Thanks for pointing this out. We have fixed the issue.

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.

Our 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.

The 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.

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

We 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.

The paper introduces a new method to compute the complexity measure µy(X). Including more detailed explanations would be useful.

We 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.