Information Theory, Learning and Big Data (Simons Institute, 2015)
2015-03-16..2015-03-20
Berkeley, United States
[Learning, Algorithm Design and Beyond Worst-Case Analysis, Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013), Algorithmic Advances for Statistical Inference with Combinatorial Structure, Computational Phase Transitions (Simons Institute, 2020), Optimization, Statistics and Uncertainty, Randomized Numerical Linear Algebra and Applications 2018]
| title | author | length |
|---|---|---|
| Low-Rank Matrix Recovery Through Rank-One Projections | Tony Cai | 23m |
Measurements take the form Yi = beta_i^T A gamma_i + noise with Xi = beta_i gamma_i^T, so recovery uses rank-one measurements and a convex constrained… | ||
| Sketching for M-Estimators: A Unified Approach to Robust Regression | David P. Woodruff | 28m |
Presents algorithms that compress an N×D regression to about poly(D) log N rows using sparse sign sketches and diagonal subsampling, then solves the smaller… | ||
| Simple, Efficient and Neural Algorithms for Sparse Coding | Ankur Moitra | 25m |
Proposes a simple online, local, Hebbian algorithm that decodes by multiplying by the current dictionary transpose and hard‑thresholding and then updates via… | ||
| Learning a Hidden Basis through Imperfect Measurements: Why and How | Misha Belkin | 27m |
Algorithm recovers an unknown orthonormal partial basis from evaluations and gradients of F(u)=sum_i g_i(u·e_i) by iterating gradient iteration (replace u by… | ||
| Constrained Rank Aggregation and Correlation Clustering | Olgica Milenkovic | 25m |
Proposes a correlation‑clustering variant that lets negative edge weights be arbitrarily large to enforce mutual exclusivity, adds per‑vertex penalties to… | ||
| Testing Distribution Families | Jayadev Acharya | 21m |
Proposes a two-step method: use a proper learning routine (LP-based for discrete log-concave and specific estimators for Poisson binomial) to get an… | ||
| Fundamental Limit of Community Detection in Stochastic Block Models | Emmanuel Abbe | 25m |
States an exact information-theoretic threshold for exact recovery in stochastic block models with log-degree scaling: recovery occurs iff a Chernoff–Hellinger… | ||
| How Large is the Norm of a Random Matrix? | Ramon van Handel | 23m |
Gives matching upper and lower bounds for the expected spectral norm of an independent-entry Gaussian matrix in terms of two explicit parameters: the… | ||
| Lucky Talk: From Coding to Clustering | Emmanuel Abbe | 25m |
Exact recovery for the stochastic block model is pinned down: with p = a log n / n and q = b log n / n the two-group symmetric case has a sharp solvability… | ||
| Chebyshev Polynomials, Moment Matching and Optimal Estimation of the Unseen | Yihong Wu | 29m |
This work gives an explicit linear estimator on fingerprint counts that uses Chebyshev polynomials (degree about log n) and Poissonization to reduce bias and… | ||
| Information Measure Estimation and Applications: Boosting the Sample Size from n to n log n | Jiantao Jiao | 27m |
Claim: minimax estimators achieve the same error with n samples that the plug-in MLE needs with about n log n samples, an effect called effective sample size… | ||
| Sample Complexity of Estimating Entropy | Himanshu Tyagi | 28m |
Establishes sample complexity for entropy variants: Shannon needs about K / log K samples, Rényi with alpha<1 needs ~K^(1/alpha) (superlinear), noninteger… | ||
| Minimum Rényi Correlation Principle: From Marginals to Joint Distribution | Farzan Farnia | 21m |
Defines a Principle of Minimum Rényi Correlation that picks a joint P agreeing with given first/second marginals by minimizing Rényi maximal correlation… | ||
| Adaptive Coding over Countable Alphabets | Stéphane Boucheron | 26m |
Defines envelope classes for countable alphabets and shows a concrete thresholding/censoring code that uses a data-driven threshold plus a mixture coder on the… | ||
| On Learning Distributions from their Samples | Sudeep Kamath | 29m |
Characterizes minimax risk for several losses with concrete estimators and sharp constants: for relative entropy the first-order minimax term is (k-1)/(2n) and… | ||
| Efficient Minimax Optimal Strategies for Universal Prediction | Peter Bartlett | 29m |
Shows when the minimax-optimal strategy is computable and what it actually is: a dynamic-program recursion yields normalized maximum likelihood as the unique… | ||
| On the Complexity of Best Arm Identification in Multi-Armed Bandit Models | Aurélien Garivier | 27m |
Proves that best-arm identification complexities differ between the fixed-budget and fixed-confidence settings, using a new Pinsker-like change-of-measure… | ||
| Lucky Talk: Chebyshev Polynomials, Moment Matching and Optimal Estimation of the Unseen | Yihong Wu | 21m |
Claims that support-size can be estimated with sublinear samples in K and only polylogarithmic accuracy dependence, using a linear estimator that is a weighted… | ||
| Low Regret Recommendations and Item-Item Collaborative Filtering | Devavrat Shah | 25m |
Shows that a simple item-item collaborative filtering algorithm (nearest-neighbor style with explicit explore/exploit and a never-repeat constraint) gets… | ||
| Topic Modeling Approach for Rank Aggregation | Venkat Saligrama | 31m |
Claims equivalence between pairwise rank aggregation and topic modeling and uses a Mallows mixture model to generate noisy permutations, proving that for… | ||
| Machine Learning from Human Comparative Judgments | Robert Nowak | 33m |
Shows that using UCB with LIL confidence bounds yields a fixed‑confidence best‑item algorithm whose sample cost is roughly sum_i Δ_i^{-2}·log log(Δ_i^{-2}) (no… | ||
| Analytic Pattern Matching: From DNA to Twitter | Wojciech Szpankowski | 26m |
Counts occurrence distributions for patterns in memoryless and Markov texts using combinatorial generating functions built from R, M, U language decompositions… | ||
| Strong Data Processing Inequalities and Estimation with Constraints | John Duchi | 31m |
Claim: a likelihood ratio bound anywhere in a Markov chain forces a strong data processing inequality that contracts mutual information by roughly (e^α−1)^2… | ||
| Strong Data Processing Inequalities: Applications to MCMC and Graphical Models | Maxim Raginsky | 30m |
Defines a pointwise strong data processing inequality (SDPI) for phi‑divergences, proves a general lower bound eta_phi(mu,K) ≥ eta_chi^2(mu,K) (chi^2 SDPI… | ||
| Near-Optimal Hypothesis Testing via Convex Optimization | Arkadi Nemirovski | 28m |
Constructs tests by solving a finite convex optimization that maximizes affinity between two convex parameter sets in an exponential family and yields a… | ||
| Data Driven Convergence in Statistical Estimators | Narayana Santhanam | 28m |
Gives a precise, provable criterion for when a pointwise-consistent estimator can also produce a universal, data-driven stopping rule that reliably signals… | ||
| Lucky Talk: Low-regret Recommendations and Item-item Collaborative Filtering | Guy Bresler | 20m |
Matrix of binary likes, random user per round, bandit feedback and regret defined as average 1 - like; initial recommendations behave like random guessing with… | ||
| Confidence-Based Active Learning | Kamalika Chaudhuri | 25m |
Presents a reduction from agnostic active learning to a confidence-rated predictor with nonzero error guarantee and gives an LP to construct that predictor… | ||
| Constructing Informative Features for Discriminative Learning | Animashree Anandkumar | 28m |
Constructs a pipeline that estimates higher-order score functions from unlabeled X (via autoencoders or score matching), forms cross-moments E[y ⊗ score_k(X)]… | ||
| Robust Inference and Local Algorithms | Yishay Mansour | 24m |
Yishay Mansour, Tel Aviv University
Information Theory, Learning and Big Data
http://simons.berkeley.edu/talks/yishay-mansour-2015-03-19 | ||
| Tradeoffs in Large Scale Learning: Statistical Accuracy vs. Numerical Precision | Sham Kakade | 33m |
Claims an algorithm based on variance-reduced gradient ideas drives the excess risk to the empirical-risk-minimizer rate sigma^2/n while using one-pass… | ||
| Computation-Statistics Tradeoffs in Unsupervised Learning via Data Summarization | Mesrob Ohannessian | 33m |
Shows that summarizing data with coresets gives a provable computation–risk trade-off for k‑means: randomized importance sampling constructions replace n… | ||
| Statistical Property Testing and Estimation Beyond the i.i.d. Setting | Gregory Valiant | 30m |
Provides a tight, instance-optimal sample complexity for identity testing to a known distribution p: samples = Theta(max(1/epsilon, ||p after trimming epsilon… | ||
| Nearest Neighbor Based Greedy Coordinate Descent | Pradeep Ravikumar | 31m |
Shows that greedy coordinate selection reduces to a nearest neighbor query on the residual, so using approximate nearest neighbor data structures (LSH or… | ||
| Learning and Testing Structured Distributions | Ilias Diakonikolas | 33m |
Ilias Diakonikolas, University of Edinburgh
Information Theory, Learning and Big Data
http://simons.berkeley.edu/talks/ilias-diakonikolas-2015-03-19 | ||
| Approximating Spherical Gaussian Mixtures | Ananda Suresh | 29m |
Proves an algorithmic pipeline that learns mixtures of spherical Gaussians with no separability or weight assumptions and near–optimal sample scaling: previous… | ||
| Lucky Talk: An Algorithmic Characterization of a Class of Inequalities | Gregory Valiant | 23m |
Main theorem: given finite sequences a_i, b_i, c_i the multiplicative inequality over all positive x_j,y_j holds exactly when the target expression decomposes… | ||
| Detection and Estimation through an Information Theory Lens | Sergio Verdú | 27m |
States that detection and estimation bounds are expressed in information terms: uses the relative information spectrum and tilted distribution p_alpha to get… | ||
| Testing Probability Distributions using Conditional Samples | Rocco A. Servedio | 29m |
Introduces a conditional-sampling model where an algorithm queries a subset and receives a sample conditioned on that subset, and shows concrete gains… | ||
| Sample Starved Correlation Mining | Al Hero | 28m |
Claims that in the sample-starved regime (n fixed, p → ∞) a universal critical correlation rho_c governs when false positives explode, and that raising the… | ||
| Fast Approximations of the Pattern Maximum Likelihood Estimate | Pascal Vontobel | 25m |
Defines the pattern maximum likelihood (PML) as the p that maximizes a permanent over a matrix parameterized by p and shows practical surrogates: a Bethe… | ||
| Spy vs Spy: Anonymous Messaging | Pramod Viswanath | 26m |
Claim: replacing random diffusion with a sampled-control spreading rule yields dramatically better source hiding. Using an adaptive diffusion protocol inspired… | ||
| Learning Sparse Data with Near-optimal Speed and Efficiency from a Variety of Measurement Processes | Sidharth Jaggi | 26m |
This framework unifies compressed sensing, network tomography, phase retrieval and group testing and claims near‑optimal sample complexity (order k… | ||
| Must One Learn the Channel to Communicate at Capacity? | Aaron Wagner | 32m |
Asks how large input/output alphabets can grow with blocklength n before universal codes that don’t know the channel stop achieving capacity. Proves a… | ||
| nothing matches | ||