Heavy Ball Momentum
wc_heavy_ball_momentum(mu, L, alpha, beta, n; solver=Clarabel.Optimizer, verbose=true)Problem statement
Compute a PEPit worst-case guarantee for wc_heavy_ball_momentum.
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 Heavy-ball (HB) method, aka Polyak momentum method. That is, it computes the smallest possible $\tau(n, L, \mu, \alpha, \beta)$ such that the guarantee
\[f(x_n) - f_\star \leqslant \tau(n, L, \mu, \alpha, \beta) (f(x_0) - f_\star)\]
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$, $L$ and $\mu$, $\tau(n, L, \mu, \alpha, \beta)$ is computed as the worst-case value of $f(x_n)-f_\star$ when $f(x_0) - f_\star \leqslant 1$.
Algorithm
\[x_{t+1} = x_t - \alpha \nabla f(x_t) + \beta (x_t-x_{t-1})\]
with\[\alpha \in (0, \frac{1}{L}]\]
and\[\beta = \sqrt{(1 - \alpha \mu)(1 - L \alpha)}\]
Theoretical guarantee
The upper guarantee obtained in [2, Theorem 4] is
\[f(x_n) - f_\star \leqslant (1 - \alpha \mu)^n (f(x_0) - f_\star).\]
References
This methods was first introduce in [1, Section 2], and convergence upper bound was proven in [2, Theorem 4].
Arguments
mu: strong convexity or monotonicity parameter, as used by the modeled class.L: smoothness or Lipschitz parameter, as used by the modeled class.alpha: algorithm parameter used in the update rule.beta: operator or algorithm parameter used in the model.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(mu, L, alpha, beta, 2; verbose=true)
## Returns approximately: (pepit_tau, theoretical_tau) = (0.753493, 0.9025)