Convex Analysis for Bandits

Corresponds to Lattimore & Szepesvári, Part VI introduction and Chapter 26.

Motivation: why bandits need convex analysis

IntuitionWhere Part VI is headed

The adversarial linear bandit looks like the stochastic linear bandit with $\theta$ chosen by an adversary. Its algorithms combine optimal design (Chapter 21) with exponential weights (Chapter 11). But the two models differ in subtle ways (Chapter 29), and with large or infinite action sets Exp3-style algorithms are computationally hopeless. The efficient alternatives, mirror descent and follow-the-regularised-leader (adversarial-linear-bandits), are built from the objects in this note:

Tool	Role in the algorithms
Convex functions and Jensen	regret bounds, potential arguments
Fenchel dual	moving between “primal” (actions) and “dual” (gradients/scores)
Bregman divergence	the problem-adapted “distance” that replaces $\frac12\lVert x - y\rVert^2$
Legendre functions	regularisers whose gradient map is invertible and keeps iterates inside the domain
First-order optimality	characterising each update step
Bregman projections	pulling an update back into the feasible set

NoteScope

Extremely brief: definitions and statements, with standard texts (Rockafellar, Convex Analysis; Boyd–Vandenberghe) for most proofs. Topological terms (interior, closed, boundary) are recalled in Notes.

Convex sets and functions

DefinitionConvex set and convex hull

$A\subseteq\mathbb R^d$ is convex if $\alpha x + (1-\alpha)y\in A$ for all $x,y\in A$ and $\alpha\in(0,1)$ . The convex hull $\mathrm{co}(A)$ is the smallest convex set containing $A$ . For finitely many points,

$\mathrm{co}(x_1, \ldots, x_n) = \Big\{\sum_{i=1}^np_ix_i : p\in\mathcal P_{n-1}\Big\}$

(all mixtures). Compare the convex-hull reduction for lower bounds.

DefinitionConvex function (Def. 26.1)

Work on the extended reals $\bar{\mathbb R} = \mathbb R\cup\{\pm\infty\}$ . A function $f : \mathbb R^d\to\bar{\mathbb R}$ is convex if its epigraph

$E_f = \{(x,y)\in\mathbb R^d\times\mathbb R : y\ge f(x)\}$

is a convex set (“epi” = upon: the points sitting on top of the graph).

Term	Meaning
Domain	$\mathrm{dom}(f) = \{x : f(x) < \infty\}$
Restriction convention	$f : S\to\bar{\mathbb R}$ is extended by $+\infty$ off $S$ , so a real-valued $f$ on $S$ has $\mathrm{dom}(f) = S$ : constraints become infinite values
Proper	never $-\infty$ , and nonempty domain
”Let $f$ be convex”	from now on: $f : \mathbb R^d\to\bar{\mathbb R}$ proper convex
Strictly convex	the inequality below is always strict
Concave	$-f$ is convex

FormulaThe familiar inequality

For convex $f$ , all $x,y$ (with the infinity arithmetic) and $\alpha\in(0,1)$ ,

$f(\alpha x + (1-\alpha)y)\le\alpha f(x) + (1-\alpha)f(y) \tag{26.1}$

Some authors take (26.1) plus a convex domain as the definition. Allowing the value $-\infty$ is a convenience, since some operations (infimal convolution) can produce it, but it never matters in the book.

TheoremBasic facts

Continuity: convex functions are continuous on $\mathrm{int}(\mathrm{dom}f)$ (Exercise 26.1). Discontinuities can only occur at the boundary.
Second-order test: if $f$ is twice differentiable on the interior of its domain, it is convex iff $\nabla^2f(x)\succeq0$ there.
Local is global: every local minimum of a convex function is global. This is why convex problems are (usually) efficiently solvable by gradient-type methods. (A function can have all local minima global without being convex.)

DefinitionFenchel dual (convex conjugate)

$f^*(u) = \sup_{x\in\mathbb R^d}\big(\langle x,u\rangle - f(x)\big)$

