Online Optimization, Smoothing, and Competitive Ratio

on YouTube ↗01h 01m

" summary

Claims that competitive ratio for online resource allocation improves if the objective psi is optimally smoothed; derives a concrete scalar metric alpha curvature measure that controls ratio (worst-case ≥ 1/(1−alpha), so alpha in (−1,0] gives ≥1/2 and recovers 1−1/e for AdWords). Tools: primal–dual and saddle updates, convex optimization over conjugates (smoothing via conjugate), discretization and differential-equation reductions, and matrix monotone representation via Löwner’s theorem. Produces an offline solver that outputs psi_s and g_s, shows numerical gains and a gamma trade-off between competitive ratio and budget violation.

AI-written summary · about

" chapters (13)

1. 0:00Intro
2. 0:56An Online Resource Allocation Model
3. 4:34Example: Adwords Problem
4. 7:12Example Online Packing LP
5. 10:32Example: Online D-optimal Experiment Design
6. 16:27Dual problem
7. 19:51Greedy approaches
8. 29:22Smoothing intuition
9. 32:08Smoothing via conjugate functions
10. 35:36Design Optimal
11. 39:21Optimized solution vs handcrafted
12. 41:32Design Smoothing for Matrix Trace functions
13. 55:37Related Literature