Bregman Proximal Point
wc_bregman_proximal_point(gamma, n; verbose=true)Problem statement
Compute a PEPit worst-case guarantee for wc_bregman_proximal_point.
Consider the composite convex minimization problem
\[F_\star \triangleq \min_x \{F(x) \equiv f_1(x)+f_2(x) \}\]
where $f_1(x)$ and $f_2(x)$ are closed convex proper functions.
Performance metric
This code computes a worst-case guarantee for Bregman Proximal Point method. That is, it computes the smallest possible $\tau(n, \gamma)$ such that the guarantee
\[F(x_n) - F(x_\star) \leqslant \tau(n, \gamma) D_{f_1}(x_\star; x_0)\]
is valid, where $x_n$ is the output of the Bregman Proximal Point (BPP) method, where $x_\star$ is a minimizer of $F$, and when $D_{f_1}$ is the Bregman distance generated by $f_1$.
Algorithm
Bregman proximal point is described in [1, Section 2, equation (9)]. For $t \in \{0, \dots, n-1\}$,
\[ \begin{aligned} x_{t+1} & = & \arg\min_{u \in R^n} f_1(u) + \frac{1}{\gamma} D_{f_2}(u; x_t), \\ D_h(x; y) & = & h(x) - h(y) - \nabla h (y)^T(x - y). \end{aligned}\]
Theoretical guarantee
A tight empirical guarantee can be guessed from the numerics
\[F(x_n) - F(x_\star) \leqslant \frac{1}{\gamma n} D_{f_1}(x_\star, x_0).\]
References
Arguments
gamma: step-size parameter.n: number of iterations.verbose: print example and solver progress information when true.
Returns
pepit_tau: worst-case value.theoretical_tau: theoretical value.
Julia usage
PEPit_tau, theoretical_tau = wc_bregman_proximal_point(3.0, 5; verbose=true)
## Returns approximately: (PEPit_tau, theoretical_tau) = (0.066667, 0.066667)