Structured Sparsity-Inducing Norms Through Submodular Functions

on YouTube ↗44m

" summary

Derives convex sparsity norms from nondecreasing submodular set functions and proves the Lovász extension is the convex envelope of any penalty that depends on support, so replacing L0 by Lovász extension yields polyhedral norms with faces that encode allowed supports. Proximal steps reduce to submodular-function minimization and can be solved by at most ≤P submodular minimizations, enabling fast proximal algorithms. Applies group/rectangle constructions to get localized nonzeros for sparse PCA on faces, and shows semidefinite relaxations for matrix-factorization norms exist but fail to outperform simple alternating optimization empirically.

AI-written summary · about

" chapters (31)

1. 0:00Intro
2. 0:58Outline
3. 1:31Sparsity in unsupervised machine learning
4. 4:04Structured sparse PCA (Jenatton et al., 2009)
5. 5:25Why structured sparsity?
6. 5:59Different types of structured sparsity
7. 6:38Classical approaches to structured sparsity
8. 7:11Unit norm balls Geometric interpretation
9. 7:40ℓ₁-norm = convex envelope of cardinality of support
10. 9:00Convex envelopes of general functions of the support (Bach, 2010)
11. 9:39Submodular functions (Fujishige, 2005; Bach, 2011)
12. 11:24Submodular functions - Examples
13. 12:03Submodular functions - Lovász extension
14. 16:38Polyhedral unit balls
15. 18:27Submodular functions and structured sparsity Examples
16. 20:11Selection of contiguous patterns in a sequence
17. 21:10Other examples of set of groups H
18. 21:43Sparse Structured PCA (Jenatton, Obozinski, and Bach, 2009)
19. 22:11Application to face databases (2/3)
20. 22:51Application to background subtraction (Mairal, Jenatton, Obozinski, and Bach, 2010)
21. 25:42Unified optimization algorithms
22. 26:54Proximal methods for Lovász extensions
23. 28:06Comparison of optimization algorithms
24. 28:18Unified theoretical analysis
25. 29:18ε-relaxation of combinatorial penalties
26. 30:35γ-relaxation of submodular penalties
27. 34:00Structured matrix decomposition (Bach, 2013)
28. 35:58Special cases
29. 36:55Semi-definite relaxations for dual norm e(Y)
30. 38:08Finding decompositions
31. 39:23Conclusion

" related talks

• 01h 04mSubmodularity: Theory and Applications IStefanie Jegelka · Foundations of Machine Learning Boot Camp 2017
• 37mTight Bounds for Volumetric Spanners in All NormsAditya Bhaskara, Ali Vakilian, Sepideh Mahabadi · Sketching and Algorithm Design 2023
• 56mSparsifying Generalized Linear ModelsYang Liu · Optimization and Algorithm Design 2023
• 01h 01mLP/SDP Hierarchies and Sum of Squares Proofs 1Ankur Moitra, Pablo Parrilo · Bridging Continuous and Discrete Optimization Boot Camp 2017
• 01h 11m(Hidden) Symmetries of Computational Problems (continued)Michael Walter, Avi Wigderson · Geometric Methods in Optimization and Sampling Boot Camp
• 52mConstrained Subset Selection Problems under Diversity MeasuresMohit Singh · Hyperbolic Polynomials and Hyperbolic Programming
• 01h 00mOn Approximating the Covering Radius and Finding Dense Lattice SubspacesDaniel Dadush · Lattices: Geometry, Algorithms and Hardness 2020
• 01h 03mSparsifying Sums of NormsYang Liu · Beyond the Boolean Cube 2023