Improved Interior Algorithm
wc_improved_interior_algorithm(L, mu, c, lam, n; verbose=true)Problem statement
Compute a PEPit worst-case guarantee for wc_improved_interior_algorithm.
Consider the composite convex minimization problem
\[F_\star \triangleq \min_x \{F(x) \equiv f_1(x) + f_2(x)\},\]
where $f_1$ is a $L$-smooth convex function, and $f_2$ is a closed convex indicator function. We use a kernel function $h$ that is assumed to be closed, proper, and strongly convex (see [1, Section 5]).
Performance metric
This code computes a worst-case guarantee for Improved interior gradient algorithm (IGA). That is, it computes the smallest possible $\tau(\mu,L,c,\lambda,n)$ such that the guarantee
\[F(x_n) - F(x_\star) \leqslant \tau(\mu,L,c,\lambda,n) (c D_h(x_\star;x_0) + f_1(x_0) - f_1(x_\star))\]
is valid, where $x_n$ is the output of the IGA and where $x_\star$ is a minimizer of $F$ and $D_h$ is the Bregman distance generated by $h$.
In short, for given values of $\mu$, $L$, $c$, $\lambda$ and $n$, $\tau(\mu,L,c,\lambda,n)$ is computed as the worst-case value of $F(x_n)-F_\star$ when $c D_h(x_\star;x_0) + f_1(x_0) - f_1(x_\star)\leqslant 1$.
Algorithm
The IGA is described in [1, "Improved Interior Gradient Algorithm"]. For $t \in \{0, \dots, n-1\}$,
\[ \begin{aligned} \alpha_t & = & \frac{\sqrt{(c_t\lambda)^2+4c_t\lambda}-\lambda c_t}{2},\\ y_t & = & (1-\alpha_t) x_t + \alpha_t z_t,\\ c_{t+1} & = & (1-\alpha_t)c_t,\\ z_{t+1} & = & \arg\min_{z} \left\{ \left< z;\frac{\alpha_t}{c_{t+1}}\nabla f_1(y_t)\right> +f_2(z)+D_h(z;z_t)\right\}, \\ x_{t+1} & = & (1-\alpha_t) x_t + \alpha_t z_{t+1}. \end{aligned}\]
Theoretical guarantee
The following upper bound can be found in [1, Theorem 5.2]:
\[F(x_n) - F_\star \leqslant \frac{4L}{c n^2}\left(c D_h(x_\star;x_0) + f_1(x_0) - f_1(x_\star) \right).\]
References
Arguments
L: smoothness or Lipschitz parameter, as used by the modeled class.mu: strong convexity or monotonicity parameter, as used by the modeled class.c: initial value.lam: the step-size.n: number of iterations.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_improved_interior_algorithm(1.0, 1.0, 1.0, 1.0, 5; verbose=true)
## Returns approximately: (pepit_tau, theoretical_tau) = (0.06807, 0.111111)