Optimistic Gradient
wc_optimistic_gradient(n, gamma, L; solver=Clarabel.Optimizer, verbose=true)Problem statement
Compute a PEPit worst-case guarantee for wc_optimistic_gradient.
Consider the monotone variational inequality
\[\mathrm{Find}\, x_\star \in C\text{ such that } \left<F(x_\star);x-x_\star\right> \geqslant 0\,\,\forall x\in C,\]
where $C$ is a closed convex set and $F$ is maximally monotone and Lipschitz.
Performance metric
This code computes a worst-case guarantee for the optimistic gradient method. That, it computes the smallest possible $\tau(n)$ such that the guarantee
\[\|\tilde{x}_n - \tilde{x}_{n-1}\|^2 \leqslant \tau(n) \|x_0 - x_\star\|^2,\]
is valid, where $\tilde{x}_n$ is the output of the optimistic gradient method and $x_0$ its starting point.
Algorithm
The optimistic gradient method is described as follows, for $t \in \{ 0, \dots, n-1\}$,
\[ \begin{aligned} \tilde{x}_{t} & = & \mathrm{Proj}_{C} [x_t-\gamma F(\tilde{x}_{t-1})], \\ {x}_{t+1} & = & \tilde{x}_t + \gamma (F(\tilde{x}_{t-1}) - F(\tilde{x}_t)). \end{aligned}\]
where $\gamma$ is some step-size.
Theoretical guarantee
The method and many variants of it are discussed in [1] and a PEP formulation suggesting a worst-case guarantee in $O(1/n)$ can be found in [2, Appendix D].
References
Arguments
n: number of iterations.gamma: step-size parameter.L: smoothness or Lipschitz parameter, as used by the modeled class.solver: JuMP optimizer constructor used to solve the generated SDP.verbose: print example and solver progress information when true.
Returns
pepit_tau: worst-case value.theoretical_tau: no theoretical bound.
Julia usage
pepit_tau, theoretical_tau = wc_optimistic_gradient(5, 1 / 4, 1; solver=Clarabel.Optimizer, verbose=true)
## Returns approximately: (pepit_tau, theoretical_tau) = (0.066314, nothing)