Gradient Descent Lyapunov 2
wc_gradient_descent_lyapunov_2(L, gamma, n; solver=Clarabel.Optimizer, verbose=true)Problem statement
Compute a PEPit worst-case guarantee for wc_gradient_descent_lyapunov_2.
Consider the convex minimization problem
\[f_\star \triangleq \min_x f(x),\]
where $f$ is $L$-smooth and convex.
Performance metric
This code verifies a worst-case guarantee for gradient descent with fixed step-size $\gamma$. That is, it verifies that the Lyapunov (or potential/energy) function
\[V_n \triangleq (2n + 1) L \left(f(x_n) - f_\star\right) + n(n+2) \|\nabla f(x_n)\|^2 + L^2 \|x_n - x_\star\|^2\]
is decreasing along all trajectories and all smooth convex function $f$ (i.e., in the worst-case):
\[V_{n+1} \leqslant V_n,\]
where $x_{n+1}$ is obtained from a gradient step from $x_{n}$ with fixed step-size $\gamma=\frac{1}{L}$.
Algorithm
Onte iteration of radient descent is described by
\[x_{n+1} = x_n - \gamma \nabla f(x_n),\]
where $\gamma$ is a step-size.
Theoretical guarantee
The theoretical guarantee can be found in [1, Theorem 3]:
\[V_{n+1} - V_n \leqslant 0,\]
when $\gamma=\frac{1}{L}$.
References
The detailed potential function and SDP approach can be found in [1].
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_gradient_descent_lyapunov_2(L, 1 / L, 10; verbose=true)
## Returns approximately: (pepit_tau, theoretical_tau) = (0.0, 0.0)