Bridging Continuous and Discrete Optimization Boot Camp 2017
2017-08-21..2017-08-25
Berkeley, United States
[Discrete Optimization via Continuous Relaxation, Semidefinite Optimization, Approximation and Applications 2014, Foundations of Machine Learning Boot Camp 2017, Geometric Methods in Optimization and Sampling Boot Camp, Optimization and Algorithm Design 2023, Foundations of Data Science Boot Camp 2018]
as the organisers put it
The last decade has seen an emerging confluence of ideas from discrete and continuous optimization, leading to several significant breakthroughs. This program will bring together researchers from both the discrete and continuous optimization communities in order to stimulate further interaction at this interface.
who it's for
optimization researchers, theoretical computer scientists, applied mathematicians, algorithm designers, operations researchers, machine learning researchers, graduate students
topics
conic duality and Slater regularity; semidefinite programming for stable set; sum-of-squares proofs to SDP; LP and SDP hierarchies; extended formulations and nonnegative rank; interior point methods; continuous-time algorithm discretization; mirror descent and acceleration; robustness and stochastic optimization; projected and stochastic gradient methods; polynomial optimization via Gram matrices; flag algebra to SOS reductions
| title | author | length |
|---|---|---|
| Duality 1 | Michel Goemans | 01h 01m |
Develops conic duality and Slater regularity for cone programs, shows the PSD and second‑order cones are self‑dual, and derives complementary slackness that… | ||
| Duality 2 | Michel Goemans | 01h 02m |
Shows that semidefinite programming exactly captures the stable set polytope for perfect graphs (theta body = STAB for perfect graphs) and describes two ways… | ||
| LP/SDP Hierarchies and Sum of Squares Proofs 1 | Pablo Parrilo, Ankur Moitra | 01h 01m |
Explains that nonnegativity checks reduce to semidefinite programming by writing a polynomial as a quadratic form over a chosen monomial basis and searching… | ||
| LP/SDP Hierarchies and Sum of Squares Proofs 2 | Pablo Parrilo, Ankur Moitra | 01h 04m |
Real infeasibility certificates appear as an f + g = -1 certificate with f in the ideal of equations and g in the cone generated by inequalities; bounding the… | ||
| Duality 3 | Michel Goemans | 01h 05m |
Shows that stab(G) equals Qstab(G) exactly when every induced subgraph satisfies Omega = Chi, proved by LP duality on the weighted clique problem and Lovász’s… | ||
| Continuous Methods 1 | Lorenzo Orecchia, Maryam Fazel, Stefanie Jegelka | 01h 02m |
Asserts that designing first-order algorithms from continuous dynamics plus conjugate duality yields a mechanical recipe: pick mirror map via conjugate… | ||
| Continuous Methods 2 | Lorenzo Orecchia, Maryam Fazel, Stefanie Jegelka | 58m |
Claims that continuous-time gap invariants plus two discretization recipes produce accelerated O(1/T^2) convergence for convex problems, with concrete… | ||
| Robustness, Stochastics, Uncertainty 1 | Sasha Rakhlin, Ben Recht, Laurent El Ghaoui | 01h 01m |
Shows that finite-sample learning guarantees come from concrete optimization tools: Blackwell approachability gives a randomized strategy that matches the… | ||
| Robustness, Stochastics, Uncertainty 2 | Sasha Rakhlin, Ben Recht, Laurent El Ghaoui | 01h 01m |
Shows that projected SGD and online linear optimization give a deterministic 1/√N regret for bounded gradients and that an adaptive stepsize (Adagrad-style)… | ||
| LP/SDP Hierarchies and Sum of Squares Proofs 3 | Pablo Parrilo, Ankur Moitra | 59m |
Part three shows an SOS/SDP proof that a triangle-free graph has at most asymptotically half the possible edges (an SOS version of Mantel’s theorem), by… | ||
| LP/SDP Hierarchies and Sum of Squares Proofs 4 | Pablo Parrilo, Ankur Moitra | 01h 06m |
Presents a concrete SOS-based algorithm: a quasi-polynomial time N^{O(log N / ε^2)} method that approximates the max of a degree‑4 polynomial (M defined as… | ||
| Extended Formulations 1 | Thomas Rothvoß, Prasad Raghavendra, Hamza Fawzi | 58m |
Quick tutorial that proves the core claims: extended formulations let some polytopes shrink from exponentially many inequalities to n×B network flow LP for… | ||
| Extended Formulations 2 | Thomas Rothvoß, Prasad Raghavendra, Hamza Fawzi | 01h 00m |
Shows a concrete lower bound for the correlation polytope by extracting a submatrix of its slack matrix with entries 1 for disjoint 0/1 vectors and 0 for pairs… | ||
| Robustness, Stochastics, Uncertainty 3 | Sasha Rakhlin, Ben Recht, Laurent El Ghaoui | 01h 03m |
Gives a practical tour: shows that tiny implementation noise (example cited: 0.001% error breaks feasibility) ruins some linear-program designs, converts… | ||
| Extended Formulations 3 | Thomas Rothvoß, Prasad Raghavendra, Hamza Fawzi | 53m |
Extension complexity equals non-negative rank of the slack matrix, and for the correlation polytope LP/SDP relaxations correspond to families or vector spaces… | ||
| Extended Formulations 4 | Thomas Rothvoß, Prasad Raghavendra, Hamza Fawzi | 58m |
Shows how any bounded density F on {0,1}^n that tests indistinguishably against a family of functions D1 … Dm is approximated by a normalized exponential of a… | ||
| Interior Point Methods 1 | Steve Wright, Aaron Sidford, Aleksander Madry | 01h 01m |
Lecture claims simple Newton-style primal‑dual schemes solve LP by following the central path and driving the duality gap mu to zero, using only linear solves… | ||
| Interior Point Methods 2 | Steve Wright, Aaron Sidford, Aleksander Madry | 54m |
Covers concrete algorithms and guarantees: path-following Newton steps on the log barrier give the usual sqrt(n) iteration bound for short-step primal‑dual… | ||
| Interior Point Methods 3 | Steve Wright, Aaron Sidford, Aleksander Madry | 01h 10m |
Derives a path-following interior‑point method that minimizes the barrier f_mu = (c^T x)/mu + sum_j -log(slack_j) using Newton steps in the local Hessian norm… | ||
| Continuous Methods 3 | Lorenzo Orecchia, Maryam Fazel, Stefanie Jegelka | 01h 02m |
Shows that a submodular set function has a convex continuous extension via the Lovász extension and a dual base polytope whose linear optimization costs O(n… | ||
| Continuous Methods 4 | Lorenzo Orecchia, Maryam Fazel, Stefanie Jegelka, Reza Eghbali | 01h 00m |
Compares two greedy online algorithms — sequential greedy (Frank‑Wolfe/forward Euler style) and simultaneous greedy (implicit/backward update) — and proves… | ||
| Interior Point Methods 4 | Steve Wright, Aaron Sidford, Aleksander Madry | 01h 08m |
Claims an interior-point framework that gets sqrt(d) iterations while keeping each step as cheap as a projection-based Newton solve, yielding runtimes about… | ||
| nothing matches | ||