{"id":4791,"date":"2015-07-20T09:00:16","date_gmt":"2015-07-20T16:00:16","guid":{"rendered":"https:\/\/blogs.msdn.microsoft.com\/msr_er\/?p=4791"},"modified":"2016-07-20T07:29:04","modified_gmt":"2016-07-20T14:29:04","slug":"icml-2015-best-paper-summary-a-nearly-linear-time-framework-for-graph-structured-sparsity","status":"publish","type":"post","link":"https:\/\/www.microsoft.com\/en-us\/research\/blog\/icml-2015-best-paper-summary-a-nearly-linear-time-framework-for-graph-structured-sparsity\/","title":{"rendered":"ICML 2015 best paper summary: A nearly-linear time framework for graph-structured sparsity"},"content":{"rendered":"<p>A novel method of structuring the largest and most complex datasets\u2014from social networks to global financial markets\u2014has won a Best Paper award at the world\u2019s leading academic conference on machine learning.<\/p>\n<p>In the paper, <em><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" rel=\"noopener noreferrer\" href=\"http:\/\/jmlr.org\/proceedings\/papers\/v37\/hegde15.pdf\" target=\"_blank\">A Nearly-Linear Time Framework for Graph-Structured Sparsity<span class=\"sr-only\"> (opens in new tab)<\/span><\/a><\/em>, by Chinmay Hegde, Piotr Indyk, and Ludwig Schmidt, recently delivered to <a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" rel=\"noopener noreferrer\" href=\"http:\/\/icml.cc\/2015\/\" target=\"_blank\">International Conference on Machine Learning (ICML), <span class=\"sr-only\"> (opens in new tab)<\/span><\/a>the researchers from MIT explain their use of 3-D graphs to meet the challenges of high dimensional datasets.<\/p>\n<p>Performance tests of the algorithm \u201cGraph-CoSaMP\u201d tasked with \u201crecovering 2-D data with clustered sparsity\u201d showed massive improvements over earlier methods, according to the study from MIT\u2019s Computer Science and Artificial Intelligence Laboratory (CSAIL).<\/p>\n<p>\u201cOur algorithm is about 20 times faster than StructOMP, the other method with provable guarantees for the image cluster model,\u201d the study states.<\/p>\n<p>The authors point to three main features underlying the success of the new framework centered on a \u201cWeighted Graph Model\u201d (WGM).<\/p>\n<ul>\n<li>Builds on previously studied sparsity models.<\/li>\n<li>Statistical efficiency. Reduces sample complexity in sparse recovery, achieving an \u201cinformation-theoretic optimum for a wide range of parameters.\u201d<\/li>\n<li>Computational efficiency. Uses a nearly linear time algorithm, a genuine breakthrough that significantly improves on all earlier work \u2013 \u201cboth in theory and practice.\u201d<\/li>\n<\/ul>\n<p>The study pointed to two specific applications that could benefit from the WGM algorithms: Seismic feature extraction and event detection in social networks.<\/p>\n<p>A total of <a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" rel=\"noopener noreferrer\" href=\"http:\/\/jmlr.org\/proceedings\/papers\/v37\/#default\" target=\"_blank\">270 papers were accepted<span class=\"sr-only\"> (opens in new tab)<\/span><\/a> at the ICML conference, July 6-11, 2015 in Lille, France.<\/p>\n<p>\u2014John Kaiser, Research News<\/p>\n<p>For more computer science research news, visit <a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" rel=\"noopener noreferrer\" href=\"http:\/\/www.researchnews.com\/\" target=\"_blank\">ResearchNews.com<span class=\"sr-only\"> (opens in new tab)<\/span><\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>A novel method of structuring the largest and most complex datasets\u2014from social networks to global financial markets\u2014has won a Best Paper award at the world\u2019s leading academic conference on machine learning. In the paper, A Nearly-Linear Time Framework for Graph-Structured Sparsity, by Chinmay Hegde, Piotr Indyk, and Ludwig Schmidt, recently delivered to International Conference on [&hellip;]<\/p>\n","protected":false},"author":32627,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","msr-author-ordering":[],"msr_hide_image_in_river":0,"footnotes":""},"categories":[194466,194455,194459],"tags":[195863,195955,196519],"research-area":[],"msr-region":[],"msr-event-type":[],"msr-locale":[268875],"msr-post-option":[],"msr-impact-theme":[],"msr-promo-type":[],"msr-podcast-series":[],"class_list":["post-4791","post","type-post","status-publish","format-standard","hentry","category-algorithms","category-machine-learning","category-researchnews","tag-icml-2015","tag-international-conference-on-machine-learning-icml","tag-mit","msr-locale-en_us"],"msr_event_details":{"start":"","end":"","location":""},"podcast_url":"","podcast_episode":"","msr_research_lab":[],"msr_impact_theme":[],"related-publications":[],"related-downloads":[],"related-videos":[],"related-academic-programs":[],"related-groups":[],"related-projects":[],"related-events":[],"related-researchers":[],"msr_type":"Post","byline":"","formattedDate":"July 20, 2015","formattedExcerpt":"A novel method of structuring the largest and most complex datasets\u2014from social networks to global financial markets\u2014has won a Best Paper award at the world\u2019s leading academic conference on machine learning. In the paper, A Nearly-Linear Time Framework for Graph-Structured Sparsity, by Chinmay Hegde, Piotr&hellip;","locale":{"slug":"en_us","name":"English","native":"","english":"English"},"_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/posts\/4791","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/users\/32627"}],"replies":[{"embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/comments?post=4791"}],"version-history":[{"count":1,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/posts\/4791\/revisions"}],"predecessor-version":[{"id":260718,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/posts\/4791\/revisions\/260718"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=4791"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/categories?post=4791"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/tags?post=4791"},{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=4791"},{"taxonomy":"msr-region","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-region?post=4791"},{"taxonomy":"msr-event-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-event-type?post=4791"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=4791"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=4791"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=4791"},{"taxonomy":"msr-promo-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-promo-type?post=4791"},{"taxonomy":"msr-podcast-series","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-podcast-series?post=4791"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}