Linear and Kernel Classification in the Streaming Model: Improved Bounds for Heavy Hitters

We study linear and kernel classification in the streaming model. For linear classification, we improve upon the algorithm of (Tai, et al. 2018), which solves the \ell_1 point query problem on the optimal weight vector w_* \in \mathbb{R} d in sublinear space. We first give an algorithm solving the more difficult \ell_2 point query problem on w_*, also in sublinear space. We also give an algorithm which solves the \ell_2 heavy hitter problem on w_*, in sublinear space and running time. Finally, we give an algorithm which can \textit{deterministically} solve the \ell_1 point query problem on w_*, with sublinear space improving upon that of (Tai, et al. 2018).