Gradient Descent Lyapunov 1
wc_gradient_descent_lyapunov_1(L, gamma, n; solver=Clarabel.Optimizer, verbose=true)Problem statement
Compute a PEPit worst-case guarantee for wc_gradient_descent_lyapunov_1.
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 n (f(x_n) - f_\star) + \frac{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 gradient 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 e.g., [1, Theorem 3.3]:
\[V_{n+1} - V_n \leqslant 0,\]
when $\gamma=\frac{1}{L}$.
References
The detailed potential function can found in [1] and the SDP approach can be found in [2].
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_1(1.0, 1.0, 10; verbose=true)
## Returns approximately: (pepit_tau, theoretical_tau) = (0.0, 0.0)