4
$\begingroup$

I was reading up on stochastic subgradient descent, and most sources i could find via google search give quick proofs on convergence in expectation and probability, and say that proofs of almost sure convergence exist.

Can anyone point me to a proof of this claim? I would be especially interested in proving the following claim : for $f$ convex and a decreasing sequence $\gamma_k$ of steps such that $\sum_{i=1}^{\infty} \gamma_i = \infty$, $\sum_{i=1}^{\infty} \gamma_i^2 < \infty$ we have $\lim_{k \rightarrow \infty} x_k = x^* $ almost surely, where $x_k$ is a sequence generated by stochastic subgradient descent.

Improve this question
$\endgroup$
2
  • 4
    $\begingroup$ Check out Theorem 1 in On Convergence of the Stochastic Subgradient Method with On-Line Stepsize Rules sciencedirect.com/science/article/pii/0022247X86901046 $\endgroup$
    – Nawaf Bou-Rabee
    Commented Oct 30, 2016 at 19:50
  • $\begingroup$ That looks great, and has a number of interesting references as well. Thank you very much. $\endgroup$
    – user1539279
    Commented Oct 30, 2016 at 20:33

0

Reset to default

You must log in to answer this question.