Learning, Algorithm Design and Beyond Worst-Case Analysis
2016-11-14..2016-11-18
Berkeley, United States
[Information Theory, Learning and Big Data (Simons Institute, 2015), Quantifying Uncertainty: Stochastic, Adversarial, and Beyond, Optimization, Statistics and Uncertainty, Uncertainty in Computation 2016, Randomized Numerical Linear Algebra and Applications 2018, Optimization and Decision-Making Under Uncertainty (Simons Institute, September 2016)]
who it's for
algorithm designers, machine learning researchers, theoretical computer scientists, data scientists, optimization practitioners, software engineers working on algorithms
topics
smoothed analysis of simplex; semidefinite relaxations for community recovery; perturbation-resilient clustering; nearest neighbor search analysis; self-improving algorithms for sorting; PAC learning for algorithm selection; applied mixed integer programming; sketching for submodular optimization; differential privacy in linear regression; nonnegative matrix factorization recovery; power of predictions in online optimization
| title | author | length |
|---|---|---|
| A Brief Intro to Analysis Beyond the Worst Case | Avrim Blum | 41m |
Survey of concrete beyond-worst-case claims and tools across decades: semi-random graph model where random flips at noise rate P ≈ 1/√n let SDPs recover… | ||
| Learning Probabilistic Models for Graph Partitioning in the Presence of Noise | Aravindan Vijayaraghavan | 47m |
Semidefinite relaxations plus a simple greedy clustering on the SDP vectors give provable guarantees: a constant‑factor approximation for minimum balanced cut… | ||
| Clustering Under Perturbation Resilience | Colin White | 40m |
Shows polynomial-time exact algorithms for symmetric and asymmetric k‑center assuming 2-perturbation resilience, and proves no algorithm below 2 unless NP=RP… | ||
| On the Effect of Randomness on Planted 3-Coloring Models | Uriel Feige | 42m |
Framework plants a 3‑coloring P inside a host H, removes monochromatic edges, and asks for a legal 3‑coloring of the resulting G. Main positive claim: running… | ||
| Analyzing Algorithms on Real World Data | Cliff Stein | 41m |
Work on Google traces builds a replay simulator from checkpoint files, tests 11 algorithms on CPU/RAM/disk multi‑dimensional packing, and shows that naive… | ||
| Applied Mixed Integer Programming: Beyond 'The Optimum' | Pawel Lichocki | 42m |
Practical claim: mixed integer programming lets engineers express complex product rules quickly and change them incrementally — a multi‑dimensional bin‑packing… | ||
| Distribution-Specific Analysis of Nearest Neighbor Search and Classification | Sanjoy Dasgupta | 42m |
Compares algorithmic and statistical behavior of nearest neighbor with concrete bounds: shows KD-style spill forest and random-projection trees have failure… | ||
| Spectral Approaches to Nearest Neighbor Search | Robert Krauthgamer | 43m |
Claims that when data equals a hidden k-dimensional subspace plus independent Gaussian noise of magnitude σ ≈ d^{-1/4}, the exact nearest neighbor remains… | ||
| Timing Matters: Online Dynamics in Broadcast Games | Shuchi Chawla | 46m |
Broadcast broadcast-game with Shapley cost sharing can hit worst-case Nash gaps of Θ(n) but best equilibria are constant-factor. This work shows arbitrary… | ||
| A Theoretical Approach to Semantic Coding and Hashing | Sanjeev Arora | 44m |
Proposes a log‑linear generative model where a latent discourse vector does a random walk on the sphere, words have vectors VW, and under spatial isotropy the… | ||
| Automatic Resource Bound Analysis and Linear Optimization | Jan Hoffmann | 48m |
Automatic system generates symbolic worst‑case resource bounds by encoding type‑based potential annotations into linear constraints and solving them with LP… | ||
| Self-Improving Algorithms for Sorting and Geometric Problems | Ken Clarkson | 43m |
Comparison based algorithms learn a product distribution (each Xi independent) and build per-input entropy-optimal search trees plus a small “typical set” V… | ||
| A PAC Approach to Application-Specific Algorithm Selection | Rishi Gupta | 39m |
Proposes a PAC-style solution to pick algorithms from parametric families (e.g. greedy independent‑set rules weight/(deg+1)^rho) and gives two concrete models… | ||
| Beyond Big-O: Statistical Analysis of Performance Scaling | Holger H. Hoos | 52m |
Empirical analysis fits explicit scaling models, uses bootstrap confidence intervals on median runtimes, and finds per-size runtimes are roughly log-normal… | ||
| Learning the Best Agorithm for Max-Cut, Clustering, and Other Partitioning Problems | Vaishnavh Nagarajan | 33m |
Proves that two natural algorithm families—agglomerative alpha-linkage clusterings and Feige–Langberg S‑linear SDP roundings for MaxCut—have sample complexity… | ||
| Learning as a Tool for Algorithm Design and Beyond-Worst-Case Analysis | Kevin Leyton-Brown | 52m |
Shows that a learned empirical hardness model (features → runtime) predicts run time of black‑box SAT and MIP solvers with RMS error often <1 (i.e., better… | ||
| The Computational Benefit of Correlated Instances | Shafi Goldwasser | 01h 00m |
Two theoretical papers claim concrete speedups when many instances share structure: for Boolean constraint‑satisfaction, order log n auxiliary instances… | ||
| Recovery Guarantee of Non-Negative Matrix Factorization via Alternating Updates | Yingyu Liang | 43m |
Alternate-update NMF uses pseudo-inverse + ReLU decoding (decode x = ReLU(A†y − α)) then update A by the empirical expectation of (y y') (x x')^T using fresh… | ||
| Characterizing the Typical Case Complexity of Formal Verification and Synthesis | Sanjit A. Seshia | 51m |
Three research threads: graph-based SAT structure, SMT encodings, and invariant synthesis. Shows that common modularity metrics can be embedded to make SAT… | ||
| Beyond Worst Case: When Complex Feedback Can Improve the Label Complexity of Active Learning | Kamalika Chaudhuri | 43m |
Combines a cheap but biased weak labeler and an expensive correct oracle by training a cost-sensitive difference classifier that enforces very low false… | ||
| Follow the Leader with Dropout Perturbations | Manfred Warmuth | 45m |
Claims a concrete result for the expert/hedge setting: in the single-neuron linear-loss case applying multiplicative dropout (zeroing components with p=1/2)… | ||
| When Does Clustering Become Easy, and Should We Care About Other Cases? | Shai Ben-David | 53m |
Survey argues that many formal “clusterable” definitions let algorithms run fast but only under unrealistically strong gaps (e.g. epsilon-separateness ≈ 200×… | ||
| Sketching and Randomization for Distributed Submodular and Coverage Optimization | Vahab Mirrokni | 39m |
Randomized composable coresets plus sketching produce practical two‑round MapReduce and streaming algorithms for large coverage and submodular problems. Key… | ||
| Automated Scientific Discovery Using Insights from Problem Structure | Bart Selman | 44m |
Shows how a plain SAT solver plus unit propagation and clause learning finds a machine proof of the Erdős discrepancy case (the 1161 bound and a 1160 witness)… | ||
| How Hard Is Inference for Structured Prediction? | Tim Roughgarden | 48m |
Asks whether recovering binary vertex labels from noisy edge parity is possible and when; proves the simple minimize-disagreements (correlation‑clustering)… | ||
| Monotone Estimation Framework and its Applications for Scalable Analytics of Large Data Sets | Edith Cohen | 40m |
Defines a monotone sampling with seed u model where each sample reveals a set of consistent data vectors and estimators must be unbiased, nonnegative and… | ||
| Above Average-Case Analysis? | Ankur Moitra | 39m |
Claims a polynomial-time procedure that, under an adversary who corrupts an ε fraction of samples (or distributions ε-close in total variation), recovers mean… | ||
| When Existing Techniques in Linear Regression Preserve Differential Privacy | Or Sheffet | 31m |
Shows that standard regressors already give differential privacy if applied to the second-moment matrix with the right randomness and scale. Releasing the… | ||
| The Power of Predictions in Online Optimization | Adam Wierman | 42m |
Predictive noise is modeled as a filter-like noise model (impulse weights times IID shocks), letting adversarial instances coexist with stochastic prediction… | ||
| nothing matches | ||