Subgradient Method
wc_subgradient_method(M, n, gamma; solver=Clarabel.Optimizer, verbose=true)Problem statement
Compute a PEPit worst-case guarantee for wc_subgradient_method.
Consider the minimization problem
\[f_\star \triangleq \min_x f(x),\]
where $f$ is convex and $M$-Lipschitz. This problem is a (possibly non-smooth) minimization problem.
Performance metric
This code computes a worst-case guarantee for the subgradient method. That is, it computes the smallest possible $\tau(n, M, \gamma)$ such that the guarantee
\[\min_{0 \leqslant t \leqslant n} f(x_t) - f_\star \leqslant \tau(n, M, \gamma)\]
is valid, where $x_t$ are the iterates of the subgradient method after $t\leqslant n$ steps, where $x_\star$ is a minimizer of $f$, and when $\|x_0-x_\star\|\leqslant 1$.
In short, for given values of $M$, the step-size $\gamma$ and the number of iterations $n$, $\tau(n, M, \gamma)$ is computed as the worst-case value of $\min_{0 \leqslant t \leqslant n} f(x_t) - f_\star$ when $\|x_0-x_\star\| \leqslant 1$.
Algorithm
For $t\in \{0, \dots, n-1 \}$
\[ \begin{aligned} g_{t} & \in & \partial f(x_t) \\ x_{t+1} & = & x_t - \gamma g_t \end{aligned}\]
Theoretical guarantee
The tight bound is obtained in [1, Section 3.2.3] and [2, Eq (2)]
\[\min_{0 \leqslant t \leqslant n} f(x_t)- f(x_\star) \leqslant \frac{M}{\sqrt{n+1}}\|x_0-x_\star\|,\]
and tightness follows from the lower complexity bound for this class of problems, e.g., [3, Appendix A].
References
Classical references on this topic include [1, 2].
[2] S. Boyd, L. Xiao, A. Mutapcic (2003). Subgradient Methods (lecture notes).
Arguments
M: the Lipschitz parameter.n: number of iterations.gamma: step-size parameter.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(M, n, gamma; verbose=true)
## Returns approximately: (pepit_tau, theoretical_tau) = (0.755929, 0.755929)