Gradient Exact Line Search
wc_gradient_exact_line_search(L, mu, n; verbose=true)Problem statement
Compute a PEPit worst-case guarantee for wc_gradient_exact_line_search.
Consider the convex minimization problem
\[f_\star \triangleq \min_x f(x),\]
where $f$ is $L$-smooth and $\mu$-strongly convex.
Performance metric
This code computes a worst-case guarantee for the gradient descent (GD) with exact linesearch (ELS). 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) (f(x_0) - f_\star)\]
is valid, where $x_n$ is the output of the GD with ELS, 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 $f(x_0) - f_\star \leqslant 1$.
Algorithm
GD with ELS can be written as
\[x_{t+1} = x_t - \gamma_t \nabla f(x_t)\]
with $\gamma_t = \arg\min_{\gamma} f \left( x_t - \gamma \nabla f(x_t) \right)$.
Theoretical guarantee
The tight worst-case guarantee for GD with ELS, obtained in [1, Theorem 1.2], is
\[f(x_n) - f_\star \leqslant \left(\frac{L-\mu}{L+\mu}\right)^{2n} (f(x_0) - f_\star).\]
References
The detailed approach (based on convex relaxations) is available in [1], along with theoretical bound.
Arguments
L: smoothness or Lipschitz parameter, as used by the modeled class.mu: strong convexity or monotonicity parameter, as used by the modeled class.n: number of iterations.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_exact_line_search(1.0, 0.1, 2; verbose=true)
## Returns approximately: (pepit_tau, theoretical_tau) = (0.448125, 0.448125)