Gradient Descent Qg Convex Decreasing
wc_gradient_descent_qg_convex_decreasing(L, n; solver=Clarabel.Optimizer, verbose=true)Problem statement
Compute a PEPit worst-case guarantee for wc_gradient_descent_qg_convex_decreasing.
Consider the convex minimization problem
\[f_\star \triangleq \min_x f(x),\]
where $f$ is quadratically upper bounded ($\text{QG}^+$ [1]), i.e. $\forall x, f(x) - f_\star \leqslant \frac{L}{2} \|x-x_\star\|^2$, and convex.
Performance metric
This code computes a worst-case guarantee for gradient descent with decreasing step-sizes. 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 gradient descent with decreasing step-sizes, 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
Gradient descent with decreasing step sizes is described by
\[x_{t+1} = x_t - \gamma_t \nabla f(x_t)\]
with
\[\gamma_t = \frac{1}{L u_{t+1}}\]
where the sequence $u$ is defined by
\[\begin{aligned} u_0 & = & 1 \\ u_{t} & = & \frac{u_{t-1}}{2} + \sqrt{\left(\frac{u_{t-1}}{2}\right)^2 + 2}, \quad \mathrm{for } t \geq 1 \end{aligned}\]
Theoretical guarantee
The tight theoretical guarantee is conjectured in [1, Conjecture A.3]:
\[f(x_n)-f_\star \leqslant \frac{L}{2 u_t} \|x_0-x_\star\|^2.\]
References
The detailed approach is available in [1, Appendix A.3].
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_gradient_descent_qg_convex_decreasing(1.0, 6; verbose=true)
## Returns approximately: (pepit_tau, theoretical_tau) = (0.105547, 0.105547)