Foundations of Data Science Boot Camp 2018
2018-08-27..2018-08-31
Berkeley, United States
[Foundations of Machine Learning Boot Camp 2017, Probability, Geometry, and Computation in High Dimensions Boot Camp (Simons Institute, Fall 2020), Randomized Numerical Linear Algebra and Applications 2018, Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013), Geometric Methods in Optimization and Sampling Boot Camp, Data Privacy: Foundations and Applications Boot Camp]
who it's for
research scientists, machine learning researchers, applied statisticians, algorithm engineers, data scientists, optimization engineers
topics
Johnson-Lindenstrauss via Gaussians; CountSketch subspace embeddings; randomized Hadamard / SRHT transforms; leverage score estimation via sketching; SVD best-fit subspace for clustering; row/column sampling and CUR low-rank approximation; subsampled Newton and Hessian sketching; stochastic second-order methods and quasi-Newton; importance sampling for SGD and adaptive rates; finite-moment methods and Gaussian annulus; variance-reduced methods (SVRG-style); high-dimensional robust statistics
| title | author | length |
|---|---|---|
| Intro and Foundations of Data Science I | David P. Woodruff, Ravi Kannan | 58m |
A compact course first promotes a finite-moment method that replaces exponential moment proofs with Rth moments and an R! bound to get Gaussian-like moment… | ||
| Foundations of Data Science II | Ravi Kannan | 55m |
Claims that SVD identifies the k-dimensional subspace spanned by Gaussian means, yielding a polynomial-time algorithm to learn K spherical Gaussians with… | ||
| Sketching for Linear Algebra: Basics of Dimensionality Reduction and CountSketch I | David P. Woodruff | 59m |
Shows that CountSketch matrices (hash rows, random ±1 signs) give a subspace embedding for regression with one non-zero per column and k = Θ(d^2/ε^2) rows, so… | ||
| Sketching for Linear Algebra: Basics of Dimensionality Reduction and CountSketch II | David P. Woodruff | 01h 10m |
Shows that CountSketch JL moment (L=2) gives an unbiased subspace embedding with variance O(1/K) and needs about K = 2/(ε^2 δ) rows to get the desired moment… | ||
| Sketching for Linear Algebra III: Randomized Hadamard, Kernel Methods | Ken Clarkson | 01h 04m |
Describes how to compute leverage scores via sketching by forming S A, QR on the sketch, forming R^{-1}, multiplying by a short JL matrix pi of size M' = O(log… | ||
| First-Order Stochastic Optimization | Rachel Ward | 58m |
Proves that under smooth, (strongly) convex finite-sum assumptions SGD with a constant step size < 1/L converges exponentially to a neighborhood whose radius… | ||
| Sampling for Linear Algebra, Statistics, and Optimization I | Michael Mahoney | 01h 03m |
Randomized linear‑algebra sketches replace large matrices by sampled rows/columns or random projections (Hadamard, Gaussian, CountSketch) so downstream… | ||
| Sampling for Linear Algebra, Statistics, and Optimization II | Michael Mahoney | 01h 02m |
Mixing importance sampling with a small uniform fraction reduces estimator variance, with an empirical sweet spot near half leverage plus half uniform (roughly… | ||
| Stochastic Second Order Optimization Methods I | Fred Roosta | 01h 07m |
Covers using subsampled Newton methods for finite-sum empirical risk: form a sub-sampled Hessian and solve the positive-definite linear system approximately… | ||
| Stochastic Second Order Optimization Methods II | Fred Roosta | 01h 12m |
Survey of practical stochastic second‑order methods claims that limited‑memory BFGS and Hessian‑vector products make curvature usable at scale, that subsampled… | ||
| Statistical Inference I | Will Fithian | 56m |
Defines a statistical model, loss and risk, then compares three binomial estimators delta0 = X/n, delta1 = (X+3)/n, delta2 = (X+3)/(n+6) and plots MSE vs θ to… | ||
| Statistical Inference II | Will Fithian | 01h 02m |
Defines hypothesis testing with controlled Type I error α and power as rejection probability, explains uniformly most powerful tests and the chi-square vs… | ||
| High Dimensional Geometry and Concentration I | Santosh Vempala | 57m |
High-dimensional sets have most of their volume near boundary (shrinking by 1−ε multiplies volume by (1−ε)^n) and Euclidean balls put half their mass inside a… | ||
| High Dimensional Geometry and Concentration II | Santosh Vempala | 01h 03m |
Proves the functional Brunn–Minkowski (Prékopa–Leindler) inequality by induction on dimension, using Brunn–Minkowski only in the one‑dimensional base case… | ||
| Algorithmic High Dimensional Robust Statistics I | Ilias Diakonikolas | 01h 00m |
Goal: recover a Gaussian mean in d dimensions with an epsilon fraction of corruptions and identity covariance. Transcript claims sample complexity… | ||
| Algorithmic High Dimensional Robust Statistics II | Ilias Diakonikolas | 01h 04m |
Proves a concrete certificate: if the empirical covariance spectral norm stays within 1+δ then the empirical mean is robust under strong contamination, with… | ||
| Nearest Neighbor Methods I | Ilya Razenshteyn | 01h 05m |
Nearest-neighbor search is framed as approximate search with radius R and approximation C, and the core claim is that locality-sensitive hashing (LSH) yields… | ||
| Nearest Neighbor Methods II | Ilya Razenshteyn | 01h 01m |
Covers concrete algorithms and limits: a deterministic L∞ decision-tree gives O(log log D) approximation with near-linear space and O(d log N) query work… | ||
| Data Streams I | Michael Kapralov | 01h 06m |
Shows that classic linear sketches (distinct‑elements, AMS) are applied to the graph edge‑incidence matrix to handle dynamic edge insertions and deletions… | ||
| Data Streams II | Michael Kapralov | 01h 03m |
CountSketch is used to turn unbiased dot‑product estimators into a practical CountSketch with B≈10·K buckets and hash repetitions T=Θ(log n): each bucket… | ||
| nothing matches | ||