Constrained Subset Selection Problems under Diversity Measures

on YouTube ↗52m

" summary

Presents a concrete model: embed items as vectors and optimize spectral objectives (determinant for D-optimality, trace for average effective resistance, spectral norm for worst-case error). Shows determinant objective equals volume and for graph Laplacians counts spanning-tree count. Algorithms: convex relaxations plus randomized rounding give 1+ε approximations once K = Ω(D/ε^2) but solving the program is slow; simple local search runs fast and is provably 1+ε when K is sufficiently larger than D. Partition constraints yield existence guarantees via real-stable polynomials but mostly nonconstructive algorithms.

AI-written summary · about

" chapters (15)

1. 0:00Intro
2. 2:04Determinantal Point processes (Kulesza and Taskar '12)
3. 6:31Outline of the talk.
4. 8:00Experimental Design in Statistics
5. 13:03Related problems: Graphs and Laplacians
6. 17:17D-design-Convex Programming Approach
7. 21:25Fedorov Exchange method
8. 27:26Partition Constraints and Allocation Problems
9. 31:52Maximizing Determinant • Maximum Determinant problem subject to partition constraints
10. 34:25Geometric Concave Program
11. 36:36Relaxation
12. 40:39Approximation Algorithm
13. 42:35Generalizations
14. 43:10E-design with partition matroid
15. 46:24Conclusion

" related talks

• 46mRecent Advances in Diversity Maximization in the Offline and Composable Coreset ModelsSepideh Mahabadi · Dynamic Graphs and Algorithm Design (Simons Institute, 2023)
• 35mLocal Statistics, Semidefinite Programming, and Community Detection IISidhanth Mohanty · Computational Phase Transitions (Simons Institute, 2020)
• 45mNoisy Estimation of Simultaneously Structured ModelsMaryam Fazel · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 01h 08mData Driven Optimization Models and AlgorithmsYinyu Ye · Optimization, Statistics and Uncertainty
• 29mSampling Algorithms for Combinatorial Pure ExplorationAnupam Gupta · Optimization, Statistics and Uncertainty
• 47mLearning Probabilistic Models for Graph Partitioning in the Presence of NoiseAravindan Vijayaraghavan · Learning, Algorithm Design and Beyond Worst-Case Analysis
• 48mRandomized Numerical Linear AlgebraPetros Drineas · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 01h 30mHigh-Dimensional Statistics IMartin Wainwright · Big Data Boot Camp 2013