Computational Limits in Statistical Inference: Hidden Cliques and Sum of Squares

Channel:
Microsoft Research
Subscribers:
344,000
Published on ● Video Link: https://www.youtube.com/watch?v=Bkm-HECa4qw


Duration: 1:03:30
254 views
2

Characterizing the computational complexity of statistical inference problems is an outstanding open problem. This is gaining increasing importance given the ubiquity of large scale data analysis and algorithms in application domains as diverse as genomics, healthcare, finance and social sciences. The hidden clique problem is a prototypical example of an inference problem wherein computational constraints dramatically alter the inference ability. The hidden clique problem posits to find a "hidden" or "planted" clique (a densely connected set of vertices) within an otherwise random Erdos-Renyi graph. Unfortunately, standard reduction tools from theoretical computer science to demonstrate hardness fail to capture statistical nature of the hidden clique problem. I will describe a framework based on the powerful Sum-of-Squares (SOS) technique for characterizing computational difficulty in the hidden clique and other related problems. The analysis of the SOS algorithms requires controlling the spectra of random matrices of a non-standard type. I will describe a set of results that represent the state-of-the-art in proving lower bounds for the hidden clique and related problems.



Other Videos By Microsoft Research


2016-06-13Future Microprocessors Driven by Dataflow Principles
2016-06-13Theory and Experiments on the Spontaneous Evolution of Culture
2016-06-13Single-shot error correction with the gauge color code
2016-06-13Robust Spectral Inference for Joint Stochastic Matrix Factorization and Topic Modeling
2016-06-13How Much Information Does a Human Translator Add to the Original and Multi-Source Neural Translation
2016-06-13Opportunities and Challenges in Global Network Cameras
2016-06-13Nature in the City: Changes in Bangalore over Time and Space
2016-06-13Making Small Spaces Feel Large: Practical Illusions in Virtual Reality
2016-06-13Machine Learning as Creative Tool for Designing Real-Time Expressive Interactions
2016-06-13Recent Developments in Combinatorial Optimization
2016-06-13Computational Limits in Statistical Inference: Hidden Cliques and Sum of Squares
2016-06-13Coloring the Universe: An Insider's Look at Making Spectacular Images of Space
2016-06-13Towards Understandable Neural Networks for High Level AI Tasks - Part 6
2016-06-13The 37th UW/MS Symposium in Computational Linguistics
2016-06-13The Linear Algebraic Structure of Word Meanings
2016-06-13Machine Learning Algorithms Workshop
2016-06-13Interactive and Interpretable Machine Learning Models for Human Machine Collaboration
2016-06-13Improving Access to Clinical Data Locked in Narrative Reports: An Informatics Approach
2016-06-13Representation Power of Neural Networks
2016-06-13Green Security Games
2016-06-13e-NABLE: A Global Network of Digital Humanitarians on an Infrastructure of Electronic Communications


Tags:
microsoft research
data visualization
analytics and platform
erdos-renyi graph
statistical inference