The Space Complexity of Approximating Logistic Loss

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.

Strengths

Logistical functions are widely used in a multitude of learning tasks, and coresets have been studied for a variety of numerical/optimization problems. The 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.

Questions

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

Rating

7

Confidence

3

Soundness

4

Presentation

3

Contribution

4

Limitations

yes

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.

Strengths

* nearly tight lower bounds against data compression for logistic regression * hold against arbitrary data reduction techniques, not only coresets * 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. * the $\Omega(\mu)$ bound is only from a $\Omega(n)$ bound for some case where $\mu \approx n$

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?

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

see above

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.

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.

Questions

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

Rating

5

Confidence

1

Soundness

3

Presentation

2

Contribution

3

Limitations

Yes.

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.

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

-

Rating

5

Confidence

2

Soundness

3

Presentation

2

Contribution

3

Limitations

Yes. Authors mention that more comprehensive experiments in computing $\mu_y(X)$ for real datasets as an open direction.

thank you

Thank you for these clarifications and further details. My opinions on the paper are unchanged.