It is convex as a supremum of affine functions of $u$ . If $f$ is proper convex with a closed epigraph, then $f^{**} = f$ (biduality). In general $f^{**}\le f$ , with equality on the interior of the domain for differentiable convex $f$ (Exercise 26.3).

Component	Detail
Signature	$f^* : \mathbb R^d\to\bar{\mathbb R}$ , a function of the “slope” $u$
Meaning	$-f^*(u)$ is the intercept of the best affine minorant of $f$ with slope $u$
Key property	for nice $f$ , $\nabla f^* = (\nabla f)^{-1}$ (Theorem 26.6)
Fenchel–Young	$f(x) + f^*(u)\ge\langle x,u\rangle$ , immediate from the definition

RemarkWe have met the dual before

The large-deviation rate function $\psi^*$ is the Fenchel dual of the cumulant-generating function (Chapter 5).
The method of mixtures linearised a quadratic with $\frac12\lVert S\rVert^2_{V^{-1}} = \max_x\langle x,S\rangle - \frac12\lVert x\rVert_V^2$ , i.e. $f^{**} = f$ for $f = \frac12\lVert\cdot\rVert_V^2$ (Chapter 20).

Jensen’s inequality

TheoremTheorem 26.2 — Jensen

Let $f$ be measurable and convex, and $X$ an $\mathbb R^d$ -valued random element with $\mathbb E[X]$ existing and $X\in\mathrm{dom}(f)$ a.s. Then

$\mathbb E[f(X)]\ge f(\mathbb E[X])$

The inequality reverses for concave $f$ . (Allowing integrals to equal $\infty$ removes the domain condition: if $X\notin\mathrm{dom}f$ with positive probability, the left side is $\infty$ .) (26.1) is the two-point case, and Jensen can itself serve as the definition of convexity.

ProofGraphical proof (finite support) and the general route

Finite support: let $\mathbb P(X = x_k) = p_k$ and $\bar x = \sum_kp_kx_k$ . The point $(\bar x,\sum_kp_kf(x_k))$ is a mixture of the points $(x_k,f(x_k))$ , so it lies in their convex hull, which sits inside the convex epigraph $E_f$ . So it is on or above $(\bar x,f(\bar x))$ , which lies on the lower boundary of $E_f$ .

General case (Exercise 26.2): take a supporting hyperplane to $E_f$ at $(x_0,f(x_0))$ with $x_0 = \mathbb E[X]$ . It gives an affine $g$ with $g(x_0) = f(x_0)$ and $g\le f$ , so $\mathbb E f(X)\ge\mathbb Eg(X) = g(\mathbb EX) = f(\mathbb EX)$ .

∎

NoteUsed throughout

Gibbs’ inequality, data processing, concavity of entropy (Cover & Thomas), moving a max inside an expectation (the adversarial-to-stochastic reduction), and the Bretagnolle–Huber proof all rest on Jensen.

Bregman divergence

DefinitionBregman divergence induced by $f$

For convex $f$ and $y\in\mathrm{dom}(f)$ ,

$D_f(x,y) = f(x) - f(y) - \nabla_{x-y}f(y)$

where $\nabla_vf(y) = \lim_{h\to0^+}\frac{f(y + hv) - f(y)}h\in\bar{\mathbb R}$ is the directional derivative, which always exists for convex $f$ but may be infinite. If $f$ is differentiable at $y$ ,

$D_f(x,y) = f(x) - f(y) - \langle x - y,\nabla f(y)\rangle$

$\mathrm{dom}(\nabla f)$ denotes the points where $f$ is differentiable.

IntuitionThe error of the tangent-plane approximation

$D_f(x,y)$ is how far $f(x)$ sits above the first-order Taylor approximation of $f$ built at $y$ . For convex $f$ the tangent plane is a global under-estimator, so the gap is nonnegative. Curvature makes it large: flat directions of $f$ contribute nothing.

TheoremTheorem 26.3 — Basic properties

