Entropic Mirror Simplex Update

Update probability weights multiplicatively while paying an explicit KL movement cost.

Entropic Mirror Simplex Update

Mirror descent offers a principled way to optimize functions over constrained spaces. When updating weights on a probability simplex, the standard Euclidean gradient descent can easily push weights out of bounds. The entropic mirror update uses the Kullback-Leibler (KL) divergence as its proximity measure, resulting in multiplicative updates that naturally remain within the simplex.

Worked Example: Simplex Weight Update

Suppose we start with a uniform prior distribution over three categories and apply increasing losses. We will compute the updated weights after a given number of steps.

Given prior p = [1/3, 1/3, 1/3], losses l = [0, 0.5, 1], learning rate η = 1, and steps t = 2.

Compute the unnormalized weights w_i = p_i exp(-η · t · l_i):

w_1 = (1/3) exp(-1 · 2 · 0) = 0.33333333
w_2 = (1/3) exp(-1 · 2 · 0.5) = (1/3) exp(-1) ≈ 0.12262648
w_3 = (1/3) exp(-1 · 2 · 1) = (1/3) exp(-2) ≈ 0.04511176

Sum the weights to find the normalization constant Z:

Z = 0.33333333 + 0.12262648 + 0.04511176 = 0.50107157

Normalize to obtain the final probabilities q_i = w_i / Z:

q_1 ≈ 0.6652
q_2 ≈ 0.2447
q_3 ≈ 0.0900

The KL divergence to the prior is calculated as ∑ q_i ln(q_i / p_i) ≈ 0.2662.

Experimenting with the Update

You can interactively explore the entropic mirror descent using the Entropic Mirror Simplex Update module:

Set Prior to "Uniform" and Losses to "Increasing". Observe how the trace moves towards the coordinate with the lowest loss (Coordinate 1).
Increase the Learning rate to "2". The trajectory becomes steeper, reaching a more concentrated distribution at the same number of steps.
Change Prior to "Sparse". Notice that Coordinate 3 remains exactly at zero; the multiplicative update cannot revive a component once it has zero probability.

Limitations

A fundamental property of the multiplicative weights update is support preservation. Any coordinate with an initial prior probability of zero will remain zero forever, regardless of how favorable its loss might be. Therefore, this method cannot be used directly if new, unseen categories need to be explored or integrated dynamically, unless the prior strictly assigns a non-zero probability to all possible categories.

References

For a mathematical foundation of mirror descent and its application to the simplex using entropy, refer to these lecture notes on Mirror Descent.

Entropic Mirror Simplex Update