Theorem:
Let $f$ be a coercive, strictly convex and $L$-Lipschitz function, $L >0$. Denote by $\partial f(x)$ the subdifferential of $f$ at the point $x \in \mathbb R^n$. For all $x^0 \in \mathbb R^n$, there exists $(\alpha_k)_{k\geq 0}\subseteq \mathbb R$ with $\forall k, \alpha_k \geq 0$; $\sum_k \alpha_k^2 < \infty$; and $\sum_k \alpha_k = \infty$, such that the subgradient descent algorithm, $$ x^{k+1} := x^k - \alpha_k g^k, \qquad g^k \in \partial f(x^k) $$ converges to the optimal solution $x^*$ in the sense that $x^k_\mathrm{best} \xrightarrow{k\to \infty} x^*$ where $$ x^k_\mathrm{best} := \arg\min \{ f(w) : w = x_j, 0\leq j \leq k \}. $$
Proof.
The proof follows material similar to Boyd and Vandenberghe's Convex Optimization book. By definition, \begin{align*} \|x^* - x^{k+1}\|_2^2 &= \|x^k - x^*\|_2^2 - 2\alpha_k \langle g^k , x^k - x^*\rangle + \alpha_k^2 \|g^k\|_2^2 \\ &\leq \|x^k - x^*\|_2^2 - 2\alpha_k (f(x^k) - f(x^*)) + \alpha_k^2 \|g^k\|_2^2 \\ &\leq \|x^0 - x^*\|_2^2 - \sum_{j\leq k} \alpha_j (f(x^j) - f(x^*)) + \sum_{j \leq k} \alpha_j^2 \|g_j\|_2^2 \end{align*} Now, $\|x^{k+1} - x^*\|_2^2 \geq 0$ and $\|x^0 - x^*\|_2^2 = R$ for some $ R> 0$. Therefore, for $x^j_\mathrm{best}$ as defined above, it follows that \begin{align*} 2 (f(x^k_\mathrm{best}) - f(x^*)) \sum_{j\leq k} \alpha_j \leq 2 \sum_{j\leq k} (f(x^j) - f(x^*)) \leq R^2 + \sum_{j\leq k} \alpha_j^2 \|g^j\|_2^2 \end{align*} For $g \in \partial f(x)$ and $y \in \mathbb R^n$ with $f$ being $L$-Lipschitz, $|\langle g, x-y\rangle| \leq |f(x) - f(y)| \leq L \|x-y\|_2$. This, by definition of the operator norm for $\langle g, \cdot \rangle$ implies that $\|g\|_2 \leq L$. Therefore, the above expression can be rearranged as \begin{align*} f(x^k_\mathrm{best}) - f(x^*) \leq \frac{R^2 + L^2 \sum_{j\leq k} \alpha_j^2}{2\sum_{j\leq k} \alpha_j} \xrightarrow{k\to\infty} 0. \end{align*} It follows from strict convexity and coercivity of $f$ that $x^k_\mathrm{best} \xrightarrow{k\to\infty} x^*$.
