Inexact Gradient

Source file

wc_inexact_gradient(L, mu, epsilon, n; solver=Clarabel.Optimizer, verbose=true)

Problem statement

Compute a PEPit worst-case guarantee for wc_inexact_gradient.

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 and looks for a low-dimensional worst-case example nearly achieving this worst-case guarantee using $10$ iterations of the logdet heuristic.

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 where $x_\star$ is the minimizer of $f$. Then, it looks for a low-dimensional nearly achieving this performance.

The inexact descent direction is assumed to satisfy a relative inaccuracy described by (with $0 \leqslant \varepsilon \leqslant 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

The inexact gradient descent under consideration can be written as

\[x_{t+1} = x_t - \frac{2}{L_{\varepsilon} + \mu_{\varepsilon}} d_t\]

where $d_t$ is the inexact search direction, $L_{\varepsilon} = (1 + \varepsilon)L$ and $\mu_{\varepsilon} = (1-\varepsilon) \mu$.

Theoretical guarantee

A tight worst-case guarantee obtained in [1, Theorem 5.3] or [2, Remark 1.6] 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$. This guarantee is achieved on one-dimensional quadratic functions.

References

The detailed analyses can be found in [1, 2]. The logdet heuristic is presented in [3].

[1] E. De Klerk, F. Glineur, A. Taylor (2020). Worst-case convergence analysis of inexact gradient and Newton methods through semidefinite programming performance estimation. SIAM Journal on Optimization, 30(3), 2053-2082.

[2] O. Gannot (2021). A frequency-domain analysis of inexact gradient methods. Mathematical Programming.

[3] F. Maryam, H. Hindi, S. Boyd (2003). Log-det heuristic for matrix rank minimization with applications to Hankel and Euclidean distance matrices. American Control Conference (ACC).

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.
• 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_inexact_gradient(1.0, 0.1, 0.1, 6; solver=Clarabel.Optimizer, verbose=true)
## Returns approximately: (pepit_tau, theoretical_tau) = (0.139722, 0.139731)