Stochastic Control via Entropy Compression

on YouTube ↗42m

" summary

Introduces a flows-action framework that turns Moser’s local-resampling into a general stochastic-control algorithm, proves a cutoff-style convergence when every flaw satisfies amenability = local entropy − congestion (amenability k in k-CNF so 2−k appears), and handles adversarial noise by a noise model with adversary probability p whose extra burden is a weighted sum of 2−amenability terms. Gives a concrete criterion to compute tolerance (recovers near-LLL bounds, linear-time finding under those conditions) and uses entropy compression for sequences to bound failure probability.

AI-written summary · about

" chapters (10)

1. 0:00Introduction to stochastic
2. 1:03The Lovasz local lemma
3. 4:24Satisfiability applications
4. 6:06Moser's algorithm
5. 8:33Flows and actions framework
6. 12:33Entropy and congestion
7. 17:34Amenability and causality
8. 21:33Convergence theorem
9. 25:31Noise and robust control
10. 32:24Entropy compression theory

" related talks

• 59mCompositional Properties of Statistical Procedures: An Information-Theoretic ViewMax Raginsky · Optimization, Statistics and Uncertainty
• 38mAn Information Theoretic View of HypercontractivityEhud Friedgut · Information Theory in Complexity Theory and Combinatorics 2015
• 29mA Pre-Expectation Calculus for Probabilistic SensitivityJustin Hsu, Alejandro Aguirre, Gilles Barthe, Joost-Pieter Katoen, Benjamin Lucien Kaminski, Christoph Matheja · POPL 2021
• 01h 01mRobustness, Stochastics, Uncertainty 1Sasha Rakhlin, Ben Recht, Laurent El Ghaoui · Bridging Continuous and Discrete Optimization Boot Camp 2017
• 33mA Few Connections Between Optimization and ProbabilitySasha Rakhlin · Optimization, Statistics and Uncertainty
• 01h 03mSampling Crash CourseAndreas Eberle · Geometric Methods in Optimization and Sampling Boot Camp
• 34mThe Non-Stochastic Control FrameworkNaman Agarwal · Mathematics of Online Decision Making 2020
• 28mData Driven Convergence in Statistical EstimatorsNarayana Santhanam · Information Theory, Learning and Big Data (Simons Institute, 2015)