Conjugate Gradient
wc_conjugate_gradient(L, n; solver=Clarabel.Optimizer, verbose=true)Problem statement
Compute a PEPit worst-case guarantee for wc_conjugate_gradient.
Consider the convex minimization problem
\[f_\star \triangleq \min_x f(x),\]
where $f$ is $L$-smooth and convex.
Performance metric
This code computes a worst-case guarantee for the conjugate gradient (CG) method (with exact span searches). That is, it computes the smallest possible $\tau(n, L)$ such that the guarantee
\[f(x_n) - f_\star \leqslant \tau(n, L) \|x_0-x_\star\|^2\]
is valid, where $x_n$ is the output of the conjugate gradient method, and where $x_\star$ is a minimizer of $f$. 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 $\|x_0-x_\star\|^2 \leqslant 1$.
Algorithm
\[x_{t+1} = x_t - \sum_{i=0}^t \gamma_i \nabla f(x_i)\]
with\[(\gamma_i)_{i \leqslant t} = \arg\min_{(\gamma_i)_{i \leqslant t}} f \left(x_t - \sum_{i=0}^t \gamma_i \nabla f(x_i) \right)\]
Theoretical guarantee
The **tight** guarantee obtained in [1] is\[f(x_n) - f_\star \leqslant\frac{L}{2 \theta_n^2}\|x_0-x_\star\|^2.\]
where\[ \begin{aligned} \theta_0 & = & 1 \\ \theta_t & = & \frac{1 + \sqrt{4 \theta_{t-1}^2 + 1}}{2}, \forall t \in [|1, n-1|] \\ \theta_n & = & \frac{1 + \sqrt{8 \theta_{n-1}^2 + 1}}{2}, \end{aligned} and tightness follows from [2, Theorem 3].\]
References
The detailed approach (based on convex relaxations) is available in [1, Corollary 6].
Arguments
L: smoothness or Lipschitz parameter, as used by the modeled class.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 valuetheoretical_tau: theoretical value
Julia usage
pepit_tau, theoretical_tau = wc_conjugate_gradient(1.0, 2; solver=Clarabel.Optimizer, verbose=true)
## Returns approximately: (pepit_tau, theoretical_tau) = (0.061894, 0.061894)