{"id":898524,"date":"2022-11-15T15:36:55","date_gmt":"2022-11-15T23:36:55","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/"},"modified":"2022-11-22T12:23:38","modified_gmt":"2022-11-22T20:23:38","slug":"adaptive-sketches-for-robust-regression-with-importance-sampling","status":"publish","type":"msr-research-item","link":"https:\/\/www.microsoft.com\/en-us\/research\/publication\/adaptive-sketches-for-robust-regression-with-importance-sampling\/","title":{"rendered":"Adaptive Sketches for Robust Regression with Importance Sampling"},"content":{"rendered":"<p><span dir=\"ltr\" role=\"presentation\">We introduce data structures for solving robust regression through stochastic gradient descent (SGD) <\/span><span dir=\"ltr\" role=\"presentation\">by sampling gradients with probability proportional to their norm, i.e., importance sampling. Although <\/span><span dir=\"ltr\" role=\"presentation\">SGD is widely used for large scale machine learning, it is well-known for possibly experiencing slow <\/span><span dir=\"ltr\" role=\"presentation\">convergence rates due to the high variance from uniform sampling.<\/span> <span dir=\"ltr\" role=\"presentation\">On the other hand, importance sampling<\/span><span dir=\"ltr\" role=\"presentation\"> can significantly decrease the variance but is usually difficult to implement because computing <\/span><span dir=\"ltr\" role=\"presentation\">the sampling probabilities requires additional passes over the data, in which case standard gradient <\/span><span dir=\"ltr\" role=\"presentation\">descent (GD) could be used instead.<\/span> <span dir=\"ltr\" role=\"presentation\">In this paper, we introduce an algorithm that approximately <\/span><span dir=\"ltr\" role=\"presentation\">samples<\/span> <span dir=\"ltr\" role=\"presentation\">T<\/span> <span dir=\"ltr\" role=\"presentation\">gradients of dimension<\/span> <span dir=\"ltr\" role=\"presentation\">d<\/span> <span dir=\"ltr\" role=\"presentation\">from nearly the optimal importance sampling distribution for a robust <\/span><span dir=\"ltr\" role=\"presentation\">regression problem over<\/span> <span dir=\"ltr\" role=\"presentation\">n<\/span> <span dir=\"ltr\" role=\"presentation\">rows.<\/span> <span dir=\"ltr\" role=\"presentation\">Thus, our algorithm effectively runs<\/span> <span dir=\"ltr\" role=\"presentation\">T<\/span> <span dir=\"ltr\" role=\"presentation\">steps of SGD with importance <\/span><span dir=\"ltr\" role=\"presentation\">sampling while using sublinear space and just making a single pass over the data. Our techniques also <\/span><span dir=\"ltr\" role=\"presentation\">extend to performing importance sampling for second-order optimization.<\/span><\/p>\n","protected":false},"excerpt":{"rendered":"<p>We introduce data structures for solving robust regression through stochastic gradient descent (SGD) by sampling gradients with probability proportional to their norm, i.e., importance sampling. Although SGD is widely used for large scale machine learning, it is well-known for possibly experiencing slow convergence rates due to the high variance from uniform sampling. On the other [&hellip;]<\/p>\n","protected":false},"featured_media":0,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","footnotes":""},"msr-content-type":[3],"msr-research-highlight":[],"research-area":[13561],"msr-publication-type":[193716],"msr-product-type":[],"msr-focus-area":[],"msr-platform":[],"msr-download-source":[],"msr-locale":[268875],"msr-post-option":[],"msr-field-of-study":[],"msr-conference":[],"msr-journal":[],"msr-impact-theme":[],"msr-pillar":[],"class_list":["post-898524","msr-research-item","type-msr-research-item","status-publish","hentry","msr-research-area-algorithms","msr-locale-en_us"],"msr_publishername":"","msr_edition":"","msr_affiliation":"","msr_published_date":"2022-9-1","msr_host":"","msr_duration":"","msr_version":"","msr_speaker":"","msr_other_contributors":"","msr_booktitle":"","msr_pages_string":"","msr_chapter":"","msr_isbn":"","msr_journal":"","msr_volume":"","msr_number":"","msr_editors":"","msr_series":"","msr_issue":"","msr_organization":"","msr_how_published":"","msr_notes":"","msr_highlight_text":"","msr_release_tracker_id":"","msr_original_fields_of_study":"","msr_download_urls":"","msr_external_url":"","msr_secondary_video_url":"","msr_longbiography":"","msr_microsoftintellectualproperty":1,"msr_main_download":"","msr_publicationurl":"","msr_doi":"","msr_publication_uploader":[{"type":"url","viewUrl":"false","id":"false","title":"https:\/\/arxiv.org\/pdf\/2207.07822.pdf","label_id":"243109","label":0}],"msr_related_uploader":"","msr_attachments":[],"msr-author-ordering":[{"type":"user_nicename","value":"Sepideh Mahabadi","user_id":40780,"rest_url":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=Sepideh Mahabadi"},{"type":"text","value":"David P. Woodruff","user_id":0,"rest_url":false},{"type":"text","value":"Samson Zhou","user_id":0,"rest_url":false}],"msr_impact_theme":[],"msr_research_lab":[199565],"msr_event":[],"msr_group":[437022],"msr_project":[],"publication":[],"video":[],"download":[],"msr_publication_type":"inproceedings","related_content":[],"_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/898524"}],"collection":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item"}],"about":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-research-item"}],"version-history":[{"count":3,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/898524\/revisions"}],"predecessor-version":[{"id":898533,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/898524\/revisions\/898533"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=898524"}],"wp:term":[{"taxonomy":"msr-content-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-content-type?post=898524"},{"taxonomy":"msr-research-highlight","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-highlight?post=898524"},{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=898524"},{"taxonomy":"msr-publication-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-publication-type?post=898524"},{"taxonomy":"msr-product-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-product-type?post=898524"},{"taxonomy":"msr-focus-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-focus-area?post=898524"},{"taxonomy":"msr-platform","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-platform?post=898524"},{"taxonomy":"msr-download-source","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-download-source?post=898524"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=898524"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=898524"},{"taxonomy":"msr-field-of-study","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-field-of-study?post=898524"},{"taxonomy":"msr-conference","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-conference?post=898524"},{"taxonomy":"msr-journal","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-journal?post=898524"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=898524"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=898524"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}