No Lips In Bregman Divergence
wc_no_lips_in_bregman_divergence(L, gamma, n; solver=Clarabel.Optimizer, verbose=true)Problem statement
Compute a PEPit worst-case guarantee for wc_no_lips_in_bregman_divergence.
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
\[\min_{t\leqslant n} D_h(x_{t-1}; x_t) \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 $\min_{t\leqslant n} D_h(x_{t-1}; x_t)$ 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 upper guarantee obtained in [2, Proposition 4] is
\[\min_{t\leqslant n} D_h(x_{t-1}; x_t) \leqslant \frac{2}{n (n - 1)} D_h(x_\star; x_0),\]
for any $\gamma \leq \frac{1}{L}$. It is empirically tight.
References
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_bregman_divergence(L, gamma, 10; verbose=true)
## Returns approximately: (pepit_tau, theoretical_tau) = (0.022222, 0.022222)