Mirror Descent

Mirror descent generalizes gradient descent by measuring distance with a problem-adapted geometry instead of the Euclidean norm.

Beyond Euclidean steps

Gradient descent implicitly measures how far it moves with the squared Euclidean distance. That choice is arbitrary and can be a poor match for the geometry of the feasible set. Mirror descent replaces the Euclidean penalty with a Bregman divergence built from a chosen convex potential function, adapting the step geometry to the problem.

The proximal view

One iteration solves x_{k+1} = argmin_x ( t grad f(x_k)^T x + D_h(x, x_k) ), where D_h is the Bregman divergence of a strongly convex potential h. Choosing h(x) = (1/2)||x||^2 recovers ordinary gradient descent exactly. Choosing the negative entropy h(x) = sum x_i log x_i over the probability simplex yields entropic mirror descent, whose update is the multiplicative-weights rule: multiply each coordinate by exp(-t gradient) and renormalize.

import numpy as np

def entropic_md(grad_fn, x0, t, iters):
    x = x0 / x0.sum()          # start on the simplex
    for _ in range(iters):
        g = grad_fn(x)
        x = x * np.exp(-t * g)  # multiplicative update
        x = x / x.sum()         # renormalize to the simplex
    return x

Why the geometry helps

On the probability simplex in n dimensions, Euclidean-projected gradient descent has a convergence bound that scales with sqrt(n), while entropic mirror descent scales with sqrt(log n). For large n that is an enormous improvement. The lesson is that matching the potential to the constraint set (entropy for the simplex, the log-barrier for the positive orthant) can change the dimension dependence of the convergence rate.

Connections

Mirror descent unifies several algorithms: gradient descent, multiplicative weights, and exponentiated-gradient updates are all special cases. It is central to online learning, where the multiplicative-weights view gives regret bounds, and it connects to natural gradient methods, which also replace the Euclidean metric with a problem-derived one. The practical recipe is to pick a potential strongly convex in the norm under which the gradients are bounded.