$D_f(x,y)\ge0$ for all $y\in\mathrm{dom}(f)$ .
$D_f(x,x) = 0$ for $x\in\mathrm{dom}(f)$ .
$x\mapsto D_f(x,y)$ is convex for every $y\in\mathrm{dom}(\nabla f)$ .

Part 3 can fail if $f$ isn’t differentiable at $y$ (Exercise 26.14). $\sqrt{D_f}$ behaves somewhat like a metric, and is one for some $f$ , but in general $D_f$ is asymmetric and violates the triangle inequality.

ExampleExample 26.4 — Squared Euclidean distance

$f(x) = \frac12\lVert x\rVert_2^2$ , $\nabla f(x) = x$ :

$D_f(x,y) = \frac12\lVert x\rVert^2 - \frac12\lVert y\rVert^2 - \langle x - y,y\rangle = \frac12\lVert x - y\rVert_2^2$

ExampleExample 26.5 — Unnormalised negentropy gives relative entropy

$f(x) = \sum_i(x_i\log x_i - x_i)$ on $[0,\infty)^d$ (with $0\log0 = 0$ ), and $\nabla f(y) = \log y$ for $y > 0$ :

$D_f(x,y) = \sum_ix_i\log\frac{x_i}{y_i} + \sum_i(y_i - x_i)$

On the simplex the second sum vanishes and $D_f(x,y)$ is exactly the relative entropy $D(x\Vert y)$ . If some $y_i = 0 < x_i$ , the divergence is infinite. This regulariser drives exponential weights: mirror descent with it on the simplex is Exp3/Hedge.

Legendre functions

DefinitionLegendre function

Let $f$ be convex with $A = \mathrm{dom}(f)$ and $C = \mathrm{int}(A)$ . Then $f$ is Legendre if

$C\ne\emptyset$ ;
$f$ is differentiable and strictly convex on $C$ ;
$\lVert\nabla f(x_n)\rVert_2\to\infty$ for every sequence in $C$ converging to a point of $\partial C$ .

IntuitionA dish with ever-steepening edges

The graph of a Legendre function is a bowl whose walls become vertical at the boundary of its domain, as with $-\sqrt x$ at 0. Minimising such a function (plus anything linear) can never land on the boundary, so iterates of mirror descent stay strictly inside the domain automatically, for example keeping all probabilities positive.

TheoremTheorem 26.6 — Duality for Legendre functions

If $f$ is Legendre:

$\nabla f$ is a bijection from $\mathrm{int}(\mathrm{dom}f)$ to $\mathrm{int}(\mathrm{dom}f^*)$ , with inverse $(\nabla f)^{-1} = \nabla f^*$ ;
$D_f(x,y) = D_{f^*}(\nabla f(y),\nabla f(x))$ for $x,y\in\mathrm{int}(\mathrm{dom}f)$ (note the swapped order);
$f^*$ is Legendre.

ImportantMirror maps

$\nabla f$ maps a point (for example a distribution over actions) to its “dual” coordinates (for example log-weights or scores). $\nabla f^*$ maps back. Mirror descent takes gradient steps in the dual space and maps back: a step that would be awkward in the primal (staying in the simplex) is trivial in the dual.

TheoremProposition 26.7 and Corollary 26.8 — No minimisers on the boundary

If $f$ is Legendre, $x\in\mathrm{int}(\mathrm{dom}f)$ and $y\in\partial\,\mathrm{int}(\mathrm{dom}f)$ , then $\lim_{\alpha\to1}\langle y - x,\nabla f((1-\alpha)x + \alpha y)\rangle = \infty$ : along any straight path to the boundary, the slope blows up. Hence any minimiser of $f$ over $\mathrm{dom}(f)$ lies in the interior (Exercise 26.6).

ExampleExample 26.9 — The self-dual case

$f = \frac12\lVert\cdot\rVert_2^2$ on $\mathbb R^d$ : $f^* = f$ , and $\nabla f = \nabla f^* = \mathrm{id}$ . There is no boundary, so condition 3 holds vacuously.

ExampleExample 26.10 — $f(x) = -2\sum_i\sqrt{x_i}$ on $[0,\infty)^d$ (Exercise 26.8)

