Big Data: The Computation/Statistics Interface

on YouTube ↗01h 31m

" summary

Argues that progress requires marrying computational ideas with statistical decision theory and gives concrete tools and numbers: convex relaxation hierarchies trade off runtime vs. sample size via a geometric quantity called Gaussian squared complexity (examples show complexity scaling like P^1/2 or P^1/4 across cuts, matchings and planted‑clique relaxations). Implements a cloud‑friendly estimator, the Bag of Little Bootstraps (BLB), which parallelizes resampling, cuts I/O for a quarter‑terabyte logistic regression and matches bootstrap accuracy while running orders of magnitude faster and retaining higher‑order correctness (O(1/n)).

AI-written summary · about

" chapters (12)

1. 0:00Start
2. 3:31What is the Big Data Phenomenon?
3. 6:36What is the Big Data Problem?
4. 15:21Example of an Ultimate Goal
5. 17:39Statistical Decision Theory 101
6. 45:32Frequentist Perspective
7. 48:50Computation/Statistics Tradeoffs
8. 50:50Time-Data Tradeoffs
9. 52:51An Estimation Problem
10. 53:56Convex Programming Estimator
11. 55:20Statistical Performance of Estimator
12. 58:30Hierarchy of Convex Relaxations

" related talks

• 43mComputational and Statistical Tradeoffs via Convex RelaxationVenkat Chandrasekaran · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 01h 04mStatistical Physics and Computation in High DimensionFlorent Krzakala, Lenka Zdeborova · Probability, Geometry, and Computation in High Dimensions Boot Camp (Simons Institute, Fall 2020)
• 01h 07mA Few Simple Average-Case Reduction Techniques And Their Surprising EffectivenessGuy Bresler · Rigorous Evidence for Information-Computation Trade-offs
• 38mRole of Statistics in the era of Big DataRajeeva Karandikar · SkillUp 2021
• 01h 04m"More is Different." Also in Computing?Marc Mézard · Symposium on Visions of the Theory of Computing 2013
• 01h 12mPedagogical Talk: Frameworks for Information-Computation TradeoffsTselil Schramm · Computational Phase Transitions (Simons Institute, 2020)
• 48mComputational-Statistical Tradeoffs in Robust High-Dimensional EstimationIlias Diakonikolas · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 01h 11mStatistical Physics and Computation in High DimensionFlorent Krzakala, Lenka Zdeborova · Probability, Geometry, and Computation in High Dimensions Boot Camp (Simons Institute, Fall 2020)