PEPit.primitive_steps.inexact_proximal_step
- PEPit.primitive_steps.inexact_proximal_step(x0, f, gamma, opt='PD_gapII')[source]
This routine encodes an inexact proximal operation with step size \(\gamma\). That is, it outputs a tuple \((x, g\in \partial f(x), f(x), w, v\in\partial f(w), f(w), \varepsilon)\) which are described as follows.
First, \(x\) is an approximation to the proximal point of \(x_0\) on function \(f\):
\[x \approx \mathrm{prox}_{\gamma f}(x_0)\triangleq\arg\min_x \left\{ \gamma f(x) + \frac{1}{2}\|x-x_0\|^2\right\},\]where the meaning of \(\approx\) depends on the option “opt” and is explained below. The notions of inaccuracy implemented within this routine are specified using primal and dual proximal problems, denoted by
\begin{eqnarray} &\Phi^{(p)}_{\gamma f}(x; x_0) \triangleq \gamma f(x) + \frac{1}{2}\|x-x_0\|^2,\\ &\Phi^{(d)}_{\gamma f}(v; x_0) \triangleq -\gamma f^*(v)-\frac{1}{2}\|x_0-\gamma v\|^2 + \frac{1}{2}\|x_0\|^2,\\ \end{eqnarray}where \(\Phi^{(p)}_{\gamma f}(x;x_0)\) and \(\Phi^{(d)}_{\gamma f}(v;x_0)\) respectively denote the primal and the dual proximal problems, and where \(f^*\) is the Fenchel conjugate of \(f\). The options below encode different meanings of “\(\approx\)” by specifying accuracy requirements on primal-dual pairs:
\[(x,v) \approx_{\varepsilon} \left(\mathrm{prox}_{\gamma f}(x_0),\,\mathrm{prox}_{f^*/\gamma}(x_0/\gamma)\right),\]where \(\approx_{\varepsilon}\) corresponds to require the primal-dual pair \((x,v)\) to satisfy some primal-dual accuracy requirement:
\[\Phi^{(p)}_{\gamma f}(x;x_0)-\Phi^{(d)}_{\gamma f}(v;x_0) \leqslant \varepsilon,\]where \(\varepsilon\geqslant 0\) is the error magnitude, which is returned to the user so that one can constrain it to be bounded by some other values.
Relation to the exact proximal operation: In the exact case (no error in the computation, \(\varepsilon=0\)), \(v\) corresponds to the solution of the dual proximal problem and one can write
\[x = x_0-\gamma g,\]with \(g=v=\mathrm{prox}_{f^*/\gamma}(x_0/\gamma)\in\partial f(x)\), and \(x=w\).
Reformulation of the primal-dual gap: In regard with the exact proximal computation; the inexact case under consideration here can be described as performing
\[x = x_0-\gamma v + e,\]where \(v\) is an \(\epsilon\)-subgradient of \(f\) at \(x\) (notation \(v\in\partial_{\epsilon} f(x)\)) and \(e\) is some additional computation error. Those elements allow for a common convenient reformulation of the primal-dual gap, written in terms of the magnitudes of \(\epsilon\) and of \(e\):
\[\Phi^{(p)}_{\gamma f}(x;x_0)-\Phi^{(d)}_{\gamma f}(v;x_0) = \frac{1}{2} \|e\|^2 + \gamma \epsilon.\]Options: The following options are available (a list of such choices is presented in [4]; we provide a reference for each of those choices below).
‘PD_gapI’ : the constraint imposed on the output is the vanilla (see, e.g., [2])
\[\Phi^{(p)}_{\gamma f}(x;x_0)-\Phi^{(d)}_{\gamma f}(v;x_0) \leqslant \varepsilon.\]
This approximation requirement is used in one PEPit example: an accelerated inexact forward backward.
‘PD_gapII’ : the constraint is stronger than the vanilla primal-dual gap, as more structure is imposed (see, e.g., [1,5]) :
\[\Phi^{(p)}_{\gamma f}(x;x_0)-\Phi^{(d)}_{\gamma f}(g;x_0) \leqslant \varepsilon,\]
where we imposed that \(v\triangleq g\in\partial f(x)\) and \(w\triangleq x\). This approximation requirement is used in two PEPit examples: in a relatively inexact proximal point algorithm and in a partially inexact Douglas-Rachford splitting.
‘PD_gapIII’ : the constraint is stronger than the vanilla primal-dual gap, as more structure is imposed (see, e.g., [3]):
\[\Phi^{(p)}_{\gamma f}(x;x_0)-\Phi^{(d)}_{\gamma f}(\tfrac{x_0 - x}{\gamma};x_0) \leqslant \varepsilon,\]
where we imposed that \(v \triangleq \frac{x_0 - x}{\gamma}\).
References
- Parameters
- Returns
x (Point) – the approximated proximal point.
gx (Point) – a (sub)gradient of f at x (subgradient used in evaluating the accuracy criterion).
fx (Expression) – f evaluated at x.
w (Point) – a point w such that v (see next output) is a subgradient of f at w.
v (Point) – the approximated proximal point of the dual problem, (sub)gradient of f evaluated at w.
fw (Expression) – f evaluated at w.
eps_var (Expression) – value of the primal-dual gap (which can be further bounded by the user).