Accelerated Proximal Point
wc_accelerated_proximal_point(A0, gammas, n; solver=Clarabel.Optimizer, verbose=true)Problem statement
Compute a PEPit worst-case guarantee for wc_accelerated_proximal_point.
Consider the minimization problem
\[f_\star \triangleq \min_x f(x),\]
where $f$ is convex and possibly non-smooth.
Performance metric
This code computes a worst-case guarantee an accelerated proximal point method, aka fast proximal point method (FPP). That is, it computes the smallest possible $\tau(n, A_0,\vec{\gamma})$ such that the guarantee
\[f(x_n) - f_\star \leqslant \tau(n, A_0, \vec{\gamma}) \left(f(x_0) - f_\star + \frac{A_0}{2} \|x_0 - x_\star\|^2\right)\]
is valid, where $x_n$ is the output of FPP (with step-size $\gamma_t$ at step $t\in \{0, \dots, n-1\}$) and where $x_\star$ is a minimizer of $f$ and $A_0$ is a positive number.
In short, for given values of $n$, $A_0$ and $\vec{\gamma}$, $\tau(n)$ is computed as the worst-case value of $f(x_n)-f_\star$ when $f(x_0) - f_\star + \frac{A_0}{2} \|x_0 - x_\star\|^2 \leqslant 1$, for the following method.
Algorithm
For $t\in \{0, \dots, n-1\}$:
\[ \begin{aligned} y_{t+1} & = & (1-\alpha_{t} ) x_{t} + \alpha_{t} v_t \\ x_{t+1} & = & \arg\min_x \left\{f(x)+\frac{1}{2\gamma_t}\|x-y_{t+1}\|^2 \right\}, \\ v_{t+1} & = & v_t + \frac{1}{\alpha_{t}} (x_{t+1}-y_{t+1}) \end{aligned}\]
with
\[ \begin{aligned} \alpha_{t} & = & \frac{\sqrt{(A_t \gamma_t)^2 + 4 A_t \gamma_t} - A_t \gamma_t}{2} \\ A_{t+1} & = & (1 - \alpha_{t}) A_t \end{aligned}\]
and $v_0=x_0$.
Theoretical guarantee
A theoretical upper bound can be found in [1, Theorem 2.3.]:
\[f(x_n)-f_\star \leqslant \frac{4}{A_0 (\sum_{t=0}^{n-1} \sqrt{\gamma_t})^2}\left(f(x_0) - f_\star + \frac{A_0}{2} \|x_0 - x_\star\|^2 \right).\]
References
The accelerated proximal point was first obtained and analyzed in [1].
Arguments
A0: initial value for parameter A_0.gammas: sequence of step-sizes.n: number of iterations.solver: JuMP optimizer constructor used to solve the generated SDP.verbose: print example and solver progress information when true.
Returns
pepit_tau: worst-case valuetheoretical_tau: theoretical value
Julia usage
pepit_tau, theoretical_tau = wc_accelerated_proximal_point(5, [(i + 1) / 1.1 for i in 0:2], 3; solver=Clarabel.Optimizer, verbose=true)
## Returns approximately: (pepit_tau, theoretical_tau) = (0.015931, 0.051188)