The theorem

Given a ρ-bounded oracle with ρ > ε/2, multiplicative weights finds x ∈ P with

Ax ≥ b − ε·𝟙

in O(ρ² log m / ε²) iterations (days T) (14:52, 15:41).

The reduction

  • Experts = the m constraints of the LP (16:32, 17:09).
  • Day 1 starts from the uniform distribution over experts; p_t then evolves as usual (17:09, 17:38).
  • Cost vector: m_t = (1/γ)(A x_t − b), where x_t is the oracle's answer on input p_t and γ = ρ (18:16, 18:52).
  • Legality: MW allows the cost vector to be chosen adversarially after p_t is committed, which is exactly the order here (17:38, 17:59).
  • The 1/γ normalization is precisely what forces m_t ∈ [−1, 1]^m, the hypothesis the MW theorem needs (21:32).
  • If the oracle ever reports infeasible, halt and declare the LP infeasible (19:30).
flowchart LR
    A["MW state: p_t over m constraints"] --> B["ρ-bounded oracle(p_t)"]
    B -->|infeasible| H["Halt: LP infeasible"]
    B -->|"x_t ∈ P"| C["m_t = (1/γ)(A x_t − b)"]
    C --> D["MW update → p_(t+1)"]
    D --> A
    C --> E["Accumulate x̃ = (1/T) Σ x_t"]
    E --> F["Output x̃ with A x̃ ≥ b − ε·𝟙"]

Proof sketch — the squeeze

  1. Lower bound. ⟨m_t, p_t⟩ = (1/γ)(p_tᵀA x_t − p_tᵀb) ≥ 0, because that is exactly the guarantee the oracle enforces on (⋆) (20:51, 21:32, 22:29).
  2. Sum over all days — still non-negative term by term (23:23).
  3. Upper bound. Apply the MW theorem with its own error parameter η (deliberately different from the final ε): 0 ≤ (1/γ)Σ_t(aᵢ·x_t − bᵢ) + ηT + log m / η, for every i (23:57, 24:23, 24:58).
  4. Average the iterates. Set x̃ = (1/T) Σ_t x_t. Each x_t ∈ P and P is convex, so x̃ ∈ P (25:59).
  5. Multiply through by γ/T: 0 ≤ aᵢ·x̃ − bᵢ + γη + γ ln m / (ηT) (25:24, 26:33).
  6. Tune both error terms to ε/2 (27:32, 28:35):
  7. Conclude aᵢ·x̃ ≥ bᵢ − ε for all i (29:00).

The algorithm in one sentence

Run the oracle once per iteration to get x_t; the final almost-feasible output is the average of all the x_t produced (29:29, 29:49).