Subgradient Method Rsi Eb
wc_subgradient_method_rsi_eb(mu, L, gamma, n; solver=Clarabel.Optimizer, verbose=true)Problem statement
Compute a PEPit worst-case guarantee for wc_subgradient_method_rsi_eb.
Consider the convex minimization problem
\[f_\star \triangleq \min_x f(x),\]
where $f$ verifies the "lower" restricted secant inequality ($\mu-\text{RSI}^-$) and the "upper" error bound ($L-\text{EB}^+$) [1].
Performance metric
This code computes a worst-case guarantee for gradient descent with fixed step-size $\gamma$. That is, it computes the smallest possible $\tau(n, \mu, L, \gamma)$ such that the guarantee
\[\| x_n - x_\star \|^2 \leqslant \tau(n, \mu, L, \gamma) \| x_0 - x_\star \|^2\]
is valid, where $x_n$ is the output of gradient descent with fixed step-size $\gamma$, and where $x_\star$ is a minimizer of $f$.
In short, for given values of $n$, $L$, and $\gamma$, $\tau(n, \mu, L, \gamma)$ is computed as the worst-case value of $\| x_n - x_\star \|^2$ when $\|x_0 - x_\star\|^2 \leqslant 1$.
Algorithm
Sub-gradient descent is described by
\[x_{t+1} = x_t - \gamma \nabla f(x_t),\]
where $\gamma$ is a step-size.
Theoretical guarantee
The tight theoretical guarantee can be found in [1, Prop 1] (upper bound) and [1, Theorem 2] (lower bound):
\[\| x_n - x_\star \|^2 \leqslant (1 - 2\gamma\mu + L^2 \gamma^2)^n \|x_0-x_\star\|^2.\]
References
Definition and convergence guarantees can be found in [1].
Arguments
mu: strong convexity or monotonicity parameter, as used by the modeled class.L: smoothness or Lipschitz parameter, as used by the modeled class.gamma: step-size parameter.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_subgradient_method_rsi_eb(mu, L, mu / L^2, 4; solver=Clarabel.Optimizer, verbose=true)
## Returns approximately: (pepit_tau, theoretical_tau) = (0.960596, 0.960596)