Nonnegative Polynomials, Nonconvex Polynomial Optimization, and Applications to Learning

on YouTube ↗27m

" summary

Shows NP-hardness of testing a cubic polynomial’s monotonicity over a box, then gives an SOS relaxation that certifies monotone polynomial regressors and proves any C1 function with a monotonicity profile can be approximated by a polynomial whose monotonicity is certifiable by sum of squares. Proves every polynomial equals the difference of two SOS-convex polynomials, defines an undominated decomposition minimizing integrated trace of the Hessian, and reports CCP experiments (8 variables, degree 4) where the undominated decomposition finds substantially better minima.

AI-written summary · about

" chapters (16)

1. 0:00Intro
2. 0:47Optimizing over nonnegative polynomials
3. 1:371. Shape-constrained regression
4. 3:302. Difference of Convex (DC) programming Problems of the form min fo (x)
5. 5:21Monotone regression: problem definition
6. 6:52NP-hardness and SOS relaxation
7. 7:57Approximation theorem
8. 9:07Numerical experiments (1/2) • Low noise environment
9. 11:17Difference of Convex (dc) decomposition
10. 12:00Existence of dc decomposition (2/3)
11. 16:03Convex-Concave Procedure (CCP)
12. 17:47Picking the "best" decomposition for CCP
13. 18:23Undominated decompositions (1/2)
14. 20:48Comparing different decompositions (1/2)
15. 21:55Main messages • Optimization over nonnegative polynomials has many applications Powerful SDP/SOS-based relaxations available.
16. 23:52Uniqueness of dc decomposition

" related talks

• 59mCertificates of Polynomial Non-Negativity via Hyperbolic OptimizationJames Saunderson · Hyperbolic Polynomials and Hyperbolic Programming
• 01h 01mLP/SDP Hierarchies and Sum of Squares Proofs 1Ankur Moitra, Pablo Parrilo · Bridging Continuous and Discrete Optimization Boot Camp 2017
• 39mOptimization over the Hypercube via Sums of Nonnegative Circuit PolynomialsMareike Dressler · Hyperbolic Polynomials and Hyperbolic Programming
• 42mTight Semidefinite Programming Relaxations for Polynomial OptimizationJiawang Nie · Hyperbolic Polynomials and Hyperbolic Programming
• 57mCompletely Log-Concave PolynomialsCynthia Vinzant · Hyperbolic Polynomials and Hyperbolic Programming
• 49mDiscrete Optimization using Log-Concave PolynomialsNima Anari · Hyperbolic Polynomials and Hyperbolic Programming
• 01h 04mSubmodularity: Theory and Applications IStefanie Jegelka · Foundations of Machine Learning Boot Camp 2017
• 01h 11mPedagogical Talk: Failure of Low-Degree PolynomialsAlex Wein · Computational Phase Transitions (Simons Institute, 2020)