Showing cs.DSShow all
2 papers · 1 filter
cs.DS2024
The Space Complexity of Approximating Logistic Loss
Gregory Dexter, Petros Drineas, Rajiv Khanna
We provide space complexity lower bounds for data structures that approximate logistic loss up to -relative error on a logistic regression problem with data $\mathbf{X} \in \mat…
cs.DS2023
Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile Streaming
Gregory Dexter, Petros Drineas, David P. Woodruff +1
Sketching algorithms have recently proven to be a powerful approach both for designing low-space streaming algorithms as well as fast polynomial time approximation schemes (PTAS).…