Inexact Gradient Exact Line Search
wc_inexact_gradient_exact_line_search(L, mu, epsilon, n; verbose=true)Problem statement
Compute a PEPit worst-case guarantee for wc_inexact_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 an inexact gradient method with exact linesearch (ELS). That is, it computes the smallest possible $\tau(n, L, \mu, \varepsilon)$ such that the guarantee
\[f(x_n) - f_\star \leqslant \tau(n, L, \mu, \varepsilon) ( f(x_0) - f_\star )\]
is valid, where $x_n$ is the output of the gradient descent with an inexact descent direction and an exact linesearch, and where $x_\star$ is the minimizer of $f$.
The inexact descent direction $d$ is assumed to satisfy a relative inaccuracy described by (with $0 \leqslant \varepsilon < 1$)
\[\|\nabla f(x_t) - d_t\| \leqslant \varepsilon \|\nabla f(x_t)\|,\]
where $\nabla f(x_t)$ is the true gradient, and $d_t$ is the approximate descent direction that is used.
Algorithm
For $t \in \{0, \dots, n-1\}$,
\[ \begin{aligned} \gamma_t & = & \arg\min_{\gamma \in R^d} f(x_t- \gamma d_t), \\ x_{t+1} & = & x_t - \gamma_t d_t. \end{aligned}\]
Theoretical guarantee
The tight guarantee obtained in [1, Theorem 5.1] is
\[f(x_n) - f_\star\leqslant \left(\frac{L_{\varepsilon} - \mu_{\varepsilon}}{L_{\varepsilon} + \mu_{\varepsilon}}\right)^{2n}( f(x_0) - f_\star ),\]
with $L_{\varepsilon} = (1 + \varepsilon) L$ and $\mu_{\varepsilon} = (1 - \varepsilon) \mu$. Tightness is achieved on simple quadratic functions.
References
The detailed approach (based on convex relaxations) is available in [1],
Arguments
L: smoothness or Lipschitz parameter, as used by the modeled class.mu: strong convexity or monotonicity parameter, as used by the modeled class.epsilon: level of inaccuracy.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_inexact_gradient_exact_line_search(1.0, 0.1, 0.1, 2; verbose=true)
## Returns approximately: (pepit_tau, theoretical_tau) = (0.518917, 0.518917)