Gradient descent is usually taught as if it were geometry-free. You compute a gradient, you step in the opposite direction, and you repeat. That picture hides a choice that matters more than the step size: what does "opposite direction" even mean?
In Euclidean space, the answer is obvious. In a probability simplex, a positive orthant, or a space of matrices, it is not. Mirror descent is the algorithm that makes that choice explicit. It replaces the Euclidean distance in the gradient step with a distance that matches the geometry of the problem, and the payoff can be dramatic: faster rates, iterates that stay feasible without projection, and updates that look like familiar algorithms in disguise.
The hidden geometry in one gradient step
Ordinary gradient descent can be written as a trade-off. At iterate xt , the next iterate solves:
Read that carefully. The linear term says "move downhill according to the local slope". The quadratic term says "but do not move too far, where far is measured by Euclidean distance". The step size η balances the two.
Mirror descent keeps the first term and changes the second. Replace the squared Euclidean distance with a Bregman divergence DΦ generated by a strictly convex function Φ :
The Bregman divergence is defined by:
It is the gap between Φ and its tangent at y , evaluated at x . It is not symmetric, and it is not a metric, but it is non-negative when Φ is convex, and it is zero only when x=y . Different choices of Φ give different notions of "close", and therefore different algorithms.
The update has a clean dual form. Let yt=∇Φ(xt) be the dual variable. Then mirror descent is:
In words: take a gradient step in dual space, then map back to primal space through the mirror map ∇Φ . The name "mirror" comes from this reflection between primal and dual coordinates. The algorithm is gradient descent, but seen through a mirror that distorts space in a useful way.
Two mirrors, two famous algorithms
The power of the framework is best seen in examples.
Euclidean mirror: ordinary gradient descent
Choose Φ(x)=21∣x∣22 . Then DΦ(x,y)=21∣x−y∣22 , the mirror map is the identity, and mirror descent collapses to ordinary gradient descent. This is the baseline, not a special case to ignore: it tells you that Euclidean geometry is a choice, and it is the right choice only when Euclidean distance is the natural way to measure movement.
Entropic mirror: exponentiated gradient
Now suppose x must lie on the probability simplex: entries non-negative, summing to one. This is the setting for portfolio weights, mixture weights, and distributions over experts. Euclidean steps constantly leave the simplex, and projecting back is awkward.
Choose the negative entropy as the mirror map generator:
The Bregman divergence is then the Kullback-Leibler divergence, and the mirror descent update becomes multiplicative:
This is the exponentiated gradient, or Hedge, update. Coordinates are multiplied by an exponential factor and renormalised. Positivity and the sum-to-one constraint are preserved automatically, with no projection step. The geometry does the work that projection used to do.
The contrast is instructive. For a problem on the simplex in dimension d , Euclidean gradient descent typically has a convergence rate that scales with d in the worst case, while the entropic version scales with logd . When d is thousands or millions, that is not a minor constant: it is the difference between a usable method and a useless one. The right geometry removes a dimension dependence that the wrong geometry imposes.
A worked example: learning a distribution over experts
Consider online prediction with expert advice. Each round, you choose a distribution xt over d experts, nature reveals a loss vector, and you suffer the expected loss ⟨ℓt,xt⟩ . You want low regret against the best single expert in hindsight.
Euclidean projected gradient descent works, but it treats the simplex like a flat box. Exponentiated gradient, the entropic mirror descent update, gives the classic Hedge bound: with a tuned step size, regret grows like Tlogd over T rounds. The logd factor is the signature of the entropic geometry. It appears because the natural "size" of the simplex under KL divergence is logarithmic in dimension, not linear.
A minimal sketch in Python makes the update concrete:
import numpy as np def exponentiated_gradient_step(x, grad, eta): # Multiplicative update, then renormalise onto the simplex. unnormalised = x * np.exp(-eta * grad) return unnormalised / unnormalised.sum() # Three experts, starting from uniform weights. x = np.array([1.0 / 3, 1.0 / 3, 1.0 / 3]) grad = np.array([0.8, 0.1, 0.4]) # expert 2 looks best this round x = exponentiated_gradient_step(x, grad, eta=0.5) print(x) # weight shifts toward expert 2, never leaves the simplex Note what the code does not contain: no projection, no clipping, no repair step. Feasibility is a property of the update, not an afterthought.
When mirror descent helps, and when it does not
Mirror descent helps most when three conditions hold:
- The domain has structure. Simplex, positive orthant, spectrahedron, or another set where Euclidean distance is a poor measure of closeness.
- A mirror map matches that structure. Entropy for the simplex, log-barrier style maps for the positive orthant, von Neumann entropy for density matrices.
- The mirror update is cheap. The dual map and its inverse must be computable. If inverting ∇Φ requires solving a hard optimisation problem at every step, the theoretical gain may not survive contact with implementation.
It does not help automatically. Picking a mirror map is a modelling decision, and a bad one can be worse than Euclidean. A mirror map that is not strongly convex relative to the norm in which gradients are bounded will give a weak rate. A mirror map whose inverse is numerically unstable will give iterates that overflow or underflow, a real hazard with exponentiated updates when gradients are large. In practice, this is why exponentiated gradient implementations work in log space or rescale gradients before exponentiating.
There is also a conceptual pitfall: mirror descent is not a different optimiser in the sense of Adam or momentum. It is a family that contains gradient descent as one member. Asking "mirror descent or gradient descent?" is like asking "which distance?" The honest answer is that gradient descent already answered that question implicitly, with Euclidean distance. Mirror descent forces you to answer it deliberately.
Mirror descent in modern machine learning
The ideas show up far beyond textbook optimisation. Entropic mirror descent underlies multiplicative weights, a workhorse in boosting, online learning, and game solving. Mirror descent with a suitable geometry appears in policy optimisation, where the policy is a distribution and KL divergence is the natural step penalty: trust-region and proximal policy methods are close relatives, penalising movement in distribution space rather than in parameter space. In matrix problems, the von Neumann entropy mirror gives multiplicative updates on positive semidefinite matrices.
The broader lesson generalises. Natural gradient descent, covered earlier in this series, also changes the geometry, using the Fisher information metric. Mirror descent and natural gradients are cousins: both say that the parameterisation you happened to choose should not dictate the optimisation path. Mirror descent achieves this through a chosen convex function and its Bregman divergence; natural gradients achieve it through a Riemannian metric. When the two agree, as they do for exponential families with the right mirror map, the connection is exact rather than merely suggestive.
A practical checklist
Before reaching for mirror descent, work through these questions:
- What set must the iterates live in, and does Euclidean projection onto it cost anything?
- Is there a convex function whose Bregman divergence measures closeness on that set in a natural way?
- Can you compute ∇Φ and its inverse cheaply and stably?
- In which norm are your gradients bounded, and is Φ strongly convex in that norm? If not, the rate will not deliver what you hoped.
- Have you tested the Euclidean baseline at the same step-size tuning effort? A fancy geometry that beats an untuned baseline has proved nothing.
If the answers favour a non-Euclidean mirror, the algorithm is often simpler than the theory suggests: one dual step, one mirror map back, and feasibility for free.
Takeaway
Gradient descent is not one algorithm. It is a template with a distance plugged in, and the default plug-in is Euclidean. Mirror descent makes that plug-in a choice: pick a convex function, get a Bregman divergence, and let the geometry of your problem shape the update. On the simplex, that choice turns additive steps into multiplicative ones, removes a projection, and replaces a dimension dependence with a logarithmic one. That is not a trick. It is what happens when the algorithm respects the space it is optimising over.
Connect with me on LinkedIn: linkedin.com/in/umeshtharukaofficial

