Heavy Ball Momentum Qg Convex
wc_heavy_ball_momentum_qg_convex(L, n; solver=Clarabel.Optimizer, verbose=true)Problem statement
Compute a PEPit worst-case guarantee for wc_heavy_ball_momentum_qg_convex.
Consider the convex minimization problem
\[f_\star \triangleq \min_x f(x),\]
where $f$ is quadratically upper bounded ($\text{QG}^+$ [2]), i.e. $\forall x, f(x) - f_\star \leqslant \frac{L}{2} \|x-x_\star\|^2$, and convex.
Performance metric
This code computes a worst-case guarantee for the Heavy-ball (HB) method, aka Polyak momentum method. That is, it computes the smallest possible $\tau(n, L)$ such that the guarantee
\[f(x_n) - f_\star \leqslant \tau(n, L) \|x_0 - x_\star\|^2\]
is valid, where $x_n$ is the output of the Heavy-ball (HB) method, and where $x_\star$ is the minimizer of $f$. In short, for given values of $n$ and $L$, $\tau(n, L)$ is computed as the worst-case value of $f(x_n)-f_\star$ when $\|x_0 - x_\star\|^2 \leqslant 1$.
Algorithm
This method is described in [1]
\[x_{t+1} = x_t - \alpha_t \nabla f(x_t) + \beta_t (x_t-x_{t-1})\]
with\[\alpha_t = \frac{1}{L} \frac{1}{t+2}\]
and\[\beta_t = \frac{t}{t+2}\]
Theoretical guarantee
The tight guarantee obtained in [2, Theorem 2.3] (lower) and [2, Theorem 2.4] (upper) is
\[f(x_n) - f_\star \leqslant \frac{L}{2}\frac{1}{n+1} \|x_0 - x_\star\|^2.\]
References
This methods was first introduce in [1, section 3], and convergence tight bound was proven in [2, Theorem 2.3] (lower) and [2, Theorem 2.4] (upper).
Arguments
L: smoothness or Lipschitz parameter, as used by the modeled class.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 valuetheoretical_tau: theoretical value
Julia usage
pepit_tau, theoretical_tau = wc_heavy_ball_momentum_qg_convex(1, 5; verbose=true)
## Returns approximately: (pepit_tau, theoretical_tau) = (0.083333, 0.083333)