Computational and Statistical Tradeoffs via Convex Relaxation
Talkat Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013) · 2013-09-16..09-19·
summary
Claim: with abundant IID data extra samples let one use sample mean then projection on successively weaker convex relaxations to cut runtime while keeping fixed risk. Tool: convex relaxation hierarchies and the Gaussian complexity of cones control required n. Examples: exact cut polytope is intractable, elliptope P^2.25 needs √P samples up to constants, while nuclear norm SVD P^1.5 needs a larger constant times √P; sample-mean cost is n·P so throwing away data sometimes helps.
AI-written summary · about
chapters (16)
- 0:00Intro
- 1:17Classical Analysis in Statistics
- 2:35A Thought Experiment
- 5:20Computer Science vs. Statistics
- 6:50Outline
- 7:31Time-Data Tradeoffs
- 13:28An Estimation Problem
- 14:49Convex Programming Estimator
- 16:28Statistical Performance of Estimator
- 19:28Weakening via Convex Relaxation
- 21:59Hierarchy of Convex Relaxations
- 27:05Before We Get to Examples ...
- 29:29Example 1
- 36:15Recall Plot ...
- 37:03Some Questions
- 39:23Summary
related talks
09mConvex Programs, Computational Phase Transitions, and Robust Algorithms
48mComputational-Statistical Tradeoffs in Robust High-Dimensional Estimation
01h 31mBig Data: The Computation/Statistics Interface
46mCan Non-Convex Optimization be Robust?
01h 03mSampling for Linear Algebra, Statistics, and Optimization I
42mLearning What Works Best When
01h 11mOptimization and Sampling Under Symmetry: Part 1 -- Examples
01h 11m(Hidden) Symmetries of Computational Problems (continued)