The reduction target: instead of solving a linear program directly, reduce it to repeatedly answering a single-constraint relaxation, handled by an oracle.

The problem being solved

  • Decide feasibility of: does there exist x ∈ P with Ax ≥ b, where P is a convex set and A is an m × n matrix (5:43, 6:29).
  • Only feasibility is treated; optimization is recovered later by binary searching on the objective value (32:44).

The relaxed subproblem (⋆)

For a probability vector p, ask: does there exist x ∈ P with pᵀAx ≥ pᵀb? (6:29, 8:47)

  • Key observation: if the original m-constraint problem is feasible, so is (⋆) — take a feasible x and multiply both sides by pᵀ, using non-negativity of p (9:12).
  • Contrapositive: if the oracle reports (⋆) infeasible, the original LP is infeasible (19:30).
  • Intuition for why this is easier: (⋆) has one constraint (plus membership in P), the original has m (14:30).

Definition: ρ-bounded oracle

An algorithm that, given P, A, b, and the probability vector p (9:35):

  • If (⋆) is feasible, it outputs an x satisfying (⋆) and additionally |aᵢ·x − bᵢ| ≤ ρ for all i (7:25).
  • Otherwise it outputs infeasible (7:25).
  • The extra ρ promise is a strengthening: the oracle must not return just any feasible x, but one with bounded constraint violation magnitude (30:52).

What ρ does and does not say

  • The bound is on absolute value, so it says nothing about which side of the constraint aᵢ·x falls on; the returned x need not be feasible for the original LP (9:57, 10:41, 11:01).
  • ρ is the price paid in running time: a badly-shaped polytope forcing a large ρ means multiplicative weights must run more iterations (13:02, 13:39).
  • Notation warning: capital P is the convex set, lowercase p is the probability distribution over experts (14:01). Because ρ looks like p on the board, it is renamed γ mid-proof (20:51).