Discrete Optimization using Log-Concave Polynomials

on YouTube ↗49m

" summary

Shows a concrete algorithmic pipeline: relax the 0/1 max-coefficient integer program to a continuous program over the polynomial G_mu, solve when G_mu is log-concave, and round by sampling to get a e^K approximation for degree-K objectives (matching known hardness for determinants). Extends to constrained cases by applying differential operators to G_mu·G_nu, invoking a capacity inequality to produce a log-concave surrogate and another e^K-bound; works for Nash Social Welfare as an e^n guarantee. Caveat: surrogate gives value estimates but not always an explicit feasible set.

AI-written summary · about

" chapters (7)

1. 0:00Start
2. 0:30Optimization Problem
3. 1:18Example: Determinant Maximization
4. 5:23Approximation Factor
5. 8:42Solving the Relaxation
6. 31:28Fractional Relaxation
7. 45:27Open Questions

" related talks

• 57mComputationally Efficient Alternatives to Nonconvex-Nonconcave Min-Max OptimizationNisheeth Vishnoi · Adversarial Approaches in Machine Learning 2022
• 01h 00mLog-concave Polynomials and Spectral Independence 2Kuikui Liu · Analysis and TCS Boot Camp 2023
• 46mSmooth Nonconvex Min-Max OptimizationMeisam Razaviyayn · Adversarial Approaches in Machine Learning 2022
• 27mNonnegative Polynomials, Nonconvex Polynomial Optimization, and Applications to LearningGeorgina Hall · Hierarchies, Extended Formulations and Matrix-Analytic Techniques (2017)
• 01h 04mSubmodularity: Theory and Applications IStefanie Jegelka · Foundations of Machine Learning Boot Camp 2017
• 35mOnline Optimization and Learning Under Long-Term Convex Constraints and ObjectivesNikhil Devanur · Optimization and Decision-Making Under Uncertainty (Simons Institute, September 2016)
• 46mCan Non-Convex Optimization be Robust?Rong Ge · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 01h 04mSubmodularity: Theory and Applications IIAndreas Krause · Foundations of Machine Learning Boot Camp 2017