No Lips 1

Source file

wc_no_lips_1(L, gamma, n; solver=Clarabel.Optimizer, verbose=true)

Problem statement

Compute a PEPit worst-case guarantee for wc_no_lips_1.

Consider the constrainted non-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 and $L$-smooth relatively to $h$, and where $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+1}; x_t) \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+1}; x_t)$ 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

The tight theoretical upper bound is obtained in [1, Proposition 4.1]

\[\min_{0 \leqslant t \leqslant n-1} D_h(x_{t+1}; x_t) \leqslant \frac{\gamma}{n(1 - L\gamma)}(F(x_0) - F(x_n))\]

References

The detailed setup and results are availaible in [1]. The PEP approach for studying such settings is presented in [2].

[1] J. Bolte, S. Sabach, M. Teboulle, Y. Vaisbourd (2018). First order methods beyond convexity and Lipschitz gradient continuity with applications to quadratic inverse problems. SIAM Journal on Optimization, 28(3), 2131-2151.

[2] R. Dragomir, A. Taylor, A. d'Aspremont, J. Bolte (2021). Optimal complexity and certification of Bregman first-order methods. Mathematical Programming, 1-43.

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_1(L, gamma, 5; verbose=true)
## Returns approximately: (pepit_tau, theoretical_tau) = (0.2, 0.2)