Accelerated Gradient Convex
wc_accelerated_gradient_convex(mu, L, n; solver=Clarabel.Optimizer, verbose=true)Problem statement
Compute a PEPit worst-case guarantee for wc_accelerated_gradient_convex.
Consider the convex minimization problem
\[f_\star \triangleq \min_x f(x),\]
where $f$ is $L$-smooth and $\mu$-strongly convex ($\mu$ is possibly 0).
Performance metric
This code computes a worst-case guarantee for an accelerated gradient method, a.k.a. fast gradient method [1]. That is, it computes the smallest possible $\tau(n, L, \mu)$ such that the guarantee
\[f(x_n) - f_\star \leqslant \tau(n, L, \mu) \|x_0 - x_\star\|^2\]
is valid, where $x_n$ is the output of the accelerated gradient method, and where $x_\star$ is the minimizer of $f$. In short, for given values of $n$, $L$ and $\mu$, $\tau(n, L, \mu)$ is computed as the worst-case value of $f(x_n)-f_\star$ when $\|x_0 - x_\star\|^2 \leqslant 1$.
Algorithm
Initialize $\lambda_1=1$, $y_1=x_0$. One iteration of accelerated gradient method is described by
\[\begin{align} \text{Set: }\lambda_{t+1} & = & \frac{1 + \sqrt{4\lambda_t^2 + 1}}{2} \\ x_{t} & = & y_t - \frac{1}{L} \nabla f(y_t),\\ y_{t+1} & = & x_{t} + \frac{\lambda_t-1}{\lambda_{t+1}} (x_t-x_{t-1}). \end{align}\]
Theoretical guarantee
The following worst-case guarantee can be found in e.g., [2, Theorem 4.4]:
\[f(x_n)-f_\star \leqslant \frac{L}{2}\frac{\|x_0-x_\star\|^2}{\lambda_n^2}.\]
References
Arguments
mu: strong convexity or monotonicity parameter, as used by the modeled class.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_accelerated_gradient_convex(0, 1, 1; solver=Clarabel.Optimizer, verbose=true)
## Returns approximately: (pepit_tau, theoretical_tau) = (0.166667, 0.5)