Learning Algorithm Design and Beyond Worst-Case Analysis

# click the upper-left icon to select videos from the playlist

source: Simons Institute    2016年11月14日
Learning Algorithm Design and Beyond Worst-Case Analysis
This workshop will explore well-motivated non-worst-case approaches to the analysis of algorithms and problems, as well as to the development of techniques that can take advantage of underlying structure in instances. It will bring together researchers from algorithms, learning theory, and AI, as well as application areas including SAT, formal verification, and sustainability. The themes of the workshop include: (i) learning commonalities of past instances to get an advantage in dealing with future instances; (ii) extracting features of different problem instances to learn which algorithmic approach to use; and (iii) finding natural assumptions, as in semi-random and smoothed-analysis models, which may allow for more efficient algorithms or tighter guarantees.
For more information, please visit https://simons.berkeley.edu/workshops/uncertainty2016-2
These presentations were supported in part by an award from the Simons Foundation.

A Brief Intro to Analysis Beyond the Worst Case 40:42 Avrim Blum, Carnegie Mellon University https://simons.berkeley.edu/talks/avr...
Learning Probabilistic Models for Graph Partitioning in the Presence of Noise 46:41
Clustering Under Perturbation Resilience 40:17
On the Effect of Randomness on Planted 3-Coloring Models 41:30
Analyzing Algorithms on Real World Data 41:07
Applied Mixed Integer Programming: Beyond 'The Optimum' 42:27
Distribution-Specific Analysis of Nearest Neighbor Search and Classification 42:18
Spectral Approaches to Nearest Neighbor Search 43:23
Timing Matters: Online Dynamics in Broadcast Games 45:32
A Theoretical Approach to Semantic Coding and Hashing 43:38
Automatic Resource Bound Analysis and Linear Optimization 48:13
Self-Improving Algorithms for Sorting and Geometric Problems 43:07
A PAC Approach to Application-Specific Algorithm Selection 39:05
Beyond Big-O: Statistical Analysis of Performance Scaling 52:18
Learning the Best Agorithm for Max-Cut, Clustering, and Other​ ​Partitioning Problems 32:37
Learning as a Tool for Algorithm Design and Beyond-Worst-Case Analysis 51:35
The Computational Benefit of Correlated Instances 59:48
Recovery Guarantee of Non-Negative Matrix Factorization via Alternating Updates 43:00
Characterizing the Typical Case Complexity of Formal Verification and Synthesis 50:40
Beyond Worst Case: When Complex Feedback Can Improve the Label Complexity of Active Learning 43:12
Follow the Leader with Dropout Perturbations 45:16
When Does Clustering Become Easy, and Should We Care About Other Cases? 52:50
Sketching and Randomization for Distributed Submodular and Coverage Optimization 39:18
Automated Scientific Discovery Using Insights from Problem Structure 43:59
How Hard Is Inference for Structured Prediction? 47:36
Monotone Estimation Framework and its Applications for Scalable Analytics of Large Data Sets 39:38
Above Average-Case Analysis? 39:13
When Existing Techniques in Linear Regression Preserve Differential Privacy 31:18
The Power of Predictions in Online Optimization 41:57