Robust Sketching for Large-Scale Multi-Instance Conic Optimization
summary
Proposes robust sketching: replace data matrix A by a low‑rank approximation à and add an uncertainty ball so solutions remain valid for any A within that error; produces an elastic‑net style correction for sparse learning and a second‑order‑cone reformulation for LP feasibility. Claims a one‑order reduction in complexity when rank k is small and shows experiments on 20k×40k and 28k×49k text matrices where a rank-50 approximation recovers full accuracy and yields an order-of-magnitude speedup.
AI-written summary · about
chapters (8)
- 0:00Start
- 0:26Outline
- 6:15Robust sketching
- 13:27Elastic net allows better sparsity control
- 14:08Solving robust low-rank LASSO
- 15:49Numerical experiments
- 19:05Multi-label classification
- 21:41Low-rank LP
related talks
53mSketching and Projecting
01h 03mSampling for Linear Algebra, Statistics, and Optimization I
28mSketching for M-Estimators: A Unified Approach to Robust Regression
01h 04mSketching and Randomized Linear Algebra
28mRandomized Constrained Matrix Decompositions
01h 03mSketching as a Tool for Numerical Linear Algebra
01h 10mSketching for Linear Algebra: Basics of Dimensionality Reduction and CountSketch II
59mSketching for Linear Algebra: Basics of Dimensionality Reduction and CountSketch I