No Lips 2
wc_no_lips_2(L, gamma, n; solver=Clarabel.Optimizer, verbose=true)Problem statement
Compute a PEPit worst-case guarantee for wc_no_lips_2.
Consider the constrainted composite convex minimization problem
\[F_\star \triangleq \min_x \{F(x) \equiv f_1(x)+f_2(x) \}\]
where $f_2$ is a closed convex indicator function and $f_1$ is possibly non-convex, $L$-smooth relatively to $h$, and $h$ is closed proper and convex.
Performance metric
This code computes a worst-case guarantee for the NoLips method. That is, it computes the smallest possible $\tau(n,L,\gamma)$ such that the guarantee
\[\min_{0 \leqslant t \leqslant n-1} D_h(x_t;x_{t+1}) \leqslant \tau(n, L, \gamma) (F(x_0) - F(x_n))\]
is valid, where $x_n$ is the output of the NoLips method, and where $D_h$ is the Bregman distance generated by $h$:
\[D_h(x; y) \triangleq h(x) - h(y) - \nabla h (y)^T(x - y).\]
In short, for given values of $n$, $L$, and $\gamma$, $\tau(n, L, \gamma)$ is computed as the worst-case value of $\min_{0 \leqslant t \leqslant n-1}D_h(x_t;x_{t+1})$ when $F(x_0) - F(x_n) \leqslant 1$.
Algorithm
This method (also known as Bregman Gradient, or Mirror descent) can be found in, e.g., [1, Section 3]. For $t \in \{0, \dots, n-1\}$,
\[x_{t+1} = \arg\min_{u \in R^d} \nabla f(x_t)^T(u - x_t) + \frac{1}{\gamma} D_h(u; x_t).\]
Theoretical guarantee
An empirically tight worst-case guarantee is
\[\min_{0 \leqslant t \leqslant n-1}D_h(x_t;x_{t+1}) \leqslant \frac{\gamma}{n}(F(x_0) - F(x_n)).\]
References
The detailed setup is presented in [1]. The PEP approach for studying such settings is presented in [2].
DISCLAIMER: This example requires some experience with PEPit and PEPs (see Section 4 in [2]).
Arguments
L: smoothness or Lipschitz parameter, as used by the modeled class.gamma: step-size parameter.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 value.theoretical_tau: theoretical value.
Julia usage
pepit_tau, theoretical_tau = wc_no_lips_2(L, gamma, 3; verbose=true)
## Returns approximately: (pepit_tau, theoretical_tau) = (0.333333, 0.333333)