Poster
The Space Complexity of Approximating Logistic Loss
Gregory Dexter · Petros Drineas · Rajiv Khanna
West Ballroom A-D #7305
Abstract:
We provide space complexity lower bounds for data structures that approximate logistic loss up to -relative error on a logistic regression problem with data and labels . The space complexity of existing coreset constructions depend on a natural complexity measure . We give an space complexity lower bound in the regime that shows existing coresets are optimal in this regime up to lower order factors. We also prove a general space lower bound when is constant, showing that the dependency on is not an artifact of mergeable coresets. Finally, we refute a prior conjecture that is hard to compute by providing an efficient linear programming formulation, and we empirically compare our algorithm to prior approximate methods.
Chat is not available.