PEPit.primitive_steps.bregman_gradient_step

PEPit.primitive_steps.bregman_gradient_step(gx0, sx0, mirror_map, gamma)

This routine outputs \(x\) by performing a mirror step of step-size \(\gamma\). That is, denoting \(f\) the function to be minimized and \(h\) the mirror map, it performs

\[x = \arg\min_x \left[ f(x_0) + \left< \nabla f(x_0);\, x - x_0 \right> + \frac{1}{\gamma} D_h(x; x_0) \right],\]

where \(D_h(x; x_0)\) denotes the Bregman divergence of \(h\) on \(x\) with respect to \(x_0\).

\[D_h(x; x_0) \triangleq h(x) - h(x_0) - \left< \nabla h(x_0);\, x - x_0 \right>.\]

Warning

The mirror map \(h\) is assumed differentiable.

By differentiating the previous objective function, one can observe that

\[\nabla h(x) = \nabla h(x_0) - \gamma \nabla f(x_0).\]

Parameters

• sx0 (Point) – starting gradient \(\textbf{sx0} \triangleq \nabla h(x_0)\).

• gx0 (Point) – descent direction \(\textbf{gx0} \triangleq \nabla f(x_0)\).

• mirror_map (Function) – the reference function \(h\) we computed Bregman divergence of.

• gamma (float) – step size.

Returns

• x (Point) – new iterate \(\textbf{x} \triangleq x\).

• sx (Point) – \(h\)’s gradient on new iterate \(x\) \(\textbf{sx} \triangleq \nabla h(x)\).

• hx (Expression) – \(h\)’s value on new iterate \(\textbf{hx} \triangleq h(x)\).