The mapping

  • Given a candidate point x, define the cost vector entry mᵢ = aᵢ·x − bᵢ — the slack of constraint i 1:16:04 1:17:21.
  • Each constraint (row of A) is an expert 1:18:42.
  • Open normalization detail: mᵢ must land in [−1, 1]; the lecturer explicitly defers this normalization to the next lecture, having confused himself on it live 1:17:21.

Reading the sign correctly

The polarity looks backwards at first 1:18:42:

mᵢ = aᵢ·x − bᵢMeaning for the LPMeaning as an "expert"
Positive (large slack)Constraint comfortably satisfied → easyExpert was very "wrong"
NegativeConstraint violated → hardExpert was "right"
  • The right mental model: experts predict whether constraint i is hard. Large slack means the constraint was easy, so the expert who called it hard was wrong 1:19:18 1:19:35.

Why this is exactly what we want

  • MW down-weights experts who are wrong, so it shifts weight away from well-satisfied constraints and onto unsatisfied ones 1:19:35 1:19:53.
  • Since the goal is approximate feasibility of all constraints, spending future iterations on the constraints still violated is precisely the correct effort allocation 1:19:53 1:20:41.

Deferred to the next lecture

  • The iteration-count analysis: how many MW rounds are needed for the ε-approximate feasibility guarantee 1:20:59.
  • What property of the convex set P is actually required (the oracle) 1:20:59.
  • The normalization of mᵢ into [−1, 1] 1:17:21.
  • After that, the course leaves LP solving behind entirely and starts a new topic 1:21:19.