Continuous Methods 4
summary
Compares two greedy online algorithms — sequential greedy (Frank‑Wolfe/forward Euler style) and simultaneous greedy (implicit/backward update) — and proves primal‑dual competitive‑ratio bounds under a diminishing‑returns condition; maps the dual updates to follow‑the‑regularized‑leader (regret) with conjugate regularizers; shows smoothing (Moreau/Nesterov style, e.g. shifted entropy) yields better ratios and recovers the 1 − 1/e optimal bound for AdWords, and formulates an automated convex program to design the best smooth surrogate for separable objectives.
AI-written summary · about
chapters (12)
- 0:00Introduction
- 0:40Optimization
- 5:04AdWords
- 9:03Online Learning
- 14:18Primal Dual
- 18:08Greedy
- 19:39sequential greedy
- 24:16simultaneous greedy
- 25:45discretization
- 29:46analysis
- 39:11duality gap
- 40:51Diminishing return assumption
related talks
41mOnline Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization
56mCompetitive Analysis of Online Algorithms (Part 1)
01h 04mCompetitive Analysis of Online Algorithms (Part 2)
43mOnline Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization
51mAre Single-Loop Algorithms Sufficient for Unbalanced Minimax Optimization?
35mOnline Optimization and Learning Under Long-Term Convex Constraints and Objectives
41mCompetitive Algorithms for Online Control
01h 04mSubmodularity: Theory and Applications II