Data subsampling is one of the most natural methods to approximate a massively large data set by a small representative proxy. In particular, sensitivity sampling received a lot of attention, which samples points proportional to an individual importance measure called sensitivity. This framework reduces in very general settings the size of data to roughly the VC dimension $d$ times the total sensitivity $\\mathfrak S$ while providing strong $(1\\pm\\varepsilon)$ guarantees on the quality of approximation. The recent work of Woodruff and Yasuda (2023) improved substantially over the general $\\tilde O(\\varepsilon^{-2}\\mathfrak Sd)$ bound for the important problem of $\\ell_p$ subspace embeddings to $\\tilde O(\\varepsilon^{-2}\\mathfrak S^{2\/p})$ for $p\\in[1,2]$. Their result was subsumed by an earlier $\\tilde O(\\varepsilon^{-2}\\mathfrak Sd^{1-p\/2})$ bound which was implicitly given in the work of Chen and Derezinski (2021)..<\/p>\n
We show that their result is tight when sampling according to plain $\\ell_p$ sensitivities. We observe that by augmenting the $\\ell_p$ sensitivities by $\\ell_2$ sensitivities, we obtain better bounds improving over the aforementioned results to optimal linear $\\tilde O(\\varepsilon^{-2}(\\mathfrak S+d)) = \\tilde O(\\varepsilon^{-2}d)$ sampling complexity for all $p \\in [1,2]$. In particular, this resolves an open question of Woodruff and Yasuda (2023) in the affirmative for $p \\in [1,2]$ and brings sensitivity subsampling into the regime that was previously only known to be possible using Lewis weights (Cohen \\& Peng, 2015).<\/p>\n
As an application of our main result, we also obtain an $\\tilde O(\\varepsilon^{-2}\\mu d)$ sensitivity sampling bound for logistic regression, where $\\mu$ is a natural complexity measure for this problem. This improves over the previous $\\tilde O(\\varepsilon^{-2}\\mu^2 d)$ bound of Mai et al. (2021) which was based on Lewis weights subsampling.<\/p>\n","protected":false},"excerpt":{"rendered":"
Data subsampling is one of the most natural methods to approximate a massively large data set by a small representative proxy. In particular, sensitivity sampling received a lot of attention, which samples points proportional to an individual importance measure called sensitivity. This framework reduces in very general settings the size of data to roughly the VC dimension $d$ times the total sensitivity $\\mathfrak S$ while providing strong $(1\\pm\\varepsilon)$ guarantees on […]<\/p>\n","protected":false},"author":14,"featured_media":0,"template":"","meta":{"_acf_changed":false,"footnotes":""},"publication-type":[32],"class_list":["post-32644","publication","type-publication","status-publish","hentry","publication-type-inproceedings"],"acf":[],"publishpress_future_workflow_manual_trigger":{"enabledWorkflows":[]},"_links":{"self":[{"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/publication\/32644","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/publication"}],"about":[{"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/types\/publication"}],"author":[{"embeddable":true,"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/users\/14"}],"version-history":[{"count":0,"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/publication\/32644\/revisions"}],"wp:attachment":[{"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/media?parent=32644"}],"wp:term":[{"taxonomy":"publication-type","embeddable":true,"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/publication-type?post=32644"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}