Questions: Multiplicative Weights Method

Question 1

In the multiplicative weights update, the learning rate eta controls a tradeoff. What happens if eta is too large or too small?

• A. Large eta causes convergence to a single expert too quickly (high regret from commitment); small eta causes uniform weighting for too long (high regret from slow adaptation)
• B. Large eta causes numerical overflow; small eta causes underflow
• C. Large eta makes the algorithm equivalent to follow-the-leader; small eta makes it equivalent to random guessing
• D. The learning rate has no effect on the regret bound — only the number of rounds T matters

Answer: (A)

The learning rate eta balances responsiveness against stability. Large eta means each round's loss dramatically changes the weights — the algorithm overreacts to recent losses and may commit too quickly to an expert that happened to do well recently, suffering high regret when that expert later performs poorly. Small eta means the weights barely change each round, so the algorithm adapts very slowly to the actual loss sequence and wastes rounds maintaining near-uniform weighting. The optimal eta = sqrt(ln(N)/T) minimizes total regret at O(sqrt(T * ln N)), balancing these two failure modes. Setting eta optimally requires knowing T in advance (or using a doubling trick).

Question 2

The multiplicative weights method guarantees that the learner's cumulative loss is at most the best expert's loss plus O(sqrt(T * ln N)). This bound holds even if the adversary knows the algorithm the learner is using.

• T. True
• F. False

Answer: True

This is a key strength of the multiplicative weights method: the regret bound holds against an oblivious adversary (who fixes the loss sequence in advance) and even against an adaptive adversary (who can choose round t's losses based on the learner's previous actions), as long as the learner randomizes according to the weights. The adversary can know the algorithm completely — the randomization is what protects the learner. This robustness is why MW is used in cryptographic protocols and zero-sum game solving, where the opponent has full information.

Question 3

The multiplicative weights method is only applicable to prediction with expert advice — it cannot be used for continuous optimization problems.

• T. True
• F. False

Answer: False

While MW is most naturally stated for the finite-expert setting (choose among N discrete options), it has been extended to continuous optimization through its connection to mirror descent. The multiplicative update is the mirror descent algorithm with the negative entropy regularizer (the KL divergence). This connection allows MW-type algorithms to handle continuous action spaces by maintaining probability distributions over actions. MW also appears in LP solvers (Plotkin-Shmoys-Tardos), zero-sum game equilibrium computation, and flow problems — all continuous optimization settings.

Question 4

Explain why the multiplicative weights method achieves the same regret bound as AdaBoost's weight update, and what the conceptual connection between them is.

Model answer: Both AdaBoost and MW use the same multiplicative update structure: multiply weights by a factor that depends exponentially on the loss (or classification error). In MW, the learner downweights experts that incur high loss. In AdaBoost, the algorithm upweights training examples that are misclassified — the dual perspective where examples play the role of 'experts.' The formal connection is that AdaBoost can be derived as a MW algorithm applied to a zero-sum game between a booster (choosing example weights) and a weak learner (choosing classifiers). The regret bound for MW translates directly into AdaBoost's training error bound: exp(-2 * gamma^2 * T) corresponds to the regret of the example-weighting player in the game. This game-theoretic view unifies boosting, online learning, and minimax optimization.

Freund and Schapire explicitly developed AdaBoost from the MW framework. The connection is not just analogical — AdaBoost IS the MW algorithm applied to a specific game, and its convergence guarantees follow from the MW regret bound.