Sparsifying Sums of Norms

on YouTube ↗01h 03m

" summary

For N(x)=Σi Ni(x) there exist nonnegative weights w with only O(ε^{-2} n log(n/ε) (log n)^{2.5}) nonzeros and |N(x)−Σi wiNi(x)| ≤ εN(x) for all x, found by independent sampling with probabilities proportional to μ ∝ e^{-N(x)} (oversampled by polylog factors). Algorithm runs in O(m (log n)^{O(1)} + poly(n))·T where T evaluates a Ni(x). Proof combines Dudley’s chaining, Sudakov packing, and log‑concave tail bounds (KLS‑type) and yields the same guarantee for sums of symmetric submodular functions via the Lovász extension.

AI-written summary · about

" chapters (9)

1. 0:00Introduction
2. 1:06Sparsification goal
3. 9:52Generalizing to norms
4. 18:12Random sampling
5. 31:38Sampling probabilities & covering
6. 40:01Sudakov method proof
7. 57:47KLS conjecture for tails
8. 1:00:01Proof & sparsifier size
9. 1:01:47Open questions

" related talks

• 56mSparsifying Generalized Linear ModelsYang Liu · Optimization and Algorithm Design 2023
• 01h 06mLP/SDP Hierarchies and Sum of Squares Proofs 4Ankur Moitra, Pablo Parrilo · Bridging Continuous and Discrete Optimization Boot Camp 2017
• 44mStructured Sparsity-Inducing Norms Through Submodular FunctionsFrancis Bach · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 01h 10mOptimization IIBen Recht · Big Data Boot Camp 2013
• 37mTight Bounds for Volumetric Spanners in All NormsAditya Bhaskara, Ali Vakilian, Sepideh Mahabadi · Sketching and Algorithm Design 2023
• 23mHow Large is the Norm of a Random Matrix?Ramon van Handel · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 46mSpectral Partitioning for Metrics (And NNs Too)Alex Andoni · Sublinear Algorithms and Nearest-Neighbor Search
• 01h 23mGeneralization IIPeter Bartlett, Sasha Rakhlin · Deep Learning Boot Camp 2019