{"id":667434,"date":"2020-06-16T10:54:53","date_gmt":"2020-06-16T17:54:53","guid":{"rendered":"https:\/\/new-cm-edgedigital.pages.dev\/en-us\/research\/?post_type=msr-research-item&p=667434"},"modified":"2020-06-16T10:54:53","modified_gmt":"2020-06-16T17:54:53","slug":"learning-mixtures-of-linear-regressions-in-subexponential-time-via-fourier-moments","status":"publish","type":"msr-research-item","link":"https:\/\/new-cm-edgedigital.pages.dev\/en-us\/research\/publication\/learning-mixtures-of-linear-regressions-in-subexponential-time-via-fourier-moments\/","title":{"rendered":"Learning Mixtures of Linear Regressions in Subexponential Time via Fourier Moments"},"content":{"rendered":"

We consider the problem of learning a mixture of linear regressions (MLRs). An MLR is specified by\u00a0k<\/span><\/span><\/span><\/span>\u00a0nonnegative mixing weights\u00a0p<\/span>1<\/span><\/span>,<\/span>\u2026<\/span>,<\/span>p<\/span>k<\/span><\/span><\/span><\/span><\/span>\u00a0summing to\u00a01<\/span><\/span><\/span><\/span>, and\u00a0k<\/span><\/span><\/span><\/span>\u00a0unknown regressors\u00a0w<\/span>1<\/span><\/span>,<\/span>.<\/span>.<\/span>.<\/span>,<\/span>w<\/span>k<\/span><\/span>\u2208<\/span>R<\/span><\/span><\/span>d<\/span><\/span><\/span><\/span><\/span>. A sample from the MLR is drawn by sampling\u00a0i<\/span><\/span><\/span><\/span>\u00a0with probability\u00a0p<\/span>i<\/span><\/span><\/span><\/span><\/span>, then outputting\u00a0(<\/span>x<\/span>,<\/span>y<\/span>)<\/span><\/span><\/span><\/span>\u00a0where\u00a0y<\/span>=<\/span>\u27e8<\/span>x<\/span>,<\/span>w<\/span>i<\/span><\/span>\u27e9<\/span>+<\/span>\u03b7<\/span><\/span><\/span><\/span>, where\u00a0\u03b7<\/span>\u223c<\/span>N<\/span><\/span><\/span>(<\/span>0<\/span>,<\/span>\u03c2<\/span>2<\/span><\/span>)<\/span><\/span><\/span><\/span>\u00a0for noise rate\u00a0\u03c2<\/span><\/span><\/span><\/span>. Mixtures of linear regressions are a popular generative model and have been studied extensively in machine learning and theoretical computer science. However, all previous algorithms for learning the parameters of an MLR require running time and sample complexity scaling exponentially with\u00a0k<\/span><\/span><\/span><\/span>.<\/p>\n

In this paper, we give the first algorithm for learning an MLR that runs in time which is sub-exponential in\u00a0k<\/span><\/span><\/span><\/span>. Specifically, we give an algorithm which runs in time\u00a0O<\/span>\u02dc<\/span><\/span><\/span><\/span>(<\/span>d<\/span>)<\/span>\u22c5<\/span>exp<\/span><\/span>(<\/span>O<\/span>\u02dc<\/span><\/span><\/span><\/span>(<\/span>k<\/span><\/span>\u2212\u2212\u221a<\/span>)<\/span>)<\/span><\/span><\/span><\/span>\u00a0and outputs the parameters of the MLR to high accuracy, even in the presence of nontrivial regression noise. We demonstrate a new method that we call “Fourier moment descent” which uses univariate density estimation and low-degree moments of the Fourier transform of suitable univariate projections of the MLR to iteratively refine our estimate of the parameters. To the best of our knowledge, these techniques have never been used in the context of high dimensional distribution learning, and may be of independent interest. We also show that our techniques can be used to give a sub-exponential time algorithm for learning mixtures of hyperplanes, a natural hard instance of the subspace clustering problem.<\/p>\n","protected":false},"excerpt":{"rendered":"

We consider the problem of learning a mixture of linear regressions (MLRs). An MLR is specified by\u00a0k\u00a0nonnegative mixing weights\u00a0p1,\u2026,pk\u00a0summing to\u00a01, and\u00a0k\u00a0unknown regressors\u00a0w1,…,wk\u2208Rd. A sample from the MLR is drawn by sampling\u00a0i\u00a0with probability\u00a0pi, then outputting\u00a0(x,y)\u00a0where\u00a0y=\u27e8x,wi\u27e9+\u03b7, where\u00a0\u03b7\u223cN(0,\u03c22)\u00a0for noise rate\u00a0\u03c2. Mixtures of linear regressions are a popular generative model and have been studied extensively in machine learning and […]<\/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":"","msr-author-ordering":null,"msr_publishername":"","msr_publisher_other":"","msr_booktitle":"","msr_chapter":"","msr_edition":"","msr_editors":"","msr_how_published":"","msr_isbn":"","msr_issue":"","msr_journal":"","msr_number":"","msr_organization":"","msr_pages_string":"","msr_page_range_start":"","msr_page_range_end":"","msr_series":"","msr_volume":"","msr_copyright":"","msr_conference_name":"STOC 2020","msr_doi":"","msr_arxiv_id":"","msr_s2_paper_id":"","msr_mag_id":"","msr_pubmed_id":"","msr_other_authors":"","msr_other_contributors":"","msr_speaker":"","msr_award":"","msr_affiliation":"","msr_institution":"","msr_host":"","msr_version":"","msr_duration":"","msr_original_fields_of_study":"","msr_release_tracker_id":"","msr_s2_match_type":"","msr_citation_count_updated":"","msr_published_date":"2020-6","msr_highlight_text":"","msr_notes":"","msr_longbiography":"","msr_publicationurl":"","msr_external_url":"","msr_secondary_video_url":"","msr_conference_url":"http:\/\/acm-stoc.org\/stoc2020\/","msr_journal_url":"","msr_s2_pdf_url":"","msr_year":0,"msr_citation_count":0,"msr_influential_citations":0,"msr_reference_count":0,"msr_s2_match_confidence":0,"msr_microsoftintellectualproperty":true,"msr_s2_open_access":false,"msr_s2_author_ids":[],"msr_pub_ids":[],"msr_hide_image_in_river":0,"footnotes":""},"msr-research-highlight":[],"research-area":[13561],"msr-publication-type":[193716],"msr-publisher":[],"msr-focus-area":[],"msr-locale":[268875],"msr-post-option":[],"msr-field-of-study":[],"msr-conference":[],"msr-journal":[],"msr-impact-theme":[],"msr-pillar":[],"class_list":["post-667434","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":"2020-6","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\/abs\/1912.07629","label_id":"243109","label":0}],"msr_related_uploader":"","msr_citation_count":0,"msr_citation_count_updated":"","msr_s2_paper_id":"","msr_influential_citations":0,"msr_reference_count":0,"msr_arxiv_id":"","msr_s2_author_ids":[],"msr_s2_open_access":false,"msr_s2_pdf_url":null,"msr_attachments":[],"msr-author-ordering":[{"type":"text","value":"Sitan Chen","user_id":0,"rest_url":false},{"type":"user_nicename","value":"Jerry Li","user_id":38305,"rest_url":"https:\/\/new-cm-edgedigital.pages.dev\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=Jerry Li"},{"type":"user_nicename","value":"Zhao Song","user_id":37935,"rest_url":"https:\/\/new-cm-edgedigital.pages.dev\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=Zhao Song"}],"msr_impact_theme":[],"msr_research_lab":[],"msr_event":[],"msr_group":[],"msr_project":[],"publication":[],"video":[],"msr-tool":[],"msr_publication_type":"inproceedings","related_content":[],"_links":{"self":[{"href":"https:\/\/new-cm-edgedigital.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/667434","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/new-cm-edgedigital.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item"}],"about":[{"href":"https:\/\/new-cm-edgedigital.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-research-item"}],"version-history":[{"count":1,"href":"https:\/\/new-cm-edgedigital.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/667434\/revisions"}],"predecessor-version":[{"id":667440,"href":"https:\/\/new-cm-edgedigital.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/667434\/revisions\/667440"}],"wp:attachment":[{"href":"https:\/\/new-cm-edgedigital.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/media?parent=667434"}],"wp:term":[{"taxonomy":"msr-research-highlight","embeddable":true,"href":"https:\/\/new-cm-edgedigital.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-research-highlight?post=667434"},{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/new-cm-edgedigital.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=667434"},{"taxonomy":"msr-publication-type","embeddable":true,"href":"https:\/\/new-cm-edgedigital.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-publication-type?post=667434"},{"taxonomy":"msr-publisher","embeddable":true,"href":"https:\/\/new-cm-edgedigital.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-publisher?post=667434"},{"taxonomy":"msr-focus-area","embeddable":true,"href":"https:\/\/new-cm-edgedigital.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-focus-area?post=667434"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/new-cm-edgedigital.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=667434"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/new-cm-edgedigital.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=667434"},{"taxonomy":"msr-field-of-study","embeddable":true,"href":"https:\/\/new-cm-edgedigital.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-field-of-study?post=667434"},{"taxonomy":"msr-conference","embeddable":true,"href":"https:\/\/new-cm-edgedigital.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-conference?post=667434"},{"taxonomy":"msr-journal","embeddable":true,"href":"https:\/\/new-cm-edgedigital.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-journal?post=667434"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/new-cm-edgedigital.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=667434"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/new-cm-edgedigital.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=667434"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}