Algorithmic Advances for Statistical Inference with Combinatorial Structure
2021-10-11..2021-10-15
-- online --
[Information Theory, Learning and Big Data (Simons Institute, 2015), Random Instances and Phase Transitions (Simons Institute, 2016), Computational Phase Transitions (Simons Institute, 2020), Randomized Numerical Linear Algebra and Applications 2018, Algorithmic Aspects of Causal Inference 2022, Learning, Algorithm Design and Beyond Worst-Case Analysis]
who it's for
statistical researchers, machine learning researchers, theoretical computer scientists, graph algorithms researchers, optimization researchers, privacy and robust-statistics researchers, signal and inverse-problem researchers
topics
random combinatorial matrices; correlated stochastic block models; graph matching and alignment; causal observation matrix estimation; differential privacy with robustness; phase synchronization estimation; approximate message passing for orthogonally invariant models; symmetric binary perceptron structure; metric repair and metric polytope methods; learning minimax estimators via online learning; tensor graphical models; deep generative models for inverse problems
| title | author | length |
|---|---|---|
| Random Combinatorial Matrices | Amin Coja-Oghlan | 50m |
Proves that sparse random F2 matrices (Bernoulli model) are replica symmetric but not strongly: for density D>e the posterior overlap concentrates but randomly… | ||
| Correlated Stochastic Block Models: Graph Matching And Community Recovery | Miklos Racz | 45m |
Model uses P = A log N / N and Q = B log N / N and generates two subsampled, permuted copies; exact graph matching is feasible down to the… | ||
| Tractability And Overparametrization In Some Simple Models | Andrea Montanari | 45m |
Proves precise large-|kappa| asymptotics for when negative‑margin linear classifiers exist versus when they’re findable: the satisfiability threshold δ_S… | ||
| Causal Matrix Estimation | Devavrat Shah | 52m |
Estimates a low‑rank matrix A when the observation mask D depends on latent row/column factors (a causal observation mask that can confound sampling but not… | ||
| Differential Privacy Meets Robust Statistics | Sewoong Oh | 43m |
An efficient algorithm that provably combines robustness to an α fraction of poisoned samples and (ε,δ)-differential privacy is presented, cutting iterative… | ||
| Exact Minimax Estimation for Phase Synchronization | Chao Gao | 48m |
Proves the minimax risk equals sigma^2/(n p), derives a matching lower bound and shows MLE, generalized power method (GPM) with eigenvector initialization, and… | ||
| Statistical Estimation from Dependent Data | Constantinos Daskalakis | 53m |
Model sets labels Y as an Ising with feature-dependent external fields: each node’s external field equals f_theta(x_i) and labels have network coupling beta·A… | ||
| A Curious Case Of Symmetric Binary Perceptron Model: Algorithms And Barriers | David Gamarnik | 54m |
Random symmetric binary perceptron uses an M×N random (Gaussian or Rademacher) matrix and seeks σ∈{±1}^N with Aσ/√N entrywise in [−κ,κ]. Existence has a sharp… | ||
| Metric Representations: Algorithms and Geometry | Anna Gilbert | 49m |
Shows that corrupted pairwise distances (e.g., 5% bad edges wrecking an Isomap embedding) are repairable by optimizing over the metric polytope; introduces… | ||
| Approximate Message Passing Algorithms For Orthogonally Invariant Models | Zhou Fan | 49m |
Approximate Message Passing extends to W with Haar eigenvectors and arbitrary spectral law by replacing the usual Onsager terms with coefficients given by the… | ||
| Learning Minimax Estimators Via Online Learning | Pradeep Ravikumar | 55m |
Proposes solving the minimax estimation problem by reducing the zero‑sum game to an online learning loop that alternates a Bayes estimator best response with… | ||
| New Algorithms For The Graph Alignment Problem | Marc Lelarge | 52m |
Defines a correlated Erdos-Renyi model and reduces matching to local hypothesis tests on Galton-Watson neighborhoods, computing a local likelihood-ratio… | ||
| Structures Of Local Minima In K-Means And Mixture Models | Yudong Chen | 51m |
For two-component mixtures the population negative log-likelihood has exactly five stationary points and the only local minima correspond to the true centers… | ||
| Tensor Graphical Models For Complex And High Dimensional Data | Shuheng Zhou | 01h 00m |
Claims that one can jointly estimate high‑dimensional means and row/column covariances in matrix‑normal/tensor data with provable rates, often matching… | ||
| Uncertainty Quantification In The Bradley-Terry-Luce Model | Anderson Ye Zhang | 59m |
Provides non-asymptotic expansion formulas for both MLE and spectral estimators under the Bradley–Terry–Luce model, with the leading error term an average of… | ||
| Deep Generative Models And Unsupervised Methods For Inverse Problems | Alex Dimakis | 52m |
Pretrained deep generators serve as differentiable priors to solve ill‑posed inverse problems by optimizing the latent code to match measurements: the CSGM… | ||
| Exact Matching Of Random Graphs With Constant Correlation | Cheng Mao | 54m |
Provides a polynomial-time algorithm that achieves exact recovery of the latent permutation for two correlated Erdős–Rényi graphs when average degree is… | ||
| Estimation Beyond the IID Setting (Two Vignettes) | Gregory Valiant | 01h 02m |
Two vignettes show concrete claims and tools: the worst‑case squared‑error estimator for a coin with one flip predicts quarter/three-quarters rule and for k… | ||
| nothing matches | ||