No Lips In Function Value
wc_no_lips_in_function_value(L, gamma, n; solver=Clarabel.Optimizer, verbose=true)Problem statement
Compute a PEPit worst-case guarantee for wc_no_lips_in_function_value.
Consider the constrainted composite convex minimization problem
\[F_\star \triangleq \min_x \{F(x) \equiv f_1(x) + f_2(x)\},\]
where $f_1$ is convex and $L$-smooth relatively to $h$, $h$ being closed proper and convex, and where $f_2$ is a closed convex indicator function.
Performance metric
This code computes a worst-case guarantee for the NoLips method. That is, it computes the smallest possible $\tau(n, L)$ such that the guarantee
\[F(x_n) - F_\star \leqslant \tau(n, L) D_h(x_\star; x_0),\]
is valid, where $x_n$ is the output of the NoLips method, where $x_\star$ is a minimizer of $F$, and where $D_h$ is the Bregman divergence generated by $h$. In short, for given values of $n$ and $L$, $\tau(n, L)$ is computed as the worst-case value of $F(x_n) - F_\star$ when $D_h(x_\star; x_0) \leqslant 1$.
Algorithm
This method (also known as Bregman Gradient, or Mirror descent) can be found in, e.g., [2, Algorithm 1]. For $t \in \{0, \dots, n-1\}$,
\[x_{t+1} = \arg\min_{u} \{f_2(u)+\langle \nabla f_1(x_t) \mid u - x_t \rangle + \frac{1}{\gamma} D_h(u; x_t)\}.\]
Theoretical guarantee
The tight guarantee obtained in [2, Theorem 1] is
\[F(x_n) - F_\star \leqslant \frac{1}{\gamma n} D_h(x_\star; x_0),\]
for any $\gamma \leq \frac{1}{L}$; tightness is provided in [2, page 23].
References
NoLips was proposed [1] for convex problems involving relative smoothness. The worst-case analysis using a PEP, as well as the tightness are provided 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_in_function_value(L, gamma, 3; verbose=true)
## Returns approximately: (pepit_tau, theoretical_tau) = (0.666667, 0.666667)