Big Data Boot Camp 2013
2013-09-03..2013-09-06
Berkeley, United States
who it's for
research scientists, machine learning researchers, computational statisticians, algorithm engineers, applied mathematicians, data engineers
topics
randomized numerical linear algebra; leverage-score column sampling; subsampled Hadamard sketches; Johnson-Lindenstrauss projections; locality-sensitive hashing; matrix concentration inequalities; bag of little bootstraps (BLB); streaming and sketching algorithms; L1 minimization and compressed sensing; accelerated and proximal optimization methods
| title | author | length |
|---|---|---|
| Big Data: The Computation/Statistics Interface | Michael Jordan | 01h 31m |
Argues that progress requires marrying computational ideas with statistical decision theory and gives concrete tools and numbers: convex relaxation hierarchies… | ||
| Algorithmic High-Dimensional Geometry I | Alex Andoni | 01h 34m |
Shows that random linear maps (Gaussian projections, i.e. the Johnson-Lindenstrauss lemma) cut dimension to k = O(log n / ε^2) and preserves pairwise distances… | ||
| User-Friendly Tools for Random Matrices I | Joel Tropp | 01h 04m |
Shows that a sample covariance estimator is a sum of independent rank-one pieces and analyzes its spectral error with a Matrix Bernstein concentration bound… | ||
| User-Friendly Tools for Random Matrices II | Joel Tropp | 57m |
Proves a concrete tail bound for a matrix Rademacher series: P(λ_max(X) ≥ t) ≤ D exp(−t^2/(2σ^2)) with σ^2 = ||E[X^2]||, so deviations scale like σ and a… | ||
| User-Friendly Tools for Random Matrices III | Joel Tropp | 45m |
Proves a usable bound: for a Rademacher series X = sum εi Ai the paper builds an exchangeable pairs construction (replace one εi) to form a matrix-Stein pair… | ||
| Algorithmic High-Dimensional Geometry II | Alex Andoni | 01h 34m |
Shows that datasets with doubling dimension λ admit ANN by projecting to O(λ) dimensions with asymmetric contraction/expansion guarantees and by using… | ||
| Past, Present and Future of Randomized Numerical Linear Algebra I | Petros Drineas, Michael Mahoney | 01h 27m |
Randomized sketches replace heavy SVDs by sampling columns/rows or by applying subsampled Hadamard or sign matrices, then uniform sampling; matrix… | ||
| Past, Present and Future of Randomized Numerical Linear Algebra II | Petros Drineas, Michael Mahoney | 01h 31m |
Claims concrete speed and accuracy tradeoffs for randomized matrix methods and shows what actually gets built and tested: use statistical leverage scores to… | ||
| Optimization I | Ben Recht | 01h 18m |
Covers concrete algorithms and rates: plain gradient descent converges linearly at a rate governed by condition number κ (example κ≈100 needs ~40 steps)… | ||
| Optimization II | Ben Recht | 01h 10m |
Claim: an S-sparse x0 in R^n is the unique optimal solution of L1 minimization from m Gaussian measurements when m ≥ (1+ε)(2S log n)+S+1 with failure… | ||
| High-Dimensional Statistics I | Martin Wainwright | 01h 30m |
High-dimensional settings need non-asymptotic guarantees: classification with D comparable to N shows a Kolmogorov-style alpha = N/D offset in error rates… | ||
| High-Dimensional Statistics II | Martin Wainwright | 01h 30m |
General recipe: M‑estimators with convex loss plus a decomposable regularizer yield concrete error rates once restricted strong convexity holds and the… | ||
| Streaming, Sketching and Sufficient Statistics I | Graham Cormode | 01h 24m |
Sketching algorithms use low-independence hash functions and linear sketches to compress massive update streams into small summaries that support merge by… | ||
| Streaming, Sketching and Sufficient Statistics II | Graham Cormode | 01h 26m |
Covers L0 sampling and L2 sampling with concrete constructions: geometric-level subsampling plus sparse recovery produces an L0 sampler that lets sketches of… | ||
| Some Geometric Perspectives on Combinatorics: High-Dimensional, Local and Local-to-Global I | Nati Linial | 01h 25m |
Counts Latin squares and their higher‑dimensional analogs by reducing to permanents and using Bregman + van der Waerden via permanents to get tight upper… | ||
| Some Geometric Perspectives on Combinatorics: High-Dimensional, Local and Local-to-Global II | Nati Linial | 01h 26m |
Random d‑dimensional simplicial complexes are sampled by keeping the full (d−1)-skeleton and choosing each d‑face independently with probability p; studying… | ||
| Theory and Big Data | Ravi Kannan | 01h 02m |
Argues that linear algebra + randomness actually gives provable wins: computing the best-fit k-subspace via SVD and projecting reduces dimension and often acts… | ||
| nothing matches | ||