$\nabla f(x) = -1/\sqrt x$ (componentwise), which blows up as any $x_i\to0$ , and $f$ is strictly convex, so $f$ is Legendre. ( $\lVert\nabla f\rVert\to0$ as $\lVert x\rVert\to\infty$ , but " $\infty$ " isn’t part of the boundary.)

Bregman: $D_f(x,y) = \sum_i\frac{(\sqrt{x_i} - \sqrt{y_i})^2}{\sqrt{y_i}}$ .
Dual: maximise $x_iu_i + 2\sqrt{x_i}$ in each coordinate. For $u_i < 0$ the maximiser is $x_i = 1/u_i^2$ , giving $f^*(u) = -\sum_i\frac1{u_i}\ \text{ on }(-\infty,0)^d\ (\infty\text{ otherwise}), \qquad\nabla f^*(u) = \frac1{u^2}$ so $\mathrm{dom}(\nabla f^*) = (-\infty,0)^d$ , and $\nabla f^*(\nabla f(x)) = \nabla f^*(-1/\sqrt x) = x$ .
Dual Bregman: $D_{f^*}(u,v) = -\sum_i\frac{(u_i - v_i)^2}{u_iv_i^2}$ . Check of Theorem 26.6(2): with $u = -1/\sqrt y$ and $v = -1/\sqrt x$ , this equals $\sum(\sqrt x - \sqrt y)^2/\sqrt y = D_f(x,y)$ .

This regulariser underlies the $O(\sqrt{nk})$ Tsallis-INF-type bandit algorithms that remove Exp3’s $\sqrt{\log k}$ . (Computations worked here.)

ExampleExample 26.11 — Unnormalised negentropy (Exercise 26.9)

$\nabla f(x) = \log x$ blows up at the boundary and $f$ is strictly convex, so $f$ is Legendre. Its dual is

$f^*(u) = \sum_ie^{u_i}, \qquad\nabla f^*(u) = e^u, \qquad\mathrm{dom}(\nabla f^*) = \mathbb R^d$

(maximise $x_iu_i - x_i\log x_i + x_i$ at $x_i = e^{u_i}$ ), and

$D_{f^*}(u,v) = \sum_i\Big(e^{v_i}(v_i - u_i) + e^{u_i} - e^{v_i}\Big)$

The mirror map is “log weights ↔ weights”: exactly the exponential-weights update. (Dual computed here.)

ExampleWhich functions are Legendre? (Exercise 26.4)

$f$ on domain	Legendre?	Reason
$x^2$ on $[-1,1]$	No	gradient stays bounded at $\pm1$
$-\sqrt x$ on $[0,\infty)$	Yes	the archetype
$\log(1/x)$ , $f(0) = \infty$	Yes	domain $(0,\infty)$ ; $f'(x) = -1/x\to-\infty$ at 0
$x\log x$ on $[0,\infty)$	Yes	$f' = \log x + 1\to-\infty$ at 0
$\lvert x\rvert$ on $\mathbb R$	No	neither differentiable nor strictly convex
$\max\{\lvert x\rvert,x^2\}$ on $\mathbb R$	No	equals $\lvert x\rvert$ on $[-1,1]$ : kink at 0, linear pieces

(Answers worked here.) Adding a linear term preserves Legendre-ness (Exercise 26.10).

Bregman divergences as local quadratics

FormulaSecond-order intuition

With $g(y) = D_f(x,y)$ : $g(x) = 0$ , $\nabla g(x) = 0$ , and the Hessian at $x$ is $\nabla^2f(x)$ , so $D_f(x,y)\approx\frac12\lVert y - x\rVert^2_{\nabla^2f(x)}$ . Locally, a Bregman divergence is a squared norm in the Hessian’s geometry. The approximation can be poor when $x, y$ are far apart.

TheoremTheorem 26.12 — Exact Hessian form

If $f$ is convex and twice differentiable on $A = \mathrm{int}(\mathrm{dom}f)$ and $x,y\in A$ , then for some $z$ on the segment $[x,y]$ ,

