A novel method of structuring the largest and most complex datasets—from social networks to global financial markets—has won a Best Paper award at the world’s leading academic conference on machine learning.
In the paper, A Nearly-Linear Time Framework for Graph-Structured Sparsity (opens in new tab), by Chinmay Hegde, Piotr Indyk, and Ludwig Schmidt, recently delivered to International Conference on Machine Learning (ICML), (opens in new tab)the researchers from MIT explain their use of 3-D graphs to meet the challenges of high dimensional datasets.
Performance tests of the algorithm “Graph-CoSaMP” tasked with “recovering 2-D data with clustered sparsity” showed massive improvements over earlier methods, according to the study from MIT’s Computer Science and Artificial Intelligence Laboratory (CSAIL).
Microsoft Research Podcast
AI Frontiers: Models and Systems with Ece Kamar
Ece Kamar explores short-term mitigation techniques to make these models viable components of the AI systems that give them purpose and shares the long-term research questions that will help maximize their value.
“Our algorithm is about 20 times faster than StructOMP, the other method with provable guarantees for the image cluster model,” the study states.
The authors point to three main features underlying the success of the new framework centered on a “Weighted Graph Model” (WGM).
- Builds on previously studied sparsity models.
- Statistical efficiency. Reduces sample complexity in sparse recovery, achieving an “information-theoretic optimum for a wide range of parameters.”
- Computational efficiency. Uses a nearly linear time algorithm, a genuine breakthrough that significantly improves on all earlier work – “both in theory and practice.”
The study pointed to two specific applications that could benefit from the WGM algorithms: Seismic feature extraction and event detection in social networks.
A total of 270 papers were accepted (opens in new tab) at the ICML conference, July 6-11, 2015 in Lille, France.
—John Kaiser, Research News
For more computer science research news, visit ResearchNews.com (opens in new tab).