Bregman Divergences

A natural way to measure closeness

Efficiency is key in optimization.
To that end, how can you craft your algorithm
to respect a problem’s geometry?

Standard algorithms often use Euclidean geometries,
but one can generalize these with
𝗕𝗿𝗲𝗴𝗺𝗮𝗻 𝗱𝗶𝘃𝗲𝗿𝗴𝗲𝗻𝗰𝗲𝘀.

Essentially, one can use a convex function
and measure the difference between two points
as the difference between the function value
at one point and a tangent line,
starting from the other point.
This can yield simpler algorithms
(e.g. when minimizing over the unit simplex)
and/or more quickly converging algorithms.

For more details, check out the slides below.

Cheers,

Howard

𝗥𝗲𝗰𝗼𝗺𝗺𝗲𝗻𝗱𝗮𝘁𝗶𝗼𝗻𝘀 𝗳𝗼𝗿 𝗳𝘂𝗿𝘁𝗵𝗲𝗿 𝗿𝗲𝗮𝗱𝗶𝗻𝗴:
- Chapter 2 of Yair’s book "Parallel Optimization: Theory, Algorithms, and Applications"
- Chapter 9 of Amir Beck’s book "First-Order Methods in Optimization"
- Lieven Vandenberghe's 236C slides

𝗦𝗶𝗱𝗲 𝘀𝘁𝗼𝗿𝘆:
Yair Censor and I used to make annual trips
to this one Dairy Queen in SoCal.
As I recall, he said back in the day (i.e. before internet),
he and a collaborator would scroll
through lists of abstracts at the library
looking for anything interesting.
On one of those library trips,
they came across Lev Bregman’s 1967 paper.
Apparently, the idea went unnoticed for 14 years
until Yair’s 1981 paper introduced these
divergences in the form we use today.
What a good reminder to not just study recent works.

p.s. Thanks are due to reader Liang Dai for introducing me to the area perspective for visualizing Bregman divergences.