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

Channel:
Microsoft Research
Subscribers:
343,000
Published on ● Video Link: https://www.youtube.com/watch?v=_Ayuckh1BpU


Duration: 1:03:30
41 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-22The Once and Future Internet
2016-06-22The First Order World of Galton-Watson Trees
2016-06-22Verasco, a formally verified C static analyzer
2016-06-22Symposium: Deep Learning - Max Jaderberg
2016-06-22Satisfiability of Ordering CSPs Above Average Is Fixed-Parameter Tractable
2016-06-22Symposium: Deep Learning - Harri Valpola
2016-06-22Machine Learning as Creative Tool for Designing Real-Time Expressive Interactions
2016-06-22Symposium: Deep Learning - Sergey Ioffe
2016-06-22Multi-rate neural networks for efficient acoustic modeling
2016-06-22Robust Spectral Inference for Joint Stochastic Matrix Factorization and Topic Modeling
2016-06-22Computational Limits in Statistical Inference: Hidden Cliques and Sum of Squares
2016-06-22Extreme Classification: A New Paradigm for Ranking & Recommendation
2016-06-22A Lasserre-Based (1+epsilon)-Approximation for Makespan Scheduling with Precedence Constraints
2016-06-22Oral Session: Learning Theory and Algorithms for Forecasting Non-stationary Time Series
2016-06-22Recent Developments in Combinatorial Optimization
2016-06-22Invited Talks: Computational Principles for Deep Neuronal Architectures
2016-06-22Coalescence in Branching Trees and Branching Random Walks
2016-06-22Oral Session: Randomized Block Krylov Methods
2016-06-22Oral Session: Fast Convergence of Regularized Learning in Games
2016-06-22Ito Processes, Correlated Sampling and Applications
2016-06-22Statistical and computational trade-offs in estimation of sparse principal components.


Tags:
microsoft research
algorithms