$D_f(x,y) = \frac12(x - y)^\top\nabla^2f(z)(x - y) \tag{26.2}$

If $\nabla^2f$ is continuous, $z = g(x,y)$ can be chosen measurably, by a measurable-selection theorem (Kuratowski–Ryll-Nardzewski; Exercise 26.15). This matters when $x, y$ are random. With $\nabla^2f(z)\succ0$ this is $\frac12\lVert x - y\rVert^2_{\nabla^2f(z)}$ .

TheoremTheorem 26.13 — The key inequality for mirror descent

Let $\eta > 0$ and $f$ Legendre and twice differentiable with $\nabla^2f\succ0$ on $A = \mathrm{int}(\mathrm{dom}f)$ . For all $x,y\in A$ and $u\in\mathbb R^d$ , there is $z\in[x,y]$ with

$\langle x - y,u\rangle - \frac{D_f(x,y)}\eta\le\frac\eta2\lVert u\rVert^2_{(\nabla^2f(z))^{-1}}$

ProofCauchy–Schwarz in the Hessian norm, then maximise a quadratic

Pick $z$ with $D_f(x,y) = \frac12\lVert x - y\rVert_H^2$ , $H = \nabla^2f(z)$ . Then $\langle x - y,u\rangle\le\lVert x - y\rVert_H\lVert u\rVert_{H^{-1}} = \lVert u\rVert_{H^{-1}}\sqrt{2D_f(x,y)}$ , so the left side is at most $a s - b s^2$ with $s = \sqrt{2D_f}$ , $a = \lVert u\rVert_{H^{-1}}$ and $b = \frac1{2\eta}$ . Use $\max_s(as - bs^2) = \frac{a^2}{4b} = \frac\eta2\lVert u\rVert^2_{H^{-1}}$ .

∎

IntuitionGain versus movement cost

$\langle x - y,u\rangle$ is how much a step from $y$ to $x$ gains against a loss vector $u$ ; $D_f(x,y)/\eta$ is the price of moving. The net benefit is bounded by $\eta\times$ the local dual norm of $u$ . In bandit analyses $u$ is an importance-weighted loss estimate, and the regulariser’s Hessian at the current point is exactly what tames its variance. This is the generalisation of $\sum_jP_{tj}\hat X_{tj}^2$ in the Exp3 proof: for negentropy, $(\nabla^2f)^{-1} = \mathrm{diag}(x)$ , so $\lVert u\rVert^2_{(\nabla^2f)^{-1}} = \sum_ix_iu_i^2$ .

Optimisation

TheoremFirst-order optimality

Unconstrained: for convex differentiable $f$ , $\nabla f(x) = 0$ is necessary and sufficient for $x$ to be a minimiser. Constrained: for convex differentiable $f$ and nonempty convex $A$ ,

$x^*\in\arg\min_{x\in A}f(x)\iff\langle x - x^*,\nabla f(x^*)\rangle\ge0\ \ \forall x\in A \tag{26.3}$

IntuitionA supporting hyperplane

If $\nabla f(x^*)\ne0$ , the hyperplane through $x^*$ with normal $\nabla f(x^*)$ must support $A$ at $x^*$ , with all of $A$ on the side the gradient points into. Otherwise some feasible direction makes an acute angle with $-\nabla f(x^*)$ , and a small step along it stays in $A$ and decreases $f$ . Conversely, by convexity $f(x)\ge f(x^*) + \langle x - x^*,\nabla f(x^*)\rangle\ge f(x^*)$ .

TheoremProposition 26.14 — Nondifferentiable and Legendre versions

For convex $f : \mathbb R^d\to\bar{\mathbb R}$ , nonempty convex $A$ , and $x^*\in\mathrm{dom}(\nabla f)$ :

$x^*\in\arg\min_{x\in A}f(x)\iff\langle x - x^*,\nabla f(x^*)\rangle\ge0\ \ \forall x\in A\cap\mathrm{dom}(f) \tag{26.4}$

