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.


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.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.