Epsilon Subgradient Method
wc_epsilon_subgradient_method(M, n, gamma, eps, R; solver=Clarabel.Optimizer, verbose=true)Problem statement
Compute a PEPit worst-case guarantee for wc_epsilon_subgradient_method.
Consider the minimization problem
\[f_\star \triangleq \min_x f(x),\]
where $f$ is closed, convex, and proper. This problem is a (possibly non-smooth) minimization problem.
Performance metric
This code computes a worst-case guarantee for the $\varepsilon$ -subgradient method. That is, it computes the smallest possible $\tau(n, M, \gamma, \varepsilon, R)$ such that the guarantee
\[\min_{0 \leqslant t \leqslant n} f(x_t) - f_\star \leqslant \tau(n, M, \gamma, \varepsilon, R)\]
is valid, where $x_t$ are the iterates of the $\varepsilon$ -subgradient method after $t\leqslant n$ steps, where $x_\star$ is a minimizer of $f$, where $M$ is an upper bound on the norm of all $\varepsilon$-subgradients encountered, and when $\|x_0-x_\star\|\leqslant R$.
In short, for given values of $M$, of the accuracy $\varepsilon$, of the step-size $\gamma$, of the initial distance $R$, and of the number of iterations $n$, $\tau(n, M, \gamma, \varepsilon, R)$ is computed as the worst-case value of $\min_{0 \leqslant t \leqslant n} f(x_t) - f_\star$.
Algorithm
For $t\in \{0, \dots, n-1 \}$
\[ \begin{aligned} g_{t} & \in & \partial_{\varepsilon} f(x_t) \\ x_{t+1} & = & x_t - \gamma g_t \end{aligned}\]
Theoretical guarantee
An upper bound is obtained in [1, Lemma 2]:
\[\min_{0 \leqslant t \leqslant n} f(x_t)- f(x_\star) \leqslant \frac{R^2+2(n+1)\gamma\varepsilon+(n+1) \gamma^2 M^2}{2(n+1) \gamma}.\]
References
Arguments
M: the bound on norms of epsilon-subgradients.n: number of iterations.gamma: step-size parameter.eps: the bound on the value of epsilon (inaccuracy).R: the bound on initial distance to an optimal solution.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_epsilon_subgradient_method(M, n, gamma, eps, R; verbose=true)
## Returns approximately: (pepit_tau, theoretical_tau) = (1.019156, 1.044911)