# Convergence rates for the iterates of SGD on Lipschitz convex functions

Let $$f:X \rightarrow \mathbb{R}$$ be a convex and $$L$$-Lipschitz continuous function. Suppose $$f^* = \min_{x \in X} f(x) \in \mathbb{R}$$ and let $$X^* = \{x \in X : f(x) = f^*\}$$.

For a non-negative decreasing sequence $$(\eta_t)_{t \in \mathbb{N}}$$ and $$x_0 \in \mathbb{R}$$, define

$$x_{t+1} = x_t - \eta_t g_t$$, $$\quad g_t \in \partial f (x_t)$$ (the subdifferential of $$f$$ at $$x_t$$)

These are the iterates generated by the sub-Gradient descent algorithm.

1. I'm looking for pointers to convergence rate or impossibility results for the quantity $$d(x_t, X^*) = \min_{z \in X^*} \|x_t-z\|$$.

2. A similar question is related to the stochastic case (in case 1) admits a positive answer) where the iterates are defined replacing $$g_t$$ with a stochastic estimate $$\hat{g}_t$$ satisfying

• $$E[\hat{g}_t|F_t] = g_t \in \partial f(x_t)$$
• $$E[\|\hat{g}_t - g_t \|^2|F_t] \leq \sigma^2 < \infty$$ for all $$x_t$$.

where $$F_t$$ is the sigma-algebra generated by the first $$t$$ estimates.

Update

An example of convergence for $$d(x_t, X^*)$$ is given by the minimization of $$f(x)=\|x\|_1$$ with $$\eta_{t} = 1/\sqrt{t}$$. In this case, the convergence of the values (which is well-established for convex Lipschitz functions) gives $$d(x_t,X^*) \leq \|x_t\|_1 = \tilde{O}\left(1/\sqrt{t}\right)$$ (ignoring log factors). This holds (in-expectation or even with high-probability) also in the stochastic case.

I'm interested in a reference for a general convergence result (where generality is w.r.t. the objective function and the step-size schedule), or in an impossibility results negating the existence of a rate.