If $f$ is Legendre, any constrained minimiser automatically lies in $\mathrm{dom}(\nabla f)$ (it is interior by Corollary 26.8, and $\mathrm{int}(\mathrm{dom}f) = \mathrm{dom}(\nabla f)$ by Theorem 26.6), so (26.4) always applies.

RemarkAlready used

The Kiefer–Wolfowitz proof (Chapter 21) is exactly (26.3) for the concave $\log\det$ over the simplex: maximality iff $\langle\nabla f(\pi^*),\pi - \pi^*\rangle\le0$ for all designs $\pi$ .

Projections

DefinitionEuclidean and Bregman projections

$\Pi_A(x) = \arg\min_{y\in A}\lVert x - y\rVert_2^2, \qquad\Pi_{A,f}(x) = \arg\min_{y\in A}D_f(y,x)$

Note that the projected point goes in the first argument of $D_f$ .

TheoremTheorem 26.15 — Constrained minimisation = unconstrained minimisation + projection

Let $f$ be Legendre, $A$ nonempty, closed and convex with $A\cap\mathrm{dom}(f)\ne\emptyset$ , and suppose $\tilde y = \arg\min_zf(z)$ exists. Then

$y = \arg\min_{z\in A}f(z)$ exists and is unique;
$y = \arg\min_{z\in A}D_f(z,\tilde y)$ , the Bregman projection of $\tilde y$ .

The existence of $\tilde y$ is needed: $-\sqrt x$ is Legendre on $[0,\infty)$ but has no minimiser.

IntuitionWhy this is the shape of mirror descent and FTRL

Each step minimises “linearised loss + regulariser” over the action set. Theorem 26.15 says: solve the unconstrained problem (often in closed form, via the mirror map) and then project. Since $\nabla f(\tilde y) = 0$ , $D_f(z,\tilde y) = f(z) - f(\tilde y)$ , so projecting $\tilde y$ and minimising $f$ over $A$ are literally the same problem. Adding a linear term $\langle z,u\rangle$ keeps $f$ Legendre (Exercise 26.10), which covers the actual updates.

ExampleNegentropy projections (Exercises 26.11–26.12)

Onto the simplex: for $y\in(0,\infty)^d$ , $\arg\min_{x\in\mathcal P_{d-1}}D_f(x,y) = y/\lVert y\rVert_1$ . Normalisation is a KL projection, which is why exponential weights simply renormalise.
Onto the capped simplex $\mathcal P_{d-1}\cap[\alpha,1]^d$ (forced exploration): with $y$ sorted increasingly and $m$ the smallest index with $y_m(1 - (m-1)\alpha)\ge\alpha\sum_{j\ge m}y_j$ , the projection sets the $m-1$ smallest coordinates to $\alpha$ and rescales the rest proportionally: $x_i = (1 - (m-1)\alpha)y_i/\sum_{j\ge m}y_j$ for $i\ge m$ .

TheoremGeneralised Pythagorean inequality (Exercise 26.13)

If $A$ is closed and convex, $x\in A$ , $z = \Pi_{A,f}(y)$ , and $f$ is differentiable at $y$ , then

$D_f(x,y)\ge D_f(x,z) + D_f(z,y)$

Projecting onto a convex set only brings you closer (in $D_f$ ) to every point of the set, which is what makes projected steps safe in regret proofs. The differentiability assumption cannot be dropped.

Notes

ConventionInfinity arithmetic

$\alpha + \infty = \infty$ for $\alpha > -\infty$ ; $\alpha - \infty = -\infty$ for $\alpha < \infty$ ; $\alpha\cdot(\pm\infty) = \pm\infty$ for $\alpha > 0$ (signs flip for $\alpha < 0$ ); $0\cdot(\pm\infty) = 0$ ; $\infty - \infty$ (like $\alpha/0$ ) is undefined; $-\infty\le\alpha\le\infty$ .

DefinitionTopology in $\mathbb R^d$

Interior point of $A$ : some ball $B_\varepsilon(x)\subseteq A$ . $\mathrm{int}(A)$ is the set of interior points.
Open: $\mathrm{int}(A) = A$ . Closed: the complement is open.
Boundary $\partial A$ : points every ball around which meets both $A$ and $A^c$ (they need not lie in $A$ ). Examples: $\partial[0,\infty) = \partial(0,\infty) = \{0\}$ , $\partial\mathbb R^n = \emptyset$ .

Quick reference

Object	Statement	Note
Convex function	epigraph convex; $f(\alpha x + (1-\alpha)y)\le\alpha f(x) + (1-\alpha)f(y)$	constraints as $+\infty$
Fenchel dual	$f^*(u) = \sup_x\langle x,u\rangle - f(x)$	$f^{**} = f$ (closed epigraph); Fenchel–Young
Jensen	$\mathbb Ef(X)\ge f(\mathbb EX)$	supporting hyperplane
Bregman	$D_f(x,y) = f(x) - f(y) - \langle x - y,\nabla f(y)\rangle\ge0$	asymmetric; convex in $x$
Euclidean	$f = \frac12\lVert\cdot\rVert^2\Rightarrow D_f = \frac12\lVert x - y\rVert^2$	self-dual
Negentropy	$f = \sum x\log x - x\Rightarrow D_f = \sum x\log\frac xy + y - x$	KL on the simplex; $f^* = \sum e^u$
$-2\sum\sqrt x$	$D_f = \sum\frac{(\sqrt x - \sqrt y)^2}{\sqrt y}$ ; $f^* = -\sum1/u$	Tsallis-type regulariser
Legendre	strictly convex, differentiable, gradient blows up at boundary	minimisers interior
Duality	$\nabla f^* = (\nabla f)^{-1}$ ; $D_f(x,y) = D_{f^*}(\nabla f(y),\nabla f(x))$	mirror maps
Hessian form	$D_f(x,y) = \frac12\lVert x - y\rVert^2_{\nabla^2f(z)}$ , $z\in[x,y]$	measurable choice of $z$
Key inequality	$\langle x - y,u\rangle - D_f(x,y)/\eta\le\frac\eta2\lVert u\rVert^2_{(\nabla^2f(z))^{-1}}$	local-norm regret term
Optimality	$\langle x - x^,\nabla f(x^)\rangle\ge0\ \forall x\in A$	supporting hyperplane
Projection	constrained min = Bregman projection of unconstrained min	Legendre $f$
Simplex KL projection	$y/\lVert y\rVert_1$	renormalisation
Pythagoras	$D_f(x,y)\ge D_f(x,z) + D_f(z,y)$ for $z = \Pi_{A,f}(y)$	projections never hurt

Facts to keep to hand

Bregman divergences generalise squared distance. They are the gap between $f$ and its tangent plane: nonnegative, convex in the first argument, asymmetric, and locally a squared norm in $f$ ‘s Hessian geometry. Negentropy gives KL, which is why exponential weights is mirror descent.
Legendre regularisers are self-enforcing barriers. Their gradients blow up at the boundary, so minimisers stay interior. Their gradient maps invert each other across the Fenchel dual, giving primal (weights) ↔ dual (scores) mirror maps.
One inequality drives the regret analyses. “Gain minus movement cost” is at most $\frac\eta2\lVert u\rVert^2_{(\nabla^2f)^{-1}}$ . The regulariser’s curvature at the current point is what controls the variance of the loss estimates.
Constrained steps = unconstrained steps + Bregman projection, and projections only bring you closer to every feasible point (Pythagoras). First-order optimality is the supporting-hyperplane condition.

References

Lattimore & Szepesvári, Bandit Algorithms — Part VI introduction; Chapter 26
Rockafellar, Convex Analysis (2015 reprint) — Fenchel duality (Part III), Legendre functions (Part V)
Boyd & Vandenberghe, Convex Optimization (2004)

Related

Motivation: why bandits need convex analysis

Convex sets and functions

Jensen’s inequality

Bregman divergence

Legendre functions

Bregman divergences as local quadratics

Optimisation

Projections

Notes

Quick reference

References

Mentioned in